# Recovering Nonuniform Planted Partitions via Iterated Projection

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2017.

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

- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [On the Power of SVD in the Stochastic Block Model](https://mlsanity.com/paper/2309.15322/) (2023)

## Abstract (arXiv)

In the planted partition problem, the n vertices of a random graph are partitioned into k "clusters," and edges between vertices in the same cluster and different clusters are included with constant probability p and q, respectively (where 0 ≤ q < p ≤ 1). We give an efficient spectral algorithm that recovers the clusters with high probability, provided that the sizes of any two clusters are either very close or separated by ≥ Omega(√ n). We also discuss a generalization of planted partition in which the algorithm's input is not a random graph, but a random real symmetric matrix with independent above-diagonal entries. Our algorithm is an adaptation of a previous algorithm for the uniform case, i.e., when all clusters are size n / k ≥ Omega(√ n). The original algorithm recovers the clusters one by one via iterated projection: it constructs the orthogonal projection operator onto the dominant k-dimensional eigenspace of the random graph's adjacency matrix, uses it to recover one of the clusters, then deletes it and recurses on the remaining vertices. We show herein that a similar algorithm works in the nonuniform case.