# A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 53 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Semi-Supervised Learning with Deep Generative Models](https://mlsanity.com/paper/1406.5298/) (2014)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Semi-Supervised Learning with Ladder Networks](https://mlsanity.com/paper/1507.02672/) (2015)
- [Deep Compressed Sensing](https://mlsanity.com/paper/1905.06723/) (2019)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Recovering communities in the general stochastic block model without knowing the parameters](https://mlsanity.com/paper/1506.03729/) (2015)
- [Capacity Releasing Diffusion for Speed and Locality](https://mlsanity.com/paper/1706.05826/) (2017)
- [Flow-Based Local Graph Clustering with Better Seed Set Inclusion](https://mlsanity.com/paper/1811.12280/) (2018)
- [Statistical guarantees for local graph clustering](https://mlsanity.com/paper/1906.04863/) (2019)

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

- [Graph-based Semi-supervised Local Clustering with Few Labeled Nodes](https://mlsanity.com/paper/2211.11114/) (2022)
- [Local Clustering for Lung Cancer Image Classification via Sparse Solution Technique](https://mlsanity.com/paper/2407.08800/) (2024)
- [Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods](https://mlsanity.com/paper/2504.19419/) (2025)
- [Scalable Graph Coreset Selection via Greedy Sampling](https://mlsanity.com/paper/2607.27602/) (2026)

## Abstract (arXiv)

A least squares semi-supervised local clustering algorithm based on the idea of compressed sensing is proposed to extract clusters from a graph with known adjacency matrix. The algorithm is based on a two-stage approach similar to the one in citeLaiMckenzie2020. However, under a weaker assumption and with less computational complexity than the one in citeLaiMckenzie2020, the algorithm is shown to be able to find a desired cluster with high probability. The ``one cluster at a time" feature of our method distinguishes it from other global clustering methods. Several numerical experiments are conducted on the synthetic data such as stochastic block model and real data such as MNIST, political blogs network, AT&T and YaleB human faces data sets to demonstrate the effectiveness and efficiency of our algorithm.