Research map / Learning theory and algorithms / Optimal transport
Partial Gromov-Wasserstein Metric
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Partial Gromov-Wasserstein (PGW), a total-variation-penalized unbalanced GW formulation proven to be a metric between general mm-spaces, with two Frank-Wolfe solvers reducing the direction-finding step to partial OT, plus PGW barycenters.
Problem
Unbalanced Gromov-Wasserstein (UGW) yields only a discrepancy, not a metric, between general (non-probability) metric measure spaces, and existing solvers for unbalanced/partial GW variants are limited.
Approach
Use a total-variation (linear) mass penalty on the squared marginals in the GW objective, which reduces to a GW problem with cost shifted by -2λ over partial couplings; prove this gives a metric between mm-spaces and solve it via Frank-Wolfe with the direction step as a partial OT problem solved by converting to OT.
Key results
- PGW achieves 100% SVM accuracy on Dataset II versus 80.83% for GW, and 96.25% on Dataset I versus 98.13% for GW.
- PGW has the lowest wall-clock time among compared distances: 35.92s on Dataset I (vs. 1484.49s for UGW) and 79.27s on Dataset II.
- In shape matching with 20% outliers, PGW and MPGW match one-to-one without matching outliers, whereas GW matches all outliers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PGW instead of GW | Shape retrieval · Dataset I | accuracy: 0.9813 -> 0.9625 | Hurt |
| Use PGW instead of GW | Shape retrieval · Dataset II | accuracy: 0.8083 -> 1.0000 | Helped |
| Use PGW instead of GW | Shape retrieval · Dataset I | wall-clock time: 49.02s -> 35.92s | Helped |
| Use PGW instead of GW | Shape retrieval · Dataset II | wall-clock time: 137.12s -> 79.27s | Helped |
| Use PGW instead of UGW | Shape retrieval · Dataset I | wall-clock time: 1484.49s -> 35.92s | Helped |
| Use PGW instead of UGW | Shape retrieval · Dataset II | wall-clock time: 519.91s -> 79.27s | Helped |
| Use PGW instead of MPGW | Shape retrieval · Dataset I | accuracy: 0.2375 -> 0.9625 | Helped |
| Use PGW instead of MPGW | Shape retrieval · Dataset II | accuracy: 0.2500 -> 1.0000 | Helped |
| Use PGW rather than GW for matching with outliers | Shape matching · 2D/3D point clouds with 20% target outliers | outlier matching | Helped |
| Use PGW rather than UGW for matching with outliers | Shape matching · 2D/3D point clouds with 20% target outliers | outlier matching | Helped |
| Use PGW barycenters rather than GW barycenters | Shape interpolation · Noisy target shapes at 5% and 10% noise | robustness to noise | Helped |
Surprising findings
- MPGW achieves only about 24-25% SVM accuracy, far below the other distances, despite being a related partial GW formulation.
- GW slightly outperforms PGW on Dataset I shape retrieval (98.13% vs 96.25%).
Limitations
- Solvers find only local minima because the GW problem is non-convex; global optimality is not guaranteed.
- Experiments are limited to small-scale 2D/3D toy and shape datasets.
Experimental setup
Datasets: make_moons (scikit-learn) 2D shape dataset adapted from prior work (bone, goblet, star, horseshoe) synthetic 2D rectangle/house/arrow/semicircle/circle shapes synthetic 2D/3D spherical data
Benchmarks: shape retrieval on Dataset I (160 shapes, 8 classes) shape retrieval on Dataset II (120 shapes, 6 classes) shape matching with outliers (toy) barycenter shape interpolation with noise
Metrics: SVM classification accuracy nearest neighbor confusion matrix wall-clock time
Baselines: GW MPGW UGW
Builds on: Gromov-Wasserstein distance unbalanced Gromov-Wasserstein (UGW) partial optimal transport Frank-Wolfe algorithm mass-constrained partial GW (MPGW)
Closest papers by meaning
- Linear Partial Gromov-Wasserstein Embedding (ICLR 2025 · similarity 0.92)
- A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.87)
- Joint Metric Space Embedding by Unbalanced Optimal Transport with Gromov–Wasserstein Marginal Penalization (ICML 2025 · similarity 0.86)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.85)
- Tree-Sliced Wasserstein Distance with Nonlinear Projection (ICML 2025 · similarity 0.84)
- Distance-Based Tree-Sliced Wasserstein Distance (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.