mlsanityData to 7 Oct 2026

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

arXiv 2002.03421 ↗First posted 9 Feb 2020cs.CR cs.LG cs.SIcited by 29

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 5; 2024: 7; 2025: 3; 2026: 1.

29 papers.

Sort:

By area:

  1. 2021PointGuard: Provably Robust 3D Point Cloud Classificationcited by 49
  2. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  3. 2021Single Node Injection Attack against Graph Neural Networkscited by 45
  4. 2022PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learningcited by 33
  5. 2022FLCert: Provably Secure Federated Learning against Poisoning Attackscited by 29
  6. 2023RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletioncited by 17
  7. 2022UniCR: Universally Approximated Certified Robustness via Randomized Smoothingcited by 10
  8. 2021Mask-GVAE: Blind Denoising Graphs via Partitioncited by 9
  9. 2023Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attackscited by 8
  10. 2024Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structurecited by 8
  11. 2022FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-based Node Classificationcited by 7
  12. 202110 Security and Privacy Problems in Large Foundation Modelscited by 5
17 more
  1. 2023A Certified Radius-Guided Attack Framework to Image Segmentation Modelscited by 5
  2. 2022Pre-trained Encoders in Self-Supervised Learning Improve Secure and Privacy-preserving Supervised Learningcited by 4
  3. 2024Collective Certified Robustness against Graph Injection Attackscited by 3
  4. 2024Robustness of shallow graph embedding methods for community detectioncited by 3
  5. 2023Graph Adversarial Immunization for Certifiable Robustnesscited by 2
  6. 2023Structure-Aware Robustness Certificates for Graph Classificationcited by 2
  7. 2024A Survey of Neural Network Robustness Assessment in Image Recognitioncited by 2
  8. 2025Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbationscited by 2
  9. 2021Adversarial Robustness of Probabilistic Network Embedding for Link Predictioncited by 1
  10. 2022Tightening Robustness Verification of MaxPool-based Neural Networks via Minimizing the Over-Approximation Zonecited by 1
  11. 2024Effects of Exponential Gaussian Distribution on (Double Sampling) Randomized Smoothingcited by 1
  12. 2025AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothingcited by 1
  13. 2022Adversarial contamination of networks in the setting of vertex nomination: a new trimming methodcited by 0
  14. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  15. 2024Certified Adversarial Robustness via Partition-based Randomized Smoothingcited by 0
  16. 2025Attacking and Securing Community Detection: A Game-Theoretic Frameworkcited by 0
  17. 2026Single-Edge Node Injection Threats to GNN-Based Security Monitoring in Industrial Graph Systemscited by 0