# Efficient and Scalable Graph Generation through Iterative Local Expansion

arXiv: https://arxiv.org/abs/2312.11529 · HTML: https://mlsanity.com/paper/2312.11529/

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 69 references that are in the map.
- First posted on arXiv 14 Dec 2023.

## Builds on (most cited first, 30 of 46)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Elucidating the Design Space of Diffusion-Based Generative Models](https://mlsanity.com/paper/2206.00364/) (2022)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Vector Quantized Diffusion Model for Text-to-Image Synthesis](https://mlsanity.com/paper/2111.14822/) (2021)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [AudioLM: a Language Modeling Approach to Audio Generation](https://mlsanity.com/paper/2209.03143/) (2022)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [MusicLM: Generating Music From Text](https://mlsanity.com/paper/2301.11325/) (2023)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning](https://mlsanity.com/paper/2208.04202/) (2022)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Graphite: Iterative Generative Modeling of Graphs](https://mlsanity.com/paper/1803.10459/) (2018)
- [Graph Normalizing Flows](https://mlsanity.com/paper/1905.13177/) (2019)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [MiDi: Mixed Graph and 3D Denoising Diffusion for Molecule Generation](https://mlsanity.com/paper/2302.09048/) (2023)
- [Diffusion Visual Counterfactual Explanations](https://mlsanity.com/paper/2210.11841/) (2022)

## Built on by (most cited first, 30 of 36)

- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [Graph Generative Pre-trained Transformer](https://mlsanity.com/paper/2501.01073/) (2025)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [LLM-Based Multi-Agent Systems are Scalable Graph Generative Models](https://mlsanity.com/paper/2410.09824/) (2024)
- [Improving Molecular Graph Generation with Flow Matching and Optimal Transport](https://mlsanity.com/paper/2411.05676/) (2024)
- [Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation](https://mlsanity.com/paper/2503.21592/) (2025)
- [HYGENE: A Diffusion-based Hypergraph Generation Method](https://mlsanity.com/paper/2408.16457/) (2024)
- [Bures-Wasserstein Flow Matching for Graph Generation](https://mlsanity.com/paper/2506.14020/) (2025)
- [HOG-Diff: Higher-Order Guided Diffusion for Graph Generation](https://mlsanity.com/paper/2502.04308/) (2025)
- [Leveraging LLM-based agents for social science research: insights from citation network simulations](https://mlsanity.com/paper/2511.03758/) (2025)
- [Next Level Message-Passing with Hierarchical Support Graphs](https://mlsanity.com/paper/2406.15852/) (2024)
- [Graph-GRPO: Training Graph Flow Models with Reinforcement Learning](https://mlsanity.com/paper/2603.10395/) (2026)
- [Diffusion-Free Graph Generation with Next-Scale Prediction](https://mlsanity.com/paper/2503.23612/) (2025)
- [GGBall: Graph Generative Model on Poincar'e Ball](https://mlsanity.com/paper/2506.07198/) (2025)
- [Generating Directed Graphs with Dual Attention and Asymmetric Encoding](https://mlsanity.com/paper/2506.16404/) (2025)
- [PolyGraph Discrepancy: a classifier-based metric for graph generation](https://mlsanity.com/paper/2510.06122/) (2025)
- [Flowette: Flow Matching with Graphette Priors for Graph Generation](https://mlsanity.com/paper/2602.23566/) (2026)
- [Diffusion-based Graph Generative Methods](https://mlsanity.com/paper/2401.15617/) (2024)
- [EDGE-Rec: Efficient and Data-Guided Edge Diffusion For Recommender Systems Graphs](https://mlsanity.com/paper/2409.14689/) (2024)
- [Fast Graph Generation via Autoregressive Noisy Filtration Modeling](https://mlsanity.com/paper/2502.02415/) (2025)
- [Satellites Reveal Mobility: A Commuting Origin-destination Flow Generator for Global Cities](https://mlsanity.com/paper/2505.15870/) (2025)
- [LGDC: Latent Graph Diffusion via Spectrum-Preserving Coarsening](https://mlsanity.com/paper/2512.01190/) (2025)
- [Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generation](https://mlsanity.com/paper/2603.28572/) (2026)
- [Hierarchical Discrete Flow Matching for Graph Generation](https://mlsanity.com/paper/2604.00236/) (2026)
- [Variational Bayesian Flow Network for Graph Generation](https://mlsanity.com/paper/2601.22524/) (2026)
- [Feature-Aware (Hyper)graph Generation via Next-Scale Prediction](https://mlsanity.com/paper/2506.01467/) (2025)
- [Discrete Bayesian Sample Inference for Graph Generation](https://mlsanity.com/paper/2511.03015/) (2025)
- [Balancing Symmetry and Efficiency in Graph Flow Matching](https://mlsanity.com/paper/2602.18084/) (2026)
- [Local Message-Passing for Discrete Graph Generation](https://mlsanity.com/paper/2603.08825/) (2026)

## Abstract (arXiv)

In the realm of generative models for graphs, extensive research has been conducted. However, most existing methods struggle with large graphs due to the complexity of representing the entire joint distribution across all node pairs and capturing both global and local graph structures simultaneously. To overcome these issues, we introduce a method that generates a graph by progressively expanding a single node to a target graph. In each step, nodes and edges are added in a localized manner through denoising diffusion, building first the global structure, and then refining the local details. The local generation avoids modeling the entire joint distribution over all node pairs, achieving substantial computational savings with subquadratic runtime relative to node count while maintaining high expressivity through multiscale generation. Our experiments show that our model achieves state-of-the-art performance on well-established benchmark datasets while successfully scaling to graphs with at least 5000 nodes. Our method is also the first to successfully extrapolate to graphs outside of the training distribution, showcasing a much better generalization capability over existing methods.