# Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing

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

## Key facts

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

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

- [PointGuard: Provably Robust 3D Point Cloud Classification](https://mlsanity.com/paper/2103.03046/) (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)
- [PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learning](https://mlsanity.com/paper/2205.06401/) (2022)
- [FLCert: Provably Secure Federated Learning against Poisoning Attacks](https://mlsanity.com/paper/2210.00584/) (2022)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [UniCR: Universally Approximated Certified Robustness via Randomized Smoothing](https://mlsanity.com/paper/2207.02152/) (2022)
- [Mask-GVAE: Blind Denoising Graphs via Partition](https://mlsanity.com/paper/2102.04228/) (2021)
- [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)
- [FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classification](https://mlsanity.com/paper/2210.13815/) (2022)
- [10 Security and Privacy Problems in Large Foundation Models](https://mlsanity.com/paper/2110.15444/) (2021)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [Pre-trained Encoders in Self-Supervised Learning Improve Secure and Privacy-preserving Supervised Learning](https://mlsanity.com/paper/2212.03334/) (2022)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [A Survey of Neural Network Robustness Assessment in Image Recognition](https://mlsanity.com/paper/2404.08285/) (2024)
- [Robustness of shallow graph embedding methods for community detection](https://mlsanity.com/paper/2405.00636/) (2024)
- [Graph Adversarial Immunization for Certifiable Robustness](https://mlsanity.com/paper/2302.08051/) (2023)
- [Structure-Aware Robustness Certificates for Graph Classification](https://mlsanity.com/paper/2306.11915/) (2023)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Adversarial Robustness of Probabilistic Network Embedding for Link Prediction](https://mlsanity.com/paper/2107.01936/) (2021)
- [Tightening Robustness Verification of MaxPool-based Neural Networks via Minimizing the Over-Approximation Zone](https://mlsanity.com/paper/2211.09810/) (2022)
- [Effects of Exponential Gaussian Distribution on (Double Sampling) Randomized Smoothing](https://mlsanity.com/paper/2406.02309/) (2024)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation](https://mlsanity.com/paper/2405.08645/) (2024)
- [Certified Adversarial Robustness via Partition-based Randomized Smoothing](https://mlsanity.com/paper/2409.13546/) (2024)
- [Attacking and Securing Community Detection: A Game-Theoretic Framework](https://mlsanity.com/paper/2512.11359/) (2025)
- [Single-Edge Node Injection Threats to GNN-Based Security Monitoring in Industrial Graph Systems](https://mlsanity.com/paper/2602.01113/) (2026)

## Abstract (arXiv)

Community detection plays a key role in understanding graph structure. However, several recent studies showed that community detection is vulnerable to adversarial structural perturbation. In particular, via adding or removing a small number of carefully selected edges in a graph, an attacker can manipulate the detected communities. However, to the best of our knowledge, there are no studies on certifying robustness of community detection against such adversarial structural perturbation. In this work, we aim to bridge this gap. Specifically, we develop the first certified robustness guarantee of community detection against adversarial structural perturbation. Given an arbitrary community detection method, we build a new smoothed community detection method via randomly perturbing the graph structure. We theoretically show that the smoothed community detection method provably groups a given arbitrary set of nodes into the same community (or different communities) when the number of edges added/removed by an attacker is bounded. Moreover, we show that our certified robustness is tight. We also empirically evaluate our method on multiple real-world graphs with ground truth communities.