Research map / Graph learning / Graph self-supervised learning
A Simple and Scalable Representation for Graph Generation
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 GEEL, a gap-encoded edge list representation with bandwidth restriction and node positional encoding, generated autoregressively by an LSTM in O(M) time, and extends it to attributed molecular graphs via a grammar.
Problem
Graph generation with neural networks does not scale to large graphs because adjacency-matrix representations grow quadratically with node count, while prior edge-list representations suffer from a vocabulary of size N^2 that makes learning hard.
Approach
Represent a graph as a sorted edge list encoded with inter-edge and intra-edge gaps, so the token vocabulary is bounded by B^2 (graph bandwidth after Cuthill-McKee ordering) rather than N^2; add source-node positional encoding and generate with an LSTM, with grammar-constrained decoding for attributed graphs.
Key results
- On general graph benchmarks GEEL achieves MMD at or near training-graph level on most datasets (e.g., Grid degree/clustering/orbit all 0.000, Planar degree 0.001), reported as state-of-the-art or competitive across 8 general datasets.
- On ZINC250k GEEL reaches 99.31% validity, FCD 0.401 and scaffold similarity 0.5565, outperforming domain-agnostic baselines such as DiGress and GDSS.
- On QM9 GEEL achieves FCD 0.089 and scaffold 0.9386, with FCD and scaffold better than molecule-specific models in the table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GEEL instead of DiGress | graph generation · Planar | orbit MMD: 0.008 -> 0.001 | Helped |
| Use GEEL instead of GraphRNN | graph generation · Lobster | orbit MMD: 0.000 -> 0.001 | Hurt |
| Use GEEL instead of GDSS | graph generation · Enzymes | orbit MMD: 0.009 -> 0.006 | Helped |
| Use GEEL instead of DiGress | graph generation · SBM | orbit MMD: 0.058 -> 0.026 | Helped |
| Use GEEL instead of BiGG | graph generation · Ego | orbit MMD: 0.012 -> 0.016 | Hurt |
| Use GEEL instead of GDSM | graph generation · Grid | orbit MMD: 0.000 -> 0.000 | No clear effect |
| Use GEEL instead of SwinGNN | graph generation · Proteins | orbit MMD: 0.003 -> 0.003 | No clear effect |
| Use GEEL instead of BiGG | graph generation · 3D point cloud | orbit MMD: 0.007 -> 0.020 | Hurt |
| Remove source node positional encoding (ablation) | GEEL · Planar | orbit MMD: 0.001 -> 0.001 | No clear effect |
| Remove source node positional encoding (ablation) | GEEL · Lobster | orbit MMD: 0.001 -> 0.006 | Hurt |
| Remove source node positional encoding (ablation) | GEEL · Enzymes | orbit MMD: 0.006 -> 0.002 | Helped |
| Remove source node positional encoding (ablation) | GEEL · SBM | orbit MMD: 0.026 -> 0.028 | Hurt |
Surprising findings
- Novelty of GEEL on general graphs is lower than diffusion-based models (e.g., 22.30% novelty on QM9), which the authors attribute to a trade-off with distribution fidelity.
- The authors found that sampling a C-M ordering per graph at each training step, rather than fixing one, improved novelty without hurting performance.
Limitations
- Novelty is lower than diffusion-based and some autoregressive baselines, reflecting a fidelity-novelty trade-off.
- Representation relies on graphs having low bandwidth after C-M ordering; high-bandwidth graphs would enlarge the vocabulary.
- Some baseline results were reproduced by the authors with open-source code, and several cells in the tables are missing or OOM, complicating comparison.
Experimental setup
Datasets: Planar Lobster Enzymes SBM Ego Grid Proteins 3D point cloud QM9 ZINC250k Ego-small Community-small
Benchmarks: Planar Lobster Enzymes SBM Ego Grid Proteins 3D point cloud QM9 ZINC250k MOSES Ego-small
Metrics: MMD degree MMD clustering coefficient MMD orbit count validity uniqueness novelty NSPDK FCD scaffold similarity SNN
Baselines: GraphRNN GRAN BiGG GDSS DiGress GraphGen GraphGen-Redux BwR HGGT GraphAF GraphDF EDP-GNN
Builds on: GraphRNN BiGG GRAN BwR
Closest papers by meaning
- Graph Generative Pre-trained Transformer (ICML 2025 · similarity 0.88)
- On the Scalability of GNNs for Molecular Graphs (NeurIPS 2024 · similarity 0.88)
- SNACK: A Sequential Notation Framework for Probabilistic Graph Generation (NeurIPS 2026 · similarity 0.86)
- Graph Generation with $K^2$-trees (ICLR 2024 · similarity 0.86)
- GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.86)
- LLaMo: Large Language Model-based Molecular Graph Assistant (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.