# Sparse Training of Discrete Diffusion Models for Graph Generation

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

## Key facts

- Cited by 27 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 43 of its 56 references that are in the map.
- First posted on arXiv 3 Nov 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 43)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Imagen Video: High Definition Video Generation with Diffusion Models](https://mlsanity.com/paper/2210.02303/) (2022)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [DiffWave: A Versatile Diffusion Model for Audio Synthesis](https://mlsanity.com/paper/2009.09761/) (2020)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [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)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [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)
- [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)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [Constrained Graph Variational Autoencoders for Molecule Design](https://mlsanity.com/paper/1805.09076/) (2018)

## Built on by (most cited first, 27 of 27)

- [Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design](https://mlsanity.com/paper/2402.04997/) (2024)
- [Unlocking Guidance for Discrete State-Space Diffusion and Flow Models](https://mlsanity.com/paper/2406.01572/) (2024)
- [How Discrete and Continuous Diffusion Meet: Comprehensive Analysis of Discrete Diffusion Models via a Stochastic Integral Framework](https://mlsanity.com/paper/2410.03601/) (2024)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation](https://mlsanity.com/paper/2503.21592/) (2025)
- [GLAD: Improving Latent Graph Generative Modeling with Simple Quantization](https://mlsanity.com/paper/2403.16883/) (2024)
- [FreeScene: Mixed Graph Diffusion for 3D Scene Synthesis from Free Prompts](https://mlsanity.com/paper/2506.02781/) (2025)
- [FragFM: Hierarchical Framework for Efficient Molecule Generation via Fragment-Level Discrete Flow Matching](https://mlsanity.com/paper/2502.15805/) (2025)
- [TFG-Flow: Training-free Guidance in Multimodal Generative Flow](https://mlsanity.com/paper/2501.14216/) (2025)
- [Discrete State Diffusion Models: A Sample Complexity Perspective](https://mlsanity.com/paper/2510.10854/) (2025)
- [Principled Latent Diffusion for Graphs via Laplacian Autoencoders](https://mlsanity.com/paper/2601.13780/) (2026)
- [Scalable Generative Modeling of Weighted Graphs](https://mlsanity.com/paper/2507.23111/) (2025)
- [Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generation](https://mlsanity.com/paper/2603.28572/) (2026)
- [Hierarchical Discrete Flow Matching for Graph Generation](https://mlsanity.com/paper/2604.00236/) (2026)
- [GraphRCG: Self-Conditioned Graph Generation](https://mlsanity.com/paper/2403.01071/) (2024)
- [Heterogeneous Graph Generation: A Hierarchical Approach using Node Feature Pooling](https://mlsanity.com/paper/2410.11972/) (2024)
- [A collaborative constrained graph diffusion model for the generation of realistic synthetic molecules](https://mlsanity.com/paper/2505.16365/) (2025)
- [SynCircuit: Automated Generation of New Synthetic RTL Circuits Can Enable Big Data in Circuits](https://mlsanity.com/paper/2509.00071/) (2025)
- [CoPHo: Classifier-guided Conditional Topology Generation with Persistent Homology](https://mlsanity.com/paper/2512.19736/) (2025)
- [Local Message-Passing for Discrete Graph Generation](https://mlsanity.com/paper/2603.08825/) (2026)
- [DBMol: Design of High-Affinity, Target-Specific Small Molecules through Structure Prediction Models](https://mlsanity.com/paper/2607.19237/) (2026)
- [Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index](https://mlsanity.com/paper/2609.26199/) (2026)
- [From Graphs to Feeders: Constraint-Guided Diffusion for Rule-Compliant Feeder Generation](https://mlsanity.com/paper/2609.29879/) (2026)
- [Graph Representation via Elements of Discrete Morse and Cobordism Theories](https://mlsanity.com/paper/2610.01937/) (2026)
- [Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction](https://mlsanity.com/paper/2610.04056/) (2026)

## Abstract (arXiv)

Generative graph models struggle to scale due to the need to predict the existence or type of edges between all node pairs. To address the resulting quadratic complexity, existing scalable models often impose restrictive assumptions such as a cluster structure within graphs, thus limiting their applicability. To address this, we introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network, which ensures that space complexity scales linearly with the number of chosen edges. During inference, SparseDiff progressively fills the adjacency matrix with the selected subsets of edges, mirroring the training process. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets, confirming its effectiveness and robustness across varying graph sizes. It also ensures faster convergence, particularly on larger graphs, achieving a fourfold speedup on the large Ego dataset compared to dense models, thereby paving the way for broader applications.