A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations
Authors: Junwei Su
Chuan Wu
Venue: ICML 2025 poster (2025)
Keywords: graph generation
score-based generative model
convergence analysis
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: This paper provides a non-asymptotic convergent analysis for score-based graph generative models.

Abstract: This paper investigates the convergence behavior of score-based graph generative models (SGGMs). Unlike common score-based generative models (SGMs) that are governed by a single stochastic differential equation (SDE), SGGMs utilize a system of dependent SDEs, where the graph structure and node features are modeled separately, while accounting for their inherent dependencies. This distinction makes existing convergence analyses from SGMs inapplicable for SGGMs. In this work, we present the first convergence analysis for SGGMs, focusing on the convergence bound (the risk of generative error) across three key graph generation paradigms: (1) feature generation with a fixed graph structure, (2) graph structure generation with fixed node features, and (3) joint generation of both graph structure and node features. Our analysis reveals several unique factors specific to SGGMs (e.g., the topological properties of the graph structure) which significantly affect the convergence bound. Additionally, we offer theoretical insights into the selection of hyperparameters (e.g., sampling steps and diffusion length) and advocate for techniques like normalization to improve convergence. To validate our theoretical findings, we conduct a controlled empirical study using a synthetic graph model. The results in this paper contribute to a deeper theoretical understanding of SGGMs and offer practical guidance for designing more efficient and effective SGGMs.

A Non-Asymptotic Convergent Analysis for Scored-Based Graph Generative Model via a System of Stochastic Differential Equations
Junwei Su
Chuan Wu
Abstract
1. Introduction
Score-based graph generative models (SGGMs) have proven effective in critical applications such as drug discovery and protein synthesis. However, their theoretical behavior, particularly regarding convergence, remains underexplored. Unlike common score-based generative models (SGMs), which governed by single stochastic differ- ential equation (SDE), SGGMs involve system of coupled SDEs. In SGGMs, the graph struc- ture and node features are governed by separate but interdependent SDEs. This distinction makes existing convergence analyses from SGMs inap- plicable for SGGMs. In this work, we present the first non-asymptotic convergence analysis for SGGMs, focusing on the convergence bound (the risk of generative error) across three key graph generation paradigms: (1) feature generation with a fixed graph structure, (2) graph structure gener- ation with fixed node features, and (3) joint gen- eration of both graph structure and node features. Our analysis reveals several unique factors spe- cific to SGGMs (e.g., the topological properties of the graph structure) which affect the convergence bound. Additionally. we offer theoretical insights into the selection of hyperparameters (e.g., sam- pling steps and diffusion length) and advocate for techniques like normalization to improve conver- gence. To validate our theoretical findings, we conduct a controlled empirical study using syn- thetic graph models, and the results align with our theoretical predictions. This work deepens the theoretical understanding of SGGMs, demon- strates their applicability in critical domains, and provides practical guidance for designing effec- tive models.
Graph-structured data is ubiquitous across wide range of domains, including social networks, biological systems, recommendation engines, and knowledge graphs (Newman, 2018). The graph generation problem involves creating new graphs that closely resemble real-world data, a task critical to many graph-based applications. In recent years, score- based graph generative models (SGGMs) (Niu al., 2020; Jo et al., 2022; Vignac et al., 2022; Chen et al., 2023c) have emerged as a flexible and powerful approach, deliver- ing state-of-the-ar empirical performance in graph gener- ation tasks. These models have shown significant impact in critical areas such as molecular generation (Gnaneshwar et al., 2022), protein design (Lee et al., 2023c), graph-based recommendation systems (Liu et al., 2024), and automated program generation (Zhu et al., 2022).
SGGMs are a subclass of the broader family of score-based generative models (SGMs), also referred to as diffusion probabilistic models (Song et al., 2020a; Ho et al., 2020; Nichol Dhariwal, 2021; bocl-Dickstein al., 2015; Song & Ermon, 2019; Song et al., 2020b; Li al., 2024; Yang et al., 2024). SGMs generate data by learning score func- tion (see Sec. 3 for more details), which represents the gra- dient of the log probbabibbby of the data distribution. These models conceptualize the data generation process as a diffu- sion process, where data is progressively corrupted by noise and then reconstructed through a reverse process. The for- ward process involves gradually adding noise over several steps, transforming the data into simple distribution (e.g.. Gaussian noise), and is governed by stochastic differen- tial equation (SDE) (Song et al., 2020b). In the reverse process, the model uses the learned score function to iter- atively denoise the data, starting from random noise and guiding step-by-step toward the original data distribution. To efficiently approximate this reverse process, discrete sampling approach is employed, using numerical methods such the Euler- Maruyama scheme the exponential integrator (Chen et al., 2023a).
'School of Computing and Data Science. University of Hong Kong. Correspondence to: Junwei Su <jun- weisu www.eeecoocnncuuu....... Chuan Wu <cwu@cs.hku.kk>.
Understanding the convergence behavior of SGGMs is both theoretically and practically crucial (Suh & Cheng, 2024; Huang et al., 2024; Chen al., 2022a; 2024a; Lee et al., 2023b). Convergence bounds quantify the discrepancy be-
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Convergent Analysis of Graph Diffusion Generation
Tween the generated graphs and the true data distribution, indicating whether the diffusion process will eventually produce samples that align with the desired target distribu- tion. This is particularly important for SGGMs, as conver- gence guarantees the reliability and validity of the generated graphs, which are used in high-stakes applications like drug discovery. Furthermore, understanding convergence pro- vides valuable insights into practical considerations, such as the selection of hyperparameters (e.g., sampling steps and diffusion length). Convergence analysis also helps iden- tify sources of error and guides the development of more effective models.
factors and insights from this analysis with the practical SGGM framework. This includes not only understanding the theoretical results in the context of graph data but also leveraging these insights to guide model design decisions, such as hyperparameter tuning (e.g., sampling steps, dif- fusion length) and implementing regularization techniques. These challenges make the convergence analysis of SGGMs both novel and non-trivial.
Our Contributions and Results. We present comprehen- sive formulation for SGGMs that captures the complex in- terdependencies between graph structure, node features, and the use of graph neural networks (GNNs). Based on this for- mulation, we present a detailed non asymptoti convergence analysis for three common graph generation paradigms: 1) node feature generation with fixed graph structure (Theo- rem 4.1). 2) graph structure generation with fixed node fea- tures (Theorem 4.2), and 3) joint generation of both graph structure and node features (Theorem 4.3). Our analysis provides a detailed account of the factors influencing con- vergence bound of SGGMs. In addition, our results reveal several key insights and implications (Sec. 4) regarding the convergence behavior of SGGMs:
Gap in Existing Research. Despite the empirical success of SGGMs in high-stakes applications, their convergence behavior remains underexplored. Most existing research has primarily focused on SGMs derived from the image domain (Yegin & Amasyalı, 2024; Li et al., 2024; Wang et al., 2024; Chen et al., 2024b; Benton et al., 2023). There are two key differences between SGGMs and SGMs. First, while the generative process of SGMs is governed by a sin- gle SDE, SGGMs, due to the nature of graph data (which includes both graph structure and node features), involve system of coupled SDEs (Jo al., 2022; Niu al., 2020). In SGGMs, the graph structure and node features are gov- erned by separate but interdependent SDEs. Second, SGM convergence analyses often assume independence between data elements (c.g.. pixels in images), while in SGGMs, the graph structure and node features are inherently coupled and interdependent (Deshpande et al., 2018). Thus, the for- mulation and convergence analysis of SGGMs must account for these relationships. As result, existing convergence analyses for SGMs cannot be directly applied to SGGMs, highlighting the need for new theoretical formulations and analyses to understand and ensure their convergence.
1. Graph size vs. feature dimensionality: There is non- isotropic effect between the graph size (number of nodes) and feature dimensionality. Specifically, increasing the size of the graph leads to a greater risk of generative error (i.e., larger convergence bounds) than increasing the dimensional- ity of node features. This finding helps explain why SGGMs are empirically effective for smaller graphs, even when the node features are complex (Jo et al., 2022).
2. Topological properties of the graph structure: The topological properties of the graph significantly influ- ence the convergence bounds of SGGMs. In particular, graphs with heterogeneous degree Distributions-wher some nodes have significantly more connections than oth- ers-tend to result in a larger generative error. Our findings suggest that SGGMs perform more reliably when generat- ing graphs with more uniform degree distributions, as the risk of large error is lower in these graphs. This insight is critical for applications where the generated graphs need to closely match real-world graph structures.
Problem Studied and Challenges. this paper, we ad- dress this gap by extending the convergence analysis to SGGMs. Several key challenges arise in this extension: First, the interdependency between graph structure and node features requires a careful and nuanced formulation. Unlike the independent elements typically found in conventional SGMs, the graph structure and node features in SGGMs are deeply interconnected. Accurately modeling this interde- pendency is crucial for capturing the true generative process of SGGMs and deriving meaningful insights. Second, this interdependency creates entangled dynamics in the genera- tive process. Changes in the graph structure directly affect the node features, and vice versa. This reciprocal influ- ence complicates the convergence analysis, as conventional methods that assume independence are no longer applica- ble. The simultaneous evolution of both the graph structure and node features calls for the development of new tools and methodologies to analyze the convergence of the entire system effectively. Finally, it is essential to connect the
3. Impact of norms on feature matrices: Smaller norms in the feature matrices reduce the risk of generative error in the generated graphs, providing theoretical support for employing normalization techniques in SGGMs. By control- ling the scale of the feature matrices, these techniques help tighten the convergence bounds, resulting in more stable and accurate graph generation.
The empirical results from our controlled experiments us- ing synthetic graphs are consistent with our theoretical pre- dictions, thereby validating our analysis and conclusions.
2

---

Convergent Analysis of Graph Diffusion Generation
These results enhance the theoretical understanding of SG- GMs, confirm their applicability in high-stakes applications, and provide practical insights for designing and deploying more effective SGGMs.
trast, SGGMs involve system of dependent SDEs, with separate equations governing the graph structure and the node features, respectively. It remains unclear how this in- tercomnectedness nature of graph data is manifested in the convergent behavior of SGGMs. In this paper, we address this gap by providing a non-asymptotic convergence anal- ysis for SGGMs, accounting for the distinctive challenges posed by graph data.
2. Related Work
Graph Generation Methods. The graph generation prob- lem has long history of study, with rule-based random graph models traditionally dominating the field (Barabási & Albert, 1999; Holland et al., 1983; Erdös et al., 1960; Newman et al., 2002). A prime example of such models is the Stochastic Block Model (SBM) (Holland et al., 1983), which is based on the observation that real-life graphs often consist of densely connected blocks of vertices exhibiting similar behaviors (Abbe, 2018; Newman et al., 2002; New- man & Girvan, 2004; Newman, 2006; Karrer & Newman, 2011; Cherifi et al., 2019; Su & Marbach, 2022). How- ever, such rule-based models fail to capture the complex and nuanced distribution of graph-structured data observed in real-world problems (Russell& & Norvig, 2016). As a result, the focus has shifted towards deep learning-based methods that can model more intricate graph properties (Zhu al., 2022; You et al., 2018; Xie al., 2021; Liao et al., 2019; Li et al., 2018; Jensen, 2019; Fu et al., 2021; De Cao & Kipf, 2018; Zang& & Wang, 2020; Simonovsky & Komodakis, 2018). Among these, SGGMs have emerged as a promis- ing approach, showing impressive empirical performance in graph generation (Niu et al., 2020; Jo et al., 2022; Vignac et al., 2022: Chen et al., 2023c). Due to the nature of graph data, the standard formulation of SGGMs involves sys- tem of stochastic processes, either manifested as Markov chain (discrete) (Chen et al., 2023c; Vignac et al., 2022) or SDE (continuous) (Jo et al., 2022: Niu et al.. 2020). In this paper, we focus on the formulation with SDE, and point out our analysis can be extended to the discrete version by replacement of suitable theoretical tools (Sec. 6).
3. Preliminaries and Problem Formulation
In this section, we introduce the formulation SGGMs via a system of SDEs, and different graph generation paradigms.
Notation. We use bold upper and lower-case letters to denote vectors and matrices. For two functions ((x) 2 O and (xx) 2 O, we write f(x) S g(x) if f(x) S c- g(x) for some absolute constant e > 0. For a given SDE, we use æ to denote the forward continuous process, I to denote the backward continuous process and T. to denote the backward approximated process. A graph G can be formally defined as a two-tuple g = (X, A), where X E R NFF is the node feature matrix and A E RNXN is the adjacency matrix representing the graph structure. Here, N is the number of nodes in the graph and I' is the dimension of node features. In addition, we use N(a, b) denote Gaussian distribution with mean a and variance b.
3.1. SGGMs via System of SDEs.
SGGMs consist of three main components: 1) a forward process, 2) a reverse process, and 3) a sampling process that approximates the reverse process to facilitate data genera- tion. In the following sections, we provide an introduction to each of these components.
1. FORWARD PROCESS.
Formally, the forward diffusion process can be described by the trajectory of random variables {g. = (X,, A.) ArEo.TT in fixed time horizon [0, T]. where Go = (Xo, Ao) is sampled from the data distribution P(Go) (what we want to learn). This process is modelled using the following system of dependent SDEs:
Convergent Analysis of SGMs. Theoretical studies on SGMs have garnered significant attention in recent years (De Bortoli al., 2021; Zhang et al., 2024; Lee et al., 2022; 2023a; Wang et al., 2024; Chen et al., 2024b; Li et al., 2023; Benton et al., 2023; Chen et al., 2022a; 2023a:b). A central focus of these studies is examining the conver- gence behavior of these models, specifically how well they approximate the true data distribution. Existing research has shown that, under suitable smoothness and regularity assumptions on the score functions, SGMs provide provable guarantees for convergence, meaning that the generated sam- ples increasingly resemble the true data distribution as the number of iterations increases (Chen et al., 2022a; 2023a;b). However, much of the existing work has been motivated by tasks such as image generation, where the generative process is governed by a single stochastic process. con-
dX. fx( t) dt + 9x t) dWx. dA, = (A () di + SA (G,, 1) dW
(3.1)
where the first equation is the forward SDE for the node feature and the second equation is the forward SDE for the graph structure. fx(.) and SA (-) are drift coefficients, and (x) and (.) are scalar diffusson coefficients. Wx. WA are standard Wiener processes (also known as Brownian mo- tion) acting in the node feature space and graph structure space, respectively. This diffusion process gradually adds
3

---

Convergent Analysis of Graph Diffusion Generation
noise the initial graph samples, and at the terminal time T, the sample Gr (Xr, Ar) follows a simple convergent distribution (also referred to as the prior distribution) which we denote as A and IIx for the graph structure process and node feature process respectivelys. In this paper, we focus on the commonly used standard Gaussian distribu- tion (with zero mean and unit variance) as the convergent distribution.
Training SGGMs. The partial score functions can be es- timated by training time-dependent neural networks (also referred to the score networks) se(.) and s.).,, that
se (Gr, t) R Vx P(Ge), (b, ~ VA. log P(G),
where 0 and & are learnable parameters. Since the drift coefficients of the forward diffusion process are linear, the transition distribution P(Gr(9o) can be decomposed terms of X, and A,, as follows:
We focus analysis on the following choices of the drift and diffusion coefficients:
P(G.)9)) (
fx(C,, t) -1/2gx X),,
Notably, is easy sample from the transition distributions of each component, P(X, Xx)) and P Ao), as they are Gaussian distributions with mean and variance determined by the coefficients of the forward diffusion process given by Eq, 3.3. Then, with the decomposition above, training objectives of SGGMs generalize the one from (Song et al., 2020b) to minimizing the estimation of partial scores on the given graph dataset:
t) -1/29A (9c, (,,tt),, A.., tx( (9, t) 1. 1.
(3.2)
These choices match those in the original SGMs pa- per (Song et al., 2020a; Jo et al., 2022), and are commonly used for similar convergence analysis (Chen et al., 2023a). We emphasize that our analysis can be adapted for some other choices of linear drift terms and constant variance functions as well (we provide a further discussion on this regard in Appendix A).
min E, e
Egg Ea.1o. (10( - Vx log (X, log
min E, Es, Bo, ( VA log (A.) Ao)
Under these choices of coefficients, the forward process becomes the Ornstein- Ornstein-Uhlenbeck Uhlenbeck (OU) process (Jacobsen, 1996). which has an explicit conditional density:
The expectations above can be efficiently computed us- ing Monte Carlo estimation with samples Go, G.). For completeness, we provide a more detailed derivation and discussion on the training objectives in Appendix A.
X, X, 1//21 Xo, (1 e -01==""NNx0 IxxF),
Ao ~ N(e 1/21 Ao, (1 - INxN).
(3.3)
Functional Form of Score and Score Networks. To cap- ture and model the dependencies between graph structure and node features, GNNs, such as Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017) and Graph Trans- formers (Dwivedi & Bresson, 2020), are used the score networks for SGGMs. A defining characteristic of GNNs is their usage of graph structure to combine and update the representation of each node or edge. From a func- tional perspective, GNNs can be expressed as a function (T(A)T where T and T' represent some transfor- mations applied the adjacency matrix A and the feature matrix X. respectively. For simplicity and interpretability. in this paper, we focus on the case where T and T'' are identity mappings, corresponding to a vanilla GCN without the nor- malization. Our analysis and results can be extended to other transformations by replacing A, X with T(A), (X) In addition, we focus on a feasible setting where we assume certain regularity conditions on the data distribution, and that the score function aligns with the functional form of GNNs.
Moreover, the OU process converges exponentially to the standard Gaussian distribution:
KL(P(X,)) Ix) S 'KL(P(X))| Ixx)
KL(P(A,)) IIA) S E (KL(P(A))
where KL denotes the Kullback-Leible (KL) divergence used to quantify the discrepancy of two distributions (see Appendix D for a further discussion).
3.1.2. REVERSE PROCESS.
The reverses process aims to generate graph samples from the convergent distribution by reversing the forward process. This is also described by a system of SDEs driven by the
score function:
dx, [1/2X; Vx log P(G)] di + dWx,
A [1/2A, VA P(G)) dt - dW
(3.4)
where X,, A,, Wx. WA are the respective reverse pro- cesses in time. Vx log ( and VA. log (P,)) are the partial score (partial gradient of log- bog-biibility of graph dis- tribution) with respect to node feature and graph structure respectively.
The data distributions for node fea- tures and graph structure are twice differentiable and have bounded second moments, i.c.,
Assumption 3.1.
Hix = E|| 00, HA = -EEAA < Co.

---

Convergent Analysis of Graph Diffusion Generation
Furthermore, the score functions V log Pp, are L-Lipschitz and can be written function of the form I (A,X.).
where AW, A and AW, A represent the increment in the Wiener processes within the interval.
Exponential Integrator Scheme provides a more accurate method for solving SDEs, especially when the system has a semi-linear structure. It discretizes the nonlinear terms while retaining the continuous dynamics arising from the linear terms. Specifically, the nonlinear term discretized while the linear part evolves continuously according to:
The regularity conditions such as continuity, boundedness and smoothness of data distributions and score function are commonly employed in other similar studies (Benton et al., 2023; Chen et al., 2022a; 2023a;b). We note that the smooth- ness assumption could be relaxed in recent analysis (Chen et al., 2023a); however, such relaxation would complicate the results. In this paper, we target more user-friendly re- sults for better interpretability and connection with practical settings, and hence retain these standard assumptions.
K/11 2//25 +2 22(2//2tt - -1) so so (2)
+ Vedln -Ek,
3.1.3. SAMPLING PROCESS.
1/+1 =e 1/200x Are 2 (2 (cl/25te-1) 80 (0 1/2
discrete-time approximation of the sampling dynamies in Eq. 3.4 is required for practical implementation. Let 0 = to S f1 Σ
+ Veet - 16'
(3.6)
S tm = T be the discretization points. For the k-th discretization step (1 < k S M). we denote At,= == tx= - as the step size for the k-th step. k be the corresponding discretization points in the reverse-process SDE. In addition, we make the following assumption on the learned score functions with respect to the discretization.
where E and E are sampled from standard Gaussian.
3.2. Graph Generation Paradigms
Let 1/2 = T - tM-k
For graph generation tasks, there are three distinct paradigms, each with its unique significance.
Assumption 3.2. For both score functions s.()) and s.)), we assume that there exist constant cx, CA for any S i i M:
Joint Generation of Graph Structure and Node Features. This paradigm aims to simultaneously generate both the graph structure and node features. It is particularly signifi- cant in biological applications, such as protein design (Vi- gnac et al., 2022: Jo et al., 2022), where the graph structure represents the interactions between proteins (nodes), and the node features describe attributes like protein function, structure, or expression levels. Jointly generating both com- ponents ensures that the resulting graph is biologically plau- sible, accurately reflecting both the interaction patterns and functional properties of the proteins. The corresponding forward process is given by Eq. 3.1.
Al. E V log P(G.) - so (:,l S &
T
M
V log P(G..) - sQ (G 1:)l S e
Assumption 3.2 commonly used in convergence analyses of diffusion models with general distributions (Chen al., 2022a; Zhang et al., 2024; Chen et al., 2023a). We will further discuss in Sec. 6 how we can extend the analysis and relax this assumption to obtain a more precise (but less general) result, with additional modelling assumptions on the underlying distribution.
Node Feature Generation with Fixed Graph Structure. In this paradigm, the goal is to generate node features while maintaining a fixed graph structure. This is particu- larly important in domains like molecular graph generation, where the connectivity of atoms is predefined, but their properties-sun as chemical features- can vary (Sanchez- Lengeling et al., 2017: Simonovsky & Komodakis, 2018; Jin et al., 2018). By focusing on feature generation, this paradigm enables the exploration of diverse attribute combi- nations while maintaining a consistent structural backbone, facilitating the generation of realistic and varied instances for a given graph structure. In this setting, node features are generated based on fixed graph structure. The correspond- ing forward process is:
We consider two types of discretization schemes that are widely used in existing works: the Euler- Marer-Maruyama scheme and the exponential integrator scheme.
Euler-Maruyama Scheme is a simple, first-order discretiza- tion method that approximates an SDE by applying a first- order Taylor approximation. For approximated trajectory X, A, with the discrete scheme, the progression rule at the k-th step is given by:
& -x,; + 11/28,; - -50 5o( (1)) Ale + A/e Wxx
Aec. = - + -1/2Ar so
(2)
Atk + At& WA.
dx,- = 1/2X, dt + dWx,
dA, = 0, Ao = A
(3.7)
(3.5)
5

---

Convergent Analysis of Graph Diffusion Generation
where A A is the fixed graph structure that remains constant during the feature generation process.
and 3.2 and supposing the fixed feature matrix X has bounded norm, i.e., |x112 I xx, we have the following results:
Graph Structure Generation with Fixed Node Features. This paradigm focuses generating the graph structure while keeping the node features fixed. It is particularly useful when the node features are known or predefined, but the relationships between the nodes (i.c., the graph structure) need be learned or generated (Martínez et al., 2016; Zhang & Chen, 2018; Benson et al., 2016; Niu et al., 2020). For
For exponential integration scheme,
((((F(A))|P((A)))) S (Il N27E-T +TeA
M
M
+ N
L 0x
(4.3)
example, in social network analysis, the characteristics of individuals (c.g., age, location, interests) are known, but the interactions or connections between them need to be inferred. In this setting, the generating process focuses solely on the graph structure, as modeled by:
For Euler-Maruyana, scheme,
KL(P(A))|| S (HA - +T
M
M
+ (N + Nº) Σ AC + (N Hx)
AC.
dX;- - 0, X X dA, = 1/2A, + AWAi
(4.4)
(3.8)
Theorem 4.3 (Convergence Bound of Joint Generation of Graph Structure and Node Features). Consider the gruph generation paradigm in Eq. 3.1. Under Assumptions 3. 1
where X* is the node feature matrix that remains constant during the feature generation process.
and 3.2, we have the following results:
4. Main Results
For exponential integration scheme,
We next present our main results on the convergence behaviour of SGGMs across the three graph generation paradigms. We first present the convergence results for each paradigm, deferring the detailed discussion of these results until after all paradigms have been presented.
KL(P(X.) (F((X) S (lxx + NF)e T +TEX
M
+NFL
L
L
A
A
KL(P(Au) (P((A) S (HA + N -T + TTA
)-
4.1. Convergence Results
M 1
N
A
Σ A
(4.5)
Theorem 4.1 (Convergence Bound of Node Feature Gener- ation with Fixed Structure). Consider the graph generation paradigm in Eq. 3.7. Under Assumptions 3.1 and 3.2 and supposing that the fixed graph structure A has bounded norm, i.e.,
For Marierrmaauaamaa scheme,
< ||2
x we have the following results:
(I. S (Hx + NN +T>
For exponential integration scheme,
+ +NFL++NF) Σ AC, (NFL+ + Hxx) Σ At.
(I(P((x)|I((X))) S
(Hx +
+NF)
+ +
(L((()))I((OO) (HA + NNT +Te
M T
+NFL
A
At
Σ
At
(4.1)
M
+ +
Σse (N HAN Σ A
For Euler-Maruyama scheme,
(4.6)
KL(P(X)))IP((X)) S (Hx NF)e + Tex
M + ONFL NNE) Σ + (NFL+ Hx)
M
The proofs of Theorem 4.1, Theorem 4.2 and Theorem 4.3 can be found in the Appendix.
At
3
(4.2)
4.2. Discussion and Insights.
Theorem 4.2 (Convergence Bound of Graph Structure Gen- eration with Fixed Node Features). Consider the graph generation paradigm Eq. 3.8. Under Assumptions 3.1
In this section, we provide a detailed discussion of the con- vergence results, highlighting several interesting insights and their implications.
6

---

Convergent Analysis of Graph Diffusion Generation
Source of Error. From Theorems 4.1, 4.2, and 4.3, we identify three primary sources of generative errors in SG- GMs: 1) Distance to convergent distribution: represented by the first term, (HA + NN and (Hx + FF""""" in the convergence bounds, this error quantifies how far the forward process has transformed the initial data distribution towards the convergent distribution. Interestingly, is inde- pendent of the initial data distribution and is influenced by the dimensionality, second moments of the data distribution, and the length of the diffusion process; 2) Score estimation error: captured by the second term, Te& and T in the convergence bounds, this eгror arises from inaccuracies in estimating the underlying score functions; 3) Discretization error: represented by the remaining terms the conver- gence bounds, this error induced by the discretization of sampling scheme.
Remark 4.6. Applying the normalization technique X in the feature generation paradigm can improve the conver- gence bound of SGGMs.
Hy peprpaaraeetrrs. Next, we discuss the implications of the convergence results for the hyperparameters involved in SGGM learning, particularly the length of the diffusion process T and the sampling step M. For clarity, we as- sume uniform discretization steps and focus on the joint generation paradigm with the exponential integrator scheme. The implications also extend to other paradigms and the Euler-Maruyama scheme (see Appendix D).
Corollary 4.7. Suppose the discretization step is uniform At, = T/M I 1, E 1,... M. Then the convergence results of SGGMs under the exponential integrattr scheme are given by
(L(P(x))IP(XT)) 2
Connection with Graph Data. The convergence bounds reveal several interesting connections between the prop- erties of the graph data and the convergence behavior of the SGGM. The scale of graph data is determined by two factors: the size of the graph N and the dimension of the features F. Our convergence results show that these two fac- tors affect convergence behavior in a non-isotropic manner. Specifically, we have the following remark:
2FL2T M
(Hx + NNF) -T T +T&x+
+
(L(P(A))I((AT)) 2
N2
(HA+ + NN +T2
M
Furthermore, taking
Remark 4.4. The performance of SGGMs deteriorates more significantly as the graph size increases compared increase in the feature dimensionality.
Hx + NF
Hx + N2
T max log
,log
X
2
A
NFFL222
22
This is evident from the convergence bounds, where the bounds grow quadratically with respect to graph size but only linearly with respect feature dimensionality. This also explains why SGGMs perform well for smaller graphs, even when the features are complex (Jo et al., 2022).
M = max
2
we have that the overall generative error of SGGMs is bounded by the score estimation errors, i.e.,
& KL(P(A)) IIE
Additionally, the terms a and dx, which represent bounds on the norms of the graph structure and feature matrices, are significant in the feature generation and structure generation paradigms respectively. Larger a and ox lead to a larger risk of generative errors (i.e., larger convergence bound). Based on spectral graph theory, A has an intrinsic connec- tion with the graph structure. For example, dA is closely related to the maximum degree of the graph (Spielman, 2012):
This corollary provides a clearer formulation for the conver- gence bounds and offers guidance for choosing the hyperpa- rameters. It is evident that there is a trade-off in the length of the diffusion T: larger values of T lead to smaller er- rors and better convergence the target distribution, while larger sampling step M (which increases computational complexity) is required to control the sampling error.
Sampling Scheme. When comparing the convergence bounds under the -aler-Maruyama scheme and the expo- nential integrator scheme (e.g., Eq.4.1 vs. Eq.4.2), we observe that the Euler-Maruyama scheme introduces ad- ditional error terms due to higher-order discretization errors. As a result, the Guler-Maruyana scheme leads to larger convergence bound than the exponential integrator scheme. Therefore, theoretically, the exponential integrator scheme is expected to outperform the Buler-Maruye scheme in graph generation tasks. This finding aligns with the results in SGMs (Chen et al., 2023a).
A S max (g).
Based on this connection, we make the following remark: Remark 4.5. SGGMs are better at learning and generating graphs with uniform degree distributions (more regular-like) than graphs with heterogeneous degree distributions (e.g., pawer-law graphs).
On the other hand, ox, can be reduced with the commonly used normalization techniques, leading to a smaller conver- gence bound. This insight results in the following remark:
7

---

Convergent Analysis of Graph Diffusion Generation
KL-Divergence
Divergencce
Requiar Graph
Normalization
10
Power-low Graph
Without Normalization
10
50
100
200
500
10
50
100
200
500
Graph Size
Feature Size
(a) Regular Graph
(b) Power-law Graph
(c) Craph Size and Structure
(d) Feature and Normalization
Figure 1. Performance SGGMs. Fig. (()) and Fig. ((b) are examples of regular and power-law graphs generated from our synthetic graph model. Fig. I(c) plots the performance of SGGMs with respect to increasing graph size for regular and power-law graphs. The feature size in this experiment fixed to 50. Fig. ((d) plots the performance of SGGMs with respect to increasing feature size w./woo. normalization. The graph size is fixed to 50.
5. Empirical Study
paradigm as the graph size increases. As predicted, SGGMs perform better regular graphs compared power-law graphs. Fig. (d) illustrates the performance of SGGMs as the feature size increases. As predicted, applying normal- ization improves SGGMs' performance. Comparing the trends in Fig.1(c) and Fig. I(d), we observe that SGGMs' performance degrades more rapidly with increasing graph size than with increasing feature size.
We next present an empirical study to validate our theoretical results. Specifically, we answer the following questions:
QI: Is SGGM more effective learning and generating regular graphs compared to power-law graphs in the feature generation paradigm?
Q2: Does applying normalization techniques improve the convergence SGGM in the feature generation paradigm?
6. Concluding Discussions
Q3: Does increasing graph size result more significant performance degradation than increasing feature size?
This paper presents a novel convergence analysis for SG- GMs across three common graph generation paradigms. Our analysis identifies the primary sources of generative error in SGGMs and provides valuable insights into the factors unique graph data that influence their convergence behay- ior. Specifically, examine how graph size, structure, and feature dimensionality affect the convergence bound. Ad- ditionally, we offer practical recommendations for improv- ing model performance, including the use of normalization and the selection of key hyperparameters, such as diffusion length and sampling step size. Our empirical study using synthetic graph data validates the theoretical predictions. Overall, this work advances the theoretical foundation of score-based generative models, confirms the applicability of SGGMs in critical applications, and provides actionable insights for their effective use in graph generation tasks.
We conduct controlled experiments using synthetic graph models, consistent with other theoret- ical studies, examine how the performance of SGGMs varies with changes in graph size, graph structure (regu- lar vs. power-law), feature size, and the application of normalization techniques. To generate power-law graphs, we employ the well-known Barabási-Albert model (Pósfai & Barabási, 2016). Node features for all experiments are drawn from Gaussian distribution with mean of and variance of (to distinguish them from the convergent distribution). The SGGM is implemented using the hy- perparameters specified in the theoretical analysis, with diffusion length T' = 100 and sampling steps M = 500, and a simple one-layer GCN as the score network. For sim- plicity, we use uniform discretization and the exponential integrator scheme to facilitate the sampling process. Each experiment generates 200 independent samples, which are then split into training, validation, and test sets in 6:2:2 ratio. Each experiment consists of five independent trials, with the results averaged across these trials to ensure statisti- cal robustness. Further technical details of the experiments and implementation can be found in Appendix
Experimental Setup.
6.1. Future Works
Learning Process. outcome of the learning process, as specified in Assump- tion 3.2. However, in practice, the estimation (or learning) of score functions is subject to errors that accumulate over time as the score network learns from data. These errors are influenced by the specific behavior of the learning algorithm. Future work could incorporate the dynamics of the learning process in SGGMs, as explored in studies such as (Chen et al., 2022a:b; Benton et al., 2024: Zhu et al., 2023), to gain a more nuanced understanding of SGGMs' behavior. This
Our current analysis assumes a static
The experimental results, summarized in Fig.1, provide affirmative answers to the questions (Q1-Q3) and validate our theoretical predictions. Fig.1(0) shows the performance of SGGMs the graph structure generation
Results.
8

---

Convergent Analysis of Graph Diffusion Generation
would be especially valuable for addressing challenges like sample complexity in SGGMs and for providing insights into their empirical performance.
Chen, H., Lee, H., and Lu, J. Improved analysis of score- based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Con- ference on Machine Learning. pp. 2023a.
PMLR,
More Precise Analysis with Synthetic Graph Model.
The analysis presented in this paper does not assume any spe- cific structure for the data distribution, making it applicable to general smooth and bounded distributions. However, to make the analysis more precise, one could impose additional structural assumptions on the underlying data distribution, similar to case studies with Gaussian mixture models in SGM research (Chen al., 2024b; Shah al.. 2023). A natural extension for graph data would be assume that the graph is generated from the contextual stochastic block model (Deshpande et al., 2018). Integrating this modeling choice could lead to more accurate convergence bounds and provide valuable insights that would require a more detailed, fine-grained analysis.
Chen, M., Huang, K., Zhao, T., and Wang, M. Score approx- imation, estimation and distribution recovery of diffusion models on low-dimensional data. In International Con- ference on Machine Learning, pp. (672-4712. PMLR, 2023b.
Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209. /215, 2022a.
Chen, S., Chewi, S., Lee, H., Li, Y., Lu, J., and Salim, A. The probability flow ode is provably fast. Advances in Neural Information Processing Systems, 36, 2024a.
Impact Statement
Chen, S., Kontonis, V., and Shah, K. Learning general gaussian mixtures with efficient score matching. arXiv preprint arXiv:2404 18893, 2024b.
This paper presents work whose goal is to advance the under- standing of score-based graph generation methods. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, X., He, J., Han, X., and Liu, L.-P. Efficient and degree- guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.04111 2023c.
Acknowledgement
Chen, Y., Chewi, S., Salim, A., and Wibisono, Improved analysis for a proximal algorithm for sampling. In Confer- ence Learning Theory, pp. 2984-3014. PMLR, 2022b.
We would like to thank the anonymous reviewers and area chairs for their helpful comments. This work was supported in part by grants from Hong Kong RGC under the contracts 17207621, 17203522, and C7004-22G (CRF).
Cherifi, H., Palla, G., Szymanski. B. K., and Lu, X. On community structure in complex networks: challenges and opportunities. Applied Network Science, 4(1):1-35, 2019.
References
Abbe, E. Community detection and stochastic block mod- cls: recent developments. Journal of Machine Learning Research, 18(177):1-88) 2018.
Chewi, S., Erdogdu, M. A., Li, M., Shen, R., and Zhang, M. S. Analysis of langevin monte carlo from poincare to log-sobolev. Foundations of Computational Mathematics, pp. 1-51, 2024.
Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439):509-511 1999.
De Bortoli, V., Thornton, J., Heng, J., and Doucet, A. Diffu- sion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34: 144116995-7709, 2021.
Benson, A. R. Gleich, D. F., and Leskovec, J. Higher- order organization of complex networks. Science, 353
(6295):163-166 July 2016. ISSN 1095-9203. doi: 10. 1126/ccience..ad0922. URL http::/tp///... http//xx..io//////ooo/////ooooot doi. www../oogg/////oo 10. http:/iiinc..adddaae...
De Cao, N. and Kipf, T. Molgan: An implicit genera- tive model for small molecular graphs. arXiv preprint arXiv: 1805. 11973, 2018
Benton, J., Deligiannidis, G., and Doucet, A. Error bounds for flow matching methods. arXiv preprint arXiv:2305. 16860, 2023.
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Con- textual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018
Benton, J., Bortoli, V., Doucet, A., and Deligiannidis, G. Nearly d-linear convergence bounds for diffusion models via stochastic localization. 2024.
Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. arXiv preprint arXiv:20/2.09699, 2020.

---

Convergent Analysis of Graph Diffusion Generation
Erdós, P., Rényi, A., al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
Lee, H., Lu, J., and Tan, Y. Convergence for score-based generative modeling with polynomial complexity. Ad- vances in Neural Information Processing Systems, 35: 22870-22882, 2022.
Fu, T., Gao, W., Xiao, C., Yasonik, J., Coley, C. W., and Sun, J. Differentiable scaffolding tree for molecular opti- mization. arXiv preprint arXiv:2109. 10469, 2021.
Lee, H., Lu, J., and Tan, Y. Convergence of score-based generative modeling for general data distributions. In In- ternational Conference on Algorithmic Learning Theory, pp. 146-985. PMLR, 2023a.
Gnaneshwar, D., Ramsundar, B., Gandhi, D., Kurchin, R., and Viswanathan, V. Score-based generative models for molecule generation. arXiv preprint arXiv:2203.04668, 2022.
Lee, H., Lu, J., and Tan, Y. Convergence for score-based generative modeling with polynomial complexity, 2023b. URL www.httpps//om. /ttpp:s////xvvvei////eee http:iiv.rrrr/b///////a/// aaa//bs/222000 06227.
Hagberg, A., Swart, P., and S Chult, D. Exploring net- work structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab,LL, Los Alamos, NM (United States), 2008.
Lee, J. S., Kim, J., and Kim, P. M. Score-based generative modeling for de novo protein design. Nature Computa- tional Science, (15):382-392 2023c.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851, 2020.
Li, G., Huang, Y., Efimov, T., Wei, Y., Chi, Y., and Chen, Accelerating convergence of score-based diffusion mod- els, provably. arXiv preprint arXiv:2403.03852 2024.
Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social nelworks, 502:1109-137, 1983.
Li, P., Li, Z., Zhang, H., and Bian, J. On the generaliza- tion properties of diffusion models. Advances in Neural Information Processing Systems, 36:2097-2127, 2023.
Huang, D. Z.., Huang, J., and Lin, Z. Convergence analysis of probability flow ode for score-based generative mod- els. 2024. URL https: / httpaaaxivvv..... http://wwww...r////////////// 09730.
Li, Y., Vinyals, O., Dyer, C., Pascanu, R., and Battaglia, P. Learning deep generative models of graphs. arXiv preprint urXiv: 180.00334, 2018
Liao, R., Li, Y., Song, Y., Wang, S., Hamilton, W., Du- venaud, D. K., Urtasun, R., and Zemel, R. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
Jacobsen, M. Laplace and the origin of the ornstein- uhlenbeck process. Bernoulli, 2(3):271-286 1996.
Jensen, J. H. A graph-based genetic algorithm and gener- ative model/monte carlo tree search for the exploration of chemical space. Chemical science, 10(12)335773352, 2019.
Liu, C., Zhang. J., Wang, S., Fan, W., and Li, Q. Score-based generative diffusion models for social recommendations. arXiv preprint arXiv:2412. 2024.
Jin, W., Barzilay, R., and Jaakkola, T. Junetion tree vari- ational autoencoder for molecular graph generation. In International conference machine learning, pp. 2323- 2332. PMLR, 2018
Martínez, V., Berzal, F,, and Cubero, J.-C. A survey of link prediction in complex networks. ACM computing surveys (CSUR), 49(4):1333, 2016.
Jo, J., Lee, S., and Hwang, S. Score-based generative modeling of graphs via the system of stochastic differen- tial equations. In International Conference Machine Learning, pp. 10362-10383. PMLR, 2022.
Newman, M. Networks. Oxford university press, 2018.
Newman, M. E. Modularity and community structure in net- works. Proceedings of the national academy of sciences, 103(23):8577-88882 2006.
Karrer, B. and Newman, M. F. Stochastic blockmodels and community structure in networks. Physical review E, 83 (1):016107, 2011.
Newman, M. E. and Girvan, M. Finding and evaluating community structure in networks. Physical review E, 69 (2):0261 13, 2004.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint wrXiv:142..6980 2014.
Newman, M. E.. Watts, D. J., and Strogatz, S. H. Random graph models of social networks. Proceedings of the national academy of sciences, 991supp..1:22566-25777 2002.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks, 2017.
10

---

Convergent Analysis of Graph Diffusion Generation
Nichol, A. Q. and Dhariwal, P. Improved denoising diffu- sion probabilistic models. In International conference machine learning, pp. 8162-8171. PMLR, 2021.
Suh, N. and Cheng, G. A survey on statistical theory of deep learning: Approximation, training dynamics, and generative models. Annual Review of Statistics and Its Application, 12, 2024.
Niu, C., Song, Y. Song, J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via score-based generative modeling. In International Conference on Ar- rificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020.
Trench, W. F. Introduction to real analysis. 2013.
Vignac, C., Krawezuk. I., Siraudin, A., Wang. B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.14334 2022.
Pósfai, M. and Barabási, A.-L. Network science. Citeseer, 2016.
Vincent, P. A connection between score matching and de- noising autoencoders. Neural computation, 23(7): 1661- 1674, 2011.
Revuz, D. and Yor, M. Continuous martingales and Brow- nian motion, volume 293. Springer Science & Business Media, 2013.
Wang, P., Zhang, H., Zhang, Z., Chen, S., Ma, Y., and Qu, Q. Diffusion models learn low-dimensional distributions via subspace clustering. arXiv preprint arXiv:2409.00 022492 2024.
Russell, and Norvig, P. Artificial intelligence: a modern approach. Pearson, 2016.
Sanchez-Lengeling, B., Outeiral, C., Guimaraes, G. L., and Aspuru-Guzik, A. Optimizing distributions over molecu- lar space. an reinforee generative adversarial network for inverse-design chemistry (organic). 2017.
Xie, Y., Shi, C., Zhou, H., Yang, Y., Zhang, W., Yu, Y., and Li, L. Mars: Markov molecular sampling for multi-objective drug discovery. arXiv preprint arXiv:2103. 10432, 2021.
Shah, K., Chen, S., and Klivans, A. Learning mixtures of gaussians using the ddpm objective. Advances in Neural Information Processing Systems, 36:19636-19643 2023.
Yang, L.,, Zhang, Z., Song, Y., Hong, S., Xu, R., Zhao, Y., Zhang, W., Cui, B., and Yang, M.-H. Diffusion models: comprehensive survey of methods and applications, 2024. URL httph:tt///aaate //ap:iva//ivv/v//a orgg /aag/////////////////g//////a 2200222222222 00796.
Simonovsky, M. and Komodakis, N. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning- ICANN 2018: 27th International Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 1 27, pp. 412-422. Springer, 2018.
Yegin, M. N. and Amasyah, M. F. Generative diffusion models: A survey of current theoretical developments. Neurocomputing, 608: 128373, 2024.
Sohl-Dickstein, Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International conference machine learning, pp. 2256-2263 PMLR, 2015.
You, J., Liu, B., Ying, Z., Pande, V., and Leskovec, J. Graph convolutional policy network for goal-directed molecu- lar graph generation. Advances in neural information processing systems, 31, 2018.
Song, J., Meng, C., and Ermon, S. Denoising diffusion im- plicit models. arXiv preprint arXiv:2010.025502 2020a.
Zang, C. and Wang, F. Moflow: an invertible flow model for generating molecular graphs. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 617-626, 2020.
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Zhang, M. and Chen, Link prediction based on graph neu- ral networks. Advances in neural information processing systems, 31, 2018.
Song. Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., mon, S., and Poole, B. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456. 2020b.
Zhang, Z., Chen, Z., and Gu, Q. Convergence of score- based discrete diffusion models: A discrete-time analysis. arXiv preprint arXiv:2410.00
Spielman, D. Spectral graph theory. Combinatorial scien- tific computing, 18:18, 2012.
2024.
Zhu, Y., Du, Y., Wang, Y., Xu, Y., Zhang, J., Liu, Q. and Wu, S. survey on deep graph generation: Methods and applications. In Learning on Graphs Conference, pp. 47-1. PMLR, 2022.
Su, J. and Marbach, P. Structure of core-periphery commu- nities. In International Conference on Complex Networks and Their Applications, pp. 151-161. Spprinrr,pr 2022.

---

Convergent Analysis of Graph Diffusion Generation
Zhu, Z., Locatello, F., and Cevher, V. Sample complexity bounds for mattemmtching: Causal discovery and gener- ative modeling, 2023, URL https: / /arxiv.rrgg////// 18123.
12

---

Convergent Analysis of Graph Diffusion Generation
A. Problem Formulation Discussion
In this appendix, we provide further discussion on our problem formulation, including the choice of hyper-parameter and the derivation of the training objectives.
A.1. Choice Hlyper-parameee
For our analysis, we have chosen the following set of hyper-
[x( t) = -1/2gx (9t, X:: (A 1) - -1/2gA (9r, 1)2 Ar: (9, 1) - (9,, 1.
(A.1)
As mentioned the main paper, our analysis can generalize further to any linear drift function fx (Gr, () and /a (G:, () and other constant variance functions long as the underlying process remain OU process and would converge the prior distribution (i.e., the convergent distribution)
Without loss of generality, we can express the set of linear function and constant variance function
fx t) = Egx (9,, x)² fA t) EgA A), (x( (9, Ki
(A.2)
where & E (-1,0) and is some positive constant.
The selection of a constant variance function does not result in any loss of generality. This is because altering the variance function can be viewed as a re-scaling of time, provided that the drift function does not explicitly depend on time. In other words, changing the variance function only affects the rate at which the diffusion process evolves, but this transformation effectively equivalent adjusting the temporal scale of the process. Consequently, the analysis remains valid even if the variance function is modified, as long as the time re-scaling is appropriately accounted for.
By changing the coefficient in the linear drift function, this amounts to different conditional density for the forward process and score:
X, ~ N(e (1 - e 26L -28h 1 INNF),
A.|Aa N(e Ao, - E -xxN).
(A.3)
Since all the theoretical tools we use for the analysis are grounded in the OU process and independent of the scale of the pyper-parameters, all the results and analysis can be immediately applied with the general formulation above. However, in the paper, we strike for cleaner results for better interpretability and focus on the set of sapeer-prramterss specified the paper.
A.2. Training Objective Derivation
In this appendix, we present a derivation for the Equations used in the problem formulation for completeness. similar derivation can be found in (Jo et al., 2022).
The partial score functions can be estimated by training the time-dependent score-based models se(.) and s.).,, that
sg t) Vx log P(G,), (G,, VA log IP()))
However, the objectives introduced in SGM for estimating the score function not directly applicable here, since the partial score functions are defined as the gradient of each component, rather than the gradient of the data as in the conventional score function. This interdependence between the two diffusion processes tied by the partial scores adds another layer of difficulty.
To address this issue, an new objective for estimating the partial scores is needed. Intuitively, the score- booee models should be trained to minimize the distance to the corresponding ground-truth partial scores. The following new objectives
13

---

Convergent Analysis of Graph Diffusion Generation
generalize score matching (Song al., 2020b) the estimation of partial scores for the given graph dataset, as follows:
min B
ggg G. Go
(G.)
Vx log (P;))
(A.4)
0
min E,
Ego Lg 9o (6,1
VA log ((:))
(A.5)
where / is uniformly sampled from [0, T). The expectations taken samples Go Pdata and 9, PP where P(G:/9)) denotes the transition distribution from 0 to induced by the forward diffusion process.
Unfortunately, the equations above are still not directly trainable since the bround-truth partial scores are not analytically accessible in general. This is why we need to underlying process to be an OU process, as we can leverage the known conditional density of OU process for training.
min E,
Ego 1 10 (0., - Vx log PGr
(A.6)
min B, Egg E. (9 V log P(G
(A.7)
Since the drift coefficient of the forward diffusion process linear, the transition distribution P(Gr(9o) can be separated in terms of X₁ and A; as follows:
P(G. PXX
(A.8)
Notably, easily sample from the transition distributions of each component, P(X, and P(Ac(Ao), as they Gaussian distributions with mean and variance determined by the coefficients of the forward diffusion process. This leads to the following training objective:
min E, Eg Eg.1 l1s0 Vx I(, Xx)
(A.9)
min E, Eg, Eg.1o (s t) V log (o
(A.10)
The expectations in the equation above can be efficiently computed using the Monte Carlo estimate with the samples (1, Go, G.). Note that estimating partial scores is not equivalent to estimating Vx log P(X,) or V log P(A+). the main objective of previous score-based generative models, since estimating the partial scores requires capturing the dependency between X, and A, determined by the joint probability through time.
A.2.1. DERIVATION OF TRAINING OBJECTIVE A.4
The original score matching objective can be written as follows:
Eg, [lIs !) Vx log 12 Eg, [||0 (Gr, 0) - 2Eg, (Go (), Vx log PPG.)) + Ci.
where Cj is constant that does not depend on W. On the other hand, we have
Eg, Go [IIso(G,,)) t) Vx P( Eg, Eg, [[ []] 2Eg, Eg, loo ((50 t). Vx log P(G,())))) C2.
For the second term, from the derivation (Appendix A.I from (Jo al., 2022)), know that it has the following equivalency:
Eg, ((s( t), Vx ()g))()))) Eg, 19. ((so t), Vx log (P))]
14

---

Convergent Analysis of Graph Diffusion Generation
Since the constant C₁ and C2 does affect the optimization results, can conclude that the following two objectives equivalent with respect to f
Eg, Egg Soo [G., Vx log P(C) Egg [1ss((e,,)) 1) Vx log [
Similarly, computing the gradient with respect to A, we can show that the following two objectives are also equivalent with respect to Φ:
g3 g. (91s)(9,, - V log (()) RG (9,) () V log ((G:) [
Now, it remains to show that Vx log (o) is equivalent to Vx log P X Xo). Using the chain rule, we get that
i log F AA))
aA
TF VA (o) 0 ((X,);
0(x)) = 0.
With this result, have that,
Go) Vx log Xo) Vx VxlogP(X
Therefore, we can conclude that
Vx log P(S = Vx log ((X,
With a similar computation for As, we can also show that V log Po) is equal to VA log ((A,(A)))
A.2.2. TRACTABLE TRAINING ORJECTIVE
In the previous section, have proved the equivalence of the training objective used in analysis and the common score-based generative model. It remains to show how compute this training objective with tractable objects. To simplify the notation, we define the following for the rest of appendix, for any 0 s S
of = 1 e
0t,s e 11/2(8-1)
0, Cuu.
Then, using the ideas in (Vincent, 201 I), we get the following,
E| ( 1) - 2
F (())) (Ro (), Vx log P(G.))
< 2RV (0
[[l 2E (p(C.
(o,,t.
[l/ 2EP(C.) (P(G. (6))
V x log Po) so so,
B|(s<((.,,00+++ 2EP(C.) Ep(G, (o) (G)
V log P(X, ) so (0, t))
X
[X - 2EP(G. E (P(G.1)))
so (G,, ()
of
X, axXo
d
E
so(9,,t)
E| V
of
of
X, 0;X0
(0(9,, t)
+Css
o
15

---

Convergent Analysis of Graph Diffusion Generation
where C3 is some constant independent of 0. Therefore, we can the last equation the training objective. Through similar computation, get that,
(9 V (())) E (o) A A0
+ C4
of
A.2.3. DISCUSSION OF ASSUMPTION 3.2
In this section, we present an argument for why Assumption 3.2 is reasonable and hold in practice. We can observe that
X
a
1
E
of
0f
Therefore, it is natural expect the error scale
E Bla (9,, Vx log P(G.)1 2
for some 8x. Furthermore, notice that of min(ta, 1}, then we have,
T
80 (9, - Vx log P(G)) - ['
8x tAi
di S 8x log(1/4).
Through a symmetric argument, we can get a similar result for the structure process.
B. Useful Lemmas
In this appendix, we present a useful results that are going to be used in the proof of the main theorem. The proof of some of the results also be found in other diffusion convergent analysis (Chen et al., 2023a; 2022a; Zhu et al., 2023; Lee et al., 2023b; Gnaneshwar et al., 2022). We present the proof for these results for completeness.
To simplify the notation a bit, in the following, we use Pt and P(X,) interchangeably to represent the density of X at time t. We use Pup and (XX, X interchangeably to represent the condition density of X at time I given l'. In addition, we adopt the Frobenius norm as the matrix norm.
Lemma B.1. Given two Itô processes coupled by the same initial condition and random noise as follows,
dX² fi(2,, gt)ddW, f Xo = 7
xx f2(2,, + X = Y
where fes g are continuous function. Furthermore, suppose the two SDEs satisfy the following conditions.
1. the two SDEs have unique solutions,
2. X1, admit densities Pt, Qu that are twice continuously differentiable with respect to inputs t > 0.
Then, we denote the relative Fisher information between I. and Qe by
Pr 1
J(P.IQu)= - / (2)(2))
Vlog
dx.
Q
Then for any 1. >> 0, the time derivative of (L(Pp is given by.
d
P. = -ot))))))))((()(()1(l1))) + E (11(8.0) So(, 1), V V
dt
Q.
16

---

Convergent Analysis of Graph Diffusion Generation
Proof. By definition of KL divergence, we have that
Pa(22)
(L(P)1))))) = (1)
Qc(xt) d.t.
Taking the time derivative of the expression above, we obtain,
①
0 [ Po())) log
((())
kI.(P.IQ:))
dx
dt
0t
Q2(2)))
- OI, (x))
(2() Q+((t)
(x()) (Qx(x)
log
d.''
dx
(2)
Then, can use Fokker-Plank equation to obtain the time derivatives of P. and Qt which are given by
(x) V -x(())));()))) 2(1) (x)(
0X
(Q(())
1xx( + a()² [Q((x))
0X'
2
Substituting the time derivatives of IP, and Q, into the corresponding terms of the time derivative of 2r (LP..1))):) we get that,
OP, (2)
P((2)) (2')
de' = / V. ((xx g(t)²
P((A)
log
2 VP((X)) log
dx
Ōt
Qx(
(VIOE
Vlog
Pe(a))
g(t)
(P((A)
dX
Qx(())
2
-BL(()) (f(x,,)) V log
Qx(x)) )) g(t)²
P((2)
P((
v log
VPI(X))
dX.
Qx
/ P((2) (Qi()) Q+(x) ot =x= / P((2)) V. [ f2(xx,))0((1) + g())
VQ((X) dx,
Q1(2)
2
/ P((t)
g(t)
fa(X
t)((()
vQ.(2))
Qx(t))
2
/ 0.(12) (
Pr
f2(x
g(t)
(
P(()))
VQ.(d)) dx.
Q
2
(x)
Combining the results above, we obtain,
① KT (KT(PP./(0
a
/ (2(()) log
P²(2))
Cx(2)) dx
Øt
at
/ UP, (2)
(P((2))
dx dx- /
(x)
(Q,(2)
log
Qi(x)) Ot dx,
St
Qi(2t))
-BP((X) t) t), V log
P((d))
g(t)2
V Vog
P((x)) Qr(x))
VP((X) dx dx-
Q2)(2')
/ /0/(0))
( -2(2,,) ))+ g(t)²
Px)
(Qr(2)) dX,
Qx(x))
g(t)p
(
P((xt
P((A)
) dxl +...
(2(2))
(Q((2)
V
VV((())
Qx(x)
f (1(1)) ( ()) Vlog P2()))
Pi(X)
Qi(xt))
Q((x) f2(x1,) dx,
(2)
17

---

Convergent Analysis of Graph Diffusion Generation
Notice that
vela)) - (Vlog log Ci(K)
Pi(2)
Pa(2)) Cx(
VP.(2)) dx
Vlog (log(((1)) - Pt
V log Qx(X)* V VlogP((2))
(((
Q1(x)
/PICO ( (vlog
Pa(d)
VlogQu(A) PP: (Vlog (P(())
Vlog P,( dX,
Qx(2))
(x)
--((P(())1Q((11)))
In addition, we have
|PACX) (Fi(z,)), V log Px(X)
(x
(x(2)) - (x(
(2( 1) dx
Qr (X)
= - ( (1(xX 1), log Px(x)
(x) ) (2)(2))
P((X)
log
(x)x) 12(x dx
= (vlog F()
(x) -
E [1122,00 12 1), log Q((2)
P((A)) }
Combining all the results above, we get that,
0 (T(( = -003P))))0))))))))))))00000))))) + (1((8,0)5(xx.0) Vlog Qx(2)) P,(X') }
at
This completes the proof.
The next two lemmas capture the properties of Gaussian perturbation in the forward process.
Lemma B.2. Let P be a probability measure on N Consider the Gaussian perturbation of that admits density
(X), where X RNN.M Specifically, we define
PP P x I exp
X - Y dIP(Y)
JRNXM
202
where || || the Frobenius Let u.o (Y be the conditional probability measure given X, defined
|X-+Y112 Y dIP(Y)
dPp (Y x exp
20
P admits a density in C2 )RMM have
Vx log P
(X)
Ep
(Y(x)
V PYY)
18

---

Convergent Analysis of Graph Diffusion Generation
Proof.
JANXM P(Y)Vx exp
| 1
dY
20²
V log P. (x)
JENXM PYY) exp
|
20
JANXM P(Y) Vx exp
x 1x-1X|1
dY
20
1. JRNNM P(Y) exp
X- 2
dY
JANKM P(Y) Vx cxp
X- ?
dY
20
01,8 JENNN P(Y) exp
|X- 20
dY
1 ( Vy log P(Y).
Lemma B.3. For < k S M 1 and for time (txy tx+1h, consider the continuous and the discrete approximated
reverse SDE starting from 7
dx; [1/2X, Vx PG))) +dW,
X %
d², = 1/2XX + so the dWe.
X, = %
for time E (be, 1R+1]. Let Petee the density of Xt given Xx, and Pete. the density of X. given Rae. Then we have that
1. For any 7, the two processes above satisfy: 1) there is unique solution; and 2) the density functions two continuously differentiable for O.
2. For a.e. (with respect to he Lebesgue measure), we have that
lim KL (ml = 0
Proof. Let [g. and Qpy, denote the path measure of (X.) and (X.), sose. respectively. For any Y RNM, we have
KL(PHg (-IY)) (LIY)) s KL (11)))
Thus, it suffices to show
lim KL(P +-
iy an |Y) (111)) (-l)) 0,
for a.c. E NxM easy to check the Novikov condition satisfied under Assumption 3.1 and 3.2. Therefore, we can apply Girsanov change of measure (Revuz & Yor, 2013) on (r,,,)(-/Y) and Q1 YY. Then, for the exponential integrator scheme, have that
[/" Vx log P(9) - (0 =
KL(P eg.. (1)))
Again, by Assumption 3.2, we have that || Vx log (P)) (G 12 is bounded and therefore, we can apply the dominated convergence theorem (Trench, 2013) and move the limit inside the expectation, i.e.,
L' Vx log P(g) ,o( 1 & = 7
lim (L +
lim b-
E
/'
E
lim b
Vx log P(g) so So(āe; 11) =7
19

---

Convergent Analysis of Graph Diffusion Generation
This complete the proof for the exponential integrator scheme. Similarly for the Euler-Maruyama scheme, have that
=E | |Vx log P(G.) so (0 +1/2( - - =>/
Again, by Assumption 3.1 and 3.2, we can conclude that || (og so( + 1/2((G, -) |1 is bounded. Then, again, by the dominant convergence theorem, we get that
lim KL(P (1 +++
Vx log))(G)) so(9,, + 1 (
7)11 =>] Vx log - so (G: 4) 1/2(0, >,,1, =7)
E
lim (-tl
This completes the proof.
have the following results for the decomposition of the convergence bound for the Murer-Maruyama scheme and the exponential integrator scheme. We emphasize that the result below is independent of the generation paradigms. Lemma B.4. For the exponential integrator scheme, we have that,
M
A |1 t) Vx log (PG
KL(P(X) (XT)) S (L(P(XT)) IIx) + Σ
(B.1)
M
V log (G))) - Vx log (og,(,,,))l3tt,
c. (I.(P())IP(AT)) & KL((P(AT) IIA) + Σ (s VA log Pl
(B.2)
M
V log P(G.) V log
For the Euler-Maruyama scheme, we have that,
M
1
KI(P(())/P((x)) (T IIx +
Σ
|1s0 - Vx log (1
(B.3)
1=1
(E) Vx log (.
Vx log (P E|X. x1, dl,
M
pt
KL(P(A)IP(AT)) & KL(P(AT)
IIA) Σ
([ V log log,
(B.4)
14-1
VE log P(G)) VA P(G.)) + - A1, 1t2)) dt.
Proof. We start with deriving the expression for the feature progression. Consider an arbitrary time interval f, < S f let P denote the distribution of X, given X,, Let Prpe. denote the distribution of the discrete approximation X, given X
Then for any 7 E IR NXF, by the chain rule of KL-divergence, we can get the following progression relation,
(L IIPe, S Ep, KL K. le (11)))) (1)))))))) + KL(P, (Pp))
(B.5)
20

---

Convergent Analysis of Graph Diffusion Generation
Equivalently, we have that
e 1g (IPPP; S KL(Pe KL(P& & I (4,)
(1))) 4/ in (-b)).
We can observe that we do a telescope sum over 0 Σ i S M, the left-hand side can cancel most of the term and left of (L (P)r and ( (Po).
Therefore, we can focus on the right hand side and deriving an expression for
Ep (L(F,; 1 (-)))) 14 (l7)).
By Lemma B.3 we have that the two process satisfy the conditions: 1) unique solution and 2) twice continuously differentiable. Then, by Lemma B.1, we have the following time evolution relation for any 7 and >
d
Pey (X,lr)
pp (L 14 le dt
((x)) = (,
Ep Miig (X,rl>)
V log P Mie (X,+>)
Pen (X17)
+ E2 of (X,rl7)
V llog so( + 2 2xxx -x+). log
Perpo (X/r)
Using the fact that (a. b) = ||/l/1 + 11b1 we get that
poqe (X (y))
E (xngg(((1)))
V log
2
Pule (X ly)
+ 2
Beeng(X
V V Pr (X,)) - so so 15) + + 2xx -x:xx
log Pule (X I7)
+
Ep B.riigg (X,1x)
2
PMrpe (X /7)
1
+ VlogP::(Xx) so( (1) + 1 - -xx-
Ep 1E
This means that we have,
KL (Pe s
1
v Po - 60l),, (1) + "x(xx -xx:) |
2
||Vlog ( 4)1l + _
2 (x:: x::) 11)
1
< Ee (211)
1
T [ -xx) |
M (x,1)) (o so
+0)1 201l
Then, by Lemma B.3, for a.e. 7, we have
KL (L(PPrc(4)))PPPex 0. e-
lim
This means that Pete (-lr) and (-lrr) become increasingly similar the approximation interval become small. Then, by the derivation above and taking the integral from E to l/41 we get that,
KT,(PP K., (11-))
44_ (,,
1 611
Eg
Ee (x.1)) V log (X.) - sa(Se, 42)12+
1 2 Eerrn
1
2 [x, - xx;) dl.
2
21

---

Convergent Analysis of Graph Diffusion Generation
Because of the fact that (X() ) is absolutely continuous with respect the Lebesgue measure, integrating both sides above with respect to Pt we get,
B (L Me (1))) le (ly)) =
1 [ xx,,,,
x dt
(x,) - Substitute the above result into the progression relation given in Eq. B.5, we get the following progression relation,
Es V
(0 -
2 J (x) | (oogPr(Xx)) so(0e, 6011 +
1
1 [Xx - (xxx-xx))
B (x,1)
dt
2
KLL(P (P))t
h+
1
xx:) /
2
(x,) (X)) - s0(0n +a]l + 2 y (x)
1 2
-xx:
dt
2 e
Then, summing above iterative relation over ssis M and replacing Pvr Pr-c, obtain,
_ -xxxxaa) /| di
PL(Po|[PT) (L(PT
Ex,(x
| Voog P(G:) so (11,1114111 + Eg xx))
M
= =KL(PT|l>)
E (x /| Vx P(.)) Vx log P(G..)) + Vx log P(G - se (0
i=0
1
E2,(x)
2 (X,
X 1)
dt
2
M
< (L((P//77)
Ep,(x) Vx Vx (ogg)(()..) + Vx log so(
1=0 t1
2 (xx
1 [x, Xx:)
dt
1 M 1++1
(x,(x) Vx log P(G)) Vx log .I. + (x) V log P(G so (0 1
2
1=0
14
2
[x, X
E
(x)
dl
2
This completes the derivation for the Euler Fuler-Marumaya scheme for the feature matrix. The derivation for the structure matrix is symmetric.
Furthermore, to obtain the derivation for the exponential integrator scheme, we only need to replace the time derivative with,
d
KT. (T. sj.. PP.r.. I (-lr) P..,, (X Vog (X(X) so 1:)l
1
dt
Then, go through the derivation above in similar manner obtain the derivation for feature and structure with the exponential integrator scheme.
Lemma B.5. Under Assumption for T >> 1, have
KL(P, Ix) S (NF+ Hx
(I) S (N2 + -T.
22

---

Convergent Analysis of Graph Diffusion Generation
Proof. First, we that that (x) log is a convex function for 0. Then, for any / 0, we can Jensen's inequality bound the entropy of P,:
I P: dx=
/ 1/ Pajo (X)(( log (f (/PO((II))(()) dx,
- /
dPP))) dx, / (/ Pro(X dP(Y).
Since X, X, Y -NaXo of we have
f Pupp(X/ (og
NF
log (TT NF
2
Substitute this back into the derivation before, we have
/ PXXX))
NF
NF 2
log( (2TO7)
(B.6)
2
Then, by the definition of KL divergence, we have that,
KT((P.|ITT) = / P.(() log (x( dX
IIx
= f Px( [og (X) log lxx] dX
Substitute int the definition of standard Gaussian for Ixx, get
X 12
NF
=
dx + Ep,
+
log (T))
2
2
Subsitute in the result of Eq. B.6 and rearrange the terms, we get
NF 2
< log
+ 2 (Hx - NF).
Since Langevin dynamics with strongly log-concave stationary distribution converge exponentially, we can obtain
-T NF
NF 2
log o, + 1 (Hxx NF),
KL(P, II Se
Picking log 2, log
S 1. we obtain
(NF Hx).
The proof for the structure is symmetric by replace the dimension of NF with N
Lemma B.6. Suppose the step size for the Fuler-Maruyama scheme satisfies A S 1, then for siS M, we have
E X, X,, 12 NF(4: + Hx(1: - 1)2 4-1 l < 4,
A
1 12 22 - +)+ AA. - 1)2
1--1 S 1 $ t,
23

---

Convergent Analysis of Graph Diffusion Generation
Proof. We start with the feature matrix. By the definition of the forward process, get that
1
1
X X
X,
dw.
2
1
+ 1:
S
Xs
dW,
2
By Cauchy-Schwartz inequality, we can get
2 (ti - t)
E x ds + NF - t)
In addition, we have the explicit expression for the conditional density X, given by,
N(e 1lc-1/2xp4 Xo, (1 (1-6) (1-e~))I) I)..
Then, based on the expression and the Assumption 3.1 that the second moment is bounded, we can get that
E x. < Hx + NE
Substitute this back into the derivation before, get
E| X & (NF+ Hx) 1)2
Similarly, for the structure matrix, we have that,
f
d:
1
E A,
Ar,
1 = E
ds
dw
2
2
1,
t
2
E
A,ds
+
W
2
2
By Cauchy-Sch inequality, we can get
$ (4 (44-) 1) S.²
E||A.11 ds N 1)
In addition, we have the explicit expression for the conditional density As given by.
N(e-1/2>A0 1/25 (1-e
Then, based on the expression and the Assumption 3.1 that the second moment is bounded, we can get that
1 S HA 2
Substitute this back into the derivation before, we get
E A, A,, S t) + (N2 Hx)(tt+ -t)2.
Lemma B.7 ((Chewi et al., al. 2024)). Let IP be continuously differentiable probability density. Suppose V log is L-Lipschitz,
we have
E V log P())( NFI,
E A log 2( 2
24

---

Convergent Analysis of Graph Diffusion Generation
Proof. Using integration by parts for feature X, have:
/ P Vxg
E| V log P())
(VP(X), Vx log F(9)) dx,
/ P(
S NFL
The derivation for structure similar.
Lemma B.8. For any St T. the forward process satisfies
E x log (G,) Vx log
E V log P(G.) log
log.oogPPaaaa P(a, [/xxxxx))))) (1 -1- a (1-
E A log (C.) V log P 9.) (., x
V log P(G.)
VA log (a g.) [IV log (1 ai,!)
Proof. We start with proving for the feature By our choice of condition density:
the forward process is OU process with
X, ~ N(ar, X., (1- -2
A, A. A1, (1 - (2,e) I)
from Lemma B.2, we can rewrite Vx log (CG)) as
Vx P(Gs) at, Bp... Vx P.)),
where Pr|s is the conditional density of G. given G.. Thus the discretization error can be bounded by
|||xx log G.. Vx log P() = Ep, ||0 Vx log P(C)) Vx log P.
< E || Vx log ((G.) Vx log P(a G.)
< 2(1 a., 2 V (o:)P(()))
2E V log (.. Vx log Pa 7 1.
Therefore, splitting the error into the space-discretization and the time-discretization error, have
E Vx P(G))
Vx log 1og
< 2E V log (G.) Vx log P(o,
2E (1 - Vx log P(G
V log (P.)))
V x log (P.)) -oog
< V log [ (1- (1- 2 + V log Vx log
The proof for the structure matrix A is symmetric and therefore obmitted here.
Lemma B.9. For l2
S1 < 4., iL 1 and A., S we have:
E V log P(G.) Vx log ((g NFT2 +NNF - - 1)2 El V log P(G.) V 1P T2 - +N -1).
25

---

Convergent Analysis of Graph Diffusion Generation
Proof. We start with proving for the feature X.
By Lemmas B.8, we have that
V log P( Vx log P():))
x log P(.)
Vx log P( 9.) +E [[[Vx log P())) - (1-a7,?)²
Next, we tackle each term of the equation above. By Assumption 3.1, we have that,
E| V log (G.) Vx log P( )1
= V log P(G,) Vx log F a 1 Gell
< INLLBIJAA A,X; Ot | ?
-2
(tx (e -1) 1)
NFL
Using the premise that 4 -s A 1:
E Vx (())
V log & (t
Then, by Lemma B.7, we have that
E Vx log ((G:) -1 - S NFI(42-1 -1)
Thus, we conclude that:
V ((9)) - Vx (().,)) & NFL -) + NFF(ttt t)2
Similarly for the structure, we have that By Lemmas B.8, we have that
V log PG..) - VA log (C II
E | PGG)) - VA log + IIVA P(G.))] (1 - a,,
Next, we tackle each term of the equation above. By Assumption 3.1, we have that,
E VA log (G)) - V log P( )1( E A log (GG) V log P( GIll < N A,X, a,, A,X, 1
12 (c - 1)
Using the premise that - AB S 1:
E
V A Pggi) V log S L2 - +)²
Then, by Lemma B.7, we have that
E V -1 N2 N t)
Thus, we conclude that:
V P(G.) Vx log P(G N -) +2)+ +)2
26

---

Convergent Analysis of Graph Diffusion Generation
Lemma B.10. For the graph paradigm given by Eq. 3.7, under the premise |||]| < for 42-1 S S 4. if 1 and
At 1, we have:
E
V log (G)))
Vx log (( NF 1)o + NNI((t - -))?
Proof. By Lemmas B.8, we have that
E
Vx log P(G)) Vx P(
V log (G)) Vx log ( )1l + V log P1 o2,h)
Next, we tackle each term of the equation above. By Assumption 3.1, we have that,
E V log (G)) Vx log (( )1
E V log P(G,) Vx log P( Gell
NNLL X: -0,74
-1 X, ||A
(C 1
Using the premise that - As S 1:
E Vx log P(G.) - Vx & - t)o
Then, by Lemma B.7, we have that
E| log Pog - NFL t)2
Thus, conclude that:
V P(g.) - Vx ll & NFI t)o + NFL(tt - t)²
We complete the proof.
Lemma B.11. For graph generation paradigm given by Eq. 3.8, under the premise that |X| for tar S15 if
A and D., S 1, we have:
E V log P(G.)
V log P(G.)) 2 N2 s
+)o L -))²
Proof. By Lemmas B.8, we have that
E A log P(G)) V (Gr,) )Il
V A log P(.) VA log (Il + + log P(G))) a2
Next, we tackle each term of the equation above. By Assumption 3.1, we have that,
E V (G,) - V log P(. 1 V log P(,)) Vx log (og GOll N2 X || A, 0 A,
( 1)03
Using the premise that f4 - Ab 1::
E A log PPG.) V log P(G )12 SNN2 -)0x
27

---

Convergent Analysis of Graph Diffusion Generation
Then, by Lemma B.7, have that
E| V 1VV N - 112
Thus, conclude that:
E V log P():) - V P( ( 1)0 + L -)
We complete the proof.
Lemma B.12. For tk-1 Sts the L 21 and 4 S 1, we have:
E Vx log ((G))
Vx log & NFT. -1)²
Proof. By Lemmas B.8, we have that
E X log P(G.) Vx log ((
E V log ((G)) Vx log (P,,, )1 + E/| log (( o7,,)
Next, we tackle each term of the equation above. By Assumption 3.1, we have that,
Vx log P(G)) Vx log P(G )112
E V log P(G() Vx log PP P( Ge)l
S NFL X, 01,42 x A. ai, A,
(F - 1)²
Using the premise that ty - As S 1:
E
V log P(g) - Vx Pog S NFL -t)
Then, by Lemma B.7, we have that
B log (( - 22 NF((k)
Thus, we conclude that:
$ ddT2(1 - 1) + dL(lk - 1222$10
S dl 1).
We complete the proof.
C. Proof of Main Results
In this section, we present the proof of the main results. The overall structure of the proof for each paradigm is similar. We first use Lemma B.4 to obtain the decomposition of the convergence bound and then apply the intermediate results we prove in the last section to get the final expression.
C.1. Proof of Theorem 4.1
In this section, we present the proof for Theorem 4.1.
28

---

Convergent Analysis of Graph Diffusion Generation
Proof of Theorem 4.1. Let Pu be the data distribution and Pr is the learned distribution through the sampling scheme. We start with considering the exponential integrator scheme. By Lemma B.4, decompose the KI. divergence of Po and P follows.
M Σ
(L(((X)))I((XT) S (L(P(X+)
+
(1sa 4:) Vx log P(gr,,
(C.1)
12-1
Σ
V log P(G.) Vx log P(G))
Then, we tackle each term in the equation above. By Lemma B.5, we can immediately bound the first term as follows,
(X) [x) S (NF+ + hx)e
Next, we tackle the second term, By Assumption 3.2, we have that,
|se (9t, Vx log P(G:.))dt
M
Ac11s0(91, - Vx P(r,)
1=1
TTxx
Therefore, it remains to tackle the last term. By Lemma B.10, we immediately get that
M
V log ((g.)) - Vx log (l
M
NFL 2 ( ttdt + NFL 1" (t; t)²
OA
14-1
M
NFL + NFLA
Combining all the results above, we get that,
KT,(P(X.)) (T((P(X [Ix) + Σ l E/
(1so(9(.:4) 4)
Vx log ((
1=1 Je--
M
Ex Pog
Vx log P(G:)l
M
S (NF+ T + + NFL +NLLA
This completes the derivation for the exponential integrator scheme.
Again, from Lemma B.4, we have that the decomposition of the convergence bound of the Euler- scheme is given by.
(X) & (T Ix) + Σ de i=1 1:-1
(100(9r,44)) - Vx log (ld
(C.2)
M
( x log Pr( Vx log 21 E| 13) dl,
29

---

Convergent Analysis of Graph Diffusion Generation
From comparing the decomposition of Maramayaa and the exponential integrator scheme, we can easily see that the difference between the Fuler-Marumaya scheme and the exponential integrator scheme is the extra term
E B
For this, we can use Lemma B.6 and immediately get that
E X - X, 11 & NF(t t) + Hx - t)2 4-1
Substituting this result into the extra term, we have that,
M
B| - dt.
M NF(t; -t) + Hx(t; - -t
M
NF(tt - -t)² + Hx(tt, -)3
M NFA + Hx42
Therefore, combining this result and the result of the exponential integrator scheme, we have,
KI.(((X)) $ (L(
[x) +
(ta Vx log P(
M
E V log ((G))
Vx log Pd
M NFA + Hx42
S (NF+ Hx)e T + +T + Σ NFI + +NFLA]
This completes the proof.
C.2. Proof of Theorem 4.2
In this section, we present the proof for Theorem 4.2.
Proof of Theorem 4.2. Let Po be the data distribution and P is the learned distribution through the sampling scheme. We start with considering the exponential integrator scheme. By Lemma B.4, we can decompose the KL divergence of Po and Py as follows,
M E/
KL(P(AN)IP(AT) & KL(P(AT)
IIA [ + i=1 1:-
11s0 (4) VA log P(
(C.3)
M
V log P(G..) VA log Pd.
Then, we tackle each term in the equation above.
By Lemma B.5, we can immediately bound the first term as follows.
(L(P (N2 + HA)e
30

---

Convergent Analysis of Graph Diffusion Generation
Next, tackle the second term. By Assumption 3.2, we have that,
(9s.() VA log
M
A (91
VA P(G.)
-
T
Therefore, remains tackle the last term. By Lemma B.1 we immediately get that
VA log P())) VA log (()t.)) dl
M
N 22 t)o + N2 - 2)
-4-1
M
M
S
N
4 + N Σ A
A
2=1
Combining all the results above, we get that,
E/ (1s VA log ((
KL(P(A))) (L(P(AT)
IIA)
M
E V ((G.) V log (gg)
M
M + + Σ A
$ (N² + Hx)e - + + N2
A
t=1
i=1
+ (N² + Hx)e + T + N
Lox 2
Σ A
Σ A
1=1
This complete the derivation for the exponential integrator scheme.
Again, from Lemma B.4, we have that the decomposition of convergence bound of the Fuler-Marumaya scheme given by,
IIA) IIA) + Σ hh
%/ [[s((9,, 84) V log.
(A( & (L(P(AT)
(C.4)
M Σ 11-1
(ElVV log (.)..) V log (( + E|A, A,, 112) dt,
From comparing the decomposition of Hadery-Maruumay and the exponential integrator scheme, we easily that the difference between Euler Marumaaa scheme and the exponential integrator scheme is the extra term
M
EIA,
Ai,
For this, we can use Lemma B.6 and immediately get that
A., 1 HA(4 1)², 4-11 S154
31

---

Convergent Analysis of Graph Diffusion Generation
Substituting this result into the extra term, have that,
M
4
E|A, - Av. Pdl
M
Σ 14-1
(144-11) HA 1)2
M
Σ
(2 - -)² (Hi -13 1)3
1=1
M
N2A + HAD!
Therefore, combining this result and the result of the exponential integrator scheme, we have,
M
(L(P(A))[I(AT)) & (L(P(AT)
A +
Σ
||so(9r, 42) VA log dl
E V
PG,)
V Pg
M
M
M
2 (N2 Hx)e + Tea + N2 xx
A +
A +
N E + HAD
M
M
= (N² + Hx)e -T +T + LN + N2) Σ
A + (N L + HA Σ A
This completes the proof.
C.3. Proof of Theorem 4.3
In this section, we present the proof for Theorem 4.3.
Proof of Theorem 4.3. We start with proving the result for the exponential integrator scheme.
Let Po be the data distribution and Pr is the learned distribution through the sampling scheme. We start with considering the exponetial integrator scheme. By Lemma B.4, we can decompose the KL divergence of Po and Pr as follows,
KL(P(X,))I(( S (L(P(X IIx) +
Σ
([sa( Vx log ((9
(C.5)
M
V log P(G..) Vx log F(.
Then, tackle each term in the equation above.
By Lemma B.5, we can immediately bound the first term as follows,
(L(PT(XX) S (NF+ + Hx)e
Next, we tackle the second term. By Assumption 3.2, we have that,
M
||s0 (9r, 4:) Vx log ((G,,)
M Aul1s0(91,,5) (.) - Vx log Pl
1=1
< T
32

---

Convergent Analysis of Graph Diffusion Generation Therefore, it remains tackle the last term. By Lemma B.9, we immediately get that
d; E.
V V log P(G.) Vx log de
NFI - 1) NFI( NFL d)
M
M
NFL Σ 2 + NFL Σ A
Combining all the results above, we get that,
+ Σ l (1s0(9u.;44) 44)
(I.(((X))I((XT) S (T [x)
Vx log (1
i=1 -e
M
E/| log P(G.) Vx log P(gr))]
11-1
M S (NF + Hx)e +T N
M NFL
2 4
+
Σ
3
i=1
M
M
+T NNL
L
A
A
f=1
1=1
This complete the derivation for the exponential integrator scheme. Again, from Lemma B.4, we have that the decomposition of convergence bound of the Burer-Marumaya scheme given by,
(L)) & (X [Ix) + Σ/ ld (s Vx log PGG,))
(C.6)
1
M Σ i=1
(ElVVx P.G.) Vx log + E| X,, 112) dt,
From comparing the decomposition of Bulery-Marumay and the exponential integrator scheme, we easily see that the difference between Marumaya scheme and the exponential integrator scheme is the extra term on
M
Σ
E X
X 1ddt
For this, we can use Lemma B.6 and immediately get that
X, X.,115555
SNF(
t) 11x (1: 1)2,
4-1 4-15151
33

---

Convergent Analysis of Graph Diffusion Generation
Substituting this result into the extra term, have that,
E 1, X., 11.
NF - + Hx(1; - 1)?
14-1
NF(4 -1 + - 11x(1xx-114 -t)3
NFA + Hx
Therefore, combining this result and the result of the exponential integrator scheme, we have,
M Σ
KL(P((,))(((x))) S (I((P(X)))
Ix) +
|150 (9.
Vx log P(9
1=1
4/1
M
E|] Vx log P(G.)
Vx log P(
+ TT +T NFL
A NFL
Σ
A Σ
NFA
-x
i=1
This completes the proof.
The derivation for the structure matrix A is similar and therefore is omitted here
D. Additional Results
In this appendix, we present additional results on the selection of Syper-parametert
Corollary D.1. Suppose the discretization step is uniform At; T/M 1, 1,-.. M. Then the convergence results of SGGMs under the exponential integrator scheme are given by
NFLTT2
KL(P(())II((r)) & (Hx + -FF))=F+TT- +
M
2
KL(P(A.)IP S (HA + +T
M
Furthermore, taking
T= max {log
Hx + NFF 6x
+NF
log
Hx + N2
2
E
2
22
M = max
2
we have that the overall generative error of SGGMs is bounded by the score estimation errors, i.e.,
{L(P(X)))IP(x+)))+
(L(P(A))IP(ATT) S a.
34

---

Convergent Analysis of Graph Diffusion Generation
Proof. By Theorem 4.3, have that,
KL(P(X))|P((r)) S (Hx + NNFe - +T
M
NNL
L
A + Σ At
(T(P(An) (T(()) S (HA + N2)e T
M N I. Σ
A + ΣS
(D.I)
By premise, have that A S This means that
A 2 A
This means that we can absorb the higher-order term with a larger constant. This leads to:
(T,(P(X)) 2 (Hx
NFJe + T
M
NNL
L
A
(L(P(Ao) (P)(()) & (HA N3)e +TEA
M
+ N 1. T
(D.2)
Then, replacing A., with T/M we get,
(L(P(X))IP(X)) (Hx NF)e +TE + NFL /M),
KL(P(A, (I((A)) (HA + + L (LT/MM)
(D.3)
With some algebra, we arrive
NFL2
(I(P(()))I((XT) S (Hx + +
M
N2
(T.((()))I((TT) (HA + -
M
Next, substituting in our choice of T and M
Hxx + NF
Hix + +22
T = max
log
log
X
NFFT222
Nº
M = max
&
is easy to check that the overall generative error of SGGMs bounded by the score estimation errors, i.c..
KL(P(X, PP (X)) S &
(P 2
Similarly, we have the following result for the Marum-ya scheme and omit the proof due to similarity.
35

---

Convergent Analysis of Graph Diffusion Generation
Corollary D.2. Suppose the discretization step is uniform Al; T/M s 1, 1,.. M. Then the convergence resulls of SGGMs under MallerMarumaya scheme are given by
NFI.T
KL(P(X.)III(X))) (Hx + NFFe +T +
M
2T
KT.P(AO)]IP(TT)) (HA ( (
Furthermore, laking
+NF Hx + NF
Hx + N2 A
T max
log
,log
&
(NFL'T Nº
M max
we have that the overall generative error of SGGMs is bounded by the score estimation errors, i.e.
KLIP(X.))IP(A.)) 5c, (LPP(A))IP(AO)) E
D.1. Bound with Other Measures
In the context of generative models and their convergence properties, it is often useful to bound the discrepancy between two probability distributions, P and Q, using different metries. Among the most commonly used divergence measures are the Kullback-Leibhe (KL) divergence, Wasserstein distance, and total variation (TV) distance. In this paper, we adopt the KI. divergence as the measure for the analysis of its direct relation with the training objectives. In this section, we present a discussion of how our result with KL divergence also immediately implies a bound on the other two bounds. We start by providing brief introduction each of the metrics.
The Kullback-Leibler (KI.) divergence, is defined as:
dP log
KL(P| = Ep
dQ
measures the expected logarithmic difference between the probability densities I and Q corresponding to the distributions and Q. This divergence widely used in variational inference and optimization because of its convenient properties, such when TP = Q. However, KI. divergence is not symmetric and does
non-negatyvyty and the fact that it is always satisfy the triangle inequality, making it less suitable distance metric in certain contexts.
In contrast, the Wasserstein distance, is defined as:
W (FP, Q) inf (Ex -
7EL(F.0)
It measures the "cost" of transforming one distribution into another by considering the optimal transport plan that minimizes this cost. is a more intuitive and geometrically meaningful metric compared to KI. divergence, especially in high-dimensional spaces. Wasserstein distance has the advantage of being symmetric and satisfying the triangle inequality, which makes a true metric. When p = 1, the Wasserstein distance is often referred to as the Earth Mover's Distance (EMD).
Total variation (TV) distance is another useful metric defined as:
TV(P, Q) = 1 / [P(x)) (())ddr,,
which quantifies the maximum difference between the probabilities assigned to the same event by two distributions. TV distance is symmetric and satisfies the triangle inequality, making it a true distance metric. tightly connected to other divergences like KI. divergence and can be bounded terms of them.
36

---

Convergent Analysis of Graph Diffusion Generation
D. 1.1. RELATIONSHIP BETWEEN KL DIVERGENCE, WASSERSTEIN DISTANCE, TV DISTANCE
is known that the KL divergence can be bounded in terms of both the Wasserstein distance and the total variation distance. Specifically, the following inequalities provide useful bounds:
KL. Divergence and Total Variation Distance:
KL(PIQQ) 2 (TV Q)² for distributions with bounded support.
The result above is known to be Pinsker's inequality. It shows that while KL divergence is at least as large as the square of the TV distance, up to constant factor.
Wasserstein Distance AND Total Variation Distance:
Wi Q) IV(P.Q)
where (P,,, Q) is the Wasserstein distance with 1. The relation above holds for bounded metric space. Then, by transitivity property, we get that (IP,, Q) S (Q).
The results above show that our results in this paper immediately imply a (growth) bound with the other two commonly used measures (at least in some cases) as well.
E. Experiment Details
In this appendix, provide additional details experimental study. This section elaborates the testbed setup, graph generation model, the implementation of score-based graph generative models (SGGMs), and the hyperparameter search.
E.1. Testbed
Our experiments were conducted Dell PowerEdge C4140 server. The key specifications of this server, relevant to research, are as follows:
CPU: Dual Intel Xeon Gold 6230 processors, each offering 20 cores and 40 threads.
GPU: Four NVIDIA Tesla V100 SXM2 units, each equipped with 32GB of memory, tailored for NV Link.
Memory: total of 256GB RAM, distributed across eight 32GB RDIMM modules.
Storage:
Dual 1. 1,92TB SSDs with a 6Gbps SATA interface.
Networking: Dual 1bbs NICs and Mellanox ConnectX-5 EX Dual Port 40/100GbE QSFP28 Adapter with GPUDirect support.
Operating System: Ubuntu 18.04 LTS.
E.2. Graph Generation Model
For our experiments, primarily utilize the NetworkX Python library (Hagberg et al., 2008). Specifically, default implementations of regular graph generation and the Barabási-Albert model (Pósfai & Barabási, 2016) provided by NetworkX. The Barabási-Alle Albert (BA) model is widely used to generate scale-free networks characterized by power-law degree distribution. The core idea behind the BA model is preferential attachment, where new nodes are more likely to connect to existing nodes with a higher degree of connections. This mechanism mirrors real-world networks, such as social networks, where popular individuals (nodes) tend attract more connections.
the
Procedure of the Barabási-Albert Model.
The Srrabási-Albert model generates network through the following steps:
1. Initialization: Start with a small connected network of my nodes.
2. Growth: Add one new node at time, Each new node forms edges connecting it to m existing nodes.
37

---

Convergent Analysis of Graph Diffusion Generation
3. Preferential Attachment: The probability that node connects existing node is proportional the degree of node Formally, the probability P(t) that the new node connects to node is given by:
k Σ, ky
P(i)
where ky is the degree node and the sum is taken over all existing nodes.
Hyperparameters. The BA model has two key hyperparameters:
mo The initial number of nodes in the network.
m The number of edges each new node adds when it is introduced to the network. This parameter influences the density and structure of the resulting network.
E.3. Score Networks and Diffusion
simple one-layer Graph Convolutional Network (GCN) as the network. However, to ensure sufficient capacity for learning, we use two-layer MLPs (multi-layer perceptrons) preceding the GCN layer. The hidden layer size is set to 500 for all experiments. For the diffusion process, we set the diffusion length 7 50 to ensure sufficient diffusion, and we use a uniform step size of 0.1 for the sampling scheme. For simplicity, our experiments focus on the Suler-Maruyaan scheme, and early stopping is employed to prevent variance explosion near the end.
In the experiments,
E.4. Hyperparameter Search for Learning Algorithm
To train the SGGMs, we use the widely adopted Adam optimizer (Kingma Ba, 2014). A simple parameter search is performed for the learning rate, testing values from the set (0.1, 0.01, 0.001, 0.0001]. The implementation of the Adam algorithm is provided by the PyTorch library.
38


Reviews:
[{"review_id": "GhBfK57nUl", "reviewer": "Reviewer_cgKb", "summary": "The authors present convergence analysis for score-based graph diffusion generative models where both the generation of the feature vectors at each node of the graph as well as the graph structure is generated based on a diffusion model.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## Why Not Formulate as a Single SDE on $\\mathbf{G}_t$\n\nYou 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:\n\n- Intra-structure dependency: among entries of $\\mathbf{A}_t$.\n- Intra-feature dependency: among entries of $\\mathbf{X}_t$.\n- Cross-dependency: between $\\mathbf{A}_t$ and $\\mathbf{X}_t$, which evolves through the shared time parameter and coupled score functions.\n\nThe 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.\n\nTherefore, 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.\n\n## What Is Technically Novel and Important?\n\nWe 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:\n\n- 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).\n- 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.\n\nWe 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.", "claims_and_evidence": "The claims made are clear", "methods_and_evaluation_criteria": "Evaluation and method make sense", "theoretical_claims": "I did not check the correctness of the proofs. I skimmed the proof structure and key lemmas.", "experimental_designs_or_analyses": "I did not check the soundness of the experimental designs.", "relation_to_broader_scientific_literature": "The joint generation creates extra difficulties in the convergence analysis as compared to prior work that focused on convergence analysis of generative models, but not graphical models. In particular, the two reverse diffusion processes are interdependent.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "I found the main claim of the essence of the technical contribution not clear.\n\nIt is true that the two reverse SDEs are interdependent, but what was not at all clear to me was why theoretically can't one just view this as a single SDE on the pair G_t = (Xt, At). \n\nWhat breaks if one views the generative process as a single SDE on Gt and applies prior results on the convergence of score-based generative models. In any single generative model, the process that generates any sub-component of the vector, is interdependent with the process that generates the remaining sub-components. So this type of difficulty exists in prior proofs too, if one views it as a single diffusion process.\n\nThe authors do not explain clearly, why such a route to a theoretical result is not viable, even if in practice one would view them qualitatively as two processes.\n\nThe proof seems to essentially be invoking prior theoretical results on convergence for single diffusion processes, but simply twice, for each diffusion. A better explanation as to which technical lemmas are novel would be very elucidating.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "No other questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "14wY3X5CXS", "reviewer": "Reviewer_cnQ4", "summary": "The paper presents an analysis of graph diffusion processes building heavily on results from https://arxiv.org/abs/2211.01916 (at least based on my reading?) . They find that graph size is much more determinative for convergence rate than feature complexity (mirroring results from https://proceedings.neurips.cc/paper/2020/hash/99503bdd3c5a4c4671ada72d6fd81433-Abstract.html ) derive testable implications from their analysis (normalization helps, regular graphs are easier than power law graphs, graph size hurts more than feature size) which are verified in a toy example.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## Suggested Reference\n\nThank 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.\n\n## Empirical study improvement\n\nThank you very much for your thoughtful suggestions regarding the empirical study — we greatly appreciate the detailed and constructive feedback.\n\nWe 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.\n\nRegarding 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.\n\nIn 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.\n\nTo quantify the effects, we further computed best-fit line coefficients to estimate the sensitivity of KL-divergence to changes in each variable:\n\n|  | 50 | 100 | 200 | 500 | Best-Fit Line Coefficient |\n| --- | --- | --- | --- | --- | --- |\n| Changing Graph Size (with fixed feature size= 50, with normalization) | 0.56 | 2.00 | 4.86 | 8.67 | 0.017 |\n| Changing Feature size with normalization (with fixed graph size = 50) | 0.56 | 1.23 | 2.23 | 3.88 | 0.007 |\n| Changing Feature size without normalization (with fixed graph size = 50) | 0.60 | 1.31 | 2.62 | 4.46 | 0.008 |\n\nAs 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.\n\nThank you again for your valuable comments. We will incorporate these new results and the accompanying analysis into the revised version of the paper.\n\n[1] Newman, Mark, Networks: An Introduction", "claims_and_evidence": "The analysis looks sensible, although I did not have time to critically check each step.\nThe empirical analysis is a bit weak, but passes a toy example sniff test in what is primarily a theory paper", "methods_and_evaluation_criteria": "As above, the numerics are a toy example, I think it would be beneficiel to check literature results of SOTA models that fit the papers framework and check the graph properties for the expected correlation (maybe kendal tau) with performance to beef up the papers applicability with realtively little work. alterantively, picking tractable datasets or  standard models (SBM, AB is already present, a few more), and confirm with numerics not via the kernel generation method but via somehting more interpretable (the images look the same to me). failing that, at least using suitable statistical tests (see e.g. https://arxiv.org/abs/1811.12808 ) should be performed.", "theoretical_claims": "As stated above, the claims seem supported, but no detailed anaysis has been performed.", "experimental_designs_or_analyses": "see the methods and evaluation section.", "relation_to_broader_scientific_literature": "I think https://proceedings.neurips.cc/paper/2020/hash/99503bdd3c5a4c4671ada72d6fd81433-Abstract.html is an important paper to cite, since it offers some justification for why feature complexity might not matter. open question of _why_ graph size hurts so much though (intuitively it makes sense)", "essential_references_not_discussed": "none except the above suggestion.", "other_strengths_and_weaknesses": "nothing I can highlight", "other_comments_or_suggestions": "nothing I can highlight", "questions_for_authors": "nothing I can highlight", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "alPs5FTutR", "reviewer": "Reviewer_LiK1", "summary": "This paper provides a non-asymptotic convergence analysis for score-based graph generative models (SGGMs), which involve coupled stochastic differential equations for graph structure and node features. The authors explore convergence bounds across three graph generation paradigms and identify factors like graph topology and feature normalization that influence convergence. Theoretical insights are paired with experimental validation using synthetic graphs, offering practical guidance on hyperparameter selection. The work deepens understanding of SGGMs' theoretical behavior and their application in fields such as drug discovery.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n# Independency in the forward equation\n\n* 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].\n\n* 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.\n\nThank 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.\n\n[1] \"Score-based generative modeling of graphs via the system of stochastic differential equations.\" *International conference on machine learning*.\n\n[2] \"DiGress: Discrete Denoising diffusion for graph generation.\" *The Eleventh International Conference on Learning Representations*.", "claims_and_evidence": "The claims made in the submission are well supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "Theorem 4.1 to Theorem 4.3 in page 6 checked, no issue found.", "experimental_designs_or_analyses": "Experiment design in Section 5 checked, no issue identified.", "relation_to_broader_scientific_literature": "This paper builds on prior work in score-based generative models (SGMs), which typically use a single SDE. It extends these analyses to score-based graph generative models (SGGMs) involving coupled SDEs for graph structure and node features. The paper provides novel non-asymptotic convergence bounds and insights for hyperparameter tuning.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper presents a novel non-asymptotic convergence analysis for score-based graph generative models (SGGMs), extending traditional SGM theories to accommodate the complexities of coupled stochastic differential equations (SDEs), which enhances its theoretical contributions in graph generation.\n\n2. By addressing SGGMs, the paper makes a meaningful contribution to critical real-world applications like drug discovery and protein design, where graph-based generative models have significant practical value.\n\n3. The authors provide empirical evidence to support their theoretical findings, using synthetic graph models. This strengthens the paper's practical relevance and enhances the reliability of the proposed convergence analysis.\n\nWeaknesses:\nSee questions for authors", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Although the paper is overall sound and convincing, I have some confusion regarding the equation: $P(g_t|g_0)=p(X_t|X_0)P(A_t|A_0)$ on page 4. If I understand correctly, does this imply that, at time t, the influence of the node feature $X$ and and the adjacency matrix $A$ on the graph are independent of each other? \n\nWhile this can be explained by the assumption that the generation process is based on a standard Gaussian distribution, an intuitive explanation for why this assumption holds—or at least does not significantly impact the model's performance—would strengthen the paper further.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors present a strong theoretical contribution on the consistency of graph-based diffusion generative models. Their analysis is heavily buidling on prior work on consistency of score based diffusion models, albeit by explicitly analyzing the convergence behavior of the graph component and the node value component they shed light on practical aspects of graph generative modeling.
Decision: Accept (poster)