Is Noise Conditioning Necessary? A Unified Theory of Unconditional Graph Diffusion Models
Authors: Jipeng Li
Yanning Shen
Venue: NeurIPS 2025 spotlight ()
Keywords: Graph Diffusion Models
Unconditional Graph Diffusion
Noise Conditioning
Primary area: deep_learning
TL;DR: This paper shows that explicit noise conditioning in Graph Diffusion Models (GDMs) is not essential.

Abstract: Explicit noise-level conditioning is widely regarded as essential for the effective operation of Graph Diffusion Models (GDMs). In this work, we challenge this assumption by investigating whether denoisers can implicitly infer noise levels directly from corrupted graph structures, potentially eliminating the need for explicit noise conditioning.  To this end, we develop a theoretical framework centered on Bernoulli edge-flip corruptions and extend it to encompass more complex scenarios involving coupled structure-attribute noise. Extensive empirical evaluations on both synthetic and real-world graph datasets, using models such as GDSS and DiGress, provide strong support for our theoretical findings. Notably, unconditional GDMs achieve performance comparable or superior to their conditioned counterparts, while also offering reductions in parameters (4-6%) and computation time (8-10%). Our results suggest that the high-dimensional nature of graph data itself often encodes sufficient information for the denoising process, opening avenues for simpler, more efficient GDM architectures.

Is Noise Conditioning Necessary? A Unified Theory of Unconditional Graph Diffusion Models
Jipeng Li
Department of Electrical and Computer Engineering University of California, Davis Davis, CA 95616 j jipli@ucdavia edu
Yanning Shen
Department of Electrical Engineering and Computer Science University of California, Irvine Irvine, CA 92697 yannings@uci.c. edu
Abstract
Explicit noise-level conditioning is widely regarded as essential for the effective operation of Graph Diffusion Models (GDMs). In this work, we challenge this assumption by investigating whether denoisers can implicitly infer noise levels di- rectly from corrupted graph structures, potentially eliminating the need for explicit noise conditioning. To this end, we develop theoretical framework centered on Bernoulli edge-flip corruptions and extend it to encompass more complex scenarios involving coupled structure-attribute noise. Extensive empirical evaluations on both synthetic and rorl-world graph datasets, using models such as GDSS and DiGress, provide strong support for theoretical findings. Notably, unconditional GDMs achieve performance comparable or superior to their conditioned counter- parts, while also offering reductions in parameters (4 6%) and computation time (8 18-10%% 10%). Our results suggest that the high-dimensional nature graph data itself often encodes sufficient information for the denoising process, opening avenues for simpler, more efficient GDM architectures.
Introduction
Diffusion models have demonstrated strong performance across range of generative tasks, including image synthesis, molecular design, and graph- based combinatorial optimization [177] A central assumption these models the requirement for the denoiser to explicitly conditioned on the noise level (or timestep) [ (9. However, recent work on continuous data suggests that high-capacity denoisers can implicitly infer noise scale directly from the corrupted inputs, potentially eliminating the need for explicit conditioning [2].
Extending this conclusion to graph diffusion models (GDMs) non-trivial, owing the inherently discrete and structured nature of graphs. The Gaussian noise commonly used in diffusion models for continuous data ill-suited for graphs as it tends destroy their essential structural properties (13). To address this, modern GDMs employ discrete or structured corruption processes, such as Bernoulli edge flips 77 14,, categorical rewiring [15], or Poisson jumps [16], ensure that intermediate graph states remain valid. Unlike continuous domains where Gaussian perturbations are common, graphs are typically corrupted by discrete, structure preeturv--peeervinggg processes. The resulting noisy adjacency A,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

already carries information about the corruption scale through simple statistics, and the number of potential edges grows as M- (2). Hence, the observation each step may be informative enough for a denoiser to infer the noise level without an explicit time input. These considerations lead to our central question: Is explicit noise-level conditioning truly necessary for GDMs?
In this work, we address this question through a unified theoretical and empirical investigation. We introduce novel theoretical framework featuring posterior concentration and error propagation bounds-Edge- Sadss-Fiipp Posterior Concentration (EFPC), Edge- Targe- Deviation Bound (ET and Multi-Step Denoising Error Propagation (MDEP) to rigorously characterize when explicit noise-level conditioning in GDMs can be safely omitted. For instance, with Bernoulli edge flips, we prove noise scale posterior variance shrinks optimally O(M ) and omitting timesteps yields a reconstruction error bounded by (T) over I steps. Our analysis generalizes to other corruption processes, including Poisson, Beta, multinomial, and jointly structured gature-graph noise.
Extensive experiments on synthetic and real-world datasets corroborate our theory, validating that ex- plicit noise inputs are often dispensable. Unconditional variants of state-of-the-art GDMs, GDSS [17] and DiGress 77.. match or surpass their conditioned counterparts in quality, while improving effi- ciency (4-6% fewer parameters, 8-10% faster per-epoch runtime). Open source implementation is available for regenerating the results. Overall, this work revisits a foundational assumption in diffusion modeling, demonstrating that noise-unconditinn GDMs can be as accurate, more efficient, and conceptually simpler, paving the way for new GDM designs.
2 Related Work
Timestep Conditioning in Graph Diffusion Models. Denoising diffusion models reconstruct data by reversing a noise process through iterative denoising steps conditioned on the timestep t GDMs, such DiGress with discrete categorical Markov processes 77.. GDSS with coupled stochastic differential equations (SDEs) [7). and EDM with equivariant diffusion for molecules [19, explicitly condition the denoiser the noise level. This explicit conditioning adds complexity and training cost, prompting questions about its necessity for graph data [I 12].
g 9 [8]
Blind Denoising, Blind denoising infers noise implicitly and is effective in continuous domains 2oise2Self (20] and recent diffusion work [10] [1]. Graphs pose a tougher case: these methods assume continuous Gaussian noise, whereas GDMs discrete or structured corruptions to keep topology intact and thus rely on fixed noise schedules with explicit timesteps. This gap motivates unconditional graph denoisers that can absorb discrete, structured noise without extra inputs.
Noise Types in GDMs. GDMs employ tailored noise processes. Early works injected Gaussian noise into adjacency and features 17 211 but this disrupts sparsity. Discrete categorical noise 13, as in DiGress 71. better preserves graph structure. Latent- approaches, notably hyperbolic diffusion, capture hierarchy efficiently (22). Recent variants include categorical flips (71. permutation invariant multinomial noise [21], Bernoulli edge flips [1], discrete- -ime Poisson processes [16), and Beta- distributed noise (3). Yet all methods still pass explicit timestep input. We argue that denoisers can implicitly infer structured noise levels during generation.
3 Problem Setting and Preliminaries
Graph Diffusion Models (GDMs) generate realistic graphs via a forward process that iteratively corrupts an input graph with noise, followed by a reverse process that learns to undo this corruption, sampling new graphs from noise. We examine whether the reverse step truly needs explicit knowledge of the current scalar noise level at each individual denoising timestep during generation.
Graph Definition. We consider an undirected graph G = (V, E), where V is the set of n = | nodes and E is the set of edges. The initial, clean graph structure is represented by its adjacency matrix Ag E {0, 1] joxn, Node features, if present, are denoted by X, E RRaxdy where dy is the feature dimensionality. Our theoretical development primarily focuses on structural diffusion, with extensions to coupled structure and feature corruption discussed in Section 5) We use A, and X, for the noisy adjacency and feature matrices at diffusion step I, respectively, with Åg Ao and Xo Xo. The total number of diffusion steps is T.

---

Forward Process. The forward process introduces sequences of noisy graph states (A.T and noisy feature states (X,) (if features are considered). Graph structure is commonly corrupted using the Bernoulli edge-flipping model. At each step t, every potential edge e is independently perturbed. Given the state of an edge A (e) at step 1, its state at step Ac(e), drawn from:
Ac(e))A(1((e) ~ Bernoulli (11 (1- ((1-3,),,,(())) B Ae-1
Here, 8e E [0, 2 is the per-step flip probability for edge e. The sequence (3e forms a noise schedule that typically increases with t. Under this channel, Ar approaches an Erdös Rényi graph with 2/ in the marginal sense; the exact recursion and a sufficient convergence condition are given in Appendix | When node features X, are present, they are corrupted in parallel (e.g., Gaussian or structured noise). In Section 5 we introduce coupled model where structural and feature perturbations are correlated; further details appear in Appendix
Reverse Denoising Process and Training Objective. The fundamental aspect of the GDM the reverse denoising process, which learns to reverse the forward corruption. This involves denoising function fa. often a Graph Neural Network, parameterized by 9. It takes noisy graph A, (and potentially X₂) as input. Conventionally, fe is explicitly conditioned on the noise level or timestep t, i.e., fo,,,, t). Its objective is to predict a cleaner graph version, such as Ao. A or the noise itself. For instance, to predict Ag. fo(A,, t) is trained to approximate Ag- Parameters 0 are optimized by minimizing an expected loss. For the Bernoulli adge-flipiig model targeting Ag, a common loss the sum of per-edge Binary Cross-Entropy (BCE) losses:
[())= IE Ao- A. Ad
Σ SoC ()))
is the conditional probability from the where Pdata is the true graph distribution and o(A,|Au,? t) forward process.
The Central Question: Necessity of Explicit Noise Conditioning. A prevalent assumption in GDM design is that the denoiser fa requires explicit noise level f input to perform well at every corruption stage X 99, thus formulated as (A l). Our work questions this necessity for GDMs. We hypothesize that a model (A,) can implicitly infer the noise level from the corrupted graphs A, 's structure and attributes, for discrete graph data under structured noise. Addressing this simplifies GDM architectures, reduces parameters, and improves efficiency without sacrificing quality.
Notation. We use M := (2) as the total number of potential edges in a graph with n nodes, and |E] for the realized edge count. All theoretical rates are stated in M; when density is nearly fixed in synthetic settings, [E] ((M) so slopes are equivalent.
4 Key Theoretical Results
This section develops a theoretical framework to rigorously analyze the consequences of omitting explicit noise-level conditioning in Graph Diffusion Models (GDMs). Focusing primarily on the Bernoulli edge-fippiig noise model (Section and its coupled structure-attribute extensions, we aim to demonstrate that for sufficiently large graphs, the noisy graph structure inherently encodes adequate information for the denoiser to infer the noise level, rendering explicit conditioning unnecessary. We establish this by proving three interconnected theoretical results. Unless specified otherwise, all expectations and variances herein are with respect to the forward corruption process (Section 3).
Roadmap Our theoretical investigation unfolds through three main results establishing a formal link from local noise level uncertainty to global generation performance. First, Edge-Flip Posterior Concentration (EFPC) shows the corruption rate's posterior concentrates (variance O(M-))) making the noise level inferable. Second, Edge-Target Deviation Bound (ETDB) demonstrates that omitting explicit noise level input yields an expected squared error in the denoising target also scaling as OM- Third, Multi-Step Denoising Error Propagation (MDEP) bounds the total reconstruction error over I reverse steps by O /M) (errors do not compound catastrophically).
3

---

Assumptions Our analysis relies on key assumptions (rationale in Appendix A Briefly, these are:
A1 Degree Condition. Graphs satisfy constraints on node degrees (e.g., bounded Amax or power-law P(k) & k- with a > 2).
A2 Global Lipschitz Regularity. There exists constant Lmax 1 7 with 7) 1 such that (i) the learned denoiser fe is Lmax -ipschitt with respect to its graph input at every reverse step; (ii)
the ideal conditional target / + u == E[Ao År, I] is also Lmax-Lipschitz.
A3 Prior Regularity. The prior
noise parameters is continuously differentiable and bounded, ensuring well-defined Fisher information
A4 Model Capacity and Optimization Quality, The trained GDM achieves a per-component Mean Squared Error (MSE) in single reverse step on the order of O(M-)).
4.1 Edge-Flip Posterior Concentration (EFPC)
EFPC establishes noise level inferability from corrupted graph. For clean graph Ao under Bernoulli edge-flipping (rate 31), the noisy graph A, contains sufficient information to estimate Br, based on its statistical properties like edge differences or global statistics dependent on 3.. EFPC formalizes that the flip rate's posterior distribution concentrates sharply around its true value with increasing graph size, implying A, encodes substantial corruption level information.
Theorem 4.1 (Edge-Flip Posterior Concentration (EFPC)). Consider a graph Ag corrupted by the Bernoulli edge-flipping process (Section 3). resulting in noisy graph Å step t with true flip rate Se. Let K be the number of edges in A, that differ from Ag- Under Assumption A3 Prior Regularity), the variance of the posterior distribution p(3)K) (or more generally, p( if inference relies on other statistics of A, beyond just K) of the flip rate 3 satisfies:
Var Varg~p(B1 (~ [3] O(M
Theorem 4.1 arises from Bayesian principles: the M potential edges offer multiple, largely indepen- dent observations regarding the flip rate 3, This allows the posterior p(3).A,) )) to sharpen around the true Be as M increases, with the ((M-) variance being characteristic. Under Assumption A3 the Bernstein-von von Mises theorem [25 yields a more precise rate and confirms asymptotic normality for p(3) A.). The variance refines to (detailed derivation in Appendix B
[ar[ 3. 3x) + {(
For scale-free graphs (Assumption A1 with P(k) x km 2), degree heterogeneity alters the effective number of independent observations, modifying the concentration rate to (see Appendix FF:
(ar A.) = (a-2221)1(--1)))
4.2 Edge-Target Deviation Bound (ETDB)
Given EFPC (Theorem 1.1 that the noise level Br is inferable from the noisy graph Å., we quantify the impact of omitting explicit noise level f on the denoiser's single-step objective. We define pooond E E[Ag] A,, as the optimal Bayesian estimate of clean graph Ag (given A, and timestep t), and üt E AE[AAl Ar] as the estimate with implicitly inferred (averaging over p(t) A.)). ETDB measures their expected error.
Theorem 4.2 (Edge-Taree Target Deviation Bound (ETDB)). Under Assumption A2 (ii). the expected squared Frobenius norm of the deviation between p and T4 is bounded:
[ pond
Fu 1 O(M
The ETDB (Theorem 4.2) results from EFPC (Theorem 4.1)p. which guarantees minimal posterior uncertainty about the variable t for large parameter M. If the function pooond is Lipschitz continuous in (a regularity ensuring small changes in t cause proportionally small changes in the target, as reflected by Assumption A2 for the leamed denoiser). then this minimal uncertainty in t translates to an ( deviation in the denoising target. Intuitively, an unconditional model's one-step prediction is almost as good as conditional model's 's because the large number of edges provides a precise estimate of the noise level, making the two outputs differ only slightly(detailed proof in Appendix C

---

4.3 Multi-Step Denoising Error Propagation (MDEP)
While ETDB (Theorem 4.2) addresses single-step errors, MDEP analyzes deviation accumulation over a T-step reverse trajectory when omitting noise conditioning. Let Ao be the graph from T-step unconditional sampler (from noise År), and define Aj as the ideal graph from a perfectly noise-conditioned sampler.
Theorem 4.3 (Multi-Step Denoising Error Propagation (MDEP)), Consider a T Tteep denoising
Denoiser, with Tmaa = 1 " < 0.2) and Assumption A4 (Model Capacity, implying maximum single-step target deviation 8 = O(M from ETDB), the Frobenius norm of the difference between the generated graph Ao and the ideal graph Ag bounded:
sampler. Under Assumption A2
||A6 Aoll F S
mmax O(TM-
Lmax
The O(TM-1) bound shows linear error accumulation with steps T. This is due to Assumption A2 (Lmmx a nearly non-expansive denoiser). The prefactor (L 11)(( - 1) is O(T) for Lmax near 1. This linear growth, combined with ((M-1) single-step errors, ensures manageable total error that diminishes for large graphs (M)ddetailed proof in Appendix D
Remark. The theoretical results Desults-EFPC (Theorem (.1). ETDB (Theorem 4.2 and MDEP (The- orem 4.3 form coherent argument: The noise level is inferable from the noisy graph (EFPC). Consequently, omitting explicit noise conditioning leads to minor single-step target deviation (ETDB). Crucially, these small errors accumulate linearly over the generative process (MDEP). This suggests that for large graphs (M), explicit noise-level conditioning is not critical for effective GDMs, allowing simpler, f-free architectures (explored empirically in Section 6).
5 Coupled Structure-Feature Noise Model
Our analysis in Section assumed independent structural noise on A. Yet social, biological, and infor- mation networks often exhibit coupled structure-attribute dynamics: node-level changes frequently coincide with edge updates 29) Modeling this coupling vital both for faithful data representa- tion and for practical aims, such as improving GNN robustness to joint perturbations 30 32 and building contextual stochastic block models that encode such correlations [33 35). Accordingly,
we introduce a coupled Gaussian noise model that explicitly parameterizes structure struture-feature corre- lations, extending the independent-nove setting and enabling a finer test noise conditioning in attribute-aware graph diffusion.
5.1 Coupled Gaussian Noise Process
We model correlated feature and structural perturbations using shared latent random vectors 7)s E Rd ~ ~N lay) for each node i (where dy is feature dimensionality), independent structural noise term Eij ~ (o, 1) for each potential edge (i,j), and coupling coefficient [0, 1]. Given dime-dependent noise scales x (1) for features and (1) for structure, the clean features X; (from initial features Xo) and clean adjacency entries Aij (from initial adjacency An) are corrupted at step t to their noisy counterparts (t) and (t)(t) as follows:
+ T 2/dd 92
x,(t= xx Th. Á,1(t) Auj (at(t)
The shared latent vector ? creates the dependency between feature and structural noise, with ?y controlling its strength (7 implies independence). The Eıj term ensures idiosyncratic structural randomness. The joint perturbation vector, combining vectorized Á()) and {(), follows a multi- variate Gaussian distribution. Its covariance matrix Σ(I,7) depends on a ((), x (l), 7, and graph incidence structures. The total dimensionality of this joint noisy data (structure and features) D M + dy, where M (2) is the number of potential edges for nodes.
5

---

5.2 Theoretical Guarantees for the Coupled Model
Under the coupled Gaussian framework, we extend our previous theoretical results. These demonstrate that noise level inferability and the limited impact of omitting explicit noise conditioning persist even with correlated structure and feature noise. Let 0 = (3, Y ax ..) denote the noise process parameters, where 3 can relate to parameters of an underlying discrete structural corruption if this Gaussian model is an approximation or extension.
Theorem 5.1 (Joint Posterior Concentration (JPC)). For the coupled Gaussian noise model, with total data dimensionality D M + n n.dy, dj, and coupling coefficient Y [0, 1], the posterior variance of the noise process parameters ON = (3,7, xx A), given the noisy graph structure At and noisy features X,, satisfies:
Ox X,) = -.
As the total data dimensionality D increases, the noise parameters can be jointly inferred with increasing accuracy. As y 1, covariance matrix Σ(t,7) may become singular. Analysis can proceed via projection onto its non-degenerate subspace, preserving O(D-) rates but potentially with larger constants. In Section we varied over the interval [0, 0.99) during empirical validation.
Next, we bound the deviation in the denoising target when explicit noise information is omitted for the joint structure-feature space, Let ffodd = B[(Ao, X X., 4] be the optimal Bayesian estimate of the clean graph structure Ao and features Xo given the noisy data and true timestep I.
Similarly, let t4 = [(o, [o)| X.) be the estimate without explicit t.
Theorem 5.2 (Joint Target Deviation Bound (JTDB)). Under Assumption A2 [i) applied the ideal conditional target and Theorem 3.7 the expected squared Frobenius norm of the deviation between the conditional target (sg pugoud and the unconditional target (1t for the joint data (A, X) is bounded by:
14 cond
pe 1u = O(D-1)
The impact of omitting noise-level conditioning on the immediate denoising target remains minimal even with coupled noise, scaling inversely with the total dimensionality D.
Finally, we analyze the propagation of these errors over multiple denoising steps. Let (Ao, Xo) be the output of T-step unconditional sampler and (Ag, X5) be the output of an ideal conditional sampler.
Theorem 5.3 (Joint Multi-Step Error Propagation (JMEP)). Consider a T -tep denoising sampler for the coupled model. If the single-step larget deviation (characterized by JTDB, Theorem 5.2 d = O(D-1) ) for each step i, and the reverse operator sutisfies a Lipschitz condition La Lmmax (Assumption[A2) then after T reverse steps, the cunulative error between the unconditional generation (Ao, Xo) and the ideal conditional generation (Ag, Xτ) is bounded by:
||Ab - AolLE + +|Xx Xoll= OT /D).
Here, I1
l| denotes an appropriate edge-wise norm (e.g., Frobenius norm on the adjacency matrix difference) and || || is the Frobenius norm for feature differences.
JMEP (Theorem 5.3)
demonstrates that, similar to the structure-only case, errors in the unconditional coupled model accumulate linearly with the number of steps T and diminish with the total graph
dimensionality D. Detailed proof's for Theorems 5.1 5.2 and 5.3 are provided in Appendix E
6 Empirical Validation of the Theoretical Framework
This section empirically assesses the theoretical framework developed in Section 4 and 3 We first validate the predicted scaling laws for EFPC, ETDB, MDEP, and their coupled counterparts (JPC, JTDB, JMEP) using synthetic graph data. Subsequently, we evaluate the practical performance of t- free GDMs on real-world graph generation benchmarks. For synthetic experiments, Erdös-Rényi [36] or Stochastic Block Model (SBM) 37 graphs with n [50, 1.4 10*) nodes are utilized, with default parameters B = 0.2 (edge-flip rate) and = 0.5 (feature-noifs variance). All configurations are repeated times with different random seeds, and we report means with 95% confidence intervals. In addition, we include an industrial-scale case study on soc- soc-Epinionss with node-cap sweep (Nmax E (200, 1000)) to examine large-graph behavior and training choices; the full protocol and results are provided in Appendix

---

6.1 Broad Validation of Theoretical Scaling Laws
We comprehensively test the predicted scaling behaviors across all core components of our theory. [able|[summatte the quantitative comparison between theoretical rates and empirically measured exponents (or constants) for statistics related to each theorem (EFPC/JPC, ETDB/JTDB, and JMEP).
Table I: Summary of empirical scaling exponents and constants (mean + 95% CI over five seeds).
Group
Quantity
Theory
Empirical
R
Var(B Ad) vs. |E] [F]] Var(B A,)
-..0
0.999
EFPC
const 0
0.160
Posterior mean bias
I 2x100
Deviation/edge vs.
-1
0.03
0.998
ETDB
[[ vs. |B|
+1
+1.00=0.01
1.000
Relative error vs. E
-2 0.11
0.997
JPC variance vs. D
-1
-1.00=0.03
0.999
JTDB deviation vs.
-1
0.006
0.996
Coupled (y 0.7) || |Runcoudll 21 vs. 1)
+1
+1.01+0.02
0.999
JMEP error (T - vs. D
-1
0.05 0.995
Interpretation of Scaling Law Validation. Results in Table 1 show excellent correspondence between theoretical predictions and empirical measurements. Empirically derived slopes for scaling rates are within =0006 of theoretical targets, with high coefficients of determination (lypically R2 > 0.995). This precise agreement across diverse ispects-noise rate posterior concentration (EFPC/JPC), single-step target deviation (ETDB/ITDB), and coupled model error propagation (JMEP for T = 4) provides robust initial evidence for our theory's 's soundness. For instance, flip rate 3's posterior variance diminishes as O(E (or O(D ') for JPC), confirming noise level inferability. This accuracy is critical, as these principles underpin subsequent multi-step denoising analysis.
6.2 Multi-Step Error Propagation (MDEP) in Detail
MDEP slopem-1.03
To validate MDEP (Theorem 4.3
which predicts 10-2
how single-step deviations accumulate, we sim- ulated reverse denoising trajectories of varying lengths [4, 8, 16,32, 64] on synthetic graphs with edges [E] ranging from 102 to 10". For each (|E), T)) pair. we recorded ET A,, the cu- mulative Frobenius-norm gap between t-free and t-aware updates, normalized by [E]] for a size- agnostic eтror metric, as shown in Figure
stopes-]
10-1
T-8
10-
Tw32
T-66
MOEP errer
10-
Our empirical findings significantly validate the MDEP theorem. The cumulative er- ror clearly shows a power-law decay with edge count (E),, excellently aligning with the pre- dicted O(E scaling (e.g., slope 1103, n² 0.9998 for Tase = 4). Moreover, the error scales linearly with trajectory length (I"): log-log plots for different T' are parallel, and normalizing by T' collapses data onto single line, confirming the full O scaling. Crucially, even for exten- sive trajectories (e.g.. T 64), this error becomes negligible (< 10 ') for large graphs (EE) 2 10*). This demonstrates that omitting explicit noise con- ditioning incurs a minimal, diminishing cost with increasing graph size, strongly supporting the via- bility of t-free models in Barge-graph scenarios.
Key Insight:
102 107 10a
10
[E]
Figure I: MDEP empirical scaling, Log-log plot: per-edge cumulative error Σ A:/ E vs. edges [E] for various T values. The black dashed line (slope -1.03, R² = 0.9998) for Tosse 4 aligns with the predicted O(M rate (Theo- rem 4.3). since density is nearly fixed in these synthetic settings, |E| x M, so we plot against [E]. All curves are approximately parallel, with vertical offsets proportional T TuTee verifying the O(T/|E)) scaling law.
7

---

6.3 Impact of Structure-Feature Coupling Strength (n)
We then investigated the coupled noise model (Section 5 specifically how the coupling strength between structural and feature noise affects model performance and noise inferability. As shown in we varied y from (independent noise) to 0.99 (highly coupled shared noise component).
Figure 2
(a)
Reconstruction error vs.
(b)
Accuracy vs.
1.000
105000
0.995
100000
Classiftation accurac
0.990
95000
0.985
90000
0.980
85000
0.975
80000
0.970
75000
0.965
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Figure 2: Effect of coupling strength on unconditional model. (a): Total reconstruction error e (b): Node classification accuracy. Shaded bands indicate 95% CI over ten trials. Stronger coupling improves both reconstruction and downstream task performance.
Al - Aolla + I1 Xulle.
Key Insight: Increasing the structure-feature coupling strength (7) empirically improves uncon- ditional model performance. Specifically, as increases from O to 0.99, total reconstruction error decreases substantially (~40%), and downstream node classification accuracy improves (from ~94% to over 97%). This suggests that shared noise, potentially through robust joint signal from shared la- tent component 7/s effectively aligns feature and structure channels, enhancing overall signal-to-non ratio. While theoretical results (JPC & JTDB) predict posterior uncertainty about noise parameters decays as ODD-1 irrespective of < 1, our empirical findings indicate stronger coupling aids noise inference. This underscores key takeaway: omitting explicit conditioning coupling strength (or timestep f) within the coupled noise model does not degrade and can even enhance performance.
6.4 Performance of I-free Models on Real-World Graph Generation
Experimental Setup. We used QM9 38 dataset of 133,885 small organic molecules, for evalu- ating molecular graph generation. Metrics included chemical Validity (fraction of valid molecules generated), Uniqueness, Novelty, and fidelity of structural distributions (mean ring count, mean molecular weight). The second benchmark was soc-Epinionsl [39], larger social network from the SNAP dataset, used evaluate structural reconstruction fidelity. Metrics included subgraph Validity, Uniqueness, basic structural statistics (average nodes and edges), and Maximum Mean Discrepancy (MMD) for degree, clustering coefficient, and triangle distributions (more details in Appendix H). We benchmarked two GDM architectures, DiGress ( and GDSS [17] under three variants:
learnable embedding of the timestep. t-free: Models trained without any timestep conditioning.
t-aware: Standard models explicitly conditioned
t-free (warm): t-free models initialized from pre-trained t-aware weights and then fine-
tuned without timestep embeddings.
Beyond the main tables, we also conduct industrial-scate evaluation on soc-Epinionsi using induced subgraphs with Nmax E (200, 1000} and report validity and the change in MMD when increasing N (negative indicates improvement); the complete results appear in Appendix
Table g
Analysis of Real-World Performance. Summarizing our key findings succinctly, Table reveal that i-free variants typically deliver comparable or superior generative quality their T-aware counterparts, coupled with clear computational advantages (up to 19.9% parameter reduction for

---

GDSS and speedups of 8-9%). We now highlight specific conditions under which explicit time conditioning remains beneficial, guided by detailed insights from our experiments:
Graph Scale and Signal Strength. Small or sparse graphs provide limited statistical signals (as evidenced Loc-Epinions1 with maximum number of nodes Nmax 50 (Table where initial validity was modest, e.g., 25.44% for GDSS t-aware). Increasing the graph scale to Nmax = 200 (Table drastically improved validity 100% across GDSS variants. Explicit time conditioning thus offers clear advantages in low-information scenarios, bridging the gap where implicit noise inference (predicted by EFPC theory) struggles due insufficient statistical signals. Sehhitecttue-Speciiie Sensitivity. DiGress models demonstrated significant sensitivity to the removal of explicit time conditioning, particularly evident in the sharp validity drop for Di- Gress t-free(warm) (from 100.00% 23.67%). This highlights key architectural consideration: transformer- based models using discrete diffusion processes appear heavily reliant on explicit time embeddings due learned transition probabilities and attention mechanisms. Conversely, SDE- based models like GDSS exhibit greater robustness in transitioning to unconditional generation.
Optimization and Training Stability. Training from scratch revealed challenges, with t-free GDSS models reaching full validity but slightly lagging in structural metrics compared to their warm-started or explicitly conditioned counterparts (e.g., on soc-Epinionsl, GDSS I-free from scratch yields MMDoveell = 0.72 vs. 0.66 for the warm-started variant). Explicit conditioning simplifies optimization by providing guidance noise levels, suggesting crucial role in achieving stable convergence, particularly in architectures less adept at implicitly inferring noise dynamics.
In summary, although our results strongly endorse the simplicity and efficiency of L-free models, explicit conditioning still remains valuable, especially in small low-signal graphs, architectures heavily reliant on learned embeddings, and scenarios demanding greater training stability. These insights provide guidance for practitioners when t-free suffices and when conditioning preferable.
Table 2: Generation results for QM9 and soc- soc-Epinions] datasets. Metrics are mean + 95 % CI over five seeds. "Params" in millions; "Time" is per-epoch on one NVIDIA L4 GPU.
QM9 Dataset
Model / Variant
Valid %
Unique
Novel %
MW mean
Params
Time
DiGress t-aware
99.98110011
4.76
100.00 0.00
145.37.10.03
13.16
47.82
DiGress t-free
99.99-10.01
4.65=0.08
100000=0.00
149.74=0.01
12.65
48.16
DiGress (-frre((wrrm)
99.96:10.01
5.09:0.12
100.0010.000
147.46:10.02
12.65
48.23
GDSS t-aware
92.32:10.19
81.08=0..1
99.09=0.00
95.00=:0.12
1.89
9.56
GDSS t-free
94.00-10.09
89.60-10.20
99.99-10.00
99.23-10.17
1.79
8.78
GDSS t-free(warm)
92.57=00.03
88.46+00.1
99.99=0.00
97.74
1.79
8.78
soc-Epinions1 Dataset
Metric
DiGress
DiGress
DiGress L- free(warm)
GDSS
GDSS (-free
GDSS
L-aware
I-free
(-aware
free(warm)
Valid %
10..0011..00
99.8311..27
23.67-12.08
25.44111.22
33.36:11.43
48.00-11.99
Unique %
100000+-0.00
100.00--0.00
100.00-0.000
94.68+1.40
9..51++1.59
09.91
Avg Nodes
50.00:10.00
50.00.10.00
50.00-10.00
31.11:1.25
36.97:10.81
44.6 44.64
Avg Edges
291. 006:
281.39-100225
270.05:10.12
503.57-132.42
529.06:1 15.64
670.82-116.33
MMD
0.46:E0.00
0.41
0,40=:0.01
0.76+10.00
0.66:10.01
0.69:10.01
MMD
0.71-10.00
0.69
0.68-10.01
0.70.10.01
0.70.10.01
0.39
MMD
0.41++0.00
0.38+00.0
0.37=+0000
0.80++0.02
0.82++0001
0,90+00.00
MMDoveralt
0.53:10.00
0.49110.00
0.48:10.00
0.76100.0
0.72110.00
0.66110.00
Params (M)
1.355
1.322
1.322
0.251
0.201
0.201
Time
6.97
6.95
6.96
1.71
1.55
1.55
Conclusion
This work challenges the necessity of explicit noise-level conditioning in Graph Diffusion Models (GDMs). We provide strong theoretical and empirical evidence that this conditioning often unnecessary for effective graph generation. Our theoretical framework (EFPC, ETDB, MDEP)

---

proves noise levels are implicitly inferable from corrupted graph data, showing negligible error (O(M single-step. O(T/M) cumulative) when omitting conditioning. Comprehensive empirical evaluations corroborate these predictions. Unconditional GDSS and DiGress variants matched or surpassed conditioned models in quality on diverse datasets. They also proved more efficient, reducing parameters (4 6-6% and computation time (8-10%).
These findings support our thesis: graph data's high dimensionality enough for denoising without explicit noise levels, enabling simpler yet equally powerful and efficient GDM architectures. Although this study provides robust foundation, promising directions include adaptive coupling, scaling to larger graphs, and novel sampling strategies. We believe this work offers solid basis, theoretically and practically, for designing the next generation of simpler and more efficient GDMs.
Acknowledgments and Disclosure of Funding
Work in the paper is supported by, NSF ECCS 2412484, NSF ECCS 2442964 and NSF GEO CI 2425748.
References
[1] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances neural information processing systems, 34:8780-8794, 2021.
[2] Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. Wavegrad: Estimating gradients for waveform generation. arXiv preprint wrXiv:2009.007// 2020.
[3] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint arXiv:2009 09761, 2020.
[4] Shitong Luo and Wei Hu. Diffusion probabilistic models for 3d point cloud generation. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pages 2837-2845, 2021.
[5] Minkai Xu, Lantao Yu, Yang Song, Chence Shi. Stefano Ermon, and Jian Tang. Geodiff: geo- metric diffusion model for molecular conformation generation. arXiv preprint arXiv:2203.02923, 2022.
[6] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems, 36:3706-3734 1301,,3312222 2023.
[7] Clement Vignac, Igor Krawczuk, Antoine Siraudin. Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
[8] Jonathan Ho. Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
[9] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-hased generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456 2020.
[10] Qiao Sun, Zhicheng Jiang, Hanhong Zhao, and Kaiming He. Is noise conditioning necessary for denoising generative models? arXiv preprint (XXi:22502.13129, 2025.
[11] David Heurtel- Deppiges, Charles C Margossian, Ruben Ohana, and Bruno Régaldo-Saint Blancard. Listening to the noise: Blind denoising with gibbs diffusion. arXiv preprint 19455 2024.
[12] Subham Sahoo, Aaron Gokaslan, Christopher M De Sa, and Volodymyr Kuleshov. Diffusion models with learned adaptive noise. Advances Neural Information Processing Systems, 37: 105730-105779,
10

---

[13] Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces, arXiv preprint arXiv:2210.01549, 2022.
[14] Alex M Tseng, Nathaniel Diamant, Tommaso Biancalani, and Gabriele Scalia. Graphguide: interpretable and controllable conditional graph generation with discrete bernoulli diffusion. arXiv preprint arXiv:2302.08 302.03990 2023.
[15] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-space statesspaces. Advances in neural information processing systems, 34:1 19911-19933, 2021.
[16) Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffusion for graph generation. Advances in Neural Information Processing Systems. 37:79704-79740, 2024.
[17] Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International conference on machine learning. pages 10362-10383. PMLR, 2022.
[18] Jaseha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256-2265, pmlr, 2015.
[19] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In International conference on machine learning, pages 8867-8887. PMLR, 2022.
[20] Joshua Batson and Loic Royer. Noise2self: Blind denoising by self-supervision. International conference muchine learning, pages 524-533. PMLR, 2019.
[21] Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International conference on artificial intelligence and statisties, pages 4474 4484. PMLR, 2020.
[22] Lingfeng Wen, Xuan Tang, Mingjie Ouyang. Xiangxiang Shen, Jian Yang, Daxin Zhu, Mingsong Chen, and Xian Wei. Hyperbolic graph diffusion model. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15823-15831, 2024.
[23] Xinyang Liu, Yilin He, Bo Chen, and Mingyuan Zhou Advancing graph generation through beta diffusion. arXiv preprint arXiv:2406.09:: 09357, 2024.
[24] Jorma J Rissanen. Fisher information and stochastic complexity. IEEE transactions on information theory, 42(1):40 2002.
[25] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[26] Tom AB Snijders, Gerhard G Van de Bunt, and Christian EG Steglich. Introduction to stochastic bcser models for network dynamics. Social networks, 32(1):44-60, 2010.
[27] Yuanzhao Zhang, Maxime Lucas, and Federico Battiston. Higher-order interactions shape col- lective dynamics differently in hypergraphs and simplicial complexes. Nature communications, 1461):1605, 2023.
[28] Christian Steglich, Tom AB Snijders. and Michael Pearson. 8. dynamic networks and behavior: separating selection from influence. Sociological methodology, 40(1):329-393, 2010.
[29] Márton Karsai, Gerardo Iniguez, Kimmo Kaski, and János Kertész. Complex contagion process in spreading of online innovation. Journal of The Royal Society Interface, 11(101):201 (11101)20140069,
2014.
[30] Xiang Zhang and Marinka Zinik. Gnnguard: Defending graph neural networks against adversarial attacks. Advances in neural information processing systems, 33:9263-9275. 2020.
11

---

[31] Jiate Li, Meng Pang. Yun Dong, Jinyuan Jia, and Binghui Wang. Provably robust explainable graph neural networks against graph perturbation attacks. arXiv preprint arXiv:2502.0444 042244. 2025.
[32] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu, Ad- versarial examples on graph data: Deep insights into attack and defense. arXiv preprint arXiv:1903.01610, 2019.
[33] Shuwen Chai and Miklós Z Rácz. Efficient graph matching for correlated stochastic block models, Advances in Neural Information Processing Systems, 37:1 16388-116461, 2024.
[34] Olivier Duranthon and Lenka Zdeborová. Optimal inference in contextual stochastic block models. arXiv preprint arXiv:2306.0733 07948, 2023.
[35] Kang Sun, Liqing Qiu, and Wenxiu Zhao. Aegraph: Node attribute-enannced graph encoder method. Expert Systems with Applications, 236: 121382, 2024.
[36] Paul Erd6s and Alfréd Rényi On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17-61, 1960.
[37] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 109-1379 1983.
[38] Raghunathan Ramakrishnan, Pavlo Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
[39] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):-es, 2007.
[40] Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24(3):234-24 2004.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state the contributions that are proved in Sec-
tions 5 and 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section lists four concrete simitations-scope of the theoretical noise models, strength of Lipschitz/near-optimaall assumptions, untested performance on web-scale heterogeneous graphs, and architecture-depender warm-start sensitivity and explains why each remains an open question.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are listed in Section 4 full proofs appear in Appendix B Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper ?
Answer: [Yes]
Justification: Appendix H and G details preprocessing, hyper-parameters, random seeds, and commands replicate every experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code ?
Answer: [Yes]
Justification: We uploaded the paper with code, data scripts, and one-command reproduction scripts for every experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https PoooeeSubiissionooll1.
//iips.c/ppll wwtpp//wwccgg.udeeeeeeeopeppeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details ?
Answer: [Yes]
Justification: Data splits, optimizer choices, LR schedules, and early-stopping rules appear in Appendix H and
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably ?
Answer: [Yes]
Justification: All key figures and tables show mean 95% Cls over five seeds; computation method explained in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on com- puter resources ?
Answer: [Yes]
Justification: Appendix and G lists hardware, per-epoch runtime, and total GPU-hours for each run.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform ?
Answer:
[Yes]
Justification: The work only publicly available datasets and human animal subjects, fully complying with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focuses on foundational theory and empirical validation of graph diffusion models; societal impact analysis is considered outside the scope of this submission and therefore omitted.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place ?
Answer: [NA]
Justification:
Released models are moderate in size and pose negligible dual-use risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets properly credited ?
Answer: [Yes]
Justification: The creators or original owners of the assets used in the paper, such code, data, and models, have been appropriately recognized, and the licenses and terms of use have been clearly mentioned and properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi www.we..tcc....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
17

---

Question: Are new assets introduced in the paper well documented ?
Answer: [NA]
Justification:
The paper releases no new dataset pretrained model.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects ?
Answer: [NA]
Justification:
No human or crowdsourcing data were involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks and whether Institutional Review Board approvals were obtained?
Answer: [NA]
Justification: Not applicable-no human-subject research performed.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage L.LMs
Answer: [NA]
Justification: LLMs were used only for minor proofreading and formatting; they are not part of the research methodology.
Guidelines:
The answer NA means that the method development in this research does
involve L.LMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : /ttp:://n.uii...m http//uurpp.cc//offeeeeeeeee /cC//ooeeeeencce/22255555 for what should or should not be described.
18

---

A Detailed Assumptions and Rationale for Theoretical Framework
This appendix provides detailed statement and justification for the assumptions underpinning the theoretical framework developed in Section 4 of the main paper.
Formal Statement of Assumptions
To ground theoretical analysis, we make the following four key assumptions:
A1. Degree Condition.
The graph G = (V, E) under consideration is assumed to satisfy one of the following conditions regarding its node degrees:
(a) The maximum node degree, maxx - max.ev deg(v), (v), ), is bounded by a constant, that is,
max
(1).
(b) The graph has a power-law degree distribution P(k) x k- with a decay exponent a > Further discussion is provided in Appendix
A2. Global Lipschitz Continuity of Denoiser. Fix constant Lmax + 7) with small 1) 0.
We require both the following Lipschitz conditions to hold:
(i) Learned denoiser. For any two graph inputs G1, G2 and suitable graph norm ||-I|,
[[ fo(G2))l s Lmmxx ||G G2ll-
(ii Ideal conditional target. Let po = E[Ao A,, t| (or the joint (Ao. in the coupled case). Then for any two noise levels & t2
|
coud
U4z
cond
S Lmxx 14 - 12/-
This single assumption supplies the non non-expansive property needed in MDEP 4.3 (via (i) and
the target smoothness used in ETDB 4.2 JTDB 5.2 (via (ii)).
A3. Prior Regularity Noise Parameters. For noise models with explicit parameters (for example, a Bernoulli edge-flipping rate (), the prior (B) is twice continuously differentiable on the interior of its domain and strictly positive on compact subsets. Concretely, if (0, 1) then for B E [e, - with fixed e, > 0.
c S π (B)
A4. Model Capacity and Optimization Quality. The Graph Diffusion Model is assumed to achieve per-component mean- -squrred eиror that scales as O(M (M. where M the number potential edges, when predicting the clean graph signal (or the noise) at each reverse step.
Rationale for Assumptions
The assumptions stated above are foundational our theoretical derivations and are justified as:
Assumption A1. (Degree Condition)
This assumption allows our analysis to cover a wide spectrum of graph structures. Part (a), bounded maximum degree, is characteristic of many real-world networks such molecular graphs or certain types of citation networks where connectivity is inherently limited. Part (b), power-law degree distributions with a 2, enables the framework to apply scale-free networks, which are ubiquitous in social, biological, and information systems. The condition a >> 2 ensures finite mean degree, common property even in heterogeneous networks. The distinct scaling behaviors that can arise in scale-free networks are further detailed in Appendix FF
Assumption A2. (Global-Lipschite Denoiser)
This unified condition has two roles. (i) Learned denoiser. bounded Lipschitz constant prevents small single-step errors from exploding along the T reverse updates. If fo were highly non-Lipschitz
Lmax > those errors could grow exponentially, yielding unstable or divergent trajectories. Keeping Lmax ~ 1 (e.g.. 1 1+ 1) with small 17) guarantees at most linear error accumulation, as required by the MDEP analysis. Architecturll tricks such residual blocks, layer normalisation, bound in practice. (ii) Ideal conditional target. We also need the mapping + p to vary
spectral normalisation help enforce this
smoothly that the posterior uncertainty in (captured by EFPC 4.I. 5.1 translates
19

---

For common noise schedules, goond is differentiable and its derivative is bounded, giving a Lipschitz constant of the same order as that of fa. With both parts bounded by shared Liaxx the theory cleanly links single-step target bias to multi-step error growth, while keeping notation compact.
into an O(M-l) target deviation (ETDB 4.2 JTDB 5.2)
Assumption A3. (Prior Regularity)
This assumption is standard in Bayesian asymptotic theory (e.g.. for the Bernstein-von Mises theorem). It ensures that the prior distribution does not pathologically concentrate mass the boundaries of the parameter space (e.g., at 3 = 0 or / for flip rate), which could lead issues like infinite Fisher information ill-defined posterior distributions. A smooth, bounded prior allows for stable inference and well-behaved asymptotic approximations of the posterior.
Assumption A4. (Model Capacity and Optimization Quality)
This assumption bridges the gap between the ideal Bayesian denoiser (which our theory often analyzes as an intermediate step) and the learned denoiser fa. It posits that with sufficient model capacity and effective training, the learned denoiser can approximate the ideal target well enough such that its single-step prediction eπror diminishes as the graph size (and thus the amount of information) increases. The O(M-1) scaling for this error is optimistic but reflects a scenario where the model effectively learns from the available data. This assumption is essential for the practical relevance of the derived multi-step error bounds (MDEP and JMEP).
B Detailed Proof for Edge-Flip Posterior Concentration (EFPC)
This section provides detailed derivation for the Edge-Flip Posterior Concentration (EFPC) result, which was formally stated as Theorem 4.1 in the main text. For clarity and self-comtaimment within this appendix, we restate the theorem.
Theorem B.1 (Edge-Flip Posterior Concentration (EFPC)), Lei Ao E (0, 1)mxn be the adjacency matrix of an undirected graph with set of M = =()) potential edges, denoted Epot Let A, be the noisy graph observed at diffusion step generated by independently flipping each potential edge E Eoot from its state in Ag with true, unknown probability Be 10,
Pr(Ac(e) + Ao(e)] 3r,
Ve Expot-
Let X = 1(A((e) + Ao(e)} be the total number of observed edge flips. Assume a prior distribution x(3) for the flip rate 3 (which is our inferential target representing 3¹). This prior (B) is continuously differentiable and strictly positive any compact subset of its domain (0, 1), satisfying A3 posterior distribution of 3 given is p(3 X) x L(X M,3)=(3) 3x M- -x (3)). This posterior distribution satisfies:
Var = O(M
Furthermore, the leading constant of this variance is determined by the true flip rate Be, such that:
(1 3e)
+ +)M
M
Proof. The proof is structured into three main stages to rigorously establish the theorem's claims:
1. Concentration of the Sufficient Statistic: We demonstrate that the total number of observed edge flips, X, which a sufficient statistic for B, concentrates sharply around its expected value.
We analyze the posterior variance Var[3 X). This is first done by assuming Beta conjugate prior to derive an exact analytical form for the variance. We then generalize this to show that the (MM-1) scaling holds for any sufficiently smooth prior π x33 by applying Laplace's method for posterior approximation.
Posterior Variance Analysis using Conjugate Priors and Laplace's Method:
Asymptotic Normality and Refined Rate via Bernstein-von Mises Theorem: Finally, we employ the Bernstein-von Mises theorem to formally establish the asymptotic normality of the posterior distribution. This allows for precise determination of the leading constant in the ((M-1) variance term, linking it directly to the Fisher information.
20

---

Step 1: Concentration of the Sufficient Statistic X. Given that each of the M potential edges flips independently with the true probability St. the random variable X, representing the total number of flipped edges, follows binomial distribution: X ~ Binomial M, Bz). The expectation of X is [[X]= Sr.
To quantify the concentration of the empirical flip rate X/M around 3,, we use Chernoff's inequality, standard bound for sums of independent Bernoulli random variables. For any 0, Chernoff's inequality provides:
Pr[IX/M 3.1 > = Pr[ M3,1 eM] S 2 2exp(-2e²M)
(1)
This bound implies that the empirical flip rate X/M converges in probability to the true rate 3 exponentially fast as M + oc. Thus, for large number of potential edges M, X/M is highly precise estimator of 3t. This concentration fundamental the subsequent Bayesian inference, as
X encapsulates the data's 's information about 3 in the likelihood function.
Step Posterior Variance Analysis. We first consider Beta distribution as a conjugate prior for 8, denoted π (3) } = Beta 3o) with hyperparameters on, fo > 0. The likelihood function for X
given / is L(X M, 3) x 8* (1 B) M- Due to conjugacy, the posterior distribution p( X) is
also a Beta distribution:
3 11X Beta(X + ao; M - X BB))
(2)
The variance of a Beta(a, b) distribution (atb)=(atb+1)- Substituting the posterior parameters
ab
X + ag and b = M - X + Bo. we have:
ao) - X 30)
Varl3 [
(M + + (M + +00 + -00 1)
From Step 1, for large M, X se M, Substituting this into Equation (3)
The numerator is asymptotically (M B.)) M (, 36) O(M), which is (M²)). The denominator is asymptotically M M M O(M3). which is ((M3).
Therefore, Var[3 | X]
O(MS3) O(M-1)
o(M5))
This ( scaling is not limited to conjugate priors. holds more generally for any sufficiently smooth prior π (33 satisfying Assumption A3 (Prior Regularity), as can be shown using Laplace's method for posterior approximation. The log- posttrrti is:
p( x) X log B + (M X) log(1 3) + log x (B) + C,
(4)
where C' is a normalizing constant. Laplace's 's method approximates p(3 X) with Gaussian distribution centered at the posterior mode, Amotee For large M, Amatte converges to the Maximum Likelihood Estimator (MLE), ÊMLE = X/M. The variance of this approximating Gaussian is the negative inverse of the second derivative of the nog-posterior evaluated at the mode:
(-
0 log p(3 IX) 0g2
VaT |8 X|
B Bm
The second derivative is dominated by the likelihood term, ag2 M which evaluates to approximately 3
(X log 3 + (M - logg - 3)) = M(1
M8.
M (1-9.)" (1-3) at the mode (since
[1-8)7,
3mods se 3t). Thus, its negative inverse scales O(M-)) confirming the general scaling of the posterior variance.
Step 3: Refinement of Rate and Leading Constant via Bernstein-von Mises Theorem. To formalize the asymptotic normality of the posterior and to precisely determine the leading constant in the (M-²) variance term, we apply the Bernstein-von Mises theorem (25). This theorem states that, under regularity conditions (satisfied by Assumption A3 and the Bernoulli likelihood), the posterior distribution p(3 X) converges in distribution to a Normal distribution as M oc. Specifically:
V M 3MLE) X 4 N (B.)
(5)
21

---

where BLLE X/M is the MLE of B, and (1t) is the Fisher information for single Bernoulli trial (one potential edge flip), evaluated at the true parameter Br..
The log-likelihood for a single Bernoulli trial Y. E [0. (where Y. = indicates flip) is & (B; Y.) Ye log 8 + Y.) log(1
B). The Fisher information for this single trial is:
(B:
(3) Ey, (errooenl))))((
(6)
0,3
3(1- - B)
For M independent trials, the total Fisher information concerning ,3 is ( = M (B)) = ((1-8))
From Equation (5), the limiting distribution of 3 X is NV( (M -1.(3) Therefore, the asymptotic variance of the posterior distribution p(3 X) is:
1
Bc(1 3c) + {M
Varl3 x] (1,)) +
M
This result not only rigorously confirms the O(M-1) decay rate for the posterior variance but also explicitly identifies the leading constant term, B,(1 Be), which depends on the true underlying flip rate. This is the "sharp rate" referred to in the main text.
The convergence of these three analytical steps- the concentration of the sufficient statistic X, the O(M variance scaling derived from both conjugate prior analysis and Laplace's method for general smooth priors, and the precise asymptotic form and constant factor obtained via the Bernstein-von Mises theorem- coleemcvvoll establishes the proof of Theorem B.1
Extension 1: Robustness to Correlated Edge Flips
The core proof of Edge-Flip Posterior Concentration (EFPC, Theorem B.I assumes that edge flips are independent events across all M potential edges. This extension investigates the robustness the EFPC findings, particularly the ((M-1) scaling of the posterior variance, when this independence assumption is relaxed to allow for local dependencies between edge flip events.
Modeling Local Dependencies. We consider the of indicator random variables (Y= ((x(()) # An(e)))eeF,,.. where Y. = if edge flips. Instead of full independence, as- sume these variables form a dependency graph. In this graph, nodes correspond to the potential edges Epot of the original graph Ag, and an edge exists between two such "edge-nodes" (say, corresponding to é₁ and e2) if the random variables Ye, and Ye, are statistically dependent. We stipulate that this dependency graph has maximum degree A, which is bounded by constant, i.e.. A = O(). This implies that the flip status of any single edge e is directly dependent on at most A other edge flips, thereby modeling scenario of local bounded dependency. The total number of observed edge flips remains X -eeEE Ye.
Concentration under Local Dependency. Even with local dependencies, the sum X can still exhibit strong concentration around its expectation E[X]. While the standard Chernoff bound (Equation (I) for i.i.d. variables may not directly apply, more general concentration inequalities, such Janson's 's Inequality 440, are designed for sums dependent indicator variables.
Lemma B.2 (Concentration Bound for Dependent Flips, adapted from Janson [4)). Let {Ye be a collection of indicator random variables, and let X = E Ye. If these variables form dependency graph with maximum degree A O(),, then under suitable conditions the nature of dependencies and individual flip probabilities pe = Pr(Y. = 1), concentration bounds for X can be derived. common form of such bounds, related Chernoff-type bounds for variables with bounded dependency (e.g., m-dependence), is:
( C1 C2
Pr|
E[X] eM] < exp
-1 f(A)
where C1 is a constant and f(A) ) is some function reflecting the dependency strength, often polynomial in A. For instance. specific form provided in the user's context is:
2:2 M
Pr Pr||X- - E[X] > eM] < 2exp
1 2A
22

---

(The applicability of this specific form depends on underlying assumptions about the dependency structure, often related to notions like Poisson approximation or specific correlation decay.)
Proof Sketch. The detailed proof of Janson's 's Inequality and its variants can be found in Janson [40]. The core idea involves bounding tail probabilities by analyzing the sum of covariances or by using techniques like the method of bounded differences adapted for dependent variables.
Implications for Posterior Variance. The critical insight from applying concentration bounds like
Lemma B.2 is that if A = (1), the sum X still concentrates effectively around its mean E[ This implies that the variance of X. Var(X), while potentially larger than the i.idd case M Br (1 (3) (e.g., it might be scaled by factor related to A), often remains ((M) as long as the dependencies are not pervasive enough to make all variables highly correlated globally. If Var(X) = ( then the empirical flip rate X/M remains consistent estimator of the average underlying flip probability 8 E[X Consequently, the subsequent Bayesian analysis steps, which rely on the concentration of X/M and the behavior of the likelihood function, remain largely valid. The Fisher information structure might be adjusted by factors dependent on A, but the overall O(M-1) scaling for the posterior variance of an effective flip parameter ,3 is typically robustly preserved. The leading constant in the variance may change, reflecting the reduced effective number of independent observations, but the fundamental rate of concentration with M is expected to persist. Thus, the EFPC result demonstrates robustness to certain forms of local, bounded correlations between edge flips.
Extension 2: Robustness to Time-Varying Bernoulli Schedules
The primary EFPC analysis (Theorem B.1 assumes a single, uniform flip probability 3: for all edges given step This extension considers the scenario where the corruption process involves sequence of T steps, each with potentially different flip probabilities {.3.)-m. as is typical in iterative diffusion models. After I such steps, edge e, initially in state Ao(e), transitions to state (r))). Our interest lies in the inferability of an *effective* or *aggregate* noise level that characterizes this multi-step process.
Effective Flip Probability. Let Pe off denote the effective probability that the final state of an edge, (r(e). differs from its initial state, Ao(e), i.e., pef (c) * Ao(e)]. ) The user's text notes specific formula for Pe under a symmetric channel model: Pr = II= (e)),, where (e(e) is the flip probability at step i. This formula arises if (e( is the probability of flipping from state (e) at step and each (1 (e) represents the correlation between A,(e) and A,-1(e). (e) is simply Pr[A((e) * (e) (e)] the cumulative probability (r(Ar(e) & Ae(e)] could be more complex. For this extension, assume that effective, overall probability ye for each edge e can be defined, encapsulating the net effect of the T-step process.
Epot 1(Ar(e) + Ao(e)) be the total count of edges whose final state differs from their initial state. If these effective flip events (Ar(e) A A are independent across different edges but the probabilities yf are non-identical (e.g., due to edge-specifis attributes influencing (,(e), or a non- non-uniform accumulation of noise), then Y is sum of independent. non-identically distributed Bernoulli random variables. Hoeffding's inequality provides a suitable concentration bound.
Concentration for Non-Identical Bernoulli Trials. Let = EeE
Lemma B.3 (Hoeffding's Inequality for Sums of Independent Bounded Random Variables). Ler Y. (ernoulli(pett) be independent random variables for Epor, where peff [0, 1). Let EeeEpo Ye. Then for any e > 0,
Pr|1Y - E[y] > sM] < 2 2exxp(22e2M)
where E|y] Eee Fypst De
Proof. This result a direct application of Hoeffding's inequality, which applies to sums of indepen- dent random variables bounded within an interval (here, Ye [0, 1)).
23

---

Implications for Posterior Variance. Lemma B.3 demonstrates that the total observed count of differing edges, Y. concentrates around its mean E. We can define an average effective flip rate as Peff | (DeE p )/M. The observed fraction of differing edges, Y/M, will then concentrate around this Peft. If the inferential goal is to estimate Pett (or a set of parameters characterizing the schedule } that yield {p. }), then Y/M serves as the empirical data. By applying Bayesian principles similar to those Step and Step of the main EFPC proof (e.g.. Laplace's & method or Bernstein-von Mises under suitable regularity for the likelihood based on P.tt). the concentration of Y/M implies that the posterior variance for Pett will also scale as ((M-)). Therefore, the EFPC principle that an effective or aggregate measure of noise is inferable with a posterior variance scaling inversely with M-is robust and extends to scenarios involving time- varying noise schedules, provided the cumulative effect across edges results in indicators of change that are independent or, at worst, weakly dependent.
Concluding Remarks on EFPC and its Extensions
The preceding analyses, encompassing the main proof of Edge-Flip Posterior Concentration (The- orem B.I and its extensions, robustly support critical insight: the noise level, an effective aggregate thereof, is inherently inferable from a sufficiently large noisy graph structure. This in- ferability forms the cornerstone of our argument for the potential dispensability of explicit noise conditioning in GDMs.
Robustness to Local Dependencies: The extension to scenarios with correlated edge flips (Sec- tion B), utilizing concentration results such as Janson's 's Inequality (Lemma B.2), demonstrates that the fundamental (MM-)) posterior variance scaling is not strictly confined to i.i.d. flip events. Provided that dependencies between edge flips are local (e.g.. characterized by a bounded maximum degree A in the dependency graph), the concentration property, and consequently the scaling of posterior variance, largely persists. This finding is particularly relevant real-world graph structures often exhibit such local correlations.
Adaptability to Varying Noise Schedules: The extension considering time-varying Bernoulli schedules (Section [ which leverages tools like Hoeffding's inequality (Lemma [B.3). indicates that even if the "noise level" observed in Ay results from a complex, multi-step corruption process, an effective measure of this cumulative noise (Pen) can still be estimated with a posterior variance scaling ((M-1). This suggests that noise-unconditional denoiser has the potential to learn to recognize these aggregate noise states directly from the data.
In summary, these theoretical findings collectively provide strong support for the premise that the figh-dimensional nature of graph stttu--peeiffcallly... the large number of potential edges M- M-offers substantial statistical information for accurately inferring the parameters of the underlying noise process. This robust inferability of the noise level is the foundational pillar upon which subsequent theoretical results in this paper, namely the Edge-Taree Target Deviation Bound (ETDB) and Multi- Step Denoising Error Propagation (MDEP), are constructed. Ultimately, this underpins the central argument for the viability and potential advantages of designing GDMs without explicit noise-level conditioning.
C Detailed Proof for TaggeTarrett Deviation Bound (ETDB)
This section provides detailed derivation for the -arget Deviation Bound (ETDB), formally stated as Theorem 4.2 in the main text. This theorem quantifies the expected error introduced in the ideal denoising target when explicit noise-level information (c.g.. or its proxy 3r) is omitted. The proof builds upon the Edge-Flip Posterior Concentration (EFPC) result (Theorem B.T For clarity, restate the ETDB theorem.
Theorem C.1 (Edge-Targe) Deviation Bound (ETDB)). Let A, be the noisy adjacency matrix at step generated from clean graph Ag under given noise model parameterized by noise level indicator u (e.g., the flip rate Bg in the Bernoulli model). Let the ideal conditional regression target be
cond Hy
= E[Ag | Ae, u).
24

---

Define the unconditional regression target, where the explicit noise level is marginalized out according to its posterior p(u At), as
Pr :- E uup cond
Assume the following conditions hold:
(i) Posterior Concentration of Noise Level: The variance of the noise level parameter u given As satisfies Var(u A.) O(M-)), where M (2) the number of potential edges. This is established by Theorem B.7 (EFPC) for the Bernoulli flip model.
(ii Lipschitz Regularity of the Conditional Target: The conditional target poond is L--Lipschitz continuous with respect the noise level parameter u, I.e., for any two noise levels u1, U2.
||
|| S L|uu -22
where L = (1) is a constant independent of M. This corresponds to Assumption A2 (Global-Lipschitz Denoiser) from the main paper, applied to the ideal Bayesian estimator.
Then, the expected squared Frobenius norm of the deviation between the conditional and unconditional targets, denoted & (At), satisfies:
[lle E(A,) == E Bu-p(u)AA) cond - --ell? O(M
Furthermore, if || ll? (M)), the relative squared error diminishes O(M-2), ensuring approaches zero as M + co.
Proof. The quantity E(A,) represents the expected squared deviation of the conditional target go from its mean Fz, where is drawn from the posterior p(u At). This is effectively the variance of the random matrix (or vector) unind where U ~ p(u u A.).
We can bound this variance using the Lipschitz property of peond A standard result states that if a function g(u) is L-Lipschitz with respect to U, then Varlg(U)] < L Var(U). Applying this principle (which can be derived using, for instance, properties of expectation and the definition of Lipschitz continuity, by a first-order Taylor expansion for highly concentrated U):
consequence of the Poincaré inequality under certain conditions,
E(Ai) -uup((lãd)) [1la Eupptel (,)lp, [1
< 1,2 E Bamp(uldd) [(u:
E [1)))
(by Condition (ii), Lipschitz continuity)
L2 Var(u At).
The inequality step leverages the fact that the variance of function is bounded by the square of its Lipschitz constant times the variance of its argument.
By Condition (i) of the theorem (Posterior Concentration from EFPC, Theorem B.1. we have Var(u Ae) = O1. Since L (1)), it follows that:
E(A,) < (O(1))
This establishes the primary result for the absolute expected squared deviation.
For the relative squared eтror, if we assume || || ((M) (a reasonable assumption for non-trivin trivial graphs where ü. represents probabilities or expectations over M potential edges, many of which are expected to be non-zero average), then:
E E(A))
O(M-1) 3 A 2 ((M)
This (M rate ensures that the relative error diminishes rapidly M oo, implying that Pa becomes an increasingly accurate approximation of goond in a relative sense for large graphs. The statement the theorem's conclusion that the relative error (M-11) a looser bound that also satisfied, as (2) O(M-1). The crucial point is its convergence to zero.
25

---

Lipschitz Constants for Additional Noise Families (Supporting ETDB Assumption (ii)
The second assumption of Theorem C.T (Lipschitz Regularity the Conditional Target) crucial for the ETDB result. This subsection briefly justifies that this condition, || pag I| S L|u1 U2l with = (11), holds for several common noise models beyond Bernoulli flips. This ensures the broad applicability of the ETDB. The analysis focuses the per-edge conditional expectation u ((A((e) u).
Poisson Jump Noise. The probability that an edge flips its state by time /. due to Poisson process with rate À is Pt (1 (1-e 22))22. The derivative |atpel = de 22t X. The conditional target [[Ao(e) (e), t| is typically simple (e.g., linear) function of pt- If pa,, [[A)(e) Pell is O(1), then by the chain rule, the Lipschitz constant with respect to is Lpoisson = O()). If A O(1), then
LPoisson (1).
Beta Noise on [0, 1]. Consider the noise model Ac(e) = (1- A)Ao(e) + tWe. where Ug Beta(a, B) and E [0, 1] is the noise intensity. For specific forms of the conditional expectation [[Ao(e) A,(e), f). such as R(A((e))t)
(1-t) +t)) (derived in Appendix - the
(1-r)_,leeao-tt.
derivative [0.R(A((e) t)] can be shown be bounded by constant (e.g.. 1 under certain parameter conditions in your paper). Thus, LBeta = (())
Multinomial (K categories) Noise. If edges transition between K categories, with probability 1 1- 1 of staying in the original category and / of resampling from a base distribution π, the conditional probability My (Ar(e) k t) Pr[Ao(e)
(pp,tt j Áe(e) k, t] takes the form (I-A]py + The derivative with respect / is bounded by constant dependent K and minimum prior/base probabilities (e.g.. [0,py] S [ming p6)7
Pyt,, yielding LMuiti (1) for fixed K.
Implication. For these diverse noise models, the Lipschitz constant L of the per-edge conditional expectation with respect to the noise parameter ł is ((1) (i.e., independent of graph size M). This validates Assumption (ii) of Theorem C.I and supports the general applicability of the ETDB.
Bayesian Details for Additional Noise Families (Supporting Lipschitz Analysis)
This subsection provides concise Bayesian formulations for the conditional expectations (regression targets) R(A((e) t) for the noise families discussed above, supporting the Lipschitz constant derivations.
Poisson Jump Model. Given Ae( y and flip probability Pt = (1-t-22t)1 If the prior P(Au(e) = πı and P(Ao(e) = 0) = no = 1 - T1 then:
R(A((e) = y Pc) (P( Ac(e) = y.
(1-P))=
yf
(1-PAJat-PeT
PiTi yf 0 (1=p())
This function rational in Pt. and since p. is Lipschitz in I, R is also Lipschitz in I.
Beta Noise on 00, 1]. Given Å,(e) (1 Ao(e) ) + tie with Ao(e) Beta(ao, bo) and U. Beta(a., 3w). The posterior mean (conditional expectation) from your paper is:
(1 1) Ar)an + la..
R(A,(e) (1) (1 - t) + bb) + t(a, + BB))
Its derivative with respect to t is bounded under non-degenerate parameters.
Multinomial (K categories) Noise. Given År(e) = k, with prior P(Ao(e) = j) = Pj and
resampling distribution Ty. The conditional target (posterior probability of original state j)
(1 ==1;= + Inj
R,(A((e) = k
(1 t)Pk + tT
26

---

Its derivative with respect to t is bounded if priors and resampling probabilities are bounded away from zero.
Corollary C.2 (ETDB Constant for Bernoulli Flips). Under the Bernoulli edge-flip noise model (Section 3 and Theorem B.T. the expected squared deviation Theorem C.7 (ETDB) has the precise
leading term:
E Illlg pell 3 3x) + o(M
M
This leading constant matches that of the posterior variance of Bi (Theorem) B. Appendix By, directly linking noise inference uncertainty to target deviation.
D Detailed Proof for Multi-Step Denoising Error Propagation (MDEP)
This appendix provides rigorous derivation for the Multi-Step Denoising Error Propagation (MDEP) theorem, which was formally stated as Theorem 4.3 in the main text. The MDEP theorem critical as it bounds the accumulation of errors introduced at each step when explicit noise-level conditioning omitted. This connects the single-step deviation, quantified by the Edge- Target Deviation Bound (ETDB, Theorem C.T). to the fidelity of the final generated graph. For clarity, restate the MDEP theorem.
Theorem D.1 (Multi-Step Denoising Error Propagation (MDEP)). Let {Ar,Ar- Ar-1....,AA be the sequence of graph states generated by a learned denoising operator Dg that operates without explicit noise-level input t. Thus, the trajectory is given by A, = to ( for 1,..., O, originating from an initial noisy state Ar. Let {Ar, - Aj} denote the corresponding ideal trajectory produced by the same underlying operator architecture D but perfectly conditioned on the true noise level t; at each step i. Thus, A Po(A t.), with the same starting state
A1 Ar.
The following conditions are assumed to hold for each reverse step i = - O....., -
(i) Single-Stey Deviation Bound: The Frobenius norm of the difference between the output of the unconditional operator and the ideal conditional operator, when both are given the same imput A from the unconditional trajectory, is bounded by d;:
11 (1oo(Ait,,)) 2 (Ar41, [t)lF S 6,
(8)
This d quantifies the error from omitting explicit conditioning t,. From ETDB (Theorem we have 5; = O(M I... Let 8 max; 8;-
C.1
(ii) Lipsehitz Continuity of the Conditional Operator: The ideal conditional operator & (
4.) is Lipschitz continuous with respect to its graph input, with Lipschitz constant T.₃ 0:
[X i t4) 4 t)ll= < -
VX,Y.
(9)
This aligns with Assumption A2 Global--ipschhtzz Denoiser in the main text, ensure this label is correct), where L, < Lmax (1). Specifically, we assume Lmax = 1+ +1 with a small 17 0.
Let B, = [IA, A be the Frobenius norm of the error between the unconditional and ideal trajectories al reverse step i. Then, the error in the final generated gruph Bo I|Ao Atll is bounded by:
Bo
Σ
II Lj
8k.
(10)
R=
(The product I1 Ly is defined 1 for the term).
Consequently, if 8 = O and L; S Lmnax (where Lmax + + with small 1j < 0.2 as per
Assumption A2 the cumulative error is:
Å AblF O(TM-1)
This indicates that the cunulative error grows at most linearly with the number of denoising steps T and diminishes for larger graph sizes M.
27

---

Proof. Let B; = IIA, - A7 represent the accumulated error (in Frobenius norm) between the unconditional trajectory {A,} and the ideal conditional trajectory {A7} at reverse step i. Our goal is to establish a recursive relation for B, and unroll it.
At step i, the entor B; is defined as:
B; = 11. A @ (A(+1,,, Do(A7 1
We add and subtract the term Φ A (4), which is the output of the ideal conditional operator if were given the input from the unconditional path Å,t1. Applying the triangle inequality:
B - P (A.
$3 (A.,1, (t)llF
+ || Lo (4.1, 4.) ( t.)lF..
The first term on the right-hand side the single-step deviation due omitting the explicit time conditioning t,, given the same input A4+1. By Condition (i) of the theorem (Equation (8) ), this term is bounded by dy:
|| 1 (A.+1, Φ i 4.)le S d;
The second term measures how the ideal conditional operator propagates the error from the previous step. By Condition (ii) of the theorem (Lipschitz continuity, Equation ()), this term bounded by:
| [ 4.) (p(A++1 i 4))lF S LillA - Ai+1l F = L, L,
Combining these bounds, we establish the recursive inequality for the error:
B; S 8 + T, B,+1-
(11)
This recursion holds for = T 1, .,..., The process starts from AN = Ar, so the initial
error is Br = || Ai O.
We unroll the recursion:
For i T 1: Br-1 S 8T LT-1Br 8T
.
For i = T -22 2: Br-2 S 8T L < ö + 2
For i ---3:
3: Br-3 8T LT-3BT-2 S 8T LT-3ÔT-2 + -T-3-L--0---
Continuing this pattern down to i = 0, we arrive at the sum presented in Equation 10
Bo S
II Lj
8k.
R=
where the product 11 L. is defined for the term (i.e., the first term the sum do).
To obtain the final scaling, substitute the assumed orders for 5g and Lg. Given og S 8max O(M-1) for all k. and Ly Lmaxx for all j, where Liaax O():
Bo S 8max
(Lmmux)*
k=0
This is sum of geometric series.
If Lmax = 1 (i.e., the conditional operator is non-expansive), then ΣiD [Lmaa)* T. In this case, B, v Tômax = T 1(M = O(TM
If Lmax > 1, the sum Limax I IIma = + v for a small > (such that IT
LT
does not grow excessively fast, e.g., S 0.2 as per Assumption A2) the factor (1+n)T can be approximated. For small 1/T, using the binomial expansion + n)T ~ 1 + Tn T(T-1), +... the factor is approximately T' + T(T-1) +) which is O(T). More generally, as long as Lmax is constant close the sum D is O(T)) if is not excessively large relative to 1/( [[(Tmax 1), or bounded by factor polynomial in T if IT Imaxx remains bounded.
Under the stated assumption that Liax 1 with small 17 < 0.2, the sum Zmav I is indeed O(T) because for small 7), I
L -1
Ty using the approximation eTn Ty (1 + n)) R Tn.
Thus, Bo O(M O(T) -1) This concludes the proof.
28

---

Remarks and Further Implications of MDEP
The Multi-Step Denoising Error Propagation (MDEP) theorem offers several key insights into the behavior and design of unconditional graph diffusion models:
Controlled Error Accumulation: The theorem crucially establishes that errors introduced by omitting explicit time/noise-level conditioning do necessarily compound catastrophically. Instead, under the Lipschitz continuity of the denoiser (Assumption A2) and diminishing single- step deviations (from ETDB, Theorem [.I).. the total accumulated error scales at most linearly with the number of denoising steps T" and inversely with the graph size metric M. This linear (rather than exponential) growth in vital for the feasibility of generating graphs through many denoising steps.
Scalability with Graph Size:
The O(M-!) factor ensures that for sufficiently large graphs (large M), the cumulative enror from lacking explicit condiiiniii becomes negligible. This provides a theoretical underpinning for why I-free models can perform competitively on large graph datasets.
Applicability to Diverse Noise Models: The MDEP framework general. As discussed in Appendix (Lipschitz constants for other noise families), the requisite Lipschitz condition the ideal denoiser holds for various common noise models beyond simple Bernoulli flips (e.g.. Poisson, Beta, Multinomial). If the single-step deviation 6, also scales as O 1) under these noise models (which is expected if EiPC-like posterior concentration holds for their respective noise parameters), then the MDEP O(TM-)) result extends broadly.
Impact of Denoiser's Lipschitz Constant (Lmax): The precise value of Linax affects the constant factor in the error bound. A strictly non-expansive denoiser (Jmax = yields the tightest bound
Tomax- If Lmax = + for a small 17 > 0, the error is scaled by (1+n)== which approximately T for small v/T' The assumption (e.g.. < 0.2) ensures this factor does not lead to explosive error growth for typical T. Maintaining Immax close
is thus beneficial, a property often encouraged by common neural network architectures and regularization. The practical implications of this factor can be explored empirically, as suggested by your reference to Figure (ensure this label is correct for your main paper).
In essence, MDEP provides theoretical assurance that omitting explicit noise-level conditioning is viable strategy for large graphs. leading to predictable and controlled error accumulation. This supports the design simpler and more efficient (-free Graph Diffusion Models.
E Proofs for the Coupled Structure-Feature Model
This appendix provides detailed derivations for the theoretical results concerning the coupled structure- feature noise model, as introduced in Section the main paper. These results extend our theoretical framework to scenarios where perturbations in graph structure and node attributes are correlated.
Throughout this appendix, and (t) are denoted as σ and σ respectively. The clean graph structure Ag and features Xn are stacked into Zo = (vec(Ap) vec(Xx))T_ The corresponding noisy observation is 2 = (rec(Ar),, vec( T, Under the coupled Gaussian noise model (Section 5). Ž ~ (Zo, ))),))
fix specific time index (or noise level) t. The noise scales dx (t)
where ON (8, 7, ox, a) are the noise process parameters, and Σ is the covariance matrix dependent on these parameters. The total dimensionality of Ž is D M - n dy, where M (2)
Proof of Theorem 5.1 (Joint Posterior Concentration)
Theorem 5.1 (Theorem 5.1 in the main paper) states that the joint posterior distribution of the noise process parameters x = (8, xx A concentrates, with the variance of each parameter scaling as O(D ))
Proof. The proof relies on Bayesian asymptotic theory, particularly the Bernstein-von Mises theorem 25]. Let Zo be the (fixed) clean graph data. The noisy data 2 are generated as Z (Zo. )), where the covariance matrix E(Ox) is parameterized by 0x (3, (3,7,xx,0A)
29

---

The parameter 3 may relate to an underlying discrete corruption process that influences Zo or the structure of x) while xx J.a directly define the coupled Gaussian perturbation.
The log-likelihood function for ON given 2 and Zo is e(ON; 2, Zo) log p Zo; 0x). Under standard regularity conditions for the likelihood (e.g., differentiability with respect to 0N. identifiabil- ity, and non-degenerate Fisher information matrix), which are generally met for Gaussian models where parameters smoothly define the covariance matrix, the posterior distribution of N concentrates around the true parameter values nue-
The Fisher information matrix for 0x denoted I(Ox). is derived from the expectation of the negative Hessian of {(0x). For D-dimensional Gaussian likelihood WV (Z E(Ox)). the Fisher information associated with the parameters N (which define E(Ox) )) typically scales with the numher of effective independent observations, which proportional D. This is because each of the D components of Z (or, more accurately, the vector 2 - Zo) provides information for estimating Ox. For example, terms in the Fisher information matrix involve derivatives like 00/0ax x and 0Σ/07, which affect multiple entries of Σ, and the overall information aggregates across the DD dimensions.
According to the Bernstein-von Mises theorem 25 under suitable conditions (including Assump- tion A3 extended to the prior on 0,), the posterior distribution p(0 22 Zo) converges asymptot-
ically to a Normal distribution centered near the Maximum Likelihood Estimate (MLE) 0x. with a covariance matrix that the inverse of the total Fisher information matrix, i.c., (O m If the total Fisher information Zp (0 moe) scales as (D), then its inverse, the asymptotic posterior covariance matrix, will scale as @ Consequently, the marginal posterior variance for each component parameter within NN scales O(D
This general argument from asymptotic Bayesian theory establishes that Var(component of ON ž) = (D--) ), thus proving the JPC result. The eigenvalues of [00x being bounded away from zero (for 1, per Amiu (2') > min(o (1 >²), xx x }) and infinity (Amax (2) (()) ensures that I( is well-behaved and its inverse exists, supporting the regularity conditions needed.
Proof of Theorem 5.2 (Joint Target Deviation Bound)
Theorem 5.2 Theorem 5.2 in the main paper) quantifies the expected deviation between the ideal con- ditional denoising target Rqond : E Z, t] and the unconditional target Ri := IE uu-p(ul 2)) [[tgodd] for the joint structure-feature data Zo (Ao, Xo). The conditions assumed are:
(i) Posterior Concentration of Noise Level Parameter t: From JPC (Theorem 5.1 Var(t
7) = OD--1).
(ii) Lipschitz Regularity of Rçond; | Roond || S L/h 12| for some I, = (())
Proof. The expected squared Frobenius norm of the deviation is E(
E Bump(u)2) ||| |||ooodd Rell This term is the variance of the random matrix Ro where U ~ p(u 2). Using the property that for a random variable U and an L-Lipschitz function o(U) (mapping to space with norm || F),, Varlg(U)] Blllo(U) E[g(U)]| < L Var(U].
Applying this with g(u) Rrond we have:
E(Z)= = Var ump(( 2) (goodd) I L2 Var(u (Z). (by Condition (ii)
From Condition (i) (JPC, Theorem
5.1 Var(u Ż) O(D-1), Since L = O(1),
E(²) (0(1))2 (000))2.0(DD-))) O(D-1) = O(D-1).
This establishes that [[[[RRond
Rs R = O(D-1). The subsequent conclusion regarding the
relative error diminishing follows [ @(D), yielding relative error of O(D-2)
Proof of Theorem 5.3 (Joint Multi-Step Error Propagation)
Theorem 5.3 (Thoormm 5.3 the main paper) extends the MDEP analysis the coupled structure- feature model. bounding the error accumulation over T reverse steps.
30

---

Let (2r,..., Zo} be the trajectory from the unconditional operator Ø9. and ( 2 be the ideal trajectory from the conditional operator ( t.), with 2r- Z7. The error step is
B, 22 1r Conditions:
ii Single-step deviation: [(00(2++1,)) ( (2(+1,1 4)]l S 6, with o, - O(D-)) (from
JTDB, Theorem 5.2
Lipschitz continuity: || +g +.)1 $ L Ylles with L, S Lmaxx
(1).
Proof. The proof structure is identical to that of Theorem (MDEP proof in Appendix D replacing graph-only states A, with joint states Z, and using total dimensionality D instead of M. The recursive error bound is derived as B, s 6, + L, B,41 Unrolling this recursion from down to with B1 0, yields:
Bo S
Lj
8k.
R=
Given 8% I 6max O(D-1) and Lj I Lmux (where Lmax = 1 + with small 17), the sum is bounded
L Limax by Smax T-max-1 1 which is (TTmmax) for Liuax close to 1. Thus, Bu = Zo Z = O(TD-))
The theorem statement concludes ||Ao AullE I1xo Xollı O(T/D). Since Zo Zó
(vec(Ag A5), vec(Xo xT , we have
12 1 = 1|
Abll? + 18 -x
This implies that both |lA - AAill- -(T/)==(TT/D))) and - Xolle -=
O(T/D). Therefore, their sum (using an appropriate norm |g for edges, typically Frobenius) is also O(T/D).
Discussion
The theoretical guarantees established for the coupled structure- feature noise model (Theorems 5.1
5.2 and 5.3) parallel those derived for the structure-only case. A key insight is that coupling (i.e.,
0) can be beneficial for the inferability of noise parameters. By creating statistical dependencies between feature perturbations and structural perturbations (mediated by shared latent variables 7):), feature observations can provide information about structural noise, and vice versa. This potentially increases the effective Fisher information regarding shared noise components the overall noise level.
The three theorems collectively demonstrate that, for any fixed correlation strength y 1 (to avoid degenerate covariance matrices). the fundamental scaling laws hold:
Posterior uncertainty regarding the noise process parameters diminishes at rate of O(D-1), where D is the total dimensionality the joint graph and feature data.
The deviation in the ideal denoising target due to omitting explicit noise conditioning also
scales as (D-1)
The multi-step reconstruction error for unconditional denoiser accumulates controlled rate, scaling as OT//D).
When 0, the model decouples into independent noise processes for structure and features. In this case, these results naturally reduce to applying the independent-noie analyses (from Appendices B C and D adapted for features as necessary) to each component separately. The use of the joint dimensionality as the scaling factor correctly reflects that information from both modalities contributes to noise level inference in the coupled (7 > 0) setting. These findings provide a robust theoretical basis for designing unconditional GDMs capable of effectively modeling graphs with rich, correlated attribute and structural information.
31

---

Theoretical Justiffcattin for Posterior Variance Scaling in Scale-Free Graphs
This appendix provides conceptual outline for the derivation of the posterior variance scaling for the noise flip rate when Graph Diffusion Models (GDMs) are applied to scale-free graphs. As stated in the main manuscript, for scale-free graphs with a degree distribution P(k) x k (where a >> 2), the posterior variance is hypothesized to scale as:
Var(3 Aa) = (a)== - ==?
where M (2) is the total number of potential edges graph with n nodes, and Å is the noisy graph at time This scaling notably deviates from the ((M-1) rate typically observed graphs with more homogeneous degree structures. This section elucidates the rationale and the conceptual steps leading to this modified scaling.
Rationale for Deviation from O(M Scaling in Scale-Free Networks
The primary driver for the altered scaling of posterior variance in scale-free networks is their pro- nounced degree heterogeneity, contrast graphs with bounded maximum degrees dense Cedos-Rényi graphs (where information about the global flip rate 3 is more uniformly distributed across the M potential edges), scale-free networks are characterized by power-law degree distri- bution P(k) x k This implies the existence of a few high-degree "hub" nodes alongside vast majority of low-degree nodes.
This structural heterogeneity means that the information pertinent to B, is not contributed equally by all potential edges. Edges connected hubs, for instance, might provide different quality or quantity of information compared to edges between low-degree nodes. Consequently, the M potential edges cannot be treated as M statistically equivalent and fully independent observations. This leads reduction in the effective number of independent observations, denoted Mor. such that Mat < M. smaller effective sample size naturally results in a larger posterior variance for any estimator of Br. corresponding to slower convergence rate than the benchmark (MM-1).
Conceptual Outline of the Derivation
The derivation seeks understand how the Fisher information ((3.), which is inversely related to the asymptotic posterior variance, behaves in scale-free networks.
Posterior Variance and Fisher Information
Under suitable regularity conditions (Assumption A3. from Appendix A the Bernstein-von Mises
theorem indicates that the posterior distribution p( A,) is asymptotically Gaussian, with variance:
Var(8 Ā.) T(9))
The Fisher information ((3) for parameter 3, given observed data A., defined
T(B) = E 1.9% Olog ((A))))
8 log (egp(An) (A.1))
E 1,1%
08
032
evaluated at the true parameter 3 = 3r. The core of the derivation involves estimating or bounding (3,) for scale-free graphs. The effective number of observations, Metr. is often directly proportional to the Fisher information. If ((t) scales as Mar ~ M (ignoring factors dependent on 3g but not M), then the posterior variance will scale as M
Incorporating the Scale-Free Nature of the Clean Graph Ao
The likelihood p(A,) (5) is implicitly conditioned on the unknown clean graph Ag, as the Bernoulli edge-flipping process p( Ag. 9). The analysis typically considers an ensemble average over scale-free graphs Ag characterized by P(k) oc k- properties of a typical large graph from this
32

---

ensemble. The structural characteristics of Au (e.g., its degree sequence and moments) influence the expected Fisher information [(3, Ao).
Derivatives of the log-likelihood function involve sums over the M potential edges. The specific structure of Ag (i.e., which entries Ao,ij
versus 0) dictates the form of these sums. For scale-free Ao. the power-law degree distribution P(k) and its associated moments (such as the mean degree (k), the second moment (k²), and the maximum degree kmax) become crucial. Sums of the form Ei, [kis ki,, Ao, [t) will arise, and their asymptotic behavior will be governed by P(k).
Hypothesis: Mer Linked to Degree Moment Scalings
The scaling Mar (and thus I(3,)) in scale-free networks is hypothesized to be linked to the behavior of degree moments, particularly the second moment (1:2) Σx k2 P(k).. The properties of (K2) depend on
For 3, ( diverges with the number of nodes N in idealized infinite networks.
In finite networks of size N, (k2) & if the maximum degree kimxx ~ No-r, This divergence signifies strong heterogeneity.
For 3, (k2) converges to a finite constant as N 00.
For a 3, (A²) typically diverges logarithmically with N, i... (6²) ~ log N.
A heuristic argument for the scaling of Man can be developed by considering an "effective number of nodes" Ner that properly accounts for degree heterogeneity. In some network phenomena, Net
has been related to N (k) If (k)) O(1) (typical for sparse scale-free graphs where a > 2) and, for
2 < 3. (12)
N
then:
New N/N N 2=
20
N
the effective number of independent edge- observations, Mett. scales proportionally to New (if information is node-centrie) or perhaps N -N even related to N2 in some interaction contexts, this could lead to various scalings. The specific form Mer ~ M - (since M ~ N²/2) implies
Nour ~ -_1, The heuristic argument presented in your original text. Mei (N²) -- M ==1 directly links the scaling of Man to M. A rigorous derivation for the Fisher Information I [(3,) in the context edge-flip inference on scale-free graphs is needed firmly establish this scaling. The exponent (a - 2)/(c 1) arises from the specific way information aggregates under power-law degree distributions for this particular inference task.
Asymptotic Analysis and Dominant Terms
A formal proof would involve an asymptotic analysis of ((3)) as N + co (and thus M - oo). The objective to identify the term in the expression for T(3)) that dictates its dominant scaling behavior with M (or N) and a. This typically requires:
Expressing sums nodes edges (arising from log-liielihood derivatives) in terms of the degree distribution P(k).
Approximating these sums with integrals for large N: Et (()))()) R [(k)k
Carefully handling the integration limits, which depend on kmin (minimum degree) and
kmax (maximum degree, which often scales as kmax ~ N1/(a-1) for < a < oo). Identifying which parts of the degree spectrum (e.g., hubs versus low-degree nodes) pre- dominantly contribute to the Fisher information.
The Ô notation indicates that logarithmic factors M (or N) are suppressed. Such factors can arise from the precise evaluation of integrals involving - particularly near cutoffs or when a is an integer (e-g. 3).
Interprefation of the Scaling Exponent
The exponent a-2 for M in the expression for Mar (and thus 2- for the variance) can be rewritten a-I
q-1
as - Its behavior quantifies the impact of network heterogeneity the concentration of the posterior:
33

---

As + 2 (corresponding to maximum heterogeneity for networks with finite mean degree), a-1 1* so the exponent 1 ब 0 (or 0+ if defined as Mots/M). the
exponent for Mess is near O, the variance scaling Man would be very slow (i.e., M ---). indicating poor concentration.
For a = 3, the exponent is (3 2) 1) 1/2. The variance then scales as Ó As a + oo (approaching a more homogeneous, regular graph structure), a - 0, so the exponent 1 - --j + 1. The variance scaling thus approaches ((M recovering the rate observed for graphs with more regular degree distributions.
smaller value of a (indicating stronger degree heterogeneity) leads to smaller exponent s=? for Man. This results in slower convergence rate for the posterior variance (i.c., the variance is larger for a given M). The distinct behavior for a E 3) (where (A²) diverges in the infinite limit) versus (where (I2) is finite) is captured by this functional form of the exponent.
This conceptual outline highlights the key theoretical arguments and structural properties of scale-free networks that are expected to yield the specified posterior variance scaling for noise level inference. A complete, rigorous algebraic derivation would further detail the calculation of the Fisher Information under these scale-free graph assumptions.
G Synthetic Validation of Theoretical Scaling Laws
This section details the experimental setup and parameters used for the synthetic studies designed to validate the theoretical scaling laws for Edge-Flip Posterior Concentration (EFPC), Edge-Targel Deviation Bound (ETDB), Multi-Step Denoising Error Propagation (MDEP), and their coupled- noise counterparts (Joint Posterior Concentration JPC, Joint Target Deviation Bound JTDB, Joint Multi-Step Error Propagation JMEP), as presented in Sections 4 and 5 of the main paper.
General Synthetic Experiment Setup
Graph Generation. For experiments focusing on EFPC, ETDB, and MDEP (uncoupled), Stochastic Block Model (SBM) graphs were primarily used. The SBM graphs were generated with k = 3 communities of roughly equal size. The intra-community connection probability (p_int intra) was set to 0.3, and the inter-community connection probability (p_ (p_inter) of nodes n) were varied to achieve different total potential edge counts (EE). For experiments involving coupled noise (JPC, JTDB, JMEP), Erdós Rényi (ER) graphs (nx ler.ggn_rrmnn random rar_da_annaaapplall
0.05. Graph sizes (number
were used, with the number of nodes n chosen to target specific orders of magnitude for [E] (or total dimensionality D), and edge probability Pedge adjusted accordingly.
Noise Application.
Bernoulli Edge Flipping (for EFPC, ETDB, MDEP): Clean adjacency matrices AO (boolean or float tensors on GPU) were corrupted by adding Bernoulli noise. Each potential edge was flipped independently with a true probability Brne (typically 0.1 or 0.2). The number of actual flips was recorded.
Coupled Gaussian Noise (for JPC, JTDB, JMEP): For experiments involving coupled structure-attribute noise, node features xO_t were generated as standard Gaussian random vectors (R with dreat 8). Noisy features Xt_t t were obtained by adding Gaussian noise with variance tau_X (typically 0.5). The structural noise (Bernoulli flips for Ao) was kept, and the analysis considered the joint dimensionality D |E| + diea-
Posterior and Target Computations.
For EFPC, the posterior distribution of the flip rate 3 given the observed number of flips and total potential edges was modeled as a Beta distribution (Beta (flips + ag, |E' - flips + 3o) with priors at 1.0, :o 1.0), and its mean and variance were computed analytically. For ETDB (Bernoulli noise), the conditional target Reond (A,, Brue. Po) and unconditional target Rumcond (A,, flips. |E), were computed based on Bayesian optimal estimation, where Pu is the true graph density. The unconditional target used the posterior mean of B (from the Beta distribution) 3.
34

---

For JTDB (coupled noise), deviations were computed similarly for edge posteriors and feature posteriors (where feature posterior Re,feu (1.0 and Rutteat X,/(1.0+ ix) ), with ix estimated from X₃ is variance).
Error Metries and Aggregation. For ETDB and JTDB, deviation was measured as the mean squared error per edge (or component) between conditional and unconditional targets. For MDEP and JMEP, the cumulative error > A (or /D) was recorded over T steps, where A; is the pereeegg/commonnnt L2 norm squared difference between one-step conditional and unconditional updates, Results were typically averaged over multiple trials (e.g., Nespeat depending on the specific experiment in the provided code) to compute means and 95% confidence intervals (using standard error of the mean and t-distribution for CI. or as specified in plotting functions). Log-log linear regression was used to estimate scaling exponents.
or Nuials = 10, 20, 50
Software and Hardware. Experiments were conducted using Python with libraries such NumPy, SciPy (for stats. 1 linregress), Matplotiib NetworkX, and PyTorch. Computations involving PyTorch tensors were run GPU if available (specified device in the code). Sublersssmmrries key parameters for the synthetic validation experiments.
Summary of Synthetic Validation Findings
The empirical results from these synthetic experiments, presented in Section 6.1 and illustrated in Figures and 5 of the main paper, provide strong quantitative support for the derived theoretical
scaling laws.
EFPC & JPC: The posterior variance of the inferred noise level (3 for edge flips, or joint parameters fy for coupled noise) was empirically found to decay with the number of potential edges [E] (or total dimensionality D) at a rate of |E]-1006000.2 (EFPC) and D-1.00=0.03 (JPC), closely matching the theoretical O [E] -1) or O(D-1) prediction. The product F| x Var( remained approximately constant, aligning with B - (1-)) ETDB & JTDB: The per-edge (or per-component) mean squared deviation between the conditional and unconditional denoising targets was observed to scale as |1- -1.11.125 (ETDB) and - (JTDB), consistent with the theoretical O( or O(D-1) rate.
The norm of the unconditional target |[ scaled approximately as O( [[EE|+1000000 +1.0000001 O(D+1.0==002)) leading to relative error that diminishes rapidly.
MDEP & JMEP: The cumulative error over T denoising steps was found to scale as (lI) for uncoupled Bernoulli noise (MDEP, with an empirical slope of approximately
-1.03 for [E] dependence and linear scaling with T) and O(T/D) for coupled noise (JMEP,
with an empirical slope of approximately 1..4 for 'D dependence at T = 4).
Effect of Coupling (7): Increasing the structure-feature noise coupling strength 7 led
reduced reconstruction error and improved downstream node classification accuracy
in unconditional models, suggesting stronger coupling aids noise inference despite the theoretical O(D-1) posterior variance rate holding for 7 <
All empirical scaling exponents showed high coefficients of determination (N² z 0.99), validating the robustness of the theoretical framework.
(a)
(b)
(4)
11% 05
38-
0.522
0.508
0.53
0.355
20' 20turtall udge COARS E1)
2010rtul edgo COUPR
Figure 3: EFPC verification. Posterior variance Var(3] A.) versus potential edge count E on SBM graphs with B = 0.2. The log-log fit has slope -1.02 + 0.02 (R² = 0.999), matching the theoretical -1.
35

---

Table 3: Synthetic Experiment Parameters for Scaling Law Validation.
Parameter Group
Details
EFPC (Expl)
Graph Type
Stochastic Block Model (SBM)
Node counts (71)
[50, 100, 150, 200, 250, 300}
SBM Communitics
3
SBM Pintea/ Phater/Putter Plater
0.3 / 0.05
Noise Type
Bermoulli Edge Flips 0.2
True flip rate (Strue)
Posterior Prior (3ela((ko,90))
ctp 1.0, 3o 1.0
Number of Trials per size
5 or 10 (as per different code versions)
ETDB (Exp2)
Graph Type & Parameters
Same EFPC (SBM, E [200, 3200] in one script, im- plies larger [b] than EFPC script) Bernoulli Edge Flips 0.2
Noise Type
True flip rate (Strue)
Unconditional Target Approx.
Posterior mean / (flips + 1) 2)
Monte Carlo samples for unconditional target 500 (though analytic posterior mean was primary)
Number of Trials per size
MDEP (Exp5, uncoupled)
Graph Type & Parameters
SBM, Node counts [400, 3200 Bernouli Edge Flips
Noise Type
True flip rate (3)
Number of Denoising Steps (T)
{4, 8, 16, 32, 64)
Error Metric
Cumulative Lz error per edge: Ei= |R Ra, 1//1
Number Trials per size
Coupled Noise (Exp3: "--seee,, Exp4: JMEP)
Graph Type (Exp4)
Erdós Rényi (ER)
Target Edge Counts (argt for Exp4)
15 10', 102 10?,..., 10" (node count n derived)
Pedge (Exp4)
Derived to match target [P] for given
Node count for s-sweep (Exp3)
400 (graph type for Exp3 implied SBM from context of other plots)
Coupling coefficient (7)
Varied in (0, 0.2, 1.0) for Exp3; fixed at 0.7 for scaling table
Node feature dim (deatt
8
Feature noise variance (rx)
0.5
Denoising Steps for JMEP (Exp4,
{4, 8, 16, 32, 64), specifically T 32 reported for main table, T = 4 for plot
Number of Trials per size (Exp4)
Nrepar 6
36

---

(x)
(b)
[c)
22
20003
10X33
31-1
pevande odgs cound (6)
p.0cets CDOP CHAR
possrtal adpa count
Figure 4: ETDB verification. Deviation between the conditional target R(A, t) and unconditional R Ag), normalized by El, on the same SBM graphs. The log-log slope is -1.06 + 0.03 (R²
0.998).
(8)
siape-11
skape-1100
11-1
31-1
12-
10
22-
307
-07
-.7
400
2.*
1.7
127
107
[4]
JTDB UR slopc-t 11.1
JNEP slopo-
10
200
10
160
307
2.7
3.5
30'
32"
307
141
[2]
Figure 5: JMEP verification. Cumulative multi-step error on coupled SBM graphs as a function of graph diameter D. The log-log slope is -1.04 + 0.05, confirming the O(D-1) bound.
H Experimental Setup for Real- World Datasets
This appendix provides detailed description of the experimental setup, including dataset prepro- cessing, model configurations, training procedures, and evaluation protocols used for the real-world graph generation tasks on the QM9 and soc-Epinionsl datasets.
General Setup
Hardware and Software. All models were trained and evaluated primarily on NVIDIA L4 GPUs (22.5GB). Specific code snippets also indicate usage of T4 GPUs for some QM9 evaluations. The primary software stack includes Py TyTch 1.13.1 (with specific CUDA versions like 11.8 depending on the environment), PyTorch Geometric 2.3.0, RDKit 2022.9.5, NetworkX, NumPy 1.25.2, and the OGB package for certain evaluation metrics. CUDA version 11.8 was predominntlyy used. Random seeds (typically 0 or 42) were set for reproducibility across PyTorch, NumPy, and Python's random module. For multi-seed evaluations (typically 5 seeds, e.g., 10,1,2,3,41 3,)), means and 95% confidence intervals (CI) were computed. Joblib and Python's multiprocessing were used for parallelizing RDKit computations during evaluation.
37

---

QM9 Dataset Experiments
Dataset Details. The QM9 dataset (38 consists of 133,885 small organic molecules, with up to heavy atoms (C, N. O, F). We used the standard 80%/10%/10% random split for training, validation, and testing. Node features were one-hot encoded vectors of size 5, representing atom types (Carbon, Nitrogen, Oxygen, Fluorine, and a dumny/padding type). Edge features were one-hot encoded vectors of size 4, representing bond types (single, double, triple, aromatic). For all experiments, molecules were padded to a maximum of NMAX 9 atoms. The atom type mapping used was: dummy/padding (0), C (1), N (2), O (3), F (4), based on the atom2idx dictionary: (0:0, 6:1, 7:2, 8:3, 9:4].
Data Preprocessing. Molecules from the PyTorch Geometric QM9 dataset were converted into fixed-size tensors. Node features (atomic numbers from data. 2) and edge features (bond types from the first dimension of data. blata.edge_aat edge_attr) were processed into X allll (shape (num_mo mww.cmlls, N_MAX, 5)) and A_all (shape (num_molecules, N_MAX, M_MAX, 4)). Molecules with fewer than N_MAX atoms were padded using the dummy atom type. Adjacency tensors A aalll were made symmetric, and diagonal entries (self-loops) were zeroed out. These preprocessed tensors were cached in a file named packed. pt for efficient loading in subsequent experimental runs.
Models and Variants Tested. Both GDSS and DiGress models were evaluated under three settings:
t-aware: Standard models explicitly conditioned on the diffusion timestep t.
t-free: Models trained without any explicit timestep conditioning.
t-free (warm): t-free models initialized with weights from pre-trained t-aware model (excluding time-specific layers, e.g., time_ emb, t_proj) and then fine-tuned.
GDSS on QM9.
Training Details:
Noise Model: VP-SDE with Bmin = 0.1 and 8max = 20.0. Noise was applied via the forward_now mnise function, scaling features xo and adjacency AO by att) and adding Gaussian
noise scaled by (tt).
Architecture: NodeNet and EdgeNet components with hidden dimension typically 384. Time embedding, if used taree,, was sinusoidal with dimension 128, projected to the hidden dimension. Both NodeNet and EågeNet consisted of 4 residual blocks with LayerNorm and SiLU activations.
Optimization: AdamW optimizer with learning rates typically 10-4 for t-aware and t-free (scratch) models, and 1 x 10-4 for i-free (warm-start). Batch size was 256. Models were trained for 100 epochs. Gradient clipping was applied (e.g.. 0.5).
EMA: Exponential Moving Average with a decay of 0.999 was applied to model weights.
Evaluation Details:
Sampling: Molecules were generated using an Fuler-Maruyama sampler (suler_samples __amplerr or euler_samples batch) for typically 400-500 steps with a noise factor r) 1.0. The generated continuous tensors for nodes and edges were converted to discrete categorical assignments via an argmax operation.
Metries: Chemical validity (%), uniqueness (%), novelty (%), mean molecular weight (MW_mean), and mean ring count [Ring_mean,
Protocols for Validity: Two distinct RDKit- based sanitization protocols were employed to assess chemical validity, as described in Section H Multi-seed evaluations seeds) generated 10,000 or 20,000 molecules per seed to calculate means and 95% Cls, depending the protocol.
Novelty Calculation: Based on a pre-calculated set of SMILES strings (train_smiles from the first 20,000 training samples.
DiGress on QM9.
Training Details:
Noise Model: Discrete flip noise with T = 1000 diffusion steps. Node and edge flip
probabilities (flip_non) node, flip_edge) were linearly interpolated from 0.001 to 0.10 over T
38

---

steps. Flipped elements were resampled based on prior categorical distributions of node/edge types derived from the training set.
Architecture: A GraphTranst TraphTransfoo ormer model with hidden dimension of 512, 12 layers, and attention heads. If time conditioning was used (use_t=True), an nn Embedding layer was used for discrete timesteps ż E [1, .
Optimization: Adam W optimizer with a learning rate of 2 x 10 Batch size was 128. Models were trained for 30-40 epochs (c.g., EPOCHS=30 in one script, 40 in Table44). Gradient clipping was set to 1.0. The loss function was sum cross-entropy losses for node and edge predictions.
Evaluation Details:
Sampling: Reverse diffusion process (reverse (iteerseddiffssoon for STEPS-200 (strict eval- uation) STEPS=400 (permissive evaluation). Categorical features were sampled using Gumbel-Softmax with a temperature
0.7.
Metrics & Protocols for Validity: Same for GDSS QM9, employing both striet and permissive RDKit sanitization protocols as detailed in Section H Table indicates 20k samples/seed for strict and 10k for permissive evaluation.
Hyperparameters Summary for QM9. A consolidated list of key hyperparameters for Q.99 experiments across DiGress and GDSS variants is provided in Table
Table QM9 Hyperparameters. Settings marked "_" are used by that model.
Parameter
Di(t-aware) Di(t-free) Di(warm) GD(t-aware GD(t-free) GD(warm)
Split (train/val/test)
80/10/10%
80/10/10%
80/10/10%
80/10/10% 80/10/10%
80/10/10%
Padding size NMAX
9
9
9
Node channels
5
5
Edge channels
4
4
4
4
Hidden width
512
512
512
384
384
384
Res. blocks/ Transf. Layers
4
4
4
Dropout
10%
10%
10%
10%
10%
10%
Time embedding
yes
Params (M)
13.16
12.65
12.65
1.89
1.79
1.79
Optimiser
Adam W
Learning rate
10
10-4
2 10-4
10-4
10
10
Batch size
128
128
128
256
256
256
Epochs
40
40
100
100
100
EMA decay
0.999
0.999
0.999
0.999
0.999
0.999
Grad-clip
1.0
1.0
1.0
0.5
0.5
0.5
Schedule type
flip
flip
flip
VP-SDE
VP-SDE
VP-SDE
Bmin/Bmas
0.1/20
0.1/20
0.1/20
Rev. steps (strict)
200
200
200
500
500
500
Rev. steps (perm.)
400
400
400
500
500
500
Euler noise 7)
1.0
1.0
1.0
1.0
1.0
1.0
Samples/seed (strict) Samples/seed (perm.)
20k
20k
20k
20k
10k
10k
10k
10k
10k
10k
RDKit strict filter RDKit perm. filter
1-pass
1 1-pass
1 1-pass
1-pass
1-pass
1-pass
pass
2 2-pass
2-pass
pass
pass
2 2-pass
Training Dynamics for GDSS on QM9, The training dynamics, including metrics like training loss, validation loss, and one-step reconstruction Mean Squared Error (MSE) for various GDSS model variants on the QM9 dataset, are illustrated in Figure
soc-Epinionsl Dataset Experiments
Dataset Details and Preprocessing. The soc-Epinionsl dataset (39, obtained from the SNAP datasct repository (https: /stpp//aapppaaa/aa stanford http:/dataacc--ppiiiioe .html), represents
39

---

Validity (%) Epoch
Uniqueness Epach
Novelty (%6 Epoch
100
100
09.90
196)
09.05
Volldiy (%6
90
Novelty
99.90
85
taree
frocswamm)
75
20
40
60
80
100
20
40
80
100
0
20
40
60
80
100
Epoch
Epoch
Epoch
Mol. Wt. (mean) vs. Epoch
Rings (mean) vs. Epoch
3.40
26
24
Mel Wt. (mean)
120
20
110
Rings
16
100
14
20
40
100
1.00
Epoch
Epoch
Figure 6: GDSS on QM9: Training-time evolution of molecular metrics. Bands denote 95% over five seeds.
who-trusts- whom social network. For experiments, the graph treated undirected. The full graph contains approximately 75,879 nodes and 405,740 edges. Given its size, experiments were performed sampled subgraphs.
Subgraph Sampling. A dataset of 5,000 subgraphs generated using the following procedure:
Parameters:
Maximum nodes per subgraph (NMAx) was set to 50. Candidate seed nodes were selected if their degree in the full graph was > DEGREE_ TH 5. BFS sampling was performed from these seeds with radius limit of RADIUS
A total of NUM_GRAPHS
5, 000 subgraphs were targeted for sampling.
Procedure: the number of candidate seeds was less than GRAPHS, seeds were sampled with replacement. Each sampled subgraph was induced from nodes found via BFS up to max frax_nodes and then relabeled to integers starting from using sorted ordering. Tensor Representation: Node features for subgraphs were binary indicators (1.0 for existing nodes, 0.0 for padding) resulting in a feature channel of (X_all with shape (num_ doum_subgraphs, N N_MAX, 1)). Adjacency matrices were binary and symmetric with no self-loops, also with an edge channel of (A_all with shape (num_subgraphs, N_ N_MAX, N_MAX, 1)).
Caching and Splitting: The processed subgraph tensors were saved to epinions ppainiossppackett packed. pt. This dataset was then split into 80% training, 10% valida- tion, and 10% test sets. Daters used batch size of 128.
Models and Variants Tested. Both GDSS and DiGress models were evaluated using the same three variants as for QM9: t-aware, t-free (from scratch), and t-free (warm-started).
GDSS soc-Epinionsl.
Training Details:
Data Format: Raw node features (X_raw) and adjacency matrices (A_raw) from sub-
graphs were converted to a 2-channel categorical format (presence/absence) for both nodes (IDDE_CH=2) and edges (EDGE_CH=2).
Noise Model: VP-SDE with 8min = 0.1 and 3max = 9.5.
Architecture: NodeNetSDE and EdgeNet modules with hidden dimension 128 and time embedding dimension 128.
40

---

Optimization: Adam W optimizer. Learning rates: 2 x 10 (t-aware), x 10 (t-free scratch), 0.5 x 10-4 (t-free warm). Epochs: 50 (t-aware, t-free warm), 75 (t-free scratch).
Gradient clipping at 1.0. EMA decay 0.999. Early stopping with patience 10.
Evaluation Details:
Sampling: Suler-Maruyane sampler
with 200 steps and
= 0.0.
Metries: Subgraph Validity (%), Uniqueness (% via WL-hashes), Avg Nodes, Avg Edges, and MMD scores for degree, clustering coefficient, and triangle count distributions. Reference statistics from 1000 training subgraphs.
-C Calculation: Mean 95% CI over seeds, 500 graphs/seed.
DiGress on soc-Epinionsl.
Training Details:
Data Format: Same 2-channel categorical format as GDSS.
Noise Model:
Discrete diffusion with DIFFUSSIO 500 steps, using cosine-based
sisia_bar_diigee schedule. Transition matrices (c.g., computed.
pre-
Architecture: DiGresSGraphTransformm (hidden: 128, layers: 4, heads: 4, dropout: 0.1, time embed dim: 128).
-Optimization: AdamW. W. LRs: 2 x 10-4 (t-aware), 2 x 10-6 (t-free scratch), 0.5 x 10-4 (t-free warm). Epochs: 20 (t-aware), 8 (t-free scratch), 10 (t-free warm). Grad clip 1.0. Edge loss weight Jedge loss 1.0. Early stopping patience 15-20.
Evaluation Details:
Sampling: p_sample, sacpppeeellpp___eee lttpllloppeeeeeeeeeeeee digress from / TiIFusION to 1. Initial noise from training data marginals.
Metrics:
Same GDSS soc- Epiniinii...
-CI Calculation: Mean 95% CI over or runs, 200-500 graphs/run.
Hyperparameters Summary for soc-Epinionsl. consolidated list of key hyperparameters for QM9 experiments across DiGress and GDSS variants is provided in Table
Consolidated Results, Key performance metrics for all model variants on both QM9 and soc- Epinionsl are presented in Tables in the main paper. These tables also detail parameter counts and average per-epoch training times, highlighting the efficiency gains of t-frec models.
Evaluation Metrics Details
QM9 Molecular Metrics. The following metrics were used to evaluate the quality of generated molecules for the QM9 dataset:
Validity (%): This measures the percentage of generated molecules that are considered
chemically valid according to RDKit's molecular sanitization rules. Two distinct protocols were employed:
Strict Protocol: This protocol applies stringent one-pass RDKit sanitization. Specif- ically, it uses Chem. SanitizeMo (mol, Chem. Samm.Sanitte wwattiieellaseei.i SANITIZE_ ALL "Chem. SaniSaniiiiiii www.SSanniizelaagee SANITIZE, SANITIZE_ADJUSTHSS ADJUSTHS). which excludes the adjustment of hydrogens. Molecules failing this check are discarded. This protocol typically used 200 reverse diffusion steps and generated 20,000 molecules per seed to ensure robust statistics for chemical correctness.
Permissive Protocol: This protocol is designed be more tolerant, giv- ing models better chance to produce an acceptable chemical graph, often useful for faster debugging or assessing best-case potential. It involves two-pass sanitization. If the standard RDKit check fails, a second attempt SANITIZE, made using Chem. SanitizeMol (mol, Chem. Sani tizetlizeess SaaizeFFIaasSS.IIIEEE _LLL "Chem SanitizeFlags. www.eellaagsssaI.......... CANITIZE_PROPERTEE and explicit-hydrogen inconsistencies rejected by the strict protocol, followed by Chem. Chem. Soaa.eeeteetBoosSSeeeeeceeeenett (mol).
which tolerates certain valence
(mol). To compensate for this relaxed filter-
41

---

Table 5: QM9 generation results. Metries + 95% CI over five seeds. "Params" in millions; "Time" is per-epoch on one T4 GPU. strict protocol (one-pas pass RDKit sanitisation) and permissive protocol (relaxes sanitisation and doubles the -iverseddiffusion horizon) used during the evaluation.
Strict evaluation
Model Variant
Valid %
Unique %
Novel %
Ringmean
MW
MW mean
Params
Time
DiGress t-aware
99.93-10.02
5.63:10.06
100.0010.00 O. 0.000
143.23:10.02
13.16
47.82
DiGress t-free
99.41
6.67=10.9
100.00-1:.00
0.09-10.00
138.41++003
12.65
48.16
DiGress t-free (warm)
99.93=0.01
4.20=#0.04
100.00+0.00
0.01
143.97=0001
12.65
48.23
GDSS t-aware
12.54=0.11
13.80=00.35
99.36+0.28
0.02+00000
33.92:10:34
1.89
9,56
GDSS t-free
7.11.10.08
18.90.10.99
99.26.10.2
0.03110.00
33.39110.77
1.79
8.78
GDSS t-free (warm)
8.34-+022
17.55+0.22
99.52+0.17 0.03++0000
32.92+0.09
1.79
8.78
Permissive evaluation
Model / Variant
Valid %
Unique %
Novel %
Ringmean
MW mean
Params
Time
DiGress t-aware
4.76:10.0 99.98:00.01
100.00+0..00 0.00110.00
145.37=0.03
13.16
47.82
DiGress t-free
99.99110.01
4.65:10.08
100.00110.00 0.00110.00
149.74.10.01
12.65
48.16
DiGress t-free (warm)
99.96=+0.01
5.09=0.12
100.00+0.00
0.00+0000
147.46=2002
12.65
48.23
GDSS t-aware
92.32 19
81.08=00.11
99.99=00000
12.87=0.02
95.00++0.12
1.89
9,56
GDSS t-free
94.00110.09
89.60:10.20
99.9910.00
14.5210.055
99.23:10.17
1.79
8.78
GDSS t-free (warm)
92.57-+0.03
88.46+00.41
99.99+0.00
14.16+00.99
07.74+0..36
1.79
8.78
ing, the reverse-diffusion process was run for 400 steps, and 10,000 molecules were generated per seed.
Uniqueness (%): Calculated as the percentage of valid generated molecules that are unique, based on their canonical SMILES strings (non-isomeric). This is computed relative to the set of valid generated molecules.
Novelty (%) ): This is the percentage of unique valid generated molecules that do not appear in the training dataset. Novelty determined by comparing the SMILES strings of generated molecules against pre-compiled set of SMILES strings from approximately 20,000 training molecules.
MW m_emm:
The average molecular weight of all valid generated molecules, computed using Descriptors .Moli from RDKit.
MollWt Ring mean: The average number of rings present in all valid generated molecules, com- puted using Descriptors. .ingooont or rdMolDescriptors Cal cNumRings from RD- Kit.
Reporting results under both strict and permissive protocols provides transparent comparison, where strict numbers support claims of chemical correctness and permissive numbers reveal the model's potential under more lenient conditions.
soc-Epinionsl Subgraph Metries. For the larger soc-Epinionsl graph dataset, evaluation focused on structural properties sampled subgraphs:
Validity (%): Defined as the percentage of generated subgraphs that are connected and comprise at least 3 nodes. This ensures that trivial or disconnected components are not counted as valid complex structures.
Uniqueness (%): This measures the diversity of the generated subgraphs. Is the percentage of valid generated subgraphs that are structurally unique, typically determined by comparing graph hashes (wl_ hash with 3 iterations and digest size of 16). Avg Nodes / Avg Edges: The average number of nodes and edges in the set of valid generated subgraphs. These provide a basic measure of the scale of graphs the model tends to produce.
their Weisfeiler-
MMD Scores (Degree, Clustering, Triangles, Overall): Maximum Mean Discrepancy used to compare the distributions of key graph topological statistics between the generated
42

---

subgraphs and reference set of 1,000 subgraphs sampled from the training data. Specifically,
MMD is calculated for:
Node degree distributions.
Local clustering coefficient distributions.
Triangle count distributions.
For each statistic, histograms are computed for both generated and reference sets using predefined bins (e.g., deg_bins siis__ddss clust_bins, seatt_iin_ddiiee_eee The MMD is then the L2 norm of the difference between the two normalized histograms. The MMD MID_Overalll score the arithmetic mean of the MMD scores for degrees, clustering coefficients, and triangle counts, providing a single aggregate measure of distributional similarity.
Table 6: soc-Epinions] Subgraph Experiment Hyperparameters. Settings marked "-" are not applicable or were not explicitly specified as varied for that model variant in the provided scripts.
Parameter
Di(t-aware)
Di(t-frre
Di(t-free warm)
GD((-awan GD(ttfree
GD(t-free
scratch)
seratch)
warm)
Split (train/val/test)
80/10/10%
80/10/10%
80/10/10%
80/10/10%
80/10/10%
80/10/10%
Target num subgraphs
5,000
5,000
5,000
5,000
5,000
5,000
Subgraph NMAX
50
50
50
50
50
Seed node degree
5
5
5
5
BES radius Node channels (input model)
2
2
2
2
2
2
Edge channels (input model)
2
2
2
2
Hidden width
128
128
128
128
128
128
Transformer Layers (Di)
4
4
4
Attention Heads (Di)
MLP Blocks (GD)
4
4
Dropout
0.1
0.1
0.1
0.1
0.1
0.1
Time embedding
yes
yes
Time embed. dim
128
128
Params (M)
Rd 1.3
1.3
6: 1.3
Rd 0.25
0.20
RS 0.20
Optimiser
AdamW
Learning rate
10-4
2 10-5
x.5
2 10-4
10-4
0.5 10-4
Batch size
128
128
128
128
128
128
Epochs (target)
10
50
50
Early stepping patience
15-20
15-20
15
10
10
10
EMA decay
0.999
0.999
0.999
0.999
0.999
0,999
Grad-clip
1.0
1.0
1.0
1.0
1.0
1.0
Edge Loss "fedge (Di)
1.0
1.0
1.0
Schedule type
Discrete 500
Discrete 500
Discrete 500
VP-SDE
VP-SDE
VP-SDE
DIITUSION (Di)
Smin/ Bmax (GD)
0.1/9.5
0.1/9.5
0.1/9.5
Sampler steps (eval)
500
500
500
200
200
200
Sampler (GD)
0.0
0.0
0.0
Initial noise (Di eval)
marginal
marginal
marginal
Samples/seed (CI)
200-500
200-500
200-500
500
500
Num. seeds for CT
3-5
3-5
3-5
5
5
I Experiments on Larger Subgraphs for soc-Epinions with GDSS
To further investigate the performance of unconditional Graph Diffusion Models (GDMs) as graph size increases, we conducted additional experiments on the soc-Epinions! dataset using the GDSS model with larger maximum number of nodes per subgraph (N (N_MAX=200), compared to the N M_ results presented for GDSS T panel). The primary motivation was to assess whether the observed trends and the efficacy of f-free models, particularly the t-free(warm) variant,
43

---

persist or change when applied to more complex graph structures derived from the same underlying social network. The experimental setup for training and evaluation largely followed that described in Appendix H (or your relevant appendix section for experimental setup), with the key change being the subgraph sampling parameter N_ MAX. All GDSS N MAX==00 experiments were conducted on an NVIDIA A A100 GPU.
The results, also presented in Table (right panel), offer several key insights:
Validity and Uniqueness. A notable improvement was observed in graph validity and uniqueness when N MAX was increased to 200. All GDSS variants (t-aware, t-free, and t-free(warm)) achieved 100.00% for both Valid % and Unique %, significant increase from the N N_MAX=50 setting where, for instance, GDSS t-aware had a Valid of 1.,.4411222 This suggests that generating larger, more information-rich subgraphs may lead to more stable and structurally sound outputs across all model types, potentially by providing richer context for the diffusion and denoising processes.
Graph Statisties (Avg Nodes and Edges). As expected, subgraphs generated with N. MAX=200 were substantially larger, with average node counts around 89-95 and average edge counts in the range of 3200-3500, compared to N_MAX=50 (approx. 31-45 nodes and 500-670 edges). The t-free model tended to generate slightly larger graphs (Avg Nodes: 95, 1110.11) compared to t-aware (8.032::0009) and t-free(warm) -.007) in the N N_MAX=200 setting. These generated sizes should be compared against the statistics of the reference dataset sampled with N 2_MAX=200 to fully assess fidelity in scale.
Distributional Similarity (MMD Scores). When comparing MMD scores, it is important to note that the absolute values for N_ MAX=200 are generally higher than for N __MAX=50. This is anticipated, as matching the complex distributions of larger graphs is inherently more challenging, and the reference distribution itself changes with N N_MAX. The focus remains on the relative performance of the model variants within each N MAX setting.
For N_ MAX=200:
MMDoveralll The (-free(warm) variant (68.85=0.00) demonstrated the best overall struc- tural similarity, outperforming both t-aware (74.76:0.05) and t-free (77.46=0.08). This reinforces the finding from N. MAX=50 where (-free(warm) also superior.
MMD Clust
Consistent with N. MAX=50, the t-free(warm) model (95.82=0.15) achieved the lowest (best) MMD score for clustering coefficient distribution, significantly better than t-aware (114.07=+0.07) and t-free (117.01=0.24).
MMD Deg and MMDTri Tri For these metries, the t-aware model (61.66++0.05 for De- gree, 48.54 for Triangles) performed best, with t-free(warm) being a close second 062.00=0.00 for Degree, 48. 48.732+0.02 for Triangles). The t-free model trained from scratch showed higher MMD values for these specific aspects.
The consistent strong performance the t-free(warm) variant. especially in overall structural fidelity (MMDoveran) and clustering (MMDclust). across both N MAX=50 and N MAX=200 settings for GDSS is a significant observation. It suggests that with a good initialization from a pre-trained (-aware model, the unconditional GDM can effectively learn to generate high-quality graphs even when they are larger and more complex, often surpassing its f-aware counterpart.
Computational Efficiency. The advantages of t-free models in terms of parameter count (0.201M for (-free variants vs. 0.251M for (-aware) and average time per epoch (e.g.. i-free at 7.98s vs. I-aware 8.29s for N N_MAX=200) were maintained with the larger graph size, consistent with our theoretical expectations and previous findings.
Conclusion for Larger Graph Experiments. The experiments on Em-nionno subgraphs with N M_MAX2000 using the GDSS model further substantiate the potential of unconditional GDMs. The dramatic improvement in basic validity for all models N MAX=200 suggests that the increased information content in larger graphs might inherently stabilize the generation process. More impor- tantly, the (ffree(warm) strategy consistently yields GDSS models that are not only more efficient but also achieve comparable or superior graph generation quality relative to f-aware models, even as
44

---

the complexity of the target graph structures increases. This lends additional support to our central thesis that explicit noise conditioning may not always be indispensable, particularly when effective training strategies like warm-starting are employed. The performance of the I-free model trained from scratch, while generally not outperforming the other variants on MMDs for N M_MAX=200, still produced 100% valid and unique graphs, indicating its fundamental capability.
Table 7: GDSS generation results for the soc-Epinions dataset, comparing subgraphs sampled with N MAX=50 and N__ MAX=200. Metrics are mean + 95% CI over five seeds. "Params" in millions; "Time" is per-epoch on an NVIDIA A100 GPU.
soc-Epinions Dataset (GDSS Performance by N MAX)
MAX
N MAX 200
Metric
t-aware
t-free
afreeewarma
t-aware
t-free
t-free(warm)
Valid %
2..44+1.22
33.36 1.33
48.00+1..99
100.00+10.00
100.00-+0.00
100.00-10.00
Unique %
94.68+1.40
9..51=1.59
99.91=0.17
100,00:10.00
100.00:10.00
100.00:10.00
Avg Nodes
31.11::1.25
36.97:10.81
04.64
89.32:10.09
95.11110.13
89.98
Avg Edges
503.57::32.42
529.06=15.64
670.82:+16338
3256.56=6648
1473.51=1000077
MMDDeg
0.76
0.06
0.69110.01
61.66.10.05
64.83:10.07
62.00.10.04
MMDclust
0.70=0.01
0.70=0.01
0.39=00011
114.07+00.07
117.01+0.24
95.82++0.15
MMD Tvi
0.80=0.02
0.82=0.01
0,90=00.0
48.54-1003
50.53:10.05
48. 08.7
OvDovalll
0.76==0.02
0.72=0.00
0.66
74.76+00.05
77.46+t0.08
68.85
Params (M)
0.251
0.201
0.201
0.251
0.201
0.201
Time (8)
1.71
1.55
1.55
8.29
7.98
8.02
Industrial-scale real graph: soc-Epinionsl We evaluate on soc- Eic--pinions1 (75,879 nodes; 405,740 74, edges) using induced subgraphs with node cap Nmax E (200, 1000]. We report validity and the change in MMD when moving from Nmax = 200 to Nmax = 1000. AMMD defined as MMD (N ~ negative values mean lower divergence at the larger scale. Results are mean + std over seeds; training schedules follow the main text. The variant "time-dropout t-free fine-tune" removes timestep embeddings by training with time-dropout, then fine-tunes a t-free model; the choice is fixed on validation and kept unchanged across sizes.
MMD(N (IMD(Nmax==1000 1000)
Table 8: soc-Epinionsl: validity and MMD change when increasing the node cap from Nmax -200 to 1000 (mean + std over 5 seeds).
Model Variant
Valid (%) (t)
AMMD vs. Nma 220 (1 better)
GDSS t-aware
100.0 + 0.0
-17.1% + 2.0%
GDSS t-free (scratch)
100.0 + 0.0
-19.3% + 1.8%
GDSS t-free (warm)
100.0 + 0.0
-23.4%
+ 2.2%
DiGress t-aware
100.0 + 0.0
-12.6%
+ 2.7%
DiGress t-free (scratch)
99.7 + 0.3
-14.3%
+ 2.9%
DiGress t-free (warm)
68.4 1 4.1
+1.2%
+. 2.8%
DiGress t-free (warm) time-dropout + t-free fine-tune
97.9 + 0.7
-18.1%
3.1%
Analysis. (i) All GDSS variants keep 100% validity and show clear decrease in MMD Nmax grows from 200 to 1000. (ii) For DiGress, removing timestep embeddings at test time degrades validity; the time-dropout
t-free fine-tune remedy restores high validity and yields the same downward MMD trend as Nmax increases (selection fixed on validation and frozen across sizes). (iii) The trend agrees with ETDB/MDEP: larger Nmax increases available information (through M effective Mett under heavy-tailed degrees), which reduces error; this is consistent with the synthetic ER/SBM studies where the one-step slope near -1
L.1 Metrics and per-dimension normalization for the coupled model
Our coupled results (PPC/TDB//MP; see Section bound posterior variance and reconstruction error in the joint space of structure and features. Hence report joint reconstruction error that
45

---

is normalized by the joint dimension = generated and target distributions bounded by constant multiple of the root mean squared joint envor; improving reconstruction is therefore consistent with a lower MMD (the constant depends on the kernel choice).
= M + ndj. For 1 1-Lipschitz kernel, the MMD between
Results. All errors below per-dimension (divide by D).
Table 9: Coupled study (5-fold CV, mean + std). Increasing the coupling strength y reduces both per-dimension joint enror and overall MMD.
Per-Dim Joint Error (1)
MMD (overall) (J) MAE (masked-label) (1)
0.0
(28.7 + 2.6)
10-3
0.121 0.011
0.129 1 0.010
0.5
(21.3 = 1.9) x 10-3
0.096 0.009
0.103 + 0.009
(15.0 1.5)
10-3
0.073 0.007
0.085 0.008
Takeaway. Stronger coupling increases the shared signal between structure and features; the measure- ments show consistent drops in both joint error and MMD, in line with JPC/TDB//MMP..
1.2 Diagnosing DiGress at small subgraph size on soc soc- Ee-ininnnnnn
We study the case Nmax 50 (5-fold CV) to separate two possible causes of failure: weak graph signal versus architectural reliance time embeddings. The scratch-trained I-free model performs well, which indicates that the signal is sufficient. The warm-started f-free model fails, but time- dropout + t-free fine-tune procedure restores performance.
Table 10: soc-Epinionsi at Nmax 50 (5-fold CV, mean + std).
Variant
Valid (t) MMD (overall) (L)
t-aware (original)
100.0 0.0
0.53 + 0.01
f-free (warm)
24.1 + 2.6
0.49 0.02
t-free (warm) with time-dropout t-free fine-tune
73.9 + 3.2
0.49 + 0.01
Takeaway. The pattern points to architectural reliance on explicit time as the primary cause of the warm-start failure.
1.3 Graph signal versus robustness: GPA degrec-exponent sweep
To vary graph signal strength, we use a Generalized Preferential Attachment (GPA) model and sweep the degree exponent a. Larger weakens hubs and increases the effective edge count Mar. The theory predicts that the performance gap between f-aware and t-free variants should shrink as a increases.
Table 11: GPA sweep (5-fold CV, mean std) with f-free warm models. Increasing a improves validity and reduces MMD for both architectures.
Model / Degree exponent
Valid % (t)
MMD (overall) (L)
GDSS
94.2 1.1
0.96 0.04
GDSS / 4.0
100.0 + 0.0
0.51 0.02
DiGress a 2.2
41.8 3.7
0.69 0.03
DiGress / 4.0
95.1 + 1.5
0.47 0.02
Takeaway: Performance improves as increases from to 4.0, and the gap between L-aware and t-free variants shrinks, which agrees with the effective-sample-site view based on Mett.
46

---

1.4 Near non-expansive denoiser: spectral norm of the Jacobian
We estimate the spectral norm of the learned denoiser's Jacobian by power iteration on mini-batches. Let J denote the Jacobian with respect the input the training noise level; we report ||||| averaged over batches.
Table 12: Estimated spectral norm ||/]|2 (mean = std over runs). Values close to support Assumption
A2 (Lmax Rs 1) used by ETDB/MDEP.
Dataset
|
QM9
1.06 1 0.08
soc-Epinions!
1.09 0.07
1,5 Time-embeddingg reliance in DiGress and architectural fixes
We quantify the directional dependence on the timestep embedding by the cosine alignment between the time embedding vector and the layer-wise averaged key/query channel:
cosAliguume
cos Orime: q):
computed at Naxx = 50.
Cosine alignment and ablations on DiGress at Maxx 50 (mean + std over folds). Large alignment indicates learned reliance on explicit time. cosAligname
Table 13:
Setting
Notes
warm-start (t-free warm) scratch (I-free from scratch)
0.41 0.07
strong alignment
0.02 1 0.01
negligible alignment
Variant (DiGress, Nmax 50)
Valid (1)
MMD (overall) (L)
t-free (warm) before
23.7 +
0.48 0.00
time-dropout - t-free fine-tune
73.9 + 3.2
0.47 0.01
phase-calibration head (train-only) 81.4 +: 2.9
0.46 0.01
These results indicate that the failure of the warm-started DiGress is linked how time is routed through attention, not to the impossibility of implicit noise inference. Simple architectura//raining adjustments reduce the dependence while keeping the model t-free.
1.6 Scaling with graph size and sparsity
For graphs with bounded degrees the single-step error scales O(M-1). For very sparse graphs with average degree d = (11) (so p O(1/N),, the Fisher information scales with N rather than M. giving single-step error O(N-1) )) We verify this by sparsity stress test using GDSS t-free models.
Table 14: Sparsity stress test (GDSS t-free): graphs with N {100, 200, 400) and d E {4, 6} (mean across settings).
Graph size
Valid (t)
MMD (overall) (L)
100
62
0.92
200
0.75
400
90
0.62
Performance improves with N, consistent with the Fisher-information view for sparse graphs
47

---

1.7 Qualitative samples and motif statisties
QM9 (random SMILESS. f-aware: C1= CCD, N#CCO, CC(=0) C1C0C1F r-free (scratch): C1C0CC1, CCN, O=C=0, CCF, C= I-free (warm): CCOCF, C1 C1=COC=C1, CN, C1cC10, CC(=0)
Table 15: Motif statistics align with the MMD components reported in the main paper.
Variant t-aware
Triangles
4-cycle ratio Assortativity
0.048
0.033
-0.12
t-free (scratch)
0.045
0.032
-0.11
t-free (warm)
0.046
0.033
-0.12
soc-Epinionsl (motifs; mean per node).
L8 Runtime breakdown for DiGress
profile per-epoch time into three blocks on the same hardware.
Table 16: Per-epoch wall-clock time (seconds, mean + std). The small gap is dominated by data pipeline and MMD computation rather than the model pass.
Block
t-aware
I-free (scratch)
t-free (warm)
Data I/O batching 29.1 0.4
29.3 + 0.5
29.2 + 0.5
Model forward/back
14.7 +
15.1 1:1:0000 0.2
+
MMD metrics
4.0 = 0.1
3.8
4.0 = 0.1
Total
47.8
48.2
48.2
The measured GPU FLOPs differ by less than 2%. The slight overhead in f-free comes from masking logic and rejection checks used during training and sampling.
1.9 Pilot study on GuacaMol
We run parameter-free free setup of GDSS GuacaMol to probe scalability. Results show that the t-free variants match or exceed t-aware on core metrics.
Table 17: GuacaMol pilot (GDSS; mean std when available). Lower FCD better.
Model (unconditional)
Valid (f) Unique (1)
Novel (1)
FCD (L)
GDSS t-aware
100.0
98.1
93.4
3.01 + 0.07
GDSS t-free (scratch)
100.0
98.6
94.7
+ 0.06
GDSS t-free (warm)
100.0
99.0
95.2
2.73 + 0.06
I.10 Robustness to the noise schedule 3x
We test whether the single-step error scaling predicted by ETDB remains stable under different forward noise schedules. We evaluate three schedules for the Bernoulli edge-flip process: (i) constant, (ii) linearly increasing, and (iii) cosine [ For each schedule we fit the log-log slope the one-step eπror versus M. ETDB predicts slope of - under the specific schedule.
For
non-expansive denoiser, independent of
These results confirm that the O(M-1) single-step rate is stable across schedules. The choice of schedule mainly affects constants, not the slope, which supports the use of standard monotone schedules in the main experiments.
A concrete cosine choice is B, Bmax 1-oonstt/T), schedule with 8. E (0, 1/2] and informative steps acceptable.
48

---

Table 18: Noise schedule sweep (mean = std over 3 seeds). The slope for log(error) vs. log M. All cases match the ((M-l) prediction.
Noise schedule
Slope (log-log error vs M)
constant
-0.99 = 0.02
0.996
linear
-1.01 = 0.03
0.995
cosine
-1.00 0.02
0.997
1.11
Effect of the coupling parameter in the coupled model
The parameter y E [0, 1] controls the correlation between structure and features in the data generation process (Section ; is not provided to the neural network. Our theoretical bounds (JPC/JMEP) hold for any fixed 7. Empirically, larger y increases the shared signal, which reduces constants in joint errors while keeping the O(D-1) rate unchanged.
Table 19: Coupling sweep (5-fold CV, mean + std). Errors are per-dimension (divide by D = M + ndy).
Per-dim joint error (1)
MMD (overall) (1)
(28.7 2.6) 2.6)
10-3
0.121 + 0.011
0.5
(21.3 + 1.9) x 10
0.096 + 0.009
1.0 (15.0 + 1.5) x 10
0.073 + 0.007
The monotone decrease both measures shows that stronger coupling provides clearer joint signal for learning: constants improve while the asymptotic dependence D) remains the same. This clarifies the role of y as a property of the data rather than a conditioning variable of the model.
Limitations
While our theory and experiments support the effectiveness of unconditional GDMs, several open questions remain:
Scope of theoretical analysis. Our formal results cover Bernoulli edge-flip noise and coupled Gaussian model. We sketch how the proof extends to Poisson, Beta, and Multinomial noise, but have not yet derived complete error bounds for every common corruption. The constants in those bounds may change for highly sparse or highly structured noise that is not treated explicitly here.
Strength of assumptions. The guarantees require Lipschitz denoisers (Lmax = 1) and optimml single-step error O(M-1) Large deviations from these assumptions such as extremely deep diffusion chains unstable training-could weaken the bounds. In particular, the scale-free rate relies on an informal link to the Fisher information; establishing that link rigorously is left to future work.
Extremely large or heterogeneous graphs. We did not run on web-scale graphs with billions of edges because of memory and time limits. How graph size, heavy-tailed degree distributions, and other structural properties interact with implicit noise inference at that scale remains to be tested, possibly with distributed training.
Warm-starting efficacy. Warm-starting /-free models from (-aware checkpoints helped GDSS, but for DiGress soc- loc-Eoini 1 the validity rate fell from 99.2 % 95.1 %. More work is needed to understand which architectures and datasets benefit from warm warm-starting.
Bernoulli edge-flip recursion and mixing flips its state with probability 3, step
For each unordered edge pair the forward channel
( (e),
w.p. 1- B,, w.p. Br.
Åz(e)
[1 Ae-1(e),
Let p: Pr(A,(e) 1) and 04 := 1- Then the exact marginal recursion is
Pt 3: + (1-23) P:-1 (p-11 )
49

---

which solves to
Pr = 2 + (po
a=1
Hence Pp. - Po 1 as so the marginal of each edge converges to Bern(1/2) whenever
IT.= a, A sufficient condition is Σ== S. oc, since II (1 28,) I exp( 2 E 9.) for 3g [0, 5) It is without loss of generality to restrict 9r E [0, 2) because only 2 affects
the mixing; allowing Be > equivalent using 3e up to a label swap. For the constant-rate case 3. = 3 E (0, 2)
log (e/ Po - 2))
1
Po
Pp 1 1po (1 - -2)', te
log
log(1 2,3)
2,9
In this appendix, "approaches random graph" refers this marginal convergence ER 5)) Our theory only requires these marginals and aggregate counts; independence across edges is not assumed.
Coupled structure-feature forward channel We couple structural flips with feature noise through shared latent while preserving the desired marginals. Let (e(e) (0, 1) be i.i.d. across edge pairs and (i) ~ (0, Ia,) ) be i.i.d. across nodes, independent over L. Given coupling weight E [0, 1]. define the flip indicator and feature noise as
Fi(e) ((U)(e) (1 B,)),
Ze(i) v70((1) v
where the standard normal edf and (1) the averaged edge latent around node (e.g.. nerree-normalized incidence average). The structure updates by Ac(e) 1 @ Fi(e). and the features follow
X, = m) X + oe Zz,
with (f), 0z) chosen to match the target feature marginal. This construction yields the correct (ernoulli(S:) flip rate and Gaussian feature marginals, while introducing tunable correlation between structural and feature perturbations through 7. assume exchangeability across indices and finite fourth moments, with independence across steps L. Under these mild conditions, the joint dimension == + rdy acts as the effective sample size in Section which the basis for JPC/TDB//MEP rates stated in the main text.
50


Reviews:
[{"review_id": "FKbLEOopVH", "reviewer": "Reviewer_vsmw", "summary": "This paper investigates whether explicit noise-level conditioning is necessary in graph diffusion models (GDMs). Through new theoretical analysis and extensive experiments, the authors show that unconditional GDMs can match or even surpass conditioned models in both accuracy and efficiency (4–6% fewer parameters, 8–10% faster runtime) without explicit noise input. This finding challenges a key assumption in diffusion model design and suggests simpler, more effective approaches for graph generative modeling.", "questions": "What are the limitations of unconditional models in tasks that require fine-grained or conditional generation, such as node-specific or class-conditional graph generation?", "limitations": "See Weaknesses.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\nThis paper provides a novel theoretical framework demonstrating that explicit noise conditioning is not necessary for large-scale GDMs, as the models can infer noise levels implicitly. Backed by solid mathematical proofs and extensive experiments on both synthetic and real datasets, the work not only advances our understanding but also offers practical benefits without sacrificing performance.\n\n## Weaknesses\nThe paper mainly addresses theoretical derivations and preliminary experiments. Its performance and robustness in complex or industrial-scale applications remain to be thoroughly investigated.", "was_revised": true, "final_justification": "The additional industrial-scale application experiments demonstrate that the t-free GDM remains effective even on industrial-scale graphs, thus, I increase my confidence.", "rebuttal": "We thank you for acknowledging the novelty and strengths of our submission. Please find our responses to the weaknesses(W) and questions(Q) below.\n\n*Abbreviations:* GDSS, DiGress (models). ETDB/MDEP (theory, Sec. 4). JPC/JTDB/JMEP (theory, Sec. 5).\n*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.\n\n---\n**W- Lack of evaluation on industrial-scale applications.**\n\nThank 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.\n\nFurthermore, 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.\n\n**Results (*soc-Epinions1*, $N_{\\max}=1000$; mean ± std over 5 seeds).**\n\n| Model / Variant | Valid % (↑) | ΔMMD vs $N_{\\max}=200$ (↓ better) |\n|:--|--:|--:|\n| GDSS t-aware | 100.0 ± 0.0 | -17.1% ± 2.0% |\n| GDSS t-free (scratch) | 100.0 ± 0.0 | -19.3% ± 1.8% |\n| GDSS t-free (warm) | 100.0 ± 0.0 | -23.4% ± 2.2% |\n| DiGress t-aware | 100.0 ± 0.0 | -12.6% ± 2.7% |\n| DiGress t-free (scratch) | 99.7 ± 0.3 | -14.3% ± 2.9% |\n| DiGress t-free (warm) raw | 68.4 ± 4.1 | +1.2% ± 2.8% |\n| DiGress t-free (warm) **time-dropout → t-free fine-tune** | 97.9 ± 0.7 | -18.1% ± 3.1% |\n\n**Result analysis.**\n(i) All GDSS variants keep $100\\,\\%$ validity and show a **clear decrease in MMD** when moving from $N_{\\max}=200$ to $1000$.\n(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.\n(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$.\n\nOverall, the results show that the strong performance of our unconditional models still holds over larger-scale real graphs.\n\n---\n**Q. limitations of unconditional models in tasks that require fine-grained or conditional generation**\n\nOur theory targets **unconditional** generation $p(A,X)$. We summarize what carries over and where the limits are.\n\n**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.\n\n**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\n$$\nO\\left(\\frac{T}{D + N \\times d_c}\\right).\n$$\nThis 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."}, {"review_id": "ZwCzY0iEzV", "reviewer": "Reviewer_KTdR", "summary": "This works investigates the necessity of explicit noise conditioning in graph diffusion models (GDMs). While several recent studies have addressed this issue for continuous data, graph data inherently involves discrete types of noise, making the direct application of previous studies nontrivial.\nThe authors first highlight a theoretical analysis indicating that a noisy graph implicitly encodes the information about the noise itself. Based on this, they further explain that omitting explicit noise conditioning leads to small errors that accumulate linearly during the generation process.\nConsequently, the authors present empirical evidence that supports the theoretical results in both synthetic and real-world data setting. In sum, the authors conclude that explicit noise conditioning is often unnecessary for graph generation.", "questions": "Below are some points that disturbed me from understanding the paper. I would highly appreciate if the authors could address the following questions.\n\n### Minor questions\n\n1. How does the Ref. [13] relate to the statement in line 23-24?\n2. It would be nice if the authors provide an appropriate reference corresponding to the statement of line 51-52.\n3. In the part describing the forward process using the Bernoulli edge-flipping model (line 81-83), shouldn't be $\\beta_t \\in [0, \\frac{1}{2}]$ to make $\\tilde{A}_T$ approach to a random graph (assuming the authors meant ER network in this context)? Please correct me if I'm wrong.\n4. In line 266 or 274, the notation $|E|$ is used as a potential edge, while $M$ was primarily used in this context beforehand. Are these two used differently or is this a typo?\n5. Since the authors framework is based on Bernoulli edge-flip, benchmark experiments with GraphGUIDE [15] would be a natural model to explore before expanding it into two architectures; DiGress [7] and GDSS [18].\n6. Minor suggestion. It would have been more readable if the core part of the experiment setting was described in the main body, or at least if the reference to the corresponding part of the appendix was made. For example, which type of network was used in which setting. I had to go through the appendix to find that SBM was used in uncoupled, and ER was used in coupled setting.\n\n\n### Major questions\n1. Also related to $\\beta_t$, has the authors experimented on varying noise schedule in synthetic setting? Showing the robustness with respect to $\\beta_t$ would more strengthen the theoretical framework to the real-world practices.\n2. In Section 4.1, the authors explicitly provide the EFPC for scale-free network. Then can the authors also provide the empirical results for scale-free case? If this was provided, it would highly support the authors claims.\n3. In the synthetic experiment setup, is there a specific reason to only use SBMs in the uncoupled case and ER network in the coupled case? Is the empirical results robust across graph structures (i.e. for the uncoupled model, is the results also consistent for example, ER and scale-free networks)?\n4. I understand that the authors used shared latent random vectors to model the coupled structure-feature dynamics of real networks. Then I think it would be (slightly) more reasonable to experiment with scale-free networks than ER networks in their synthetic setup of the coupled model, if they were to take real-world into account. According to line 1113-1115 in the appendix, it is said that ER network is used in this setting.\n5. In Section 5.1, while the authors model the noisy adjacency matrix as continuous, it seems that in the experiments, Bernoulli flips were used for adding the noise (line 1125 in the appendix). Can the authors provide a detailed discussion about this discrepancy (for example, possible effects to empirical results)?\n6. Regarding the results of Section 6.3, the authors highlight that stronger coupling \"improves\" both reconstruction error and task performance. What I do not understand about this setting is that the coupling coefficient $\\gamma$ is used as a factor to model the real-world networks, not as a control variable in the authors framework. Although the result that shows the dependence of error/performance on $\\gamma$ despite that in theoretical result it is not provided, is interesting, I think the experiment is slightly misconducted in this perspective. Also, I think that experiments in this section should first support the fact that JPC or JMEP stays valid irrespective of $\\gamma$ before claiming the statement made in line 296-298.", "limitations": "Yes, however the limitations are currently discussed in the appendices. It would be preferable to move the relevant content into the main body of the paper.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths\n1. This work studies an important question; expanding the investigation of explicit noise conditioning to discrete, structured data.\n2. Theoretical framework are well-structured. Which starts from the posterior concentration to the final error propagation, and expanding it to the coupled structure-feature noise model that tries to model the real world.\n3. Empirical results are provided to support the theoretical investigation.\n\n### Weaknesses\n1. There are several points in the current version of this draft where it seems overstated. For example, 'unified theory' in the title and 'extensive' in the abstract. Although the authors provide a scetch how the current theoretical results extends to other types of noise corruption, I don't see as a 'unified' framework in this current stage. \n2. While I agree that investigating the necessity of explicit noise conditioning in GDMs is an important topic to explore, the writing seems to lack clear motivation. Especially in the Introduction line 24-29 is written in result-oriented way and makes a logical leap before introducing the central question in line 30. Furthermore, this work might be seen as a special case study of Ref. [10] (the flow of the proofs are inevitably similar). The authors should more focus on the different nature of the noise inherent in the common diffusion models and graph diffusion models.\n3. There are some points that the authors claimed which the empirical justifications should be more strenghtened (refer to Questions).", "was_revised": true, "final_justification": "Overall, the weaknesses I raised (primarily concerning the writing) have been resolved. The authors have also clarified the points raised in the minor questions and addressed the major questions with additional explanations and supporting experiments.", "rebuttal": "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.\n\n*Abbreviations:* EFPC/ETDB/MDEP (theory for structure-only, Sec. 4), JPC/JTDB/JMEP (theory for coupled structure-feature, Sec. 5).\n*Symbols:* $n$ = number of nodes, $M = \\binom{n}{2}$ = number of potential edges, $d_f$ = feature dimension, $D = M + n \\times d_f$.\n\n---\n\n### **Major Questions**\n\n**Q1: Robustness to the noise schedule $\\beta_t$.**\n\nThank 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.\n\nOur 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.\n\n**Results (mean ± std over 3 seeds):** The log-log slope of error vs. $M$ remains consistently close to $-1$, validating our theory.\n\n| Noise Schedule | Slope (log-log error vs $M$) | $R^2$ |\n| :--- | :---: | :---: |\n| constant | $-0.99\\pm0.02$ | $0.996$ |\n| linear | $-1.01\\pm0.03$ | $0.995$ |\n| cosine | $-1.00\\pm0.02$ | $0.997$ |\n\nThe results confirm that our framework is robust to the choice of noise schedule. We will add this experiment and discussion to the appendix.\n\n**Q2: Empirical results for EFPC on scale-free graphs.**\n\nThank 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.\n\nWe 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.\n\n**Q3: Robustness across different graph families.**\n\nWe thank you for this question on robustness. We have verified our findings across different graph generation models.\n* **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.\n* **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.\n\nWe will add a summary of these robustness checks to the main text.\n\n**Q4: Rationale for using ER graphs in the coupled model.**\n\nThis 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.\n\n**Q5: Discrepancy between continuous noisy adjacency and Bernoulli flips.**\n\nWe 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.\n\n**Q6: Role of the coupling parameter $\\gamma$.**\n\nThank 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$.\n\nEmpirically, 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.\n\n| $\\gamma$ | Per-Dim Joint Error $(\\downarrow)$ | MMD (overall) $(\\downarrow)$ |\n| :---: | :---: | :---: |\n| 0.0 | $(28.7\\pm 2.6)\\times 10^{-3}$ | $0.121\\pm 0.011$ |\n| 0.5 | $(21.3\\pm 1.9)\\times 10^{-3}$ | $0.096\\pm 0.009$ |\n| 1.0 | $(15.0\\pm 1.5)\\times 10^{-3}$ | $0.073\\pm 0.007$ |\n\nWe will add this clarification and the new results to the paper.\n\n---\n\n## Minor questions\n\n1) **How does Ref. [13] relate to Lines 23–24?**  \nAfter 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.\n\n2) **Reference for Lines 51–52.**  \nWe 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).\n\n3) **Range of  $\\(\\beta_t\\)$ and “approach a random graph.”**  \nWe use $\\(\\beta_t\\in[0,1/2]\\)$. The exact marginal recursion is\n$$\n\\Pr(A_t=1)=\\tfrac12+\\bigl(\\Pr(A_0=1)-\\tfrac12\\bigr)\\prod_{s=1}^{t}(1-2\\beta_s),\n$$\nso $\\(\\bar A_t\\)$ approaches ER with $\\(p=\\tfrac12\\)$ whenever $\\(\\sum_s\\beta_s=\\infty\\)$. We will add this formula to Sec. 3.\n\n4) **$|E| $vs. $M$.**  \n$|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.\n\n5) **Benchmark choice (GraphGUIDE).**  \nOur 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.\n\n6) **Readability of the experiment setup.**  \nWe 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."}, {"review_id": "n6WEEfhMIk", "reviewer": "Reviewer_WZ8Z", "summary": "This paper challenges the prevailing assumption that explicit noise-level (or timestep) conditioning is essential for Graph Diffusion Models (GDMs). The authors develop a unified theoretical framework to argue that for discrete graph data, the denoising model can implicitly infer the noise level directly from the corrupted graph structure. The core of their theory is built on three results: Edge-Flip Posterior Concentration (EFPC), which shows the noise level is inferable with posterior variance shrinking as $O\\left(M^{-1}\\right)$ with the number of potential edges M; Edge-Target Deviation Bound (ETDB), which bounds the single-step error from omitting conditioning by $O\\left(M^{-1}\\right)$; and Multi-Step Denoising Error Propagation (MDEP), which proves these small errors accumulate linearly, leading to a manageable total error of $O\\left(T M^{-1}\\right)$.\n\nThis framework is extended to handle more complex scenarios, including coupled structure-attribute noise. To validate their theory, the authors conduct extensive experiments. First, on synthetic data, they show an excellent match between their theoretical scaling laws and empirical measurements. Second, on real-world benchmarks for molecular generation (QM9) and social network generation (soc-Epinions1), they compare standard \"t-aware\" variants of GDSS and DiGress with \"t-free\" counterparts. The results demonstrate that unconditional GDMs can achieve comparable or even superior performance, particularly on larger graphs, while also being more efficient by reducing parameter counts (4-6%) and computation time (8-10%).", "questions": "1.\tThe paper notes that the t-free(warm) DiGress model's validity collapses on soc-Epinions1, attributing this to the transformer architecture's reliance on time embeddings. However, many state-of-the-art GDMs, including DiGress itself and others like DISCO-GT [1], leverage transformers for their strong performance. Does this failure imply that the proposed implicit noise inference is incompatible with top-performing GDM architectures? Could the authors elaborate on why this failure occurs? For instance, does the attention mechanism over-fit to the time embedding, causing an unrecoverable collapse when it is removed? Understanding this specific failure mode is crucial for assessing the practical scope of the unconditional approach.\n2.\tThe theory posits that error scales inversely with M, the number of potential edges. The experiments on soc-Epinions1 show that increasing subgraph size from Nmax=50 to Nmax=200 drastically improved validity for all GDSS models. Is this improvement purely a function of the larger M, or is there a more subtle interplay with the \"richness\" or \"complexity\" of the graph structure that isn't captured by M alone? For instance, how would the theory and models perform on a very large but extremely sparse graph, where M is large but the number of actual edges (and thus structural information) is low?\n3.\tThe paper provides a comprehensive and rigorous quantitative evaluation using statistical metrics like MMD and chemical property distributions. However, the evaluation currently lacks a qualitative component. To provide a more intuitive and complete comparison, have the authors considered including visualizations of representative graph samples? For instance, showing a few valid molecules generated by the t-aware and t-free variants of GDSS/DiGress on QM9, or visualizing typical subgraphs from the soc-Epinions1 experiments, could be very insightful. \n4.\tIn Table 2 (QM9 Dataset), the t-aware DiGress variant is reported with a slightly lower per-epoch computation time (47.82s) than the t-free (48.16s) and t-free(warm) (48.23s) variants. This is counter-intuitive, as the t-free models have fewer parameters  and should theoretically be faster. Could the authors clarify the reason for this discrepancy? Is it due to experimental variance, or is there a specific implementation detail causing this minor overhead?\n5.\tThe real-world experiments are conducted on the QM9 dataset and soc-Epinions1 dataset. To better assess the practical advantages of the t-free approach, have the authors considered evaluating their framework on benchmarks with larger and more complex graphs or molecules, such as those found in the GuacaMol benchmark [3]? Such experiments would provide stronger evidence for the method's scalability and its applicability to more challenging generation tasks.\n\n[3] Brown, Nathan, et al. \"GuacaMol: benchmarking models for de novo molecular design.\" Journal of chemical information and modeling 59.3 (2019): 1096-1108.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The paper tackles a foundational assumption in a popular and powerful class of generative models. Moving away from explicit noise conditioning could simplify GDM architectures, improve efficiency, and is a significant conceptual contribution. While blind denoising has been explored in continuous domains such as images, this work provides a novel and non-trivial extension to the discrete, structured domain of graphs, supported by a new theoretical framework.\n* The paper's claims are backed by a rigorous and comprehensive theoretical framework (EFPC, ETDB, MDEP). The proofs are detailed extensively in the appendices and the theory is thoughtfully extended to more complex cases like coupled feature noise and scale-free graphs, demonstrating a deep engagement with the problem.\n* The empirical validation is well-executed.\n   - The direct validation of the theoretical scaling laws on synthetic data is a major strength, with the tight agreement between theory and experiment (e.g.,$R^2 \\geq 0.995$) providing strong evidence for the framework's correctness.\n   - The evaluation on real-world datasets using two distinct, state-of-the-art GDM architectures (GDSS and DiGress) grounds the work in practical relevance.\n   - The analysis is nuanced, exploring different training strategies (from scratch vs. warm-starting) and varying graph sizes, which provides valuable insights into the practical applicability of the approach.\n* Clarity: The paper is very well-written and structured. The central research question is clearly motivated and stated , and the logical progression of the theoretical argument is easy to follow. Figures and tables are clear, informative, and effectively support the paper's claims.\n\nWeaknesses:\n* The theoretical results hinge on key assumptions, notably that the learned denoiser is Lipschitz with a constant close to 1 and that the model can achieve a single-step prediction error of $O\\left(M^{-1}\\right)$. While the authors acknowledge this in their limitations section, the practical verification of these assumptions (especially the Lipschitz constant of the trained networks) is not fully explored, which makes the link between the theory and the empirical results slightly less direct.\n* The success of the unconditional approach is not universal across all experiments, which slightly tempers the main claim that conditioning is \"unnecessary.\" For example, the warm-started DiGress model shows a catastrophic failure in validity on the soc-Epinions1 dataset. Furthermore, the t-free model trained from scratch, while promising, often lags behind the t-aware or warm-started variants in fine-grained structural metrics (MMDs). The conclusion seems to be more that conditioning is \"not always necessary\" rather than completely redundant.\n* A potential weakness of the paper is that the empirical validation, while thorough for the models tested, does not cover the full taxonomy of modern Graph Diffusion Models (GDMs). The experiments focus on GDSS , a continuous-state/continuous-time model, and DiGress, a discrete-state/discrete-time model. This leaves the framework's applicability to other significant GDM classes empirically unverified. For instance, the authors do not test their framework on discrete-state, continuous-time models, such as the recently proposed DISCO [1] and continuous-state, discrete-time models, a category that includes influential works like EDP-GNN [2]. While the authors briefly sketch a theoretical extension to Poisson processes (which underpins DISCO), providing empirical results for these other model classes would be crucial to fully substantiate the central claim of developing a \"unified theory\" and demonstrating that noise conditioning is broadly unnecessary.\n\n[1] Xu, Zhe, et al. \"Discrete-state Continuous-time Diffusion for Graph Generation.\" arXiv preprint arXiv:2405.11416 (2024).\n\n[2] Niu, Chenhao, et al. \"Permutation invariant graph generation via score-based generative modeling.\" International conference on artificial intelligence and statistics. PMLR, 2020.", "was_revised": true, "final_justification": "The authors have addressed my concerns.", "rebuttal": "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.\n\n*Abbreviations:* EFPC/ETDB/MDEP (Sec. 4), JPC/JTDB/JMEP (Sec. 5). *Models:* GDSS, DiGress, LGD.\n*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.\n\n---\n### **Weaknesses**\n\n**W1: \"The practical verification of these assumptions (especially the Lipschitz constant of the trained networks) is not fully explored.\"**\n\nThank 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:\n- The measured spectral norm is $\\|J\\|_2 = 1.06 \\pm 0.08$ for QM9.\n- The measured spectral norm is $\\|J\\|_2 = 1.09 \\pm 0.07$ for soc-Epinions1.\n\nThese 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.\n\n---\n**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?**\n\nWe 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.\n\n**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$:\n- $\\mathrm{cosAlign}_{\\text{time}}(\\text{warm}) = 0.41 \\pm 0.07$\n- $\\mathrm{cosAlign}_{\\text{time}}(\\text{scratch}) = 0.02 \\pm 0.01$\n\nThis 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.\n\nTo 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.\n\n| Variant (DiGress, $N_{\\max}=50$) | Valid % (↑) | MMD (overall) (↓) |\n|:--|:--:|:--:|\n| t-free (warm) — before | **$23.7 \\pm 2.1$** | $0.48 \\pm 0.00$ |\n| **time‑dropout → t‑free fine‑tune** | **$73.9 \\pm 3.2$** | $0.47 \\pm 0.01$ |\n| + **phase‑calibration head** (train-only) | **$81.4 \\pm 2.9$** | $0.46 \\pm 0.01$ |\n\n---\n**W3: The empirical validation does not test the full taxonomy of modern GDMs, such as discrete-state, continuous-time models like DISCO.**\n\nThank 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.\n\n---\n### **Questions**\n\n**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?**\n\nThis 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.\n\nOur 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$.\n\nTo verify this, we conducted a sparsity stress-test. The results confirm that performance scales with $N$, matching the theoretical prediction for sparse graphs.\n\n**Sparsity Stress-Test Results** (GDSS t-free on graphs with $N \\in \\{100,200,400\\}$ and $\\bar{d} \\in \\{4,6\\}$):\n- **Validity:** $\\{62, 78, 90\\}\\%$\n- **MMD(overall):** $\\{0.92, 0.75, 0.62\\}$\n\n---\n**Q3: The evaluation lacks a qualitative component. Have you considered including visualizations or samples?**\n\nWe 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.\n\n**QM9 SMILES (random samples):**\n- **t-aware:** `C1=CC=CC=C1`, `CCO`, `N#CCO`, `CC(=O)O`, `C1COC1F`\n- **t-free (scratch):** `C1CCOCC1`, `CCN`, `O=C=O`, `CCF`, `C1COC(=O)C1`\n- **t-free (warm):** `CCOCF`, `C1=COC=C1`, `CN`, `C1CC1O`, `CC(=O)N`\n\n**soc-Epinions1 Motifs (mean per node):**\n- **Triangles:** $0.048\\,/\\,0.045\\,/\\,0.046$ (t-aware / t-free-scratch / t-free-warm)\n- **4-cycle ratio:** $0.033\\,/\\,0.032\\,/\\,0.033$\n- **Assortativity:** $-0.12\\,/\\,-0.11\\,/\\,-0.12$\nThese statistics align well across variants and match the MMD components reported in the main paper.\n\n---\n**Q4: Why is the t-aware DiGress variant slightly faster than the t-free versions, which is counter-intuitive?**\n\nThank 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:\n\n| Block | t-aware (s) | t-free (scratch) (s) | t-free (warm) (s) |\n|:--|:--:|:--:|:--:|\n| Data I/O + batching | $29.1 \\pm 0.4$ | $29.3 \\pm 0.5$ | $29.2 \\pm 0.5$ |\n| Model forward/backward | **$14.7 \\pm 0.2$** | $15.1 \\pm 0.2$ | $15.0 \\pm 0.2$ |\n| MMD + metrics | $4.0 \\pm 0.1$ | $3.8 \\pm 0.1$ | $4.0 \\pm 0.1$ |\n| **Total** | **$47.8 \\pm 0.5$** | $48.2 \\pm 0.5$ | $48.2 \\pm 0.5$ |\n\nThe 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\\%$.\n\n---\n**Q5: Have you considered evaluating on larger, more complex benchmarks like GuacaMol?**\n\nWe 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.\n\nThe 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).\n\n**GuacaMol Pilot Study Results (GDSS):**\n\n| Model (unconditional) | Valid % (↑) | Unique % (↑) | Novel % (↑) | FCD (↓) |\n|:--|:--:|:--:|:--:|:--:|\n| GDSS t-aware | **$100.0$** | $98.1$ | $93.4$ | $3.01 \\pm 0.07$ |\n| GDSS t-free (scratch) | **$100.0$** | $98.6$ | $94.7$ | $2.86 \\pm 0.06$ |\n| GDSS t-free (warm) | **$100.0$** | **$99.0$** | **$95.2$** | **$2.73 \\pm 0.06$** |"}, {"review_id": "gDRVZjVsOl", "reviewer": "Reviewer_VRVQ", "summary": "The authors introduce an extensive theoretical framework for quantifying and understanding the effects of noise conditioning on diffusion models applied for graph generation. The theory proposed within this paper establishes that not only is the noise level of the graph diffusion process inferable but that squared error scales and the reconstruction error is bounded under the paper's assumptions; indicating the ability of the diffusion process to encode information from graph structure. The authors further explore this effect with a coupled structure-feature noise model. Empirical analysis across synthetic scenarios and with DiGress, GDSS on QM9 and soc-Epinions1 provide consistent proof to the author's claims.", "questions": "1. Why chose classification accuracy and node reconstruction error as the target for testing the coupled structure-feature diffusion model? From what I gathered in the reading, it appears that the Section 5 theory and subsequently-built latent process allow the coupled gaussian noise process to model the generation of features as well as structure. Within pre-existing graph diffusion models, the modelling of features and structure is often detailed as two separate downstream tasks; 'general' graph generation measured with MMD (Section 7.1 and Table 1 in [1]) and node regression measured with MAE (Section 5.2.1 and Table 3 in [2]) to indicate effective learning of node features. The node regression is not necessatily 1-to-1 since it typically involves some form of guidance in pre-existing graph generative models but the insights testing this mechanism as it relates to this paper feels especially pertinent given how pre-existing models rely on conditional-generation for effective regressions. I understand that strong classification performance can be foundation for developing meaningful graph generative models, but the seemingly-high reconstruction error makes me question the applicability of this framework and insights to directly generating graphs. This is the first of two defining limiting factors for this current review score, particularly since it's difficult to quantify the practical benefit propsed by this paper without further clarification as to why there is or can not be a 1-to-1 application of metrics commonly used in other graph generative architectures.\n\n2. What practical considerations would have to be made in order to derive more formal proofs when considering degree or power-law scaling constraint for graph data, as indicated within Appendix A and F. From there, it seems possible to fully-quantify whether the issue which occurs within the warmed-up version of DiGress when not conditioned on the soc-Epinions1 Dataset is more closely-related to a reliance on explicit time-conditioning or another potential shortcoming within how DiGress can effectively model graph generation. This consideration is not necessarily a defining factor for the score within this review, but seems important to consider in order to reduce the potential for confirmation bias. This can be addressed through clarifications as they relate to this paper's conceptual outlines or theory.\n\n3. Additionally, although the evaluation is comprehensive in how well it relates to the theoretical components of this paper; two datasets seems limited in terms of determining whether increased graph signals does indeed contribute to the idea that score-based diffusion models like GDSS are more resilient to the removal of explicit time-free conditioning versus DiGress, even when altering the size of maximum subgraph node sizes from N=50 to N=200. Is it not viable to repeat or extend the tests conducted within Table 2 and 7 to include synthetic Barabasi-Albert graph samples with varying weights applied to the preferential-attachment mechanism? From there, it seems possible to form and test for a more continuous trend between the relation of graph signals and the resilience of scoring-diffusion models to the removal of time-conditioning. This question can be address through clarification as to why these tests are excluded, but direct results would be certain to eliminate any potential bias. This is the second of the two defining factors for the score within this review, any relevant clarifications or additional tests are certain to raise the score within this review.\n\n[1] Vignac, Clement, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. \"Digress: Discrete denoising diffusion for graph generation.\" arXiv preprint arXiv:2209.14734 (2022).  \n[2] Cai, Zhou, Xiyuan Wang, and Muhan Zhang. \"Latent graph diffusion: A unified framework for generation and prediction on graphs.\" arXiv e-prints (2024): arXiv-2402.", "limitations": "Yes, the authors explore the limitations of their work directly within Section J of the Appendix. Although I agree with the assertion that including more detailed proofs for error bounds on Poisson, Beta, and Multinomial noise will produce a more comprehensive paper; the current theoretical and empirical results still indicate promise which is insightful and complete enough for the further development/improvement of diffusion models for graph generation.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n---------\n1. The authors provide extensive theoretical and targeted empirical analysis on the effects of noise-conditioning with graph diffusion models indicating an intuitive relation with information stored within target graphs and the ability of the diffusion process to encode said information for models without explicit targeting to retain said information and high-downstream performance. The authors do this in a way that condenses already-dense information into an easily-parsed format.\n2. The impact of answering the question regarding the necessity of noise conditioning is significant in itself given that developments aided by this analysis are highly-likely to distinguish graph diffusion models from diffusion models within other data modalities, as evident within the author's exploration of structure-feature coupled noise modelling.\n3. The insights provided by the authors are well-supported by theory and experiments, aiding to the significance of this work. The author's also take care to indicate limitations of their theory and potential future applications in interesting contexts for reducing model parameters in expensive graph diffusion models.\n\nWeaknesses:\n----------\n1. As discussed in the author's limitation section, the assumptions within this paper are not unreasonable but are fairly-strong (i.e. power-law scaling/degree constraint in input graphs, Lipschitz denoisers). This can make it difficult for practitioner's to quantify how to design an effective graph diffusion model following intuitions derived from this paper. However, this does not detract from paper quality or significance. More concerning details are explored within Question 1 of this review.\n2. The evaluation of the coupled structure-feature graph generative model is comprehensive in it's relation to theoretical assumptions but seems to have limited practical applications. More details are provided within Questions 2 and 3 of this review.\n3. There are minor clarity issues within the main paper's Section 5 and 6 given the omission of details, but these are addressed with more extensive details provided within the paper's appendix.", "was_revised": true, "final_justification": "Overall, I think this is a really good paper. It does a great job of empirically studying the importance of noise conditioning for graph diffusion.", "rebuttal": "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.\n\n*Abbreviations:* EFPC/ETDB/MDEP (Sec. 4), JPC/JTDB/JMEP (Sec. 5).\n*Symbols:* $N$ = # nodes, $M$ = # potential edges, $d_f$ = feature dimension, $D=M+N\\,d_f$, $T$ = # reverse steps, $\\alpha$ = degree-tail exponent.\n\n---\n\n### **Q1: Metrics for the coupled structure–feature study.**\n\nThank 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.\n\n**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.\n\n**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.\n\n**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.\n\nTo 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.\n\n**Coupled Study Results (5-fold CV, mean ± std):**\n| $\\gamma$ | Per-Dim Joint Error (↓) | MMD (overall) (↓) | MAE (masked-label) (↓) |\n|:---:|:---:|:---:|:---:|\n| 0.0 | $(28.7 \\pm 2.6) \\times 10^{-3}$ | $0.121 \\pm 0.011$ | $0.129 \\pm 0.011$ |\n| 0.5 | $(21.3 \\pm 1.9) \\times 10^{-3}$ | $0.096 \\pm 0.009$ | $0.103 \\pm 0.009$ |\n| 1.0 | $(15.0 \\pm 1.5) \\times 10^{-3}$ | $0.073 \\pm 0.007$ | $0.085 \\pm 0.008$ |\n\nWe will clarify this rationale in the revised manuscript.\n\n---\n\n### **Q2: Formalizing power-law scaling and diagnosing DiGress failure.**\n\nThank you for pushing for a more formal treatment and a clearer diagnosis.\n\n**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.\n\n**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.\n\nOur 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.\n\n**DiGress Diagnostic on *soc-Epinions1* ($N_{\\max}=50$, 5-fold CV, mean ± std):**\n| Variant | Valid % (↑) | MMD (overall) (↓) |\n|:---|:---:|:---:|\n| t-aware (original) | $100.0 \\pm 0.0$ | $0.53 \\pm 0.01$ |\n| t-free (warm) | **$24.1 \\pm 2.6$** | $0.49 \\pm 0.02$ |\n| t-free (warm) with time-dropout fine-tune | **$73.9 \\pm 3.2$** | $0.49 \\pm 0.01$ |\n\nWe will add this detailed diagnosis to the appendix.\n\n---\n\n### **Q3: Probing the link between graph signal and robustness.**\n\nThis 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}}$).\n\nOur 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).\n\n**GPA Sweep Results (t-free warm models, 5-fold CV, mean ± std):**\n| Model / Degree Exponent $\\alpha$ | Valid % (↑) | MMD (overall) (↓) |\n|:---|:---:|:---:|\n| GDSS / $\\alpha=2.2$ | $94.2 \\pm 1.1$ | $0.96 \\pm 0.04$ |\n| GDSS / $\\alpha=4.0$ | $100.0 \\pm 0.0$ | $0.51 \\pm 0.02$ |\n| DiGress / $\\alpha=2.2$ | $41.8 \\pm 3.7$ | $0.69 \\pm 0.03$ |\n| DiGress / $\\alpha=4.0$ | $95.1 \\pm 1.5$ | $0.47 \\pm 0.02$ |\n\nThis new experiment provides strong evidence for the interplay between graph structure and model robustness. We will add these results to the main paper."}]

Author rebuttal:

Meta-review: This paper makes a compelling case against the necessity of explicit noise conditioning in Graph Diffusion Models. The authors introduce a novel theoretical framework and provide strong empirical evidence showing that unconditional models can achieve comparable or superior performance with greater efficiency.

Reviewers were impressed by the work's foundational nature. While they initially raised valid concerns about experimental scope and a specific model failure, the authors' thorough rebuttal, which included extensive new experiments, fully addressed all issues. This led to a unanimous consensus, with all reviewers raising their scores and confidently recommending acceptance.
Decision: Accept (spotlight)