Improved convergence rate of kNN graph Laplacians: differentiable self-tuned affinity

In graph-based data analysis, k-nearest neighbor (kNN) graphs are widely used due to their adaptivity to local data densities. Allowing weighted edges in the graph, the kernelized graph affinity provides a more general type of kNN graph where the kNN distance is used to set the kernel bandwidth adaptively. In this work, we consider a general class of kNN graph where the graph affinity is W_{ij} = ε^{-d/2} k_0 ( | x_i - x_j |^2 / εϕ( \hat ρ(x_i), \hat ρ(x_j) )^2 ) , with \hatρ(x) being the (rescaled) kNN distance at the point x, ϕ a symmetric bi-variate function, and k_0 a non-negative function on [0,\infty). Under the manifold data setting, where N i.i.d. samples x_i are drawn from a density p on a d-dimensional unknown manifold embedded in a high dimensional Euclidean space, we prove the operator pointwise convergence of the kNN graph Laplacian to the limiting manifold operator (depending on p) at the rate of O(N^{-2/(d+6)}), up to a log factor, when k_0 and ϕ have C^3 regularity and satisfy other technical conditions. This is obtained when ε\sim N^{-2/(d+6)} and k \sim N^{6/(d+6)}, both at the optimal order to balance the theoretical bias and variance errors. Our improved convergence rate is based on a refined analysis of the kNN estimator, which can be of independent interest. We validate our theory by numerical experiments on simulated data.