Spectral Convergence Rate of Graph Laplacian
This work addresses the theoretical foundation for spectral manifold learning algorithms, such as diffusion maps and spectral clustering, by providing convergence guarantees for practitioners in machine learning and data analysis.
The paper establishes the spectral convergence rate of the graph Laplacian for graphs constructed from random samples on a compact submanifold, implying consistency for spectral clustering algorithms, with a numerical study suggesting the need for denoising.
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 $\mathbb{R}^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.