# Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2019.

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

- [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)
- [Convolutional Neural Networks on Manifolds: From Graphs and Back](https://mlsanity.com/paper/2210.00376/) (2022)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Stability to Deformations of Manifold Filters and Manifold Neural Networks](https://mlsanity.com/paper/2106.03725/) (2021)
- [Stability of Neural Networks on Manifolds to Relative Perturbations](https://mlsanity.com/paper/2110.04702/) (2021)
- [Uniform Convergence Rates for Lipschitz Learning on Graphs](https://mlsanity.com/paper/2111.12370/) (2021)
- [Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs](https://mlsanity.com/paper/2305.18467/) (2023)
- [Kernel Two-Sample Tests for Manifold Data](https://mlsanity.com/paper/2105.03425/) (2021)
- [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)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [SpecNet2: Orthogonalization-free spectral embedding by neural networks](https://mlsanity.com/paper/2206.06644/) (2022)
- [Convolutional Filtering on Sampled Manifolds](https://mlsanity.com/paper/2211.11058/) (2022)
- [GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators](https://mlsanity.com/paper/2603.16849/) (2026)
- [Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation](https://mlsanity.com/paper/2108.08687/) (2021)
- [Nonparametric regression on random geometric graphs sampled from submanifolds](https://mlsanity.com/paper/2405.20909/) (2024)
- [Convergence of Laplacian Eigenmaps and its Rate for Submanifolds with Singularities](https://mlsanity.com/paper/2110.08138/) (2021)

## Abstract (arXiv)

In this paper we improve the spectral convergence rates for graph-based approximations of Laplace-Beltrami operators constructed from random data. We utilize regularity of the continuum eigenfunctions and strong pointwise consistency results to prove that spectral convergence rates are the same as the pointwise consistency rates for graph Laplacians. In particular, for an optimal choice of the graph connectivity varepsilon, our results show that the eigenvalues and eigenvectors of the graph Laplacian converge to those of the Laplace-Beltrami operator at a rate of O(n-1/(m+4)), up to log factors, where m is the manifold dimension and n is the number of vertices in the graph. Our approach is general and allows us to analyze a large variety of graph constructions that include varepsilon-graphs and k-NN graphs.