# Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 57 references that are in the map.
- First posted on arXiv 28 Apr 2025.

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

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Hierarchical Clustering: Objective Functions and Algorithms](https://mlsanity.com/paper/1704.02147/) (2017)
- [DeepDPM: Deep Clustering With an Unknown Number of Clusters](https://mlsanity.com/paper/2203.14309/) (2022)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [p-Norm Flow Diffusion for Local Graph Clustering](https://mlsanity.com/paper/2005.09810/) (2020)
- [Flow-Based Local Graph Clustering with Better Seed Set Inclusion](https://mlsanity.com/paper/1811.12280/) (2018)
- [A Compressed Sensing Based Least Squares Approach to Semi-supervised Local Cluster Extraction](https://mlsanity.com/paper/2202.02904/) (2022)
- [A testing based extraction algorithm for identifying significant communities in networks](https://mlsanity.com/paper/1308.0777/) (2013)
- [Compressive Sensing for cut improvement and local clustering](https://mlsanity.com/paper/1808.05780/) (2018)
- [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)

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

- [Scalable Graph Coreset Selection via Greedy Sampling](https://mlsanity.com/paper/2607.27602/) (2026)

## Abstract (arXiv)

Local clustering aims to identify specific substructures within a large graph without any additional structural information of the graph. These substructures are typically small compared to the overall graph, enabling the problem to be approached by finding a sparse solution to a linear system associated with the graph Laplacian. In this work, we first propose a method for identifying specific local clusters when very few labeled data are given, which we term semi-supervised local clustering. We then extend this approach to the unsupervised setting when no prior information on labels is available. The proposed methods involve randomly sampling the graph, applying diffusion through local cluster extraction, then examining the overlap among the results to find each cluster. We establish the co-membership conditions for any pair of nodes, and rigorously prove the correctness of our methods. Additionally, we conduct extensive experiments to demonstrate that the proposed methods achieve state of the art results in the low-label rates regime.