MADALGO Theory Seminar

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

2016.09.06 | Lotte Damsgaard

Date Tue 06 Sep
Time 13:30 14:15
Location Nygaard 395

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

Lecture / talk