Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods
This work addresses graph analysis for applications like community detection, but it is incremental as it builds on existing compressive sensing and diffusion techniques.
The paper tackles local clustering on graphs by proposing semi-supervised and unsupervised methods that use compressive sensing and random sampling to identify substructures, achieving state-of-the-art results with few labeled data.
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.