# A simple SVD algorithm for finding hidden partitions

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2014.

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

- [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)
- [A Multiscale Environment for Learning by Diffusion](https://mlsanity.com/paper/2102.00500/) (2021)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle](https://mlsanity.com/paper/2106.10374/) (2021)
- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [Optimal Clustering with Noisy Queries via Multi-Armed Bandit](https://mlsanity.com/paper/2207.05376/) (2022)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [Capturing the Denoising Effect of PCA via Compression Ratio](https://mlsanity.com/paper/2204.10888/) (2022)
- [On consistency of constrained spectral clustering under representation-aware stochastic block model](https://mlsanity.com/paper/2203.02005/) (2022)
- [Spectral Algorithms Optimally Recover Planted Sub-structures](https://mlsanity.com/paper/2203.11847/) (2022)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [On the Power of SVD in the Stochastic Block Model](https://mlsanity.com/paper/2309.15322/) (2023)

## Abstract (arXiv)

Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.