Graphs Laplacians are used for various tasks in machine learning, e.g. for spectral clustering, or to find adapted bases of eigenfunctions that can be used as feature maps. In the case where the underlying graph is a neighborhood graph built on top of n i.i.d. points sampled on a submanifold M, the discrete Laplacian operator is known to converge towards a weighted Laplace operator on M. We focus on exhibiting rates of convergence for the eigenvalues of the operators. Namely, if the density p is of regularity s (large enough) and the manifold is of dimension d, we show that the estimation of the eigenvalues of the p-weighted Laplace operator can be done as quickly as the estimation of the density itself, with rates of order n^(-s/(2s+d)). We are also able to show that this rate is minimax optimal in the case of a curve (d=1).

(Joint work with Clément Berenfeld and Yann Chaubet)