mlsanityData to 7 Oct 2026

Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation

arXiv 2008.10715 ↗First posted 24 Aug 2020cs.CRcited by 57

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 15; 2023: 11; 2024: 12; 2025: 10; 2026: 7.

57 papers.

Sort:

By area:

  1. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  2. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  3. 2022Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspectivecited by 41
  4. 2022PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learningcited by 33
  5. 2023Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attackscited by 32
  6. 2022FLCert: Provably Secure Federated Learning against Poisoning Attackscited by 29
  7. 2021A Hard Label Black-box Adversarial Attack Against Graph Neural Networkscited by 26
  8. 2024Graph Neural Networks for Financial Fraud Detection: A Reviewcited by 24
  9. 2022Scalable Verification of GNN-based Job Schedulerscited by 18
  10. 2022Dimensionless machine learning: Imposing exact units equivariancecited by 16
  11. 2022Projective Ranking-based GNN Evasion Attackscited by 14
  12. 2023Incremental Randomized Smoothing Certificationcited by 12
38 more
  1. 2022Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attackcited by 10
  2. 2022UniCR: Universally Approximated Certified Robustness via Randomized Smoothingcited by 10
  3. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  4. 2022Confidence-aware Training of Smoothed Classifiers for Certified Robustnesscited by 9
  5. 2023Robust Spatiotemporal Traffic Forecasting with Reinforced Dynamic Adversarial Trainingcited by 9
  6. 2023Hierarchical Randomized Smoothingcited by 9
  7. 2022A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunitiescited by 8
  8. 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
  9. 2024Graph Neural Network Causal Explanation via Neural Causal Modelscited by 8
  10. 2024DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Modelscited by 8
  11. 2023Adversarially Robust Neural Architecture Search for Graph Neural Networkscited by 7
  12. 2024Robustness Inspired Graph Backdoor Defensecited by 7
  13. 2022(De-)Randomized Smoothing for Decision Stump Ensemblescited by 5
  14. 2023A Certified Radius-Guided Attack Framework to Image Segmentation Modelscited by 5
  15. 2023Certifiably Robust Graph Contrastive Learningcited by 5
  16. 2022Pre-trained Encoders in Self-Supervised Learning Improve Secure and Privacy-preserving Supervised Learningcited by 4
  17. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  18. 2024Collective Certified Robustness against Graph Injection Attackscited by 3
  19. 2024Tensor learning with orthogonal, Lorentz, and symplectic symmetriescited by 3
  20. 2024Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphscited by 3
  21. 2024Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Methodcited by 3
  22. 2025Watermarking Graph Neural Networks via Explanations for Ownership Protectioncited by 3
  23. 2025Backdoor Attacks on Discrete Graph Diffusion Modelscited by 3
  24. 2025Graph Prompting for Graph Learning Models: Recent Advances and Future Directionscited by 3
  25. 2023Graph Adversarial Immunization for Certifiable Robustnesscited by 2
  26. 2023Structure-Aware Robustness Certificates for Graph Classificationcited by 2
  27. 2023Everything Perturbed All at Once: Enabling Differentiable Graph Attackscited by 2
  28. 2025Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbationscited by 2
  29. 2025Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifiercited by 2
  30. 2022Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Modelcited by 1
  31. 2022Detecting Topology Attacks against Graph Neural Networkscited by 1
  32. 2024AutoRNet: Automatically Optimizing Heuristics for Robust Network Design via Large Language Modelscited by 1
  33. 2025AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothingcited by 1
  34. 2025Community detection robustness of graph neural networkscited by 1
  35. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  36. 2024Defense-as-a-Service: Black-box Shielding against Backdoored Graph Modelscited by 0
  37. 2025Principal Eigenvalue Regularization for Improved Worst-Class Certified Robustness of Smoothed Classifierscited by 0
  38. 2025Adaptive Branch Specialization in Spectral-Spatial Graph Neural Networks for Certified Robustnesscited by 0

50 most cited of 57 All 57 (JSON)