# Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation

arXiv: https://arxiv.org/abs/2008.10715 · HTML: https://mlsanity.com/paper/2008.10715/

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2020.

## Built on by (most cited first, 30 of 57)

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspective](https://mlsanity.com/paper/2206.12227/) (2022)
- [PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learning](https://mlsanity.com/paper/2205.06401/) (2022)
- [Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attacks](https://mlsanity.com/paper/2307.16630/) (2023)
- [FLCert: Provably Secure Federated Learning against Poisoning Attacks](https://mlsanity.com/paper/2210.00584/) (2022)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Graph Neural Networks for Financial Fraud Detection: A Review](https://mlsanity.com/paper/2411.05815/) (2024)
- [Scalable Verification of GNN-based Job Schedulers](https://mlsanity.com/paper/2203.03153/) (2022)
- [Dimensionless machine learning: Imposing exact units equivariance](https://mlsanity.com/paper/2204.00887/) (2022)
- [Projective Ranking-based GNN Evasion Attacks](https://mlsanity.com/paper/2202.12993/) (2022)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attack](https://mlsanity.com/paper/2202.07114/) (2022)
- [UniCR: Universally Approximated Certified Robustness via Randomized Smoothing](https://mlsanity.com/paper/2207.02152/) (2022)
- [Verifying message-passing neural networks via topology-based bounds tightening](https://mlsanity.com/paper/2402.13937/) (2024)
- [A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunities](https://mlsanity.com/paper/2210.08906/) (2022)
- [Confidence-aware Training of Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2212.09000/) (2022)
- [Robust Spatiotemporal Traffic Forecasting with Reinforced Dynamic Adversarial Training](https://mlsanity.com/paper/2306.14126/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models](https://mlsanity.com/paper/2412.08160/) (2024)
- [Adversarially Robust Neural Architecture Search for Graph Neural Networks](https://mlsanity.com/paper/2304.04168/) (2023)
- [Robustness Inspired Graph Backdoor Defense](https://mlsanity.com/paper/2406.09836/) (2024)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [Certifiably Robust Graph Contrastive Learning](https://mlsanity.com/paper/2310.03312/) (2023)
- [Pre-trained Encoders in Self-Supervised Learning Improve Secure and Privacy-preserving Supervised Learning](https://mlsanity.com/paper/2212.03334/) (2022)
- [Exact Verification of Graph Neural Networks with Incremental Constraint Solving](https://mlsanity.com/paper/2508.09320/) (2025)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)

## Abstract (arXiv)

Graph neural networks (GNNs) have recently gained much attention for node and graph classification tasks on graph-structured data. However, multiple recent works showed that an attacker can easily make GNNs predict incorrectly via perturbing the graph structure, i.e., adding or deleting edges in the graph. We aim to defend against such attacks via developing certifiably robust GNNs. Specifically, we prove the certified robustness guarantee of any GNN for both node and graph classifications against structural perturbation. Moreover, we show that our certified robustness guarantee is tight. Our results are based on a recently proposed technique called randomized smoothing, which we extend to graph data. We also empirically evaluate our method for both node and graph classifications on multiple GNNs and multiple benchmark datasets. For instance, on the Cora dataset, Graph Convolutional Network with our randomized smoothing can achieve a certified accuracy of 0.49 when the attacker can arbitrarily add/delete at most 15 edges in the graph.