Graph diffusion models memorize training graphs during noise reversal
Your Discrete Graph Diffusion Model is Secretly Memorizing
Machine LearningArtificial Intelligence
Summary
Graph diffusion models try to generate new graphs by learning from noisy versions of existing ones. The authors found that these models can secretly memorize specific training graphs rather than truly learning to create new ones. This memorization shows up when the model tries to reverse the noise on data it was trained on, recovering training graphs almost perfectly but not new graphs. This hidden copying behavior starts before the graphs show clear community structures.
What this means in practice
- •For graph machine learning engineers: Detect and diagnose memorization in graph diffusion models to improve the reliability of synthetic graph generation.
- •For data privacy officers: Assess risks of memorization in graph generative models that could lead to unintended disclosure of sensitive training graph data.
Authors
Adarsh Jamadandi, Nicolas Keriven
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.