Strong uniform convergence of Laplacians of random geometric and directed <i>k</i> NN graphs on compact manifolds

Abstract Consider n points independently sampled from a density p of class $\mathcal{C}^2$ on a smooth compact d -dimensional submanifold $\mathcal{M}$ of $\mathbb{R}^m$ , and consider the random walk visiting these points according to a transition kernel K . We study the almost sure uniform convergence of the generator of this process to the diffusive Laplace–Beltrami operator when n tends to infinity, from which we establish the convergence of the random walk to a diffusion process on the manifold. In contrast to known results, our result does not require the kernel K to be continuous, which covers the cases of walks exploring k -nearest neighbor ( k NN) 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 case of k NN Laplacians is detailed. The convergence of the stochastic processes having these operators as generators is also studied, by establishing additional tightness results of their distributions on the space of càdlàg functions.