# Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

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

## Key facts

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

## Built on by (most cited first, 30 of 33)

- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Joint Community Detection and Rotational Synchronization via Semidefinite Programming](https://mlsanity.com/paper/2105.06031/) (2021)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Semidefinite Programming for Community Detection with Side Information](https://mlsanity.com/paper/2105.02816/) (2021)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [Community Detection: Exact Recovery in Weighted Graphs](https://mlsanity.com/paper/2102.04439/) (2021)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2112.14204/) (2021)
- [Community Recovery in the Geometric Block Model](https://mlsanity.com/paper/2206.11303/) (2022)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Multilayer hypergraph clustering using the aggregate similarity matrix](https://mlsanity.com/paper/2301.11657/) (2023)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)
- [Community detection in censored hypergraph](https://mlsanity.com/paper/2111.03179/) (2021)
- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [Spectral Algorithms Optimally Recover Planted Sub-structures](https://mlsanity.com/paper/2203.11847/) (2022)
- [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)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Conic Descent Redux for Memory-Efficient Optimization](https://mlsanity.com/paper/2308.07343/) (2023)
- [Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models](https://mlsanity.com/paper/2403.19516/) (2024)
- [Why the Metric Backbone Preserves Community Structure](https://mlsanity.com/paper/2406.03852/) (2024)

## Abstract (arXiv)

The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p=a log n/n and q=b log n/n for fixed a,b and n → ∞, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. citeAbbe14. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.