# Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- Placed in Flow matching, time series and science, one of 14 directions in Diffusion models.
- Builds on 41 of its 61 references that are in the map.
- First posted on arXiv 6 May 2023.

## Placed in

- Diffusion models / [Flow matching, time series and science](https://mlsanity.com/diffusion/flow-matching-time-series-and-science/)

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [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)
- [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)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/1702.03118/) (2017)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models](https://mlsanity.com/paper/1811.12823/) (2018)
- [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)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [MoFlow: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/2006.10137/) (2020)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [GraphNVP: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/1905.11600/) (2019)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Graph Normalizing Flows](https://mlsanity.com/paper/1905.13177/) (2019)
- [Diffusion Models for Graphs Benefit From Discrete State Spaces](https://mlsanity.com/paper/2210.01549/) (2022)
- [Scalable Deep Generative Modeling for Sparse Graphs](https://mlsanity.com/paper/2006.15502/) (2020)

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

- [Discrete-state Continuous-time Diffusion for Graph Generation](https://mlsanity.com/paper/2405.11416/) (2024)
- [Enhancing Deep Reinforcement Learning: A Tutorial on Generative Diffusion Models in Network Optimization](https://mlsanity.com/paper/2308.05384/) (2023)
- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [DiffMS: Diffusion Generation of Molecules Conditioned on Mass Spectra](https://mlsanity.com/paper/2502.09571/) (2025)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Optimizing OOD Detection in Molecular Graphs: A Novel Approach with Diffusion Models](https://mlsanity.com/paper/2404.15625/) (2024)
- [Hyperbolic Geometric Latent Diffusion Model for Graph Generation](https://mlsanity.com/paper/2405.03188/) (2024)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [GraphMaker: Can Diffusion Models Generate Large Attributed Graphs?](https://mlsanity.com/paper/2310.13833/) (2023)
- [Graph Generative Pre-trained Transformer](https://mlsanity.com/paper/2501.01073/) (2025)
- [MADGEN: Mass-Spec attends to De Novo Molecular generation](https://mlsanity.com/paper/2501.01950/) (2025)
- [Advancing Graph Generation through Beta Diffusion](https://mlsanity.com/paper/2406.09357/) (2024)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [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)
- [Neural Graph Generator: Feature-Conditioned Graph Generation using Latent Diffusion Models](https://mlsanity.com/paper/2403.01535/) (2024)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation](https://mlsanity.com/paper/2411.02322/) (2024)
- [FragFM: Hierarchical Framework for Efficient Molecule Generation via Fragment-Level Discrete Flow Matching](https://mlsanity.com/paper/2502.15805/) (2025)
- [Rethinking Diffusion Models with Symmetries through Canonicalization with Applications to Molecular Graph Generation](https://mlsanity.com/paper/2602.15022/) (2026)
- [HiGen: Hierarchical Graph Generative Networks](https://mlsanity.com/paper/2305.19337/) (2023)
- [Reviving Life on the Edge: Joint Score-Based Graph Generation of Rich Edge Attributes](https://mlsanity.com/paper/2402.04046/) (2024)
- [FairWire: Fair Graph Generation](https://mlsanity.com/paper/2402.04383/) (2024)
- [How Fair is Your Diffusion Recommender Model?](https://mlsanity.com/paper/2409.04339/) (2024)
- [Graph Guided Diffusion: Unified Guidance for Conditional Graph Generation](https://mlsanity.com/paper/2505.19685/) (2025)
- [PowerGrow: Feasible Co-Growth of Structures and Dynamics for Power Grid Synthesis](https://mlsanity.com/paper/2509.12212/) (2025)
- [RADAR: Redundancy-Aware Diffusion for Multi-Agent Communication Structure Generation](https://mlsanity.com/paper/2605.09907/) (2026)

## Abstract (arXiv)

Diffusion-based generative graph models have been proven effective in generating high-quality small graphs. However, they need to be more scalable for generating large graphs containing thousands of nodes desiring graph statistics. In this work, we propose EDGE, a new diffusion-based generative graph model that addresses generative tasks with large graphs. To improve computation efficiency, we encourage graph sparsity by using a discrete diffusion process that randomly removes edges at each time step and finally obtains an empty graph. EDGE only focuses on a portion of nodes in the graph at each denoising step. It makes much fewer edge predictions than previous diffusion-based models. Moreover, EDGE admits explicitly modeling the node degrees of the graphs, further improving the model performance. The empirical study shows that EDGE is much more efficient than competing methods and can generate large graphs with thousands of nodes. It also outperforms baseline models in generation quality: graphs generated by our approach have more similar graph statistics to those of the training graphs.