Source-linked AI summary
Your Discrete Graph Diffusion Model is Secretly Memorizing
Adarsh Jamadandi, Nicolas Keriven
TL;DR
Sample-level metrics can suggest that single-graph diffusion models generalize, leaving their memorization insufficiently detected by ordinary generation. The paper probes reverse trajectories on two-block SBMs and finds that corrupted training graphs are recovered far more strongly than held-out graphs. This conditional memorization begins before community structure emerges, so early stopping does not avoid it while retaining that structure.
Problem
Single-graph graph diffusion models can generate novel graphs, while common sample-level metrics report no memorization, leaving the question of memorization unresolved.
Source: §1 · pp. 1–2Method
Results
At n = 256 and ρ = 0.60, the model restores 96.9% of corrupted training-graph edges versus 7.7% for a denoiser that learned only the generating law, while unseen-test recall stays near that reference.
Source: §3 · p. 3Takeaways & Limitations
Across all four tested sizes, memorization onset precedes community structure, so early stopping cannot retain the structure while avoiding the memorization regime.
Source: §1 · p. 2, §3 · p. 4Experiments use a single two-block SBM and one training graph; generalization to other graph families, diffusion models, and larger training sets remains open.
Source: B Limitations · p. 8
Abstract
from arXiv · showhide
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
Graph diffusion models can generate diverse graphs from a single training graph, and common sample-level metrics suggest they do not memorize it. This work challenges that conclusion by finding conditional memorization in reverse diffusion trajectories, with memorization onset preceding community structure across four tested node sizes.
1 Introduction
- Graph generation has extended diffusion methods from continuous latent spaces to discrete graph-space corruption, which has been reported as more appropriate for realistic graph structures.The passage also notes growing work on graph diffusion and discrete flow matching.Source: §1 · p. 1
- Prior work reports that equivariant denoisers cannot copy a specific training graph exactly, while edge overlap and WL kernel similarity suggest no memorization.A single graph has Ω(n!) graphs in its isomorphism class; these metrics assert no memorization.Source: §1 · pp. 1–2
- The paper terms this conditional memorization: a corrupted training graph is recoverable through reverse dynamics, but the bias is not apparent during inference.The study probes single-graph models trained on two-block SBMs.Source: §1 · p. 2
- Across n = {64, 128, 256, 512}, memorization onset precedes community structure, so early stopping cannot separate learning the structure from entering the memorization regime.The minimum held-out loss is a poor model-selection proxy: before memorization onset, generated graphs remain structureless.Source: §1 · p. 2
2 Sample-level metrics are blind to memorization
Sample-level metrics suggest that generated graphs become structurally accurate and remain novel, but this appearance of generalization is premature: community structure emerges only after memorization begins.
2 Sample-level metrics are blind to memorization
- The experiments use two-block SBMs at n = {64, 128, 256, 512}, holding detectability margin at 7.0 and mean degree at approximately 16 across sizes.This setup varies graph size independently of task difficulty.Source: §2 · p. 2
- EDGE is the backbone: forward corruption removes edges to an empty terminal graph, while the reverse model predicts active nodes and edges between them.The reverse process copies other node pairs forward unchanged.Source: §2 · pp. 2–3
- Clustering-coefficient NMAE improves while WL kernel similarity stays flat, suggesting structural fit and novelty even though the model is memorizing.Before the memorization regime, generated samples are structureless; community structure appears well inside it.Source: §2 · p. 3
3 Conditional memorization in the reverse diffusion trajectories
A U-turn probe finds that reverse diffusion recovers corrupted training graphs far better than test graphs, revealing a bias that ordinary sample-level metrics miss. Across tested sizes, instance recall begins before generated graphs develop community structure, so early stopping does not avoid the memorized regime while producing structured samples.
3 Conditional memorization in the reverse diffusion trajectories
- The law-only reference denoiser knows the block assignment and block probabilities but not the graph itself, providing a baseline for non-instance-specific recovery.The comparison helps distinguish recovery attributable to the generating law from training-graph-specific recall.Source: §3 · p. 3
- The U-turn probe independently deletes edges from a reference graph, then reverses diffusion with its original degree sequence supplied as an auxiliary feature to measure edge recall.The setup compares reverse trajectories seeded from training and test data.Source: §3 · p. 3
- At n = 256 and ρ = 0.60, the model restores 96.9% of corrupted training-graph edges, versus 7.7% for a law-only denoiser, while test-graph recall stays near the reference.The train-data bias occurs across node sizes, though recall rates vary.Source: §3 · p. 3, Figure 2 · p. 3
- Across node sizes, edge overlap and WL similarity stay flat while U-turn edge recall rises, because unconditional sampling starts from an empty graph and does not pass near the training graph.Thus sample-level comparisons can appear clean even when the model shows bias in the noisy-state region it was trained on.Source: §3 · p. 4
- At every tested size, instance-recall onset precedes community-structure emergence, so checkpoints before recall onset produce structureless samples and structured checkpoints are already past that onset.The minimum test loss is a poor selection criterion because it returns a model that has not yet learned community structure.Source: §3 · p. 4
4 Conclusion
Single-graph diffusion models exhibit conditional memorization: reverse dynamics can recover a corrupted training graph, while community structure emerges only after memorization begins. Consequently, selecting by held-out loss can yield a denoiser that produces blob-like graphs.
4 Conclusion
- Community structure appears only after memorization begins, so checkpoints that produce structured graphs are already in the memorized regime.The reported ordering is τmem < τstruct.Source: §4 · p. 4, Figure 4 · p. 4
- Single-graph diffusion models can recover the training graph with perfect recall compared with a test graph, a behavior termed conditional memorization.The training graph is recoverable through the reverse dynamics when seeded with a corrupted version.Source: §4 · p. 4
- Choosing a model based on test loss can yield a sub-optimal denoiser that outputs blob-like graphs.Source: §4 · p. 4
B Limitations
The experiments establish conditional memorization on a single two-block SBM, while the paper identifies broader graph families and training-set sizes as open scope questions. Related work frames the result against graph-generation metrics and prior findings on diffusion-model generalization and memorization.
B Limitations
- Experiments use a single two-block SBM; whether the same behavior holds for other graph families remains open.The authors also leave comparison with other diffusion models, scaling with node size, and training sets larger than one graph for future work.Source: B Limitations · p. 8
C Related work
- Earlier diffusion studies connect generalization to inductive bias, implicit regularization, network capacity, and biased affinity to training samples.Source: C Related work · p. 8
- Prior graph-diffusion work emphasizes generation quality and scaling, while this paper studies memorization through train–test gaps and biased reverse trajectories.The paper notes that graph isomorphism complicates defining memorization, and that edge overlap is used in single-graph settings.Source: C Related work · p. 8
D Details on U-turn experiment
The U-turn experiment corrupts a graph with the model’s forward kernel and reverses from that state to test reconstruction bias against unseen graphs. It compares edge-recall and F1 gaps across corruption levels and node sizes, while excluding severely over-dense checkpoints at n = 512.
D Details on U-turn experiment
- Each U-turn starts from a forward-corrupted graph and reverses to reconstruct it; the same procedure is run on fresh same-law graphs never seen in training.Source: D Details on U-turn experiment · pp. 8–9
- Corruption is reported as ρ, the expected fraction of edges removed; 12 timesteps span ρ from 0.002 to 1 across 256 diffusion steps.Source: D Details on U-turn experiment · pp. 8–9
- The law-only reference knows the block assignments and probabilities but not the graph, so it can restore edge counts in expectation without recalling exact pairs.Source: D Details on U-turn experiment · p. 9
- For n = 512, five late checkpoints are discarded because density instability inflates recall; reported quantities are truncated at epoch 8050.The exclusion threshold is 1.15× the training graph’s edge density on either arm.Source: D Details on U-turn experiment · p. 9
- At every size where all three checkpoints are defined, τgen < τmem < τstruct: the held-out-loss optimum precedes both instance recall and structured samples.At n = 64, τmem is bounded by the earliest available checkpoint; at n = 512, τgen has no interior minimum in the scored range.Source: D Details on U-turn experiment · p. 9, Table 1 · p. 9
- The recall calculation is accompanied by a check against inflated edge prediction, since predicting too many edges can artificially raise recall.Source: D Details on U-turn experiment · pp. 9–10
- Figure 5 presents U-turn edge recall across node sizes.Source: Figure 5 · p. 10
- The experiment averages recall and F1 over independent reverse trajectories, computes train–unseen gaps, and reports their maxima over corruption levels.The unseen-graph average uses J fresh graphs; the table lists maximum recall and F1 gaps by n.Source: D Details on U-turn experiment · p. 10, Table 2 · p. 11
E.1 Data generation
The data-generation setup uses symmetric two-block SBMs, with parameters chosen to control the generating process and make structural emergence interpretable.
E.1 Data generation
- Training graphs are generated using a two-block SBM, with parameters listed in Table 3.Source: §E.1 · p. 11, Table 3 · p. 11
- The two-block setting is chosen to control the underlying generation process and make the emergence of structure interpretable.Source: §E.1 · p. 11
- The setup uses the simplest two-block setting for the experiments.Source: §E.1 · p. 11
E.2 Computing metrics.
The section defines edge-overlap and WL-kernel similarity metrics and compares them with null floors to distinguish training-instance similarity from similarity expected under the graph structure.
E.2 Computing metrics.
- Edge overlap is the percentage of training edges shared by two labelled graphs, compared against the mean overlap of 16 independent graphs from the same SBM law.The floor is model-independent and is reused at each checkpoint; 32 generated samples are evaluated per checkpoint.Source: §E.2 · p. 11
- The normalized WL subtree kernel uses three refinement rounds, with vertex degree as the initial color when node features are absent.Its similarity is the cosine similarity of concatenated color histograms, and equals 1 for a relabeled copy.Source: §E.2 · p. 11
- The WL-kernel floor uses eight double-edge-swap rewirings that preserve every vertex degree while destroying block structure.Each rewiring attempts 10 |E| swaps, accepting only those that avoid self-loops and multi-edges.Source: §E.2 · p. 11
- The WL comparison reports a component specific to the training instance rather than its degree sequence.This component is distinguished from similarity attributable to the degree sequence.Source: §E.2 · p. 11
E.3 Training details
The experiments train single-graph diffusion models and evaluate held-out loss, structure emergence, and reverse-trajectory recovery across node sizes.
E.3 Training details
- Models train on one graph for 10K epochs, with each update denoising a timestep-corrupted version of that graph and held-out loss measured on fresh same-SBM graphs.The shared hyperparameter table applies across node sizes except where noted.Source: §E.3 · p. 12, Table 4 · p. 12
- Held-out loss windows use eight fresh graphs drawn from the same SBM law as the training graph.Figure 6 tracks test loss on these graphs to demonstrate the generalization gap.Source: §E.3 · p. 12
- Structure emergence is evaluated from clustering coefficient and mean degree averaged over 64 generated graphs at each evaluation epoch.The smoothed S(τ) defines τstruct as its first value reaching 0.5 for two consecutive epochs.Source: §E.3 · p. 12
- U-turn edge-recall estimates average independent reverse trajectories per checkpoint, using fewer draws as node size increases.The experiment's draw counts are presented in Table 5.Source: §E.3 · p. 12, Table 5 · p. 12
F Loss windows
This section presents the generalization gap across node sizes in Figure 6.
F Loss windows
- Figure 6 plots the generalization gap across node sizes.The section identifies the figure as a cross-size view of the gap.Source: Figure 6 · p. 13, F Loss windows · p. 13