Algorithms for Lipschitz Learning on Graphs

Abstract

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 $\tilde{O}(mn)$. 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 $\tilde{O}(m^{3/2})$.

Code used in this work is available at https://github.com/danspielman/YINSlex 30 pages

References in corpus (1)

• Vector-valued optimal Lipschitz extensions

Cited by in corpus (16)

• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Lipschitz regularized Deep Neural Networks generalize and are adversarially robust
• Continuum Limit of Lipschitz Learning on Graphs
• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Learning on Hypergraphs with Sparsity
• Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
• Fast, Provable Algorithms for Isotonic Regression in all ${\ell }_p$-norms
• Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing
• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
• Multiscale Elliptic PDEs Upscaling and Function Approximation via Subsampled Data
• Function Approximation via The Subsampled Poincar\' e Inequality
• Minimal Lipschitz and $\infty$-Harmonic Extensions of Vector-Valued Functions on Finite Graphs
• Hardness of Graph-Structured Algebraic and Symbolic Problems
• Large data limit for a phase transition model with the p-Laplacian on point clouds
• A nonlinear diffusion method for semi-supervised learning on hypergraphs
• Iterative Refinement for ${\ell }_p$-norm Regression