Research map / Point clouds / Registration and matching
Gromov-Wasserstein Problem with Cyclic Symmetry
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 Cyclic CG and Cyclic PG, fast gradient-based solvers for entropic Gromov-Wasserstein with K-order cyclic symmetry that restrict iterates to block-circulant matrices and solve a smaller OT/EOT problem each iteration.
Problem
Gromov-Wasserstein (GW) and entropic GW are computationally expensive for object matching on inputs that have cyclic symmetry (e.g., rotational or mirror symmetry in images, point clouds).
Approach
If the initial coupling is block circulant under K-order cyclic symmetry of the inputs, all gradients, intermediate solutions and OT/EOT subproblems keep that structure, so the iterations can update only K blocks of size m'×n' and solve a reduced OT/EOT problem with m'n' variables.
Key results
- On synthetic data with K=10, C-CG took 0.64 s vs 16.82 s for CG with a comparable GWD (3.75e-3 vs 3.75e-3).
- On synthetic data with K=10, C-PG took 0.94 s vs 6.73 s for PG with the same GWD (6.89e-3 vs 6.88e-3).
- On real 2D and 3D shape classification with approximate mirror symmetry (K=2), C-CG and C-PG gave better confusion matrices and were fastest, though only after a symmetric alignment preprocessing step.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use C-CG instead of CG | C-CG · Synthetic 2D point sets | GWD: 3.75 ± 2.13 -> 3.75 ± 2.13 | No clear effect |
| Use C-CG instead of CG | C-CG · Synthetic 2D point sets | time (s): 16.82 ± 10.49 -> 0.64 ± 0.3 | Helped |
| Use C-PG instead of PG | C-PG · Synthetic 2D point sets | GWD: 6.88 ± 2.13 -> 6.89 ± 2.13 | No clear effect |
| Use C-PG instead of PG | C-PG · Synthetic 2D point sets | time (s): 6.73 ± 6.78 -> 0.94 ± 0.93 | Helped |
| Use cyclic symmetry order K=10 rather than K=2 | C-CG · Synthetic 2D point sets | time (s): 3.52 ± 2.17 -> 0.64 ± 0.3 | Helped |
| Use cyclic symmetry order K=10 rather than K=2 | C-PG · Synthetic 2D point sets | time (s): 3.56 ± 3.20 -> 0.94 ± 0.93 | Helped |
| Restrict initial solutions to cyclic-symmetric matrices | C-CG and C-PG · Synthetic point-set pairs with different initial solutions | GWD | No clear effect |
| Apply symmetric alignment before C-CG | C-CG · 2D shape analysis with real-world data | classification performance | Helped |
| Apply symmetric alignment before C-PG | C-PG · 2D shape analysis with real-world data | classification performance | Helped |
| Apply symmetric alignment before C-CG | C-CG · 3D shape analysis with real-world data | classification performance | Helped |
| Apply symmetric alignment before C-PG | C-PG · 3D shape analysis with real-world data | classification performance | Helped |
Surprising findings
- Restricting the initial solution to block-circulant form did not degrade GWD in sensitivity tests over 50 random initializations.
- The paper notes that some C-EGW instances have globally optimal solutions that are never block circulant.
Limitations
- Relies on strict cyclic symmetry; approximate symmetry requires a symmetric alignment preprocessing step that may be slow or degrade solutions.
- Must know the cyclic order K in advance and only handles cyclic symmetry.
- Output restricted to block-circulant couplings, which can exclude the globally optimal solution for some instances.
Experimental setup
Datasets: synthetic 2D point sets with 10-order rotational symmetry 2D structure dataset (Bone, Glass, Butterfly, Bell) 3D structure dataset (plane, bag, bottle, chair)
Benchmarks: synthetic cyclic-symmetric point sets 2D shape classification (Bone, Glass, Butterfly, Bell) 3D shape classification (plane, bag, bottle, chair)
Metrics: Gromov-Wasserstein distance computation time number of iterations confusion matrix of 1-NN classification
Baselines: CG (conditional gradient GW) PG (projected gradient EGW) CG with symmetric alignment PG with symmetric alignment
Builds on: Conditional gradient (Frank-Wolfe) for GW Entropic Gromov-Wasserstein projected gradient Cyclic optimal transport (Takeda et al. / ref 36) Sinkhorn-Knopp
Closest papers by meaning
- Gromov-Wasserstein at Scale, Beyond Squared Norms (ICML 2026 · similarity 0.89)
- Optimal Transport with Cyclic Symmetry (AAAI 2024 · similarity 0.85)
- Partial Gromov-Wasserstein Metric (ICLR 2025 · similarity 0.84)
- Linear Partial Gromov-Wasserstein Embedding (ICLR 2025 · similarity 0.84)
- Tree-Sliced Wasserstein Distance: A Geometric Perspective (ICML 2025 · similarity 0.82)
- Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem (NeurIPS 2026 · similarity 0.82)
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.