# Community Detection with a Subsampled Semidefinite Program

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 16 references that are in the map.
- First posted on arXiv 2 Feb 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage](https://mlsanity.com/paper/1702.06838/) (2017)
- [Sketching semidefinite programs for faster clustering](https://mlsanity.com/paper/2008.04270/) (2020)
- [Dimensionality reduction of SDPs through sketching](https://mlsanity.com/paper/1707.09863/) (2017)

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

- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Sketch-and-solve approaches to k-means clustering by semidefinite programming](https://mlsanity.com/paper/2211.15744/) (2022)
- [NISQ-ready community detection based on separation-node identification](https://mlsanity.com/paper/2212.14717/) (2022)

## Abstract (arXiv)

Semidefinite programming is an important tool to tackle several problems in data science and signal processing, including clustering and community detection. However, semidefinite programs are often slow in practice, so speed up techniques such as sketching are often considered. In the context of community detection in the stochastic block model, Mixon and Xie citemixon2020sketching have recently proposed a sketching framework in which a semidefinite program is solved only on a subsampled subgraph of the network, giving rise to significant computational savings. In this short paper, we provide a positive answer to a conjecture of Mixon and Xie about the statistical limits of this technique for the stochastic block model with two balanced communities.