mlsanityData to 14 Oct 2026

Efficient and Scalable Graph Generation through Iterative Local Expansion

arXiv 2312.11529 ↗First posted 14 Dec 2023cs.SI cs.LGcited by 36

Not on the map. Why?

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.

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

46 of 69 references.

References · 46

  1. 2020Denoising Diffusion Probabilistic Modelscited by 21,076
  2. 2020Score-Based Generative Modeling through Stochastic Differential Equationscited by 9,122
  3. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,058
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2022Elucidating the Design Space of Diffusion-Based Generative Modelscited by 3,045
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  7. 2021Structured Denoising Diffusion Models in Discrete State-Spacescited by 1,719
  8. 2019Strategies for Pre-training Graph Neural Networkscited by 971
  9. 2021Vector Quantized Diffusion Model for Text-to-Image Synthesiscited by 774
  10. 2019Graph Neural Networks for Social Recommendationcited by 714
  11. 2020A Generalization of Transformer Networks to Graphscited by 661
  12. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 652
34 more
  1. 2022AudioLM: a Language Modeling Approach to Audio Generationcited by 616
  2. 2021Argmax Flows and Multinomial Diffusion: Learning Categorical Distributionscited by 574
  3. 2023MusicLM: Generating Music From Textcited by 448
  4. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 413
  5. 2018MolGAN: An implicit generative model for small molecular graphscited by 393
  6. 2019Provably Powerful Graph Networkscited by 389
  7. 2018GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoderscited by 383
  8. 2022Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioningcited by 373
  9. 2022Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equationscited by 283
  10. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 270
  11. 2019Efficient Graph Generation with Graph Recurrent Attention Networkscited by 234
  12. 2020Hierarchical Generation of Molecular Graphs using Structural Motifscited by 208
  13. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  14. 2018Graphite: Iterative Generative Modeling of Graphscited by 112
  15. 2019Graph Normalizing Flowscited by 104
  16. 2022SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generatorscited by 99
  17. 2023MiDi: Mixed Graph and 3D Denoising Diffusion for Molecule Generationcited by 98
  18. 2022Diffusion Visual Counterfactual Explanationscited by 96
  19. 2023Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modelingcited by 80
  20. 2020GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generationcited by 66
  21. 2020Scalable Deep Generative Modeling for Sparse Graphscited by 65
  22. 2022Improved Vector Quantized Diffusion Modelscited by 62
  23. 2018Spectrally approximating large graphs with smaller graphscited by 56
  24. 2018Graph Coarsening with Preserved Spectral Propertiescited by 41
  25. 2023UniCATS: A Unified Context-Aware Text-to-Speech Framework with Contextual VQ-Diffusion and Vocodingcited by 37
  26. 2020Learning to Execute Programs with Instruction Pointer Attention Graph Neural Networkscited by 35
  27. 2019A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarseningcited by 31
  28. 2023SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generationcited by 28
  29. 2021MolGrow: A Graph Normalizing Flow for Hierarchical Molecular Generationcited by 22
  30. 2022A Unified Framework for Optimization-Based Graph Coarseningcited by 9
  31. 2022An Unpooling Layer for Graph Generationcited by 3
  32. 2023Size Matters: Large Graph Generation with HiGGscited by 3
  33. 2022Automating Rigid Origami Designcited by 1
  34. 2023Discovering Graph Generation Algorithmscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 8; 2025: 15; 2026: 13.

36 papers.

Sort:

By area:

  1. 2024Cometh: A continuous-time discrete-state graph diffusion modelcited by 32
  2. 2024Generative Modelling of Structurally Constrained Graphscited by 19
  3. 2025Graph Generative Pre-trained Transformercited by 17
  4. 2025Flatten Graphs as Sequences: Transformers are Scalable Graph Generatorscited by 13
  5. 2024LLM-Based Multi-Agent Systems are Scalable Graph Generative Modelscited by 11
  6. 2024Improving Molecular Graph Generation with Flow Matching and Optimal Transportcited by 10
  7. 2025Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generationcited by 10
  8. 2024HYGENE: A Diffusion-based Hypergraph Generation Methodcited by 9
  9. 2025Bures-Wasserstein Flow Matching for Graph Generationcited by 9
  10. 2025HOG-Diff: Higher-Order Guided Diffusion for Graph Generationcited by 8
  11. 2025Leveraging LLM-based agents for social science research: insights from citation network simulationscited by 6
  12. 2024Next Level Message-Passing with Hierarchical Support Graphscited by 5
24 more
  1. 2026Graph-GRPO: Training Graph Flow Models with Reinforcement Learningcited by 5
  2. 2025Diffusion-Free Graph Generation with Next-Scale Predictioncited by 3
  3. 2025GGBall: Graph Generative Model on Poincar'e Ballcited by 3
  4. 2025Generating Directed Graphs with Dual Attention and Asymmetric Encodingcited by 3
  5. 2025PolyGraph Discrepancy: a classifier-based metric for graph generationcited by 3
  6. 2026Flowette: Flow Matching with Graphette Priors for Graph Generationcited by 3
  7. 2024Diffusion-based Graph Generative Methodscited by 2
  8. 2024EDGE-Rec: Efficient and Data-Guided Edge Diffusion For Recommender Systems Graphscited by 2
  9. 2025Fast Graph Generation via Autoregressive Noisy Filtration Modelingcited by 2
  10. 2025Satellites Reveal Mobility: A Commuting Origin-destination Flow Generator for Global Citiescited by 2
  11. 2025LGDC: Latent Graph Diffusion via Spectrum-Preserving Coarseningcited by 2
  12. 2026Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generationcited by 2
  13. 2026Hierarchical Discrete Flow Matching for Graph Generationcited by 2
  14. 2026Variational Bayesian Flow Network for Graph Generationcited by 1
  15. 2025Feature-Aware (Hyper)graph Generation via Next-Scale Predictioncited by 0
  16. 2025Discrete Bayesian Sample Inference for Graph Generationcited by 0
  17. 2026Balancing Symmetry and Efficiency in Graph Flow Matchingcited by 0
  18. 2026Local Message-Passing for Discrete Graph Generationcited by 0
  19. 2026Efficient Synthetic Network Generation via Latent Embedding Reconstructioncited by 0
  20. 2026From topology learning to graph generation: A unifying perspectivecited by 0
  21. 2026Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Indexcited by 0
  22. 2026Autoregressive Frontier Expansion: Growing Trees with Graph Machine Learningcited by 0
  23. 2026Stable Transformers for Graph Generationcited by 0
  24. 2026Constrained Goal-directed Planar Graph Generation with Grammar-based Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction
  2. 2025Generating Large Semi-Synthetic Graphs of Any Size
  3. 2025SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion
  4. 2023Autoregressive Diffusion Model for Graph Generation
  5. 2023Graph Generation with Diffusion Mixture
  6. 2024Unifying Generation and Prediction on Graphs with Latent Graph Diffusion
  7. 2022NVDiff: Graph Generation through the Diffusion of Node Vectors
  8. 2023GraphMaker: Can Diffusion Models Generate Large Attributed Graphs?