Paper deep dive
Your Discrete Graph Diffusion Model is Secretly Memorizing
Adarsh Jamadandi, Nicolas Keriven
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/13/2026, 3:05:52 AM
Summary
This paper challenges the prevailing view that discrete graph diffusion models (GDMs) do not memorize training data when trained on a single graph. The authors demonstrate 'conditional memorization,' where GDMs can almost perfectly recover a corrupted training graph during reverse diffusion if seeded with that specific graph, despite showing no evidence of memorization via standard sample-level metrics like edge overlap or Weisfeiler-Lehman kernel similarity during unconditional generation. This memorization onset precedes the emergence of community structure in generated graphs, making early stopping ineffective for preventing memorization while maintaining structural fidelity.
Entities (8)
Relation Signals (6)
Discrete Graph Diffusion Models → exhibits → Conditional Memorization
confidence 97% · In this work, we challenge this view and show for the first time that graph diffusion models indeed exhibit memorization.
Conditional Memorization → precedes → Community Structure
confidence 96% · The onset of memorization always precedes the emergence of community structure in the generated graphs
Conditional Memorization → isdetectedby → Edge Recall
confidence 95% · Analyzing the reverse diffusion trajectories... we find a strong train-data bias... We term this conditional memorization... surfaces only when the reverse trajectory is conditioned on a corrupted training graph
Conditional Memorization → isnotdetectedby → Weisfeiler-Lehman Kernel Similarity
confidence 93% · sample-level metrics such as edge overlap and WL kernel similarity find no evidence of memorization.
Stochastic Block Models → isusedtotrain → Discrete Graph Diffusion Models
confidence 92% · Analyzing the reverse diffusion trajectories of GDMs trained on two-block stochastic block models (SBMs)
EDGE → isusedin → Discrete Graph Diffusion Models
confidence 90% · We use EDGE [9] as our backbone diffusion model
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2610.13786v1
- Canonical: https://arxiv.org/abs/2610.13786v1
Trouble viewing inline? Open PDF directly →
Full Text
39,798 characters extracted from source content.
Expand or collapse full text
BeNTO: Beyond Next Token Prediction Your Discrete Graph Diffusion Model is Secretly Memorizing Adarsh Jamadandi Affiliation: CNRS, IRISA, Rennes, France Nicolas Keriven Affiliation: adarsh.jamadandi@irisa.fr, nicolas.keriven@cnrs.fr Abstract 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. 1 Introduction Diffusion models [32, 34, 16, 25] have recently emerged as a powerful class of generative models, with major improvements in image [37] and video generation [24]. Motivated by this success, diffusion-based methods have been extended to graph generation. The two most popular approaches are: embedding nodes into a continuous latent space and applying Gaussian diffusion [26, 18, 10], or operating directly in the graph space through a discrete corruption process on edges [3]. The latter approach has been shown to be more appropriate for generating realistic graph structures [15, 35], leading to a growing body of work on both graph diffusion and discrete flow matching [13, 28, 30]. An interesting empirical observation made in [9, 23] is that we can train graph diffusion models on a single graph and still generate novel and diverse graphs without memorizing the training data. This seems counter-intuitive compared to diffusion models applied to images [19, 5] which show dataset size as one of the factors driving generalization. In contrast, the study of memorization in graph diffusion models has received little attention; the question is instead studied under the guise of model expressivity. Recent works such as [21, 22] show that equivariant denoisers cannot copy their training graphs exactly, as this would require breaking the permutation symmetry of the input graphs, which equivariant models by design cannot do. A single training graph has Ω(n!) (n!) graphs in its isomorphism class [36], and an equivariant denoiser cannot reproduce a specific graph and instead produces an average over that class. Further, the sample-level metrics commonly used to assess whether the model has reproduced the training graph such as edge overlap [7, 8], which measures the intersection of exact edge pairs between the training and generated graph, and WL kernel similarity [31], which certifies that two graphs are not isomorphic, both assert no memorization. In this work, we challenge this view and show graph diffusion models do exhibit a form of memorization, which we term conditional memorization: the training graph is recoverable from the reverse dynamics, but only when the trajectory is seeded with a corrupted version of that graph, and is otherwise undetectable during inference. Our contributions can be summarized as follows: 1. We study the learning dynamics of single-graph diffusion models on two-block SBMs at n=64,128,256,512n=\64,128,256,512\ and show the models exhibit conditional memorization, where the model restores a corrupted training graph almost perfectly against a held-out graph, a bias that is invisible in ordinary unconditional generation and surfaces only by probing the reverse diffusion trajectories. 2. We show the minimum held-out loss is a poor proxy for model selection, since memorization onset (τmem _ mem) consistently precedes the emergence of community structure (τstruct _ struct) across all four sizes: the model cannot generate the right structure without first entering the memorization regime, so early stopping cannot separate the two. 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. 2 Sample-level metrics are blind to memorization Data. We generate synthetic graphs with nodes n=64,128,256,512n=\64,128,256,512\ drawn from a symmetric two block stochastic block model (SBM) with block probabilities (pin,pout)(p_in,p_out) chosen at each size to hold the Kesten–Stigum detectability [1] margin fixed at 7.0 and mean degree fixed at ≈16≈ 16 (both well above the detectability threshold of 1), so that graph size is varied independently of task difficulty, details are present in Table 3. We choose this setting as it allows us to control the true generating process and it is easier to see the structure emerging during training. Model setup. We use EDGE [9] as our backbone diffusion model as it is computationally efficient compared to models like DiGress [35] which scales quadratically in the number of nodes. Given an input graph G with adjacency matrix A, the forward corruption involves deleting the edges resulting in an empty graph as a terminal distribution. The reverse process predicts edges between active nodes, let sit=[dit−1≠dit]s^t_i=1[d^t-1_i≠ d^t_i] be a latent variable marking whether node i’s degree changed at step t. With dt=deg(At)d^t= (A^t), the forward process is given by q(A1:T,s1:T∣A0)=∏t=1Tq(At∣At−1)q(st∣At−1,At),q (A^1:T,s^1:T A^0 )= _t=1^Tq (A^t A^t-1 )\,q (s^t A^t-1,A^t ), (1) Marginalizing Equation 1 over intermediate steps gives the absorbing marginal, in which each present edge survives to step t independently with probability α¯t α_t giving rise to q(Aijt=1∣Aij0=1)=α¯tq\! (A^t_ij=1 A^0_ij=1 )= α_t and q(Aijt=1∣Aij0=0)=0q\! (A^t_ij=1 A^0_ij=0 )=0 where α¯t α_t follows a cosine schedule with α¯T=0 α_T=0, so that edges are only ever removed and the terminal state ATA^T is the empty graph. The reverse process is given by pθ(A0:T,s1:T)=p(AT)∏t=1Tpθ(At−1∣At,st)pθ(st∣At),p_θ (A^0:T,s^1:T )=p (A^T ) _t=1^Tp_θ (A^t-1 A^t,s^t )\,p_θ (s^t A^t ), (2) where sts^t in (1) is a deterministic function of At−1,AtA^t-1,A^t, and in (2) the model first predicts which nodes are active and then predicts edges only between them, copying every other pair forward unchanged. The posterior q(st∣dt,d0)q(s^t d^t,d^0) has closed form in terms of the degree and depends on A0A^0 only through d0d^0. Pre-mature generalization. To demonstrate that existing sample level metrics are blind to the memorization, we plot the normalized mean average error (NMAE) of clustering coefficient and the WL kernel similarity for graphs generated by the diffusion model for SBMs with n=64,128,256,512n=\64,128,256,512\ in Figure 1. We can observe that as the training progresses, the NMAE improves consistently (lower is better), indicating the generated graphs are generating graphs with the right community structure and the WL kernel similarity is flat across the training epochs implying, the generated graphs are novel and diverse. Seeing these results one would conclude rather pre-maturely that the model is indeed generalizing. However, as we show in the next section, the model is actually memorizing the training graph, this is indicated as a growing gray band in the plot, interestingly looking at the generated samples, we can observe that the community structure of the graph only appears well inside this memorization regime and before this onset, the generated samples are structureless blobs. 3 Conditional memorization in the reverse diffusion trajectories 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. To show that the graph diffusion models indeed exhibit conditional memorization, we adopt the U-turn experimental setup proposed in [12]which involves analyzing the reverse diffusion trajectories seeded with the training data vs. the test data. Reference law-only denoiser. We begin by defining a law-only denoiser that can serve as an unbiased reference. The reference denoiser knows the generating law and the corruption level, but does not have access to the graph itself. Concretely, it knows the block assignment z and the block probabilities pzizjp_z_iz_j. This gives us a baseline behavior we can expect from a model that is not memorizing a particular training graph. The details of which are present in Appendix D. U-turn probe for edge recall. Let A0A^0 be the edge states of a reference graph, with edge set ℰ(A0)E(A^0) and degree sequence d0=deg(A0)d^0= (A^0). We corrupt A0A^0 up to step t using the forward process: each edge is deleted independently with probability ρ=1−α¯tρ=1- α_t, which we refer to as the destroyed fraction. We then run the reverse process from AtA^t back to t=0t=0 to obtain a reconstruction A~0 A^0. At each reverse step the model first predicts the active nodes sts^t and then predicts edges only between active pairs, with d0d^0 supplied as an auxiliary feature. We measure edge recall as ϕedge-recall=[|ℰ(A~0)∩ℰ(A0)||ℰ(A0)|], _ edge-recall=E\! [ |E( A^0) (A^0) | |E(A^0) | ], (3) estimated as the mean over R independent reverse trajectories. More details are given in Appendix D. Figure 2 plots ϕedge-recall _ edge-recall against ρ for n=256n=256, where ϕ=1φ=1 denotes perfect recall, every corrupted edge restored to its original position. The denoiser exhibits a train-data bias, for instance, for n=256n=256 at ρ=0.60ρ=0.60 it restores 96.9%96.9\% of the corrupted edges of the training graph, against 7.7%7.7\% for a denoiser that has learned only the generating law, and recall on an unseen test graph stays close to that reference throughout. We find this behavior across node sizes although the edge recall rate varies for different node sizes. Figure 3: Analyzing the edge recall through a U-turn probe allows us to detect memorization. We term this conditional memorization: the training instance is recoverable from the model’s reverse dynamics, but only when those dynamics are initialized inside the region of noisy states the model was trained on, a region unconditional sampling does not enter. A similar observation has been noted in contemporaneous work [20], although our analysis suggests a different conclusion, that is, it is not that the models memorize during training and generalize in inference, it is that the sample-level metrics commonly used to assess generalization fail to capture this bias enabling a premature conclusion of the model’s generalization abilities which can have unintended consequences for privacy-preserving deployment [6, 33]. Edge recall for memorization. In Figure 3, we plot edge overlap, WL kernel similarity and edge recall from the U-turn experiment across node sizes. Edge overlap and WL similarity stay flat, which would indicate no memorization. This is an artifact of how sampling works: inference starts from an empty graph and never passes near the training graph, so any sample-level comparison is clean by construction. The U-turn probe queries the model where it was actually trained, and there edge recall climbs steadily, exposing a bias that sample-level metrics cannot see. Community structure emerges only after memorization Garnier-Brun et al. [12] study a phenomenon of biased generalization where the test loss improves while the diffusion model continues to show unusually high ability to recover the training samples. In contrast, we observe that a graph diffusion model progressively overfits the denoising objective, resulting in a wide generalization gap. We measure the community structure of the generated samples by their average clustering coefficient c, normalized against two references: the training graph’s own clustering ctrainc_train, and a floor cER(τ)=d¯gen(τ)/(n−1)c_ER(τ)= d_gen(τ)/(n-1), the clustering expected of an Erdős–Rényi graph of the same mean degree, giving (τ)=cgen(τ)−cER(τ)ctrain−cER(τ)S(τ)= c_gen(τ)-c_ER(τ)c_train-c_ER(τ). Figure 4: Train and test loss with the structure fraction (τ)S(τ) across node sizes. Community structure emerges at τstruct _ struct well after the onset of overfitting at τcliff _ cliff. A value of 00 means the samples are as unstructured as a random graph of their own density and 11 means they match the training graph.11 1 the floor is recomputed at every evaluation from the samples’ own mean degree, because clustering rises with density and a fixed floor would credit a denser sample with structure it does not have. We define τstruct _ struct as the first epoch at which (τ)S(τ) reaches 0.50.5 and stays there for two consecutive evaluations. Figure 4 plots ℒtrainL_ train and ℒtestL_ test alongside (τ)S(τ), with τstruct _ struct annotated: community structure appears well inside the regime in which the model has already begun overfitting the training graph. The memorized regime cannot be avoided by stopping early. Table 1 gives the onset of instance recall τmem _ mem and the emergence of community structure τstruct _ struct at every size, and the ordering is the same in all the four cases: τmem<τstruct _ mem< _ struct. Every checkpoint that generates graphs with the right structure is already past the onset of instance recall, and every checkpoint before it produces structureless samples. This also makes the test loss a poor selection criterion, since its minimum returns a model that has not yet learned the community structure at all. 4 Conclusion In this work we show that single-graph diffusion models exhibit what we term conditional memorization, where the denoiser is capable of recovering the training graph with perfect recall compared to a test graph. We demonstrate this phenomenon on synthetic graphs drawn from a SBM across different node sizes. Further, we show that the community structure in the graph only appears after the onset of memorization and thus choosing a model based on test loss will result in a sub-optimal denoiser that outputs blob-like graphs. References [1] E. Abbe (2018) Community detection and stochastic block models: recent developments. Journal of Machine Learning Research 18 (177), p. 1–86. External Links: Link Cited by: §2. [2] L. Ambrogioni (2024) The statistical thermodynamics of generative diffusion models: phase transitions, symmetry breaking and critical instability. External Links: 2310.17467, Link Cited by: Appendix C. [3] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg (2021) Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. W. Vaughan (Eds.), Vol. 34, p. 17981–17993. External Links: Link Cited by: Appendix C, §1. [4] G. Biroli, T. Bonnaire, V. de Bortoli, and M. Mézard (2024) Dynamical regimes of diffusion models. Nature Communications 15 (1). External Links: ISSN 2041-1723, Link, Document Cited by: Appendix C. [5] T. Bonnaire, R. Urfin, G. Biroli, and M. Mezard (2025) Why diffusion models don’t memorize: the role of implicit dynamical regularization in training. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: Appendix C, §1. [6] N. Carlini, J. Hayes, M. Nasr, M. Jagielski, V. Sehwag, F. Tramèr, B. Balle, D. Ippolito, and E. Wallace (2023) Extracting training data from diffusion models. External Links: 2301.13188, Link Cited by: Appendix C, §3. [7] S. Chanpuriya, C. N. Musco, K. Sotiropoulos, and C. Tsourakakis (2024) On the role of edge dependency in graph generative models. In Proceedings of the 41st International Conference on Machine Learning, R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp (Eds.), Proceedings of Machine Learning Research, Vol. 235, p. 6325–6345. External Links: Link Cited by: Appendix C, §1. [8] S. Chanpuriya, C. Musco, K. Sotiropoulos, and C. E. Tsourakakis (2021) On the power of edge independent graph models. CoRR abs/2111.00048. External Links: Link, 2111.00048 Cited by: Appendix C, §1. [9] X. Chen, J. He, X. Han, and L. Liu (2023) Efficient and degree-guided graph generation via discrete diffusion modeling. External Links: 2305.04111, Link Cited by: Appendix C, §E.3, §1, §2. [10] I. Evdaimon, G. Nikolentzos, C. Xypolopoulos, A. Kammoun, M. Chatzianastasis, H. Abdine, and M. Vazirgiannis (2024) Neural graph generator: feature-conditioned graph generation using latent diffusion models. External Links: 2403.01535, Link Cited by: §1. [11] T. Farghly, P. Rebeschini, G. Deligiannidis, and A. Doucet (2025) Implicit regularisation in diffusion models: an algorithm-dependent generalisation analysis. External Links: 2507.03756, Link Cited by: Appendix C. [12] J. Garnier-Brun, L. Biggio, D. Beltrame, M. Mézard, and L. Saglietti (2026) Biased generalization in diffusion models. External Links: 2603.03469, Link Cited by: Appendix C, Appendix C, Appendix D, §3, §3. [13] I. Gat, T. Remez, N. Shaul, F. Kreuk, R. T. Chen, G. Synnaeve, Y. Adi, and Y. Lipman (2024) Discrete flow matching. Advances in Neural Information Processing Systems 37, p. 133345–133385. Cited by: §1. [14] X. Gu, C. Du, T. Pang, C. Li, M. Lin, and Y. Wang (2025) On memorization in diffusion models. External Links: 2310.02664, Link Cited by: Appendix C. [15] K. K. Haefeli, K. Martinkus, N. Perraudin, and R. Wattenhofer (2023) Diffusion models for graphs benefit from discrete state spaces. External Links: 2210.01549, Link Cited by: §1. [16] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. CoRR abs/2006.11239. External Links: Link, 2006.11239 Cited by: Appendix C, §1. [17] K. Jiang, J. Cui, X. Dong, and L. Toni (2026) Bures-wasserstein flow matching for graph generation. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix C. [18] J. Jo, S. Lee, and S. J. Hwang (2022) Score-based generative modeling of graphs via the system of stochastic differential equations. In Proceedings of the 39th International Conference on Machine Learning, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato (Eds.), Proceedings of Machine Learning Research, Vol. 162, p. 10362–10383. External Links: Link Cited by: §1. [19] Z. Kadkhodaie, F. Guth, E. P. Simoncelli, and S. Mallat (2024) Generalization in diffusion models arises from geometry-adaptive harmonic representations. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: Appendix C, §1. [20] T. Kaiser and M. Kollmann (2026) Diffusion models memorize in training – and generalize in inference. External Links: 2603.13419, Link Cited by: Appendix C, Appendix C, §3. [21] N. Laabid, S. Rissanen, M. Heinonen, A. Solin, and V. Garg (2025) Equivariant denoisers cannot copy graphs: align your graph diffusion models. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Appendix C, §1. [22] H. Lawrence, V. Portilheiro, Y. Zhang, and S. Kaba (2025) Improving equivariant networks with probabilistic symmetry breaking. External Links: 2503.21985, Link Cited by: Appendix C, §1. [23] M. Li, E. Kreacic, V. K. Potluru, and P. Li (2024) GraphMaker: can diffusion models generate large attributed graphs?. External Links: Link Cited by: §1. [24] A. Melnik, M. Ljubljanac, C. Lu, Q. Yan, W. Ren, and H. Ritter (2024) Video diffusion models: a survey. External Links: 2405.03150, Link Cited by: §1. [25] A. Q. Nichol and P. Dhariwal (2021) Improved denoising diffusion probabilistic models. In Proceedings of the 38th International Conference on Machine Learning, M. Meila and T. Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, p. 8162–8171. External Links: Link Cited by: §1. [26] C. Niu, Y. Song, J. Song, S. Zhao, A. Grover, and S. Ermon (2020) Permutation invariant graph generation via score-based generative modeling. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, S. Chiappa and R. Calandra (Eds.), Proceedings of Machine Learning Research, Vol. 108, p. 4474–4484. External Links: Link Cited by: §1. [27] N. Osman, K. Jiang, D. Buffelli, X. Dong, and L. Toni (2025) LGDC: latent graph diffusion via spectrum-preserving coarsening. External Links: 2512.01190, Link Cited by: Appendix C. [28] Y. Qin, M. Madeira, D. Thanou, and P. Frossard (2025) DeFoG: discrete flow matching for graph generation. In International Conference on Machine Learning (ICML), Cited by: §1. [29] Y. QIN, C. Vignac, and P. Frossard (2025) SparseDiff: sparse discrete diffusion for scalable graph generation. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: Appendix C. [30] D. Roos, O. Davis, F. Eijkelboom, M. Bronstein, M. Welling, İ. İ. Ceylan, L. Ambrogioni, and J. van de Meent (2026) Categorical flow maps. External Links: 2602.12233, Link Cited by: §1. [31] N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhorn, and K. M. Borgwardt (2011) Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12 (77), p. 2539–2561. External Links: Link Cited by: §1. [32] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli (2015) Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, F. Bach and D. Blei (Eds.), Proceedings of Machine Learning Research, Vol. 37, Lille, France, p. 2256–2265. External Links: Link Cited by: §1. [33] G. Somepalli, V. Singla, M. Goldblum, J. Geiping, and T. Goldstein (2022) Diffusion art or digital forgery? investigating data replication in diffusion models. External Links: 2212.03860, Link Cited by: Appendix C, §3. [34] Y. Song and S. Ermon (2020) Generative modeling by estimating gradients of the data distribution. External Links: 1907.05600, Link Cited by: §1. [35] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard (2023) DiGress: discrete denoising diffusion for graph generation. External Links: 2209.14734, Link Cited by: Appendix B, Appendix C, §E.3, §1, §2. [36] Q. Yan, Z. Liang, Y. Song, R. Liao, and L. Wang (2024) SwinGNN: rethinking permutation invariance in diffusion models for graph generation. External Links: 2307.01646, Link Cited by: Appendix C, §1. [37] T. Zhang, Z. Wang, J. Huang, M. M. Tasnim, and W. Shi (2023) A survey of diffusion based image generation models: issues and their solutions. External Links: 2308.13142, Link Cited by: §1. Appendix A Acknowledgements This work was funded by the European Union ERC-2024- STG-101163069 MALAGA. Appendix B Limitations Our experiments use a single two-block SBM, and it remains to be seen whether the same picture holds for other graph families where the structure that emerges is less cleanly summarized by a single statistic. Studying if the same trend is exhibited by other diffusion models like [35] is also a future direction. The dependence on node size is also only partially probed: our four sizes suggest a trend, but we do not characterize how τcliff _ cliff and τstruct _ struct scale with node size. Finally, we train on a single graph throughout. How the bias measured by the U-turn probe behaves as the training set grows beyond one graph is left for future work. Appendix C Related work Generalization vs. Memorization. Understanding why diffusion models [16, 3] generalize is interesting both theoretically and from a privacy perspective [33, 6]. Many recent works have explored a variety of avenues to explain the generalization vs memorization dichotomy in diffusion models. Kadkhodaie et al. [19] attribute the generalization ability of the diffusion models to the inductive bias while other works explore implicit regularization and network capacity [5, 4, 2, 11, 14] as possible arguments. Garnier-Brun et al. [12] show that diffusion models exhibit a biased generalization, where even though the test loss improves, the model shows unusually high affinity to generate some of the training samples. Similarly, Kaiser and Kollmann [20] show that models that generalize well at the sample level overfit the denoising objective resulting in a generalization gap between the train samples and test samples. Memorization in graph diffusion models. Graph diffusion models have received comparatively little attention along these lines. Existing works on discrete graph diffusion and flow matching [35, 29, 9, 27, 17] target generation quality and efficient scaling to large graphs. The notion of memorization is ill-defined for GDMs, since checking whether a model has memorized a graph amounts to solving the graph isomorphism problem as each training graph has Ω(n!) (n!) graphs in its isomorphism class. This is further worsened by the message-passing GNN architectures used as denoisers, which are permutation equivariant by construction and so invariant to node ordering. Works such as [21, 36, 22] show graph diffusion models cannot exactly copy their training graphs. In the single-graph training paradigm such as EDGE [9], edge overlap [7, 8] is used to assess whether generated graphs are highly similar to the reference training graph. Inspired by the notion of biased generalization in image diffusion models [12, 20], we study the learning dynamics of single-graph diffusion models, and find that they exhibit the same signature — a widening train–test generalization gap and a biased reverse process that leads to a behavior we call conditional memorization where the model has the ability to recover the training graph exactly compared to a test graph. Further, our analysis reveals that the community structure only appears after the onset of this memorization which early stopping cannot mitigate. Appendix D Details on U-turn experiment We adopt the experimental setup of [12] to demonstrate train-data bias. Given a fixed checkpoint and a graph G on n nodes with edge set E(G)E(G), for a chosen timestep t we apply the model’s own forward kernel to G’s clean state G0G_0, obtaining a corrupted state GtG_t, and then run the model’s reverse process from GtG_t down to G0G_0, generating a reconstruction G~ G. We measure edge recall ϕt(G)=|E(G~)∩E(G)||E(G)| _t(G)\;=\; |E( G)∩ E(G)||E(G)| (4) We report t on the interpretable axis ρ=1−α¯tρ=1- α_t, the expected fraction of G’s edges removed by step t. All runs use T=256T=256 diffusion steps with a cosine schedule. We evaluate at 1212 timesteps evenly spaced over the full range, t∈5,28,51,74,96,119,142,165,188,210,233,255t∈\5,28,51,74,96,119,142,165,188,210,233,255\, covering ρ from 0.0020.002 to 11. At each (checkpoint, t) we run R independent U-turns of the training graph, differing only in the forward and reverse randomness, and report the mean and the standard error across them. We repeat the identical procedure on fresh graphs drawn from the same stochastic block model never seen in training. Reference law-only denoiser. First, we begin by defining a law-only denoiser that can serve as an unbiased reference. The reference denoiser knows the generating law and the corruption level, but does not have access to the graph itself. Concretely, it knows the block assignment z and the block probabilities pzizjp_z_iz_j. The posterior factorizes as p(A0∣At,z)=∏i<jp(Aij0∣Aijt,z)p(A^0 A^t,z)= _i<jp(A^0_ij A^t_ij,z). The forward process only deletes edges, so an observed present pair must have been an edge, p(Aij0=1∣Aijt=1)=1p(A^0_ij=1 A^t_ij=1)=1, while for an absent pair Bayes’ rule gives β(p,ρ)=p(Aij0=1∣Aijt=0)=ρpρp+(1−p),β(p,ρ)\;=\;p\! (A^0_ij=1 A^t_ij=0 )\;=\; ρ\,pρ\,p+(1-p), (5) In the reverse process the edges are sampled independently with probability β(p,ρ)β(p,ρ), thus the law-only denoiser is capable of restoring the correct number of edges in expectation, but cannot recall the exact pairs. Averaging over true edges, a given edge either survives corruption or is deleted and predicted, giving ϕlaw(ρ)=(1−ρ)⏟survived+ρβ(p,ρ)⏟restored=(1−ρ)+pρ2pρ+1−p _law(ρ)\;=\; (1-ρ)_survived\;+\; ρ\,β(p,ρ)_restored\;=\;(1-ρ)+ p\,ρ^2p\,ρ+1-p (6) Checkpoint admissibility. Late in training at n=512n=512 the sampler develops a density instability in which a growing fraction of reverse trajectories emit far too many edges; recall is inflated one-sidedly under this failure, since a denser reconstruction intersects the target more often. We therefore discard any checkpoint whose reconstructions exceed 1.15×1.15× the training graph’s edge density on either arm, evaluated at the ρ of peak separation. This removes 55 of 2525 checkpoints at n=512n=512 (epochs 83998399–99999999, densities 1.751.75–2.26×2.26×) and none at any other size. All reported n=512n=512 quantities are therefore truncated at epoch 80508050. In Figures 5, we show the edge recall from the U-turn experiment for different node sizes. (a) n64. (b) n256. (c) n512. Figure 5: Edge recall across node sizes. Early stopping cannot mitigate memorization. Memorization begins before the model produces structured samples, at every size. τmem _mem is the first checkpoint at which the peak recall maxρΔϕedge-recall _ρ _ edge-recall exceeds a common absolute floor of 0.020.02; τstruct _struct is the first checkpoint at which the structure fraction of unconditionally generated samples crosses the E-R floor; τgen _gen minimises the per-node-pair loss on held-out graphs from the same law. At n=64n=64 the recall advantage is already above the floor at the earliest available checkpoint, so τmem _mem is bounded rather than measured. At n=512n=512 the held-out loss has no interior minimum within the scored range. The ordering τgen<τmem<τstruct _gen< _mem< _struct holds wherever all three are defined: early stopping at the held-out optimum yields a model that has not yet learnt the block structure, and every checkpoint that has learnt it is already past the onset of instance recall. This is shown in Table 1. Table 1: Memorization onset happens before the emergence of community structure. n=64n=64 n=128n=128 n=256n=256 n=512n=512 τgen _gen (argmin held-out loss) 500 1300 700 — τmem _mem (recall onset) ≤99≤ 99 2799 3199 5599 τstruct _struct (structure in samples) 1900 3100 3600 7775 τstruct−τmem _struct- _mem ≥+1801≥\!+1801 +301+301 +401+401 +2176+2176 It is possible the model might artificially show high edge recall simply by predicting too many edges, to account for this, we also compute the following: for a target graph G and its U-turn reconstruction G~ G, let M=|E(G)|,K=|E(G~)|,I=|E(G)∩E(G~)|.M=|E(G)|, K=|E( G)|, I=|E(G)∩ E( G)|. (7) The edge recall and edge F1 score for one reverse trajectory are R(G,G~)=IM=|E(G)∩E(G~)||E(G)|,R(G, G)= IM= |E(G)∩ E( G)||E(G)|, (8) and F1(G,G~)=2IM+K=2|E(G)∩E(G~)||E(G)|+|E(G~)|.F_1(G, G)= 2IM+K= 2|E(G)∩ E( G)||E(G)|+|E( G)|. (9) For checkpoint τ and corruption level t, we average each metric over independent reverse trajectories. We then define the train–unseen gaps as ΔRτ,t=R¯τ,t(Gtrain)−1J∑j=1JR¯τ,t(Gjunseen), R_τ,t= R_τ,t(G_train)- 1J _j=1^J R_τ,t(G^unseen_j), and ΔF1,τ,t=F¯1,τ,t(Gtrain)−1J∑j=1JF¯1,τ,t(Gjunseen), F_1,τ,t= F_1,τ,t(G_train)- 1J _j=1^J F_1,τ,t(G^unseen_j), where J is the number of unseen graphs and the overline denotes an average over reverse trajectories. Finally, we report the maximum gaps over the corruption grid T: ΔRmax(τ)=maxt∈ΔRτ,t,ΔF1,max(τ)=maxt∈ΔF1,τ,t. R_ (τ)= _t R_τ,t, F_1, (τ)= _t F_1,τ,t. This is shown in Table 2. Table 2: n ΔmaxRecall _ max Recall ΔmaxF1 _ max F1 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 E Experimental setup E.1 Data generation In Table 3 we show the hyperparameters used to generate our SBM training graphs. We choose the simplest two-block setting as this allows us to control the underlying generation process and it also provides the advantage of having an interpretation of what emergence of structure means. Table 3: SBM parameters for data generation. n pinp_in poutp_out 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) E.2 Computing metrics. In Figure 3 we plot the chance floor for edge overlap and WL kernel similarity metrics, this allows us to get a null behavior to compare against since neither marginal statistic is zero for an unmemorized model, so each is reported against its own measured floor. Edge overlap. For labelled graphs G,HG,H on a common vertex set we write ov(G,H)=|E(G)∩E(H)|ov(G,H)=|E(G)∩ E(H)|, reported as a percentage of |E(Gtrain)||E(G_train)|. The floor is the overlap that two unrelated graphs from the same law already share: we draw K=16K=16 independent graphs F1,…,FKF_1,…,F_K from the same stochastic block model as GtrainG_train (disjoint seeds) and take the mean over all (K2)=120 K2=120 pairs, ovchance=(K2)−1∑i<jov(Fi,Fj).ov_chance\;=\; K2^-1 _i<jov(F_i,F_j). This quantity is model-independent, so it is computed once and reused at every checkpoint. At each checkpoint we draw 3232 samples and report ov¯(Ggen,Gtrain) ov(G_gen,G_train) against it. WL kernel similarity. We use the normalized WL subtree kernel with h=3h=3 refinement rounds. Because the model has no node features, the initial color of every vertex is its degree; colors are refined by c(r+1)(v)=(c(r)(v),c(r)(u):u∈N(v))c^(r+1)(v)= (c^(r)(v),\,\\!\c^(r)(u):u∈ N(v)\\!\ ), and WL(G,H)WL(G,H) is the cosine similarity of the concatenated color histograms over rounds 0,…,h0,…,h, so that WL=1WL=1 exactly for a relabeled copy. The floor is a degree-preserving null: we generate 88 rewirings R1,…,R8R_1,…,R_8 of GtrainG_train by double-edge swaps (10|E|10\,|E| attempted swaps, each accepted only if it creates no self-loop or multi-edge), which preserve every vertex degree exactly while destroying the block structure. Two quantities are reported, WLfloor=18∑kWL(Gtrain,Rk),WLexcess=WL¯(Ggen,Gtrain)−WL¯(Ggen,R⋅),WL_floor= 18 _kWL(G_train,R_k), _excess= WL(G_gen,G_train)- WL(G_gen,R_·), the second being the part of the similarity that is specific to the training instance rather than to its degree sequence. E.3 Training details We use the experimental setup of EDGE [9] as this is more computationally efficient compared to models like DiGress [35] which scale quadratically with node size. Across all node sizes we train the models to 10K epochs. We train on a single graph. At each step we sample a timestep t, which sets the corruption level, apply the forward noising process at that level, and train the model to denoise the result back to the clean graph. Since there is only one graph, the same graph is presented many times during training; what changes from step to step is the timestep drawn and the particular corruption realized. Held-out loss is measured on fresh graphs drawn from the same block model, which the model never sees during training. Table 4: Training hyperparameters for the single-graph experiments. All settings are shared across node sizes except where noted. Parameter Value Diffusion Diffusion steps T 256 Noise schedule Cosine Forward process Absorbing (edge deletion) Architecture Backbone Degree-guided transformer GNN Hidden dimension 128 Attention heads (per layer) 8, 8, 8, 8, 1 Node feature Degree Max degree 26 / 27 / 27 / 30 Optimisation Optimiser Adam Learning rate 1×10−41× 10^-4 Gradient clipping 1.0 Warmup None Batch size 32 Steps per epoch 256 Epochs 10,000 (12,200 for n=256n=256) Seed 0 Loss windows. In Figures 6 we track the test loss on held-out test graphs to demonstrate the growing generalization gap. For this we generate 8 fresh graphs from the same SBM law as used for generating the training graph. Structure emergence. For Figure 4 at each evaluation epoch (25) we generate 64 graphs and the clustering coefficient and mean degree is computed and averaged. After computing (τ)S(τ) we use a rolling median with window 3 to smooth out the values and τstruct _ struct is defined as the first epoch where this smoothed value reaches 0.5 and stays there for 2 consecutive epochs. Edge recall. For the U-turn probe we average over R independent reverse trajectories per checkpoint. The details are provided in the table below, where we use smaller R sizes for increasing node size. Table 5: U-turn experiment R draws. n R Checkpoints 64 50 12 128 40 12 256 30 12 512 20 12 Appendix F Loss windows We plot the generalization gap across node sizes. (a) Generalization gap for n=64n=64. (b) Generalization gap for n=128n=128. (c) Generalization gap for n=256n=256. (d) Generalization gap for n=512n=512. Figure 6: Generalization gap across node sizes.