# Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 38 references that are in the map.
- First posted on arXiv 6 Feb 2023.

## Builds on (most cited first, 24 of 24)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (2018)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Adversarial Attacks and Defenses in Images, Graphs and Text: A Review](https://mlsanity.com/paper/1909.08072/) (2019)
- [Graph Adversarial Training: Dynamically Regularizing Based on Graph Structure](https://mlsanity.com/paper/1902.08226/) (2019)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Detection as Regression: Certified Object Detection by Median Smoothing](https://mlsanity.com/paper/2007.03730/) (2020)
- [Reliable Graph Neural Networks via Robust Aggregation](https://mlsanity.com/paper/2010.15651/) (2020)
- [Dynamic Divide-and-Conquer Adversarial Training for Robust Semantic Segmentation](https://mlsanity.com/paper/2003.06555/) (2020)
- [Adversarial Attack and Defense of Structured Prediction Models](https://mlsanity.com/paper/2010.01610/) (2020)
- [Uncertainty-aware Attention Graph Neural Network for Defending Adversarial Attacks](https://mlsanity.com/paper/2009.10235/) (2020)
- [DefenseVGAE: Defending against Adversarial Attacks on Graph Data via a Variational Graph Autoencoder](https://mlsanity.com/paper/2006.08900/) (2020)
- [EDoG: Adversarial Edge Detection For Graph Neural Networks](https://mlsanity.com/paper/2212.13607/) (2022)
- [Robust Collective Classification against Structural Attacks](https://mlsanity.com/paper/2007.13073/) (2020)

## Built on by (most cited first, 16 of 16)

- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [A Simple and Yet Fairly Effective Defense for Graph Neural Networks](https://mlsanity.com/paper/2402.13987/) (2024)
- [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)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [IDEA: Invariant Defense for Graph Adversarial Robustness](https://mlsanity.com/paper/2305.15792/) (2023)
- [Provable Training for Graph Contrastive Learning](https://mlsanity.com/paper/2309.13944/) (2023)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [Graph Adversarial Immunization for Certifiable Robustness](https://mlsanity.com/paper/2302.08051/) (2023)
- [Effective Data Pruning through Score Extrapolation](https://mlsanity.com/paper/2506.09010/) (2025)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation](https://mlsanity.com/paper/2405.08645/) (2024)
- [Principal Eigenvalue Regularization for Improved Worst-Class Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2503.17172/) (2025)

## Abstract (arXiv)

In tasks like node classification, image segmentation, and named-entity recognition we have a classifier that simultaneously outputs multiple predictions (a vector of labels) based on a single input, i.e. a single graph, image, or document respectively. Existing adversarial robustness certificates consider each prediction independently and are thus overly pessimistic for such tasks. They implicitly assume that an adversary can use different perturbed inputs to attack different predictions, ignoring the fact that we have a single shared input. We propose the first collective robustness certificate which computes the number of predictions that are simultaneously guaranteed to remain stable under perturbation, i.e. cannot be attacked. We focus on Graph Neural Networks and leverage their locality property - perturbations only affect the predictions in a close neighborhood - to fuse multiple single-node certificates into a drastically stronger collective certificate. For example, on the Citeseer dataset our collective certificate for node classification increases the average number of certifiable feature perturbations from 7 to 351.