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

DOI10.1016/J.ACHA.2022.06.003MaRDI QIDQ2168682zbMATH OpenOpenAlexWikidataFDO

Authors Xiuyuan Cheng, Nan Wu

Publication date 26 August 2022

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.09875

zbMATH Keywords

Gaussian kernelgraph Laplacianheat kernelLaplace-Beltrami operatormanifold learningspectral convergence

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) PDEs on manifolds (35R01) Relations of PDEs with special manifold structures (Riemannian, Finsler, etc.) (58J60) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Numerical methods for eigenvalue problems for boundary value problems involving PDEs (65N25) Learning and adaptive systems in artificial intelligence (68T05)

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 $epsilonsim(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 $epsilonsim(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.

Recommendations

• Spectral convergence of graph Laplacian and heat kernel reconstruction in L^ from random samples
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• From graph to manifold Laplacian: the convergence rate
• Convergence of graph Laplacian with kNN self-tuned kernels
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results

Cites work

• A graph discretization of the Laplace-Beltrami operator
• Analysis of p-Laplacian regularization in semisupervised learning
• Bounds for the fundamental solution of a parabolic equation
• Consistency of spectral clustering
• Convergence of Laplacian spectra from random samples
• Diffusion maps
• Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• From graph to manifold Laplacian: the convergence rate
• Gaussian upper bounds for the heat kernel on arbitrary Riemannian manifolds
• Graph connection Laplacian methods can be made robust to noise
• Heat kernel and analysis on manifolds
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Learning Theory
• Lipschitz regularity of graph Laplacians on random data clouds
• Manifold learning with bi-stochastic kernels
• On the parabolic kernel of the Schrödinger operator
• Spectral Convergence of Diffusion Maps: Improved Error Bounds and an Alternative Normalization
• Spectral convergence of graph Laplacian and heat kernel reconstruction in L^ from random samples
• Spectral convergence of the connection Laplacian from random samples
• The Laplacian on a Riemannian manifold. An introduction to analysis on manifolds
• Think globally, fit locally under the manifold setup: asymptotic analysis of locally linear embedding
• Uniform Convergence of Adaptive Graph-Based Regularization
• Unperturbed: spectral analysis beyond Davis-Kahan
• Variable bandwidth diffusion kernels

Cited in

(15)

• Spectral convergence of graph Laplacian and heat kernel reconstruction in L^ from random samples
• Data-driven efficient solvers for Langevin dynamics on manifold in high dimensions
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• From graph to manifold Laplacian: the convergence rate
• Convergence of graph Laplacian with kNN self-tuned kernels
• scientific article; zbMATH DE number 7626797 (Why is no real title available?)
• Geometric scattering on measure spaces
• Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling
• The \(G\)-invariant graph Laplacian. I: Convergence rate and eigendecomposition.
• Kernel two-sample tests for manifold data
• Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise
• The \(G\)-invariant graph Laplacian. II: Diffusion maps
• Manifold filter-combine networks
• Manifold learning in metric spaces
• Sharp error estimates for target measure diffusion maps with applications to the committor problem

This page was built for publication: Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2168682)