Research map / Learning theory and algorithms / Optimal transport
Semidefinite Relaxations of the Gromov-Wasserstein Distance
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 a semidefinite programming relaxation of the Gromov-Wasserstein distance that yields globally optimal transport plans (with optimality certificates) in many instances, solved with off-the-shelf SDP solvers.
Problem
The Gromov-Wasserstein distance is a non-convex quadratic program over transport plans, and existing solvers (conditional gradient, entropic GW) only find local optima, so global optimality is not guaranteed.
Approach
Lifts the GW quadratic program to a PSD matrix P ~ vec(pi)vec(pi)^T and drops the rank-one constraint, then tightens it with nonnegativity and marginal-consistency linear constraints (adapted from QAP relaxations but omitting orthogonality constraints, which are invalid for non-permutation plans). If the relaxation's bound equals the transport plan's cost, the plan is certified globally optimal.
Key results
- On Gaussian matching, the estimated approximation ratio of GW-SDP is close to 1.0 in most instances, while CG-GW often returns suboptimal plans with larger objective values.
- GW-SDP runtime grows steeply with sample size: about 0.24 s at n=6, 11.6 s at n=12, and 216 s at n=20, versus milliseconds for CG-GW.
- On the 3D shape-matching task, GW-SDP returned the smallest GW value in all five object-pair comparisons (e.g., Elephant-Elephant 0.007416 vs 0.043879 for GW-CG).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GW-SDP instead of GW-CG for shape matching | GW shape matching · Realistic 3D shape matching dataset (five listed object pairs) | GW objective: 0.043879 -> 0.007416; 0.050594 -> 0.015695; 0.016634 -> 0.006549; 0.033736 -> 0.011040; 0.033768 -> 0.006287 | Helped |
| Use GW-SDP instead of eGW-PPA for shape matching | GW shape matching · Realistic 3D shape matching dataset (five listed object pairs) | GW objective: 0.025688 -> 0.007416; 0.042214 -> 0.015695; 0.006757 -> 0.006549; 0.011041 -> 0.011040; 0.007395 -> 0.006287 | Mixed |
| Use GW-SDP instead of GW-CG | GW solver · Gaussian matching, n=10 | GW objective: 1.135940 -> 0.4577 | Helped |
| Use GW-SDP instead of GW-CG | GW solver · Gaussian matching, n=6, 12, 20 | runtime (seconds): 0.0005 (0.000041) -> 0.2437 (0.0265); 0.0006 (0.00003) -> 11.615 (2.4088); 0.0014 (0.000017) -> 216.3645 (14.1123) | Hurt |
| Use GW-SDP rather than GW-CG's 10-sample result | GW solver · Gaussian matching, 10 sample points | GW objective: 1.135940 -> 0.4577 | Helped |
| Increase the number of samples for GW-CG | GW-CG · Gaussian matching, n=10 to n=10000 | GW objective: 1.135940 -> 0.629425 -> 0.540984 -> 0.496796 | Helped |
| Apply the SDP relaxation to Fused-GW matching | FGW-SDP · Synthetic graph matching task | objective value | Helped |
| Use GW-SDP with m not a multiple of n rather than m a multiple of n | GW-SDP · Gaussian matching with n=8 | frequency of exactness | Hurt |
Surprising findings
- Relaxation is exact more often when m is a multiple of n, and is much less frequently exact when m is not a multiple of n.
- The standard QP SDP relaxation without the added constraints is unbounded below, so the nonnegativity and marginal constraints are essential.
Limitations
- SDP is of dimension mn, so runtime scales poorly and only moderate-sized instances are solvable with off-the-shelf solvers.
- Relaxation is not always tight; duality gap is non-zero in general, so global optimality is only certified in some instances.
- Experiments are on small synthetic and small mesh instances (up to about 20 points).
Experimental setup
Datasets: synthetic Gaussian point clouds synthetic stochastic block model graphs noisy circular graphs public triangular mesh dataset of animal shapes (72 objects, cat/elephant/horse classes)
Benchmarks: synthetic Gaussian matching SBM graph community matching 3D shape matching
Metrics: GW objective value approximation ratio (estimated optimality gap) runtime in seconds sparsity of transport plan
Baselines: CG-GW (PythonOT conditional gradient) entropic GW (eGW, Sinkhorn projections) eGW-PPA Fused-GW conditional gradient
Builds on: Gromov-Wasserstein distance conditional gradient GW solver entropic Gromov-Wasserstein quadratic assignment problem SDP relaxations Fused Gromov-Wasserstein
Closest papers by meaning
- Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem (NeurIPS 2026 · similarity 0.89)
- A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport (NeurIPS 2026 · similarity 0.89)
- A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.87)
- Linear Partial Gromov-Wasserstein Embedding (ICLR 2025 · similarity 0.87)
- Tree-Sliced Wasserstein Distance: A Geometric Perspective (ICML 2025 · similarity 0.85)
- Scalable Approximation Algorithms for $p$-Wasserstein Distance and Its Variants (ICML 2025 · similarity 0.85)
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.