Convergence of graph Laplacian with kNN self-tuned kernels

DOI10.1093/IMAIAI/IAAB019MaRDI QIDQ5044113zbMATH OpenOpenAlexFDO

Authors Xiuyuan Cheng, H.-T. Wu

Publication date 24 October 2022

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-nearest neighbor density estimatorgraph Laplacianmanifold learning

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81) Density estimation (62G07)

Abstract: Kernelized Gram matrix $W$ constructed from data points ${x_i}_{i=1}^N$ as $W_{ij}=k_0(frac|x_i-x_j{|}^{2}sigm{a}^2)$ is widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth $sigma$, and a common practice called self-tuned kernel adaptively sets a $sigm{a}_i$ at each point $x_i$ by the $k$-nearest neighbor (kNN) distance. When $x_i$'s are sampled from a $d$-dimensional manifold embedded in a possibly high-dimensional space, unlike with fixed-bandwidth kernels, theoretical results of graph Laplacian convergence with self-tuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operator $L_N$ to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels $W_{ij}^{(alpha)}=k_0(frac|x_i-x_j{|}^{2}epsilonhatho(x_i)hatho(x_j))/hatho(x_i{)}^{a}lphahatho(x_j{)}^{a}lpha$, where $hatho$ is the estimated bandwidth function {by kNN}, and the limiting operator is also parametrized by $alpha$. When $alpha=1$, the limiting operator is the weighted manifold Laplacian $Delt{a}_p$. Specifically, we prove the point-wise convergence of $L_{N}f$ and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a $C^0$ consistency for $hatho$ which bounds the relative estimation error $$ uniformly with high probability, where $$, and $p$ is the data density function. Our theoretical results reveal the advantage of self-tuned kernel over fixed-bandwidth kernel via smaller variance error in low-density regions. In the algorithm, no prior knowledge of $d$ or data density is needed. The theoretical results are supported by numerical experiments on simulated data and hand-written digit image data.

Recommendations

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• From graph to manifold Laplacian: the convergence rate
• Graph Laplacians and their convergence on random neighborhood graphs
• Towards a theoretical foundation for Laplacian-based manifold methods
• Learning Theory

Cited in

(12)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• scientific article; zbMATH DE number 7626797 (Why is no real title available?)
• Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
• Spatiotemporal analysis using Riemannian composition of diffusion operators
• Kernel two-sample tests for manifold data
• Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise
• Boundary detection algorithm inspired by locally linear embedding
• Manifold learning in metric spaces
• Sharp error estimates for target measure diffusion maps with applications to the committor problem
• Adaptive Bayesian regression on data with low intrinsic dimensionality
• Improved convergence rate of \(k\mathrm{NN}\) graph Laplacians: differentiable self-tuned affinity
• Variable bandwidth diffusion kernels

This page was built for publication: Convergence of graph Laplacian with kNN self-tuned kernels

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