Skip to content

Certified graph neural networks against label and structure poisoning

Certifying Graph Neural Networks Against Label and Structure Poisoning

arXiv: Adversarial Attacks, Backdoors & Poisoning· arXiv:2611.03350· ICML 2026· Lukas Gosch, Xichuan Chen, Yan Scholten, Stephan GünnemannSchool of Computation, Information and Technology, Technical University of Munich; Munich Data Science Institute (MDSI), Technical University of Munich; Munich Center for Machine Learning (MCML)Indexed by this site · 16 days ago· Originally publishedDefenses

Translation in progress — untranslated text is omitted.

Quick read

Defenses

Based on the paper PDF (AI-generated); refer to the original

AI summaryThe study proposes a semi-supervised framework, ST-GPA, for certifying graph neural networks against label poisoning and structure poisoning under conditions of sparse labels and sparse structure in graph data. The method supplements each graph partition with pseudo-labels and synthetic edges, can adapt to different architectures and scale to a large number of partitions. On multiple benchmarks, ST-GPA consistently and significantly improves robustness guarantees against label and structure poisoning while maintaining strong clean accuracy.

Questions
Graph neural networks lack provable robustness guarantees against label flipping and structural poisoning at training time; the partition-and-aggregate certification that is mainstream in the image domain fails when applied directly to graphs, due to the sparsity of labels and edges.
Methods
Propose ST-GPA: hash graph labels or edges into partitions, on each sparse partition use label propagation co-training and GNN self-training to generate pseudo-labels, use confidence-based link prediction to generate pseudo-edges, then train a GNN base classifier and take majority vote to provide certification.
Experiments and results
On datasets such as Cora-ML and PubMed, the authors claim ST-GPA restores ensemble clean accuracy to about 70%–80% and improves certified accuracy; on binary Cora-ML with 10% label perturbation, certified accuracy is 36.2%, higher than LabelCert's 32.6% (Table 4).
Limitations and future work
The authors note that the semi-supervised component relies on homophily, and heterophilous graphs require new methods; link prediction is expensive on large, dense graphs, and structural certification is difficult to scale to ogbn-arxiv; certificate tightness is only roughly checked via non-adaptive transfer attacks.

Related papers

Show 1 more papers
Read originalICML 2026