analiza aiqbench
This study reveals a critical flaw in discrete graph diffusion models, demonstrating that they exhibit "conditional memorization" by perfectly reconstructing corrupted training graphs during specific reverse trajectories. The research establishes a direct correlation between this memorization phenomenon and the emergence of community structures, indicating that early checkpoints produce structureless outputs before overfitting occurs. This finding is essential for researchers developing generative models on graph-structured data, as it highlights inherent generalization gaps that standard mitigation techniques like early stopping cannot resolve.
Your Discrete Graph Diffusion Model is Secretly Memorizing
arXiv:2610.13786v1 Announce Type: new 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.
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.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2610.13786 [cs.LG]
(or arXiv:2610.13786v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.13786 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 295 cuvinte
Subiecte conexe
Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction
arXiv · 7 oct. 2026
ProtoGuide: Prototype-Driven Guidance for Class-Conditional Graph Generation
arXiv · 16 sept. 2026
Backdoor Attacks on Discrete Graph Diffusion Models
arXiv · 6 oct. 2026
Graph Representation via Elements of Discrete Morse and Cobordism Theories
arXiv · 2 oct. 2026