Title: Algorithms for Lipschitz Learning on Graphs
 
Abstract:
We develop fast algorithms for some interpolation problems on graphs. Given real-valued observations on some of the vertices, our goal is to compute a smooth (Lipschitz) extension to all vertices. Our focus will be the absolutely minimal Lipschitz extension, which is the limit of p-Laplacian regularization for large p.
 
We can compute a minimal Lipschitz extension in expected linear time, and an absolutely minimal Lipschitz extension in expected O(mn) time. We have implemented variants of the latter algorithm that run on graphs with millions of edges in a few minutes.
These extensions are particularly suited to regularization: we can perform l_1 regularization on the input in O(m^(3/2)) time. We can also perform l_0 regularization (outlier removal) on the given values in polynomial time. This is surprising because outlier removal is NP-hard for other natural extensions.
 
Our definitions and algorithms naturally extend to directed graphs. This enables us to obtain good solutions to problems such as the detection of spam Web pages.
 
This is joint work with Rasmus Kyng, Anup Rao, and Sushant Sachdeva