# Minimax Rates for Robust Community Detection

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

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery](https://mlsanity.com/paper/1501.05021/) (2015)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly](https://mlsanity.com/paper/1904.09635/) (2019)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [A semidefinite program for unbalanced multisection in the stochastic block model](https://mlsanity.com/paper/1507.05605/) (2015)
- [Learning Communities in the Presence of Errors](https://mlsanity.com/paper/1511.03229/) (2015)
- [Robustness of spectral methods for community detection](https://mlsanity.com/paper/1811.05808/) (2018)

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

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [Adversarially-Robust Inference on Trees via Belief Propagation](https://mlsanity.com/paper/2404.00768/) (2024)
- [Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Point](https://mlsanity.com/paper/2503.03923/) (2025)
- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

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