Discrete graph diffusion models (GDMs) corrupt nodes and edges independently under a Markovian noise model. In the unconditional setting without node features, an equivariant denoiser trained on a single graph can generate novel graphs and sample metrics such as edge overlap and WL kernel similarity show no sign of memorization. This work demonstrates that GDMs do memorize. By inspecting reverse diffusion trajectories on two‑block stochastic block models (SBMs) we observe a strong training‑data bias: the model almost perfectly recovers a corrupted training graph, while its recovery of a held‑out test graph is far worse. We call this conditional memorization because it only appears when the reverse trajectory is conditioned on a corrupted training graph and is invisible during inference. It coincides with a growing generalization gap—training loss improves while held‑out loss degrades, and early stopping does not help. Memorization always precedes the emergence of community structure in generated graphs; checkpoints before this point produce structureless graphs. The phenomenon persists across all node sizes we examined.
Review