# Scalable Deep Generative Modeling for Sparse Graphs

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

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2020.

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

- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [A Complete Survey on Generative AI (AIGC): Is ChatGPT from GPT-4 to GPT-5 All You Need?](https://mlsanity.com/paper/2303.11717/) (2023)
- [Autoregressive Diffusion Model for Graph Generation](https://mlsanity.com/paper/2307.08849/) (2023)
- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [Assemble Your Crew: Automatic Multi-agent Communication Topology Design via Autoregressive Graph Generation](https://mlsanity.com/paper/2507.18224/) (2025)
- [On Evaluation Metrics for Graph Generative Models](https://mlsanity.com/paper/2201.09871/) (2022)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [The Future is not One-dimensional: Complex Event Schema Induction by Graph Modeling for Event Prediction](https://mlsanity.com/paper/2104.06344/) (2021)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [A Survey on Graph Diffusion Models: Generative AI in Science for Molecule, Protein and Material](https://mlsanity.com/paper/2304.01565/) (2023)
- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [Graph Transformer Networks: Learning Meta-path Graphs to Improve GNNs](https://mlsanity.com/paper/2106.06218/) (2021)
- [Multiresolution Equivariant Graph Variational Autoencoder](https://mlsanity.com/paper/2106.00967/) (2021)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [NVDiff: Graph Generation through the Diffusion of Node Vectors](https://mlsanity.com/paper/2211.10794/) (2022)
- [Metric Space Magnitude for Evaluating the Diversity of Latent Representations](https://mlsanity.com/paper/2311.16054/) (2023)
- [Graph Generative Pre-trained Transformer](https://mlsanity.com/paper/2501.01073/) (2025)
- [Improving Graph Generation by Restricting Graph Bandwidth](https://mlsanity.com/paper/2301.10857/) (2023)
- [A Simple and Scalable Representation for Graph Generation](https://mlsanity.com/paper/2312.02230/) (2023)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [Continual Learning on Graphs: A Survey](https://mlsanity.com/paper/2402.06330/) (2024)
- [LLM-Based Multi-Agent Systems are Scalable Graph Generative Models](https://mlsanity.com/paper/2410.09824/) (2024)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Node-Aligned Graph-to-Graph (NAG2G): Elevating Template-Free Deep Learning Approaches in Single-Step Retrosynthesis](https://mlsanity.com/paper/2309.15798/) (2023)
- [D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion](https://mlsanity.com/paper/2310.19321/) (2023)

## Abstract (arXiv)

Learning graph generative models is a challenging task for deep learning and has wide applicability to a range of domains like chemistry, biology and social science. However current deep neural methods suffer from limited scalability: for a graph with n nodes and m edges, existing deep neural methods require Omega(n2) complexity by building up the adjacency matrix. On the other hand, many real world graphs are actually sparse in the sense that mll n2. Based on this, we develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix, and importantly reduces the graph generation time complexity to O((n + m)log n). Furthermore, during training this autoregressive model can be parallelized with O(log n) synchronization stages, which makes it much more efficient than other autoregressive models that require Omega(n). Experiments on several benchmarks show that the proposed approach not only scales to orders of magnitude larger graphs than previously possible with deep autoregressive graph generative models, but also yields better graph generation quality.