Local Graph Clustering with Network Lasso

Abstract

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.

References in corpus (8)

• Gossip Algorithms for Distributed Signal Processing
• Network Lasso: Clustering and Optimization in Large Graphs
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Social significance of community structure: Statistical view
• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Capacity Releasing Diffusion for Speed and Locality
• On the Duality between Network Flows and Network Lasso
• A Short Introduction to Local Graph Clustering Methods and Software