# Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 25 Jan 2021.

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

- [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)
- [Analysis of p-Laplacian Regularization in Semi-Supervised Learning](https://mlsanity.com/paper/1707.06213/) (2017)
- [Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation](https://mlsanity.com/paper/2006.02037/) (2020)
- [Lipschitz regularity of graph Laplacians on random data clouds](https://mlsanity.com/paper/2007.06679/) (2020)
- [Manifold learning with bi-stochastic kernels](https://mlsanity.com/paper/1711.06711/) (2017)
- [Spectral Convergence of the connection Laplacian from random samples](https://mlsanity.com/paper/1306.1587/) (2013)
- [Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs](https://mlsanity.com/paper/1910.13476/) (2019)
- [Convergence of Graph Laplacian with kNN Self-tuned Kernels](https://mlsanity.com/paper/2011.01479/) (2020)
- [Asymptotic behavior of ℓp-based Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/1603.00564/) (2016)
- [Unperturbed: spectral analysis beyond Davis-Kahan](https://mlsanity.com/paper/1706.06516/) (2017)
- [Doubly-Stochastic Normalization of the Gaussian Kernel is Robust to Heteroskedastic Noise](https://mlsanity.com/paper/2006.00402/) (2020)
- [Spectral Convergence Rate of Graph Laplacian](https://mlsanity.com/paper/1510.08110/) (2015)

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

- [Manifold Interpolating Optimal-Transport Flows for Trajectory Inference](https://mlsanity.com/paper/2206.14928/) (2022)
- [Geometric Scattering on Measure Spaces](https://mlsanity.com/paper/2208.08561/) (2022)
- [LDLE: Low Distortion Local Eigenmaps](https://mlsanity.com/paper/2101.11055/) (2021)
- [The Manifold Scattering Transform for High-Dimensional Point Cloud Data](https://mlsanity.com/paper/2206.10078/) (2022)
- [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)
- [A Convergence Rate for Manifold Neural Networks](https://mlsanity.com/paper/2212.12606/) (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)
- [Multi-modal Differentiable Unsupervised Feature Selection](https://mlsanity.com/paper/2303.09381/) (2023)
- [A kernel-based analysis of Laplacian Eigenmaps](https://mlsanity.com/paper/2402.16481/) (2024)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [Manifold Filter-Combine Networks](https://mlsanity.com/paper/2307.04056/) (2023)
- [Manifold learning in metric spaces](https://mlsanity.com/paper/2503.16187/) (2025)
- [G-invariant diffusion maps](https://mlsanity.com/paper/2306.07350/) (2023)
- [Spectral Self-supervised Feature Selection](https://mlsanity.com/paper/2407.09061/) (2024)
- [The G-invariant graph Laplacian](https://mlsanity.com/paper/2303.17001/) (2023)
- [Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds](https://mlsanity.com/paper/2410.14539/) (2024)
- [Convergence of Manifold Filter-Combine Networks](https://mlsanity.com/paper/2410.14639/) (2024)
- [How well behaved is finite dimensional Diffusion Maps?](https://mlsanity.com/paper/2412.03992/) (2024)
- [Convergence of graph Dirichlet energies and graph Laplacians on intersecting manifolds of varying dimensions](https://mlsanity.com/paper/2509.24458/) (2025)
- [Learning manifold diffusion semigroups from graph transition matrices](https://mlsanity.com/paper/2605.25383/) (2026)
- [Group Invariant Spectral Embedding](https://mlsanity.com/paper/2607.08987/) (2026)

## Abstract (arXiv)

This work studies the spectral convergence of graph Laplacian to the Laplace-Beltrami operator when the graph affinity matrix is constructed from N random samples on a d-dimensional manifold embedded in a possibly high dimensional space. By analyzing Dirichlet form convergence and constructing candidate approximate eigenfunctions via convolution with manifold heat kernel, we prove that, with Gaussian kernel, one can set the kernel bandwidth parameter ε ~ (log N/ N)1/(d/2+2) such that the eigenvalue convergence rate is N-1/(d/2+2) and the eigenvector convergence in 2-norm has rate N-1/(d+4); When ε ~ (log N/N)1/(d/2+3), both eigenvalue and eigenvector rates are N-1/(d/2+3). These rates are up to a log N factor and proved for finitely many low-lying eigenvalues. The result holds for un-normalized and random-walk graph Laplacians when data are uniformly sampled on the manifold, as well as the density-corrected graph Laplacian (where the affinity matrix is normalized by the degree matrix from both sides) with non-uniformly sampled data. As an intermediate result, we prove new point-wise and Dirichlet form convergence rates for the density-corrected graph Laplacian. Numerical results are provided to verify the theory.