Research map / Graph learning / Graph algorithms and clustering
Graph Mixup on Approximate Gromov–Wasserstein Geodesics
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 GEOMIX, a graph mixup method that interpolates graphs along (approximate) Gromov-Wasserstein geodesics via equivalence-preserving transformations, ensuring sample-label consistency and improving GNN generalization and robustness.
Problem
Graph mixup methods use practical interpolations that are not equivalence-preserving, so generated graph samples can have labels inconsistent with their structure; the paper asks what interpolation guarantees sample-label consistency for graph data.
Approach
Defines sample-label consistency via GW distance, shows that linear interpolation of GW-aligned equivalence-preserving transformed graphs (Kronecker-product lifting) yields an exact GW geodesic, and approximates this with a low-rank GW factorization of the coupling with a tunable mixup graph size r, solved by mirror descent with Dykstra projections.
Key results
- GEOMIX achieves the best performance in 8 of 10 settings on graph classification with GCN and GIN, with up to 6.6% improvement over the best competitor.
- On sample-label consistency on IMDB-B, GEOMIX reaches a Pearson coefficient of 0.91, versus 0.71 for FGWMixup and 0.25 for G-Mixup.
- Under topology corruption GEOMIX gains up to 4.7% and under label corruption up to 1.8% over the best competitor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GEOMIX instead of G-Mixup | GCN · PROTEINS | accuracy: 63.6±3.5 -> 70.2±4.7 | Helped |
| Use GEOMIX instead of SubMix | GCN · MUTAG | accuracy: 73.5±7.1 -> 76.1±5.5 | Helped |
| Use GEOMIX instead of FGWMixup | GCN · MSRC-9 | accuracy: 89.6±3.9 -> 90.3±2.9 | Helped |
| Use GEOMIX instead of G-Mixup | GCN · IMDB-B | accuracy: 72.2±2.4 -> 72.0±4.3 | Hurt |
| Use GEOMIX instead of S-Mixup | GCN · IMDB-M | accuracy: 48.5±2.0 -> 49.3±5.5 | Helped |
| Use GEOMIX instead of M-Mixup | GIN · PROTEINS | accuracy: 70.4±6.1 -> 71.3±3.7 | Helped |
| Use GEOMIX instead of Subgraph | GIN · MUTAG | accuracy: 75.0±7.6 -> 80.8±6.2 | Helped |
| Use GEOMIX instead of DropNode | GIN · MSRC-9 | accuracy: 91.8±4.9 -> 92.8±3.6 | Helped |
| Use GEOMIX instead of M-Mixup | GIN · IMDB-B | accuracy: 71.7±3.6 -> 72.1±2.9 | Helped |
| Use GEOMIX instead of G-Mixup | GIN · IMDB-M | accuracy: 47.0±4.1 -> 46.9±4.9 | Hurt |
| Vary the mixup graph size r (ablation) | GEOMIX · graph classification datasets | accuracy: ±3% | No clear effect |
Surprising findings
- G-Mixup collapses to about 12.2% accuracy on MSRC-9 with GCN, far below vanilla training.
- Performance is stable across mixup graph sizes r, varying by at most about 3% in accuracy.
Limitations
- Experiments are limited to graph classification on five small TU-style datasets with GCN and GIN backbones.
- Node-level mixup and mixup sample selection are left as future directions.
- The approximation to exact GW geodesics depends on the mixup graph size r, which trades off approximation quality and efficiency.
Experimental setup
Datasets: PROTEINS MUTAG MSRC-9 IMDB-B IMDB-M
Benchmarks: PROTEINS MUTAG MSRC-9 IMDB-B IMDB-M
Metrics: classification accuracy Pearson correlation for sample-label consistency running time
Baselines: DropEdge DropNode Subgraph M-Mixup SubMix G-Mixup S-Mixup FGWMixup
Builds on: Mixup G-Mixup low-rank Gromov-Wasserstein FGWMixup M-Mixup
Closest papers by meaning
- AGMixup: Adaptive Graph Mixup for Semi-supervised Node Classification (AAAI 2025 · similarity 0.88)
- IntraMix: Intra-Class Mixup Generation for Accurate Labels and Neighbors (NeurIPS 2024 · similarity 0.86)
- Graph Invariant Learning with Subgraph Co-mixup for Out-of-Distribution Generalization (AAAI 2024 · similarity 0.86)
- Learning Divergence Fields for Shift-Robust Graph Representations (ICML 2024 · similarity 0.85)
- Graph Distillation with Eigenbasis Matching (ICML 2024 · similarity 0.84)
- Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 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.