mlsanityData to 7 Oct 2026

Minimax Rates for Robust Community Detection

arXiv 2207.11903 ↗First posted 25 Jul 2022cs.DS cs.LG cs.SIcited by 12

Not on the map. Why?

Abstract (arXiv)

In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an ε-fraction of corruptions and achieves error O(ε) + e^-fracC2 (1 ± o(1)) where C = (√a - √b)2 is the signal-to-noise ratio and a/n and b/n are the inter-community and intra-community connection probabilities respectively. These bounds essentially match the minimax rates for the SBM without corruptions. We also give robust algorithms for mathbbZ2-synchronization. At the heart of our algorithm is a new semidefinite program that uses global information to robustly boost the accuracy of a rough clustering. Moreover, we show that our algorithms are doubly-robust in the sense that they work in an even more challenging noise model that mixes adversarial corruptions with unbounded monotone changes, from the semi-random model.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 29 of its 38 references that are in the map. First posted on arXiv 25 Jul 2022.

Builds on

29 of 38 references.

References · 29

  1. 2017Community Detection and Stochastic Block Modelscited by 317
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2016Agnostic Estimation of Mean and Covariancecited by 131
  4. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  5. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  6. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  7. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  8. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  9. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  10. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  11. 2013A Proof Of The Block Model Threshold Conjecturecited by 35
  12. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
17 more
  1. 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 32
  2. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  3. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  4. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  5. 2015Minimax Rates of Community Detection in Stochastic Block Modelscited by 25
  6. 2014Community detection in sparse networks via Grothendieck's inequalitycited by 21
  7. 2015How Robust are Reconstruction Thresholds for Community Detection?cited by 20
  8. 2013Belief propagation, robust reconstruction and optimal recovery of block modelscited by 18
  9. 2021Robust recovery for stochastic block modelscited by 18
  10. 2015Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recoverycited by 15
  11. 2019Local Statistics, Semidefinite Programming, and Community Detectioncited by 14
  12. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  13. 2019Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustlycited by 11
  14. 2021Robust Estimation for Random Graphscited by 8
  15. 2015A semidefinite program for unbalanced multisection in the stochastic block modelcited by 7
  16. 2015Learning Communities in the Presence of Errorscited by 7
  17. 2018Robustness of spectral methods for community detectioncited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 4; 2025: 1; 2026: 2.

12 papers.

  1. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  2. 2023Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptionscited by 7
  3. 2023Semidefinite programs simulate approximate message passing robustlycited by 6
  4. 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
  5. 2024Top-K ranking with a monotone adversarycited by 2
  6. 2024A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clusteringcited by 2
  7. 2023When Does Bottom-up Beat Top-down in Hierarchical Community Detection?cited by 1
  8. 2024Perturb-and-Project: Differentially Private Similarities and Marginalscited by 1
  9. 2026Computation-Utility-Privacy Tradeoffs in Bayesian Estimationcited by 1
  10. 2024Adversarially-Robust Inference on Trees via Belief Propagationcited by 0
  11. 2025Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Pointcited by 0
  12. 2026Active Learning on Adversarially Corrupted Graphscited by 0