cs.LGNov 2, 2026

Certifying Graph Neural Networks Against Label and Structure Poisoning

Authors: Lukas Gosch, Xichuan Chen, Yan Scholten, Stephan Günnemann

Organizations: School of Computation, Information and Technology, Technical University of Munich · Munich Data Science Institute (MDSI), Technical University of Munich · Munich Center for Machine Learning (MCML)

Abstract

Robust machine learning for graph-structured data has made significant progress against test-time attacks, yet certified robustness to poisoning - where adversaries manipulate the training data - remains largely underexplored. For image data, state-of-the-art poisoning certificates rely on partitioning-and-aggregation schemes. However, we show that these methods fail when applied in the graph domain due to the inherent label and structure sparsity found in common graph datasets, making effective graph-partitioning difficult. To address this challenge, we propose a novel semi-supervised learning framework called deep Self-Training Graph Partition Aggregation (ST-GPA), which enriches each graph partition with informative pseudo-labels and synthetic edges, enabling effective certification against node-label and graph-structure poisoning under sparse conditions. Our method is architecture-agnostic, scales to large numbers of partitions, and consistently and significantly improves robustness guarantees against both label and structure poisoning across multiple benchmarks, while maintaining strong clean accuracy. Overall, our results establish a promising direction for certifiably robust learning on graph-structured data against poisoning under sparse conditions.

Figures & tables

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Contrastive Adversarial Training for Robust Graph Neural Networks under Label Poisoning

    Oct 17, 2026Manshika Charvi Bissessur, Melis Ilayda Bal, Michael MuehlebachGraph Neural NetworksRobust Classification

  2. Trust-But-Verify: Poisoning-Resilient Locally Private Graph Learning Protocols

    Sep 7, 2026Longzhu He, Li Sun, Hao Peng +3Data Poisoning AttacksDecentralized Learning

  3. Are LLM-Enhanced Graph Neural Networks Robust against Poisoning Attacks?

    Mar 27, 2026Yuhang Ma, Jie Wang, Zheng YanGraph Neural NetworksAdversarial Robustness