# Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2018.

## Built on by (most cited first, 30 of 70)

- [Neural Operator: Learning Maps Between Function Spaces](https://mlsanity.com/paper/2108.08481/) (2021)
- [Physics-Informed Deep Neural Operator Networks](https://mlsanity.com/paper/2207.05748/) (2022)
- [Manifold learning: what, how, and why](https://mlsanity.com/paper/2311.03757/) (2023)
- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [LDLE: Low Distortion Local Eigenmaps](https://mlsanity.com/paper/2101.11055/) (2021)
- [Minimum intrinsic dimension scaling for entropic optimal transport](https://mlsanity.com/paper/2306.03398/) (2023)
- [Uniform Convergence Rates for Lipschitz Learning on Graphs](https://mlsanity.com/paper/2111.12370/) (2021)
- [Kernel Two-Sample Tests for Manifold Data](https://mlsanity.com/paper/2105.03425/) (2021)
- [Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey](https://mlsanity.com/paper/2106.02154/) (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)
- [Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling](https://mlsanity.com/paper/2209.08004/) (2022)
- [Optimization on Manifolds via Graph Gaussian Processes](https://mlsanity.com/paper/2210.10962/) (2022)
- [Poisson Reweighted Laplacian Uncertainty Sampling for Graph-based Active Learning](https://mlsanity.com/paper/2210.15786/) (2022)
- [Representing and Learning Functions Invariant Under Crystallographic Groups](https://mlsanity.com/paper/2306.05261/) (2023)
- [Continuum Limits of Ollivier's Ricci Curvature on data clouds: pointwise consistency and global lower bounds](https://mlsanity.com/paper/2307.02378/) (2023)
- [Error Bounds of the Invariant Statistics in Machine Learning of Ergodic Ito Diffusions](https://mlsanity.com/paper/2105.10102/) (2021)
- [Topologically penalized regression on manifolds](https://mlsanity.com/paper/2110.13749/) (2021)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [How do kernel-based sensor fusion algorithms behave under high dimensional noise?](https://mlsanity.com/paper/2111.10940/) (2021)
- [SpecNet2: Orthogonalization-free spectral embedding by neural networks](https://mlsanity.com/paper/2206.06644/) (2022)
- [Multi-modal Differentiable Unsupervised Feature Selection](https://mlsanity.com/paper/2303.09381/) (2023)
- [Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression](https://mlsanity.com/paper/2311.00140/) (2023)
- [Boundary Estimation from Point Clouds: Algorithms, Guarantees and Applications](https://mlsanity.com/paper/2111.03217/) (2021)
- [Rates of Convergence for Regression with the Graph Poly-Laplacian](https://mlsanity.com/paper/2209.02305/) (2022)

## Abstract (arXiv)

We study the convergence of the graph Laplacian of a random geometric graph generated by an i.i.d. sample from a m-dimensional submanifold M in Rd as the sample size n increases and the neighborhood size h tends to zero. We show that eigenvalues and eigenvectors of the graph Laplacian converge with a rate of OBig(big(fraclog nnbig)^frac12mBig) to the eigenvalues and eigenfunctions of the weighted Laplace-Beltrami operator of M. No information on the submanifold M is needed in the construction of the graph or the "out-of-sample extension" of the eigenvectors. Of independent interest is a generalization of the rate of convergence of empirical measures on submanifolds in Rd in infinity transportation distance.