On the Duality between Network Flows and Network Lasso
  Many applications generate data with an intrinsic network structure such as
time series data, image data or social network data. The network Lasso (nLasso)
has been proposed recently as a method for joint clustering and optimization of
machine learning models for networked data. The nLasso extends the Lasso from
sparse linear models to clustered graph signals. This paper explores the
duality of nLasso and network flow optimization. We show that, in a very
precise sense, nLasso is equivalent to a minimum-cost flow problem on the data
network structure. Our main technical result is a concise characterization of
nLasso solutions via existence of certain network flows. The main conceptual
result is a useful link between nLasso methods and basic graph algorithms such
as clustering or maximum flow.
