# Diffusion Models for Graphs Benefit From Discrete State Spaces

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

## Key facts

- Cited by 73 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 26 of its 35 references that are in the map.
- First posted on arXiv 4 Oct 2022.

## 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, 26 of 26)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (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)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [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)
- [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)
- [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)
- [Autoregressive Diffusion Models](https://mlsanity.com/paper/2110.02037/) (2021)
- [ImageBART: Bidirectional Context with Multinomial Diffusion for Autoregressive Image Synthesis](https://mlsanity.com/paper/2108.08827/) (2021)
- [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)
- [Unleashing Transformers: Parallel Token Prediction with Discrete Absorbing Diffusion for Fast High-Resolution Image Generation from Vector-Quantized Codes](https://mlsanity.com/paper/2111.12701/) (2021)
- [Top-N: Equivariant set and graph generation without exchangeability](https://mlsanity.com/paper/2110.02096/) (2021)
- [Graphons, mergeons, and so on!](https://mlsanity.com/paper/1607.01718/) (2016)

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

- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [MiDi: Mixed Graph and 3D Denoising Diffusion for Molecule Generation](https://mlsanity.com/paper/2302.09048/) (2023)
- [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)
- [Generative Diffusion Models on Graphs: Methods and Applications](https://mlsanity.com/paper/2302.02591/) (2023)
- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [Discrete-state Continuous-time Diffusion for Graph Generation](https://mlsanity.com/paper/2405.11416/) (2024)
- [Position: Topological Deep Learning is the New Frontier for Relational Learning](https://mlsanity.com/paper/2402.08871/) (2024)
- [MolDiff: Addressing the Atom-Bond Inconsistency Problem in 3D Molecule Diffusion Generation](https://mlsanity.com/paper/2305.07508/) (2023)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [AbDiffuser: Full-Atom Generation of in vitro Functioning Antibodies](https://mlsanity.com/paper/2308.05027/) (2023)
- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [Diffusion Models in textitDe Novo Drug Design](https://mlsanity.com/paper/2406.08511/) (2024)
- [Unifying Generation and Prediction on Graphs with Latent Graph Diffusion](https://mlsanity.com/paper/2402.02518/) (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)
- [Directional diffusion models for graph representation learning](https://mlsanity.com/paper/2306.13210/) (2023)
- [SaGess: Sampling Graph Denoising Diffusion Model for Scalable Graph Generation](https://mlsanity.com/paper/2306.16827/) (2023)
- [Advancing Graph Generation through Beta Diffusion](https://mlsanity.com/paper/2406.09357/) (2024)
- [Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation](https://mlsanity.com/paper/2503.21592/) (2025)
- [Complexity-aware Large Scale Origin-Destination Network Generation via Diffusion Model](https://mlsanity.com/paper/2306.04873/) (2023)
- [D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion](https://mlsanity.com/paper/2310.19321/) (2023)
- [A Directional Diffusion Graph Transformer for Recommendation](https://mlsanity.com/paper/2404.03326/) (2024)
- [3D Vessel Graph Generation Using Denoising Diffusion](https://mlsanity.com/paper/2407.05842/) (2024)
- [Bures-Wasserstein Flow Matching for Graph Generation](https://mlsanity.com/paper/2506.14020/) (2025)
- [Generating Graphs via Spectral Diffusion](https://mlsanity.com/paper/2402.18974/) (2024)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [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)

## Abstract (arXiv)

Denoising diffusion probabilistic models and score-matching models have proven to be very powerful for generative tasks. While these approaches have also been applied to the generation of discrete graphs, they have, so far, relied on continuous Gaussian perturbations. Instead, in this work, we suggest using discrete noise for the forward Markov process. This ensures that in every intermediate step the graph remains discrete. Compared to the previous approach, our experimental results on four datasets and multiple architectures show that using a discrete noising process results in higher quality generated samples indicated with an average MMDs reduced by a factor of 1.5. Furthermore, the number of denoising steps is reduced from 1000 to 32 steps, leading to a 30 times faster sampling procedure.