Research map / Learning theory and algorithms / Optimal transport
Linear Partial Gromov-Wasserstein Embedding
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 linear partial Gromov-Wasserstein (LPGW) embedding, a linearization of the partial GW problem that reduces pairwise PGW computations from O(K^2) to O(K) solves, with a metric proof under conditions, evaluated on shape retrieval and transform-based learning.
Problem
Partial Gromov-Wasserstein (PGW) distances allow comparing unbalanced measures across metric spaces but are non-convex and expensive, so pairwise computation over K spaces needs O(K^2) solves.
Approach
Extend the linear GW (LGW) embedding, which uses barycentric projections of optimal transport plans against a fixed reference space, to the partial setting by embedding each space as a triple (transport mass, transport cost kernel, created mass), so pairwise LPGW distances need only K PGW solves against a reference space.
Key results
- On the 2D shape dataset, LPGW reaches 97.5% accuracy in 0.5s versus PGW's 96.2% in 39s, and GW's 98.1% in 43s.
- On the 3D dataset, LPGW achieves 93.7% accuracy in 1.8 min versus PGW's 93.8% in 203.6 min.
- On noisy MNIST point clouds with eta=0.5, LPGW keeps 72.9% accuracy while LOT and LGW drop to about 12.5%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LPGW with S8 as the reference space instead of pairwise PGW | Elliptical Disks · Elliptical Disks (λ = 0.1) | time (min): 46.97 -> 1.98 | Helped |
| Use LPGW with S8 as the reference space | LPGW · Elliptical Disks (λ = 0.1) | MRE: 0.0198 | Helped |
| Use LPGW with S8 as the reference space | LPGW · Elliptical Disks (λ = 0.1) | PCC: 0.9954 | Helped |
| Replace PGW with LPGW | Shape retrieval · 2D Shape Retrieval | accuracy: 98.1% -> 97.5% | Hurt |
| Replace GW with LPGW | Shape retrieval · 2D Shape Retrieval | time (s): 43s -> 0.5s | Helped |
| Replace PGW with LPGW | Shape retrieval · 3D Shape Retrieval | accuracy: 93.8% -> 93.7% | Hurt |
| Replace PGW with LPGW | Shape retrieval · 3D Shape Retrieval | time (m): 203.6m -> 1.8m | Helped |
| Use LPGW embeddings instead of LOT | MNIST point-cloud classification · MNIST point clouds (no rotation) | accuracy: 89.0% -> 82.5% | Hurt |
| Use LPGW embeddings instead of LOT | MNIST point-cloud classification · MNIST point clouds (η = 0) | accuracy: 51.2% -> 82.5% | Helped |
| Use LPGW embeddings instead of LOT | MNIST point-cloud classification · MNIST point clouds (η = 0.1) | accuracy: 13.4% -> 81.8% | Helped |
| Use LPGW embeddings instead of LOT | MNIST point-cloud classification · MNIST point clouds (η = 0.3) | accuracy: 12.5% -> 75.8% | Helped |
| Use LPGW embeddings instead of LOT | MNIST point-cloud classification · MNIST point clouds (η = 0.5) | accuracy: 12.5% -> 72.9% | Helped |
Surprising findings
- LGW and LOT embeddings collapse to near random guessing (about 12.5%) under added noise, while LPGW retains 72.9% at eta=0.5.
Limitations
- Metric property holds only under certain assumptions (e.g., lambda large enough), and the barycentric projection result is proven mainly for squared Euclidean gauges.
- The choice of reference space strongly affects approximation quality (MRE ranges from 0.02 to 0.25 across reference spaces).
Experimental setup
Datasets: 2D elliptical disks dataset 2D shape dataset (8 classes, 20 shapes each) 3D shape dataset with complete and incomplete shapes (ShapeNet-style, 4 classes sampled to 240 shapes) MNIST 2D point cloud dataset
Benchmarks: elliptical disks pairwise distances 2D shape retrieval 3D shape retrieval MNIST point cloud classification with rotation and noise
Metrics: mean relative error Pearson correlation coefficient SVM classification accuracy wall-clock time
Baselines: GW PGW LGW LOT
Builds on: linear optimal transportation (LOT) linear Gromov-Wasserstein (LGW) partial Gromov-Wasserstein
Closest papers by meaning
- Partial Gromov-Wasserstein Metric (ICLR 2025 · similarity 0.92)
- The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation (NeurIPS 2021 · similarity 0.90)
- Joint Metric Space Embedding by Unbalanced Optimal Transport with Gromov–Wasserstein Marginal Penalization (ICML 2025 · similarity 0.88)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.87)
- Generalized Sobolev Transport for Probability Measures on a Graph (ICML 2024 · similarity 0.86)
- A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport (NeurIPS 2026 · similarity 0.86)
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.