Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?

Xiyuan Wang, Yewei Liu, Lexi Pang, Siwei Chen, Muhan Zhang · 2025

Read Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions? by Xiyuan Wang, Yewei Liu, Lexi Pang, Siwei Chen, Muhan Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02488.txt.

Description

Xiyuan Wang, Yewei Liu, Lexi Pang, Siwei Chen, and Muhan Zhang test whether graph diffusion models faithfully reproduce the small patterns inside graphs in this 2025 paper. Diffusion generators are popular for making new graphs, but their expressive limits were murky. The authors judge them by how often specific substructures appear.

Existing models failed the test: their generated graphs did not keep the substructure counts of the training data. Popular backbones based on graph transformers lack the power to model such distributions exactly. The authors prove a link between the expressivity of the underlying graph network and the generator's quality. Swapping in stronger networks improved substructure generation significantly. The work gives builders a sharper yardstick and a fix for a hidden weakness.

Catalog record

CREATORXiyuan Wang, Yewei Liu, Lexi Pang, Siwei Chen, Muhan Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02488

Browse the full library · About the Tower of Babel