{"id":"cc951392-7ae6-4e79-9437-ea970e9a3da7","arxiv_id":"2502.02488","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graph diffusion models frequently distort substructure count distributions, and the paper shows theoretically and empirically that the GNN backbone's subgraph-counting expressivity controls this behavior.","lead":"This paper asks whether graph diffusion models reproduce the frequencies of small substructures, such as cycles, when generating new graphs. It finds that standard models often fail, and argues that more expressive graph neural network backbones improve substructure preservation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 is quantitatively inconsistent with the basis definitions in §4.2: a k=0 check on n=4,m=3 is off by 4×, not just by the sign error, so the central theoretical claim is unverified as stated.","rationale":"The reader correctly identified the sign error, but the sign is only the most visible symptom. The k=0 sanity check shows that Theorem 4.1 is quantitatively inconsistent with the bases defined in §4.2: the F_t expansion under-reproduces E[A0] by a factor of 1/((n-2)!)^2. This is not a limitation assumption or an edge case; it is a failure of the central theorem in the simplest fixed-size, permutation-invariant setting. The Appendix's derivation uses a permutation-average construction with (n-k)! extensions for unused nodes, which is a different object from the labelled-tuple bases in Eq 4 and Eq 6, so the theorem and proof conflate two normalizations. Because Corollary 4.2 and the paper's main expressivity argument depend on the exact form of Eq 8, the theoretical claim is currently unsupported. The empirical backbone comparison is suggestive, but it does not repair a false theorem. The paper may be salvageable by correcting the normalization and sign and by adding a numerical check of Eq 8, but as submitted the main result should not be accepted. This moves the verdict from CONDITIONAL to REJECT.","tokens_in":10841,"tokens_out":26503,"duration_ms":264488,"concrete_test":"Verify Theorem 4.1 in the simplest nontrivial case: set n=4, m=3, let p0 be uniform over all labeled simple graphs with 4 nodes and 3 edges, and take α_t=1, β_t=0.1. Compute the true score at a fixed noisy At by directly evaluating the gradient of Eq 2, and separately compute Eq 8 using Eq 9-10 truncated to k=0 (after flipping the sign on the linear term). The k=0 term of F_t alone should equal E[A0]; if it is smaller by a factor of 1/((n-2)!)^2, the theorem is false as stated. Then repeat the analytic comparison using the permutation-average basis (sum over all n! permutations rather than labelled tuples) to confirm that this corrected basis restores the identity.","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing issue is not the fixed-size assumption but that Theorem 4.1, as written, does not follow from the definitions in §4.2. Sanity-check the k=0 term. For a permutation-invariant training distribution over n-node, m-edge graphs, the numerator expectation is E[A0] = (2m/(n(n-1)))(J-I), with zero diagonal. Using Eq 9 with the bases defined by Eq 4 and Eq 6 gives F_0 = Σ_{i≠j} (2m/n!) · (1/n!)(J-I) = 2m n(n-1)/(n!)^2 (J-I). For n=4, m=3 this is 1/8(J-I), whereas E[A0] is 1/2(J-I); the ratio is 1/((n-2)!)^2. The source is a conflation of the labelled-tuple basis in Eq 4/6 with the permutation-average basis actually used in the Appendix (Eq 17-30): the latter includes (n-k)! extensions over unused nodes. Additionally, Eq 12 has the sign error noted by the reader: ∇ log p_t(At|A0) = -(At - αA0)/β^2, so the linear term in Eq 8 has the wrong sign. The sign is cosmetic; the factor error is not, because Corollary 4.2 and the expressivity claim rely on the exactness of this decomposition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11169,"tokens_out":25073,"duration_ms":259817,"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":[{"comment":"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.","section":"§4.3, Eq. (8) and Appendix Eq. (12)"},{"comment":"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.","section":"§4.2-4.3, Eqs. (9)-(10), (17)-(30)"},{"comment":"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.","section":"§4.1, fixed-size assumption"},{"comment":"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.","section":"§3.2, Tables 1 and 2"}],"minor_comments":[{"comment":"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.","section":"§2, Eq. (2)"},{"comment":"The notation j_1 ≠ j_2 ≠ ... ≠ j_k is ambiguous; it should be stated explicitly that all j_l are pairwise distinct.","section":"§4.2, Eqs. (4) and (6)"},{"comment":"The theorem statement says 'with the diffusion process in Equation 4,' but the diffusion process is defined in Eq. (2), not Eq. (4).","section":"§4.3, Theorem 4.1"},{"comment":"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.","section":"§4.4, discussion of empirical alignment"},{"comment":"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.","section":"Corollary 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper has a promising direction and the errors in Theorem 4.1 appear repairable in principle: the sign can be fixed, and the combinatorial mismatch between permutation averages and the 1/n! injective-labeling bases can be corrected by inserting the appropriate (n-k)! factors or redefining the bases. I recommend major revision rather than rejection, but the revised theorem should be checked carefully by someone with expertise in permutation-equivariant polynomial bases before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft 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.\n\nOverall, 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.\n\nMy recommendation: send to peer review, but be prepared to flag the theory as needing major revision.","headline":"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.","tokens_in":11673,"tokens_out":3937,"would_cite":true,"duration_ms":38841,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["graph diffusion models","subgraph counting","graph neural network expressivity","score function","graph generation","substructure distribution","total variation distance","graph polynomial bases"],"falsifier":"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.","tokens_in":1616,"feed_emoji":"🧩","tokens_out":1604,"duration_ms":86379,"temperature":0.7,"pith_summary":"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.","feed_headline":"Graph diffusion score functions encode subgraph counts","feed_subtitle":"A new theorem ties generation quality to a backbone's ability to count cycles and lines; expressive GNNs preserve them.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the theorem that TV distance between generated and target distributions is controlled by score estimation error, motivating the score-expressivity analysis.","marker":"Chen et al. (2023)"},{"why":"Introduces the invariant and equivariant graph polynomial bases used to express the score function.","marker":"Puny et al. (2023)"},{"why":"Establishes invariant and equivariant graph networks and polynomial approximation, the expressivity framework the paper adopts.","marker":"Maron et al. (2019b)"},{"why":"Defines GDSS, the Gaussian score-based graph diffusion model whose score function is analyzed and used as the baseline.","marker":"Jo et al. (2022)"},{"why":"Provides PPGN, the high-order backbone with the cycle-counting power that validates the expressivity ordering.","marker":"Maron et al. (2019a)"},{"why":"Provides NGNN, a lower-expressivity backbone used to show degradation in cycle generation.","marker":"Zhang & Li (2021)"},{"why":"Provides SSWL, an intermediate-expressivity backbone used in the comparison.","marker":"Zhang et al. (2023)"},{"why":"Provides DiGress, a discrete diffusion baseline whose subgraph TV distances are reported.","marker":"Vignac et al. (2022)"},{"why":"Provides Grum, the template-copying baseline that achieves low subgraph TV at the cost of novelty.","marker":"Jo et al. (2024)"}],"fun_headline_variants":["Expressive GNNs restore substructure counts in graph diffusion","Graph diffusion scores are subgraph count expectations","Counting power of GNN backbone dictates graph diffusion quality","To match substructures, graph diffusion needs counting GNNs","Substructure fidelity in graph diffusion hinges on GNN expressivity"],"cache_read_input_tokens":13824,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Expressive GNNs restore substructure counts in graph diffusion","Graph diffusion scores are subgraph count expectations","Counting power of GNN backbone dictates graph diffusion quality","To match substructures, graph diffusion needs counting GNNs","Substructure fidelity in graph diffusion hinges on GNN expressivity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000658,"raw_usage":{"total_tokens":2967,"prompt_tokens":858,"completion_tokens":2109,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":2029}},"tokens_in":474,"tokens_out":2109,"duration_ms":13763,"temperature":1.0,"reasoning_tokens":2029,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:58:07.659681+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that TV distance between generated and target distributions is controlled by score estimation error, motivating the score-expressivity analysis."},{"cited_title":"T., Maron, H., and Lipman, Y","cited_arxiv_id":null,"evidence_quote":"Introduces the invariant and equivariant graph polynomial bases used to express the score function."},{"cited_title":"and Li, P","cited_arxiv_id":null,"evidence_quote":"Provides NGNN, a lower-expressivity backbone used to show degradation in cycle generation."}],"review_version":1}