# Spectral Convergence Rate of Graph Laplacian

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2015.

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

- [Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation](https://mlsanity.com/paper/2101.09875/) (2021)
- [Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise](https://mlsanity.com/paper/2206.11386/) (2022)
- [Sharp error estimates for target measure diffusion maps with applications to the committor problem](https://mlsanity.com/paper/2312.14418/) (2023)
- [Higher-Order Regularization Learning on Hypergraphs](https://mlsanity.com/paper/2510.26533/) (2025)
- [Non-Parametric Manifold Learning](https://mlsanity.com/paper/2107.08089/) (2021)
- [How well behaved is finite dimensional Diffusion Maps?](https://mlsanity.com/paper/2412.03992/) (2024)

## Abstract (arXiv)

Laplacian Eigenvectors of the graph constructed from a data set are used in many spectral manifold learning algorithms such as diffusion maps and spectral clustering. Given a graph constructed from a random sample of a d-dimensional compact submanifold M in ℝD, we establish the spectral convergence rate of the graph Laplacian. It implies the consistency of the spectral clustering algorithm via a standard perturbation argument. A simple numerical study indicates the necessity of a denoising step before applying spectral algorithms.