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.
Figures & tables
Figure 1: Sample-level metrics report a well-generalizing model. Clustering coefficient NMAE (lower is better) improves throughout training while WL kernel similarity remains flat, suggesting the samples acquire the correct community structure without reproducing the training graph.
Figure 2: We measure the ability of the denoiser to recover the training graph vs. test graph and find the model exhibits a training-data bias where it can recover the training graph perfectly.
Figure 3: Analyzing the edge recall through a U-turn probe allows us to detect memorization.
Figure 4: Train and test loss with the structure fraction S(τ) across node sizes. Community structure emerges at τstruct well after the onset of overfitting at τcliff .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Edge recall across node sizes.
n=64
n=128
n=256
n=512
τgen (argmin held-out loss)
500
1300
700
—
τmem (recall onset)
≤99
2799
3199
5599
τstruct (structure in samples)
1900
3100
3600
7775
τstruct−τmem
≥+1801
+301
+401
+2176
Appendix
Table 1: Memorization onset happens before the emergence of community structure.
n
ΔmaxRecall
ΔmaxF1
64
0.30±0.02
0.30±0.02
128
0.58±0.01
0.58±0.01
256
0.62±0.01
0.60±0.00
512
0.48±0.01
0.47±0.00
Appendix
Table 2:
n
pin
pout
Mean degree
Edges (intra/inter)
64
0.4995
0.0161
17.00
544 (519/25)
128
0.2458
0.0081
16.19
1036 (1000/36)
256
0.1219
0.0040
16.43
2103 (2045/58)
512
0.0607
0.0020
16.12
4126 (4014/112)
Appendix
Table 3: SBM parameters for data generation.
Parameter
Value
Diffusion
Diffusion steps T
256
Noise schedule
Cosine
Forward process
Absorbing (edge deletion)
Architecture
Backbone
Degree-guided transformer GNN
Appendix
Table 4: Training hyperparameters for the single-graph experiments. All settings are shared across node sizes except where noted.