mlsanityData to 7 Oct 2026

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

arXiv 1910.13476 ↗First posted 29 Oct 2019math.PR cs.LG math.SPcited by 18

Not on the map. Why?

Abstract (arXiv)

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 varepsilon, 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 varepsilon-graphs and k-NN graphs.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 5; 2023: 2; 2024: 1; 2025: 0; 2026: 1.

18 papers.

Sort:

  1. 2023Manifold learning: what, how, and whycited by 66
  2. 2021Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolationcited by 24
  3. 2021Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphscited by 13
  4. 2022Convolutional Neural Networks on Manifolds: From Graphs and Backcited by 13
  5. 2021Stability of Neural Networks on Manifolds to Relative Perturbationscited by 9
  6. 2021Uniform Convergence Rates for Lipschitz Learning on Graphscited by 9
  7. 2023Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offscited by 9
  8. 2021Stability to Deformations of Manifold Filters and Manifold Neural Networkscited by 8
  9. 2021Kernel Two-Sample Tests for Manifold Datacited by 7
  10. 2022Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noisecited by 7
  11. 2022Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scalingcited by 7
  12. 2021Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphscited by 5
6 more
  1. 2022SpecNet2: Orthogonalization-free spectral embedding by neural networkscited by 5
  2. 2022Convolutional Filtering on Sampled Manifoldscited by 4
  3. 2026GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operatorscited by 3
  4. 2021Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolationcited by 1
  5. 2024Nonparametric regression on random geometric graphs sampled from submanifoldscited by 1
  6. 2021Convergence of Laplacian Eigenmaps and its Rate for Submanifolds with Singularitiescited by 0