# Your Discrete Graph Diffusion Model is Secretly Memorizing

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

## 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 31 of its 34 references that are in the map.
- First posted on arXiv 9 Oct 2026.

## Placed in

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

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [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)
- [Extracting Training Data from Diffusion Models](https://mlsanity.com/paper/2301.13188/) (2023)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Diffusion Art or Digital Forgery? Investigating Data Replication in Diffusion Models](https://mlsanity.com/paper/2212.03860/) (2022)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Discrete Flow Matching](https://mlsanity.com/paper/2407.15595/) (2024)
- [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)
- [Generalization in diffusion models arises from geometry-adaptive harmonic representations](https://mlsanity.com/paper/2310.02557/) (2023)
- [Dynamical Regimes of Diffusion Models](https://mlsanity.com/paper/2402.18491/) (2024)
- [DeFoG: Discrete Flow Matching for Graph Generation](https://mlsanity.com/paper/2410.04263/) (2024)
- [Why Diffusion Models Don't Memorize: The Role of Implicit Dynamical Regularization in Training](https://mlsanity.com/paper/2505.17638/) (2025)
- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [Diffusion Models for Graphs Benefit From Discrete State Spaces](https://mlsanity.com/paper/2210.01549/) (2022)
- [The statistical thermodynamics of generative diffusion models: Phase transitions, symmetry breaking and critical instability](https://mlsanity.com/paper/2310.17467/) (2023)
- [SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation](https://mlsanity.com/paper/2307.01646/) (2023)
- [A Survey of Diffusion Based Image Generation Models: Issues and Their Solutions](https://mlsanity.com/paper/2308.13142/) (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)
- [Improving Equivariant Networks with Probabilistic Symmetry Breaking](https://mlsanity.com/paper/2503.21985/) (2025)
- [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)
- [Equivariant Denoisers Cannot Copy Graphs: Align Your Graph Diffusion Models](https://mlsanity.com/paper/2405.17656/) (2024)
- [Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis](https://mlsanity.com/paper/2507.03756/) (2025)
- [Biased Generalization in Diffusion Models](https://mlsanity.com/paper/2603.03469/) (2026)
- [On the Role of Edge Dependency in Graph Generative Models](https://mlsanity.com/paper/2312.03691/) (2023)

## Abstract (arXiv)

Discrete graph diffusion models (GDMs) corrupt the graph structure by adding noise independently to nodes and edges under a Markovian noise model. In the unconditional setting without node features, an equivariant denoiser trained on a single graph is able to generate novel graphs and sample-level metrics such as edge overlap and WL kernel similarity find no evidence of memorization. In this work, we challenge this view and show for the first time that graph diffusion models indeed exhibit memorization. Analyzing the reverse diffusion trajectories of GDMs trained on two-block stochastic block models (SBMs), we find a strong train-data bias: the model recovers a corrupted training graph almost perfectly compared to a held-out test graph. We term this conditional memorization, as it surfaces only when the reverse trajectory is conditioned on a corrupted training graph and is not apparent during inference. It coincides with a growing generalization gap, where the training loss improves as the loss on held-out graphs degrades, and it cannot be mitigated by early stopping. The onset of memorization always precedes the emergence of community structure in the generated graphs, thus every checkpoint earlier produces structureless graphs. This behavior holds across all node sizes we test.