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 Wij = ε-d/2 k0 ( | xi - xj |2 / ε φ( hat ρ(xi), hat ρ(xj) )2 ) , with hatρ(x) being the (rescaled) kNN distance at the point x, φ a symmetric bi-variate function, and k0 a non-negative function on [0,∞). Under the manifold data setting, where N i.i.d. samples xi 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 k0 and φ have C3 regularity and satisfy other technical conditions. This is obtained when ε ~ N-2/(d+6) and k ~ N6/(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.