# Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing

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

## Key facts

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

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

- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [Adversarial Attacks on Graph Classification via Bayesian Optimisation](https://mlsanity.com/paper/2111.02842/) (2021)
- [(De-)Randomized Smoothing for Decision Stump Ensembles](https://mlsanity.com/paper/2205.13909/) (2022)
- [Certifiably Robust Graph Contrastive Learning](https://mlsanity.com/paper/2310.03312/) (2023)
- [EGC2: Enhanced Graph Classification with Easy Graph Compression](https://mlsanity.com/paper/2107.07737/) (2021)
- [Structure-Aware Robustness Certificates for Graph Classification](https://mlsanity.com/paper/2306.11915/) (2023)
- [Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifier](https://mlsanity.com/paper/2509.25979/) (2025)
- [Adversarial Robustness of Probabilistic Network Embedding for Link Prediction](https://mlsanity.com/paper/2107.01936/) (2021)
- [Principal Eigenvalue Regularization for Improved Worst-Class Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2503.17172/) (2025)

## Abstract (arXiv)

Graph classification has practical applications in diverse fields. Recent studies show that graph-based machine learning models are especially vulnerable to adversarial perturbations due to the non i.i.d nature of graph data. By adding or deleting a small number of edges in the graph, adversaries could greatly change the graph label predicted by a graph classification model. In this work, we propose to build a smoothed graph classification model with certified robustness guarantee. We have proven that the resulting graph classification model would output the same prediction for a graph under l0 bounded adversarial perturbation. We also evaluate the effectiveness of our approach under graph convolutional network (GCN) based multi-class graph classification model.