# Lipschitz regularity of graph Laplacians on random data clouds

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

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

- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [Uniform Convergence Rates for Lipschitz Learning on Graphs](https://mlsanity.com/paper/2111.12370/) (2021)
- [Large sample spectral analysis of graph-based multi-manifold clustering](https://mlsanity.com/paper/2107.13610/) (2021)
- [Learning Low-Dimensional Nonlinear Structures from High-Dimensional Noisy Data: An Integral Operator Approach](https://mlsanity.com/paper/2203.00126/) (2022)
- [Hamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth](https://mlsanity.com/paper/2202.08789/) (2022)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [Topologically penalized regression on manifolds](https://mlsanity.com/paper/2110.13749/) (2021)
- [SpecNet2: Orthogonalization-free spectral embedding by neural networks](https://mlsanity.com/paper/2206.06644/) (2022)
- [Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications](https://mlsanity.com/paper/2111.03217/) (2021)
- [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)
- [Laplace Learning in Wasserstein Space](https://mlsanity.com/paper/2511.13229/) (2025)
- [Learning solution operator of dynamical systems with diffusion maps kernel ridge regression](https://mlsanity.com/paper/2512.17203/) (2025)
- [Spectral Neural Networks: Approximation Theory and Optimization Landscape](https://mlsanity.com/paper/2310.00729/) (2023)
- [Manifold learning in metric spaces](https://mlsanity.com/paper/2503.16187/) (2025)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)
- [Surrogate models for diffusion on graphs via sparse polynomials](https://mlsanity.com/paper/2502.06595/) (2025)
- [Diffusion Operator Geometry of Feedforward Representations](https://mlsanity.com/paper/2605.01107/) (2026)
- [Boundary Detection Algorithm Inspired by Locally Linear Embedding](https://mlsanity.com/paper/2406.18456/) (2024)
- [Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds](https://mlsanity.com/paper/2410.14539/) (2024)
- [How well behaved is finite dimensional Diffusion Maps?](https://mlsanity.com/paper/2412.03992/) (2024)
- [Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization](https://mlsanity.com/paper/2510.02308/) (2025)
- [Energy Approach from varepsilon-Graph to Continuum Diffusion Model with Connectivity Functional](https://mlsanity.com/paper/2510.25114/) (2025)
- [Learning manifold diffusion semigroups from graph transition matrices](https://mlsanity.com/paper/2605.25383/) (2026)
- [Auditing Finite-Lag Statistics of Recurrent Representations](https://mlsanity.com/paper/2607.01746/) (2026)

## Abstract (arXiv)

In this paper we study Lipschitz regularity of elliptic PDEs on geometric graphs, constructed from random data points. The data points are sampled from a distribution supported on a smooth manifold. The family of equations that we study arises in data analysis in the context of graph-based learning and contains, as important examples, the equations satisfied by graph Laplacian eigenvectors. In particular, we prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues. Our analysis relies on a probabilistic coupling argument of suitable random walks at the continuum level, and an interpolation method for extending functions on random point clouds to the continuum manifold. As a byproduct of our general regularity results, we obtain high probability L^∞ and approximate C0,1 convergence rates for the convergence of graph Laplacian eigenvectors towards eigenfunctions of the corresponding weighted Laplace-Beltrami operators. The convergence rates we obtain scale like the L2-convergence rates established by two of the authors in previous work.