# Optimal Cluster Recovery in the Labeled Stochastic Block Model

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2015.

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

- [Exact Recovery in the General Hypergraph Stochastic Block Model](https://mlsanity.com/paper/2105.04770/) (2021)
- [Non-backtracking Graph Neural Networks](https://mlsanity.com/paper/2310.07430/) (2023)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Multiway Spherical Clustering via Degree-Corrected Tensor Block Models](https://mlsanity.com/paper/2201.07401/) (2022)
- [Exact Community Recovery over Signed Graphs](https://mlsanity.com/paper/2202.12255/) (2022)
- [Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Models](https://mlsanity.com/paper/2306.06845/) (2023)
- [When Does Bottom-up Beat Top-down in Hierarchical Community Detection?](https://mlsanity.com/paper/2306.00833/) (2023)
- [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024)
- [Estimating the number of clusters of a Block Markov Chain](https://mlsanity.com/paper/2407.18287/) (2024)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Strongly Consistent Community Detection in Popularity Adjusted Block Models](https://mlsanity.com/paper/2506.07224/) (2025)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms](https://mlsanity.com/paper/2401.08197/) (2024)
- [VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates](https://mlsanity.com/paper/2402.18805/) (2024)
- [Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms](https://mlsanity.com/paper/2501.11139/) (2025)
- [Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals](https://mlsanity.com/paper/2509.15989/) (2025)
- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)

## Abstract (arXiv)

We consider the problem of community detection or clustering in the labeled Stochastic Block Model (LSBM) with a finite number K of clusters of sizes linearly growing with the global population of items n. Every pair of items is labeled independently at random, and label ℓ appears with probability p(i,j,ℓ) between two items in clusters indexed by i and j, respectively. The objective is to reconstruct the clusters from the observation of these random labels. Clustering under the SBM and their extensions has attracted much attention recently. Most existing work aimed at characterizing the set of parameters such that it is possible to infer clusters either positively correlated with the true clusters, or with a vanishing proportion of misclassified items, or exactly matching the true clusters. We find the set of parameters such that there exists a clustering algorithm with at most s misclassified items in average under the general LSBM and for any s=o(n), which solves one open problem raised in citeabbe2015community. We further develop an algorithm, based on simple spectral methods, that achieves this fundamental performance limit within O(n mboxpolylog(n)) computations and without the a-priori knowledge of the model parameters.