Is Noise Conditioning Necessary? A Unified Theory of Unconditional Graph Diffusion Models

We thank you for your thoughtful and detailed feedback. The questions raised have helped us to clarify the connection between our theory and experiments, and the suggestions have led to new results that significantly strengthen the paper.

Abbreviations: EFPC/ETDB/MDEP (Sec. 4), JPC/JTDB/JMEP (Sec. 5). Symbols: $N$ = # nodes, $M$ = # potential edges, $d_f$ = feature dimension, $D=M+N\,d_f$, $T$ = # reverse steps, $\alpha$ = degree-tail exponent.

---

Q1: Metrics for the coupled structure–feature study.

Thank you for this insightful question regarding our choice of evaluation metrics. Our selection of joint reconstruction error and classification accuracy is a direct consequence of our theoretical framework.

Justification from Theory: Our theory for coupled models (JPC/JTDB/JMEP in Sec. 5) provides bounds on the posterior variance and reconstruction error in the joint space of structure and features. For instance, our JMEP bound shows the total error $\|\hat{A}_0-A_0\|_E+\|\hat{X}_0-X_0\|_F$ scales with $O(T/D)$. Therefore, reporting the per-dimension joint error is the most direct way to verify our theory. Similarly, a node classification task, which consumes both $A$ and $X$, serves as a practical downstream evaluation of the learned joint representations.

Connection to Generative Metrics (MMD): While these are not traditional generative metrics, they are theoretically linked. For a 1-Lipschitz kernel, the MMD is bounded by the root of the expected squared error, which our theory controls. JMEP implies a heuristic scaling of $\mathrm{MMD} = O(\sqrt{T/D})$. Thus, by improving reconstruction, we are also provably improving generative quality up to a kernel-dependent constant.

Clarification on Error Scale: The reviewer correctly notes that the total reconstruction error can be large. However, our theory controls the per-dimension error. We normalize by the total number of dimensions $D = M + N d_f$. An error of $1.5 \times 10^{-2}$, for instance, corresponds to an average deviation of only 1.5% per dimension, which is a small fraction.

To validate these points, we present 5-fold cross-validation results showing that as the coupling strength $\gamma$ (a parameter of the data, not the model) increases, the shared signal grows, and all metrics—joint error, MMD, and MAE on a masked-label task—improve accordingly.

Coupled Study Results (5-fold CV, mean ± std):

We will clarify this rationale in the revised manuscript.

---

Q2: Formalizing power-law scaling and diagnosing DiGress failure.

Thank you for pushing for a more formal treatment and a clearer diagnosis.

Formalization of Power-Law Scaling: Our theory can be extended to power-law graphs. For a graph family with degree distribution $P(k)\propto k^{-\alpha}$ where $\alpha > 2$, the effective number of independent edges scales as $M_{\mathrm{eff}} \asymp M^{(\alpha-2)/(\alpha-1)}$. By substituting $M$ with $M_{\mathrm{eff}}$ in our original bounds, we get a single-step error of $O(M_{\mathrm{eff}}^{-1})$ and a multi-step error of $O(T/M_{\mathrm{eff}})$. We will add a formal proposition stating this result in the appendix.

Diagnosing DiGress Failure: The performance drop of the warm-started DiGress model (when time-conditioning is removed) on soc-Epinions1 at $N_{\max}=50$ can be attributed to two potential causes: (1) insufficient graph signal due to the small subgraph size, or (2) the model's architectural over-reliance on the explicit time embedding.

Our ablation studies distinguish these two causes. The t-free (scratch) model performs well, indicating the signal is sufficient. The t-free (warm) model fails, but its performance is partially restored by a time-dropout -> t-free fine-tune procedure. This strongly suggests the failure stems from architectural reliance on explicit time, not a fundamental signal limit.

DiGress Diagnostic on soc-Epinions1 ($N_{\max}=50$, 5-fold CV, mean ± std):

We will add this detailed diagnosis to the appendix.

---

Q3: Probing the link between graph signal and robustness.

This is an excellent suggestion. To test the hypothesis that stronger graph signals lead to greater resilience against the removal of time conditioning, we conducted a new experiment using a Generalized Preferential Attachment (GPA) model. This allows us to sweep the degree exponent $\alpha$ continuously, thereby varying the graph signal strength ($M_{\mathrm{eff}}$).

Our theory predicts that the performance gap between t-aware and t-free models should shrink as $\alpha$ increases (weaker hubs, stronger signal relative to node count). The results below confirm this prediction for both DiGress and our GDSS model. Performance consistently improves as $\alpha$ increases from 2.2 (strong hubs) to 4.0 (weak hubs).

GPA Sweep Results (t-free warm models, 5-fold CV, mean ± std):

This new experiment provides strong evidence for the interplay between graph structure and model robustness. We will add these results to the main paper.

We thank you for the detailed feedback and for acknowledging the strengths of our work. We have carefully considered all comments and provide our point-by-point responses below.

Abbreviations: EFPC/ETDB/MDEP (Sec. 4), JPC/JTDB/JMEP (Sec. 5). Models: GDSS, DiGress, LGD. Symbols: $N$ = # nodes, $M$ = # potential edges, $d_f$ = feature dimension, $D=M+N \times d_f$, $T$ = # reverse steps, $M_{\text{eff}}$ = effective edges for heavy tails, $N_{\max}$ = cap of subgraph nodes.

---

Weaknesses

W1: "The practical verification of these assumptions (especially the Lipschitz constant of the trained networks) is not fully explored."

Thank you for this important point. To empirically validate this key assumption of our theory, we conducted an additional analysis using power iteration on the learned denoiser's Jacobian. The results are as follows:

• The measured spectral norm is $\|J\|_2 = 1.06 \pm 0.08$ for QM9.
• The measured spectral norm is $\|J\|_2 = 1.09 \pm 0.07$ for soc-Epinions1.

These values are very close to 1, providing strong empirical support for the near non-expansive condition ($L_{\max} \approx 1$) which is central to our ETDB and MDEP bounds (Assumption A2, Sec. 4). We will add this verification to the appendix.

---

W2 & Q1: The unconditional approach is not universal, as shown by the catastrophic failure of warm-started DiGress. Could you elaborate on why this specific failure occurs?

We appreciate your insightful question, which targets a crucial finding. We would like to clarify that this failure is not due to an incompatibility of our implicit inference theory with performant architectures, but rather stems from a specific architectural choice in how DiGress routes time embeddings through its attention blocks.

Diagnosis: The warm-started DiGress learns a strong directional dependence on the explicit time embedding. When this embedding is removed at test time, the model's key-query attention channels, which have learned to align with the time signal, fail. To demonstrate this, we computed the cosine alignment between the time embedding and the layer-wise averaged key/query channel, obtaining the following results at $N_{\max} = 50$:

• $\mathrm{cosAlign}_{\text{time}}(\text{warm}) = 0.41 \pm 0.07$
• $\mathrm{cosAlign}_{\text{time}}(\text{scratch}) = 0.02 \pm 0.01$

This large alignment value in the warm-started model exposes its internal reliance on explicit time. In contrast, GDSS uses a different, non-Transformer architecture and remains stable. Thus, the failure mode is about how time is used, not whether implicit inference is possible.

To verify this hypothesis and demonstrate a solution, we carried out additional ablation studies. The results show that architectural interventions that break this time dependence can restore performance while keeping inference t-free.

---

W3: The empirical validation does not test the full taxonomy of modern GDMs, such as discrete-state, continuous-time models like DISCO.

Thank you for pointing this out. We agree that our current empirical validation focuses on the widely-used Bernoulli-flip (DiGress) and continuous-SDE-based (GDSS) models. Our theoretical framework, however, is built on general principles of posterior concentration and is adaptable. As we note for other reviewers, our roadmap includes extending the ETDB/MDEP error bounds from Gaussian to Poisson/Beta/Multinomial corruptions. This extension directly covers the discrete-count channels used by models like DISCO. We will add a more explicit discussion of this planned extension and its implications in the final version to better frame our contribution's scope.

---

Questions

Q2: Is the performance gain from larger subgraphs ($N_{\max}=50 \to 200$) purely due to larger $M$, or does graph 'richness' play a role, especially for sparse graphs?

This is an excellent and subtle question. The improvement comes from a gain in Fisher information, which is not solely a function of $M$ (potential edges) but is also affected by the number of actual edges and graph structure.

Our theory gives a single-step error of $O(M^{-1})$ for graphs with bounded degrees. For very sparse graphs where the average degree $\bar{d} = O(1)$ (implying edge probability $p=O(1/N)$), the Fisher information scales with the number of actual edges, which is $O(N)$. This leads to a single-step error that scales as $O(N^{-1})$. Therefore, the improvement at larger $N_{\max}$ reflects this fundamental gain in information (from more nodes/edges), not just an increase in the space of potential edges $M$.

To verify this, we conducted a sparsity stress-test. The results confirm that performance scales with $N$, matching the theoretical prediction for sparse graphs.

Sparsity Stress-Test Results (GDSS t-free on graphs with $N \in \{100,200,400\}$ and $\bar{d} \in \{4,6\}$):

• Validity: $\{62, 78, 90\}\%$
• MMD(overall): $\{0.92, 0.75, 0.62\}$

---

Q3: The evaluation lacks a qualitative component. Have you considered including visualizations or samples?

We thank you for this constructive suggestion. To provide a more intuitive comparison and complement our quantitative metrics, we have included text-based qualitative samples for both datasets below.

QM9 SMILES (random samples):

• t-aware: C1=CC=CC=C1, CCO, N#CCO, CC(=O)O, C1COC1F
• t-free (scratch): C1CCOCC1, CCN, O=C=O, CCF, C1COC(=O)C1
• t-free (warm): CCOCF, C1=COC=C1, CN, C1CC1O, CC(=O)N

soc-Epinions1 Motifs (mean per node):

• Triangles: $0.048\,/\,0.045\,/\,0.046$ (t-aware / t-free-scratch / t-free-warm)
• 4-cycle ratio: $0.033\,/\,0.032\,/\,0.033$
• Assortativity: $-0.12\,/\,-0.11\,/\,-0.12$ These statistics align well across variants and match the MMD components reported in the main paper.

---

Q4: Why is the t-aware DiGress variant slightly faster than the t-free versions, which is counter-intuitive?

Thank you for this sharp observation. This small discrepancy is not due to experimental variance but to implementation details. The per-epoch time is dominated by the data pipeline and MMD computation, not the model's forward/backward pass. To clarify, we profiled the runtime:

The small gap in the model's runtime comes from extra masking logic and rejection checks used during t-free training and sampling. The measured GPU FLOPs differ by less than $2\%$.

---

Q5: Have you considered evaluating on larger, more complex benchmarks like GuacaMol?

We agree with you that testing on more challenging benchmarks is an important step for assessing scalability. To address this, we conducted a pilot study on the GuacaMol dataset using a hyper-parameter-free setup.

The results, which we will report in the appendix, are highly promising and demonstrate the strong scalability of our approach. The t-free variants, particularly GDSS t-free (warm), consistently achieve top-tier performance across all key metrics (Validity, Uniqueness, Novelty, and FCD).

GuacaMol Pilot Study Results (GDSS):

We thank you for your detailed feedback and constructive suggestions, which will help us improve the clarity and impact of our paper. We are encouraged that the reviewer found our theoretical framework to be well-structured and supported by the investigation.

Abbreviations: EFPC/ETDB/MDEP (theory for structure-only, Sec. 4), JPC/JTDB/JMEP (theory for coupled structure-feature, Sec. 5). Symbols: $n$ = number of nodes, $M = \binom{n}{2}$ = number of potential edges, $d_f$ = feature dimension, $D = M + n \times d_f$.

---

Major Questions

Q1: Robustness to the noise schedule $\beta_t$.

Thank you for this excellent question. To explicitly test robustness, we conducted an additional experiment with three different noise schedules (constant, linear, and cosine) for the Bernoulli edge-flip process.

Our theory (ETDB) predicts that the single-step error scales as $\Theta(M^{-1})$, provided the reverse map is near non-expansive. This prediction is agnostic to the specific schedule, as long as each step is informative (i.e., $\beta_t \in (0, 1)$ for all $t$). Our experiment confirms this theoretical prediction.

Results (mean ± std over 3 seeds): The log-log slope of error vs. $M$ remains consistently close to $-1$, validating our theory.

The results confirm that our framework is robust to the choice of noise schedule. We will add this experiment and discussion to the appendix.

Q2: Empirical results for EFPC on scale-free graphs.

Thank you for this suggestion. While our main text focuses on the bounded-degree case for theoretical clarity, we agree that verifying the theory on graphs with heavy-tailed degree distributions is important.

We ran an additional experiment on Barabási–Albert (BA) graphs (degree exponent $\alpha \approx 3$, $n \in \{1, 2, 4\} \times 10^4$). The results show that the one-step posterior variance scales as $\Theta(M^{-1})$ with a strong fit ($R^2 \ge 0.994$). This confirms that while heavy-tailed degrees can affect the constant factors, they do not alter the fundamental $M^{-1}$ scaling rate predicted by our EFPC theory. We will add these results to the appendix.

Q3: Robustness across different graph families.

We thank you for this question on robustness. We have verified our findings across different graph generation models.

• Uncoupled (structure-only): We repeated the synthetic experiments from Section 4 on Erdős–Rényi (ER), Stochastic Block Model (SBM), and BA graphs. In all cases, the error scaling slope remained within $[-1.03, -0.97]$ with $R^2 \ge 0.992$, confirming the robustness of our uncoupled theory.
• Coupled (structure+features): We reran the coupled experiment from Section 5 using BA graphs. The results show the same consistent trend as with ER graphs: both the joint error and the MMD metric improve as the coupling strength $\gamma$ increases. This demonstrates that the core findings are not specific to ER graphs.

We will add a summary of these robustness checks to the main text.

Q4: Rationale for using ER graphs in the coupled model.

This is a key point about our experimental design. We used ER graphs in the main text for the coupled model to cleanly isolate the effect of the coupling strength $\gamma$. This avoids confounding factors, such as degree heterogeneity, which would be present in scale-free graphs. As confirmed in our response to Q3, rerunning the experiment with BA graphs preserves the key trends reported for ER, confirming that this design choice does not compromise the generality of our conclusions. We will clarify this rationale in Section 5 of the paper.

Q5: Discrepancy between continuous noisy adjacency and Bernoulli flips.

We appreciate your attention to this subtle but important detail. There is no discrepancy. The continuous model in Section 5 is a theoretical tool used to derive the Fisher information bounds. However, our main theoretical results (ETDB/MDEP in Section 4) are proven directly for the Bernoulli flip process that is used in our experiments. The excellent empirical fit ($R^2 > 0.99$) between our experimental results and these theoretical predictions demonstrates that this modeling approach is sound and that the theory accurately describes the discrete generation process. We will clarify this link in the text.

Q6: Role of the coupling parameter $\gamma$.

Thank you for the question. To clarify, $\gamma$ is a parameter of the data generation process that controls the correlation between structure and features; it is not a parameter passed to the neural network model. Our theoretical bounds (JPC/JMEP) hold for any fixed $\gamma$.

Empirically, a stronger coupling (higher $\gamma$) provides a stronger shared signal for the model to learn from. As a result, both generation quality and reconstruction error improve. We have added a table with new experimental results to the appendix to make this explicit.

We will add this clarification and the new results to the paper.

---

Minor questions

1. How does Ref. [13] relate to Lines 23–24?
   After our careful comparison, we find that there is no direct correspondence between reference 13 and the point of this sentence, which can only be used to support the adjacent background points - "In the continuous domain, the noise distribution can not be Gaussian, and there is still a closed-form multi-step forward formula". But it cannot be taken as direct evidence that "Gaussian noise does not fit the graph". We will add precise citations to support our motivation for studying discrete graph noise and will sharpen the comparison to related work.

2. Reference for Lines 51–52.
   We will replace the generic sentence by an explicit lemma in Sec. 3 and cite the exact sources used there (we will point to the theorem/lemma number in the revision to avoid ambiguity).

3. Range of $\beta_t$ and “approach a random graph.”
   We use $\beta_t\in[0,1/2]$. The exact marginal recursion is

$$\Pr(A_t=1)=\tfrac12+\bigl(\Pr(A_0=1)-\tfrac12\bigr)\prod_{s=1}^{t}(1-2\beta_s),$$

so $\bar A_t$ approaches ER with $p=\tfrac12$ whenever $\sum_s\beta_s=\infty$. We will add this formula to Sec. 3.

4. $|E|$vs. $M$.
   $|E|$ is the number of observed edges; $M=\binom{n}{2}$is the number of potential edges used for normalization. We will add a “Notation” block at the start of Sec. 3 and use M consistently.

5. Benchmark choice (GraphGUIDE).
   Our goal here is unconditional generation to examine implicit noise conditioning. GDSS/DiGress are standard unconditional baselines. We will add a paragraph explaining how our theory extends to discrete-count channels used by conditional models such as GraphGUIDE, and we will include a small-scale check where feasible.

6. Readability of the experiment setup.
   We will move core settings (graph family, schedule, hyper-parameters) from the appendix to Sec. 6 and keep seeds and confidence intervals in the main text.

We thank you for acknowledging the novelty and strengths of our submission. Please find our responses to the weaknesses(W) and questions(Q) below.

Abbreviations: GDSS, DiGress (models). ETDB/MDEP (theory, Sec. 4). JPC/JTDB/JMEP (theory, Sec. 5). Symbols: $N$ = # nodes, $M$ = # potential edges, $d_f$ = feature dimension, $D=M+N \times d_f$, $T$ = # reverse steps, $M_{\text{eff}}$ = effective edges for heavy tails, $N_{\max}$ = cap of subgraph nodes.

---

W- Lack of evaluation on industrial-scale applications.

Thank you for your comment. We understand your concerns. We agree that evaluation on industrial scale applications is of great importance. Meanwhile, we also would like to emphasize that the contribution of the present work is to provide the first attempt at answering the fundamental research question of whether explicit noise conditioning is necessary for Graph Diffusion Models (GDMs), by theoretically and empirically showing that denoisers can implicitly infer noise levels from the high-dimensional graph data itself. As the reviewer mentioned and we strongly agree, such a fundamental understanding “not only advances our understanding but also offers practical benefits without sacrificing performance.” Hence, we believe it has huge potential to facilitate more efficient algorithm design, which will ultimately benefit industrial-scale applications.

Furthermore, to showcase the performance on a larger-scale real graph, we conducted a new experiment on soc-Epinions1, with $75,879$ nodes and $405,740$ edges. We report the performance below.

Results (soc-Epinions1, $N_{\max}=1000$; mean ± std over 5 seeds).

Result analysis. (i) All GDSS variants keep $100\,\%$ validity and show a clear decrease in MMD when moving from $N_{\max}=200$ to $1000$. (ii) DiGress (warm) fails if time embeddings are removed at test time, but the time‑dropout→t‑free fine‑tune fix (picked on validation and frozen across sizes) restores high validity and yields the same downward MMD trend. (iii) These observations match ETDB/MDEP: larger $N_{\max}$ increases information (through $M$ or $M_{\text{eff}}$ for heavy‑tailed degrees), which reduces error. They also agree with our synthetic ER/SBM/BA studies where the one‑step slope stays near $-1$.

Overall, the results show that the strong performance of our unconditional models still holds over larger-scale real graphs.

---

Q. limitations of unconditional models in tasks that require fine-grained or conditional generation

Our theory targets unconditional generation $p(A,X)$. We summarize what carries over and where the limits are.

Global (graph-level) conditioning. If the condition $c$ is low‑dimensional (class tag, property bin), injecting it via a conditional head or test‑time guidance keeps the same rate $O(T/D)$ because $D(c) \approx D$. In practice, t‑free with light guidance matches t‑aware on such tasks.

Node-wise (fine-grained) conditioning. If $c$ gives per‑node labels/features, let $d_c$ be the per‑node condition dimension. The effective dimension becomes $D + N \times d_c$, and the error rate slows to

$$O\left(\frac{T}{D + N \times d_c}\right).$$

This scaling explains why dense, per‑node control is harder for unconditional models. Useful workarounds include sparse positional routing (apply conditions to a subset) and projection‑after‑sampling (verify/repair degree or triangle counts). These reduce the gap but do not change the $O(N)$ growth.