Data Science|Compressive Sensing for Graph Clustering

Abstract:  This talk is based on a joint work with Daneil Mckenzie.  We will explain how to phrase the cut improvement for graphs as a sparse recovery problem, whence one can use algorithms originally developed for  compressive sensing (such as  SubspacePursuit  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.  We then propose new methods for local clustering and semi-supervised clustering, which enjoy similar guarantees of success and speed.  Finally, we demonstrate our approach with extensive numerical benchmarking.