# Linear Partial Gromov-Wasserstein Embedding

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 28 of 28)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [Wasserstein Embedding for Graph Learning](https://mlsanity.com/paper/2006.09430/) (2020)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations](https://mlsanity.com/paper/2008.09165/) (2020)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [Sliced Optimal Partial Transport](https://mlsanity.com/paper/2212.08049/) (2022)
- [On a linear Gromov-Wasserstein distance](https://mlsanity.com/paper/2112.11964/) (2021)
- [On the existence of Monge maps for the Gromov-Wasserstein problem](https://mlsanity.com/paper/2210.11945/) (2022)
- [A contribution to Optimal Transport on incomparable spaces](https://mlsanity.com/paper/2011.04447/) (2020)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [The Linearized Hellinger--Kantorovich Distance](https://mlsanity.com/paper/2102.08807/) (2021)
- [Reversible Gromov-Monge Sampler for Simulation-Based Inference](https://mlsanity.com/paper/2109.14090/) (2021)
- [Multi-View Partial (MVP) Point Cloud Challenge 2021 on Completion and Registration: Methods and Results](https://mlsanity.com/paper/2112.12053/) (2021)
- [Improving Molecular Representation Learning with Metric Learning-enhanced Optimal Transport](https://mlsanity.com/paper/2202.06208/) (2022)
- [Linear Optimal Partial Transport Embedding](https://mlsanity.com/paper/2302.03232/) (2023)
- [(Probably) Concave Graph Matching](https://mlsanity.com/paper/1807.09722/) (2018)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Partial Gromov-Wasserstein Metric](https://mlsanity.com/paper/2402.03664/) (2024)
- [Cycle Consistent Probability Divergences Across Different Spaces](https://mlsanity.com/paper/2111.11328/) (2021)
- [Transport type metrics on the space of probability measures involving singular base measures](https://mlsanity.com/paper/2201.00875/) (2022)
- [PTLp: Partial Transport Lp Distances](https://mlsanity.com/paper/2307.13571/) (2023)

## Built on by (most cited first, 1 of 1)

- [Conic Formulations of Transport Metrics for Unbalanced Measure Networks and Hypernetworks](https://mlsanity.com/paper/2508.10888/) (2025)

## Abstract (arXiv)

The Gromov-Wasserstein (GW) problem, a variant of the classical optimal transport (OT) problem, has attracted growing interest in the machine learning and data science communities due to its ability to quantify similarity between measures in different metric spaces. However, like the classical OT problem, GW imposes an equal mass constraint between measures, which restricts its application in many machine learning tasks. To address this limitation, the partial Gromov-Wasserstein (PGW) problem has been introduced. It relaxes the equal mass constraint, allowing the comparison of general positive Radon measures. Despite this, both GW and PGW face significant computational challenges due to their non-convex nature. To overcome these challenges, we propose the linear partial Gromov-Wasserstein (LPGW) embedding, a linearized embedding technique for the PGW problem. For K different metric measure spaces, the pairwise computation of the PGW distance requires solving the PGW problem O(K2) times. In contrast, the proposed linearization technique reduces this to O(K) times. Similar to the linearization technique for the classical OT problem, we prove that LPGW defines a valid metric for metric measure spaces. Finally, we demonstrate the effectiveness of LPGW in practical applications such as shape retrieval and learning with transport-based embeddings, showing that LPGW preserves the advantages of PGW in partial matching while significantly enhancing computational efficiency. The code is available at https://github.com/mint-vu/LinearizedPartialGromovWasserstein.