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

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

## Key facts

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

## Built on by (most cited first, 30 of 56)

- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Single Node Injection Attack against Graph Neural Networks](https://mlsanity.com/paper/2108.13049/) (2021)
- [Scalable Certified Segmentation via Randomized Smoothing](https://mlsanity.com/paper/2107.00228/) (2021)
- [Text-CRS: A Generalized Certified Robustness Framework against Textual Adversarial Attacks](https://mlsanity.com/paper/2307.16630/) (2023)
- [Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directions](https://mlsanity.com/paper/2306.15427/) (2023)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications](https://mlsanity.com/paper/2106.07767/) (2021)
- [Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks](https://mlsanity.com/paper/2212.04983/) (2022)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Anomalous Edge Detection in Edge Exchangeable Social Network Models](https://mlsanity.com/paper/2109.12727/) (2021)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [Collective Robustness Certificates: Exploiting Interdependence in Graph Neural Networks](https://mlsanity.com/paper/2302.02829/) (2023)
- [Robust Yet Efficient Conformal Prediction Sets](https://mlsanity.com/paper/2407.09165/) (2024)
- [RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval](https://mlsanity.com/paper/2206.11225/) (2022)
- [Incremental Randomized Smoothing Certification](https://mlsanity.com/paper/2305.19521/) (2023)
- [Adversarial Camouflage for Node Injection Attack on Graphs](https://mlsanity.com/paper/2208.01819/) (2022)
- [Localized Randomized Smoothing for Collective Robustness Certification](https://mlsanity.com/paper/2210.16140/) (2022)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [Verifying message-passing neural networks via topology-based bounds tightening](https://mlsanity.com/paper/2402.13937/) (2024)
- [Fundamental Limits in Formal Verification of Message-Passing Neural Networks](https://mlsanity.com/paper/2206.05070/) (2022)
- [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)
- [Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure](https://mlsanity.com/paper/2404.15065/) (2024)
- [Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness](https://mlsanity.com/paper/2406.17830/) (2024)
- [Integer-arithmetic-only Certified Robustness for Quantized Neural Networks](https://mlsanity.com/paper/2108.09413/) (2021)
- [Private and Reliable Neural Network Inference](https://mlsanity.com/paper/2210.15614/) (2022)
- [Invariance-Aware Randomized Smoothing Certificates](https://mlsanity.com/paper/2211.14207/) (2022)

## 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.