Algorithms for Lipschitz Learning on Graphs

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

• Publication year

  2015

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  2015-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1505.00290
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation Algorithms

  2021cited by this paper
• Semi-Supervised Learning

  2014cited by this paper
• Solving SDD linear systems in nearly mlog1/2n time

  2014influential reference
• Efficient Classification for Metric Data

  2013cited by this paper
• Finite difference methods for the Infinity Laplace and pp-Laplace equations

  2013cited by this paper
• p-voltages: Laplacian Regularization for Semi-Supervised Learning on High-Dimensional Data

  2013cited by this paper
• Advances in Neural Information Processing Systems 24

  2011cited by this paper
• Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

  2011cited by this paper
• Phase transition in the family of p-resistances

  2011cited by this paper
• Manifold Learning Theory and Applications

  2011cited by this paper
• Finite difference methods for the Infinity Laplace and p-Laplace equations

  2011cited by this paper
• Vector‐valued optimal Lipschitz extensions

  2010influential reference
• Absolutely minimal Lipschitz extension of tree-valued mappings

  2010cited by this paper
• Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data

  2009cited by this paper
• Fitting a Cm-smooth function to data, III

  2009cited by this paper
• Faster approximate lossy generalized flow via interior point algorithms

  2008cited by this paper
• Whitney’s extension problems and interpolation of data

  2008cited by this paper
• Transductive link spam detection

  2007influential reference
• A Seeded Image Segmentation Framework Unifying Graph Cuts And Random Walker Which Yields A New Algorithm

  2007cited by this paper
• Tug-of-war and the infinity Laplacian

  2006cited by this paper
• A reference collection for web spam

  2006influential reference
• Fitting a Cm-Smooth Function to Data

  2005cited by this paper
• Distance-Based Classification with Lipschitz Functions

  2004cited by this paper
• A TOUR OF THE THEORY OF ABSOLUTELY MINIMIZING FUNCTIONS

  2004cited by this paper
• Regularization and Semi-supervised Learning on Large Graphs

  2004cited by this paper
• Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

  2003cited by this paper
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

  2003cited by this paper
• Optimal Lipschitz extensions and the infinity laplacian

  2001cited by this paper
• EXISTENCE AND COMPARISON RESULTS FOR FULLY NONLINEAR DEGENERATE ELLIPTIC EQUATIONS WITHOUT ZEROTH-ORDER TERM*

  2001cited by this paper
• Combinatorial Games under Auction Play

  1999cited by this paper
• Absolutely minimal extensions of functions on metric spaces

  1999cited by this paper
• Uniqueness of Lipschitz extensions: Minimizing the sup norm of the gradient

  1993cited by this paper
• Rate of Convergence of the Discrete Pólya-1 Algorithm

  1990influential reference
• The optimal recovery of smooth functions

  1976cited by this paper
• Extension of functions satisfying lipschitz conditions

  1967cited by this paper
• Note on Dilworth’s decomposition theorem for partially ordered sets

  1956cited by this paper
• Analytic Extensions of Differentiable Functions Defined in Closed Sets

  1934cited by this paper
• Über die zusammenziehende und Lipschitzsche Transformationen

  1934cited by this paper
• Extension of range of functions

  1934cited by this paper

• Continuum limit of hypergraph $p$-Laplacian equations on point clouds

  2026cites this paper
• Enhancement of Quantum Semi-Supervised Learning via Improved Laplacian and Poisson Methods

  2025cites this paper
• Laplace Learning in Wasserstein Space

  2025cites this paper
• Partial differential equations in data science

  2025influential citation
• Lattice Lipschitz operators on C(K)-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C(K)-$$\end{document} spaces

  2025cites this paper
• Fast Frank--Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions

  2025cites this paper
• Higher-Order Regularization Learning on Hypergraphs

  2025cites this paper
• Hypergraph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si919.svg" display="inline" id="d1e824"><mml:mi>p</mml:mi></mml:math>-Laplacian regularization on point clouds for data interpolation

  2025cites this paper
• Hypergraph p-Laplacian regularization on point clouds for data interpolation

  2024cites this paper
• Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian

  2024cites this paper
• Lattice Lipschitz operators on $C(K)-$space

  2024cites this paper
• Graph-Based Semi-Supervised Segregated Lipschitz Learning

  2024cites this paper
• Convex optimization with p-norm oracles

  2024cites this paper
• The graph $\infty$-Laplacian eigenvalue problem

  2024influential citation
• Fast Algorithms for Hypergraph PageRank with Applications to Semi-Supervised Learning

  2024cites this paper
• Interface Laplace Learning: Learnable Interface Term Helps Semi-Supervised Learning

  2024cites this paper
• Improved graph-based semi-supervised learning schemes

  2024influential citation
• Extension of semi-Lipschitz maps on non-subadditive quasi-metric spaces: new tools for Artificial Intelligence

  2023cites this paper
• Consistency of Fractional Graph-Laplacian Regularization in Semisupervised Learning with Finite Labels

  2023cites this paper
• Laplacian-based Semi-Supervised Learning in Multilayer Hypergraphs by Coordinate Descent

  2023cites this paper
• Best Lp Isotonic Regressions, p∈{0, 1, ∞}

  2023cites this paper
• Fast Algorithms for (cid:96) p -Regression

  2022cites this paper
• Multiscale Elliptic PDE Upscaling and Function Approximation via Subsampled Data

  2022cites this paper
• Index spaces and standard indices in metric modelling

  2022cites this paper
• Learning Label Initialization for Time-Dependent Harmonic Extension

  2022cites this paper
• Demystifying Local Business Search Poisoning for Illicit Drug Promotion

  2022cites this paper
• Semi-Lipschitz functions and machine learning for discrete dynamical systems on graphs

  2022influential citation
• Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth

  2022cites this paper
• Graph Based Semi-supervised Learning Using Spatial Segregation Theory

  2022cites this paper
• Semi-supervised learning with dropouts

  2022cites this paper
• Fast Algorithms for ℓp-Regression

  2022cites this paper
• Nonlinear Feature Diffusion on Hypergraphs

  2022cites this paper
• A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations

  2021cites this paper
• Uniform Convergence Rates for Lipschitz Learning on Graphs

  2021cites this paper
• Almost-linear-time Weighted $\ell_p$-norm Solvers in Slightly Dense Graphs via Sparsification

  2021cites this paper
• Hardness of Graph-Structured Algebraic and Symbolic Problems

  2021cites this paper
• A nonlinear diffusion method for semi-supervised learning on hypergraphs

  2021cites this paper
• Performing Group Difference Testing on Graph Structured Data From GANs: Analysis and Applications in Neuroimaging

  2020cites this paper
• Consistent Semi-Supervised Graph Regularization for High Dimensional Data

  2020cites this paper
• Lipschitz Bounds and Provably Robust Training by Laplacian Smoothing

  2020cites this paper
• Nonlinear Higher-Order Label Spreading

  2020cites this paper
• Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates

  2020cites this paper
• Multiscale Elliptic PDEs Upscaling and Function Approximation via Subsampled Data

  2020cites this paper
• McShane-Whitney extensions for fuzzy Lipschitz maps

  2020cites this paper
• Continuum Limit of Lipschitz Learning on Graphs

  2020cites this paper
• A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening

  2019cites this paper
• Iterative Refinement for $\ell_p$-norm Regression

  2019cites this paper
• Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization

  2019influential citation
• Analysis and algorithms for $\ell_p$-based semi-supervised learning on graphs

  2019influential citation
• On Differentially Private Graph Sparsification and Applications

  2019cites this paper
• Scale Space and Variational Methods in Computer Vision

  2019influential citation
• Function approximation via the subsampled Poincaré inequality

  2019cites this paper
• Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

  2019cites this paper
• Dreaming machine learning: Lipschitz extensions for reinforcement learning on financial markets

  2019cites this paper
• Minimal Lipschitz Extensions for Vector-Valued Functions on Finite Graphs

  2019cites this paper
• Flows in almost linear time via adaptive preconditioning

  2019cites this paper
• Graph-based Semi-Supervised & Active Learning for Edge Flows

  2019cites this paper
• Dual Space Preconditioning for Gradient Descent

  2019cites this paper
• Minimal Lipschitz and ∞-harmonic extensions of vector-valued functions on finite graphs

  2019cites this paper
• The Calculus of variations

  2019cites this paper
• A Spectral Index for Selecting the Best Alternative

  2019cites this paper
• Lipschitz Learning for Signal Recovery

  2019cites this paper
• Large data limit for a phase transition model with the p-Laplacian on point clouds

  2018influential citation
• Lipschitz regularized Deep Neural Networks generalize and are adversarially robust

  2018cites this paper
• Structural Risk Minimization for C 1 , 1 p R d q Regression

  2018cites this paper
• Structural Risk Minimization for $C^{1,1}(\mathbb{R}^d)$ Regression

  2018cites this paper
• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices

  2018cites this paper
• Properly-Weighted Graph Laplacian for Semi-supervised Learning

  2018cites this paper
• Lipschitz regularized Deep Neural Networks converge and generalize

  2018cites this paper
• Numerical Linear Algebra in the Sliding Window Model

  2018cites this paper
• Learning on Hypergraphs With Sparsity

  2018cites this paper
• When Does Label Propagation Fail? A View from a Network Generative Model

  2017cites this paper
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data

  2017influential citation
• The game theoretic p-Laplacian and semi-supervised learning with few labels

  2017influential citation
• Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning

  2016cites this paper
• On Fully Dynamic Graph Sparsifiers

  2016cites this paper
• Asymptotic behavior of \(\ell_p\)-based Laplacian regularization in semi-supervised learning

  2016cites this paper
• Iterative Algorithms for Lipschitz Learning on Graphs

  2015cites this paper
• Fast, Provable Algorithms for Isotonic Regression in all L_p-norms

  2015cites this paper
• Locality in Network Optimization

  2015cites this paper
• Discovering and Analyzing Network Function and Structure

  2015cites this paper
• Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

  2011cites this paper
• Structured Semidefinite Programming for Recovering Structured Preconditioners

  year unknowncites this paper