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.
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 \emph{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.
Discrete graph generation has emerged as a powerful paradigm for modeling graph-structured data, yet state of the art models often rely on Graph Transformers or higher order architectures. We revisit this design assumption by introducing GenGNN, a modular message passing backbone for graph generation. GenGNN enables powerful generation by persisting edge fields through latent refinement of coupled node edge graph states, all without requiring global attention. Diffusion models integrating GenGNN achieve over 90 percent validity on standard benchmark datasets, performing within margins of Graph Transformer backbones and achieving up to 2x or even 5x faster inference. Systematic ablations isolate how GenGNN is resilient to oversmoothing during generative denoising, indicating each GenGNN component is necessary for downstream generation quality. Finally, representation-space analysis suggests GenGNN learns functionally similar representations to more theoretically-expressive architectures; even at deeper layers. As such, GenGNN uplifts local message-passing to challenge prevailing assumptions that performant discrete graph generation requires global attention or higher-order representations. Source Code Available Here
Jay Revolinsky, Harry Shomer, Jiliang Tang
Michigan State University East Lansing, Michigan, USA · University of Texas - Arlington Arlington, Texas, USA
Diffusion models generalize well in practice. Paradoxically, an optimal diffusion model fully memorizes the training data and therefore fails to generalize, raising the question of what induces generalization in a real diffusion model. We show that diffusion models progressively overfit the denoising training objective, creating a generalization gap between validation and training performance at intermediate noise levels. In a fully analytic 2D toy model with a controlled denoising error, we trace this gap to the interaction between model error and the density of the data distribution's support. The optimal denoising flow field localizes sharply around individual training points, whereas model error suppresses exact recall of training points, yielding a smooth, generalizing flow field. Finally, we examine how training-time overfitting manifests along inference trajectories. We find that predictions made from intermediate trajectory states occupy a distinct feature-space regime from predictions made from noised training and validation images. As training progresses and model size increases, these predictions develop greater relative affinity to the training data, despite the absolute similarity to the validation data not decreasing. Together, these findings show that the denoising objective and inference trajectories express structural memorization differently.