# Achieving Optimal Misclassification Proportion in Stochastic Block Model

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

## Key facts

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

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

- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [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)
- [Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions](https://mlsanity.com/paper/2105.03714/) (2021)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [The Multivariate Community Hawkes Model for Dependent Relational Events in Continuous-time Networks](https://mlsanity.com/paper/2205.00639/) (2022)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [Sparse Subspace Clustering in Diverse Multiplex Network Model](https://mlsanity.com/paper/2206.07602/) (2022)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (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)
- [Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Model](https://mlsanity.com/paper/2209.13762/) (2022)
- [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)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (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)
- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Detection and Evaluation of Clusters within Sequential Data](https://mlsanity.com/paper/2210.01679/) (2022)
- [rMultiNet: An R Package For Multilayer Networks Analysis](https://mlsanity.com/paper/2302.04437/) (2023)
- [Community Detection in the Multi-View Stochastic Block Model](https://mlsanity.com/paper/2401.09510/) (2024)
- [Efficient Graph Encoder Embedding for Large Sparse Graphs in Python](https://mlsanity.com/paper/2406.03726/) (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)
- [On consistency of constrained spectral clustering under representation-aware stochastic block model](https://mlsanity.com/paper/2203.02005/) (2022)

## Abstract (arXiv)

Community detection is a fundamental statistical problem in network data analysis. Many algorithms have been proposed to tackle this problem. Most of these algorithms are not guaranteed to achieve the statistical optimality of the problem, while procedures that achieve information theoretic limits for general parameter spaces are not computationally tractable. In this paper, we present a computationally feasible two-stage method that achieves optimal statistical performance in misclassification proportion for stochastic block model under weak regularity conditions. Our two-stage procedure consists of a generic refinement step that can take a wide range of weakly consistent community detection procedures as initializer, to which the refinement stage applies and outputs a community assignment achieving optimal misclassification proportion with high probability. The practical effectiveness of the new algorithm is demonstrated by competitive numerical results.