Analysis of Network Lasso For Semi-Supervised Regression

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.