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.

The data arising in many application domains have an intrinsic network structure. Such network structure is computationally apprealing due to the availability of highly scalable graph algorithms. An important class of graph algorithms is related to optimizing network flows. This paper explores the duality of network flow methods and the recently proposed network Lasso. Network Lasso extends the Lasso method from sparse linear models to clustered graph signals. It turns out that the computational and statistical properties of network Lasso crucially depends on the existence of sufficiently large network flows. Using elementary tools from convex analysis, we offer a precise characterization of the duality between network Lasso and a minimum cost network flow problem. This duality provides a strong link between network Lasso methods and network flow algorithms.

The network Lasso (nLasso) has been proposed recently as an efficient learning algorithm for massive networked data sets (big data over networks). It extends the well-known least least absolute shrinkage and selection operator (Lasso) from learning sparse (generalized) linear models to network models. Efficient implementations of the nLasso have been obtained using convex optimization methods. These implementations naturally lend to highly scalable message passing methods. In this paper, we analyze the performance of nLasso when applied to localized linear regression problems involving networked data. Our main result is a sufficient conditions on the network structure and available label information such that nLasso accurately learns a localized linear regression model from few labeled data points.

We characterize the statistical properties of network Lasso for semi-supervised regression problems involving network- structured data. This characterization is based on the con- nectivity properties of the empirical graph which encodes the similarities between individual data points. Loosely speaking, network Lasso is accurate if the available label informa- tion is well connected with the boundaries between clusters of the network-structure datasets. We make this property precise using the notion of network flows. In particular, the existence of a sufficiently large network flow over the empirical graph implies a network compatibility condition which, in turn, en- sures accuracy of network Lasso.