mlsanityData to 14 Oct 2026

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

arXiv 2503.22998 ↗First posted 29 Mar 2025cs.LG cs.AI cs.CRcited by 2

Not on the map. Why?

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.

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

35 of 64 references.

References · 35

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
  5. 2019Graph Neural Networks for Social Recommendationcited by 714
  6. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 541
  7. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 468
  8. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 371
  9. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 330
  10. 2020Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddingscited by 214
  11. 2020Data Augmentation for Graph Neural Networkscited by 203
  12. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
23 more
  1. 2022Rethinking Graph Neural Networks for Anomaly Detectioncited by 187
  2. 2018Certified Adversarial Robustness with Additive Noisecited by 180
  3. 2018Adversarial Attack and Defense on Graph Data: A Surveycited by 167
  4. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  5. 2020MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radiuscited by 114
  6. 2020(De)Randomized Smoothing for Certifiable Defense against Patch Attackscited by 98
  7. 2020Consistency Regularization for Certified Robustness of Smoothed Classifierscited by 73
  8. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  9. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  10. 2021Improved, Deterministic Smoothing for L_1 Certified Robustnesscited by 39
  11. 2023Are Defenses for Graph Neural Networks Robust?cited by 38
  12. 2021Understanding Structural Vulnerability in Graph Convolutional Networkscited by 37
  13. 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
  14. 2022Graph Neural Networks in IoT: A Surveycited by 28
  15. 2024Graph Neural Networks for Financial Fraud Detection: A Reviewcited by 25
  16. 2024ContextGNN: Beyond Two-Tower Recommendation Systemscited by 19
  17. 2024Distributed Backdoor Attacks on Federated Graph Learning and Certified Defensescited by 15
  18. 2020Efficient, Direct, and Restricted Black-Box Graph Evasion Attacks to Any-Layer Graph Neural Networks via Influence Functioncited by 14
  19. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10
  20. 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
  21. 2022FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classificationcited by 7
  22. 2025AGNNCert: Defending Graph Neural Networks against Arbitrary Perturbations with Deterministic Certificationcited by 4
  23. 2024Collective Certified Robustness against Graph Injection Attackscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Unifying Graph Neural Networks Through a Common Layer Equationcited by 0
  2. 2026The Geometry of Randomized Smoothing on Feasible Setscited by 0