The spectrum of the graph Laplacian plays an important role in data science, and forms the foundation for clustering and dimension reduction algorithms, such as spectral clustering, Laplacian eigenmaps, and diffusion maps. In this talk, we will introduce new Lipschitz regularity results for graph Poisson equations, which, in particular, apply to eigenvalue problems. The proofs use the method of coupled random walks to prove Lipschitz estimates for a corresponding non-local equation, and a new method for interpolating from the graph to the continuum. As a consequence of our results, we prove C^{0,1} convergence rates for the eigenvectors of the graph Laplacian to the eigenfunctions of the corresponding weighted Laplace-Beltrami operator on the data manifold. We will conclude the talk by discussing the difficulty with proving these results near the graph-connectivity threshold, where ideas from homogenization and/or percolation theory will be needed.
Copyright. All Rights Reserved.