Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?

Lexi Pang; Muhan Zhang; Siwei Chen; Xiyuan Wang; Yewei Liu

REVIEW 4 major objections 5 minor 1 cited by

Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?

T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The score function of a Gaussian graph diffusion model is a ratio of graph polynomials whose coefficients are expected subgraph counts, making substructure-counting expressivity the limiting factor for substructure fidelity.

desk verdict Useful evaluation metric and a plausible empirical point, but Theorem 4.1's derivation has a sign error and an apparent factor error that undercuts the theoretical claim as stated. read the letter →

arxiv 2502.02488 v1 pith:72SXXKPP submitted 2025-02-04 cs.LG

Xiyuan Wang , Yewei Liu , Lexi Pang , Siwei Chen , Muhan Zhang This is my paper · ORCID

classification cs.LG

keywords graphdiffusionmodelssubgraphcountingneuralnetworkexpressivityscorefunctiongenerationsubstructuredistributiontotalvariationdistancepolynomialbases

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the structural fidelity of graph diffusion models is governed by their backbones' ability to count substructures. It introduces total-variation distance between subgraph-count distributions as the evaluation metric and shows that several existing graph generators lose even simple patterns such as 7-node lines. The central theoretical result derives the exact score function of a Gaussian graph diffusion model and expresses it as the linear term plus a ratio of infinite series of graph polynomials, with coefficients equal to expected subgraph counts in the training set. A direct corollary is that a backbone that can count every subgraph appearing in the training set, and every edge-rooted version of those subgraphs, can express the score exactly. If this is right, backbone expressivity, rather than the noise process, is the main design lever for generating correct substructure distributions.

What carries the argument

The central machinery is the graph polynomial basis: for a pattern S, the invariant polynomial Q_S(A) is proportional to the subgraph count C_S(A) when A is a binary adjacency matrix, and there is a matching equivariant, edge-rooted analogue. The proof expands the score's nonlinear term in these bases, with each coefficient equal to an expected subgraph count in the training data, thereby converting score estimation into a subgraph-counting problem.

What would settle it

Take a fixed-size training set and use a graph diffusion backbone that provably counts every subgraph in the training set and every edge-rooted variant; if the generated subgraph TV distance remains large on those substructures, the central theorem and its expressivity corollary would be falsified. Conversely, showing that even an exact subgraph counter fails on mixed-size distributions would confirm that the fixed-size assumption, not counting power, is the real boundary.

Watch

Extended reading notes

Core claim

Under the paper's assumptions, which are a permutation-invariant training distribution, all graphs on n nodes with m edges, and Gaussian noise on the adjacency matrix, the score equals the linear term plus the ratio of two graph-polynomial series. The numerator and denominator are built from invariant and equivariant graph polynomial bases evaluated at the noisy adjacency matrix, and their coefficients are expectations over the training distribution of subgraph counts. Consequently, a model can target the exact score for a dataset only if it can count all subgraphs present in the training set and all subgraphs with two marked nodes plus an added edge, as stated in Corollary 4.2. The paper then observes empirically that high-order backbones with greater counting power produce strictly better subgraph TV distances, matching the expressivity ordering.

Load-bearing premise

The load-bearing premise is that all training graphs share one node count and one edge count, with the paper claiming this restriction loses no generality because GNNs can compute these counts; on mixed-size datasets the proven score formula does not cover the true mixture distribution.

Editorial extensions

If this is right

A graph diffusion model's backbone must count every subgraph occurring in the training set, plus edge-rooted variants, to express the exact score.
Substructure generation quality is ordered by backbone expressivity: richer counting power yields lower subgraph TV distances for cycles and lines.
Standard metrics like molecular validity can saturate and hide structural failure, whereas TV distance on subgraph counts separates models that preserve motifs from those that lose them.
The difficulty of a pattern is visible in the score: large cycles and long lines require high-degree polynomial terms that weak backbones cannot represent.
Template-copying models achieve low subgraph TV but low novelty, so subgraph fidelity must be paired with diversity measures.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

On mixed-size datasets, the score should be a mixture over graph sizes, so explicitly conditioning a backbone on node and edge counts could recover the counting guarantee outside the fixed-size theorem.
Because absent subgraphs get zero coefficients in the score expansion, targeted data augmentation for rare motifs should directly change which score terms must be learned.
A backbone's maximum countable cycle or line length could serve as a cheap predictor of the substructure sizes where generation fidelity will collapse.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the paper is worth reading for its evaluation idea and for the empirical backbone comparison, but the theoretical centerpiece is not currently reliable. The claim that the score function decomposes into graph-polynomial bases with subgraph-count coefficients is attractive, but Theorem 4.1 has a sign error and, more seriously, an apparent factor error in the k=0 term. I worked through the k=0 sanity case using the definitions as written and got a result off by 1/((n-2)!)^2, which suggests the derivation conflates the labeled-tuple basis in Eq. 4/6 with the permutation-averaged basis used later in the appendix. The sign error alone is cosmetic; the factor error is load-bearing because Corollary 4.2 and the expressivity argument rely on the exact expansion.

What is genuinely new: introducing TV distance between subgraph-count distributions as an evaluation metric, and showing that existing graph diffusion models badly miss substructure distributions. The observation that Grum succeeds by copying training graphs at the cost of novelty is a nice caveat. The empirical ordering PPGN > SSWL > NGNN on cycle preservation tracks the models' known subgraph-counting abilities, which is a plausible demonstration that backbone expressivity matters. The experiments align with the theory's sufficient condition, though they do not prove necessity.

Soft spots beyond the theorem: the fixed-n,m assumption is hand-waved for real datasets like QM9 where graph size varies; the derivation covers a mixture only if the backbone can separate sizes, which is not established. Also, the TV estimates use only 100 generated samples for the synthetic sets, with no error bars or implementation details, so some near-0/1 numbers may be noisy.

Overall, this is a solid empirical study with an interesting but currently unverified theoretical framing. It deserves a serious referee—the evaluation metric and the empirical finding are useful—but the authors need to fix the theorem and make the derivation consistent with their basis definitions. I'd bring it to a reading group as a case study in how expressivity analyses for diffusion models can go wrong at the detail level.

My recommendation: send to peer review, but be prepared to flag the theory as needing major revision.

Referee Report

4 major / 5 minor

Summary. The paper studies whether graph diffusion models reproduce substructure-count distributions. It introduces a total-variation metric between subgraph-count distributions, reports that existing models (GDSS, DiGress, HGGT, Grum) often fail to preserve such distributions, and proposes a theoretical account: Theorem 4.1 decomposes the score function of a Gaussian graph diffusion model into graph-polynomial terms whose coefficients are expected subgraph counts in the training set. The paper then replaces standard backbones with more expressive GNNs (PPGN, NGNN, SSWL) and reports improved substructure fidelity on synthetic datasets. The central claim is that backbone expressivity, measured by subgraph-counting power, controls score estimation quality and hence substructure generation.

Significance. If the theoretical decomposition were corrected and the empirical estimates were statistically robust, the paper would make a useful contribution: it proposes a principled evaluation metric for structural fidelity, and it connects GNN expressivity to score estimation in graph diffusion models via graph-polynomial bases. The comparison of PPGN, NGNN, and SSWL backbones is a valuable first step, and the authors explicitly acknowledge that their expressivity statement is sufficient rather than necessary. However, the main theorem as written contains sign and combinatorial errors, and the central empirical tables use very small sample sizes, so the paper's headline claims are currently conditional on substantial revision.

major comments (4)

[§4.3, Eq. (8) and Appendix Eq. (12)] The linear term in the score has the wrong sign. From Eq. (2), ∇_{A_t} log p_t(A_t | A_0) = -(A_t - α_t A_0)/β_t^2, so the correct score is -β_t^{-2} A_t + (α_t/β_t^2) E_{A0|At}[A0]. Equations (12) and (8) use +β_t^{-2} A_t. This is not a purely cosmetic issue: the sign appears in the decomposition that Theorem 4.1 claims to establish, and the proof must be corrected consistently.
[§4.2-4.3, Eqs. (9)-(10), (17)-(30)] Theorem 4.1 does not follow from the basis definitions given in Section 4.2. Equation (4) and Eq. (6) normalize by 1/n! over injective labelings of the pattern's nodes, whereas the derivation after Eq. (17) averages over all n! permutations of the full node set; for a pattern with k distinguished nodes these operations differ by a factor (n-k)! that is never accounted for. Concretely, for k=0, the coefficient in Eq. (9) is E[Q_{S_ij}] = 2m/n!, and the appendix's own Eq. (29) identifies the basis as M_ij = (1/n!) Σ_π E_{π(i)π(j)}. Since Σ_{i≠j} M_ij = J-I, the k=0 term evaluates to (2m/n!)(J-I), whereas E[A0] = (2m/(n(n-1)))(J-I); for n=4, m=3 this is (1/4)(J-I) instead of (1/2)(J-I). Under a literal reading of Eq. (6) the discrepancy is different but still nonzero. Additionally, Eq. (10) carries a redundant Σ_{ij∈[n]^2} that scales G_t by n^2. Since Corollary 4.2 and the expressivity claims rely on the exactness of this decomposition, the theorem needs corrected combinatorics or corrected basis definitions.
[§4.1, fixed-size assumption] The assumption that all training graphs have exactly n nodes and m edges is not made harmless by the sentence 'this assumption does not reduce the generality of our results because most GNNs can easily compute the number of nodes and edges.' For variable-size datasets such as QM9, p_t(A_t) is a mixture over graph sizes, and while n is available as the input dimension, the original edge count m is not directly recoverable from the noisy matrix A_t. The derivation applies to a single fixed-size component only. The paper should either state the theorem as a conditional statement for p_t(A_t | n, m) with an explicit argument for how backbones estimate the conditioning, or provide a separate justification for the QM9 experiments.
[§3.2, Tables 1 and 2] The synthetic TV distances are estimated from only 100 generated samples. For a TV distance over count distributions, 100 samples yield large standard errors; differences on the order of 0.01-0.03 (for example, DiGress c3c4 0.03 versus Grum 0.01 in Table 1, or several PPGN entries in Table 2) are within sampling noise. The claims that existing models fail and that the expressive backbones are ordered PPGN > SSWL > NGNN would be substantially strengthened by error bars or confidence intervals, or by using many more generated samples.

minor comments (5)

[§2, Eq. (2)] The transition density in Eq. (2) omits the (2π)^{-n^2/2} β_t^{-n^2} normalization of the matrix Gaussian; this does not affect the score, but the formula should be stated correctly.
[§4.2, Eqs. (4) and (6)] The notation j_1 ≠ j_2 ≠ ... ≠ j_k is ambiguous; it should be stated explicitly that all j_l are pairwise distinct.
[§4.3, Theorem 4.1] The theorem statement says 'with the diffusion process in Equation 4,' but the diffusion process is defined in Eq. (2), not Eq. (4).
[§4.4, discussion of empirical alignment] The authors correctly note that they do not prove a converse of Corollary 4.2, but the concluding sentence that the experiments 'confirm' the theoretical claim overstates the support; the observed ordering is a consistency check with a sufficient-condition theory, not a falsifiable prediction.
[Corollary 4.2] The definition of S' is unclear when the two marked nodes already have an edge in the subgraph; the paper should specify whether parallel-edge patterns are allowed or how such cases are handled.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the score decomposition is derived from the diffusion transition and polynomial bases, not fitted to its own conclusions.

full rationale

The paper's central claim, Theorem 4.1, is an analytic decomposition: Eq (8) is obtained from Eq (2) by differentiating the logarithm, Taylor-expanding exp((alpha_t / beta_t^2) <A0, At>), and rewriting the resulting moments in the graph polynomial bases defined in Eq (4)-(6). The coefficients in Ft and Gt are explicitly expected subgraph counts over the training distribution (Eq 9-10), so no parameter is fitted to the quantities the theorem is used to explain. Corollary 4.2 states a sufficient condition: if the backbone can express the bases appearing in Ft and Gt, it can express the score function. The paper explicitly declines to claim necessity ('Though we do not prove that whether models with lower expressivity can express the score function'), so the later experiment observing PPGN > SSWL > NGNN is a consistency check rather than a prediction forced by the derivation. The self-citations (NGNN, SSWL, subgraph WL, LGD) are used to instantiate backbone choices and as related work; none is the sole support for the theorem. The fixed-n,m assumption is stated openly and is a simplification, not a hidden definition of the conclusion. A separate concern about a possible normalization factor or sign error in Eq (8)-(12) could affect the theorem's validity, but it is not a circularity: the claimed derivation is not equivalent to its inputs by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fit; the analysis relies on domain assumptions about the data distribution and the diffusion process. The fixed-n,m assumption is the most fragile, as real datasets vary in size.

assumptions (4)

domain assumption Training distribution is permutation-invariant.
Stated in Theorem 4.1 assumptions; used to symmetrize F_k in Appendix A Eq. 21.
domain assumption All graphs have exactly n nodes and m edges.
Stated in Section 4.1; hand-waved as not reducing generality because GNNs can compute n and m, but this is not proven for mixture distributions.
domain assumption The Gaussian corruption process (Eq. 2) is a valid diffusion model for graphs.
The entire analysis is for GDSS-like continuous diffusion; discrete models are out of scope (acknowledged in Limitations).
standard math Taylor expansion of the exponential is valid term-by-term.
Used in Appendix A Eq. 15 to expand exp(α/β^2 ⟨A0, At⟩); convergence is assumed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?." pith.science (2026). https://pith.science/paper/72SXXKPP

@misc{pith2026250202488,
  author       = {Pith},
  title        = {Pith review of: Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/72SXXKPP}},
  note         = {Machine review of arXiv:2502.02488}
}

read the original abstract

Diffusion models have gained popularity in graph generation tasks; however, the extent of their expressivity concerning the graph distributions they can learn is not fully understood. Unlike models in other domains, popular backbones for graph diffusion models, such as Graph Transformers, do not possess universal expressivity to accurately model the distribution scores of complex graph data. Our work addresses this limitation by focusing on the frequency of specific substructures as a key characteristic of target graph distributions. When evaluating existing models using this metric, we find that they fail to maintain the distribution of substructure counts observed in the training set when generating new graphs. To address this issue, we establish a theoretical connection between the expressivity of Graph Neural Networks (GNNs) and the overall performance of graph diffusion models, demonstrating that more expressive GNN backbones can better capture complex distribution patterns. By integrating advanced GNNs into the backbone architecture, we achieve significant improvements in substructure generation.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Permutation-Invariant Spectral Learning via Dyson Diffusion
stat.ML 2025-10 conditional novelty 7.0 of 10

Dyson Diffusion Model learns graph spectra by scoring Dyson Brownian Motion and matches or beats GNN/transformer diffusion baselines without ad-hoc spectral features.

Reference graph

Works this paper leans on

20 extracted references · 14 canonical work pages · cited by 1 Pith paper

[1]

Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions

Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In ICLR, 2023

work page 2023
[2]

S., Riley, P

Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In ICML, 2017

2017
[3]

K., Martinkus, K., Perraudin, N., and Wattenhofer, R

Haefeli, K. K., Martinkus, K., Perraudin, N., and Wattenhofer, R. Diffusion models for graphs benefit from discrete state spaces. ArXiv, abs/2210.01549, 2022

arXiv 2022
[4]

Graph generation with \ k 2\ -trees

Jang, Y., Kim, D., and Ahn, S. Graph generation with \ k 2\ -trees. In ICLR, 2024

work page 2024
[5]

Jo, J., Lee, S., and Hwang, S. J. Score-based generative modeling of graphs via the system of stochastic differential equations. In ICML, 2022

work page 2022
[6]

Jo, J., Kim, D., and Hwang, S. J. Graph generation with diffusion mixture. In ICML, 2024

work page 2024
[7]

SaGess: Sampling Graph Denoising Diffusion Model for Scalable Graph Generation

Limnios, S., Selvaraj, P., Cucuringu, M., Maple, C., Reinert, G., and Elliott, A. Sagess: Sampling graph denoising diffusion model for scalable graph generation. ArXiv, abs/2306.16827, 2023

work page Pith review arXiv 2023
[8]

Provably powerful graph networks

Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. NeurIPS, 2019 a

work page 2019

Show all 20 references

[9]

Invariant and equivariant graph networks

Maron, H., Ben - Hamu, H., Shamir, N., and Lipman, Y. Invariant and equivariant graph networks. In ICLR, 2019 b

2019
[10]

L., Lenssen, J

Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019

2019
[11]

Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings

Morris, C., Rattan, G., and Mutzel, P. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. NeurIPS, 2020

2020
[12]

Permutation invariant graph generation via score-based generative modeling

Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, 2020

2020
[13]

T., Maron, H., and Lipman, Y

Puny, O., Lim, D., Kiani, B. T., Maron, H., and Lipman, Y. Equivariant polynomials for graph neural networks. In ICML, 2023

2023
[14]

Digress: Discrete denoising diffusion for graph generation

Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffusion for graph generation. ArXiv, abs/2209.14734, 2022

2022 arXiv
[15]

How powerful are graph neural networks? In ICLR, 2019

Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019

2019
[16]

A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests

Zhang, B., Feng, G., Du, Y., He, D., and Wang, L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In ICML, 2023

2023
[17]

and Li, P

Zhang, M. and Li, P. Nested graph neural networks. NeurIPS, 2021

2021
[18]

From relational pooling to subgraph GNN s: A universal framework for more expressive graph neural networks

Zhou, C., Wang, X., and Zhang, M. From relational pooling to subgraph GNN s: A universal framework for more expressive graph neural networks. In Proceedings of the 40th ICML, volume 202 of Proceedings of Machine Learning Research, pp.\ 42742--42768. PMLR, 2023

2023
[19]

Latent graph diffusion: A unified framework for generation and prediction on graphs

Zhou, C., Wang, X., and Zhang, M. Latent graph diffusion: A unified framework for generation and prediction on graphs. NeurIPS, 2024

2024
[20]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions

Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In ICLR, 2023

work page 2023

[2] [2]

S., Riley, P

Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In ICML, 2017

2017

[3] [3]

K., Martinkus, K., Perraudin, N., and Wattenhofer, R

Haefeli, K. K., Martinkus, K., Perraudin, N., and Wattenhofer, R. Diffusion models for graphs benefit from discrete state spaces. ArXiv, abs/2210.01549, 2022

arXiv 2022

[4] [4]

Graph generation with \ k 2\ -trees

Jang, Y., Kim, D., and Ahn, S. Graph generation with \ k 2\ -trees. In ICLR, 2024

work page 2024

[5] [5]

Jo, J., Lee, S., and Hwang, S. J. Score-based generative modeling of graphs via the system of stochastic differential equations. In ICML, 2022

work page 2022

[6] [6]

Jo, J., Kim, D., and Hwang, S. J. Graph generation with diffusion mixture. In ICML, 2024

work page 2024

[7] [7]

SaGess: Sampling Graph Denoising Diffusion Model for Scalable Graph Generation

Limnios, S., Selvaraj, P., Cucuringu, M., Maple, C., Reinert, G., and Elliott, A. Sagess: Sampling graph denoising diffusion model for scalable graph generation. ArXiv, abs/2306.16827, 2023

work page Pith review arXiv 2023

[8] [8]

Provably powerful graph networks

Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. NeurIPS, 2019 a

work page 2019