Measuring the Transport Radius: Testing ∞-Wasserstein Spectral Bounds on Real Point Clouds

Spectral methods build a neighborhood graph over data points, compute the eigenvectors of its graph Laplacian (a matrix encoding how each point differs from its neighbors), and use those eigenvectors for embedding or clustering. The best available theory for when this works rests on one geometric quantity: the ∞-Wasserstein distance $W_\infty$ between the sample and the true data distribution. This is the largest distance any single unit of probability mass must travel when the points are matched to the underlying manifold. A small $W_\infty$ means the sample covers the manifold evenly, with no holes and no crowded patches. Using this quantity, Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace-Beltrami Operator proves that graph Laplacian eigenvalues converge to those of the manifold's continuous Laplacian at a rate set only by the intrinsic dimension $m$, not the ambient dimension. The paper contains no experiments. Nobody knows whether the hidden constants, or the assumptions of a compact manifold with no boundary, leave the result predictive at the sample sizes people actually use.

We propose to treat $W_\infty$ as something to measure rather than only an object inside a proof. $W_\infty$ can be estimated from a single sample: split it in half and solve a bottleneck matching between the halves. That estimate then gives two practical things. The first is a rule for choosing the graph's connection radius. The second is a data-computable certificate that should track eigenvalue error. We then test both, together with the theorem's rate, on manifolds with known spectra and on real meshes, where a reference spectrum can be computed independently. The empirical-validation gap becomes the evaluation setting, and the transport bound becomes the mechanism being tested.

Core Claim

The proof in Error Estimates for Spectral Convergence… controls the relative eigenvalue error through a bound of roughly this form:

$$\frac{|\lambda_k(\Gamma)-\lambda_k(\mathcal M)|}{\lambda_k(\mathcal M)} \;\lesssim\; C_k\left(\frac{\varepsilon}{h}+h\right),$$

where $\varepsilon = W_\infty(\mu_n,\nu)$ is the transport radius between the empirical measure $\mu_n$ and the volume measure $\nu$, $h$ is the graph connection radius, and $C_k$ is a constant depending on the eigenvalue index $k$ and on curvature. Since $\varepsilon$ scales like $(\log n/n)^{1/m}$, choosing $h \propto \sqrt{\varepsilon}$ yields the published rate $(\log n/n)^{1/(2m)}$.

Our claim is that the same structure is usable in practice. We plug in a split-half estimate $\hat\varepsilon$ and set $h=c\sqrt{\hat\varepsilon}$, where $c$ is a constant calibrated once on synthetic manifolds and then frozen. We expect three consequences. The resulting graph should come close to the error-minimizing radius. The quantity $\sqrt{\hat\varepsilon}$ should rank-correlate with true eigenvalue error across datasets and sample sizes. And, most importantly, the correlation should hold because $W_\infty$ reflects density imbalance. Hausdorff coverage (the largest distance from any manifold point to its nearest sample, which ignores how mass is distributed) does not reflect that imbalance, so a Hausdorff-based certificate should do worse. If the transport ingredient adds nothing over simpler coverage measures, the experiments will show that. That would itself be a useful negative finding about what the theory buys.

Research Program

The first component is the estimator. For a sample split into halves $A$ and $B$, the two-sample $W_\infty$ is the smallest threshold $t$ such that a perfect matching exists between $A$ and $B$ using only pairs within distance $t$. We compute it by binary search over $t$, running Hopcroft–Karp bipartite matching on a sparse candidate graph of $k$-nearest-neighbor pairs, with $k$ enlarged until the search stabilizes. This scales to roughly $10^5$ points without the dense $O(n^2)$ memory that stops Sinkhorn solvers near 16,000 points, as reported in Hierarchical Refinement: Optimal Transport to Infinity and Beyond.

By the triangle inequality, the split-half value is at most twice the one-sample quantity $W_\infty(\mu_{n/2},\nu)$. It is not automatically a lower bound, so whether it tracks the population quantity up to a stable constant is itself tested. We check this on manifolds where $\nu$ can be sampled exactly, and we correct for the halved sample size using an intrinsic-dimension estimate.

The second component is the validation study that the theory paper never ran. On manifolds with analytically known spectra, we measure eigenvalue and eigenvector error against $n$ and $m$. We fit empirical slopes and compare them with $1/(2m)$. We also estimate the constant $C_k$ directly to see how it grows with $k$ and with ambient dimension. The manifolds are flat tori of intrinsic dimension 1 to 6 embedded isometrically and then randomly rotated into ambient dimensions up to 100, and round spheres, each under both uniform and non-uniform sampling.

The third component moves toward real geometry. ModelNet40 shapes are triangle meshes, so a high-resolution finite-element discretization of each mesh gives a reference Laplace–Beltrami spectrum. Points sampled from the mesh surface can then be scored against a ground truth that does not come from our own estimator. Many of these meshes have boundaries, creases, or non-manifold pieces. They therefore directly probe the boundary-free assumption, whose failure is priced in Spectral Convergence of Symmetrized Graph Laplacian on manifolds with boundary. That paper shows boundaries degrade the rate to $(\log n/n)^{1/(2d+6)}$, and its truncated-Laplacian correction needs the boundary known in advance. We check whether the $W_\infty$ certificate at least flags boundary-dominated shapes, where near-boundary mass cannot be matched cheaply. ModelNet40-E from ModelNet40-E: An Uncertainty-Aware Benchmark for Point Cloud Classification adds physically modeled LiDAR noise and outliers at three severities. Because $W_\infty$ is a worst-case quantity, it should be fragile to outliers; this tests exactly the tension with outlier-tolerant transport such as Elastic Optimal Transport. We will also test a trimmed variant that matches all but a fraction $\alpha$ of the mass.

Baselines

The naive reference point is the standard practice from Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering: a fixed-radius or fixed-$k$ graph with a heat kernel and a hand-set bandwidth. We run it at a common default, the median nearest-neighbor distance times a constant, with no tuning. Any method that cannot beat this has no reason to exist.

The strongest existing competitor for choosing the graph is the self-tuned $k$-nearest-neighbor kernel of Convergence of Graph Laplacian with kNN Self-tuned Kernels. It adapts the bandwidth to local density and was shown on MNIST to keep informative embeddings where fixed-bandwidth diffusion maps collapse. It is strong because it already handles the non-uniform density that $W_\infty$ is meant to capture. We give it the same tuning budget as our rule: its $k$ is calibrated on the same synthetic manifolds, then frozen and applied to the same samples. We found no reported eigenvalue-error numbers on Lacuna for this method, for the fixed-bandwidth baseline, or for any graph Laplacian on ModelNet40 meshes, so all baseline numbers will be produced in our own runs. The closest reported evidence is qualitative: truncated Laplacians recovered the first 20+ Dirichlet modes on a semi-torus (Spectral Convergence of Symmetrized Graph Laplacian on manifolds with boundary).

As an oracle upper reference, we pick the radius that minimizes true eigenvalue error by grid search on the ground-truth spectrum. Beating the baselines means that our rule's error falls within a small factor of this oracle, and below the self-tuned kernel's error, on a majority of held-out manifolds and meshes. A win on synthetic data alone does not count.

The ablation that isolates the key ingredient replaces $\hat\varepsilon$ with the empirical Hausdorff coverage radius, estimated as the maximum nearest-neighbor distance between the two halves. It also replaces $\hat\varepsilon$ with the smallest radius at which the graph becomes connected. Both use the same $h = c\sqrt{\cdot}$ rule and the same calibration. If they perform as well as $\hat\varepsilon$, the transport part of the theory is not doing practical work.

Why not just…?

Why not just set the radius to the smallest value that connects the graph? This is the real threat. On uniformly sampled manifolds, the connectivity threshold and the coverage radius move with $W_\infty$ at the same rate up to log factors. The theory distinguishes them only when density is uneven, because matching mass requires more than covering space. We therefore make non-uniform sampling and the ModelNet40 meshes, whose surface sampling is uneven, the deciding cases. If connectivity matches $W_\infty$ there as well, we will report that the simpler rule suffices.

Why not just cross-validate the bandwidth or use eigengap heuristics? Unsupervised spectral methods have no held-out loss that directly measures eigenvalue error. The fixed-bandwidth "Goldilocks" failure documented in Convergence of Graph Laplacian with kNN Self-tuned Kernels shows that such tuning can land in disconnected or over-smoothed regimes. We include an eigengap-selected radius as an additional run on the same data, so this question is answered empirically rather than argued.

Why not just fit convergence slopes on toy manifolds and stop? That is the obvious study, and it is part of what we do. On its own, though, it repeats the synthetic-only pattern of Statistical bounds for entropic optimal transport and the semicircle and semi-torus checks of Peoples and Harlim. It gives practitioners no tool, and it never confronts boundaries or noise on real geometry. The mesh-based ground truth is what makes our study different.

Why not just bootstrap the eigenvalues to get uncertainty? Resampling with replacement duplicates points, and duplicated points create zero-distance edges that distort the graph. The distortion is analogous to the bootstrap failure proven for max-sliced transport in Statistical inference with regularized optimal transport. Bootstrap spread also measures variance, not the bias that dominates at small radius. We will nonetheless run subsampling-based eigenvalue spread as a competing certificate and compare rank correlations with true error.

Proposed Experiments

On tori and spheres, we sweep $n$ from $10^3$ to $10^5$, intrinsic dimension from 1 to 6, and ambient dimension up to 100. We report fitted error slopes against $1/(2m)$, estimated constants $C_k$ for $k$ up to 50, and the ratio of split-half $\hat\varepsilon$ to the exactly computable population $W_\infty$.

On the 40 ModelNet40 classes, we report eigenvalue error relative to the finite-element reference for each radius rule. We also report the Spearman correlation between each certificate and the true error across shapes and sample sizes, including the connectivity, Hausdorff, subsampling, and $W_\infty$ certificates. Both are repeated under the three ModelNet40-E noise levels, with and without trimming.

On MNIST digit subsets, where no ground-truth spectrum exists, the downstream check is spectral clustering accuracy and the agreement between embeddings computed from disjoint halves, compared across radius rules.

Three results would be decisive. The first is whether empirical slopes approach $1/(2m)$ before $n = 10^5$ in dimensions above 3. If they do not, the theorem's rate is not the operative regime, and we will say so. The second is whether $W_\infty$ beats Hausdorff and connectivity certificates specifically under non-uniform density. This is the test of whether the transport formulation carries practical information. The third is whether the certificate still ranks shapes correctly on meshes with boundaries and LiDAR noise, which the theory does not cover.