Lipschitz regularity of graph Laplacians on random data clouds
  In this paper we study Lipschitz regularity of elliptic PDEs on geometric
graphs, constructed from random data points. The data points are sampled from a
distribution supported on a smooth manifold. The family of equations that we
study arises in data analysis in the context of graph-based learning and
contains, as important examples, the equations satisfied by graph Laplacian
eigenvectors. In particular, we prove high probability interior and global
Lipschitz estimates for solutions of graph Poisson equations. Our results can
be used to show that graph Laplacian eigenvectors are, with high probability,
essentially Lipschitz regular with constants depending explicitly on their
corresponding eigenvalues. Our analysis relies on a probabilistic coupling
argument of suitable random walks at the continuum level, and an interpolation
method for extending functions on random point clouds to the continuum
manifold. As a byproduct of our general regularity results, we obtain high
probability $L^\infty$ and approximate $\mathcal{C}^{0,1}$ convergence rates
for the convergence of graph Laplacian eigenvectors towards eigenfunctions of
the corresponding weighted Laplace-Beltrami operators. The convergence rates we
obtain scale like the $L^2$-convergence rates established by two of the authors
in previous work.
