Research map / Graph learning / Graph self-supervised learning
Efficient and Scalable Graph Generation through Iterative Local Expansion
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.
Generates graphs by iteratively expanding a single node into a full graph via coarsening-inverting denoising diffusion steps with a sparse-expressive Local PPGN, achieving subquadratic sampling and extrapolation to unseen graph sizes.
Problem
Graph generative models struggle to scale beyond a few hundred nodes because modeling edges over all node pairs costs at least quadratic time and one-shot models fail to capture global and local structure together; they also do not generalize to unseen graph sizes.
Approach
Learn to invert multilevel graph coarsening: a diffusion model repeatedly expands each node into a small cluster and refines edges locally, so generation builds global structure first and then local details, avoiding joint modeling over all node pairs. Uses spectrum-guided random coarsening sequences for training and a Local PPGN layer that is expressive on locally dense expansions but linear in e
Key results
- Achieves the highest V.U.N. on planar graphs (95.0) and tree graphs (100), outperforming DiGress (77.5 and 90.0 respectively).
- On point clouds with up to 5037 nodes, achieves MMD ratio 7.0 versus 133-143 for EDGE/BwR and OOM for several baselines; best on proteins with ratio 5.9.
- Only method among those evaluated that preserves validity and uniqueness when extrapolating to unseen node counts (48-144 nodes) on planar and tree datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use iterative local expansion instead of generating the full graph in one shot | Ours · Planar graphs | V.U.N.: 67.5 -> 95.0 | Helped |
| Use iterative local expansion instead of generating the full graph in one shot | Ours · Stochastic Block Model | V.U.N.: 75.0 -> 45.0 | Hurt |
| Use iterative local expansion instead of generating the full graph in one shot | Ours · Tree graphs | V.U.N.: 82.5 -> 100 | Helped |
| Replace Local Variation cost with random contraction-set costs (ablation) | Ours · Planar graphs | Ratio: 2.1 -> 3.9 | Hurt |
| Replace Local Variation cost with random contraction-set costs (ablation) | Ours · Planar graphs | V.U.N.: 95.0 -> 85.0 | Hurt |
| Replace Local Variation cost with random contraction-set costs (ablation) | Ours · Tree graphs | Ratio: 4.0 -> 6.2 | Hurt |
| Replace Local Variation cost with random contraction-set costs (ablation) | Ours · Tree graphs | V.U.N.: 100 -> 100 | No clear effect |
| Replace Local Variation cost with random contraction-set costs (ablation) | Ours · Proteins | Ratio: 5.9 -> 8.2 | Hurt |
Surprising findings
- On the SBM dataset the method underperforms DiGress and the one-shot variant (V.U.N. 45.0 vs 75.0 one-shot), which the authors attribute to SBM randomness.
Limitations
- Performs worse than DiGress on SBM graphs and on the MMD ratio for SBM.
- Several baselines (GRAN, DiGress, one-shot variant) fail on larger graphs, so extrapolation comparisons cannot isolate inability to interpolate from inability to generate large graphs.
- Stochastic coarsening and perturbed expansion add randomness; deterministic expansion limited to edge contraction with max expansion size two.
Experimental setup
Datasets: planar graphs stochastic block model graphs tree graphs proteins point clouds
Benchmarks: planar graphs stochastic block model graphs tree graphs proteins point clouds
Metrics: MMD degree MMD clustering MMD orbit MMD spectrum MMD wavelet MMD ratio to training set validity uniqueness novelty V.U.N.
Baselines: GraphRNN GRAN SPECTRE DiGress EDGE BwR (EDP-GNN) BiGG GraphGen
Builds on: EDM (elucidating diffusion models) PPGN SignNet GRAN DiGress
Closest papers by meaning
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.90)
- Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.89)
- Generating Graphs via Spectral Diffusion (ICLR 2025 · similarity 0.89)
- Generative Graph Pattern Machine (NeurIPS 2025 · similarity 0.88)
- Geometric Generative Modeling with Noise-Conditioned Graph Networks (ICML 2025 · similarity 0.88)
- HiGen: Hierarchical Graph Generative Networks (ICLR 2024 · similarity 0.88)
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.