# Uniform Convergence Rates for Lipschitz Learning on Graphs

arXiv: https://arxiv.org/abs/2111.12370 · HTML: https://mlsanity.com/paper/2111.12370/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 24 Nov 2021.

## Builds on (most cited first, 16 of 16)

- [Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator](https://mlsanity.com/paper/1801.10108/) (2018)
- [Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates](https://mlsanity.com/paper/2006.11184/) (2020)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (2020)
- [Continuum limit of total variation on point clouds](https://mlsanity.com/paper/1403.6355/) (2014)
- [The game theoretic p-Laplacian and semi-supervised learning with few labels](https://mlsanity.com/paper/1711.10144/) (2017)
- [Properly-weighted graph Laplacian for semi-supervised learning](https://mlsanity.com/paper/1810.04351/) (2018)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates](https://mlsanity.com/paper/2006.02765/) (2020)
- [Algorithms for Lipschitz Learning on Graphs](https://mlsanity.com/paper/1505.00290/) (2015)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data](https://mlsanity.com/paper/1710.10364/) (2017)
- [Analysis and algorithms for ℓp-based semi-supervised learning on graphs](https://mlsanity.com/paper/1901.05031/) (2019)
- [A maximum principle argument for the uniform convergence of graph Laplacian regressors](https://mlsanity.com/paper/1901.10089/) (2019)
- [Continuum Limit of Lipschitz Learning on Graphs](https://mlsanity.com/paper/2012.03772/) (2020)
- [A continuum limit for the PageRank algorithm](https://mlsanity.com/paper/2001.08973/) (2020)

## Built on by (most cited first, 9 of 9)

- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [A mean curvature flow arising in adversarial training](https://mlsanity.com/paper/2404.14402/) (2024)
- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data Classification](https://mlsanity.com/paper/2305.16239/) (2023)
- [Graph-Based Semi-Supervised Segregated Lipschitz Learning](https://mlsanity.com/paper/2411.03273/) (2024)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)
- [Energy Approach from varepsilon-Graph to Continuum Diffusion Model with Connectivity Functional](https://mlsanity.com/paper/2510.25114/) (2025)
- [Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning](https://mlsanity.com/paper/2605.19185/) (2026)

## Abstract (arXiv)

Lipschitz learning is a graph-based semi-supervised learning method where one extends labels from a labeled to an unlabeled data set by solving the infinity Laplace equation on a weighted graph. In this work we prove uniform convergence rates for solutions of the graph infinity Laplace equation as the number of vertices grows to infinity. Their continuum limits are absolutely minimizing Lipschitz extensions with respect to the geodesic metric of the domain where the graph vertices are sampled from. We work under very general assumptions on the graph weights, the set of labeled vertices, and the continuum domain. Our main contribution is that we obtain quantitative convergence rates even for very sparsely connected graphs, as they typically appear in applications like semi-supervised learning. In particular, our framework allows for graph bandwidths down to the connectivity radius. For proving this we first show a quantitative convergence statement for graph distance functions to geodesic distance functions in the continuum. Using the "comparison with distance functions" principle, we can pass these convergence statements to infinity harmonic functions and absolutely minimizing Lipschitz extensions.