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

Nicolas Garcia Trillos; Moritz Gerlach; Matthias Hein; Dejan Slepcev

Source-linked AI summary

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

Nicolas Garcia Trillos, Moritz Gerlach, Matthias Hein, Dejan Slepcev

arXiv:1801.10108v1Jan 30, 2018stat.MLmath.APmath.DGmath.PR

TL;DR

The paper asks when and how quickly graph-Laplacian spectra from i.i.d. samples on submanifolds converge to those of weighted Laplace–Beltrami operators. It develops a framework combining manifold graph approximations with empirical-measure transportation estimates, obtaining spectral convergence without requiring manifold knowledge in graph construction or eigenvector extension.

Problem
The paper asks under what conditions and at what rate graph-Laplacian spectra from i.i.d. submanifold samples converge to the spectrum of the weighted Laplace–Beltrami operator.
Method
The framework combines deterministic graph approximations with a generalization of infinity-optimal transportation convergence for empirical measures on submanifolds.
Results
The framework establishes spectral convergence for a large family of graph Laplacians, including unnormalized, normalized, and random-walk variants.
Takeaways & Limitations
The graph and out-of-sample eigenvector extensions use only ambient Euclidean distances, while the results help explain geometric information extraction when intrinsic dimension is small.
Takeaways & Limitations
The analysis assumes compactly supported kernels, while extending it to noncompact kernels such as Gaussian would require additional error bounds and more involved estimates.

Abstract

from arXiv · show

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 $O\Big(\big(\frac{\log n}{n}\big)^\frac{1}{2m}\Big)$ 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.

0.1 Notation

The notation defines the manifold, sampling distribution, point cloud, graph weights, geometric scales, and operators used to analyze graph-Laplacian convergence.

M is a compact manifold embedded in R^d, with dimension m and geometry described using geodesic distance and intrinsic balls.
The data distribution μ is supported on M with density p, while ρ defines the weight measure used for normalized graph Laplacians.
X is an i.i.d.-sampled point cloud and also the vertex set of the associated graph; μ_n is its empirical measure.
The differential δ maps a function on vertices to edge differences, while i0, K, and R quantify manifold geometry.
Edge weights depend on a nonnegative kernel η evaluated through vertex distances, with h controlling the neighborhood length scale.
The analysis uses the infinity transportation distance d∞, discretization and interpolation operators, and ε as an upper bound on transportation error.

1 Introduction

The paper asks when graph-Laplacian spectra from random samples on an unknown submanifold converge to the weighted Laplace–Beltrami spectrum, and develops a framework with improved rates.

The central question is the condition and rate for spectral convergence as n increases and h tends to zero.
Earlier work established several pointwise or restricted spectral-convergence results, but no error estimates had been established in the relevant setting.
The proposed framework analyzes rates for a large family of graph Laplacians and improves the prior convergence rate.
The graph and out-of-sample eigenvector extension use only ambient Euclidean distances, requiring no information about the unknown manifold.
The work also generalizes infinity-optimal-transport convergence rates for empirical measures on submanifolds, which supply probabilistic estimates for spectral convergence.

1.1 Graph construction

The graph is built from sampled points on a compact Riemannian submanifold using ambient Euclidean neighborhoods and kernel-based edge weights, without requiring manifold information.

The setting assumes a compact connected m-dimensional manifold without boundary, embedded in R^d, with bounded curvature, positive injectivity radius, and reach.
The sampling measure has a non-vanishing Lipschitz density p with respect to Riemannian volume.
Vertices are connected when their ambient Euclidean distance is at most h, and more general edge weights depend on the distance between vertices.
A decreasing kernel η assigns weights to edges, with examples including an indicator kernel, smooth kernels, and a truncated Gaussian.
The construction uses ambient Euclidean distance rather than geodesic distance because the manifold is assumed unknown.
Compact support of η is a technical requirement; extending the analysis to noncompact kernels would require additional error bounds.

1.2 Dirichlet forms and laplacians

The section places discrete and continuous Laplacians in a shared Dirichlet-form framework, then instantiates it for unnormalized, random-walk, and symmetric normalized graphs. It connects spectral approximation to measure approximation and kernel-density estimates, while noting a structural limitation for the symmetric normalized operator.

1.2 Dirichlet forms and laplacians: The discrete framework defines graph measures, scalar products, differentials, and a Dirichlet form for functions on sampled vertices.Edge weights induce the measure and scalar product, while the discrete differential yields the graph Dirichlet form.
1.2 Dirichlet forms and laplacians: The continuous framework uses the Sobolev space V = H1(M, µ) and a Dirichlet form based on manifold gradients and the Riemannian metric.The form is continuous because the density p is bounded above.
1.2 Dirichlet forms and laplacians: Different choices of measures on the sample and manifold produce corresponding realizations of graph and continuous Laplacian operators.The framework includes the unnormalized and random-walk graph Laplacians and their continuous counterparts.
1.2 Dirichlet forms and laplacians: The main spectral principle is that the spectrum of the graph operator ∆Γ approximates that of the continuous operator ∆ as the empirical measure approaches ρµ.The section uses a transportation-based quantity to quantify this measure approximation.
1.2.1 Unnormalized graph Laplacian: The unnormalized Laplacian sets the density vector m to all ones, yielding ρ ≡ 1 and a continuous realization identified with the pointwise limit when p ∈ C1(M).This construction is presented as one instance of the general framework.
1.2.2 Random Walk Graph Laplacian: The random-walk Laplacian uses vertex degrees as the density vector, sets ρ(x) = p(x), and relates closeness of m and ρ to kernel-density estimation on M.Its analysis uses an ∞-OT estimate; although the estimate is not optimal, the stated spectral convergence rates are unaffected.
1.2.3 Normalized graph Laplacian: The symmetric normalized Laplacian is another commonly used version, but it cannot be represented by merely choosing the measure mµ in this framework.Its spectrum can nevertheless be analyzed indirectly because it shares the same spectrum as the random-walk Laplacian.

1.3 Main results

The paper establishes quantitative spectral convergence of graph Laplacians and develops transportation-based estimates for random samples, including eigenfunction extensions that require no manifold information.

Eigenvalues: Theorem 2 provides high-probability ∞-transportation estimates for i.i.d. samples from a smooth, connected, compact m-dimensional manifold.The stated probability is at least 1 − C n^-β, with constants depending on geometric and sampling parameters.
Eigenvalues: Theorem 4 bounds graph-Laplacian eigenvalue errors using neighborhood size h, sampling distance ε, density mismatch, and manifold geometry.Here ε is the ∞-optimal transportation distance between the empirical and manifold measures.
Eigenvalues: Curvature contributes only a second-order correction to the convergence rate of graph eigenvalues toward manifold eigenvalues.The lower bound does not depend on the reach R, whereas the upper bound includes a higher-order reach-dependent correction.
Eigenvalues: The informative spectral range is limited: relative eigenvalue error is small when k ≲ 1/h^m and ε ≪ h, with m = 2 giving k ≲ log(n)^3/2 under the stated scaling.These estimates identify a lower bound on the mode beyond which the graph spectrum ceases to be informative about the manifold spectrum.
Eigenfunctions: Eigenvectors converge toward manifold eigenfunctions, and Voronoi extensions constructed solely from sample data achieve almost the same rate as the eigenfunction estimate.The Voronoi construction partitions the manifold into nearest-neighbor cells and needs no information about M.
Eigenfunctions: The Voronoi-extension estimate is worse than Theorem 5 by a logarithmic factor because of uniform Voronoi-cell bounds based on transportation.The estimate also uses eigenfunction regularity, including a bound on ∥∇f∥∞, to compare transport-cell and Voronoi-cell averages.

1.4 Outline of the approach and discussion

The paper compares discrete and continuum spectral variational problems through transportation, energy, and near-isometric maps. This framework also supports graph and out-of-sample eigenvector constructions using only ambient Euclidean distances.

Variational comparison: The proofs use variational characterizations of both graph and continuum spectra, then compare their objective functionals.The discrete and continuum eigenvalues are characterized through min–max principles.
Transportation estimates: The probabilistic component establishes transportation estimates between the sampling measure and its empirical measure on the manifold.The approach extends earlier transportation results from Euclidean domains and general densities to the manifold setting.
Geometric and energy estimates: A geometric partition into manifold patches enables Euclidean transportation arguments and yields the probabilistic estimates needed for the spectral results.The partition is combined with deterministic comparisons between discrete and continuum Dirichlet energies.
Geometric and energy estimates: The energy comparison separates graph-to-average behavior as a variance estimate from non-local-to-continuum behavior as a bias estimate.The non-local length scale r is, to leading order, equal to h, and the error depends explicitly on h, transportation error, and manifold geometry.
Spectral transfer: Sharp constants and almost-isometric discretization, adjoint, and interpolation maps complete the spectral convergence analysis.The sharp constant is obtained from the specific convolution operator used in the interpolation map.
Spectral transfer: The graph and out-of-sample eigenvector extensions require only ambient-space Euclidean distances, without information about the unknown manifold.The eigenvector convergence results also use Voronoi-cell measure bounds and uniform eigenfunction gradient estimates.

1.5 Outline

The paper first develops geometric and transportation estimates, then relates discrete and continuum Dirichlet energies before proving eigenvalue and eigenvector convergence.

Outline: Section 2 estimates the ∞-transportation distance between the empirical and sampling measures, including the proof of Theorem 2.The preceding differential-geometric estimates support this analysis.
Outline: Later sections analyze kernel-based Laplacian approximation, eigenvalue convergence, and eigenvector convergence through interpolation and Voronoi extensions.The eigenvalue analysis appears in Section 4, while Section 5 treats interpolation-map and Voronoi extensions.

1.6 Some estimates from differential geometry

The geometric preliminaries control local manifold geometry through exponential maps, intrinsic distances, volume distortion, and the reach-dependent relation to ambient Euclidean distance.

Local coordinates: The exponential map identifies sufficiently small tangent-space balls with geodesic balls on the manifold.For radii below the injectivity radius, it is a diffeomorphism between these balls.
Local coordinates: The exponential map is bi-Lipschitz with constant 2 on the stated local scale, controlling distortion between tangent-space and manifold distances.The metric coefficients and derivatives of the exponential map provide the underlying distortion bounds.
Intrinsic distance: A minimizing geodesic that leaves a geodesic ball must spend enough length outside the ball, supporting local distance comparisons.The argument bounds the lengths of curve restrictions before and after the exit point.
Intrinsic distance: The resulting local comparison bounds intrinsic distance by a constant multiple of tangent-space distance.The proof concludes with the bound d(q1,q2) ≤ 2d(exp_p^-1(q1), exp_p^-1(q2)).
Volume and embedding geometry: The Jacobian of the exponential map controls local volume elements, yielding estimates involving the unit-ball volume ωm.These estimates follow directly from the metric-distortion bounds.
Volume and embedding geometry: The manifold reach is an extrinsic quantity that controls principal curvatures and bounds the local discrepancy between intrinsic and ambient Euclidean distances.The distance discrepancy is treated as a second-order perturbation with explicit reach-dependent error bounds.

2 The ∞-transportation distance

The transportation analysis constructs a well-behaved manifold partition and transfers Euclidean estimates to it, obtaining high-probability control of local empirical transport errors.

Manifold partition: A maximal r-separated set generates a Voronoi partition whose cells lie inside geodesic balls and cover the manifold.The construction also uses disjoint smaller balls and controlled overlaps between neighboring larger balls.
Manifold partition: The overlap graph of the covering balls is connected because the manifold is connected.Disconnected overlap components would induce a separation of the manifold, contradicting connectedness.
Local transport estimates: Intermediate densities are constructed iteratively so that transport between the original densities can be bounded through local comparisons.The proof transports only the residual mass after common mass is left in place.
Probability guarantee: The stated estimates include a scaling caveat: constants depending on m, α, and r can be reduced to dependence on m and αr by rescaling to the unit ball.An analogous rescaling observation is stated for the Euclidean theorem used in the proof.
Local transport estimates: Each Voronoi cell admits a bi-Lipschitz parametrization by a Euclidean domain, allowing Euclidean transportation results to be applied locally.The stated parametrization has bi-Lipschitz constant at most 18.
Probability guarantee: The resulting local estimates hold simultaneously for all cells with probability at least 1 − C N_c n^-β.The constant depends on β, r, α, and m.

3 Kernel-based approximation of the Laplacian

The section develops a kernel-based approximation of the continuous Dirichlet form and establishes estimates showing how the resulting functional approximates the Laplacian. The analysis adapts prior arguments to variable densities and general kernels.

The kernel-based functional is the bias component of the error analysis and does not depend on the sampled graph.It approximates the continuous Dirichlet form before graph sampling effects are introduced.
The approximation bounds depend on geometric distortion and density variation, producing an additional factor (1 + αL_pr) relative to constant p.This correction appears in the estimate for E_r(f).
A smoothing operator Λ_r is introduced to map L2(M, ρµ) into Lip(M) while preserving constant functions.The normalization term θ is included specifically so that Λ_r preserves constants.

4 Convergence of eigenvalues

The section compares the discrete graph Dirichlet form with the continuum form using interpolation, discretization, and smoothing operators. Min–max arguments then yield upper and lower bounds for corresponding graph and manifold eigenvalues.

The discrete and continuum Dirichlet forms are compared through the maps P, P* and Λ_r, which interpolate and discretize between the graph and manifold.The construction is designed to be almost isometric.
The operators P and P* are only almost adjoint and P* is only almost an isometry for general weights and densities.They become exactly adjoint and isometric when mµ_n = µ_n and ρµ = µ.
The eigenvalue comparison is established in two directions: first an upper bound for λ_k(Γ) in terms of λ_k(M), then a lower bound.Both directions use the min–max principle and finite-dimensional eigenspaces.
The comparison estimates are controlled by the infinity transportation distance ε together with kernel, density, and geometric parameters.This formulation isolates randomness in ε and permits probabilistic transportation estimates to transfer to eigenvalue errors.

5 Approximation of eigenfunctions

The section establishes approximation of graph eigenvectors by continuum eigenfunctions through nearly inverse discretization and interpolation operators. It also shows that extensions approximating P*u approximate the corresponding manifold eigenfunction.

The discretization and interpolation operators P and I are shown to be almost inverse of one another.This provides the basic bridge for transferring eigenvectors between the graph and manifold settings.
Spectral projections onto eigenvalues below λ control both continuum and graph Dirichlet energies without increasing them.The associated estimates apply on the low-frequency eigenspaces H_λ(M) and H_λ(X).
An extension of a graph eigenvector approximates the corresponding manifold eigenfunction whenever it approximates P*u in L2(M, ρµ).Approximation in L2(M, µ) is equivalent in this statement.
The out-of-sample extension is analyzed using Euclidean Voronoi cells and their geometric size bounds.The cells are localized near sample points, enabling control of the extension error.
The eigenfunction proof combines graph-to-manifold operator estimates with probabilistic bounds on Voronoi-cell measures.The resulting estimate is obtained for normalized corresponding graph eigenvectors and manifold eigenfunctions.

A Kernel density estimates via transportation

The section derives kernel-density estimates from infinity transportation bounds between the empirical measure and the target measure. These estimates are sufficient for the spectral convergence analysis, although they are not optimal.

The transportation-map approach provides a simple, general route to the required kernel-density estimates.The authors contrast it with usual kernel-density-estimation approaches.
Infinity transportation distance ε is used to control kernel-density estimation errors for the sampled weights m_i.The density p is the density of µ with respect to the manifold volume form.