Papers › Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
Xiuyuan Cheng, Nan Wu
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 ϵ∼(logN/ 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 ϵ∼(logN/N)^(1/(d/2+3)), both eigenvalue and eigenvector rates are N^(-1/(d/2+3)). These rates are up to a logN 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections