Research map / Learning theory and algorithms / Optimal transport
A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace double-loop BPG/eBPG-style inner solves with single-loop KL-BAPG alternating projections | graph alignment (GW) · Synthetic graph alignment | matching accuracy: 99.79 vs 61.48 (BPG-S) and 57.56 (BPG) | Helped |
| use KL-BAPG instead of prior GW solvers for graph alignment | graph alignment on real datasets · Proteins, Enzymes, Reddit (raw and noisy) | matching accuracy: Best among GW methods in most columns, e.g. Reddit raw 50.93 vs 50.71 (SpecGW) | Helped |
| KL-BAPG on GPU instead of CPU (ablation) | KL-BAPG · Reddit and Synthetic graph alignment | wall-clock time / acceleration ratio: acceleration 6.78x (Reddit) and 7.20x (Synthetic) vs 1.88x for BPG and 0.54x for eBPG on Reddit | Helped |
| use KL-BAPG for graph partition with adjacency matrices | graph partition · Wikipedia, EU-email, Amazon, Village (adjacency, AMI) | AMI: Best on Wikipedia raw (0.469), EU-email raw and noisy, Village raw; but below eBPG on Wikipedia noisy (0.396 vs 0.413) | Mixed |
| use KL-BAPG with heat kernel matrices for graph partition | graph partition · Wikipedia, EU-email, Amazon, Village (heat kernel, AMI) | AMI: Wins 7 of 8 raw/noisy cells vs BPG/SpecGW but SpecGW is best on Wikipedia noisy (0.395 vs 0.365) | Mixed |
| relax the Birkhoff constraint (infeasible coupling) via penalty rho, versus exact-feasible solvers (ablation) | KL-BAPG · Reddit trade-off study | infeasibility error vs accuracy: Larger rho gives lower infeasibility but slower convergence; FW and SpecGW have almost zero infeasibility | Mixed |
| use KL-BAPG instead of eBPG on graph partition with heat kernel matrices | graph partition · Heat kernel partition datasets | AMI: e.g. Amazon raw 0.630 vs eBPG 0.604; eBPG drops to 0.031 on Amazon noisy | Helped |
Closest papers by meaning
- LoBCD-GW: A Fast and Data-Dependent Algorithm for Computing Gromov-Wasserstein Distance via Localized Block Coordinate Descent (ICML 2026 · similarity 0.88)
- Gromov-Wasserstein at Scale, Beyond Squared Norms (ICML 2026 · similarity 0.88)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.87)
- Graph Alignment via Birkhoff Relaxation (NeurIPS 2025 · similarity 0.87)
- A Provably Convergent and Practical Algorithm for Gromov–Wasserstein Optimal Transport (NeurIPS 2026 · similarity 0.86)
- AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs (NeurIPS 2026 · 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.