# Localized Randomized Smoothing for Collective Robustness Certification

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 63 references that are in the map.
- First posted on arXiv 28 Oct 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016)
- [Rethinking Atrous Convolution for Semantic Image Segmentation](https://mlsanity.com/paper/1706.05587/) (2017)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Albumentations: fast and flexible image augmentations](https://mlsanity.com/paper/1809.06839/) (2018)
- [Understanding the Effective Receptive Field in Deep Convolutional Neural Networks](https://mlsanity.com/paper/1701.04128/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Synthetic and Natural Noise Both Break Neural Machine Translation](https://mlsanity.com/paper/1711.02173/) (2017)
- [Adversarial Examples for Semantic Segmentation and Object Detection](https://mlsanity.com/paper/1703.08603/) (2017)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Robustness Verification for Transformers](https://mlsanity.com/paper/2002.06622/) (2020)
- [Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers](https://mlsanity.com/paper/1906.04948/) (2019)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Certified Defense to Image Transformations via Randomized Smoothing](https://mlsanity.com/paper/2002.12463/) (2020)
- [Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework](https://mlsanity.com/paper/2002.09169/) (2020)
- [SparseBERT: Rethinking the Importance Analysis in Self-attention](https://mlsanity.com/paper/2102.12871/) (2021)
- [POPQORN: Quantifying Robustness of Recurrent Neural Networks](https://mlsanity.com/paper/1905.07387/) (2019)
- [Certifying Confidence via Randomized Smoothing](https://mlsanity.com/paper/2009.08061/) (2020)
- [Scalable Certified Segmentation via Randomized Smoothing](https://mlsanity.com/paper/2107.00228/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)

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

- [A Probabilistic Perspective on Unlearning and Alignment for Large Language Models](https://mlsanity.com/paper/2410.03523/) (2024)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Rethinking Randomized Smoothing from the Perspective of Scalability](https://mlsanity.com/paper/2312.12608/) (2023)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [Discrete Randomized Smoothing Meets Quantum Computing](https://mlsanity.com/paper/2408.00895/) (2024)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Effective Data Pruning through Score Extrapolation](https://mlsanity.com/paper/2506.09010/) (2025)
- [Fast and Flexible Robustness Certificates for Semantic Segmentation](https://mlsanity.com/paper/2512.06010/) (2025)
- [PDA: Text-Augmented Defense Framework for Robust Vision-Language Models against Adversarial Image Attacks](https://mlsanity.com/paper/2604.01010/) (2026)

## Abstract (arXiv)

Models for image segmentation, node classification and many other tasks map a single input to multiple labels. By perturbing this single shared input (e.g. the image) an adversary can manipulate several predictions (e.g. misclassify several pixels). Collective robustness certification is the task of provably bounding the number of robust predictions under this threat model. The only dedicated method that goes beyond certifying each output independently is limited to strictly local models, where each prediction is associated with a small receptive field. We propose a more general collective robustness certificate for all types of models. We further show that this approach is beneficial for the larger class of softly local models, where each output is dependent on the entire input but assigns different levels of importance to different input regions (e.g. based on their proximity in the image). The certificate is based on our novel localized randomized smoothing approach, where the random perturbation strength for different input regions is proportional to their importance for the outputs. Localized smoothing Pareto-dominates existing certificates on both image segmentation and node classification tasks, simultaneously offering higher accuracy and stronger certificates.