Convergence of Graph Laplacian with kNN Self-tuned Kernels

Abstract

Kernelized Gram matrix $W$ constructed from data points $\{x_i{\}}_{i=1}^N$ as $W_{ij}=k_0(\frac{\Vert x_i-x_j{\Vert }^2}{{\sigma }^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 ${\sigma }_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{\Vert x_i-x_j{\Vert }^2}{\epsilon \hat{\rho }(x_i)\hat{\rho }(x_j)})/\hat{\rho }(x_i{)}^{\alpha }\hat{\rho }(x_j{)}^{\alpha }$, where $\hat{\rho }$ 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 ${\Delta }_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 $\hat{\rho }$ which bounds the relative estimation error $|\hat{\rho }-\bar{\rho }|/\bar{\rho }$ uniformly with high probability, where $\bar{\rho }=p^{-1/d}$, 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.

References in corpus (10)

• Consistency of spectral clustering
• Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck operators
• SpectralNet: Spectral Clustering using Deep Neural Networks
• Unperturbed: spectral analysis beyond Davis-Kahan
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Precise asymptotics of small eigenvalues of reversible diffusions in the metastable regime
• Manifold learning with bi-stochastic kernels
• Spectral Convergence Rate of Graph Laplacian
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in $L^{\infty }$ from Random Samples

Cited by in corpus (1)

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