Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations
Not on the map. Why?
Abstract (arXiv)
Graph neural networks (GNNs) are becoming the de facto method to learn on the graph data and have achieved the state-of-the-art on node and graph classification tasks. However, recent works show GNNs are vulnerable to training-time poisoning attacks -- marginally perturbing edges, nodes, or/and node features of training graph(s) can largely degrade GNNs' testing performance. Most previous defenses against graph poisoning attacks are empirical and are soon broken by adaptive / stronger ones. A few provable defenses provide robustness guarantees, but have large gaps when applied in practice: 1) restrict the attacker on only one type of perturbation; 2) design for a particular GNN architecture or task; and 3) robustness guarantees are not 100% accurate. In this work, we bridge all these gaps by developing PGNNCert, the first certified defense of GNNs against poisoning attacks under arbitrary (edge, node, and node feature) perturbations with deterministic robustness guarantees. Extensive evaluations on multiple node and graph classification datasets and GNNs demonstrate the effectiveness of PGNNCert to provably defend against arbitrary poisoning perturbations. PGNNCert is also shown to significantly outperform the state-of-the-art certified defenses against edge perturbation or node perturbation during GNN training.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 44 of its 63 references that are in the map. First posted on arXiv 24 Mar 2025.
Builds on
44 of 63 references.
References · 44
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Graph Attention Networkscited by 8,854
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
- 2019Graph Neural Networks for Social Recommendationcited by 711
- 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
- 2018Adversarial Attack on Graph Structured Datacited by 300
- 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
- 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
- 2020Backdoor Attacks to Graph Neural Networkscited by 126
- 2020Deep Partition Aggregation: Provable Defense against General Poisoning Attackscited by 112
32 more
- 2020Certified Robustness to Label-Flipping Attacks via Randomized Smoothingcited by 103
- 2021Graph Neural Networks in Network Neurosciencecited by 91
- 2020Intrinsic Certified Robustness of Bagging against Data Poisoning Attackscited by 90
- 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
- 2020On Certifying Robustness against Backdoor Attacks via Randomized Smoothingcited by 74
- 2021Extract the Knowledge of Graph Neural Networks and Go Beyond it: An Effective Knowledge Distillation Frameworkcited by 69
- 2020GraphFL: A Federated Learning Framework for Semi-Supervised Node Classification on Graphscited by 64
- 2019Transferring Robustness for Graph Neural Network Against Poisoning Attackscited by 58
- 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
- 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
- 2019Attacking Graph-based Classification via Manipulating the Graph Structurecited by 53
- 2023Unnoticeable Backdoor Attacks on Graph Neural Networkscited by 45
- 2023Are Defenses for Graph Neural Networks Robust?cited by 38
- 2019Attacking Graph Convolutional Networks via Rewiringcited by 32
- 2019A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learningcited by 30
- 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
- 2021A Hard Label Black-box Adversarial Attack Against Graph Neural Networkscited by 26
- 2022Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learningcited by 19
- 2024Graph Neural Network Explanations are Fragilecited by 18
- 2020Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networkscited by 16
- 2024Distributed Backdoor Attacks on Federated Graph Learning and Certified Defensescited by 15
- 2020Adversarial Immunization for Certifiable Robustness on Graphscited by 14
- 2020Efficient, Direct, and Restricted Black-Box Graph Evasion Attacks to Any-Layer Graph Neural Networks via Influence Functioncited by 14
- 2023Turning Strengths into Weaknesses: A Certified Robustness Inspired Attack Framework against Graph Neural Networkscited by 11
- 2022Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guaranteescited by 9
- 2023PORE: Provably Robust Recommender Systems against Data Poisoning Attackscited by 9
- 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
- 2024Graph Neural Network Causal Explanation via Neural Causal Modelscited by 8
- 2025Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attackscited by 6
- 2020Semi-Supervised Node Classification on Graphs: Markov Random Fields vs. Graph Neural Networkscited by 5
- 2025AGNNCert: Defending Graph Neural Networks against Arbitrary Perturbations with Deterministic Certificationcited by 4
- 2024Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Methodcited by 3
Built on by
Citing papers per year: 2026: 2.
2 papers.