Certifying Graph Neural Networks Against Label and Structure Poisoning

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.

Slightly manipulated or corrupted training data can have a huge detrimental effect on the resulting trained machine learning models. In this work, we focus on machine learning models for graph datasets and develop a method that allows us to mathematically prove the worst-case effect that corrupted training data could have on our trained graph models. In particular, our method is designed for learning tasks on graphs, where some nodes in the graph are labeled and we want to infer the labels of the remaining nodes in the graph. Then, our method can be used to calculate the worst-case effect on the trained graph model of having either a certain fraction of corrupted training labels, a certain fraction of wrong links between nodes, or both.