Reproduce “Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation” on OpenResearch

About this paper

Xiuyuan Cheng, Nan Wu

This work from Duke University provides explicit spectral convergence rates for Gaussian kernelized graph Laplacians, showing how their eigenvalues and eigenvectors approximate those of the continuous Laplace-Beltrami operator on a low-dimensional manifold. It establishes that eigenvalue convergence is faster than eigenvector convergence, achieving rates of O(N^(-1/(d/2+2))) and O(N^(-1/(d/2+3))) respectively, and extends these guarantees to density-corrected Laplacians for non-uniformly sampled data.

Key insights

• Eigenvalue convergence to the continuous Laplace-Beltrami operator is generally faster than eigenvector convergence, with distinct optimal kernel bandwidths required for each.
• The C2 smoothness of Gaussian kernels provides a superior bias error in point-wise convergence, which translates into better eigenvector convergence rates compared to compactly supported kernels.
• The intrinsic relationship between Gaussian kernels and the manifold heat kernel allows for a novel heat interpolation technique, crucial for establishing eigenvalue lower bounds in the spectral analysis.

Summary by alphaXiv.