# Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 22 of 22)

- [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)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (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)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [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)
- [Scalable Deep Generative Modeling for Sparse Graphs](https://mlsanity.com/paper/2006.15502/) (2020)
- [On Evaluation Metrics for Graph Generative Models](https://mlsanity.com/paper/2201.09871/) (2022)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [Demystifying Fraudulent Transactions and Illicit Nodes in the Bitcoin Network for Financial Forensics](https://mlsanity.com/paper/2306.06108/) (2023)
- [GraphMaker: Can Diffusion Models Generate Large Attributed Graphs?](https://mlsanity.com/paper/2310.13833/) (2023)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [Unified Guidance for Geometry-Conditioned Molecular Generation](https://mlsanity.com/paper/2501.02526/) (2025)
- [HiGen: Hierarchical Graph Generative Networks](https://mlsanity.com/paper/2305.19337/) (2023)
- [Graph Generation with K2-trees](https://mlsanity.com/paper/2305.19125/) (2023)
- [Random Walk Diffusion for Efficient Large-Scale Graph Generation](https://mlsanity.com/paper/2408.04461/) (2024)
- [Scalable Generative Modeling of Weighted Graphs](https://mlsanity.com/paper/2507.23111/) (2025)

## Abstract (arXiv)

Synthesizing realistic graphs at scale is vital when the graphs of interest are large and real-world samples are limited or access-sensitive. Diffusion-based generators have recently driven much of the progress, offering high modeling capacity, but most such methods have quadratic computational complexity and are hence restricted to small-scale networks, currently up to 3k nodes. Existing non-quadratic methods remain limited by memorization issues and a trade-off between scalability and generation quality. Our goal is to generate large graphs whose structural statistics --- e.g., degree distribution, clustering, and path length --- faithfully reflect those of real-world sparse graphs, without resorting to memorizing the training data. We introduce a discrete graph diffusion model that restricts training to a structurally motivated subset of node pairs --- observed edges and their wedge non-edges --- reducing training complexity below quadratic in the number of nodes. To keep the noisy graph informative throughout both the forward and reverse trajectories, we design a three-class absorbing forward process governed by a degree-aware, floored cosine noise schedule: unlike a structure-blind schedule that adds noise to every pair identically, ours adapts to each node's degree and never fully erases the graph's structure, keeping the noisy graph informative at every step. Experiments across diverse datasets show that our model consistently ranks among the top methods for structural fidelity against existing discrete diffusion baselines in large graph generation.