# Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric

arXiv: https://arxiv.org/abs/2509.04089 · HTML: https://mlsanity.com/paper/2509.04089/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 97 references that are in the map.
- First posted on arXiv 4 Sep 2025.

## Builds on (most cited first, 30 of 36)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Neural Optimal Transport](https://mlsanity.com/paper/2201.12220/) (2022)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Unified Optimal Transport Framework for Universal Domain Adaptation](https://mlsanity.com/paper/2210.17067/) (2022)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Distributionally Robust Optimization and Robust Statistics](https://mlsanity.com/paper/2401.14655/) (2024)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces](https://mlsanity.com/paper/2002.01615/) (2020)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)
- [Unbalanced Optimal Transport: A Unified Framework for Object Detection](https://mlsanity.com/paper/2307.02402/) (2023)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [Semidefinite Relaxations of the Gromov-Wasserstein Distance](https://mlsanity.com/paper/2312.14572/) (2023)
- [Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces](https://mlsanity.com/paper/2307.09057/) (2023)
- [Moment-SoS Methods for Optimal Transport Problems](https://mlsanity.com/paper/2211.10742/) (2022)
- [Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1706.07622/) (2017)

## Abstract (arXiv)

The assignment problem, a cornerstone of operations research, seeks an optimal one-to-one mapping between agents and tasks to minimize total cost. This work traces its evolution from classical formulations and algorithms to modern optimal transport (OT) theory, positioning the Quadratic Assignment Problem (QAP) and related structural matching tasks within this framework. We connect the linear assignment problem to Monge's transport problem, Kantorovich's relaxation, and Wasserstein distances, then extend to cases where source and target lie in different metric-measure spaces requiring Gromov-Wasserstein (GW) distances. GW formulations, including the fused GW variant that integrates structural and feature information, naturally address QAP-like problems by optimizing alignment based on both intra-domain distances and cross-domain attributes. Applications include graph matching, keypoint correspondence, and feature-based assignments. We present exact solvers, Genetic Algorithms (GA), and multiple GW variants, including a proposed multi-initialization strategy (GW-MultiInit) that mitigates the risk of getting stuck in local optima alongside entropic Sinkhorn-based approximations and fused GW. Computational experiments on capacitated QAP instances show that GW-MultiInit consistently achieves near-optimal solutions and scales efficiently to large problems where exact methods become impractical, while parameterized EGW and FGW variants provide flexible trade-offs between accuracy and runtime. Our findings provide theoretical foundations, computational insights, and practical guidelines for applying OT and GW methods to QAP and other real-world matching problems, such as those in machine learning and logistics.