Dear Reviewer, thank you for positive comments and insightful questions. These greatly help us in making our paper better, and we appreciate for the opportunity to address your questions here.

Independency in the forward equation

• We would like to clarify that the independence assumption in the forward equation $\mathbb{P}(\mathbf{G}_t|\mathbf{G}_0)=\mathbb{P}(\mathbf{X}_t|\mathbf{X}_0)\mathbb{P}(\mathbf{A}_t|\mathbf{A}_0)$ is conditional on the initial graph $\mathbf{G}_0 = (\mathbf{X}_0, \mathbf{A}_0)$. In other words, while the forward noising processes for $\mathbf{X}$ and $\mathbf{A}$ are independently modeled given their initial states, the resulting variables $\mathbf{X}_t$ and $\mathbf{A}_t$ remain implicitly interdependent due to their dependence on $\mathbf{X}_0$ and $\mathbf{A}_0$ (that are dependent of each other). This conditional independence assumption aligns with standard practices in score-based graph generation literature, such as those discussed in [1, 2].

• Your question also highlights an exciting future research direction for the analysis of this paper: exploring the impact of replacing the independent noising processes with a jointly dependent one, potentially by comparing their convergence behaviors. We hypothesize that if the diffusion process could better reflect the dependencies in the original data (i.e., between $\mathbf{X}_0$ and $\mathbf{A}_0$), it may lead to improved learning. Specifically, aligning the noise structure with the data dependencies could help the score networks more effectively capture the interactions between features and topology—by providing samples with more consistent relationships throughout the diffusion process.

Thank you again for this valuable point. We will incorporate this discussion into the revised version of our manuscript, and hope our response has satisfactorily addressed your questions.

[1] "Score-based generative modeling of graphs via the system of stochastic differential equations." International conference on machine learning.

[2] "DiGress: Discrete Denoising diffusion for graph generation." The Eleventh International Conference on Learning Representations.

Dear Reviewer, thank you for the positive comments and thoughtful suggestions. These greatly help us in making our paper better. Below, we outline the efforts we have undertaken and plan to take in response to your suggestions.

Suggested Reference

Thank you for pointing out the relevant reference! It will help us further strengthen our results. We will make sure to include it in the revised version of the paper.

Empirical study improvement

Thank you very much for your thoughtful suggestions regarding the empirical study — we greatly appreciate the detailed and constructive feedback.

We have attempted to collect data from existing literature involving SOTA models, but so far have not had much success due to the variability in experimental setups. Real-world studies often differ across multiple factors simultaneously, making it challenging to isolate the effects of individual variables such as graph size or feature complexity. That said, we agree that this is a promising direction and will continue investigating it for future updates and revisions.

Regarding the evaluation metric: we chose KL divergence as our primary measure because our theoretical bounds are expressed in terms of KL divergence, allowing for a principled comparison between theory and experiment. While we acknowledge that more interpretable metrics could enhance accessibility, most evaluation methods for graph generation—especially when comparing distributions—ultimately rely on kernel-based similarity metrics (e.g., MMD, Gaussian kernel estimates, etc.). Developing more interpretable or task-specific evaluation metrics remains a meaningful open question in the field of generative modeling.

In response to your suggestion, we conducted an additional experiment using the Erdős–Rényi (ER) random graph model of connection probability $0.1$ [1]. While ER does not allow us to control structural features like degree heterogeneity (e.g., power-law vs. regular), it provides a clean testbed for examining the relative influence of graph size versus feature size, as well as the effect of normalization, under a controlled setting. The setup mirrors our experiments in the paper.

To quantify the effects, we further computed best-fit line coefficients to estimate the sensitivity of KL-divergence to changes in each variable:

As shown above, the results support our theoretical predictions: graph size has a more pronounced effect on convergence than feature size, and feature normalization improves performance. These trends are consistent with those observed in our original experiments.

Thank you again for your valuable comments. We will incorporate these new results and the accompanying analysis into the revised version of the paper.

[1] Newman, Mark, Networks: An Introduction

Dear Reviewer, Thank you for your insightful comments! Your questions have helped us sharpen the presentation of our technical contributions, and we sincerely appreciate the opportunity to clarify them here.

Why Not Formulate as a Single SDE on $\mathbf{G}_t$

You are absolutely right that, in principle, the coupled reverse SDEs for $\mathbf{X}_t$ (node features) and $\mathbf{A}_t$ (graph structure) could be rewritten as a single SDE over the joint variable $\mathbf{G}_t=(\mathbf{X}_t,\mathbf{A}_t)$. However, the two-process formulation is not just a modeling preference, but a technical necessity for capturing the rich structure and asymmetry in graph data. Specifically, graphs involve:

• Intra-structure dependency: among entries of $\mathbf{A}_t$.
• Intra-feature dependency: among entries of $\mathbf{X}_t$.
• Cross-dependency: between $\mathbf{A}_t$ and $\mathbf{X}_t$, which evolves through the shared time parameter and coupled score functions.

The evolution of these dependencies involves coupled score functions that dynamically influence each other. Representing these coupled processes as a single SDE would obscure their distinct dependency structures, hindering our ability to isolate and analyze the individual and cross-dependent behaviors clearly. Crucially, such an aggregation would mask critical insights into the non-isotropic effects of increasing graph size versus feature dimensionality and would obscure how topological properties (such as regular versus power-law structures) impact convergence.

Therefore, the two-process formulation not only matches more closely with the practical implementation (providing more practical insight) but also enables a finer-grained convergence analysis that reveals how these factors differentially affect generative performance—something not accessible in standard single SDE theory.

What Is Technically Novel and Important?

We would like to first emphasize that our contribution is the first rigorous theoretical extension of these techniques to score-based graph generative models (SGGMs). Given the critical applications of SGGMs in domains such as drug discovery and protein synthesis, understanding their convergence behavior is essential for ensuring reliability and efficacy. While our overall proof framework builds on classical convergence theory for score-based generative models (SGMs), as we acknowledged in the paper, our work introduces several significant technical innovations:

• Due to the distinct dependency structure in graphs and the two-process formulation (discussed above), the derivations in Lemmas (such as B.5–B.12) are novel extension of existing SDE results. These lemmas require careful handling of the cross-dependencies between $\mathbf{A}_t$ and $\mathbf{X}_t$, which are absent in standard (single-process) SGM analyses. This leads to new forms of error decomposition and convergence bounds tailored to graph-structured data (as demonstrated explicitly in Theorems 4.1–4.3).
• Another core technical contribution lies in linking convergence behavior to graph-specific properties. Our analysis uniquely leverages spectral graph theory tools to link convergence behaviors directly to graph characteristics (e.g., graph size/feature dimensionality and topology). These tools lead to novel insights, such as identifying a preference for certain graph structures (regular vs. power-law graph), which are absent from the traditional SGM convergence literature.

We sincerely appreciate your valuable feedback, which has allowed us to refine and strengthen our paper. We will incorporate these discussions into the revision and hope our response has satisfactorily addressed your concerns and questions.