Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

We study the spectral convergence of graph Laplacians to the Laplace-Beltrami operator when the kernelized graph affinity matrix is constructed from N random samples on a d-dimensional manifold in an ambient Euclidean space. By analyzing Dirichlet form convergence and constructing candidate approximate eigenfunctions via convolution with manifold heat kernel, we prove eigen-convergence with rates as N increases. The best eigenvalue convergence rate is N−1/(d/2+2) (when the kernel bandwidth parameter ϵ∼(log⁡N/N)1/(d/2+2)) and the best eigenvector 2-norm convergence rate is N−1/(d/2+3) (when ϵ∼(log⁡N/N)1/(d/2+3)). These rates hold up to a log⁡N-factor for finitely many low-lying eigenvalues of both un-normalized and normalized graph Laplacians. When data density is non-uniform, we prove the same rates for the density-corrected graph Laplacian, and we also establish new operator point-wise convergence rate and Dirichlet form convergence rate as intermediate results. Numerical results are provided to support the theory.