Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator

DOI10.1007/S10208-019-09436-WMaRDI QIDQ2194775zbMATH OpenOpenAlexWikidataFDO

Authors Nicolás García Trillos, Moritz Gerlach, Matthias Hein, Dejan Slepčev

Publication date 7 September 2020

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.10108

zbMATH Keywords

discrete to continuum limitgraph Laplacianpoint cloudrandom geometric graphspectral clusteringspectral convergence

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Spectral problems; spectral geometry; scattering theory on manifolds (58J50) Geometric probability and stochastic geometry (60D05) Asymptotic properties of nonparametric inference (62G20) Statistics on manifolds (62R30) Numerical methods for eigenvalue problems for boundary value problems involving PDEs (65N25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study the convergence of the graph Laplacian of a random geometric graph generated by an i.i.d. sample from a $m$-dimensional submanifold $M$ in $R^d$ as the sample size $n$ increases and the neighborhood size $h$ tends to zero. We show that eigenvalues and eigenvectors of the graph Laplacian converge with a rate of $$ to the eigenvalues and eigenfunctions of the weighted Laplace-Beltrami operator of $M$. No information on the submanifold $M$ is needed in the construction of the graph or the "out-of-sample extension" of the eigenvectors. Of independent interest is a generalization of the rate of convergence of empirical measures on submanifolds in $R^d$ in infinity transportation distance.

Recommendations

• Graph Laplacians and their convergence on random neighborhood graphs
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Spectral convergence of graph Laplacian and heat kernel reconstruction in L^ from random samples
• Spectral convergence of the connection Laplacian from random samples

Cites work

• A graph discretization of the Laplace-Beltrami operator
• A variational approach to the consistency of spectral clustering
• Consistency of spectral clustering
• Convergence of operator semigroups associated with generalised elliptic forms
• Diffusion maps
• Eigenvalues of Laplacians on a Closed Riemannian Manifold and Its Nets
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Finding the homology of submanifolds with high confidence from random samples
• From graph to manifold Laplacian: the convergence rate
• Gradient estimate of an eigenfunction on a compact Riemannian manifold without boundary
• Graph Laplacians and their convergence on random neighborhood graphs
• scientific article; zbMATH DE number 3877889 (Why is no real title available?)
• scientific article; zbMATH DE number 52737 (Why is no real title available?)
• scientific article; zbMATH DE number 3602274 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Minimax grid matching and empirical measures
• On learning with integral operators
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• Random Geometric Graphs
• Sectorial forms and degenerate differential operators
• Spectral convergence of the connection Laplacian from random samples
• The Generic Chaining
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Towards a theoretical foundation for Laplacian-based manifold methods
• Uniform Convergence of Adaptive Graph-Based Regularization

Cited in

(87)

• Spectral convergence of graph Laplacian and heat kernel reconstruction in L^ from random samples
• Manifold learning with arbitrary norms
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Properly-weighted graph Laplacian for semi-supervised learning
• Asymptotic spectra of large (grid) graphs with a uniform local structure. I: Theory
• The nonlocal-interaction equation near attracting manifolds
• Wave-shape oscillatory model for nonstationary periodic time series analysis
• Localized Fourier analysis for graph signal processing
• Error bounds of the invariant statistics in machine learning of ergodic Itô diffusions
• Kernel-based prediction of non-Markovian time series
• The SPDE approach to Matérn fields: graph representations
• Data-driven efficient solvers for Langevin dynamics on manifold in high dimensions
• Graph-theoretic algorithms for Kolmogorov operators: approximating solutions and their gradients in elliptic and parabolic problems on manifolds
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Measure estimation on manifolds: an optimal transport approach
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
• Boundary estimation from point clouds: algorithms, guarantees and applications
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Delay-coordinate maps, coherence, and approximate spectra of evolution operators
• Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit
• The Bayesian update: variational formulations and gradient flows
• On the diffusion geometry of graph Laplacians and applications
• Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations
• Spectral analysis of weighted Laplacians arising in data clustering
• Approximations of the connection Laplacian spectra
• Rates of convergence for Laplacian semi-supervised learning with low labeling rates
• Graph Laplacians and their convergence on random neighborhood graphs
• Explore Intrinsic Geometry of Sleep Dynamics and Predict Sleep Stage by Unsupervised Learning Techniques
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Erratum to ‘‘Sampling in Paley-Wiener spaces on combinatorial graphs”
• Spectral convergence of the connection Laplacian from random samples
• On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
• Convergence of Laplacian spectra from random samples
• scientific article; zbMATH DE number 7370580 (Why is no real title available?)
• Diffusion state distances: multitemporal analysis, fast algorithms, and applications to biological networks
• Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise
• Spectral Convergence of Diffusion Maps: Improved Error Bounds and an Alternative Normalization
• Kernel Analog Forecasting: Multiscale Test Problems
• A maximum principle argument for the uniform convergence of graph Laplacian regressors
• Lipschitz regularity of graph Laplacians on random data clouds
• scientific article; zbMATH DE number 7626762 (Why is no real title available?)
• scientific article; zbMATH DE number 7626797 (Why is no real title available?)
• Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
• A continuum limit for the PageRank algorithm
• Graph approximations to the Laplacian spectra
• Mumford-Shah functionals on graphs and their asymptotics
• Posterior consistency of semi-supervised regression on graphs
• Learning by unsupervised nonlinear diffusion
• Analysis of p-Laplacian regularization in semisupervised learning
• Measuring Segregation via Analysis on Graphs
• Understanding Graph Neural Networks with Generalized Geometric Scattering Transforms
• Analysis of a Computational Framework for Bayesian Inverse Problems: Ensemble Kalman Updates and MAP Estimators under Mesh Refinement
• Monotone meshfree methods for linear elliptic equations in non-divergence form via nonlocal relaxation
• Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling
• Entropic Optimal Transport on Random Graphs
• Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning
• Optimization on Manifolds via Graph Gaussian Processes
• Ghost Point Diffusion Maps for Solving Elliptic PDEs on Manifolds with Classical Boundary Conditions
• Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
• Nonlocal problems with local boundary conditions. I: Function spaces and variational principles
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Kernel two-sample tests for manifold data
• Eikonal depth: an optimal control approach to statistical depths
• Convergence of Laplacian eigenmaps and its rate for submanifolds with singularities
• Nonlocal problems with local boundary conditions. II: Green's identities and regularity of solutions
• Evolution equations on co-evolving graphs: long-time behaviour and the graph-continuity equation
• Convergence rates of the fractional to the local Dirichlet problem
• Distributional limits of graph cuts on discretized grids
• The graph -Laplacian eigenvalue problem
• Spectral convergence of symmetrized graph Laplacian on manifolds with boundary
• Linear separation capacity of self-supervised representation learning
• Nonparametric regression on random geometric graphs sampled from submanifolds
• Manifold learning in metric spaces
• Augmentation invariant manifold learning
• Sharp error estimates for target measure diffusion maps with applications to the committor problem
• Large data limit of the MBO scheme for data clustering: -convergence of the thresholding energies
• Scaling limit of the Kuramoto model on random geometric graphs
• Discrete-to-continuum rates of convergence for nonlocal p-Laplacian evolution problems
• Phase synchronization in random geometric graphs on the two-dimensional sphere
• Scalable Bayesian inference for heat kernel Gaussian processes on manifolds
• Surrogate models for diffusion on graphs via sparse polynomials
• Extracting manifold information from point clouds
• Spectral neural networks: approximation theory and optimization landscape
• Convergence of graph Dirichlet energies and graph Laplacians on intersecting manifolds of varying dimensions
• Improved convergence rate of \(k\mathrm{NN}\) graph Laplacians: differentiable self-tuned affinity
• Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel
• Geometry on probability spaces

This page was built for publication: Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2194775)