Research map / Graph learning / Graph self-supervised learning
Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss
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 Any2Graph, an end-to-end supervised graph prediction framework trained with a novel size-agnostic, permutation-invariant Partially-Masked Fused Gromov-Wasserstein loss, plus a new synthetic Coloring dataset.
Problem
Supervised graph prediction: learning to output an entire graph of arbitrary size and unordered nodes from any input modality, end-to-end, with a differentiable permutation-invariant loss.
Approach
An asymmetric Optimal Transport loss (PMFGW) that extends Fused Gromov-Wasserstein with a predicted node-existence mask and partial masking of feature and edge terms, so the model predicts graph size and structure end-to-end on padded fixed-size continuous graphs.
Key results
- On Coloring, Any2Graph reaches edit distance 0.20 and GI accuracy 85.20% vs 5.47 and 18.14% for Relationformer.
- On GDB13, Any2Graph+FD achieves edit distance 3.63 and GI accuracy 16.25% vs 8.83 and 0.01% for Relationformer+FD.
- On Toulouse and USCities, Any2Graph is tied or slightly better than Relationformer (e.g., USCities edit distance 1.86 vs 2.09).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Any2Graph instead of Relationformer | Coloring · Coloring test | Edit distance: 5.47 -> 0.20 | Helped |
| use Any2Graph instead of Relationformer | Toulouse · Toulouse test | Edit distance: 0.13 -> 0.13 | No clear effect |
| use Any2Graph instead of Relationformer | USCities · USCities test | Edit distance: 2.09 -> 1.86 | Helped |
| use Any2Graph instead of FGWBary-ILE + FD | QM9 · QM9 test | Edit distance: 2.84 -> 3.44 | Hurt |
| use Any2Graph instead of Relationformer + FD | GDB13 · GDB13 test | Edit distance: 8.83 -> 7.45 | Helped |
| add feature diffusion (ablation) | Any2Graph · QM9 test | Edit distance: 3.44 -> 2.13 | Helped |
| add feature diffusion (ablation) | Any2Graph · GDB13 test | Edit distance: 7.45 -> 3.63 | Helped |
| increase maximum graph size M above the default (ablation) | Any2Graph · Coloring test | Edit distance | No clear effect |
| use uniform loss weights alpha instead of other simplex weights (ablation) | Any2Graph · Coloring test | Edit distance | Helped |
Surprising findings
- Relationformer with feature diffusion attains higher size accuracy (96.0) than Any2Graph+FD on QM9 despite worse graph-level metrics.
- Barycenter-based FGWBary methods nearly fail on Toulouse (GI accuracy 0%) despite being given the true graph size.
Limitations
- Cubic O(M^3) per-iteration cost of the PMFGW solver limits scalability to graphs of roughly a few tens of nodes (up to 20 nodes in experiments).
- Only RGB USCities variant and graph-to-graph tasks are left out of scope.
- Relies on a Hungarian/conditional-gradient OT solver, which is not fully parallel on GPU.
Experimental setup
Datasets: Coloring Toulouse USCities QM9 GDB13
Benchmarks: Coloring Toulouse USCities QM9 GDB13
Metrics: graph edit distance GI accuracy PMFGW loss edge precision edge recall node accuracy size accuracy
Baselines: Relationformer FGWBary-NN FGWBary-ILE
Builds on: Fused Gromov-Wasserstein Relationformer FGW barycenters Partial Fused Gromov-Wasserstein
Closest papers by meaning
- GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.84)
- Graph Generative Pre-trained Transformer (ICML 2025 · similarity 0.84)
- A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer (ICML 2024 · similarity 0.83)
- The quest for the GRAph Level autoEncoder (GRALE) (NeurIPS 2025 · similarity 0.83)
- Disentangled Graph Self-supervised Learning for Out-of-Distribution Generalization (ICML 2024 · similarity 0.82)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · 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.