Compressive Sensing for cut improvement and local clustering

Abstract

We show how one can phrase the cut improvement problem for graphs as a sparse recovery problem, whence one can use algorithms originally developed for use in compressive sensing (such as SubspacePursuit or CoSaMP) to solve it. We show that this approach to cut improvement is fast, both in theory and practice and moreover enjoys statistical guarantees of success when applied to graphs drawn from probabilistic models such as the Stochastic Block Model. Using this new cut improvement approach, which we call ClusterPursuit, as an algorithmic primitive we then propose new methods for local clustering and semi-supervised clustering, which enjoy similar guarantees of success and speed. Finally, we verify the promise of our approach with extensive numerical benchmarking.

arXiv comment25 pages. Generalizes and improves upon the earlier versions arxiv: 1808.05780 and arXiv:1708.09477. To appear in SIMODS

References in corpus (8)

• Community structure in social and biological networks
• Social Structure of Facebook Networks
• Semi-Supervised Learning with Ladder Networks
• Generalized Louvain Method for Community Detection in Large Networks
• General Deviants: An Analysis of Perturbations in Compressed Sensing
• A testing based extraction algorithm for identifying significant communities in networks
• Capacity Releasing Diffusion for Speed and Locality
• Recovering communities in the general stochastic block model without knowing the parameters