Lipschitz regularity of graph Laplacians on random data clouds
From MaRDI portal
Abstract: In this paper we study Lipschitz regularity of elliptic PDEs on geometric graphs, constructed from random data points. The data points are sampled from a distribution supported on a smooth manifold. The family of equations that we study arises in data analysis in the context of graph-based learning and contains, as important examples, the equations satisfied by graph Laplacian eigenvectors. In particular, we prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues. Our analysis relies on a probabilistic coupling argument of suitable random walks at the continuum level, and an interpolation method for extending functions on random point clouds to the continuum manifold. As a byproduct of our general regularity results, we obtain high probability and approximate convergence rates for the convergence of graph Laplacian eigenvectors towards eigenfunctions of the corresponding weighted Laplace-Beltrami operators. The convergence rates we obtain scale like the -convergence rates established by two of the authors in previous work.
Recommendations
- Learning Theory
- Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
- Convergence of Laplacian spectra from random samples
- Continuum limit of Lipschitz learning on graphs
- Graph Laplacians and their convergence on random neighborhood graphs
Cites work
- A graph discretization of the Laplace-Beltrami operator
- A maximum principle argument for the uniform convergence of graph Laplacian regressors
- A variational approach to the consistency of spectral clustering
- Adaptive piecewise polynomial estimation via trend filtering
- Analysis of p-Laplacian regularization in semisupervised learning
- Asymptotic Lipschitz regularity for tug-of-war games with varying probabilities
- Asymptotic analysis of the Ginzburg–Landau functional on point clouds
- Concentration inequalities. A nonasymptotic theory of independence
- Consistency of Cheeger and ratio graph cuts
- Consistency of Dirichlet partitions
- Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data
- Consistency of spectral clustering
- Continuum limit of total variation on point clouds
- Continuum limits of posteriors in graph Bayesian inverse problems
- Coupling of multidimensional diffusions by reflection
- Embeddings of Riemannian manifolds with heat kernels and eigenfunctions
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
- Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
- Estimating a smooth function on a large graph by Bayesian Laplacian regularisation
- Estimating perimeter using graph cuts
- From graph to manifold Laplacian: the convergence rate
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
- Global Lipschitz regularizing effects for linear and nonlinear parabolic equations
- Gradient Estimates on Rd
- Gradient estimates for diffusion semigroups with singular coefficients
- Gradient estimates of Dirichlet heat semigroups and application to isoperimetric inequalities.
- Gradient estimates on manifolds using coupling
- Graph Laplacians and their convergence on random neighborhood graphs
- Hölder and Lipschitz continuity of the solutions to parabolic equations of the non-divergence type
- Hölder continuity and bounds for fundamental solutions to nondivergence form parabolic equations
- Kernels and regularization on graphs.
- Large data and zero noise limits of graph-based semi-supervised learning algorithms
- Learning Theory
- Learning Theory
- Local regularity for time-dependent tug-of-war games with varying probabilities
- Manifold regularization: a geometric framework for learning from labeled and unlabeled examples
- Nonparametric sparsity and regularization
- On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
- Properly-weighted graph Laplacian for semi-supervised learning
- Regularity for nonlinear stochastic games
- Spectral Convergence of Diffusion Maps: Improved Error Bounds and an Alternative Normalization
- Spectral convergence of the connection Laplacian from random samples
- The game theoretic p-Laplacian and semi-supervised learning with few labels
- Trend filtering on graphs
- Tug-of-war games with varying probabilities and the normalized \(p(x)\)-Laplacian
- Uncertainty quantification in graph-based classification of high dimensional data
- Viscosity solutions of fully nonlinear second-order elliptic partial differential equations
Cited in
(14)- Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
- Diffusion Maps Kernel Ridge Regression
- Data-driven efficient solvers for Langevin dynamics on manifold in high dimensions
- Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
- Boundary estimation from point clouds: algorithms, guarantees and applications
- Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian
- Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
- Spectral convergence of symmetrized graph Laplacian on manifolds with boundary
- A mean curvature flow arising in adversarial training
- Manifold learning in metric spaces
- scientific article; zbMATH DE number 7626762 (Why is no real title available?)
- Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
- Meshless shape optimization using neural networks and partial differential equations on graphs
- Continuum limit of Lipschitz learning on graphs
This page was built for publication: Lipschitz regularity of graph Laplacians on random data clouds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037712)
