mlsanityData to 7 Oct 2026

Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More

arXiv 2008.12952 ↗First posted 29 Aug 2020cs.LG cs.CR cs.SIcited by 56

Not on the map. Why?

Abstract (arXiv)

Existing techniques for certifying the robustness of models for discrete data either work only for a small class of models or are general at the expense of efficiency or tightness. Moreover, they do not account for sparsity in the input which, as our findings show, is often essential for obtaining non-trivial guarantees. We propose a model-agnostic certificate based on the randomized smoothing framework which subsumes earlier work and is tight, efficient, and sparsity-aware. Its computational complexity does not depend on the number of discrete categories or the dimension of the input (e.g. the graph size), making it highly scalable. We show the effectiveness of our approach on a wide variety of models, datasets, and tasks -- specifically highlighting its use for Graph Neural Networks. So far, obtaining provable guarantees for GNNs has been difficult due to the discrete and non-i.i.d. nature of graph data. Our method can certify any GNN and handles perturbations to both the graph structure and the node attributes.

Key facts. Cited by 56 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Aug 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 9; 2023: 14; 2024: 9; 2025: 11; 2026: 4.

56 papers.

Sort:

By area:

  1. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  2. 2021Transferability of Graph Neural Networks: an Extended Graphon Approachcited by 51
  3. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  4. 2021Single Node Injection Attack against Graph Neural Networkscited by 45
  5. 2021Scalable Certified Segmentation via Randomized Smoothingcited by 35
  6. 2023Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attackscited by 32
  7. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  8. 2021A Hard Label Black-box Adversarial Attack Against Graph Neural Networkscited by 26
  9. 2021How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implicationscited by 21
  10. 2022Adversarial Weight Perturbation Improves Generalization in Graph Neural Networkscited by 21
  11. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  12. 2021Anomalous Edge Detection in Edge Exchangeable Social Network Modelscited by 17
38 more
  1. 2023RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletioncited by 17
  2. 2023Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networkscited by 16
  3. 2024Robust Yet Efficient Conformal Prediction Setscited by 16
  4. 2022RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrievalcited by 15
  5. 2023Incremental Randomized Smoothing Certificationcited by 12
  6. 2022Adversarial Camouflage for Node Injection Attack on Graphscited by 11
  7. 2022Localized Randomized Smoothing for Collective Robustness Certificationcited by 10
  8. 2023Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networkscited by 10
  9. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  10. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  11. 2023Hierarchical Randomized Smoothingcited by 9
  12. 2024Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attackscited by 9
  13. 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
  14. 2024Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structurecited by 8
  15. 2024Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustnesscited by 8
  16. 2021Integer-arithmetic-only Certified Robustness for Quantized Neural Networkscited by 7
  17. 2022Invariance-Aware Randomized Smoothing Certificatescited by 7
  18. 2022Private and Reliable Neural Network Inferencecited by 6
  19. 2022(De-)Randomized Smoothing for Decision Stump Ensemblescited by 5
  20. 2023A Certified Radius-Guided Attack Framework to Image Segmentation Modelscited by 5
  21. 2023Certifiably Robust Graph Contrastive Learningcited by 5
  22. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  23. 2023IDEA: Invariant Defense for Graph Adversarial Robustnesscited by 4
  24. 2025Robust Conformal Prediction with a Single Binary Certificatecited by 4
  25. 2025One Sample is Enough to Make Conformal Prediction Robustcited by 4
  26. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  27. 2026Are LLM-Enhanced Graph Neural Networks Robust against Poisoning Attacks?cited by 4
  28. 2024Collective Certified Robustness against Graph Injection Attackscited by 3
  29. 2023Graph Adversarial Immunization for Certifiable Robustnesscited by 2
  30. 2023Structure-Aware Robustness Certificates for Graph Classificationcited by 2
  31. 2024Discrete Randomized Smoothing Meets Quantum Computingcited by 2
  32. 2025Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbationscited by 2
  33. 2025Reconcile Certified Robustness and Accuracy for DNN-based Smoothed Majority Vote Classifiercited by 2
  34. 2025If You Want to Be Robust, Be Wary of Initializationcited by 1
  35. 2026CAGE: Certified Authorization under Typed-Return Uncertainty for Tool-Using Agentscited by 1
  36. 2022Exploring High-Order Structure for Robust Graph Structure Learningcited by 0
  37. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  38. 2025Principal Eigenvalue Regularization for Improved Worst-Class Certified Robustness of Smoothed Classifierscited by 0

50 most cited of 56 All 56 (JSON)