A simple SVD algorithm for finding hidden partitions
Not on the map. Why?
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.
Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Apr 2014.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 7; 2022: 7; 2023: 3.
17 papers.
Sort:
- 2021Exact Recovery in the General Hypergraph Stochastic Block Modelcited by 13
- 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
- 2021A Multiscale Environment for Learning by Diffusioncited by 8
- 2021Large sample spectral analysis of graph-based multi-manifold clusteringcited by 8
- 2022Clustering with Queries under Semi-Random Noisecited by 8
- 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
- 2021Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oraclecited by 6
- 2022Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oraclecited by 5
- 2022Optimal Clustering with Noisy Queries via Multi-Armed Banditcited by 5
- 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
- 2023Spectral clustering in the Gaussian mixture block modelcited by 5
- 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronizationcited by 3
5 more
- 2022Capturing the Denoising Effect of PCA via Compression Ratiocited by 3
- 2022On consistency of constrained spectral clustering under representation-aware stochastic block modelcited by 0
- 2022Spectral Algorithms Optimally Recover Planted Sub-structurescited by 0
- 2022Multi-Frequency Joint Community Detection and Phase Synchronizationcited by 0
- 2023On the Power of SVD in the Stochastic Block Modelcited by 0
- 2023On the Power of SVD in the Stochastic Block Model27 Sep 2023
- 2023Spectral clustering in the Gaussian mixture block model29 Apr 2023
- 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees31 Jan 2023
- 2022Optimal Clustering with Noisy Queries via Multi-Armed Bandit12 Jul 2022
- 2022Multi-Frequency Joint Community Detection and Phase Synchronization16 Jun 2022
- 2022Clustering with Queries under Semi-Random Noise9 Jun 2022
- 2022Capturing the Denoising Effect of PCA via Compression Ratio22 Apr 2022
- 2022Spectral Algorithms Optimally Recover Planted Sub-structures22 Mar 2022
- 2022On consistency of constrained spectral clustering under representation-aware stochastic block model3 Mar 2022
- 2022Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle17 Feb 2022
- 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization25 Dec 2021
- 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model22 Dec 2021
5 more
- 2021Large sample spectral analysis of graph-based multi-manifold clustering28 Jul 2021
- 2021Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle18 Jun 2021
- 2021Exact Recovery in the General Hypergraph Stochastic Block Model11 May 2021
- 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions8 May 2021
- 2021A Multiscale Environment for Learning by Diffusion31 Jan 2021
- 2021Exact Recovery in the General Hypergraph Stochastic Block Modelcited by 13
- 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
- 2021A Multiscale Environment for Learning by Diffusioncited by 8
- 2021Large sample spectral analysis of graph-based multi-manifold clusteringcited by 8
- 2022Clustering with Queries under Semi-Random Noisecited by 8
- 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
- 2021Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oraclecited by 6
- 2022Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oraclecited by 5
- 2022Optimal Clustering with Noisy Queries via Multi-Armed Banditcited by 5
- 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guaranteescited by 5
- 2023Spectral clustering in the Gaussian mixture block modelcited by 5
- 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronizationcited by 3
12 most cited of 17 All 17 (JSON)
- 2023On the Power of SVD in the Stochastic Block Model27 Sep 2023
- 2023Spectral clustering in the Gaussian mixture block model29 Apr 2023
- 2023Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees31 Jan 2023
- 2022Optimal Clustering with Noisy Queries via Multi-Armed Bandit12 Jul 2022
- 2022Multi-Frequency Joint Community Detection and Phase Synchronization16 Jun 2022
- 2022Clustering with Queries under Semi-Random Noise9 Jun 2022
- 2022Capturing the Denoising Effect of PCA via Compression Ratio22 Apr 2022
- 2022Spectral Algorithms Optimally Recover Planted Sub-structures22 Mar 2022
- 2022On consistency of constrained spectral clustering under representation-aware stochastic block model3 Mar 2022
- 2022Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle17 Feb 2022
- 2021A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization25 Dec 2021
- 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model22 Dec 2021
12 newest of 17 All 17 (JSON)