Aarhus University Seal

MADALGO Theory Seminar

MADALGO Seminar: Rasmus Kyng (Yale University): "Lipschitz Learning on Graphs"

Info about event


Tuesday 6 September 2016,  at 13:30 - 14:15


Nygaard 395

Lipschitz Learning on Graphs

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