Title: 
Lipschitz Learning on Graphs

Abstract:
In this talk, we will discuss how to infer a function on all vertices of a graph from observations on a few of the vertices. Given real-valued observations on some vertices, we find a smooth extension to all vertices. We study both minimal Lipschitz extensions and the absolutely minimal Lipschitz extension (AMLE) which is the limit of p-Laplacian regularization. These extensions generalize naturally to directed graphs.

We develop provably fast algorithms for computing these extensions. Our implementation of these algorithms runs in minutes on graphs with millions of vertices. We provide experimental evidence that AMLE performs well for spam webpage detection. To handle noisy input graphs, we develop regularization techniques for Lipschitz extensions and give algorithms for outlier removal. The latter is surprising, as the analogous least-squares problem is NP-hard.

Host: Thomas Dueholm