# Certifiable Robustness and Robust Training for Graph Convolutional Networks

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

## Key facts

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

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

- [Subgraph Federated Learning with Missing Neighbor Generation](https://mlsanity.com/paper/2106.13430/) (2021)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [Model Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2112.08331/) (2021)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [Understanding Structural Vulnerability in Graph Convolutional Networks](https://mlsanity.com/paper/2108.06280/) (2021)
- [How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications](https://mlsanity.com/paper/2106.07767/) (2021)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Decentralized Inference with Graph Neural Networks in Wireless Communication Systems](https://mlsanity.com/paper/2104.09027/) (2021)
- [Stability of Graph Convolutional Neural Networks to Stochastic Perturbations](https://mlsanity.com/paper/2106.10526/) (2021)
- [Robust Mid-Pass Filtering Graph Convolutional Networks](https://mlsanity.com/paper/2302.08048/) (2023)
- [Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks](https://mlsanity.com/paper/2302.02829/) (2023)
- [Spectral Adversarial Training for Robust Graph Neural Network](https://mlsanity.com/paper/2211.10896/) (2022)
- [Adversarial Camouflage for Node Injection Attack on Graphs](https://mlsanity.com/paper/2208.01819/) (2022)
- [Robust Graph Neural Networks via Probabilistic Lipschitz Constraints](https://mlsanity.com/paper/2112.07575/) (2021)
- [Localized Randomized Smoothing for Collective Robustness Certification](https://mlsanity.com/paper/2210.16140/) (2022)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [A Survey on Verification and Validation, Testing and Evaluations of Neurosymbolic Artificial Intelligence](https://mlsanity.com/paper/2401.03188/) (2024)
- [Verifying message-passing neural networks via topology-based bounds tightening](https://mlsanity.com/paper/2402.13937/) (2024)
- [BinarizedAttack: Structural Poisoning Attacks to Graph-based Anomaly Detection](https://mlsanity.com/paper/2106.09989/) (2021)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks](https://mlsanity.com/paper/2404.17947/) (2024)
- [Graph Computing for Financial Crime and Fraud Detection: Trends, Challenges and Outlook](https://mlsanity.com/paper/2103.03227/) (2021)
- [Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure](https://mlsanity.com/paper/2404.15065/) (2024)
- [DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models](https://mlsanity.com/paper/2412.08160/) (2024)
- [Neighboring Backdoor Attacks on Graph Convolutional Network](https://mlsanity.com/paper/2201.06202/) (2022)
- [Invariance-Aware Randomized Smoothing Certificates](https://mlsanity.com/paper/2211.14207/) (2022)
- [On the Prediction Instability of Graph Neural Networks](https://mlsanity.com/paper/2205.10070/) (2022)

## 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.