Local Graph Clustering with Network Lasso
This work addresses graph clustering challenges for data analysis, offering an incremental improvement with a novel method for known bottlenecks in handling sparse structures.
The paper tackles the problem of local graph clustering by introducing a network Lasso method that minimizes total variation of cluster indicator signals, demonstrating theoretically and numerically that it can handle very sparse, chain-like clusters better than spectral clustering methods.
We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes. While spectral clustering methods are guided by a minimization of the graph Laplacian quadratic form, nLasso minimizes the total variation of cluster indicator signals. As demonstrated theoretically and numerically, nLasso methods can handle very sparse clusters (chain-like) which are difficult for spectral clustering. We also verify that a primal-dual method for nonsmooth optimization allows to approximate nLasso solutions with optimal worst-case convergence rate.