# Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 36 references that are in the map.
- First posted on arXiv 17 May 2023.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [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)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [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)
- [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017)
- [Sum-of-squares proofs and the quest toward optimal algorithms](https://mlsanity.com/paper/1404.5236/) (2014)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)

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

- [Fast, robust approximate message passing](https://mlsanity.com/paper/2411.02764/) (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)
- [Multi-View Stochastic Block Models](https://mlsanity.com/paper/2406.04860/) (2024)
- [Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Point](https://mlsanity.com/paper/2503.03923/) (2025)
- [SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search](https://mlsanity.com/paper/2506.03657/) (2025)
- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

## Abstract (arXiv)

We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the n vertices. We present the first polynomial-time algorithm that achieves weak recovery at the Kesten-Stigum threshold even in the presence of a small constant fraction of corrupted nodes. Prior to this work, even state-of-the-art robust algorithms were known to break under such node corruption adversaries, when close to the Kesten-Stigum threshold. We further extend our techniques to the Z2 synchronization problem, where our algorithm reaches the optimal recovery threshold in the presence of similar strong adversarial perturbations. The key ingredient of our algorithm is a novel identifiability proof that leverages the push-out effect of the Grothendieck norm of principal submatrices.