Abstract
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 $\epsilon \sim (\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 $\epsilon \sim (\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.
Introduction
In manifold learning, high-dimensional data is often assumed to lie on a low-dimensional geometric structure $\mathcal{M}$. Algorithms such as spectral clustering, Laplacian eigenmaps, and diffusion maps rely on constructing a "graph Laplacian" matrix from $N$ data points to approximate the continuous Laplace-Beltrami operator $\Delta_{\mathcal{M}}$ of the underlying manifold.
While point-wise convergence of the graph Laplacian to the continuous operator is well-established, proving the convergence of discrete eigenvalues and eigenvectors (spectral convergence) is significantly more complex. This is particularly true for the Gaussian kernel, which is ubiquitous in practice but possesses infinite support, requiring new mathematical machinery beyond traditional proofs for compactly supported kernels. This paper establishes rigorous eigen-convergence rates for Gaussian kernels using a novel "manifold heat interpolation" technique.
Methodology: Manifold Heat Interpolation
The authors employ a variational approach based on Dirichlet forms to express eigenvalues as optimization problems over functions. A primary methodological challenge in proving eigenvalue lower bounds is mapping discrete eigenvectors (vectors in $\mathbb{R}^N$) back into continuous, smooth functions on the manifold.
The standout novelty is manifold heat interpolation, which achieves this mapping by convolving discrete vectors with the manifold's heat kernel. This choice is motivated by the fact that the Gaussian kernel used to build the graph affinity matrix in the ambient space naturally approximates the short-time heat diffusion process on the intrinsic manifold. The proof follows a four-step bootstrap strategy:
- Eigenvalue Upper Bound: Established via Dirichlet form convergence.
- Crude Lower Bound: Derived using the novel manifold heat interpolation.
- Eigenvector Consistency: Proved up to the point-wise convergence rate.
- Refined Eigenvalue Consistency: Improved to match the faster Dirichlet form rate.
This framework also extends to the density-corrected graph Laplacian, which successfully recovers manifold geometry even when data is sampled non-uniformly.
Theoretical Convergence Results
The paper establishes rigorous bounds for the first $k$ eigenvalues and eigenvectors. A key insight is that using a smooth $C^2$ kernel like the Gaussian improves the bias error of point-wise convergence from $O(\sqrt{\epsilon})$ to $O(\epsilon)$ compared to indicator kernels, directly translating to faster eigenvector convergence.
As summarized in the table above, the optimal kernel bandwidth parameter $\epsilon$ varies depending on the target metric:
- Eigenvalue convergence rate: $O((\log N/N)^{1/(d/2+2)})$ is achieved when $\epsilon \sim (\log N/N)^{1/(d/2+2)}$.
- Eigenvector convergence rate (2-norm): $O((\log N/N)^{1/(d/2+3)})$ is achieved when $\epsilon \sim (\log N/N)^{1/(d/2+3)}$.
- Combined convergence: When $\epsilon \sim (\log N/N)^{1/(d/2+3)}$, both eigenvalue and eigenvector rates are $N^{-1/(d/2+3)}$.
Numerical Verification
To verify these theoretical rates, the authors utilized synthetic datasets where true manifold eigenvalues are analytically known:
- 1D Circle ($S^1$): Embedded in $\mathbb{R}^4$, tested with both uniform and non-uniform data sampling densities.
- 2D Sphere ($S^2$): Embedded in $\mathbb{R}^3$, tested with uniform sampling.
Numerical experiments confirmed that the empirical error scaling closely matches or slightly exceeds the theoretical predictions across different Laplacian types.
Conclusion and Future Work
This work provides a rigorous foundation for the spectral convergence of Gaussian kernelized graph Laplacians. By bridging ambient Gaussian kernels and intrinsic manifold heat kernels, the authors avoid the need for rigid spatial tessellations used in prior works. Future research directions include extending these proofs to manifolds with boundaries, investigating adaptive bandwidth schemes, and establishing consistency in stronger norms such as the $L^\infty$-norm.
Summary updated