# Convergence of Graph Laplacian with kNN Self-tuned Kernels

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2020.

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

- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [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)
- [Conditional Generative Modeling for High-dimensional Marked Temporal Point Processes](https://mlsanity.com/paper/2305.12569/) (2023)
- [Spatiotemporal Analysis Using Riemannian Composition of Diffusion Operators](https://mlsanity.com/paper/2201.08530/) (2022)
- [SpecNet2: Orthogonalization-free spectral embedding by neural networks](https://mlsanity.com/paper/2206.06644/) (2022)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [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)
- [Strong uniform convergence of Laplacians of random geometric and directed kNN graphs on compact manifolds](https://mlsanity.com/paper/2212.10287/) (2022)
- [StreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm](https://mlsanity.com/paper/2108.10411/) (2021)
- [Graph Laplacians on Shared Nearest Neighbor graphs and graph Laplacians on k-Nearest Neighbor graphs having the same limit](https://mlsanity.com/paper/2302.12399/) (2023)
- [Boundary Detection Algorithm Inspired by Locally Linear Embedding](https://mlsanity.com/paper/2406.18456/) (2024)
- [Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization](https://mlsanity.com/paper/2510.02308/) (2025)
- [Learning manifold diffusion semigroups from graph transition matrices](https://mlsanity.com/paper/2605.25383/) (2026)

## Abstract (arXiv)

Kernelized Gram matrix W constructed from data points xii=1N as Wij= k0( frac | xi - xj |2 σ2 ) is widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth σ, and a common practice called self-tuned kernel adaptively sets a σi at each point xi by the k-nearest neighbor (kNN) distance. When xi's are sampled from a d-dimensional manifold embedded in a possibly high-dimensional space, unlike with fixed-bandwidth kernels, theoretical results of graph Laplacian convergence with self-tuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operator LN to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels W(α)ij = k0( frac | xi - xj |2 ε hatρ(xi) hatρ(xj))/hatρ(xi)α hatρ(xj)α, where hatρ is the estimated bandwidth function by kNN, and the limiting operator is also parametrized by α. When α = 1, the limiting operator is the weighted manifold Laplacian Deltap. Specifically, we prove the point-wise convergence of LN f  and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a C0 consistency for hatρ which bounds the relative estimation error |hatρ - barρ|/barρ uniformly with high probability, where barρ = p-1/d, and p is the data density function. Our theoretical results reveal the advantage of self-tuned kernel over fixed-bandwidth kernel via smaller variance error in low-density regions. In the algorithm, no prior knowledge of d or data density is needed. The theoretical results are supported by numerical experiments on simulated data and hand-written digit image data.