Convergence of Graph Laplacian with kNN Self-tuned Kernels

Kernelized Gram matrix W constructed from data points xii=1N as Wij= k0( frac | xi - xj |2 σ2 ) is widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth σ, and a common practice called self-tuned kernel adaptively sets a σi at each point xi by the k-nearest neighbor (kNN) distance. When xi'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 LN to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels W(α)ij = k0( frac | xi - xj |2 ε hatρ(xi) hatρ(xj))/hatρ(xi)α hatρ(xj)α, where hatρ is the estimated bandwidth function by kNN, and the limiting operator is also parametrized by α. When α = 1, the limiting operator is the weighted manifold Laplacian Deltap. Specifically, we prove the point-wise convergence of LN f and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a C0 consistency for hatρ which bounds the relative estimation error |hatρ - barρ|/barρ uniformly with high probability, where barρ = 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.