Algorithms for Lipschitz Learning on Graphs
  We develop fast algorithms for solving regression problems on graphs where
one is given the value of a function at some vertices, and must find its
smoothest possible extension to all vertices. The extension we compute is the
absolutely minimal Lipschitz extension, and is the limit for large $p$ of
$p$-Laplacian regularization. We present an algorithm that computes a minimal
Lipschitz extension in expected linear time, and an algorithm that computes an
absolutely minimal Lipschitz extension in expected time $\widetilde{O} (m n)$.
The latter algorithm has variants that seem to run much faster in practice.
These extensions are particularly amenable to regularization: we can perform
$l_{0}$-regularization on the given values in polynomial time and
$l_{1}$-regularization on the initial function values and on graph edge weights
in time $\widetilde{O} (m^{3/2})$.
