PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.27774v1math.OCcs.LG

TL;DR

Existing shape metrics such as Procrustes distance fail to distinguish shapes related by reflection, despite chirality being important in applications including chemistry. The paper introduces multilinear Gromov-Wasserstein distances, including CGW for SO(d), and develops efficient local and globally approximable algorithms. Numerical experiments demonstrate that CGW captures changes in shape chirality.

  • Problem

    Existing shape analysis metrics fail to distinguish a shape from its mirror image, although chirality can be important for molecular interactions.

  • Method

    The paper generalizes the Gromov-Wasserstein objective multilinearly over shapes represented by probability distributions quotiented by a symmetry group G, with CGW obtained for G = SO(d).

  • Results

    CGW captures changes in shape chirality, while the framework provides local optimization and a fully polynomial-time approximation scheme for approximate global solutions.

  • Takeaways & Limitations

    The framework provides a shape-comparison metric sensitive to specified transformations and demonstrates potential for comparing chiral molecules.

  • Takeaways & Limitations

    The multilinear distance is not translation invariant by definition, and the paper’s shape definition is not scaling invariant for a matrix Lie group G.

Abstract

from arXiv · show

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.

1 Introduction

The paper develops shape distances that can distinguish chiral objects by extending Gromov-Wasserstein objectives to transformations specified by a symmetry group. It introduces CGW for SO(d), establishes theoretical properties, and proposes globally approximable algorithms validated on chiral molecules.

  • Motivation: Existing Procrustes distance does not distinguish chiral shapes, motivating metrics sensitive to relevant shape transformations.The motivation includes molecular chirality, where reflected compounds can have different biological effects.
  • Shape representation: Shapes are represented as probability measures with finite second moment, and Wasserstein distance is made transformation-invariant by quotienting under a group G.The framework supports groups such as SO(d), E(d), and SL(d).
  • Related computational challenge: Gromov-Wasserstein distances provide an alternative that is directly invariant under group actions, but computing them is NP-hard in general.This motivates the paper’s focus on exploiting low-dimensional structure for approximation.
  • Proposed framework: The proposed multilinear Gromov-Wasserstein framework includes CGW for SO(d), making the resulting distance sensitive to chirality.The framework is designed to define and compute distances sensitive to specified transformations.
  • Algorithms: The multilinear formulation uses low-dimensional structure to support algorithms for global optimization, including a fully polynomial-time approximation scheme.The paper presents the complexity guarantee as the first estimation of complexity for globally solving a Gromov-Wasserstein-type problem.

2 Multilinear Gromov-Wasserstein distances and their fundamental properties

The paper defines multilinear Gromov-Wasserstein discrepancies as shape distances invariant under matrix Lie-group actions, with conditions ensuring they separate shapes up to the group. It also establishes scaling, stability, correspondence, and low-dimensional optimization properties.

  • Shape space: A G-shape is a probability distribution considered up to the pushforward action of a matrix Lie group G.The framework generalizes shape invariance beyond rigid transformations, scaling, and re-parametrization.
  • Invariant discrepancies: Multilinear forms invariant under G define discrepancies whose transformation-preserving group can include O(d), SL(d), or SO(d).The examples yield IGW, DGW, and CGW discrepancies associated respectively with O(d), SL(d), and SO(d).
  • Invariances and scaling: For centered marginals, the multilinear objective can be made translation invariant, while its cost otherwise remains translation dependent.Centering corresponds to a Procrustes distance with respect to translations.
  • Invariances and scaling: GWm is not scaling invariant, but scaling one marginal induces a one-to-one correspondence between optimal transport plans before and after scaling.This lets registration or matching reuse an optimal correspondence for rescaled shapes without rescaling or normalizing them.
  • Distance properties: Under non-degeneracy, GWm is a distance between G-shapes for compactly supported absolutely continuous measures and positive-volume point clouds.For these settings, zero discrepancy is equivalent to equality up to some g ∈ G.
  • Optimization and stability: The GWm optimization depends only on a d^2-dimensional projection of couplings and becomes polynomial optimization over a compact convex set.The same formulation supports existence and qualitative stability of minimizers under W2 perturbations of the marginals.
  • Optimal coupling: When the first marginal has a density and both measures have compact support, an optimal GWm plan is induced by a Monge correspondence map.The optimal transport plan can be written as (id, T)#µ.

3 Solving multilinear Gromov-Wasserstein problems in low-dimension

The paper solves multilinear Gromov-Wasserstein problems by projecting couplings into a low-dimensional space and approximating the feasible projection with iteratively refined bounding polytopes. This supports certified global approximation, local refinement, and an FPTAS under stated assumptions.

  • 3.1 A Sandwich algorithm to approximate polytopes: The method approximates the coupling projection PΠ with inner and outer bounding boxes that converge to PΠ.The boxes are built through sequential refinement using supporting hyperplanes and vertices.
  • 3.2 Optimization of the cost: The global optimization procedure computes lower and upper cost bounds that provide a certificate of global optimality and a stopping criterion.The algorithm stops when the relative gap reaches the target tolerance.
  • 3.4 Local optimization: A low-dimensional Frank-Wolfe reformulation provides local optimization initialized from the approximate global solution.For concave costs, the data-size-dependent computation reduces to classical optimal transport problems.
  • 3.1 A Sandwich algorithm to approximate polytopes: Each refinement direction is selected by maximizing the gap between the inner and outer bounding boxes, using optimal transport subproblems.The resulting boxes have controlled representation size as iterations increase.
  • 3.1 A Sandwich algorithm to approximate polytopes: Under Assumption 1, the bounding boxes converge to PΠ at rate 1/d2−1.The rate depends on the low-dimensional geometry and the stated compact-support and covariance assumptions.
  • 3.3 Global optimization for a concave cost: For discrete marginals with at most N points, Algorithm 2 is an FPTAS for the GWm problem.The iteration count for an ε-approximation depends on ε rather than the sample size N, while each iteration requires an optimal transport solve.

4 Numerical experiments

The experiments evaluate CGW on hands, molecular conformations, Gaussian distributions, and optimization behavior. CGW distinguishes handedness, while current computation faces memory–time limits at large bounding boxes.

  • Chiral shape comparisons: Without reflection, CGW distance and RMSD are linearly correlated for noisy penicillamine conformations.The comparison contrasts same-handedness conformations without reflection against enantiomers with reflection.
  • Chiral shape comparisons: Only CGW assigns a positive cost when transporting a right hand to its mirror-image left hand.Classical and Inner Gromov-Wasserstein costs use a reflection and yield zero cost.
  • Chiral shape comparisons: CGW distances are relatively larger between reflected D- and L-penicillamine conformations than between conformations with the same chirality.The experiment adds Gaussian noise, uses nine atoms with uniform weights, and confirms the solution by exhaustive enumeration.
  • Optimization behavior: In Gaussian experiments, bounding-box complexity was below the theoretical upper bound: linear rather than quadratic in 2D and O(k^3) rather than O(k^4) in 3D.These experiments assess the global optimization algorithm against the bounds established earlier.
  • Computational limitations: The current implementation reaches memory–time trade-off limits when bounding boxes contain approximately 10^5 vertices or constraints.This remains a bottleneck even when optimal transport is fast for small shapes such as the nine-point penicillamine case.
  • Optimization behavior: Numerical experiments found convergence in fewer than 50 iterations, suggesting theoretical convergence rate is not the main global-optimization bottleneck.The algorithm performed similarly to the compared method, with differences in iteration counts and marginal size.

5 Conclusion and discussion

The paper concludes that multilinear Gromov-Wasserstein distances provide theoretically grounded, computable shape comparisons, including a chirality-sensitive CGW distance. Experiments support chirality detection while identifying dimension-three and computational-scaling limits.

  • Contributions: GWm compares shapes modulo transformations from a matrix Lie group when an associated non-degenerate multilinear form exists.The distance is robust to marginal variations and admits optimal correspondence maps for registration and alignment.
  • Algorithms: The authors develop local optimization and a fully polynomial-time approximation scheme for globally solving GWm when the cost is concave.The algorithms exploit the problem’s low-dimensional structure.
  • Chiral distance: CGW captures object chirality by construction and is relevant to biological and chemical applications.For sufficiently large t, the CGWt cost is concave and computable with the proposed algorithm.
  • Empirical findings: Experiments in dimensions 2 and 3 confirmed that CGW captures changes in shape chirality.The authors state that further optimization and suitable data structures could enable more iterations in dimension 3.
  • Reproducibility: The implementation, tests, datasets, and numerical experiments are provided in Python, with penicillamine data originating from PubChem.The cited compound is PubChem CID 4727.

Notation

The notation defines the ambient spaces, probability-measure classes, transformation groups, couplings, product constructions, norms, and auxiliary matrix and polytope quantities used throughout the paper.

  • Spaces and dimensions: R denotes the real numbers, while d is the ambient dimension, typically 2 or 3.X and Y are subsets of R^d equipped with the canonical inner product.
  • Coordinate notation: A point x is written by coordinates as (x1,…,xd), while x denotes a k-family in (R^d)^k.The notation distinguishes a vector from a family of vectors.
  • Measure spaces: P(X) is the space of probability measures on X, and P2(X) is the subclass with finite second moment.These measure spaces represent shapes in the paper’s formulation.
  • Transformation groups: G denotes a matrix Lie group over R, including O(d), SO(d), SL(d), E(d), and SE(d).These groups encode the spatial transformations under which shapes may be compared.
  • Optimal transport: Π(µ,ν) denotes the set of couplings between probability measures µ and ν.A coupling is a probability measure on the product space X × Y with the prescribed marginals.
  • Product constructions: Product measures, tensor-product couplings, and componentwise maps extend measures, couplings, and transformations to k-fold product spaces.The constructions are denoted µ × ν, π⊗k, and g×n.
  • Maps and norms: The 2-norm applies to vectors, the Frobenius norm to matrices, and ⟨·,·⟩ denotes the canonical inner product.The pushforward f♯µ is the measure induced by mapping µ through f.
  • Auxiliary quantities: Σξ denotes the cross-covariance matrix, Spec denotes a symmetric matrix’s spectrum, E[·] expectation, and H2 Hausdorff distance between polytopes.These quantities support the paper’s covariance and geometric analyses.

A.1 Proofs of Section 2.1

The proofs establish finiteness, invariance, structural properties, and metric behavior of GWm under assumptions on multilinear forms, supports, densities, and point clouds.

  • Translation analysis: The proofs identify the multilinear objective as a polynomial function of the first moments in the relevant translated formulation.This supports the translation analysis for centered measures.
  • Metric properties: The multilinear GWm objective is non-negative, symmetric, and satisfies the triangle inequality, making it a pseudo-distance on P2(X).It does not separate measures related by transformations in G without additional assumptions.
  • Invariance and finiteness: Multilinearity and centered marginals eliminate translation terms in the objective, yielding invariance under the relevant transformed measures.Optimal couplings correspond through pushforward under the transformation.
  • Structural lemmas: A non-degenerate multilinear form together with a support basis forces a form-preserving map to extend uniquely as an invertible linear transformation.The proof shows the map is linear, surjective, and therefore invertible.
  • Distance separation: Under compactness and density assumptions, zero GWm cost yields an optimal Monge map belonging to GL(d) ∩ G.The argument uses full-measure basis sets and the non-degeneracy condition.
  • Discrete shapes: For distinct point clouds with non-zero volume, a zero-cost optimal plan is a scaled permutation matrix induced by a map preserving the multilinear form.Non-degeneracy prevents one source point from transporting to multiple target points.

A.2 Proofs of Section 2.2

The proofs establish low-dimensional representations of multilinear Gromov–Wasserstein costs by projecting couplings onto finite-dimensional function spaces. This structure supports convexity, compactness, and local or global optimization procedures.

  • Cost representation: The multilinear cost depends polynomially on the projected coupling rather than on the full coupling.The polynomial has d² variables and degree at most n, while the relevant quadratic-form term is non-negative on symmetric positive semidefinite matrices.
  • Projection properties: For compact full-dimensional supports, the coordinate-product functions are linearly independent, enabling an orthogonal projection onto a d²-dimensional space.The projection extends continuously to probability measures, and its image of the coupling set is compact and convex.
  • Chiral term: The determinant-based CGW term is expanded using multilinearity and Laplace expansions in terms of minors and cofactors of the projected moment matrix.This provides the algebraic form needed for evaluating the chiral contribution.
  • Low-dimensional structure: The multilinear GW problem can be rewritten through projections of couplings onto a finite-dimensional span of coordinate-product functions.For bounded centered marginals, the relevant space includes g(x,y)=||x||²−||y||² and f_i,j(x,y)=x_i y_j, giving dimension d²+1.
  • Optimization: The projected formulation supports a global algorithm and a Frank–Wolfe procedure for local optimization.The cost is concave in the coupling, allowing a variant of the global method and a local Frank–Wolfe scheme.

Auxiliary results

The auxiliary results establish existence, stability, and structural properties of multilinear Gromov–Wasserstein optimization. They also derive conditions under which optimal transport maps exist.

  • Existence and stability: An optimal coupling exists because the coupling set is precompact in W2 and the projected polynomial cost is continuous.A minimizing sequence has a convergent subsequence whose limit remains a coupling and attains the infimum.
  • Existence and stability: The projected coupling sets vary continuously under W2 perturbations of the marginals, yielding Hausdorff stability under bounded second-moment assumptions.The bound assumes m2(µ), m2(ν), m2(µ′), and m2(ν′) are at most α.
  • Robustness: The multilinear GW cost is robust to marginal perturbations because the projection is Lipschitz in W2 and Q_m is Lipschitz on bounded projected sets.The resulting constants depend on the polynomial coefficients, moment bounds, and dimension.
  • Optimal maps: Under compactness and appropriate absolute-continuity conditions, the GW_m problem admits an optimal transport map.The proof reduces the problem through orthogonal transformations and a projection to an h-dimensional space, then applies a twisted-cost transport theorem.
  • Optimal maps: For a projected cost of the form −⟨ψ1(x),ψ2(y)⟩ with an absolutely continuous source, the optimal transport plan is unique and induced by a map.The result applies when the measures have compact support and ψ1, ψ2 are diffeomorphisms.

Auxiliary results

These results control the geometry of the projected coupling set and provide non-degenerate bounding-box initializations. The construction relies on bounded support and positive covariance assumptions.

  • Projected-set geometry: Under Assumption 1, the projected coupling set contains a ball of radius r0 and is contained in a ball of radius r1 depending on d, R, and λ.Positive covariance and bounded support prevent the projection from collapsing in every direction.
  • Coupling construction: The coupling construction combines a one-dimensional optimal transport plan with conditional measures to recover a valid multidimensional coupling.The marginals are disintegrated along the first coordinates, then recombined with conditional distributions.
  • Projected-set geometry: The one-dimensional construction supplies a uniform lower bound on covariance-related coupling variation for centered distributions supported on [−R,R].The bound is established for centered measures with variance at least λ and is used to obtain r0.
  • Bounding-box initialization: Algorithm 6 constructs an initial bounding box whose inner and outer radii are controlled by r0, r1, and d.The resulting radius r2 depends only on these geometric parameters.
  • Approximation geometry: The bounding-box geometry yields a Hausdorff approximation result for polytopes when suitable inner and outer balls exist.Proposition 8 and Lemma 9 provide the radii needed to apply the polytope approximation result.

B.2 Proofs of Section 3.3

The algorithms approximate multilinear and classical Gromov–Wasserstein costs by iteratively refining low-dimensional polytope representations. Their complexity is polynomial for fixed dimension and precision.

  • Global approximation: The global approximation algorithm alternates optimal transport solves with updates to primal and dual polytope representations.Supporting hyperplanes and vertices tighten bounding boxes until the upper and lower cost bounds differ by at most ε.
  • Complexity: The total algorithmic complexity is polynomial in the number of iterations, marginal support size, and fixed dimension.The final bound is O(N^3 k_f^(2⌊d²/2⌋+2)).
  • Complexity: Each iteration requires an optimal transport computation of complexity O(N^3) plus polytope-update costs depending polynomially on k and d².The dominant iteration complexity is O(N^3 k^(2⌊d²/2⌋+1)).
  • Classical GW: For classical GW, Algorithm 4 first identifies the lower-dimensional span containing the projected coupling set before applying a sandwich algorithm.This handles cases where the full projected set has zero volume and changes the dimension used in the complexity analysis.
  • Classical GW: Theorem 6 states that Algorithm 5 approximates GW2(µ,ν)^2 to precision ε for discrete measures with bounded support.The implied constants depend on the dimension and the distributions.

Appendix C Convexity of the different costs

The appendix characterizes convexity conditions for multilinear GW costs and details practical bounding-box and line-search procedures for their optimization.

  • Cost convexity: The Inner Gromov-Wasserstein cost uses a squared Frobenius norm, while the Determinant Gromov-Wasserstein cost is neither convex nor concave.
  • CGW convexity: For d = 1, the CGW polynomial is convex when 0 < t ≤ 1.
  • CGW convexity: For d = 3, bounded supports and covariance controls yield eigenvalue bounds for the determinant Hessian, supporting sufficient convexity conditions for CGW.
  • Global optimization: The practical global solver initializes bounding boxes, iteratively updates cuts until |c+ − c−| ≤ ϵ, and then computes an optimal coupling.
  • Line search: Frank-Wolfe line searches optimize low-degree polynomials: quadratic for two-dimensional DGW/CGW and cubic for three-dimensional determinant terms.

Appendix F Supplementary Numerical Experiments

Supplementary experiments evaluate bounding-box complexity, Frank-Wolfe convergence, and alternative cut-direction strategies on Gaussian marginals.

  • Global optimization: In dimensions 2 and 3, bounding-box complexities were below the theoretical complexity established in Theorem 3.
  • Frank-Wolfe convergence: The Frank-Wolfe algorithm converged in less than 30 iterations for both IGW and DGW costs, measured by squared cost and transport-plan errors.
  • Cut selection: The proposed and Ryner et al.’s cut-selection strategies had similar convergence rates, with performance depending on point count and desired precision.

Appendix G Supplementary Figures

Supplementary figures visualize convergence certificates, bounding-box growth, and Frank-Wolfe errors for the paper’s optimization algorithms.

  • Figure 3: Figure 3 compares lower and upper bounds c− and c+ on the optimal CGW value; c− converges faster than c+ in the simulations.
  • Figure 4: Figure 4 plots IGW global-optimization convergence in dimensions 2 and 3, including bounding-box vertices, constraints, and the optimality certificate.
  • Figures 5–6: Figure 5 shows plan and squared-cost errors across Frank-Wolfe iterations, while Figure 6 compares two global cut-direction strategies.
Loading 2608.27774v1…