# Community detection in sparse networks via Grothendieck's inequality

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2014.

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

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [abess: A Fast Best Subset Selection Library in Python and R](https://mlsanity.com/paper/2110.09697/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models](https://mlsanity.com/paper/2108.04729/) (2021)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances](https://mlsanity.com/paper/2103.00034/) (2021)
- [Sketch-and-solve approaches to k-means clustering by semidefinite programming](https://mlsanity.com/paper/2211.15744/) (2022)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [Semidefinite programming on population clustering: a global analysis](https://mlsanity.com/paper/2301.00344/) (2023)
- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)
- [Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models](https://mlsanity.com/paper/2406.05340/) (2024)
- [Improved Robust Estimation for ErdHos-R'enyi Graphs: The Sparse Regime and Optimal Breakdown Point](https://mlsanity.com/paper/2503.03923/) (2025)

## Abstract (arXiv)

We present a simple and flexible method to prove consistency of semidefinite optimization problems on random graphs. The method is based on Grothendieck's inequality. Unlike the previous uses of this inequality that lead to constant relative accuracy, we achieve any given relative accuracy by leveraging randomness. We illustrate the method with the problem of community detection in sparse networks, those with bounded average degrees. We demonstrate that even in this regime, various simple and natural semidefinite programs can be used to recover the community structure up to an arbitrarily small fraction of misclassified vertices. The method is general; it can be applied to a variety of stochastic models of networks and semidefinite programs.