mlsanityData to 7 Oct 2026

Certifiable Robustness and Robust Training for Graph Convolutional Networks

arXiv 1906.12269 ↗First posted 28 Jun 2019cs.LG cs.CR stat.MLcited by 59

Not on the map. Why?

Abstract (arXiv)

Recent works show that Graph Neural Networks (GNNs) are highly non-robust with respect to adversarial attacks on both the graph structure and the node attributes, making their outcomes unreliable. We propose the first method for certifiable (non-)robustness of graph convolutional networks with respect to perturbations of the node attributes. We consider the case of binary node attributes (e.g. bag-of-words) and perturbations that are L_0-bounded. If a node has been certified with our method, it is guaranteed to be robust under any possible perturbation given the attack model. Likewise, we can certify non-robustness. Finally, we propose a robust semi-supervised training procedure that treats the labeled and unlabeled nodes jointly. As shown in our experimental evaluation, our method significantly improves the robustness of the GNN with only minimal effect on the predictive accuracy.

Key facts. Cited by 59 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 14; 2022: 13; 2023: 14; 2024: 13; 2025: 5.

59 papers.

Sort:

By area:

  1. 2021Subgraph Federated Learning with Missing Neighbor Generationcited by 132
  2. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  3. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  4. 2021Robust Counterfactual Explanations on Graph Neural Networkscited by 72
  5. 2022Graph Data Augmentation for Graph Machine Learning: A Surveycited by 61
  6. 2021Model Stealing Attacks Against Inductive Graph Neural Networkscited by 50
  7. 2021Single Node Injection Attack against Graph Neural Networkscited by 45
  8. 2021Understanding Structural Vulnerability in Graph Convolutional Networkscited by 37
  9. 2021How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implicationscited by 21
  10. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  11. 2021Decentralized Inference with Graph Neural Networks in Wireless Communication Systemscited by 18
  12. 2021Stability of Graph Convolutional Neural Networks to Stochastic Perturbationscited by 18
38 more
  1. 2023Robust Mid-Pass Filtering Graph Convolutional Networkscited by 17
  2. 2023Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networkscited by 16
  3. 2022Spectral Adversarial Training for Robust Graph Neural Networkcited by 12
  4. 2022Adversarial Camouflage for Node Injection Attack on Graphscited by 11
  5. 2021Robust Graph Neural Networks via Probabilistic Lipschitz Constraintscited by 10
  6. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10
  7. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  8. 2024A Survey on Verification and Validation, Testing and Evaluations of Neurosymbolic Artificial Intelligencecited by 10
  9. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  10. 2023Hierarchical Randomized Smoothingcited by 9
  11. 2024Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attackscited by 9
  12. 2021Graph Computing for Financial Crime and Fraud Detection: Trends, Challenges and Outlookcited by 8
  13. 2021BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detectioncited by 8
  14. 2024Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structurecited by 8
  15. 2024DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Modelscited by 8
  16. 2022Neighboring Backdoor Attacks on Graph Convolutional Networkcited by 7
  17. 2022Invariance-Aware Randomized Smoothing Certificatescited by 7
  18. 2022On the Prediction Instability of Graph Neural Networkscited by 6
  19. 2023Certifiably Robust Graph Contrastive Learningcited by 5
  20. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  21. 2024SafePowerGraph: Safety-aware Evaluation of Graph Neural Networks for Transmission Power Gridscited by 5
  22. 2021Adversarially Regularized Graph Attention Networks for Inductive Learning on Partially Labeled Graphscited by 4
  23. 2022EDoG: Adversarial Edge Detection For Graph Neural Networkscited by 4
  24. 2023IDEA: Invariant Defense for Graph Adversarial Robustnesscited by 4
  25. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  26. 2023Provable Training for Graph Contrastive Learningcited by 3
  27. 2024Faithful Interpretation for Graph Neural Networkscited by 3
  28. 2025Covariance Density Neural Networkscited by 3
  29. 2021BiGCN: A Bi-directional Low-Pass Filtering Graph Neural Networkcited by 2
  30. 2022How Powerful is Implicit Denoising in Graph Neural Networkscited by 2
  31. 2023Graph Adversarial Immunization for Certifiable Robustnesscited by 2
  32. 2023Structure-Aware Robustness Certificates for Graph Classificationcited by 2
  33. 2023On the Robustness of Post-hoc GNN Explainers to Label Noisecited by 2
  34. 2023On the Trade-Off between Stability and Representational Capacity in Graph Neural Networkscited by 2
  35. 2024A Benchmark for Fairness-Aware Graph Learningcited by 2
  36. 2024When Witnesses Defend: A Witness Graph Topological Layer for Adversarial Graph Learningcited by 2
  37. 2021Adversarial Robustness of Probabilistic Network Embedding for Link Predictioncited by 1
  38. 2023Can Directed Graph Neural Networks be Adversarially Robust?cited by 1

50 most cited of 59 All 59 (JSON)