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

Jeff Calder, Nicolás García Trillos

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


In this paper we improve the spectral convergence rates for graph-based approximations of weighted 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 ε, our results show that the eigenvalues and eigenvectors of the graph Laplacian converge to those of a weighted 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 ε-graphs and k-NN graphs. We also present the results of numerical experiments analyzing convergence rates on the two dimensional sphere.

Original languageEnglish (US)
Pages (from-to)123-175
Number of pages53
JournalApplied and Computational Harmonic Analysis
StatePublished - Sep 2022

Bibliographical note

Funding Information:
JC was supported by NSF-DMS grant 1713691 . NGT was supported by NSF grant DMS 1912802 .

Publisher Copyright:
© 2022 Elsevier Inc.


  • Discrete to continuum
  • Graph Laplacian
  • Laplace-Beltrami operator
  • Rates of convergence
  • Spectral convergence


Dive into the research topics of 'Improved spectral convergence rates for graph Laplacians on ε-graphs and k-NN graphs'. Together they form a unique fingerprint.

Cite this