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

DOI10.1007/s10208-019-09436-wzbMath1447.62141arXiv1801.10108OpenAlexW2976645955WikidataQ127248308 ScholiaQ127248308MaRDI QIDQ2194775

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

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

spectral convergencerandom geometric graphspectral clusteringpoint cloudgraph Laplaciandiscrete to continuum limit

Mathematics Subject Classification ID

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

Related Items (53)

A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors ⋮ Lipschitz Regularity of Graph Laplacians on Random Data Clouds ⋮ Measuring Segregation via Analysis on Graphs ⋮ Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel ⋮ From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Measure estimation on manifolds: an optimal transport approach ⋮ Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation ⋮ A continuum limit for the PageRank algorithm ⋮ Unnamed Item ⋮ Graph approximations to the Laplacian spectra ⋮ Boundary estimation from point clouds: algorithms, guarantees and applications ⋮ Unnamed Item ⋮ Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation ⋮ 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 ⋮ Understanding Graph Neural Networks with Generalized Geometric Scattering Transforms ⋮ Rates of convergence for Laplacian semi-supervised learning with low labeling rates ⋮ Unnamed Item ⋮ 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 ⋮ Mumford–Shah functionals on graphs and their asymptotics ⋮ Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach ⋮ Delay-coordinate maps, coherence, and approximate spectra of evolution operators ⋮ Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit ⋮ Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples ⋮ Manifold learning with arbitrary norms ⋮ Gromov-Hausdorff limit of Wasserstein spaces on point clouds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Posterior consistency of semi-supervised regression on graphs ⋮ Properly-weighted graph Laplacian for semi-supervised learning ⋮ Asymptotic spectra of large (grid) graphs with a uniform local structure. I: Theory ⋮ The Bayesian update: variational formulations and gradient flows ⋮ Explore Intrinsic Geometry of Sleep Dynamics and Predict Sleep Stage by Unsupervised Learning Techniques ⋮ Analysis of $p$-Laplacian Regularization in Semisupervised Learning ⋮ 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 ⋮ 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 ⋮ 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

Cites Work

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

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