cs.CVSep 26, 2026

Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling

Authors: Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha

Organizations: Columbia University · Google DeepMind

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Gromov-Wasserstein Distances (GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present Efficient Geodesic Gromov-Wasserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced GenusSink methods \citep{genussink} and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.

Figures & tables

MethodIntra-space distancesCross-space stateStatus
Dense GWD (brute-force)Dense CX,CY\mathbf{C}_{X},\mathbf{C}_{Y}Dense T,DT,KT\mathbf{T},\mathbf{D}_{\mathbf{T}},\mathbf{K}_{\mathbf{T}}Exact
DET-EGGroWOperator formDense T,DT,KT\mathbf{T},\mathbf{D}_{\mathbf{T}},\mathbf{K}_{\mathbf{T}}Exact if operators exact
APP-EGGroWOperator formO((n+m)r)O((n+m)r) factorsApproximate
Table 1: The three implementations of the Gromov-Wasserstein Distance calculation remove different dense objects. Here rr is the number of random features for APP-EGGroW. Operator storage depends on the selected separator or analytic moment backend.
Figure 1: FAUST pose correspondence for (a) source scan 004004 and (b) target scan 003003 . Colors are intrinsic source colors transferred to the target by each method (c)-(h).
PairNNOTGWDFGWDDETAPP 64APP 256APP 1024
Geodesic correspondence error ↓\downarrow
004→003004\to 0030.5740.6360.3320.1660.1660.2400.2320.230
004→006004\to 0060.5180.6410.3230.1080.1080.2520.2060.206
004→007004\to 0070.6650.6330.3540.2230.2230.2810.2610.237
Runtime (seconds) ↓\downarrow
004→003004\to 003--896.4896.41077.2587.0320.8357.1535.1
Table 2: Mean target-geodesic correspondence error on three FAUST same-subject pose pairs at n=2000n=2000 vertices. Euclidean OT and FGWD use squared Euclidean cross-feature costs.
Figure 2: Error (top) and runtime (bottom) across different methods as nn increases.
Figure 3: Octopus template localization where colors show the recovered scene density pi/aip_{i}/a_{i} ; gray points provide scene context.
Figure 4: Mean accuracy and runtime (bottom right) at increasing mesh sizes for each of the different methods under comparison.
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Random-featuren=1,000n=1{,}000n=2,000n=2{,}000
constructionGeodesic error ↓\downarrowPCK@5% ↑\uparrowGeodesic error ↓\downarrowPCK@5% ↑\uparrow
IID PRF0.310±0.0820.310\pm 0.08222.50±3.1622.50\pm 3.160.465±0.0290.465\pm 0.02918.88±3.8218.88\pm 3.82
OPRF-IID0.325±0.0920.325\pm 0.09221.84±2.5721.84\pm 2.570.457±0.0360.457\pm 0.03619.09±4.1319.09\pm 4.13
Orthogonal PRF0.421±0.0440.421\pm 0.04420.79±2.7120.79\pm 2.710.430±0.1130.430\pm 0.11317.95±1.7817.95\pm 1.78
Simplex PRF0.422±0.0440.422\pm 0.04420.80±2.7020.80\pm 2.700.430±0.1130.430\pm 0.11317.97±1.7717.97\pm 1.77
OPRF-Orthogonal0.424±0.0480.424\pm 0.04820.53±2.7520.53\pm 2.750.433±0.1160.433\pm 0.11617.78±1.8717.78\pm 1.87
Appendix
Table 3: Random-feature ablation on FAUST. RF entries are mean ±\pm sample standard deviation over five/three seeds at n=1,000/2,000n=1{,}000/2{,}000 , after averaging the two frozen updates. Geodesic error is the mean raw target distance; PCK@5% is the percentage within 5% of the sampled target geodesic diameter. The dense reference averages the same states. OPRF denotes optimized positive random features.
Figure 5: FAUST pose correspondence for (a) source scan 004004 and (b) target scans 006006 (top) and 007007 (bottom). Colors are intrinsic source colors transferred to the target by each method (c)-(h).
More in this topic

Optimal Transport

Optimal transport compares and transforms probability distributions by finding low-cost ways to move mass between them.

See all 287 papers

Explore similar work

CardsList
May 14, 2026

Distance-Matrix Wasserstein Statistics for Scalable Gromov--Wasserstein Learning

Gromov--Wasserstein (GW) distances compare graphs, shapes, and point clouds through internal distances, without requiring a common coordinate system. This invariance is powerful, but discrete GW is a nonconvex quadratic optimal transport problem and is difficult to estimate at scale. We propose Distance-Matrix Wasserstein (DMW), a hierarchy of Wasserstein statistics comparing laws of random finite distance matrices. Rather than optimizing a global point-level alignment, DMW samples nn points from each space, records their pairwise distances, and transports the resulting matrix laws. We prove that DMW is a relaxation and lower bound of GW, and establish a reverse approximation inequality: the GW--DMW gap is controlled by the Wasserstein error of approximating each original measure with nn samples. Hence population DMW converges to GW as sampled subspaces become dense. We further give finite-sample bounds, including intrinsic-dimensional rates that depend on the data manifold rather than the ambient matrix dimension (n2)\binom n2. For scalable computation, we introduce sliced and multi-scale DMW; for p=1p=1, the sliced multi-scale dissimilarity yields positive-definite exponential kernels. Experiments on synthetic metric spaces, scalability benchmarks, graph classification, and two-sample testing validate the theory and demonstrate an interpretable GW-style proxy for structural comparison.

Ao Xu, Tieru Wu

School of Artificial Intelligence Jilin University No. 2699, Qianjin Street, Chaoyang District Changchun 130012, China · Zhongguancun Academy Daniufang 2nd Ring Road, Haidian District2026 Beijing 100094, China · School of Artificial IntelligenceMay Jilin University No. 2699, Qianjin Street, Chaoyang District14 Changchun 130012, China

Optimal TransportWasserstein Distance
AskPDF
May 13, 2026

Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein

We propose min Generalized Sliced Gromov--Wasserstein (min-GSGW), a sliced formulation for the Gromov--Wasserstein (GW) problem using expressive generalized slicers. The key idea is to learn coupled nonlinear slicers that assign compatible push-forward values to both input measures, so that monotone coupling in the projected domain lifts to a transport plan evaluated against the GW objective in the original spaces. The resulting plan induces a GW objective value, and min-GSGW minimizes this cost directly in the original spaces. We further show that min-GSGW is rigid-motion invariant, a crucial property for geometric matching and shape analysis tasks. Our contributions are threefold: 1) we introduce generalized slicers into the sliced GW framework, 2) we construct a slicing-based efficient GW transport plan; and 3) we develop an amortized variant that replaces per-instance optimization with a learned slicer for unseen input pairs. We perform experiments on animal mesh matching, horse mesh interpolation, and ShapeNet part transfer. Results show that min-GSGW produces meaningful geometric correspondences and GW objective values at substantially lower computational cost than existing GW solvers.

Ashkan Shahbazi, Xinran Liu, Ping He +1

Department of Computer Science, College of Connected Computing, Vanderbilt University · Department of Electrical and Computer Engineering, Vanderbilt University

Non-Rigid Shape CorrespondenceOptimal TransportWasserstein Distance
AskPDF
Sep 25, 2026

Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems

The Gromov-Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport (EOT) problem is solved at each iteration. Despite its widespread use, the convergence of MD for this problem has only been established for restricted classes of costs. On the other hand, a recently proposed dual gradient method is available for general costs, but requires a choice of step size which depends on the regularization parameter. To address these two issues, we introduce Averaged Mirror Descent (AMD), which averages consecutive MD steps, and prove its convergence for arbitrary costs. Then, we establish that the dual gradient method with a fixed step size also converges for arbitrary costs at the cost of a more complicated iteration. In both cases, we also account for inexact iterations which are inescapable in practice. We compare the empirical performance of these methods across various settings and, in particular, show that AMD and the dual gradient method both converge on an example where classical MD fails.

Joanna Marks, Gabriel Rioux, Riccardo Passeggeri

⋆Denotes equal contribution to this work.

Gradient DescentMirror DescentOptimal TransportWasserstein Distance
AskPDF