Strong uniform convergence of Laplacians of random geometric and directed kNN graphs on compact manifolds

Consider n points independently sampled from a density p of class C2 on a smooth compact d-dimensional sub-manifold M of ℝm, and consider the generator of a random walk visiting these points according to a transition kernel K. We study the almost sure uniform convergence of this operator to the diffusive Laplace-Beltrami operator when n tends to infinity. This work extends known results of the past 15 years. In particular, our result does not require the kernel K to be continuous, which covers the cases of walks exploring kNN-random and geometric graphs, and convergence rates are given. The distance between the random walk generator and the limiting operator is separated into several terms: a statistical term, related to the law of large numbers, is treated with concentration tools and an approximation term that we control with tools from differential geometry. The convergence of kNN Laplacians is detailed.