# Advancing Graph Generation through Beta Diffusion

Yilin He  Xinyang Liu  Bo Chen  Mingyuan Zhou

###### Abstract

Diffusion models have demonstrated effectiveness in generating natural images
and have been extended to generate diverse data types, including graphs. This
new generation of diffusion-based graph generative models has demonstrated
significant performance improvements over methods that rely on variational
autoencoders or generative adversarial networks. It’s important to recognize,
however, that most of these models employ Gaussian or categorical diffusion
processes, which can struggle with sparse and long-tailed data distributions.
In our work, we introduce Graph Beta Diffusion (GBD), a diffusion-based
generative model particularly adept at capturing diverse graph structures. GBD
utilizes a beta diffusion process, tailored for the sparse and range-bounded
characteristics of graph adjacency matrices. Furthermore, we have developed a
modulation technique that enhances the realism of the generated graphs by
stabilizing the generation of critical graph structures, while preserving
flexibility elsewhere. The outstanding performance of GBD across three general
graph benchmarks and two biochemical graph benchmarks highlights its
capability to effectively capture the complexities of real-world graph data.
The code will be made available on GitHub. The code will be made available at
https://github.com/YH-UtMSB/Graph_Beta_Diffusion.

##  1 Introduction

In recent years, the field of machine learning-driven graph generation has
witnessed a surge in interest and activity. This growing attention is driven
by the recognition of graph data’s pervasive presence and utility across
diverse real-world applications, ranging from social network study (Newman et
al., 2002; Conti et al., 2011; Abbe, 2018; Shirzadian et al., 2023) to
biochemical molecular research (Jin et al., 2018; Liu et al., 2018; Bongini et
al., 2021; Guo et al., 2024; Li and Yamanishi, 2024). Additionally, the rapid
evolution of machine learning tools has introduced powerful techniques for
data generation, among which diffusion models (Ho et al., 2020; Song et al.,
2021; Austin et al., 2021; Avdeyev et al., 2023; Chen and Zhou, 2023; Zhou et
al., 2023) stand out as a notable example. As these advanced tools intersect
with the task of graph generation, we witness the emergence of numerous
diffusion-based graph generative models (Niu et al., 2020a; Jo et al., 2022;
Haefeli et al., 2022; Huang et al., 2022; Vignac et al., 2023; Jo et al.,
2023; Cho et al., 2023; Chen et al., 2023; Kong et al., 2023).

While diffusion-based graph generative models often demonstrate superior
performance compared to their predecessors (You et al., 2018; De Cao and Kipf,
2018; Li et al., 2018; Simonovsky and Komodakis, 2018; Liu et al., 2019; Shi
et al., 2020; Luo et al., 2021; Martinkus et al., 2022), there is still
potential for further enhancement in the quality of generated graphs. Among
the latest advancements in these methods, it is widely recognized that
incorporating inductive bias from the graph data is generally beneficial for
model design (Jo et al., 2023). One promising direction of incorporating this
bias involves considering the statistical characteristics of the distribution
of graph data. For instance, both Graph D3PM (Haefeli et al., 2022) and
DiGress (Vignac et al., 2023) have demonstrated that when considering the
binary or categorical nature of the graph adjacency matrix and modeling it in
the discrete space, it provides benefits for generating more realistic graphs.

Accounting for the discreteness of the graph adjacency matrix has shown
enhancement to model performance. However, it is crucial to recognize that the
complexity and flexibility of distribution characteristics of graph data
extend beyond mere discreteness. Real-world graphs typically exhibit sparsity
in edge distribution and long-tailedness in nodal statistical properties such
as degrees and categories (Barabási et al., 2000; Ciotti et al., 2015; Liang
et al., 2023; Wang et al., 2023). Moreover, when mapping the graph structure
into an adjacency matrix, the values within the matrix are also bounded by the
range of edge weights. Given these unique characteristics inherent to graph
data, it becomes apparent that Gaussian and categorical distributions, which
are typically the default choices for building the diffusion processes, may
not align well with these graph characteristics. Consequently, this mismatch
could potentially introduce limitations when modeling the distribution over
graphs.

Considering the desirable statistical characteristics of graph data, we find
that the beta distribution emerges as a particularly suitable modeling choice.
With properties such as being range-bounded and flexible to model data at all
sparsity levels, the beta distribution aligns well with the inherent traits of
graphs, hence making itself a promising candidate to surpass the potential
limitations imposed by utilizing Gaussian or categorical distributions. In
this paper, we introduce Graph Beta Diffusion (GBD) as a novel addition to
diffusion-based graph generative models. GBD models the joint distribution of
node attributes and edge connections within a graph through beta diffusion
(Zhou et al., 2023), a generative diffusion process developed upon the
thinning and thickening of beta random variables. In the forward diffusion
process, the original data is gradually attenuated toward zero. This process
starts with a modified form of the data, which is scaled and shifted to ensure
it is bounded between 0 and 1. At each step, a random proportion, sampled from
a beta distribution with a predefined noise schedule, is multiplied with the
attenuated data. Conversely, the reverse diffusion process starts from zero
and attempts to recover the original data. It does this by adding a random
proportion of the difference between one and the current value to the current
value at each step.

We underscore two major contributions arising from the development of GBD.
First, our experiments generating data on various synthetic and real-world
graphs confirm the effectiveness of beta diffusion as a strategic choice
within the design framework of the backbone diffusion model, especially for
graph generation tasks. Second, our exploration of the model’s design space
has yielded a set of recommended practices, notably a novel modulation
technique that bolsters the stability of generating essential graph
structures. We demonstrate that these practices, when implemented together,
lead to consistent enhancements in model performance.

##  2 The Methodology

Figure 1: Overview of GBD. The beta random variables $Q_{t}$ and $P_{t}$ are
sampled from the beta distribution parameterized by $G_{0}$ and clean graph
predicted by the neural network $\tilde{G}_{\theta}$, respectively.
$\tilde{G}_{\theta}$ is learned through minimizing
$\mathcal{L}_{\mathrm{sampling}}$ and $\mathcal{L}_{\mathrm{correction}}$
defined in Section 2.3.

###  2.1 Data description and mathematical notations

In this study, our primary focus lies in generating two types of graphs:
generic graphs and molecular graphs. Generic graphs are characterized as
undirected, simple graphs with $N$ nodes. Each pair of nodes $(u,v)$ in these
graphs can only have two possible edge statuses: connected or disconnected.
Therefore, the entire graph structure can be fully described by a symmetric
binary adjacency matrix ${\mathbf{A}}\in\\{0,1\\}^{n\times n}$, where “$1$”s
denote connected node pairs and “$0$”s denote pairs that are not directly
connected. Molecular graphs are also simple graphs, but they typically feature
multiple types of edges. As a result, their graph structures need to be
represented as adjacency matrices with dummy-encoded categorical variable
elements, which is a common practice established in previous research (Jo et
al., 2022; Vignac et al., 2023; Jo et al., 2023). This expression results in a
multitude of channels in the graph adjacency matrix, we use
${\mathbf{A}}^{(1:K)}$ to represent the structure of a graph with $K$ types of
edges.

While the primary goal of graph generation and quality evaluation centers
around graph architecture, incorporating the node features can be advantageous
for learning the distribution of the adjacency matrices. Node features are
typically represented by a matrix ${\mathbf{X}}$ of shape $n\times d$, where
$d$ denotes the number of features. The choices of node features offers high
flexibility, ranging from raw-data-provided node categories to some hand-
crafted features, such as node-level statistics (Jo et al., 2022) or spectral
graph signals (Jo et al., 2023). The features within ${\mathbf{X}}$ exhibit
great diversity in their nature, including numerical, categorical, and ordinal
types. Through preprocessing methods including dummy-encoding and empirical
CDF transformation, we standardize them as continuous variables bounded by
$[0,1]$. In this section, we denote the target datum as ${\mathbf{G}}$. For
generic graphs, ${\mathbf{G}}$ comprises $({\mathbf{A}},{\mathbf{X}})$; for
molecular graphs, ${\mathbf{G}}$ is defined as
$({\mathbf{A}}^{(1:K)},{\mathbf{X}})$. In the sequel, We by default employ the
generic graph scenario to illustrate the methodology.

###  2.2 Forward and reverse beta diffusion processes

#### Forward beta diffusion process.

Such a process can be characterized by the transition probability
$q({\mathbf{G}}_{t}|{\mathbf{G}}_{t-1},{\mathbf{G}}_{0})$, with
${\mathbf{G}}_{0}$ denoting the combination of the original adjacency matrix
and node feature matrix. Following recent diffusion-based graph generative
models (Jo et al., 2022; Vignac et al., 2023; Jo et al., 2023; Cho et al.,
2023), we assume $q({\mathbf{G}}_{t}|{\mathbf{G}}_{t-1},{\mathbf{G}}_{0})$ to
be factorizable such that
$q({\mathbf{G}}_{t}|{\mathbf{G}}_{t-1},{\mathbf{G}}_{0})=q({\mathbf{A}}_{t}|{\mathbf{A}}_{t-1},{\mathbf{A}}_{0})\cdot
q({\mathbf{X}}_{t}|{\mathbf{X}}_{t-1},{\mathbf{X}}_{0})$. Constructing the
forward beta diffusion process (Zhou et al., 2023) for graph modeling, we
have:

$\displaystyle{\mathbf{A}}_{t}={\mathbf{A}}_{t-1}\odot{\mathbf{Q}}_{A,t},~{}{\mathbf{Q}}_{A,t}\sim\mathrm{Beta}\left(\eta_{A}\alpha_{t}{\mathbf{A}}_{0},\eta_{A}(\alpha_{t-1}-\alpha_{t}){\mathbf{A}}_{0}\right),$
(1)
$\displaystyle{\mathbf{X}}_{t}={\mathbf{X}}_{t-1}\odot{\mathbf{Q}}_{X,t},~{}{\mathbf{Q}}_{X,t}\sim\mathrm{Beta}\left(\eta_{X}\alpha_{t}{\mathbf{X}}_{0},\eta_{X}(\alpha_{t-1}-\alpha_{t}){\mathbf{X}}_{0}\right),~{}t\in[1,T].$
(2)

Here $\eta_{A},\eta_{X}$ are positive scalars adjusting the concentration of
beta distributions, with higher values leading to enhanced concentration and
reduced variability. The diffusion noise schedule is defined with
$\\{\alpha_{t}\,\mid\,t\in[1,T]\\}$, which represent a sequence of values
descending from 1 towards 0 as $t$ increases. Elements in the fractional
multiplier ${\mathbf{Q}}_{A,t}$ or ${\mathbf{Q}}_{A,t}$ are independently
sampled from their respective beta distributions. With the forward diffusion
process defined in Equations 1 and 2, we characterize the stochastic
transitions of an element $g$ within ${\mathbf{G}}$ as:

$q(g_{t}\,\mid\,g_{t-1},g_{0})=\frac{1}{g_{t-1}}\mathrm{Beta}\left(\frac{g_{t}}{g_{t-1}}\,\mid\,\eta\alpha_{t}g_{0},\eta(\alpha_{t-1}-\alpha_{t})g_{0}\right),$
(3)

where depending on whether $g$ is an element in ${\mathbf{A}}$ or
${\mathbf{X}}$, we have either $\eta=\eta_{A}$ or $\eta=\eta_{X}$. Derived
from Equation 3, the joint distribution
$q({\mathbf{G}}_{1:T}|{\mathbf{G}}_{0})$ has analytical format in the marginal
distribution on each time stamp $t$, specifically,

$q({\mathbf{G}}_{t}\,\mid\,{\mathbf{G}}_{0})=\mathrm{Beta}(\eta\alpha_{t}{\mathbf{G}}_{0},\eta(1-\alpha_{t}{\mathbf{G}}_{0})).$
(4)

#### Reverse beta diffusion process.

It is important to note that the joint distribution
$q({\mathbf{G}}_{1:T}|{\mathbf{G}}_{0})$ can be equivalently constructed in
reverse order through ancestral sampling, which directs samples from the
terminus states ${\mathbf{G}}_{T}$ towards the initial states
${\mathbf{G}}_{0}$ by incrementally applying the changes
$\delta{\mathbf{G}}_{t}$ at each reversed time stamp. With the changes at a
given time $t$ parameterized as
$\delta{\mathbf{G}}_{t}:={\mathbf{P}}_{t}\odot(1-{\mathbf{G}}_{t})$, where
${\mathbf{P}}_{t}$ are beta-distributed fractional multipliers, the time-
reversal sampling process can be mathematically defined as: for
$t=T,T-1,\cdots,1$,

${\mathbf{G}}_{t-1}={\mathbf{G}}_{t}+{\mathbf{P}}_{t}\odot(1-{\mathbf{G}}_{t}),~{}{\mathbf{P}}_{t}\sim\mathrm{Beta}\left(\eta(\alpha_{t-1}-\alpha_{t}){\mathbf{G}}_{0},\eta(1-\alpha_{t}{\mathbf{G}}_{0})\right).$
(5)

Similar to the forward sampling process, we can derive the transition
distribution corresponding to the reverse sampling process described in
Equation 5 as following:

$q({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t},{\mathbf{G}}_{0})=\frac{1}{1-{\mathbf{G}}_{t}}\mathrm{Beta}\left(\frac{{\mathbf{G}}_{t-1}-{\mathbf{G}}_{t}}{1-{\mathbf{G}}_{t}}\,\mid\,\eta(\alpha_{t-1}-\alpha_{t}){\mathbf{G}}_{0},\eta(1-\alpha_{t-1}{\mathbf{G}}_{0})\right).$
(6)

Following previous work (Austin et al., 2021; Haefeli et al., 2022; Vignac et
al., 2023; Zhou et al., 2023), we construct the reverse diffusion process
through the definition of ancestral sampling distribution as following:

$p_{\theta}({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t}):=q({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t},\hat{G}_{\theta}({\mathbf{G}}_{t},t)),$
(7)

where $\hat{G}_{\theta}({\mathbf{G}}_{t},t)$ is a neural network that predicts
the conditional expectation of ${\mathbf{G}}_{0}$ given ${\mathbf{G}}_{t}$.
Following Vignac et al. (2023), we instantiate
$\hat{G}_{\theta}({\mathbf{G}}_{t},t)$ as a graph transformer network (Dwivedi
and Bresson, 2020a). We present the complete sampling process in Algorithms 1
and 2.

Algorithm 1 Sampling, in original domain.

1:Number of timesteps $T=1000$, default concentration parameter $\eta=30$,
predictor $\hat{G}_{\theta}$.

2:(Optional) Assign value to $\eta$ via Equation 16

3:Sample ${\mathbf{G}}_{T}=({\mathbf{A}}_{T},{\mathbf{X}}_{T})\sim
p({\mathbf{A}}_{T},{\mathbf{X}}_{T})$

4:for $t=T$ to 1 do

5:
${\mathbf{G}}_{in}=\frac{{\mathbf{G}}_{t}-\mathbb{E}[{\mathbf{G}}_{t}]}{\sqrt{\mathrm{Var}[{\mathbf{G}}_{t}]}}$

6:
$(\hat{{\mathbf{A}}}_{0}^{\prime},\hat{{\mathbf{X}}}_{0}^{\prime})\leftarrow\hat{G}_{\theta}({\mathbf{G}}_{in},t)$

7: $\hat{{\mathbf{A}}}_{0}\leftarrow
w_{A}\cdot\hat{{\mathbf{A}}}_{0}^{\prime}+b_{A}$

8: $\hat{{\mathbf{X}}}_{0}\leftarrow
w_{X}\cdot\hat{{\mathbf{X}}}_{0}^{\prime}+b_{X}$

9:
$\hat{{\mathbf{G}}}_{0}\leftarrow(\hat{{\mathbf{A}}}_{0},\hat{{\mathbf{X}}}_{0})$

10:
${\mathbf{P}}_{t}\sim\mathrm{Beta}(\eta(\alpha_{t-1}-\alpha_{t})\hat{{\mathbf{G}}}_{0},\eta(1-\alpha_{t-1}\hat{{\mathbf{G}}}_{0}))$

11:
${\mathbf{G}}_{t-1}\leftarrow{\mathbf{G}}_{t}+{\mathbf{P}}_{t}\odot(1-{\mathbf{G}}_{t})$

12:end for

13:return $({\mathbf{A}}_{0}-b_{A})/w_{A}$ and
$({\mathbf{X}}_{0}-b_{X})/w_{X}$

Algorithm 2 Sampling, in logit domain

1:Sample $\mathrm{logit}({\mathbf{G}}_{T})\sim
p(\mathrm{logit}({\mathbf{A}}_{T}),\mathrm{logit}({\mathbf{X}}_{T}))$

2:for $t=1$ to 1 do

3:
${\mathbf{G}}_{in}=\frac{\mathrm{logit}({\mathbf{G}}_{t})-\mathbb{E}[\mathrm{logit}({\mathbf{G}}_{t})]}{\sqrt{\mathrm{Var}[\mathrm{logit}({\mathbf{G}}_{t})]}}$

4:
$(\hat{{\mathbf{A}}}_{0}^{\prime},\hat{{\mathbf{X}}}_{0}^{\prime})\leftarrow\hat{G}_{\theta}({\mathbf{G}}_{in},t)$

5: $\hat{{\mathbf{A}}}_{0}\leftarrow
w_{A}\cdot\hat{{\mathbf{A}}}_{0}^{\prime}+b_{A}$

6: $\hat{{\mathbf{X}}}_{0}\leftarrow
w_{X}\cdot\hat{{\mathbf{X}}}_{0}^{\prime}+b_{X}$

7:
$\hat{{\mathbf{G}}}_{0}\leftarrow(\hat{{\mathbf{A}}}_{0},\hat{{\mathbf{X}}}_{0})$

8:
${\mathbf{U}}_{t}\sim\mathrm{Gamma}(\eta(\alpha_{t-1}-\alpha_{t})\hat{{\mathbf{G}}}_{0},1)$

9:
${\mathbf{V}}_{t}\sim\mathrm{Gamma}(\eta(1-\alpha_{t-1}\hat{{\mathbf{G}}}_{0}),1)$

10:
$\mathrm{logit}({\mathbf{P}}_{t})\leftarrow\ln{\mathbf{U}}_{t}-\ln{\mathbf{V}}_{t}$

11: Obtain $\mathrm{logit}({\mathbf{G}}_{t-1})$ from Equation 17

12:end for

13:${\mathbf{G}}_{0}\leftarrow\mathrm{sigmoid}\left(\mathrm{logit}({\mathbf{G}}_{0})\right)$

14:return $({\mathbf{A}}_{0}-b_{A})/w_{A}$ and
$({\mathbf{X}}_{0}-b_{X})/w_{X}$

###  2.3 Training GBD

The overall training procedure of GBD is described in Algorithms 3 and 4. We
employ the objective function proposed by beta diffusion (Zhou et al., 2023),
specifically,

$\mathcal{L}=\sum_{t=2}^{T}~{}(1-\omega)\mathcal{L}_{\mathrm{sampling}}(t,{\mathbf{G}}_{0})+\omega~{}\mathcal{L}_{\mathrm{correction}}(t,{\mathbf{G}}_{t}),~{}\omega\in[0,1].$
(8)

In Equation 8, the loss terms associated with sampling and correction are
defined as

$\displaystyle\mathcal{L}_{\mathrm{sampling}}(t,{\mathbf{G}}_{0})$
$\displaystyle\overset{\Delta}{=}\mathbb{E}_{q({\mathbf{G}}_{t},{\mathbf{G}}_{0})}~{}\mbox{KL}\left(p_{\theta}({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t})\;\lVert\;q({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t},{\mathbf{G}}_{0})\right),$
(9) $\displaystyle\mathcal{L}_{\mathrm{correction}}(t,{\mathbf{G}}_{0})$
$\displaystyle\overset{\Delta}{=}\mathbb{E}_{q({\mathbf{G}}_{t},{\mathbf{G}}_{0})}~{}\mbox{KL}\left(q({\mathbf{G}}_{\tau}\,\mid\,\hat{G}_{\theta}({\mathbf{G}}_{t},t))\;\lVert\;q({\mathbf{G}}_{\tau}\,\mid\,{\mathbf{G}}_{0})\right).$
(10)

In Equation 10, the KL divergence is evaluated between the following
distributions:
$q({\mathbf{G}}_{\tau}\,\mid\,\hat{G}_{\theta}({\mathbf{G}}_{t},t))$ is
$\mathrm{Beta}(\eta\alpha_{t}\hat{G}_{\theta}({\mathbf{G}}_{t},t),\eta(1-\alpha_{t}\hat{G}_{\theta}({\mathbf{G}}_{t},t)))$,
and $q({\mathbf{G}}_{\tau}\,\mid\,{\mathbf{G}}_{0})$ is the same as
$q({\mathbf{G}}_{t}\,\mid\,{\mathbf{G}}_{0})$ in distribution. The subscript
$\tau$ is introduced to represent a generic graph sample other than
${\mathbf{G}}_{t}$ that is also obtained at time $t$ from the forward
diffusion process. The core principle behind the loss function terms can be
described as follows: $\mathcal{L}_{\mathrm{sampling}}$ drives the empirical
ancestral sampling distribution towards the destination-conditional posterior
distribution, while $\mathcal{L}_{\mathrm{correction}}$ corrects the bias on
marginal distribution at each time stamp accumulated through the ancestral
sampling. These two types of loss terms collectively reduce the divergence
between the empirical joint distribution on two graphs sampled from adjacent
time stamps in the reverse process, and their joint distribution derived from
the forward diffusion process. A positive weight $\omega$ is introduced to
balance the effects of these two types of loss terms. We set it to 0.01,
following Zhou et al. (2023), and found that this configuration is sufficient
to produce graphs that closely resemble the reference graphs without further
tuning. To better elucidate the optimization objective, we list out the
following analytical expressions:

$\displaystyle\mbox{KL}\left(p_{\theta}({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t})\;\lVert\;q({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t},{\mathbf{G}}_{0})\right)$
$\displaystyle=\ln\Gamma(\eta(\alpha_{t-1}-\alpha_{t}){\mathbf{G}}_{0})+\ln\Gamma(\eta-\eta\alpha_{t-1}{\mathbf{G}}_{0})+\ln\Gamma(\eta-\eta\alpha_{t}{\mathbf{G}}_{0})$
$\displaystyle-\ln\Gamma(\eta(\alpha_{t-1}-\alpha_{t})\hat{{\mathbf{G}}}_{0})-\ln\Gamma(\eta-\eta\alpha_{t-1}\hat{{\mathbf{G}}}_{0})-\ln\Gamma(\eta-\eta\alpha_{t}\hat{{\mathbf{G}}}_{0})$
$\displaystyle+\eta(\alpha_{t-1}-\alpha_{t})(\hat{{\mathbf{G}}}_{0}-{\mathbf{G}}_{0})\cdot\psi(\eta(\alpha_{t-1}-\alpha_{t})\hat{{\mathbf{G}}}_{0})$
(11)
$\displaystyle+\eta\alpha_{t-1}({\mathbf{G}}_{0}-\hat{{\mathbf{G}}}_{0})\cdot\psi(\eta-\eta\alpha_{t-1}\hat{{\mathbf{G}}}_{0})$
$\displaystyle+\eta\alpha_{t}({\mathbf{G}}_{0}-\hat{{\mathbf{G}}}_{0})\cdot\psi(\eta-\eta\alpha_{t}\hat{{\mathbf{G}}}_{0}),$
$\displaystyle\mbox{KL}\left(q({\mathbf{G}}_{\tau}\,\mid\,\hat{G}_{\theta}({\mathbf{G}}_{t},t))\;\lVert\;q({\mathbf{G}}_{\tau}\,\mid\,{\mathbf{G}}_{0})\right)$
$\displaystyle=\ln\Gamma(\eta\alpha_{t}{\mathbf{G}}_{0})+\ln\Gamma(\eta-\eta\alpha_{t}{\mathbf{G}}_{0})-\ln\Gamma(\eta\alpha_{t}\hat{{\mathbf{G}}}_{0})-\ln\Gamma(\eta-\eta\alpha_{t}\hat{{\mathbf{G}}}_{0})$
(12)
$\displaystyle+\eta\alpha_{t}(\hat{{\mathbf{G}}}_{0}-{\mathbf{G}}_{0})\cdot\left(\psi(\eta\alpha_{t}\hat{{\mathbf{G}}}_{0})-\psi(\eta-\eta\alpha_{t}\hat{{\mathbf{G}}}_{0})\right),$

where $\hat{{\mathbf{G}}}_{0}:=\hat{G}_{\theta}({\mathbf{G}}_{t},t)$.

It is demonstrated in Zhou et al. (2023) that the KL divergence between two
beta distributions can be expressed in the format of a Bregman divergence.
Namely, considering a convex function
$\phi(\alpha,\beta)\overset{\Delta}{=}\ln\mathrm{Beta}(\alpha,\beta)$, where
$\mathrm{Beta}(\alpha,\beta)=\frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}$
is the beta function, the loss term $\mathcal{L}_{\mathrm{sampling}}$ can be
expressed as

$\begin{gathered}\mathcal{L}_{\mathrm{sampling}}(t,{\mathbf{G}}_{0})=\mathbb{E}_{q({\mathbf{G}}_{t})}\mathbb{E}_{q({\mathbf{G}}_{0}\,\mid\,{\mathbf{G}}_{t})}d_{\phi}\left([{\mathbf{a}}_{\mathrm{sampling}},{\mathbf{b}}_{\mathrm{sampling}}],[{\mathbf{a}}^{*}_{\mathrm{sampling}},{\mathbf{b}}^{*}_{\mathrm{sampling}}]\right),\\\
{\mathbf{a}}_{\mathrm{sampling}}=\eta(\alpha_{t-1}-\alpha_{t}){\mathbf{G}}_{0},~{}{\mathbf{b}}_{\mathrm{sampling}}=\eta(1-\alpha_{t-1}{\mathbf{G}}_{0}),\\\
{\mathbf{a}}^{*}_{\mathrm{sampling}}=\eta(\alpha_{t-1}-\alpha_{t})\hat{{\mathbf{G}}}_{0},~{}{\mathbf{b}}^{*}_{\mathrm{sampling}}=\eta(1-\alpha_{t-1}\hat{{\mathbf{G}}}_{0}).\end{gathered}$
(13)

Likewise, we can express the correction loss term
$\mathcal{L}_{\mathrm{correction}}$ as

$\begin{gathered}\mathcal{L}_{\mathrm{correction}}(t,{\mathbf{G}}_{0})=\mathbb{E}_{q({\mathbf{G}}_{t}})\mathbb{E}_{q({\mathbf{G}}_{0}\,\mid\,{\mathbf{G}}_{t})}d_{\phi}\left([{\mathbf{a}}_{\mathrm{correction}},{\mathbf{b}}_{\mathrm{correction}}],[{\mathbf{a}}^{*}_{\mathrm{correction}},{\mathbf{b}}^{*}_{\mathrm{correction}}]\right),\\\
{\mathbf{a}}_{\mathrm{correction}}=\eta\alpha_{t}{\mathbf{G}}_{0},~{}{\mathbf{b}}_{\mathrm{correction}}=\eta(1-\alpha_{t}{\mathbf{G}}_{0}),\\\
{\mathbf{a}}^{*}_{\mathrm{correction}}=\eta\alpha_{t}\hat{{\mathbf{G}}}_{0},~{}{\mathbf{b}}^{*}_{\mathrm{correction}}=\eta(1-\alpha_{t}\hat{{\mathbf{G}}}_{0}).\end{gathered}$
(14)

Here we reference the $d_{\phi}$ notation of Banerjee et al. (2005) to
represent the Bregman divergence. As stated in Lemmas 3-5 of Zhou et al.
(2023), one can apply Proposition 1 of Banerjee et al. (2005) to show that
both $\mathcal{L}_{\mathrm{sampling}}$ and $\mathcal{L}_{\mathrm{correction}}$
yield the same optimal solution that legitimates the usage of
$\hat{{\mathbf{G}}}_{0}$ in the reverse diffusion process.

######  Property 1.

Both $\mathcal{L}_{\mathrm{sampling}}$ and $\mathcal{L}_{\mathrm{correction}}$
are uniquely minimized at

$\hat{{\mathbf{G}}}_{0}=\hat{G}_{\theta}({\mathbf{G}}_{t},t)=\mathbb{E}_{q({\mathbf{G}}_{0}|{\mathbf{G}}_{t})}[{\mathbf{G}}_{0}].$

Algorithm 3 Training, in original domain.

1:Number of timesteps $T=1000$, default concentration parameter $\eta=30$,
predictor $\hat{G}_{\theta}$, default node influence factor $\gamma=0.5$,
input graph batch
$\mathbb{B}=\\{{\mathbf{G}}^{(k)}=({\mathbf{A}}^{(k)},{\mathbf{X}}^{(k)})\\}_{[K]}$,
default learning rate $\lambda=0.002$, optimization steps $M$.

2:(Optional) Assign value to $\eta$ via Equation 16

3:for step $=1$ to $M$ do

4: Initialize $\mathcal{L}_{X}$ and $\mathcal{L}_{A}$ with 0

5: for $k=1$ to $K$ do

6: $t\sim\text{Unif}(1,...,T)$

7:
$\alpha_{t},\alpha_{t-1}\leftarrow\mathrm{schedule}(t),\mathrm{schedule}(t-1)$

8: ${\mathbf{A}}_{0}\leftarrow w_{A}\cdot{\mathbf{A}}^{(k)}+b_{A}$

9: ${\mathbf{X}}_{0}\leftarrow w_{X}\cdot{\mathbf{X}}^{(k)}+b_{X}$

10: ${\mathbf{G}}_{0}\leftarrow({\mathbf{A}}_{0},{\mathbf{X}}_{0})$

11:
${\mathbf{G}}_{t}\sim\text{Beta}(\eta\alpha_{t}{\mathbf{G}}_{0},\eta(1-\alpha_{t}{\mathbf{G}}_{0}))$

12:
${\mathbf{G}}_{in}\leftarrow\frac{{\mathbf{G}}_{t}-\mathbb{E}[{\mathbf{G}}_{t}]}{\sqrt{\mathrm{Var}[{\mathbf{G}}_{t}]}}$

13:
$(\hat{{\mathbf{A}}}_{0}^{\prime},\hat{{\mathbf{X}}}_{0}^{\prime})\leftarrow\hat{{\mathbf{G}}}_{\theta}({\mathbf{G}}_{in},t)$

14: $\hat{{\mathbf{A}}}_{0}=w_{A}\cdot\hat{{\mathbf{A}}}_{0}^{\prime}+b_{A}$

15: $\hat{{\mathbf{X}}}_{0}=w_{X}\cdot\hat{{\mathbf{X}}}_{0}^{\prime}+b_{X}$

16:
$\mathcal{L}_{A}\leftarrow\mathcal{L}_{A}+\mathcal{L}({\mathbf{A}}_{0},\hat{{\mathbf{A}}}_{0},\eta,\alpha_{t},\alpha_{t-1})$

17:
$\mathcal{L}_{X}\leftarrow\mathcal{L}_{X}+\mathcal{L}({\mathbf{X}}_{0},\hat{{\mathbf{X}}}_{0},\eta,\alpha_{t},\alpha_{t-1})$

18: end for

19: $\theta\leftarrow\theta-\frac{\lambda}{K}\
\nabla_{\theta}(\mathcal{L}_{A}+\gamma\mathcal{L}_{X})$

20:end for

Algorithm 4 Training, in logit domain.

1:Number of timesteps $T$, concentration parameter $\eta$, predictor
$\hat{G}_{\theta}$, node influence factor $\gamma$, input graph batch
$\mathbb{B}$, learning rate $\lambda$, optimization steps $M$. Same default
values with Algorithm 3.

2:for step $=1$ to $M$ do

3: Initialize $\mathcal{L}_{X}$ and $\mathcal{L}_{A}$ with 0

4: for $k=1$ to $K$ do

5: $t\sim\text{Unif}(1,...,T)$

6:
$\alpha_{t},\alpha_{t-1}\leftarrow\mathrm{schedule}(t),\mathrm{schedule}(t-1)$

7: ${\mathbf{A}}_{0}\leftarrow w_{A}\cdot{\mathbf{A}}^{(k)}+b_{A}$

8: ${\mathbf{X}}_{0}\leftarrow w_{X}\cdot{\mathbf{X}}^{(k)}+b_{X}$

9: ${\mathbf{G}}_{0}\leftarrow({\mathbf{A}}_{0},{\mathbf{X}}_{0})$

10: ${\mathbf{U}}_{t}\sim\mathrm{Gamma}(\eta\alpha_{t}{\mathbf{G}}_{0},1)$

11: ${\mathbf{V}}_{t}\sim\mathrm{Gamma}(\eta(1-\alpha_{t}{\mathbf{G}}_{0}),1)$

12:
$\mathrm{logit}({\mathbf{G}}_{t})\leftarrow\ln{\mathbf{U}}_{t}-\ln{\mathbf{V}}_{t}$

13:
${\mathbf{G}}_{in}\leftarrow\frac{\mathrm{logit}({\mathbf{G}}_{t})-\mathbb{E}[\mathrm{logit}({\mathbf{G}}_{t})]}{\sqrt{\mathrm{Var}[\mathrm{logit}({\mathbf{G}}_{t})]}}$

14:
$(\hat{{\mathbf{A}}}_{0}^{\prime},\hat{{\mathbf{X}}}_{0}^{\prime})\leftarrow\hat{{\mathbf{G}}}_{\theta}({\mathbf{G}}_{in},t)$

15: $\hat{{\mathbf{A}}}_{0}=w_{A}\cdot\hat{{\mathbf{A}}}_{0}^{\prime}+b_{A}$

16: $\hat{{\mathbf{X}}}_{0}=w_{X}\cdot\hat{{\mathbf{X}}}_{0}^{\prime}+b_{X}$

17:
$\mathcal{L}_{A}\leftarrow\mathcal{L}_{A}+\mathcal{L}({\mathbf{A}}_{0},\hat{{\mathbf{A}}}_{0},\eta,\alpha_{t},\alpha_{t-1})$

18:
$\mathcal{L}_{X}\leftarrow\mathcal{L}_{X}+\mathcal{L}({\mathbf{X}}_{0},\hat{{\mathbf{X}}}_{0},\eta,\alpha_{t},\alpha_{t-1})$

19: end for

20: $\theta\leftarrow\theta-\frac{\lambda}{K}\
\nabla_{\theta}(\mathcal{L}_{A}+\gamma\mathcal{L}_{X})$

21:end for

###  2.4 Exploring the design space of GBD

Many diffusion-based graph generative models offer great flexibility with
technical adjustment to enhance their practical performances. Here we list
four impactful dimensions among the design space of GBD. Namely, data
transformation, concentration modulation, logit-domain computation, and
neural-network precondition. We elaborate each design dimension below and
discuss our choices in these aspects in the appendix.

#### Data transformation.

We convert the raw data $({\mathbf{A}},{\mathbf{X}})$ to ${\mathbf{G}}_{0}$
through linear transformations, _i.e._ ,

${\mathbf{G}}_{0}=({\mathbf{A}}_{0},{\mathbf{X}}_{0}),~{}\text{where}~{}{\mathbf{A}}_{0}=w_{A}\cdot{\mathbf{A}}+b_{A},~{}{\mathbf{X}}_{0}=w_{X}\cdot{\mathbf{X}}+b_{X},$
(15)

with the constraints that $\min(w_{A},b_{A},w_{X},b_{X})>0$ and
$\max(w_{A}+b_{A},w_{X}+b_{X})\leq 1$. This operation not only ensure that all
data values fall within the positive support of beta distributions, avoiding
gradient explosion when optimizing the loss function, but also provide an
effective means to adjust the rate at which diffusion trajectories mix. A
forward diffusion trajectory reaches a state of “mix” when it becomes
indistinguishable to discern the initial value from its counterfactual given
the current value. A suitable mixing rate ensures that the signal-to-noise
ratio (SNR) of the final state in the forward diffusion process approaches
zero, meeting the prerequisite for learning reverse diffusion while preserving
the learnability of graph structural patterns. The scaling parameter provides
a macro control for the mixing rate, with a smaller value contracting the data
range and promoting the arrival of the mixing state.

#### Concentration modulation.

Figure 2: Reverse Process on Graph Edges: Each edge $(u,v)$ undergoes a
reverse process with specific $\eta_{u,v}$ parameters, influenced by
$\text{deg}(u)$ and $\text{deg}(v)$. The colorbar indicates the normalized
degree of nodes in the final graph, with brighter colors (shifting towards
yellow) denoting higher degrees. Nodes in the adjacency matrices shown in the
bottom row are reordered based on decreasing node degree.

Another hyperparameter that offers a more refined adjustment to the mixing
rate is the concentration parameter $\eta$. Higher values of $\eta$ reduce the
variance of the fractional multipliers ${\mathbf{P}}_{t}$ sampled from their
corresponding beta distributions, thus delaying the arrival of the mixing
state. Leveraging this property, we have devised a simple yet effective
modulation strategy to differentiate the mixing time for various graph
substructures.

Specifically, we assign higher $\eta$ values to “important positions” within a
graph, such as edges connecting high-degree nodes or edges redeemed as
significant based on domain knowledge, such as the carbon-carbon bond in
chemical molecules. For instance, when modulating $\eta$ from node degrees,
the exact operation executed upon the $\eta$ values for edge $(u,v)$ and for
the features of node $u$ can be mathematically expressed as

$\eta_{u,v}=g_{A}(\max(\mathrm{deg}(u),\mathrm{deg}(v))),\quad\eta_{u}=g_{X}(\mathrm{deg}(u)).$
(16)

Here we first prepare several levels of $\eta$ values, then utilize two
assignment functions, namely $g_{A}(\cdot)$ and $g_{X}(\cdot)$, to map the
node degrees (or their percentile in the degree population) to one of the
choices of the $\eta$ values. We have observed that this operation indeed
prolongs the presence of these substructures during the forward diffusion
process, which in turn leads to their earlier emergence compared to the rest
of the graph during the reverse process.

We visualize the reverse process from two perspectives in Figure 2. We first
obtain the $\eta_{u,v}$ by degrees retrieved from the training set before
sampling and then generate graph through reverse beta diffusion. From the top
row, we observe that edges linked to nodes with higher degrees (indicated by
brighter colors) appear first, followed by other edges. From the bottom row,
it is evident that edges connected to the first five nodes, which have higher
degrees, are identified first and then progressively in descending order of
degree. Notably, the nodes of the adjacency matrices in the bottom row are
reordered by decreasing node degree of the final graph. Additionally, we can
also find the predicted graph of GBD converges in an early stage to the
correct topology. We attribute the enhanced quality of generated graphs to the
early emergence of these “important substructures,” which potentially enhances
the reliability of generating realistic graph structures. Furthermore, we find
this approach particularly appealing because it allows for the flexible
integration of graph inductive biases within the diffusion model framework.

#### Logit domain computation.

Another noteworthy designing direction lies in the computation domain.
Although the reverse sampling process directly implemented from Equation 5 is
already effective to generate realistic graph data, we observe that migrating
the computation to the logit space further enhances model performance and
accelerates training convergence. One potential explanation is that the logit
transformation amplifies the structural patterns of the graph when all edge
weights are very close to zero at the beginning of the ancestral sampling
process. Equivalent to Equation 5, the logit-domain computation can be
expressed as

$\mathrm{logit}({\mathbf{G}}_{t-1})=\ln\left(e^{\mathrm{logit}({\mathbf{G}}_{t})}+e^{\mathrm{logit}({\mathbf{P}}_{t})}+e^{\mathrm{logit}({\mathbf{G}}_{t})+\mathrm{logit}({\mathbf{P}}_{t})}\right).$
(17)

#### Neural-network precondition.

A drawback of the logit-domain computation is its introduction of variability
to model training, we address this issue by employing neural-network
precondition techniques (Karras et al., 2022). Specifically, precondition
involves standardizing ${\mathbf{G}}_{t}$ before passing them to the
prediction network $\hat{G}_{\theta}(\cdot)$. In other words, we modify
Equation 7 as

$p_{\theta}({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t}):=q({\mathbf{G}}_{t-1}\,\mid\,{\mathbf{G}}_{t},\hat{G}_{\theta}(\tilde{{\mathbf{G}}}_{t},t)),~{}\tilde{{\mathbf{G}}}_{t}=\frac{{\mathbf{G}}_{t}-\mathbb{E}[g_{t}]}{\sqrt{\mathrm{Var}[g_{t}]}}~{}\text{or}~{}\frac{\mathrm{logit}({\mathbf{G}}_{t})-\mathbb{E}[\mathrm{logit}(g_{t})]}{\sqrt{\mathrm{Var}[\mathrm{logit}(g_{t})]}},$
(18)

where $g_{t}$ denotes the elements within ${\mathbf{G}}_{t}$. Based upon the
law of total expectation and the law of total variance, Zhou et al. (2023)
have derived the following attribute of beta diffusion

######  Attribute 1.

Given that
$g_{t}|g_{0}\sim\mathrm{Beta}(\eta\alpha_{t}g_{0},\eta(1-\alpha_{t}g_{0}))$,
one can derive that $\mathbb{E}[g_{t}|g_{0}]=\alpha_{t}g_{0}$ and
$\mathrm{Var}[g_{t}|g_{0}]=\frac{\alpha_{t}g_{0}(1-\alpha_{t}g_{0})}{\eta+1}$.
Representing $\mathbb{E}[g_{0}]$ and $\mathrm{Var}[g_{0}]$ with $\mu$ and
$\sigma^{2}$, we have

$\mathbb{E}[g_{t}]=\alpha_{t}\mu,~{}\mathrm{Var}[g_{t}]=\frac{\alpha_{t}\mu-\alpha_{t}^{2}(\mu^{2}+\sigma^{2})}{\eta+1}+\alpha^{2}_{t}\sigma^{2}.$

Their counterparts in the logit domain are expressed as

$\displaystyle\mathbb{E}[\mathrm{logit}(g_{t})]$
$\displaystyle=\mathbb{E}[\psi(\eta\alpha_{t}g_{0})]-\mathbb{E}[\psi(\eta-\eta\alpha_{t}g_{0})],$
$\displaystyle\mathrm{Var}[\mathrm{logit}(g_{t})]$
$\displaystyle=\mathbb{E}[\psi^{(1)}(\eta\alpha_{t}g_{0})]+\mathbb{E}[\psi^{(1)}(\eta(1-\alpha_{t}g_{0}))]+\mathrm{Var}[\psi(\eta\alpha_{t}g_{0})]+\mathrm{Var}[\psi(\eta(1-\alpha_{t}g_{0}))],$

with $\psi(\cdot)$ and $\psi^{(1)}(\cdot)$ denoting digamma and trigamma
functions.

In addition to Attribute 1, the specific values for $\mathbb{E}[g_{t}]$,
$\mathrm{Var}[g_{t}]$, $\mathbb{E}[\mathrm{logit}(g_{t})]$ and
$\mathrm{Var}[\mathrm{logit}(g_{t})]$ are also reliant on the distribution of
the datum in its initial state. Recall that all variables within
${\mathbf{G}}_{0}$ have been preprocessed using either dummy encoding or CDF
transformation. Consequently, the processed variables follow either a discrete
distribution or a uniform distribution. With this context, if the original
datum follows a discrete distribution, we present the following conclusion.

######  Remark 1.

If $g_{0}$ has two potential outcomes $\\{g_{\min},g_{\max}\\}$ with
$P(g_{0}=g_{\max})=p$, then

$\displaystyle\mathbb{E}[g_{t}]$ $\displaystyle=\alpha_{t}\left(p\cdot
g_{\max}+(1-p)\cdot g_{\min}\right),$ $\displaystyle\mathrm{Var}[g_{t}]$
$\displaystyle=\frac{1}{\eta+1}\left(\mathbb{E}[g_{t}]-\mathbb{E}[g_{t}]^{2}\right)+\frac{\eta}{\eta+1}\left(\alpha_{t}^{2}(p(1-p))(g_{\max}-g_{\min})^{2}\right).$
(19)

The calculation of $\mathbb{E}[\mathrm{logit}(g_{t})]$ and
$\mathrm{Var}[\mathrm{logit}(g_{t})]$ relies on a series of components, namely

$\displaystyle\mathbb{E}[\psi(\eta\alpha_{t}g_{0})]$
$\displaystyle=p\cdot\psi(\eta\alpha_{t}g_{\max})+(1-p)\cdot\psi(\eta\alpha_{t}g_{\min}),$
$\displaystyle\mathbb{E}[\psi(\eta-\eta\alpha_{t}g_{0})]$
$\displaystyle=p\cdot\psi(\eta-\eta\alpha_{t}g_{\max})+(1-p)\cdot\psi(\eta-\eta\alpha_{t}g_{\min}),$
$\displaystyle\mathrm{Var}[\psi(\eta\alpha_{t}g_{0})]$
$\displaystyle=p(1-p)\left(\psi(\eta\alpha_{t}g_{\max})-\psi(\eta\alpha_{t}g_{\min})\right)^{2},$
$\displaystyle\mathrm{Var}[\psi(\eta-\eta\alpha_{t}g_{0})]$
$\displaystyle=p(1-p)\left(\psi(\eta-\eta\alpha_{t}g_{\max})-\psi(\eta-\eta\alpha_{t}g_{\min})\right)^{2},$
$\displaystyle\mathbb{E}[\psi^{(1)}(\eta\alpha_{t}g_{0})]$
$\displaystyle=p\cdot\psi^{(1)}(\eta\alpha_{t}g_{\max})+(1-p)\cdot\psi^{(1)}(\eta\alpha_{t}g_{\min}),$
$\displaystyle\mathbb{E}[\psi^{(1)}(\eta-\eta\alpha_{t}g_{0})]$
$\displaystyle=p\cdot\psi^{(1)}(\eta-\eta\alpha_{t}g_{\max})+(1-p)\cdot\psi^{(1)}(\eta-\eta\alpha_{t}g_{\min}),$
(20)

with which one can easily deduce the expressions of
$\mathbb{E}[\mathrm{logit}(g_{t})]$ and $\mathrm{Var}[\mathrm{logit}(g_{t})]$
following Attribute 1.

Alternatively, if the original datum follows a uniform distribution upon the
support $[g_{\min},g_{\max}]$, then as demonstrated in Zhou et al. (2023), we
have

######  Remark 2.

If $g_{0}$ follows the uniform distribution
$\mathrm{Unif}[g_{\min},g_{\max}]$, then

$\displaystyle\mathbb{E}[g_{t}]$
$\displaystyle=\frac{1}{2}\alpha_{t}(g_{\min}+g_{\max}),$
$\displaystyle\mathrm{Var}[g_{t}]$
$\displaystyle=\frac{1}{\eta+1}\left(\mathbb{E}[g_{t}]-\mathbb{E}[g_{t}]^{2}\right)+\frac{\eta}{12(\eta+1)}\left(\alpha_{t}^{2}(g_{\max}-g_{\min})^{2}\right).$
(21)

We denote by $K$ the number of sub-intervals used in the numerical integration
based on the Trapezoidal rule. Similar to Remark 1, on the logit domain, we
list out the expressions for the components as

$\displaystyle\mathbb{E}[\psi(\eta\alpha_{t}g_{0})]$
$\displaystyle=\frac{1}{\eta\alpha_{t}(g_{\max}-g_{\min})}\left(\ln\Gamma(\eta\alpha_{t}g_{\max})-\ln\Gamma(\eta\alpha_{t}g_{\min})\right),$
$\displaystyle\mathbb{E}[\psi(\eta-\eta\alpha_{t}g_{0})]$
$\displaystyle=\frac{1}{\eta\alpha_{t}(g_{\max}-g_{\min})}\left(\ln\Gamma(\eta-\eta\alpha_{t}g_{\min})-\ln\Gamma(\eta-\eta\alpha_{t}g_{\max})\right),$
$\displaystyle\mathrm{Var}[\psi(\eta\alpha_{t}g_{0})]$
$\displaystyle\approx\max\left(\frac{1}{K}\sum_{i=0}^{K}\frac{\psi^{2}\left(\eta\alpha_{t}\left(g_{\min}+\frac{i}{K}(g_{\max}-g_{\min})\right)\right)}{2^{\delta(i=0)+\delta(i=K)}}-\mathbb{E}[\psi(\eta\alpha_{t}g_{0})]^{2},0\right),$
$\displaystyle\mathrm{Var}[\psi(\eta-\eta\alpha_{t}g_{0})]$
$\displaystyle\approx\max\left(\frac{1}{K}\sum_{i=0}^{K}\frac{\psi^{2}\left(\eta-\eta\alpha_{t}\left(g_{\min}+\frac{i}{K}(g_{\max}-g_{\min})\right)\right)}{2^{\delta(i=0)+\delta(i=K)}}-\mathbb{E}[\psi(\eta-\eta\alpha_{t}g_{0})]^{2},0\right),$
$\displaystyle\mathbb{E}[\psi^{(1)}(\eta\alpha_{t}g_{0})]$
$\displaystyle=\frac{1}{\eta\alpha_{t}(g_{\max}-g_{\min})}\left(\psi(\eta\alpha_{t}g_{\max})-\psi(\eta\alpha_{t}g_{\min})\right),$
$\displaystyle\mathbb{E}[\psi^{(1)}(\eta-\eta\alpha_{t}g_{0})]$
$\displaystyle=\frac{1}{\eta\alpha_{t}(g_{\max}-g_{\min})}\left(\psi(\eta-\eta\alpha_{t}g_{\min})-\psi(\eta-\eta\alpha_{t}g_{\max})\right).$
(22)

Utilizing Attribute 1, one can derive the mathematical expressions that we use
to calculate $\mathbb{E}[\mathrm{logit}(g_{t})]$ and
$\mathrm{Var}[\mathrm{logit}(g_{t})]$.

##  3 Related Work

#### Graph generative models.

Early attempts at modeling graph distributions trace back to the Erdős–Rényi
random graph model (ERDdS and R&wi, 1959; Erdős et al., 1960), from which a
plethora of graph generative models have emerged. These models employ diverse
approaches to establish the data generative process and devise optimization
objectives, which in turn have significantly expanded the flexibility in
modeling the distribution of graph data. Stochastic blockmodels (Holland et
al., 1983; Lee and Wilkinson, 2019), more advanced latent variable models
(Airoldi et al., 2009; Zhou, 2015; Caron and Fox, 2017), and their
variational-autoencoder-based successors (Kipf and Welling, 2016; Hasanzadeh
et al., 2019; Mehta et al., 2019; He et al., 2022) assume that edges are
formed through independent pairwise node interactions, and thus factorize the
probability of the graph adjacency matrix into the dot product of factor
representations of nodes. Sequential models (You et al., 2018; Wang et al.,
2018; Jin et al., 2018; Han et al., 2023) adopt a similar concept of node
interactions but correlate these interactions by organizing them into a series
of connection events. Additionally, some models treat the graph adjacency
matrix as a parameterized random matrix and generate it by mapping a random
vector through a feed-forward neural network (Simonovsky and Komodakis, 2018;
De Cao and Kipf, 2018). In terms of optimization targets, many utilize log-
likelihood-based objectives such as negative log-likelihood (Liu et al., 2019)
or evidence lower bound objectives (Kipf and Welling, 2016), while others
employ generative adversarial losses (Wang et al., 2018) or reinforcement
learning losses (De Cao and Kipf, 2018). Diffusion-based graph generative
models (Jo et al., 2022; Haefeli et al., 2022; Vignac et al., 2023; Jo et al.,
2023; Chen et al., 2023; Cho et al., 2023; Kong et al., 2023), including this
work, feature a unique data generation process compared to previous models.
They map the observed graph structures and node features to a latent space
through a stochastic diffusion process, whose reverse process can be learned
by optimizing a variational lower bound (Vignac et al., 2023) or numerically
solving a reverse stochastic differential equation (Jo et al., 2022).

#### Diffusion models.

The stochastic diffusion process is introduced by Sohl-Dickstein et al. (2015)
for deep unsupervised learning, and its foundational connection with deep
generative models is laid down by denoising diffusion probabilistic model
(DDPM) (Ho et al., 2020). DDPM maps a data sample to the latent space via a
Markov process that gradually applies noise to the original sample, and learns
a reverse process to reproduce the sample in finite steps. The optimization
and sampling processes in DDPM can be interpreted through the lens of
variational inference (Sohl-Dickstein et al., 2015; Ho et al., 2020) or can be
formulated as score matching with Langevin dynamics (Song et al., 2021; Song
and Ermon, 2019). Both approaches are focused on diffusion processes that
define the transition between normally distributed variables, which are proven
effective for generating natural images. As the scope of generative tasks
expands to discrete domains like text, diffusion models transitioning between
discrete states emerge (Austin et al., 2021), which demonstrates that the
choice of probabilistic distribution for modeling each noise state could
significantly impact the learning task. This conclusion is also validated in
the application of graph generation (Haefeli et al., 2022; Vignac et al.,
2023). Further studies (Chen and Zhou, 2023; Zhou et al., 2023) are conducted
to improve diffusion models by introducing novel diffusion processes based on
probabilistic distributions that better capture the intrinsic characteristics
of the generation target. Among these, the beta diffusion of Zhou et al.
(2023) is chosen as the foundation of our method, due to the beta
distribution’s proficiency in capturing sparsity and long-tailed
characteristics in range-bounded data. These traits are commonly observed in
real-world graphs (Barabási et al., 2000; Ciotti et al., 2015; Liang et al.,
2023; Wang et al., 2023).

##  4 Experiments

We validated GBD on both molecular and non-molecular benchmarks, demonstrating
its ability to generate valid graphs using various evaluation metrics.

###  4.1 Generic graph generation

To verify that GBD can generate graphs accurately reflecting the underlying
data distribution, we first evaluate our method on a range of generic
generation tasks across various datasets.

#### Datasets and metrics.

We consider three synthetic and real datasets of varying size and connectivity
used as benchmarks in previous works: Ego-small consists of 200 small real
sub-graphs from the Citeseer network dataset with $4\leq N\leq 18$, where $N$
denotes the number of nodes. Community-small consists of 100 randomly
generated synthetic graphs with $12\leq N\leq 20$. Grid consists of randomly
generated 100 standard 2D grid graphs with $100\leq N\leq 400$.

For a fair comparison, we follow the experimental and evaluation setting of Jo
et al. (2022, 2023) with the same train/test split. We adopt maximum mean
discrepancy (MMD) (Gretton et al., 2012) as our evaluation metric to compare
three graph property distributions between the test graphs and the same number
of generated graphs: degree (Deg.), clustering coefficient (Clus.), count of
orbits with 4 nodes (Orbit), and their average score (Avg.). Further details
about these metrics can be found in Appendix A.

#### Baselines.

We compare GBD against the following autoregressive and one-shot graph
generation methods: DeepGMG (Li et al., 2018), GraphRNN (You et al., 2018),
GraphAF (Shi et al., 2020), GraphDF (Luo et al., 2021), GraphVAE (Simonovsky
and Komodakis, 2018), and GNF (Liu et al., 2019). We also compare GBD against
several state-of-the-art diffusion-based graph generative models: EDP-GNN (Niu
et al., 2020a), a score-based model for adjacency matrix, GDSS (Jo et al.,
2022) and ConGress (Vignac et al., 2023), continuous diffusion models, DiGress
(Vignac et al., 2023), a discrete diffusion model, and Wave-GD (Cho et al.,
2023), a wavelet-based diffusion model. We describe implementation details in
Appendix A.

#### Results.

As shown in Table 1, the proposed GBD achieves superior or comparable
performance to the MMD of the sampled graphs from the training set. Compared
to previous diffusion-based methods, GBD outperforms them on 7/9 MMD metrics
and achieves the best average results on each dataset. In particular, GBD
surpasses DiGress on all MMD metrics, demonstrating that our model is capable
of modeling discrete graph data and even achieves better results. We attribute
this to our model’s superior ability to capture the sparsity of the graph data
distribution, which makes GBD distinctive. For the larger graph dataset Grid,
GBD obtains a superior average score and other competitive MMDs compared to
Wave-GD, demonstrating its potential in generating larger graphs.

#### Evaluation with larger sample size.

For Ego-small and Community-small, it is worth noting that for most evaluation
metrics, the MMDs of the graphs sampled from the training set still have large
standard deviations, likely due to the small number of nodes in the graph and
the insufficient size of the sampled graphs. Therefore, it is necessary to
assess the quality of generated samples more definitively using a larger
number of generated graphs compared to the test data. Similar to the previous
works (Cho et al., 2023; Jo et al., 2022; Liu et al., 2019), we sampled 1024
graphs for each smaller dataset and evaluated the MMD metrics with their means
and standard deviations reported in Table 2. We observe that our proposed GBD
outperforms previous continuous and discrete diffusion models on both smaller
datasets. Furthermore, GBD significantly surpasses the wavelet-based diffusion
model (Wave-GD) by a wide margin on the Community-small dataset, as evidenced
by both means and standard deviations. Specifically, GBD achieves 85.0%,
90.5%, and 40.0% improvements over Wave-GD in the MMDs means of Degree,
Cluster, and Orbit, respectively, indicating that our model is capable of
generating smaller graphs that are closer to the data distribution with better
stability.

Table 1: Generic graph generation results.

| Ego-small | Community-small | Grid
---|---|---|---
Method | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$ | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$ | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$
DeepGMG | 0.040 | 0.100 | 0.020 | 0.053 | 0.220 | 0.950 | 0.400 | 0.523 | - | - | - | -
GraphRNN | 0.090 | 0.220 | 0.003 | 0.104 | 0.080 | 0.120 | 0.040 | 0.080 | 0.064 | 0.043 | 0.021 | 0.043
GraphAF | 0.030 | 0.110 | 0.001 | 0.047 | 0.180 | 0.200 | 0.020 | 0.133 | - | - | - | -
GraphDF | 0.040 | 0.130 | 0.010 | 0.060 | 0.060 | 0.120 | 0.030 | 0.070 | - | - | - | -
GraphVAE | 0.130 | 0.170 | 0.050 | 0.117 | 0.350 | 0.980 | 0.540 | 0.623 | 1.619 | 0.0 | 0.919 | 0.846
GNF | 0.030 | 0.100 | 0.001 | 0.044 | 0.200 | 0.200 | 0.110 | 0.170 | - | - | - | -
EDP-GNN | 0.052 | 0.093 | 0.007 | 0.051 | 0.053 | 0.144 | 0.026 | 0.074 | 0.455 | 0.238 | 0.328 | 0.340
GDSS | 0.021 | 0.024 | 0.007 | 0.017 | 0.045 | 0.086 | 0.007 | 0.046 | 0.111 | 0.005 | 0.070 | 0.062
ConGress∗ | 0.037 | 0.064 | 0.017 | 0.039 | 0.020 | 0.076 | 0.006 | 0.034 |  |  |  |
DiGress | 0.017 | 0.021 | 0.010 | 0.016 | 0.028 | 0.115 | 0.009 | 0.050 | - | - | - | -
Wave-GD | 0.012 | 0.010 | 0.005 | 0.009 | 0.007 | 0.058 | 0.002 | 0.022 | 0.144 | 0.004 | 0.021 | 0.056
GBD | 0.011 | 0.014 | 0.002 | 0.009 | 0.002 | 0.060 | 0.002 | 0.021 | 0.045 | 0.011 | 0.040 | 0.032
($\pm$0.008) | ($\pm$0.013) | ($\pm$0.004) | - | ($\pm$0.003) | ($\pm$0.004) | ($\pm$0.003) | - | ($\pm$0.004) | ($\pm$0.002) | ($\pm$0.014) | -

Table 2: Generic graph generation results with larger sample size.

| Ego-small | Community-small
---|---|---
Method | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$ | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$
GraphRNN | 0.040 | 0.050 | 0.060 | 0.050 | 0.030 | 0.010 | 0.010 | 0.017
GNF | 0.010 | 0.030 | 0.001 | 0.014 | 0.120 | 0.150 | 0.020 | 0.097
EDP-GNN | 0.010 | 0.025 | 0.003 | 0.013 | 0.006 | 0.127 | 0.018 | 0.050
GDSS | 0.023 | 0.020 | 0.005 | 0.016 | 0.029 | 0.068 | 0.004 | 0.034
ConGress∗ | 0.030 | 0.050 | 0.008 | 0.030 | 0.004 | 0.047 | 0.001 | 0.017
($\pm$ 0.001) | ($\pm$ 0.003) | ($\pm$ 0.001) | - | ($\pm$ 0.000) | ($\pm$ 0.000) | ($\pm$ 0.000) | -
DiGress∗ | 0.009 | 0.031 | 0.003 | 0.014 | 0.003 | 0.009 | 0.001 | 0.004
($\pm$ 0.000) | ($\pm$ 0.002) | ($\pm$ 0.000) | - | ($\pm$ 0.000) | ($\pm$ 0.001) | ($\pm$ 0.000) | -
Wave-GD | 0.010 | 0.018 | 0.005 | 0.011 | 0.016 | 0.077 | 0.001 | 0.031
($\pm$ 0.001) | ($\pm$ 0.003) | ($\pm$ 0.002) | - | ($\pm$ 0.000) | ($\pm$ 0.006) | ($\pm$ 0.002) | -
GBD | 0.007 | 0.011 | 0.003 | 0.010 | 0.002 | 0.007 | 0.001 | 0.003
($\pm$ 0.000) | ($\pm$ 0.001) | ($\pm$ 0.000) | - | ($\pm$ 0.000) | ($\pm$ 0.001) | ($\pm$ 0.000) | -

###  4.2 Molecule Generation

We validate GBD on 2D molecule generation tasks for attributed graphs,
demonstrating its capability to model graph structure with both node and edge
attributes.

#### Datasets and Metrics

We consider two widely-used molecule datasets as benchmarks in Jo et al.
(2022): QM9 (Ramakrishnan et al., 2014), which consists of 133,885 molecules
with $N\leq 9$ nodes from 4 different node types, and ZINC250k (Irwin et al.,
2012), which consists of 249,455 molecules with $N\leq 38$ nodes from 9
different node types. Molecules in both datasets have 3 edge types, namely
single bond, double bond, and triple bond.

Following the evaluation setting of Jo et al. (2022), we generated 10,000
molecules for each dataset and evaluate them with four metrics: the ratio of
valid molecules without correction (Val.), Fréchet ChemNet Distance (FCD),
Neighborhood subgraph pairwise distance kernel NSPDK, and Scaffold similarity
(Scaf.).

#### Baselines

We compare GBD against the following autoregressive and one-shot graph
generation methods: MoFlow (Zang and Wang, 2020), GraphAF (Shi et al., 2020),
GraphDF (Luo et al., 2021), and several state-of-the-art diffusion-based graph
generative models discussed previously: EDP-GNN (Niu et al., 2020a), GDSS (Jo
et al., 2022) and ConGress (Vignac et al., 2023), DiGress (Vignac et al.,
2023), and DruM (Jo et al., 2023). We describe the implementation details in
Appendix A.

#### Results

As shown in Table 3, we observe that our GBD outperforms most previous
diffusion-based models and is competitive with the current state-of-the-art
Gaussian-based diffusion model, DruM. In particular, compared to the basic
continuous diffusion model, GBD significantly outperforms it
(GDSS+Transformer) under the same GraphTransformer architecture. Additionally,
we observe that our proposed beta-based diffusion model is superior to the
discrete diffusion model on both 2D molecule datasets, demonstrating that the
beta-based diffusion model is also capable of modeling complex structures of
attributed graphs (even more effectively when comparing GBD to DiGress). We
attribute this to the excellent modeling ability of beta-based diffusion model
for sparse and long-tailed data distributions.

Table 3: 2D molecule generation results

| QM9 ($|V|\leq 9$) | ZINC250K
---|---|---
Method | Valid (%) $\uparrow$ | FCD $\downarrow$ | NSPDK $\downarrow$ | Scaf. $\downarrow$ | Valid(%) $\uparrow$ | FCD $\downarrow$ | NSPDK $\downarrow$ | Scaf. $\downarrow$
MoFlow | 91.36 | 4.467 | 0.0169 | 0.1447 | 63.11 | 20.931 | 0.0455 | 0.0133
GraphAF | 74.43 | 5.625 | 0.0207 | 0.3046 | 68.47 | 16.023 | 0.0442 | 0.0672
GraphDF | 93.88 | 10.928 | 0.0636 | 0.0978 | 90.61 | 33.546 | 0.1770 | 0.0000
EDP-GNN | 47.52 | 2.680 | 0.0046 | 0.3270 | 82.97 | 16.737 | 0.0485 |
GDSS | 95.72 | 2.900 | 0.0033 | 0.6983 | 97.01 | 14.656 | 0.0195 | 0.0467
GDSS+Transformer | 99.68 | 0.737 | 0.0024 | 0.9129 | 96.04 | 5.556 | 0.0326 | 0.3205
DiGress | 98.19 | 0.095 | 0.0003 | 0.9353 | 94.99 | 3.482 | 0.0021 | 0.4163
DruM | 99.69 | 0.108 | 0.0002 | 0.9449 | 98.65 | 2.257 | 0.0015 | 0.5299
GBD | 99.88 | 0.093 | 0.0002 | 0.9510 | 97.87 | 2.248 | 0.0018 | 0.5042

###  4.3 Ablation studies

With all other hyperparameter choices kept constant, we vary the options
regarding computation domain and the application of preconditioning, and
summarize the outcome of model performance in Table 4. The combination of
adopting logit domain computation without using preconditioning can sometimes
increase the challenge in model convergence, and therefore, it is not
recommended. The listed results on Ego-small and Community-small demonstrate
that both techniques are in general beneficial for achieving better model
performance, and the effect of preconditioning is more evident when the
computation is perfomed in the logit domain.

Table 4: The effect of practicing logit domain computation and preconditioning

|  | Ego-small | Community-small
---|---|---|---
logit domain | preconditioning | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$ | Deg. $\downarrow$ | Clus. $\downarrow$ | Orbit. $\downarrow$ | Avg. $\downarrow$
- | - | 0.015 | 0.018 | 0.004 | 0.012 | 0.010 | 0.076 | 0.004 | 0.030
- | ✓ | 0.013 | 0.017 | 0.002 | 0.011 | 0.004 | 0.044 | 0.007 | 0.018
✓ | ✓ | 0.011 | 0.014 | 0.002 | 0.009 | 0.002 | 0.060 | 0.002 | 0.021

###  4.4 Visualization

We provide the visualization of the generative process and generated graphs of
GBD in Appendix B. For generative process with general datasets shown in
Appendix B.1, we follow the implementation described in Section 2.4 and the
nodes in all adjacency matrices are reordered by decreasing node degree.
Apparently, we can find that edges associated with nodes with large degree
will be the first to be identified, and then spread in decreasing order of
degree on both datasets. It’s worth noting that the reverse beta diffusion can
converge rapidly, leading to generated graphs with correct topology at an
early stage. This demonstrates that our proposed GBD can further explore the
potential benefits of beta diffusion, resulting in valid graphs with stability
and high quality. For generated molecule graphs shown in Appendix B.1, we can
observe that GBD can successfully generate valid and high-quality 2D
molecules, verifying its ability to model attributed graphs.

##  5 Conclusion, Limitations and Broader Impact

We introduce graph beta diffusion (GBD), a novel graph generation framework
developed upon beta diffusion. We demonstrate that the utilization of beta
distribution to define the diffusion process is beneficial for modeling the
distribution of graph data, and outline four crucial designing elements—data
transformation, concentration modulation, logit-domain computation, and
neural-network precondition—that that consistently enhance model performance.

With these contributions achieved, we identify several areas for potential
improvement. First, while the beta distribution can adeptly model various data
distributions within the range of $[0,1]$, using it to construct the diffusion
model necessitates careful selection of scaling and shifting parameters to
ensure model convergence. This requirement can complicate the transfer of
experience between different tasks. Second, unlike discrete diffusion
processes, the beta diffusion process does not naturally generate discrete
intermediate adjacency matrices for computing graph statistics. This
necessitates a quantization strategy if one aims to incorporate statistics
from these intermediates when predicting the graph at the initial state.
Thirdly, diffusion-based graph generative models, including GBD, currently
rely on a reverse diffusion process that takes hundreds to thousands of
iterative refinement steps to generate a single sample. Recent advancements in
score-based distillation techniques, originally developed for image diffusion
models, could be adapted to distill the graph teacher model (Luo et al., 2023;
Zhou et al., 2024). Such an adaptation has the potential to significantly
accelerate the graph generation process while maintaining or even improving
performance. We plan to explore these possibilities in future studies.

Finally, we explore the potential impact of GBD. Since much real-world data
can be structured as graphs, an effective tool for generating realistic graphs
could significantly benefit researchers in the natural and social sciences,
enabling the economical creation of high-quality simulated data. However,
there is a concern: if the generated content is misused for fraudulent
activities, distinguishing it from authentic data could become increasingly
challenging for recipients.

## References

  * Abbe [2018] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  _Journal of Machine Learning Research_ , 18(177):1–86, 2018.
  * Airoldi et al. [2009] Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing.  Mixed membership stochastic blockmodels.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 21, 2009.
  * Austin et al. [2021] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg.  Structured denoising diffusion models in discrete state-spaces.  _Advances in Neural Information Processing Systems_ , 34:17981–17993, 2021.
  * Avdeyev et al. [2023] Pavel Avdeyev, Chenlai Shi, Yuhao Tan, Kseniia Dudnyk, and Jian Zhou.  Dirichlet diffusion score model for biological sequence generation.  In _Proceedings of the Fortieth International Conference on Machine Learning_ , Proceedings of Machine Learning Research. PMLR, 2023.
  * Banerjee et al. [2005] Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty.  Clustering with Bregman divergences.  _Journal of machine learning research_ , 6(10), 2005.
  * Barabási et al. [2000] Albert-László Barabási, Réka Albert, and Hawoong Jeong.  Scale-free characteristics of random networks: the topology of the world-wide web.  _Physica A: statistical mechanics and its applications_ , 281(1-4):69–77, 2000.
  * Bemis and Murcko [1996] Guy W Bemis and Mark A Murcko.  The properties of known drugs. 1. molecular frameworks.  _Journal of medicinal chemistry_ , 39(15):2887–2893, 1996.
  * Bongini et al. [2021] Pietro Bongini, Monica Bianchini, and Franco Scarselli.  Molecular generative graph neural networks for drug discovery.  _Neurocomputing_ , 450:242–252, 2021.
  * Caron and Fox [2017] François Caron and Emily B Fox.  Sparse graphs using exchangeable random measures.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 79(5):1295–1366, 2017.
  * Chen and Zhou [2023] Tianqi Chen and Mingyuan Zhou.  Learning to jump: Thinning and thickening latent counts for generative modeling.  In _International Conference on Machine Learning_ , pages 5367–5382. PMLR, 2023.
  * Chen et al. [2023] Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu.  Efficient and degree-guided graph generation via discrete diffusion modeling.  In _International Conference on Machine Learning_. PMLR, 2023.
  * Cho et al. [2023] Hyuna Cho, Minjae Jeong, Sooyeon Jeon, Sungsoo Ahn, and Won Hwa Kim.  Multi-resolution spectral coherence for graph generation with score-based diffusion.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Ciotti et al. [2015] Valerio Ciotti, Ginestra Bianconi, Andrea Capocci, Francesca Colaiori, and Pietro Panzarasa.  Degree correlations in signed social networks.  _Physica A: Statistical Mechanics and its Applications_ , 422:25–39, 2015.
  * Conti et al. [2011] Marco Conti, Andrea Passarella, and Fabio Pezzoni.  A model for the generation of social network graphs.  In _2011 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks_ , pages 1–6. IEEE, 2011.
  * De Cao and Kipf [2018] Nicola De Cao and Thomas Kipf.  Molgan: An implicit generative model for small molecular graphs.  _arXiv preprint arXiv:1805.11973_ , 2018.
  * Dwivedi and Bresson [2020a] Vijay Prakash Dwivedi and Xavier Bresson.  A generalization of transformer networks to graphs.  _arXiv preprint arXiv:2012.09699_ , 2020a.
  * Dwivedi and Bresson [2020b] Vijay Prakash Dwivedi and Xavier Bresson.  A generalization of transformer networks to graphs.  _arXiv preprint arXiv:2012.09699_ , 2020b.
  * ERDdS and R&wi [1959] P ERDdS and A R&wi.  On random graphs i.  _Publ. math. debrecen_ , 6(290-297):18, 1959.
  * Erdős et al. [1960] Paul Erdős, Alfréd Rényi, et al.  On the evolution of random graphs.  _Publ. math. inst. hung. acad. sci_ , 5(1):17–60, 1960.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _The Journal of Machine Learning Research_ , 13(1):723–773, 2012.
  * Guo et al. [2024] Zhiye Guo, Jian Liu, Yanli Wang, Mengrui Chen, Duolin Wang, Dong Xu, and Jianlin Cheng.  Diffusion models in bioinformatics and computational biology.  _Nature reviews bioengineering_ , 2(2):136–154, 2024.
  * Haefeli et al. [2022] Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer.  Diffusion models for graphs benefit from discrete state spaces.  In _The First Learning on Graphs Conference_ , 2022.
  * Han et al. [2023] Xu Han, Xiaohui Chen, Francisco JR Ruiz, and Li-Ping Liu.  Fitting autoregressive graph generative models through maximum likelihood estimation.  _Journal of Machine Learning Research_ , 24(97):1–30, 2023.
  * Hasanzadeh et al. [2019] Arman Hasanzadeh, Ehsan Hajiramezanali, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian.  Semi-implicit graph variational auto-encoders.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 32, pages 10711–10722, 2019.
  * He et al. [2022] Yilin He, Chaojie Wang, Hao Zhang, Bo Chen, and Mingyuan Zhou.  A variational edge partition model for supervised graph representation learning.  _Advances in Neural Information Processing Systems_ , 35:12339–12351, 2022.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ , 33:6840–6851, 2020.
  * Holland et al. [1983] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.  Stochastic blockmodels: First steps.  _Social networks_ , 5(2):109–137, 1983.
  * Huang et al. [2022] Han Huang, Leilei Sun, Bowen Du, and Weifeng Lv.  Conditional diffusion based on discrete graph structures for molecular graph generation.  In _NeurIPS 2022 Workshop on Score-Based Methods_ , 2022.
  * Irwin et al. [2012] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman.  Zinc: a free tool to discover chemistry for biology.  _Journal of chemical information and modeling_ , 52(7):1757–1768, 2012.
  * Jin et al. [2018] Wengong Jin, Regina Barzilay, and Tommi Jaakkola.  Junction tree variational autoencoder for molecular graph generation.  In _International conference on machine learning_ , pages 2323–2332. PMLR, 2018.
  * Jo et al. [2022] Jaehyeong Jo, Seul Lee, and Sung Ju Hwang.  Score-based generative modeling of graphs via the system of stochastic differential equations.  In _International Conference on Machine Learning_ , pages 10362–10383. PMLR, 2022.
  * Jo et al. [2023] Jaehyeong Jo, Dongki Kim, and Sung Ju Hwang.  Graph generation with diffusion mixture.  _arXiv preprint arXiv:2302.03596_ , 2023.
  * Karras et al. [2022] Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine.  Elucidating the design space of diffusion-based generative models.  _Advances in Neural Information Processing Systems_ , 35:26565–26577, 2022.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016.
  * Kong et al. [2023] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang.  Autoregressive diffusion model for graph generation.  In _International Conference on Machine Learning_ , pages 17391–17408. PMLR, 2023.
  * Landrum et al. [2006] Greg Landrum et al.  Rdkit: Open-source cheminformatics, 2006.
  * Lee and Wilkinson [2019] Clement Lee and Darren J Wilkinson.  A review of stochastic block models and extensions for graph clustering.  _Applied Network Science_ , 4(1):1–50, 2019.
  * Li and Yamanishi [2024] Chen Li and Yoshihiro Yamanishi.  Tengan: Pure transformer encoders make an efficient discrete gan for de novo molecular generation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 361–369. PMLR, 2024.
  * Li et al. [2018] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia.  Learning deep generative models of graphs.  In _International conference on machine learning_. PMLR, 2018.
  * Liang et al. [2023] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, Yuan Qi, and Jieping Ye.  Tackling long-tailed distribution issue in graph neural networks via normalization.  _IEEE Transactions on Knowledge and Data Engineering_ , 2023.
  * Liu et al. [2019] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky.  Graph normalizing flows.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Liu et al. [2018] Qi Liu, Miltiadis Allamanis, Marc Brockschmidt, and Alexander Gaunt.  Constrained graph variational autoencoders for molecule design.  _Advances in neural information processing systems_ , 31, 2018.
  * Luo et al. [2023] Weijian Luo, Tianyang Hu, Shifeng Zhang, Jiacheng Sun, Zhenguo Li, and Zhihua Zhang.  Diff-Instruct: A universal approach for transferring knowledge from pre-trained diffusion models.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=MLIs5iRq4w.
  * Luo et al. [2021] Youzhi Luo, Keqiang Yan, and Shuiwang Ji.  Graphdf: A discrete flow model for molecular graph generation.  In _International conference on machine learning_ , pages 7192–7203. PMLR, 2021.
  * Martinkus et al. [2022] Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer.  Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators.  In _International Conference on Machine Learning_ , pages 15159–15179. PMLR, 2022.
  * Mehta et al. [2019] Nikhil Mehta, Lawrence Carin, and Piyush Rai.  Stochastic blockmodels meet graph neural networks.  In _International Conference on Machine Learning (ICML)_ , pages 4466–4474, 2019.
  * Newman et al. [2002] Mark EJ Newman, Duncan J Watts, and Steven H Strogatz.  Random graph models of social networks.  _Proceedings of the national academy of sciences_ , 99(suppl_1):2566–2572, 2002.
  * Niu et al. [2020a] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon.  Permutation invariant graph generation via score-based generative modeling.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 4474–4484. PMLR, 26–28 Aug 2020a.
  * Niu et al. [2020b] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon.  Permutation invariant graph generation via score-based generative modeling.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4474–4484. PMLR, 2020b.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32, 2019.
  * Ramakrishnan et al. [2014] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld.  Quantum chemistry structures and properties of 134 kilo molecules.  _Scientific data_ , 1(1):1–7, 2014.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Shi et al. [2020] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang.  Graphaf: a flow-based autoregressive model for molecular graph generation.  In _International Conference on Learning Representations_ , 2020.
  * Shirzadian et al. [2023] Pouyan Shirzadian, Blessy Antony, Akshaykumar G Gattani, Nure Tasnina, and Lenwood S Heath.  A time evolving online social network generation algorithm.  _Scientific Reports_ , 13(1):2395, 2023.
  * Simonovsky and Komodakis [2018] Martin Simonovsky and Nikos Komodakis.  Graphvae: Towards generation of small graphs using variational autoencoders.  In _Artificial Neural Networks and Machine Learning–ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27_ , pages 412–422. Springer, 2018.
  * Sohl-Dickstein et al. [2015] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In _International conference on machine learning_ , pages 2256–2265. PMLR, 2015.
  * Song and Ermon [2019] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  _Advances in neural information processing systems_ , 32, 2019.
  * Song et al. [2021] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-based generative modeling through stochastic differential equations.  In _International Conference on Learning Representations_ , 2021.
  * Vignac et al. [2023] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard.  Digress: Discrete denoising diffusion for graph generation.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Wang et al. [2023] Haohui Wang, Baoyu Jing, Kaize Ding, Yada Zhu, Liqing Zhang, and Dawei Zhou.  Characterizing long-tail categories on graphs.  _arXiv preprint arXiv:2305.09938_ , 2023.
  * Wang et al. [2018] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo.  Graphgan: Graph representation learning with generative adversarial nets.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32, 2018.
  * You et al. [2018] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec.  Graphrnn: Generating realistic graphs with deep auto-regressive models.  In _International conference on machine learning_ , pages 5708–5717. PMLR, 2018.
  * Zang and Wang [2020] Chengxi Zang and Fei Wang.  Moflow: an invertible flow model for generating molecular graphs.  In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 617–626, 2020.
  * Zhou [2015] Mingyuan Zhou.  Infinite edge partition models for overlapping community detection and link prediction.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , volume 38 of _Proceedings of Machine Learning Research_ , pages 1135–1143, 2015.
  * Zhou et al. [2023] Mingyuan Zhou, Tianqi Chen, Zhendong Wang, and Huangjie Zheng.  Beta diffusion.  In _NeurIPS 2023: Neural Information Processing Systems_ , 2023.
  * Zhou et al. [2024] Mingyuan Zhou, Huangjie Zheng, Zhendong Wang, Mingzhang Yin, and Hai Huang.  Score identity distillation: Exponentially fast distillation of pretrained diffusion models for one-step generation.  In _International Conference on Machine Learning_ , 2024.

##  Appendix A Experimental Details

###  A.1 General graph generation

#### Datasets

We evaluated our model using three synthetic and real datasets of varying size
and connectivity, previously used as benchmarks in the literature [Cho et al.,
2023, Jo et al., 2022]: Ego-small [Sen et al., 2008] consists of 200 small
real sub-graphs from the Citeseer network dataset with $4\leq N\leq 18$.
Community-small consists of 100 randomly generated synthetic graphs with
$12\leq N\leq 20$, where the graphs are constructed by two equal-sized
communities, each of which is generated by the Erdös–Rényi model [Erdős et
al., 1960], with $p=0.7$ and $0.05N$ inter-community edges are added with
uniform probability as in previous works [Jo et al., 2022, Niu et al., 2020b].
Grid consists of randomly generated 100 standard 2D grid graphs with $100\leq
N\leq 400$ and the maximum number of edges per node is 4 since all nodes are
arranged in a regular lattice.

#### Evaluation metrics

For a fair comparison, we follow the experimental and evaluation settings of
Jo et al. [2022, 2023], using the same train/test split, where 80% of the data
is used as the training set and the remaining 20% as the test set. We adopt
maximum mean discrepancy (MMD) as our evaluation metric to compare three graph
property distributions between test graphs and the same number of generated
graphs: degree (Deg.), clustering coefficient (Clus.), count of orbits with 4
nodes (Orbit) and their average score (Avg.). Note that we use the Gaussian
Earth Mover’s Distance (EMD) kernel to compute the MMDs following the method
used in previous work [Jo et al., 2022, Cho et al., 2023].

#### Implementation details

We follow the evaluation setting of Jo et al. [2022], Cho et al. [2023] to
generate graphs of the same size as the test data in each run and we report
the mean and standard deviation obtained from 3 independent runs for each
dataset. We report the baseline results taken from Cho et al. [2023], except
for the results of ConGress in Tables 1 and 2, which we obtained by running
its corresponding open-source code. For a fair comparison, we adopt the Graph
Transformer [Dwivedi and Bresson, 2020b, Vignac et al., 2023] as the neural
network used in GDSS+Transformer [Jo et al., 2022], DiGress [Vignac et al.,
2023], and DruM [Jo et al., 2023]. We set the diffusion steps to 1000 for all
the diffusion models. For important hyperparameters mentioned in Sec 2.4, we
usually set $S_{cale}=0.9$, $S_{hift}=0.09$. and $\eta=[10000,100,30,10]$ for
the normalized degrees corresponding to the intervals falling in the interval
split by $[1.0,0.8,0.4,0.1]$, respectively. In practice, we set threshold as
0.9 to quantize generated continue adjacency matrix.

###  A.2 2D molecule generation

#### Datasets

We utilize two widely-used molecular datasets as benchmarks, as described in
Jo et al. [2023]: QM9 [Ramakrishnan et al., 2014], consisting of 133,885
molecules with $N\leq 9$ nodes from 4 different node types and ZINC250k [Irwin
et al., 2012], consisting of 249,455 molecules with $N\leq 38$ nodes from 9
node types. Molecules in both datasets have 3 edge types, namely single bond,
double bond, and triple bond. Following the standard procedure in the
literature [Shi et al., 2020, Luo et al., 2021, Jo et al., 2022, 2023], we
kekulize the molecules using the RDKit library [Landrum et al., 2006] and
remove the hydrogen atoms from the molecules in the QM9 and ZINC250k datasets.

#### Evaluation metrics

Following the evaluation setting of Jo et al. [2022], we generate 10,000
molecules for each dataset and evaluate them with four metrics: the ratio of
valid molecules without correction (Val.). Frechet ChemNet Distance (FCD)
evaluates the chemical properties of the molecules by measuring the distance
between the feature vectors of generated molecules and those in the test set
using ChemNet. Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) assesses
the quality of the graph structure by measuring the MMD between the generated
molecular graphs and the molecular graphs from the test set. Scaffold
Similarity (Scaf.) evaluates the ability to generate similar substructures by
measuring the cosine similarity of the frequencies of Bemis-Murcko scaffolds
[Bemis and Murcko, 1996].

#### Implementation details

We follow the evaluation setting of Jo et al. [2022, 2023] to generate 10,000
molecules and evaluate graphs with test data for each dataset. We quote the
baselines results from Jo et al. [2023]. For a fair comparison, we adopt the
Graph Transformer [Dwivedi and Bresson, 2020b, Vignac et al., 2023] as the
neural network used in GDSS+Transformer [Jo et al., 2022], DiGress [Vignac et
al., 2023], and DruM [Jo et al., 2023]. We apply the exponential moving
average (EMA) to the parameters while sampling and set the diffusion steps to
1000 for all the diffusion models. For both QM9 and ZINC250k, we encode nodes
and edges to one-hot and set $S_{cale}=0.9$, $S_{hift}=0.09$. For $\eta$
modulated in molecule generation, with the help of chemical knowledge, we
apply $\eta=[10000,100,100,100,30]$ on carbon-carbon bond, carbon-nitrogen,
carbon-oxygen, carbon-fluorine, and other possible bonds, respectively. For
$\eta$ of nodes, we apply $\eta=[10000,100,100,30]$ on carbon atom, nitrogen
atom, oxygen atom and other possible atoms, respectively. As described in Sec
2.4, applying appropriate $\eta$ for different node types and edge types can
prolong the presence of related substructures during the diffusion process. In
practice, we set threshold as 0.9 to quantize generated continue adjacency
matrix and the value in discrete adjacency matrix is 0 after quantizing if and
only if all values in each dimension are all 0.

###  A.3 Computing resources

For all experiments, we utilized the PyTorch [Paszke et al., 2019] framework
to implement GBD and trained the model with NVIDIA GeForce RTX 4090 and RTX
A5000 GPUs.

##  Appendix B Visualization

###  B.1 Generative process of GBD on general datasets

We visualize generative process of GBD on the Community-small and the Ego-
small dataset in Figures 3 and 4, respectively.

Figure 3: Visualization of the generative process of GBD on the Community-
small dataset. Figure 4: Visualization of the generative process of GBD on the
Ego-small dataset.

###  B.2 Generated graphs of GBD on 2D molecule datasets

Figure 5: Visualization of the generated graphs of GBD on the QM9 dataset.
Figure 6: Visualization of the generative process of GBD on the ZINC250k
dataset.

We provide the visualization of the 2D molecules generated by GBD on the QM9
and the ZINC250k datasets in Figure 5 and in Figure 6, respectively.