Research map / Graph learning / Graph self-supervised learning
Flatten Graphs as Sequences: Transformers are Scalable Graph Generators
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 AutoGraph, which flattens attributed graphs into random segmented Eulerian neighborhood trail token sequences and models them autoregressively with a decoder-only transformer, achieving SOTA MMD/VUN on synthetic and molecular graph benchmarks with much faster sampling and training than diffusion models.
Problem
Graph generation with diffusion models is slow and memory-hungry (quadratic adjacency operations, expensive node features), while prior autoregressive graph models use specialized RNN architectures and do not produce token sequences that LLMs can model directly.
Approach
Reversibly flatten graphs into random segmented Eulerian neighborhood trails (SENTs) with neighborhood sets, reindex nodes by first occurrence, and tokenize them so that a standard decoder-only language model learns next-token prediction; causal Hamiltonian/semi-Hamiltonian SENTs make prefixes induced subgraphs, enabling linear-in-edges sampling and substructure conditioning.
Key results
- On Planar, AutoGraph reaches degree MMD 0.0004 and orbit MMD 0.0003 with the best MMD ratio 1.5 among compared models, and VUN 87.5 (second-best); on SBM it reaches VUN 92.5, the best reported.
- AutoGraph trains about 3-4x faster than DiGress and ESGG (e.g., 6.2h vs 25.9h on Planar; 13.8h vs 47.7h on SBM) and samples roughly 93-284x faster per graph than DiGress.
- On MOSES, AutoGraph achieves FCD 0.91 versus 1.19 for DiGress; the PubChem-pretrained variant reaches validity 95.9 on GuacaMol.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use AutoGraph instead of GruM | small synthetic graph generation · SBM | VUN: 85.0 -> 92.5 | Helped |
| use AutoGraph instead of the strongest reported baseline | graph generation · Planar | VUN: 95.0 -> 87.5 | Hurt |
| use AutoGraph instead of ESGG | large graph generation · Proteins | Ratio: 4.7 -> 2.3 | Helped |
| use AutoGraph instead of ESGG | large graph generation · Point Clouds | Ratio: 6.8 -> 3.0 | Helped |
| use AutoGraph instead of DiGress | molecular generation · QM9 with hydrogen atoms | Valid: 95.4 -> 97.7 | Helped |
| use AutoGraph instead of DiGress | molecular generation · MOSES | FCD: 1.19 -> 0.91 | Helped |
| pre-train AutoGraph on PubChem-10M before GuacaMol training (ablation) | AutoGraph · GuacaMol | FCD: 79.2 -> 91.4 | Helped |
| replace LLaMA with GPT-2 (ablation) | AutoGraph · Planar | VUN: 90.0 -> 85.0 | Hurt |
| replace LLaMA with Mamba (ablation) | AutoGraph · Planar | VUN: 90.0 -> 55.0 | Hurt |
| use a smaller top-k (ablation) | AutoGraph inference · Planar | VUN | Helped |
| use a smaller top-k (ablation) | AutoGraph inference · SBM | VUN | No clear effect |
| increase top-k (ablation) | AutoGraph inference · Planar and SBM | Ratio | Helped |
Surprising findings
- Constraint-free decoding always produced semantically correct sequences for unattributed graphs, so transition constraints were unnecessary there.
- Restricting SET (without neighborhood information) yields VUN near zero on Planar, showing neighborhood sets are essential for structural validity.
Limitations
- Benchmark datasets are small relative to LLM pretraining corpora, so scaling claims are limited.
- Molecular metrics computed on SMILES, and about 20% of molecules cannot be mapped back to their original SMILES, introducing discrepancies.
- Validity on MOSES (87.4) and the strong FCD/validity results depend on benchmark tooling that may rely on outdated packages.
Experimental setup
Datasets: Planar SBM Proteins Point Clouds QM9 MOSES GuacaMol NetworkX PubChem-10M
Benchmarks: Planar SBM Proteins Point Clouds QM9 MOSES GuacaMol
Metrics: MMD degree MMD clustering MMD orbit MMD spectrum MMD ratio VUN validity uniqueness novelty FCD
Baselines: GraphRNN GRAN SPECTRE EDGE GraphGen BiGG DiGress GruM GEEL ESGG
Builds on: GraphRNN LLaMA GPT-2 Mamba DiGress
Closest papers by meaning
- From Sequence to Structure: Uncovering Substructure Reasoning in Transformers (NeurIPS 2025 · similarity 0.87)
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.86)
- Graph Generative Pre-trained Transformer (ICML 2025 · similarity 0.86)
- Generative Graph Pattern Machine (NeurIPS 2025 · similarity 0.86)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.86)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.86)
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.