# Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 17 Feb 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [Breaking the Small Cluster Barrier of Graph Clustering](https://mlsanity.com/paper/1302.4549/) (2013)
- [Recovering Nonuniform Planted Partitions via Iterated Projection](https://mlsanity.com/paper/1708.06783/) (2017)
- [A Simple Spectral Algorithm for Recovering Planted Partitions](https://mlsanity.com/paper/1503.00423/) (2015)

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

- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Confident Clustering via PCA Compression Ratio and Its Application to Single-cell RNA-seq Analysis](https://mlsanity.com/paper/2205.09849/) (2022)
- [VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates](https://mlsanity.com/paper/2402.18805/) (2024)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)

## Abstract (arXiv)

The stochastic block model (SBM) is a fundamental model for studying graph clustering or community detection in networks. It has received great attention in the last decade and the balanced case, i.e., assuming all clusters have large size, has been well studied. However, our understanding of SBM with unbalanced communities (arguably, more relevant in practice) is still limited. In this paper, we provide a simple SVD-based algorithm for recovering the communities in the SBM with communities of varying sizes. We improve upon a result of Ailon, Chen and Xu [ICML 2013; JMLR 2015] by removing the assumption that there is a large interval such that the sizes of clusters do not fall in, and also remove the dependency of the size of the recoverable clusters on the number of underlying clusters. We further complement our theoretical improvements with experimental comparisons. Under the planted clique conjecture, the size of the clusters that can be recovered by our algorithm is nearly optimal (up to poly-logarithmic factors) when the probability parameters are constant. As a byproduct, we obtain an efficient clustering algorithm with sublinear query complexity in a faulty oracle model, which is capable of detecting all clusters larger than tildeOmega(√n), even in the presence of Omega(n) small clusters in the graph. In contrast, previous efficient algorithms that use a sublinear number of queries are incapable of recovering any large clusters if there are more than tildeOmega(n2/5) small clusters.