Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs

Abstract

In this paper we improve the spectral convergence rates for graph-based approximations of Laplace-Beltrami operators constructed from random data. We utilize regularity of the continuum eigenfunctions and strong pointwise consistency results to prove that spectral convergence rates are the same as the pointwise consistency rates for graph Laplacians. In particular, for an optimal choice of the graph connectivity $\epsilon$, our results show that the eigenvalues and eigenvectors of the graph Laplacian converge to those of the Laplace-Beltrami operator at a rate of $O(n^{-1/(m+4)})$, up to log factors, where $m$ is the manifold dimension and $n$ is the number of vertices in the graph. Our approach is general and allows us to analyze a large variety of graph constructions that include $\epsilon$-graphs and $k$-NN graphs.

References in corpus (13)

• Consistency of spectral clustering
• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• Optimal construction of k-nearest neighbor graphs for identifying noisy clusters
• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• An Analysis of the Convergence of Graph Laplacians
• Nonparametric sparsity and regularization
• Poisson Learning: Graph Based Semi-Supervised Learning At Very Low Label Rates
• Convergence of Laplacian spectra from random samples
• On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
• Geometric structure of graph Laplacian embeddings
• Local Regularization of Noisy Point Clouds: Improved Global Geometric Estimates and Data Analysis
• Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods
• A continuum limit for the PageRank algorithm

Cited by in corpus (10)

• Uniform Convergence Rates for Lipschitz Learning on Graphs
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in $L^{\infty }$ from Random Samples
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Consistency of archetypal analysis
• Unlabeled Data Help in Graph-Based Semi-Supervised Learning: A Bayesian Nonparametrics Perspective
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• Large sample spectral analysis of graph-based multi-manifold clustering
• Convergence of Laplacian Eigenmaps and its Rate for Submanifolds with Singularities
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs