# DiGress: Discrete Denoising diffusion for graph generation

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

## Key facts

- Cited by 520 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 48 of its 62 references that are in the map.
- First posted on arXiv 29 Sep 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, 30 of 48)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [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)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Video Diffusion Models](https://mlsanity.com/paper/2204.03458/) (2022)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [RePaint: Inpainting using Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2201.09865/) (2022)
- [Variational Diffusion Models](https://mlsanity.com/paper/2107.00630/) (2021)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Equivariant Diffusion for Molecule Generation in 3D](https://mlsanity.com/paper/2203.17003/) (2022)
- [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)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation](https://mlsanity.com/paper/2203.02923/) (2022)
- [A Continuous Time Framework for Discrete Denoising Models](https://mlsanity.com/paper/2205.14987/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [GuacaMol: Benchmarking Models for De Novo Molecular Design](https://mlsanity.com/paper/1811.09621/) (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)
- [Torsional Diffusion for Molecular Conformer Generation](https://mlsanity.com/paper/2206.01729/) (2022)
- [Diffsound: Discrete Diffusion Model for Text-to-sound Generation](https://mlsanity.com/paper/2207.09983/) (2022)
- [Equivariant Flows: Exact Likelihood Generative Learning for Symmetric Densities](https://mlsanity.com/paper/2006.02425/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)

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

- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024)
- [Self-Consuming Generative Models Go MAD](https://mlsanity.com/paper/2307.01850/) (2023)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [Protein Design with Guided Discrete Diffusion](https://mlsanity.com/paper/2305.20009/) (2023)
- [Simple Guidance Mechanisms for Discrete Diffusion Models](https://mlsanity.com/paper/2412.10193/) (2024)
- [A Reparameterized Discrete Diffusion Model for Text Generation](https://mlsanity.com/paper/2302.05737/) (2023)
- [Crystal Structure Prediction by Joint Equivariant Diffusion](https://mlsanity.com/paper/2309.04475/) (2023)
- [Derivative-Free Guidance in Continuous and Discrete Diffusion Models with Soft Value-Based Decoding](https://mlsanity.com/paper/2408.08252/) (2024)
- [Unlocking Guidance for Discrete State-Space Diffusion and Flow Models](https://mlsanity.com/paper/2406.01572/) (2024)
- [On Memorization in Diffusion Models](https://mlsanity.com/paper/2310.02664/) (2023)
- [Equivariant 3D-Conditional Diffusion Models for Molecular Linker Design](https://mlsanity.com/paper/2210.05274/) (2022)
- [InstructScene: Instruction-Driven 3D Indoor Scene Synthesis with Semantic Graph Prior](https://mlsanity.com/paper/2402.04717/) (2024)
- [Dirichlet Flow Matching with Applications to DNA Sequence Design](https://mlsanity.com/paper/2402.05841/) (2024)
- [MiDi: Mixed Graph and 3D Denoising Diffusion for Molecule Generation](https://mlsanity.com/paper/2302.09048/) (2023)
- [DecompDiff: Diffusion Models with Decomposed Priors for Structure-Based Drug Design](https://mlsanity.com/paper/2403.07902/) (2024)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [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)
- [Variational Flow Matching for Graph Generation](https://mlsanity.com/paper/2406.04843/) (2024)
- [Diffusion-Based 3D Human Pose Estimation with Multi-Hypothesis Aggregation](https://mlsanity.com/paper/2303.11579/) (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)
- [Diffusion Models for Graphs Benefit From Discrete State Spaces](https://mlsanity.com/paper/2210.01549/) (2022)
- [Many Heads Are Better Than One: Improved Scientific Idea Generation by A LLM-Based Multi-Agent System](https://mlsanity.com/paper/2410.09403/) (2024)
- [EchoScene: Indoor Scene Generation via Information Echo over Scene Graph Diffusion](https://mlsanity.com/paper/2405.00915/) (2024)
- [PolyDiff: Generating 3D Polygonal Meshes with Diffusion Models](https://mlsanity.com/paper/2312.11417/) (2023)

## Abstract (arXiv)

This work introduces DiGress, a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. Our model utilizes a discrete diffusion process that progressively edits graphs with noise, through the process of adding or removing edges and changing the categories. A graph transformer network is trained to revert this process, simplifying the problem of distribution learning over graphs into a sequence of node and edge classification tasks. We further improve sample quality by introducing a Markovian noise model that preserves the marginal distribution of node and edge types during diffusion, and by incorporating auxiliary graph-theoretic features. A procedure for conditioning the generation on graph-level features is also proposed. DiGress achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement on a planar graph dataset. It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules without the use of molecule-specific representations.