Beyond Procrustes distances: a multilinear Gromov-Wasserstein distance capturing chirality

Clément Soubrier; Geoffrey Woollard; Andrew Warren; Khanh Dao Duc

math.OCAug 27, 2026

Beyond Procrustes distances: a multilinear Gromov-Wasserstein distance capturing chirality

Authors: Clément Soubrier, Geoffrey Woollard, Andrew Warren, Khanh Dao Duc

Organizations: Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada · Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada · Mathematical Institute, Utrecht University, Utrecht, 3584 CD, The Netherlands

Abstract

Efficiently and robustly analyzing shape data is critical across many scientific disciplines. While chirality is a fundamental property in numerous applications - most notably in molecular science - existing shape analysis metrics fail to distinguish between a shape and its mirror image. To address this gap, we introduce a multilinear generalization of the Gromov-Wasserstein objective. Under mild assumptions, this objective yields a distance between shapes, represented as probability distributions quotiented by a symmetry group $G$ . In particular, for $G = SO(d)$ , we introduce the Chiral Gromov-Wasserstein ( $\mathrm{CGW}$ ) distance, sensitive to chirality. We establish robustness properties for the multilinear Gromov-Wasserstein distances and develop efficient algorithms to compute them, reformulating the underlying optimization problem by projecting couplings onto a low-dimensional space. We derive algorithms for both local and approximate global solutions, yielding a fully polynomial-time approximation scheme for these problems. We validate the framework through numerical experiments that demonstrate the effectiveness of $\mathrm{CGW}$ as a shape metric for chiral objects.

Figures & tables

Figure 1 : The low-dimensional structure of the GW m problem and how it is approximately solved using a sandwich algorithm. A) Low-dimensional structure of the

\mathrm{GW}_{m}

problem described in Corollary 2 . Given a coupling

\pi\in\Pi(\mu,\nu)

, the optimization problem for computing

\mathrm{GW}_{m}(\mu,\nu)

only depends on the projection of

\pi

on a

d^{2}

dimensional space. We reformulate the computation of

\mathrm{GW}_{m}(\mu,\nu)

, as the global optimization over a compact convex set

P_{\Pi}

, of a multi-variable polynomial function

Q_{m}

. B) Representation of Kamenev’s sandwich algorithm [ 21 , 26 ] to geometrically approximate

P_{\Pi}

, as described in Section 3.1 . The algorithm recursively updates two bounding boxes

P_{\Pi}^{+}

and

P_{\Pi}^{-}

, which are converging to

P_{\Pi}

. At each iteration, the direction (black arrow) maximizing the gap between the two boxes (black dashed line) is selected. Then a new supporting hyperplane (blue dotted line) and vertex (red star) are computed to update the boxes.

Figure 2 : Chiral shape comparison using the CGW distance. A) Transport of a reference right hand to a left hand, using the Classical, Inner and Chiral Gromov-Wasserstein optimal transport maps. Only the CGW distance yields a positive value between the two hands, capturing the change of handedness. B) Comparison of penicillamine conformations using the $\mathrm{CGW}$ distance. We compared either two penicillamine enantiomers after adding noise (with reflection), or two noisy versions of the same molecule (without reflection). Without reflection, the $\mathrm{CGW}$ distance and Root-Mean-Square Deviation (RMSD) are linearly correlated. On the right side, the boxplot represents $\mathrm{CGW}$ distance between conformations of the same handedness (without reflection) and different handedness (with reflection).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Cost	Convexity	dimension	t
$\mathrm{IGW}$	Concave	all
$\mathrm{DGW}$	Non-convex, non-concave	all
$\mathrm{CGW}$	Concave	1	$0<t<1$
	Concave	2	$\frac{1}{2}\leq t<1$
	Non-convex, non-concave	2	$0<t<\frac{1}{2}$
	Concave	3	$\frac{24R^{2}}{2+24R^{2}}\leq t<1$

Appendix

Table 1 : Convexity of the different costs, for marginals contained in a centered ball of radius

R

Figure 3 : Lower and upper bound convergence for the global optimization concave algorithm, when computing the

\mathrm{CGW}

cost in Figure 2 A. More precisely,

c^{-}

and

c^{+}

bound the optimal value of

Q_{m}

P_{\Pi}

. The lower bound

c^{-}

converges faster than the upper bound

c^{+}

, which is a recurrent behavior in our simulations.

Figure 4 : Convergence of the global optimization concave algorithm for the IGW cost. A) Convergence in dimension 2 with 5000 points in each marginal. An upper bound on the number of vertices in

P_{\Pi}^{+}

and the number of constraints in

P_{\Pi}^{-}

O(k^{2})

, with

k

the number of iterations. In practice, those numbers have a lower complexity, with a linear behavior in this case.

|c^{+}-c^{-}|

is an upper bound of the precision at which the global solution is approximated (see algorithm 2 ). In dimension 2, an ordinary laptop can run several thousand iterations of the algorithm without suffering memory issues. B) Convergence in dimension 3, with 10 points in each marginal. An upper bound on the number of vertices in

P_{\Pi}^{+}

and the number of constraints in

P_{\Pi}^{-}

O(k^{4})

, with

k

the number of iterations. The blue dashed line represents the function

y=\alpha x^{3}

with

\alpha=1.3

, suggesting that the number of vertices and constraints has size

O(k^{3})

in practice.

Figure 5 : Convergence of the Frank-Wolfe scheme (Algorithm 3 ) in dimension

d=3

, with 1000 points in the marginals. Plan error corresponds to the Euclidean 2-norm between the final transport plan, and the transport plan at each iteration. The cost error similarly corresponds to the difference between the final squared cost and the squared cost at each iteration. A) Algorithm running with the concave IGW cost, which simplifies the line search (see section E ). B) Algorithm running with the DGW cost. In practice, the algorithm converges quickly with both costs, typically under 50 iterations.

Figure 6 : Convergence of the global optimization concave algorithm for the IGW cost, using two different strategies for selecting the search direction at each iteration. A) Convergence using our strategy, using the

P_{\Pi}^{-}

facet facing

x^{+}

. B) Convergence of Ryner et al.’s strategy [ 35 ] , using the gradient of

Q_{m}

x^{+}

Explore similar work

Distance-Matrix Wasserstein Statistics for Scalable Gromov--Wasserstein Learning
May 14, 2026Ao Xu, Tieru WuGromov--Wasserstein Wasserstein Distance
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
Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein
May 13, 2026Ashkan Shahbazi, Xinran Liu, Ping He +1Gromov--Wasserstein Geodesic
Department of Computer Science, College of Connected Computing, Vanderbilt University · Department of Electrical and Computer Engineering, Vanderbilt University
Sliced Inner Product Gromov-Wasserstein Distances
May 8, 2026Xiaoyun Gong, Gabriel Rioux, Ziv GoldfeldGromov--Wasserstein Slices

May 14, 2026, cs.LGJ/K move · Enter open · S save

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

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

Gromov--Wasserstein Wasserstein Distance Metric Spaces Intrinsic Dimensionality Feature Alignment

Open paper AskPDF arXiv

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 \emph{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

n

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

n

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

\binom n2

. For scalable computation, we introduce sliced and multi-scale DMW; for

p=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.

Abstract

Explore similar work

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

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

Sliced Inner Product Gromov-Wasserstein Distances