# AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 64 references that are in the map.
- First posted on arXiv 29 Mar 2025.

## Builds on (most cited first, 30 of 35)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers](https://mlsanity.com/paper/1906.04584/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Rethinking Graph Neural Networks for Anomaly Detection](https://mlsanity.com/paper/2205.15508/) (2022)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius](https://mlsanity.com/paper/2001.02378/) (2020)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Consistency Regularization for Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2006.04062/) (2020)
- [Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation](https://mlsanity.com/paper/2008.10715/) (2020)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [Understanding Structural Vulnerability in Graph Convolutional Networks](https://mlsanity.com/paper/2108.06280/) (2021)
- [Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing](https://mlsanity.com/paper/2002.03421/) (2020)
- [Graph Neural Networks in IoT: A Survey](https://mlsanity.com/paper/2203.15935/) (2022)
- [Graph Neural Networks for Financial Fraud Detection: A Review](https://mlsanity.com/paper/2411.05815/) (2024)
- [ContextGNN: Beyond Two-Tower Recommendation Systems](https://mlsanity.com/paper/2411.19513/) (2024)
- [Distributed Backdoor Attacks on Federated Graph Learning and Certified Defenses](https://mlsanity.com/paper/2407.08935/) (2024)
- [Efficient, Direct, and Restricted Black-Box Graph Evasion Attacks to Any-Layer Graph Neural Networks via Influence Function](https://mlsanity.com/paper/2009.00203/) (2020)

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

- [Unifying Graph Neural Networks Through a Common Layer Equation](https://mlsanity.com/paper/2608.16097/) (2026)
- [The Geometry of Randomized Smoothing on Feasible Sets](https://mlsanity.com/paper/2609.39497/) (2026)

## Abstract (arXiv)

Despite advancements in Graph Neural Networks (GNNs), adaptive attacks continue to challenge their robustness. Certified robustness via randomized smoothing offers provable guarantees but suffers from a severe accuracy-robustness trade-off, limiting its practical use. To bridge this gap, we introduce AuditVotes, the first framework that simultaneously achieves high clean accuracy and strong certified robustness. AuditVotes seamlessly integrates two novel components into the randomized smoothing pipeline: (1) graph rewiring augmentation, which denoises randomized graphs to recover data quality, and (2) conditional smoothing, which filters low-confidence votes to ensure prediction consistency. We establish a novel theoretical result, proving that certified robustness is preserved under arbitrary filtering functions. Designed for inductive learning, our framework generalizes to unseen nodes and applies broadly to other smoothing schemes, including de-randomized smoothing for graphs and Gaussian smoothing for images. Extensive experiments show AuditVotes delivers substantial gains: on Cora-ML under 20-edge attacks, it improves clean accuracy by 437.1% and certified accuracy by 409.3%, while maintaining comparable runtime to vanilla smoothing. As a widely applicable and efficient plug-in, AuditVotes offers higher accuracy and stronger guarantees, enabling the practical and certifiably robust GNNs in security-sensitive domains.