# Fast Graph Generation via Spectral Diffusion

Tianze Luo†, Zhanfeng Mo†, Sinno Jialin Pan* T. Luo, Z. Mo and S. J. Pan are
with the School of Computer Science and Engineering, Nanyang Technological
University, Singapore. $\dagger$ indicates co-first authors with equal
contribution. * indicates corresponding author. E-mail:
<EMAIL_ADDRESS>
###### Abstract

Generating graph-structured data is a challenging problem, which requires
learning the underlying distribution of graphs. Various models such as graph
VAE, graph GANs, and graph diffusion models have been proposed to generate
meaningful and reliable graphs, among which the diffusion models have achieved
state-of-the-art performance. In this paper, we argue that running full-rank
diffusion SDEs on the whole graph adjacency matrix space hinders diffusion
models from learning graph topology generation, and hence significantly
deteriorates the quality of generated graph data. To address this limitation,
we propose an efficient yet effective Graph Spectral Diffusion Model (GSDM),
which is driven by low-rank diffusion SDEs on the graph spectrum space. Our
spectral diffusion model is further proven to enjoy a substantially stronger
theoretical guarantee than standard diffusion models. Extensive experiments
across various datasets demonstrate that, our proposed GSDM turns out to be
the SOTA model, by exhibiting both significantly higher generation quality and
much less computational consumption than the baselines.

###### Index Terms:

Graph generative model, graph diffusion, stochastic differential equations.

##  1 Introduction

Learning to generate graph-structural data not only requires knowing the
nodes’ feature distribution, but also a deep understanding of the underlying
graph topology, which is essential to modelling various graph instances, such
as social networks [1, 2], molecule structures [3, 4], neural architectures
[5], recommender systems [6], etc. Conventional likelihood-based graph
generative models, e.g. GraphGAN [7], GraphVAE [8] and GraphRNN [9], have
demonstrated great strength on graph generation tasks. In general, a
likelihood-based model is designed to learn the likelihood function of the
underlying graph data distribution, with which one can draw new samples with
preserved graph properties from the distribution of interest. However, most
likelihood-based generative models suffer from either limited quality of
modeling graph structures, or considerable computational burden [10].

Figure 1: Illustation of the difference between applying the conventional SDE
diffusion process on images (shown in (a)) and on graphs (shown in (b)).

(a) Real data

(b) GSDM samples

(c) GDSS samples

(d) Real data

(e) GSDM samples

(f) GDSS samples

Figure 2: Non-cherry-picked random samples from the testing set as well as
samples generated by GSDM (ours) and GDSS [10], on Grid (top row) and
Community-small (bottom row) datasets. For GDSS, we use the authors’ released
code and checkpoints to generate the samples.

Recently, a series of diffusion-based generative models have been proposed to
overcome the limitations of likelihood-based models. Although being originally
established for image generation [11], diffusion models exhibit a great
success in graph generation tasks with complex graph structural properties
[12, 10]. Roughly speaking, diffusion refers to a Stochastic Differential
Equation (SDE) that smoothly converts authentic data into pure noise via noise
insertion. A diffusion model is able to reverse the data back from the noise,
as long as the corresponding reversed-time SDE is known, which depends on the
time-dependent gradient field of the density function (i.e. score function).
To achieve this, a neural network is trained to learn the score function, and
hence a reversed-time process can be constructed with the estimated score. The
first graph diffusion model through SDEs, coined Graph Diffusion via SDE
Systems (GDSS) [10], is designed to simultaneously generate node features and
adjacency matrix via reversed diffusion. Similar to image diffusion models
[11, 13], at each diffusion step, GDSS directly inserts standard Gaussian
noise to both node features and the adjacency matrix. Meanwhile, two separate
neural networks are trained to learn the score functions of the node features
and adjacency matrix, respectively.

However, unlike the densely distributed image data, graph adjacency matrices
can be highly sparse, which makes isotropic Gaussian noise insertion
incompatible with graph structural data. In these circumstances, as shown in
Figure 1, there is a stark difference between the diffusion process on images
and on graph adjacency matrices. As can bee seen from the figure, the image
corrupted by full-rank Gaussian noise exhibits recognizable numerical patterns
along the early- and middle-stage of forward diffusion. However, the corrupted
sparse graph adjacency matrix degenerates into a dense matrix with uniformly
distributed entries in a few diffusion steps. In intuition, Figure 1 implies
that standard diffusion SDEs with full-rank isotropic noise insertion is
destructive of learning graph topology and feature representations.
Theoretically speaking, for extremely sparse graphs (e.g. molecules) with low-
rank adjacency matrices, the adjacency score functions are supported on a low-
dimensional manifold embedded in the full adjacency matrix space. Thus,
directly applying diffusion models on graph topology generation is not
desirable: once the diffusion SDE is run in the full space of the adjacency
matrix, lethal noise will be injected into the out-of-support regions and
drives the signal-to-noise ratio to be essentially zero, which is fatal for
training score networks.

Even for densely connected graphs, the standard diffusion model is problematic
for topology generation. Unlike image pixels that are merely locally
correlated, an adjacency matrix governs the message-passing pattern of the
whole graph. Thus, isotropic Gaussian noise insertion severely distorts the
message-passing pattern, by blindly encouraging message passing on sparsely
connected parts, which impedes the representation learning of sparse regions.

In order to establish a graph-friendly diffusion model, one should design an
appropriate diffusion scheme that is compatible with the graph topology
structure. To this end, we propose the Graph Spectral Diffusion Model (GSDM),
which is driven by diffusion SDEs on both the node feature space and the graph
spectrum space. At each diffusion step, instead of corrupting the entire
adjacency matrix, our method confines the Gaussian insertion to the graph
spectrum space, i.e. the eigenvalue matrix of the adjacency matrix. This novel
diffusion scheme enables us to perform smooth transformations on graph data
during both the training and sampling phases. As illustrated in Figure 2, our
proposed GSDM significantly outperforms the standard graph diffusion model
(GDSS [10]) in terms of graph generation quality and plausibility. For the
Grid dataset shown in the top row of the figure, GDSS samples seem to be
merely chaotic clusters, while GSDM samples exhibit smooth surface-like
patterns that are visually similar to real data. For the Community-small
dataset shown in the bottom row of the figure, GDSS fails to capture the link
between two communities on some samples, while GSDM is able to capture
dumbbell-like pattern (two clusters connected by one edge) as well as
butterfly-like pattern (two clusters connected by two edges). This implies
that GDSS’s generation not only fails to mimic the observed topology
distribution, but also suffers from capturing challenging details of the data
such as links between communities. In contrast, GSDM is capable of generating
high-quality graphs that are topologically similar to the real data, while
retaining critical details.

We empirically evaluate the capability of our proposed GSDM on generic graph
generation tasks, by evaluating the generation quality on both synthetic and
real-world graph datasets. As shown in Section 4, GSDM outperforms existing
one-shot generative models on various datasets, while achieving competitive
performance to autoregressive models. Further molecule generation experiments
show that our GSDM outperforms the state-of-the-art baselines, demonstrating
that our proposed spectral diffusion model is capable of capturing complicated
dependency between nodes and edges. Our main contributions are 3 folds:

  * •

We propose a novel Graph Spectral Diffusion Model (GSDM) for fast and quality
graph generation. Our method overcomes the limitations of existing graph
diffusion models by leveraging diffusion SDEs on both the node feature and
graph spectrum spaces.

  * •

Through the lens of stochastic analysis, we prove that GSDM enjoys a
substantially stronger performance guarantee than the standard graph diffusion
model. Our proposed spectral diffusion sharpens the reconstruction error bound
from $\mathcal{O}(n^{2}\exp(n^{2}))$ to $\mathcal{O}(n\exp(n))$, where $n$ is
the number of nodes.

  * •

We evaluate GSDM on both synthetic and real-world graph generation tasks, on
which GSDM outperforms all existing graph generative models. Moreover, GSDM
also achieves evidently higher computational efficiency compared to existing
graph diffusion models.

##  2 Related Work

From the view of graph generation strategies, graph generative models can be
classified into two categories, sequential models and one-shot models. The
sequential models, including GraphRNN [9], GraphVAE [8], generate the nodes
and edges in a sequential way, i.e. one after another [14], with validity
checks among the generation steps. Models using a similar generation process
are also known as autoregressive models. In contrast, one-shot generative
models, e.g. GAN-based models [15], VAE-based models [16], flow-based models
[3] and score-based models [12, 10], learn the intrinsic dependency of graph
structure by treating the distribution of all the components of a graph as a
whole and therefore generate the entire graph in an integrative way. As a
result, one-shot generative models enjoy the node permutation-invariant
property. Moreover, one-shot models usually exhibit higher computational
efficiency than autoregressive models. Our proposed GSDM generates data by
reversing a spectral diffusion SDE with a learned spectral score function,
thus it is essentially a score-based model. Since GSDM accepts the destination
of the reversed diffusion SDE as the ultimately generated samples without any
additional refinements, it can also be categorized as a one-shot model.

A recently proposed score-based model, GDSS [10], is the first and state-of-
the-art diffusion-based generative model that simultaneously conducts nodes
and edges generation. In essence, GDSS recasts the image diffusion paradigm
[13] for graph generation. During the forward diffusion process, GDSS injects
Gaussian noise to both the node features and the adjacency matrix at each
diffusion step. Then, a neural network is trained to learn the score function
by minimizing the score-matching objective, which enables a reversion of graph
data from noise via a reversed time diffusion process. However, such a
directly borrowed diffusion model is incompatible with graph topology
generation: unlike images which are feature-rich, the graph adjacency matrix
is generally sparse and low-rank. Hence, injecting isotropic Gaussian noise
into the sparsely connected parts of the adjacency matrix severely harms the
graph data distribution and makes it hard to be recovered from Gaussian noise.

##  3 Preliminaries

###  3.1 Notations

In this paper, we denote the probability space of interest as
$(\Omega,\mathcal{F},\mathbb{P})$ and $(\mathcal{F}_{t})_{t\in\mathbb{R}}$ be
a filtration, i.e. a sequence of increasing sub-$\sigma$-algebra of
$\mathcal{F}$. Without specification, we denote
$(\mathbf{B}_{t})_{t\in\mathbb{R}}$ as the $d$-dimensional standard Brownian
motion on the filtered probabilistic space
$(\Omega,\mathcal{F},\mathbb{P},(\mathcal{F}_{t})_{t\in\mathbb{R}})$. The
distribution, support set and expectation of a random variable $\mathbf{z}$
are defined as $\mathrm{law}(\mathbf{z})$, $\mathrm{supp}(\mathbf{z})$ and
$\mathbb{E}[\mathbf{z}]$. $\mathbf{y}|\mathbf{z}$ denotes the distribution of
$\mathbf{y}$ conditioned on $\mathbf{z}$. $\mathrm{Unif}(A)$ denotes the
uniform distribution on a set $A$. $\|\cdot\|$ denotes the standard Euclid
norm. $\|\cdot\|_{\infty}$ and $\|\cdot\|_{\mathrm{lip}}$ denotes the supremum
norm and Lipschitz norm of a function. $[\cdot]$ denotes the flooring
function.

###  3.2 Score-based Generative Diffusion Model

A generative model refers to a mapping
$g_{\bm{\theta}}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$, which maps a simple
known priori $\pi$ to a complicated data distribution $\mathcal{D}$. Once the
model $g_{\bm{\theta}}$ is sufficiently trained on $N$ i.i.d samples from
$\mathcal{D}$, denoted by $\mathcal{S}$, it enables us to generate plausible
instances from $\mathcal{D}$ directly, by sampling from
$g_{\bm{\theta}}(\bm{\varepsilon}),\ \bm{\varepsilon}\sim\pi$. Unlike
conventional generative models, e.g. VAE and GAN, which treat $\mathcal{D}$ as
a unilateral transformation of $\pi$, diffusion models consider the bilateral
relation between $\mathcal{D}$ and $\pi$ from the perspective of SDE. Given an
SDE travelling from $\mathcal{D}$ to $\pi$, the corresponding reversed time
SDE enables us to backtrack from noisy priori to the distribution of interest.

######  Lemma 3.1 (Forward Diffusion and Reversed Time SDE [17]).

The Forward Diffusion refers to the following SDE

$\displaystyle\mathbf{z}_{0}\sim\mathcal{D},\
\mathrm{d}\mathbf{z}_{t}=\mathbf{f}(\mathbf{z}_{t},t)\mathrm{d}t+\sigma_{t}\mathrm{d}\mathbf{B}_{t},\
t\in[0,1],$ (1)

where $\mathbf{f}(\cdot,t):\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ is the drift
function, $\sigma_{t}:[0,1]\mapsto\mathbb{R}$ be a scalar diffusion function.
Let $p_{t}(\cdot)$ be the probability density function of $\mathbf{z}_{t}$,
then the Reversed Time SDE is given by

$\displaystyle\mathrm{d}\bar{\mathbf{z}}_{t}=$
$\displaystyle(\mathbf{f}(\bar{\mathbf{z}}_{t},t)-\sigma_{t}^{2}\nabla\log
p_{t}(\bar{\mathbf{z}}_{t}))\mathrm{d}\bar{t}+\sigma_{t}\mathrm{d}\bar{\mathbf{B}}_{t},$
(2) $\displaystyle\bar{\mathbf{z}}_{1}\sim$ $\displaystyle\mathbf{z}_{1},\
t\in[0,1],$

where $\mathrm{d}\bar{t}=-\mathrm{d}t$ is the negative infinitesimal time
step, $(\bar{\mathbf{B}}_{t})_{t\in\mathbb{R}}$ is a reversed time Brownian
motion w.r.t
$(\Omega,\mathcal{F},\mathbb{P},(\bar{\mathcal{F}}_{t})_{t\in\mathbb{R}})$,
and $(\bar{\mathcal{F}}_{t})_{t\in\mathbb{R}}$ is the corresponding decreasing
filtration; $\nabla\log p_{t}(\cdot)$ is the score function.

During the forward diffusion process, with a carefully designed
$\mathbf{f}(\cdot,t)$, the original data is perturbed by Gaussian noise with
increasing magnitude, and it is assumed to be gradually corrupted to a truly
noisy signal (priori), i.e. $\mathrm{law}(\mathbf{z}_{1})=\pi$. In order to
draw new data from $\pi$ via the reversed time SDE, one needs to learn the
unknown score function $\nabla\log p_{t}(\cdot)$ with a neural network
$s_{\bm{\theta}}(\cdot):\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$, by minimizing
the following explicit score matching error:

$\displaystyle\mathcal{E}(\bm{\theta})\triangleq\mathbb{E}_{\mathbf{z}\sim\mathcal{D}}\mathbb{E}_{\mathbf{z}_{t}|\mathbf{z}}\|s_{\bm{\theta}}(\mathbf{z}_{t})-\nabla\log
p_{t}(\mathbf{z}_{t})\|^{2}.$ (3)

In practice, we employ a Gaussian priori $\pi$. For each sample
$\mathbf{z}^{i}\in\mathcal{S}$, we first generate a sequence of corrupted data
$\\{\mathbf{z}^{i}_{t_{j}}\\}_{j=1}^{T}$ by discretizing (1). To learn the
score network $s_{\bm{\theta}}(\cdot)$, one can minimize a more tractable
denoising score matching objective $\hat{\mathcal{E}}(\bm{\theta})$

$\displaystyle\hat{\mathcal{E}}(\bm{\theta})\triangleq\mathbb{E}_{\mathbf{z}\sim\mathrm{Unif}(\mathcal{S})}\mathbb{E}_{\mathbf{z}_{t}|\mathbf{z}}\|s_{\bm{\theta}}(\mathbf{z}_{t})-\nabla\log
p(\mathbf{z}_{t}|\mathbf{z})\|^{2},$ (4)

which has been proven to be equivalent to $\mathcal{E}(\bm{\theta})$ in [18].
Given a well trained score network $s_{\bm{\theta}^{*}}(\cdot)$, one is able
to generate plausible data from $\pi$ via solving the learned reversed-time
SDE

$\displaystyle\mathrm{d}\hat{\mathbf{z}}_{t}=$
$\displaystyle(\mathbf{f}(\hat{\mathbf{z}}_{t},t)-\sigma_{t}^{2}s_{\bm{\theta}^{*}}(\hat{\mathbf{z}}_{t}))\mathrm{d}\bar{t}+\sigma_{t}\mathrm{d}\bar{\mathbf{B}}_{t},$
(5) $\displaystyle\hat{\mathbf{z}}_{1}\sim$ $\displaystyle\pi,\ t\in[0,1].$

Ideally, the learned reversed time SDE should lead us towards $\mathcal{D}$,
i.e. $\mathrm{law}(\hat{\mathbf{z}}_{0})=\mathcal{D}$.

##  4 Methodology

In this section, we establish the Graph Spectral Diffusion Model (GSDM) for
fast and effective graph data generation. In Section 4.1, we briefly review
the standard score-based graph diffusion model [10]. In Section 4.2, we
formally introduce our GSDM algorithm and its $\alpha$-quantile variants. In
Section 4.3, we provide theoretical analyses to justify the efficacy of GSDM
on graph data generation.

###  4.1 Standard Graph Diffusion Model

A graph with $n$ nodes is defined as
$\mathbf{G}\triangleq(\mathbf{X},\mathbf{A})\in\mathbb{R}^{n\times
d}\times\mathbb{R}^{n\times n}$, where $\mathbf{X}\in\mathbb{R}^{n\times d}$
is the node feature matrix with dimension $d$ and
$\mathbf{A}\in\mathbb{R}^{n\times n}$ denotes the adjacency matrix. A graph
generative model aims to learn the underlying data distribution, say
$\mathbf{G}\sim\mathcal{G}$, which is a joint distribution of both
$\mathbf{X}$ and $\mathbf{A}$. Note that, if $(\mathbf{X},\mathbf{A})$ is
treated as a whole and omit the intrinsic graph structure, the aforementioned
score-based generation framework can be parallelly extended to the graph
generation setting, which yields the standard graph diffusion model, i.e. GDSS
[10]. Roughly speaking, for each graph sample $(\mathbf{X},\mathbf{A})$, we
first generate a sequence of perturbed graphs
$\\{(\mathbf{X}_{t_{i}},\mathbf{A}_{t_{i}})\\}_{i=1}^{T}$ via forward
diffusion. Then, we train two score networks $s_{\bm{\theta}}(\cdot)$ and
$s_{\bm{\phi}}(\cdot)$ to learn the score functions for both $\mathbf{X}_{t}$
and $\mathbf{A}_{t}$, with which we can generate new data from $\pi$ by
running the reversed time SDE. Graph diffusion SDEs are defined as follows.

######  Definition 1 (Graph Diffusion SDEs with Disentangled Drift).

The Forward Graph Diffusion refers to the following SDE system

$\displaystyle\begin{cases}\mathrm{d}\mathbf{X}_{t}=&\mathbf{f}^{X}(\mathbf{X}_{t},t)\mathrm{d}t+\sigma_{X,t}\mathrm{d}\mathbf{B}_{t}^{X},\\\
\mathrm{d}\mathbf{A}_{t}=&\mathbf{f}^{A}(\mathbf{A}_{t},t)\mathrm{d}t+\sigma_{A,t}\mathrm{d}\mathbf{B}_{t}^{A},\end{cases}$
(6) $\displaystyle(\mathbf{X}_{0},\mathbf{A}_{0})\sim\mathcal{G},\ t\in[0,1],$

where $\mathbf{f}^{X}(\cdot,t):\mathbb{R}^{n\times
d}\mapsto\mathbb{R}^{n\times d}$ and
$\mathbf{f}^{A}(\cdot,t):\mathbb{R}^{n\times n}\mapsto\mathbb{R}^{n\times n}$
is the drift functions for nodes feature and adjacency matrix;
$\sigma_{X,t},\sigma_{A,t}$ are the scalar diffusion terms (a.k.a noise
schedule function); $(\mathbf{B}_{t}^{X})_{t\in\mathbb{R}}$ and
$(\mathbf{B}_{t}^{A})_{t\in\mathbb{R}}$ are standard Brownian motions on
$\mathbb{R}^{n\times d}$ and $\mathbb{R}^{n\times n}$, respectively.

To alleviate the computational burden of calculating the drift w.r.t the high
dimensional $\mathbf{G}$, the drift term of forward graph diffusion is
disentangled into $\mathbf{f}^{X}(\cdot,t)$ and $\mathbf{f}^{A}(\cdot,t)$.
Again, Lemma 3.1 guarantees the existence of the reversed time SDEs for graph
diffusion.

######  Corollary 1 (Reversed Time SDEs for Graph Diffusion).

The reversed time SDE system of (6) is given by

$\displaystyle\begin{cases}\mathrm{d}\bar{\mathbf{X}}_{t}=&\left(\mathbf{f}^{X}(\bar{\mathbf{X}}_{t},t)-\sigma_{X,t}^{2}\nabla_{\mathbf{X}}\log
p_{t}(\bar{\mathbf{X}}_{t},\bar{\mathbf{A}}_{t})\right)\mathrm{d}\bar{t}+\sigma_{X,t}\mathrm{d}\bar{\mathbf{B}}_{t}^{X},\\\
\mathrm{d}\bar{\mathbf{A}}_{t}=&\left(\mathbf{f}^{A}(\bar{\mathbf{A}}_{t},t)-\sigma_{A,t}^{2}\nabla_{\mathbf{A}}\log
p_{t}(\bar{\mathbf{X}}_{t},\bar{\mathbf{A}}_{t})\right)\mathrm{d}\bar{t}+\sigma_{A,t}\mathrm{d}\bar{\mathbf{B}}_{t}^{A},\end{cases}$
$\displaystyle(\bar{\mathbf{X}}_{1},\bar{\mathbf{A}}_{1})\sim\pi,\ t\in[0,1],$
(7)

where $\mathrm{d}\bar{t}=-\mathrm{d}t$ is the negative infinitesimal time
step; $(\bar{\mathbf{B}}_{t}^{X})_{t\in\mathbb{R}}$ and
$(\bar{\mathbf{B}}_{t}^{A})_{t\in\mathbb{R}}$ are the reversed time standard
Brownian motions induced by (6).

The disentanglement of the drift functions implies the conditional
independence $\mathbf{X}_{t}\perp\mathbf{A}_{t}|\mathbf{G}_{0}$, with which we
can decompose $p_{t}(\bar{\mathbf{X}}_{t},\bar{\mathbf{A}}_{t})$ into
$p_{t|0}(\mathbf{X}_{t}|\mathbf{X}_{0})\cdot
p_{t|0}(\mathbf{A}_{t}|\mathbf{A}_{0})$, where $p_{t|0}(\cdot)$ denotes the
density function of $\mathbf{G}_{t}|\mathbf{G_{0}}$. As proposed in [10], such
conditional independence reduces the denoising score matching objective to a
simpler form

$\displaystyle\widehat{\mathcal{E}}(\bm{\theta})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{G}\sim\mathrm{Unif}(\mathcal{S})}\mathbb{E}_{\mathbf{G}_{t}|\mathbf{G}}\|s_{\bm{\theta}}(\mathbf{G}_{t})-\nabla\log
p_{t|0}(\mathbf{X}_{t}|\mathbf{X}_{0})\|^{2},$ (8)
$\displaystyle\widehat{\mathcal{E}}(\bm{\phi})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{G}\sim\mathrm{Unif}(\mathcal{S})}\mathbb{E}_{\mathbf{G}_{t}|\mathbf{G}}\|s_{\bm{\phi}}(\mathbf{G}_{t})-\nabla\log
p_{t|0}(\mathbf{A}_{t}|\mathbf{A}_{0})\|^{2}.$ (9)

Hence, the training and sampling procedures can be directly borrowed from
standard score-based models.

While GDSS is the first attempt at leveraging diffusion models on graph
generation, its performance is hindered by the brute force application of
diffusion. For sparsely connected graphs, while the distribution of node
features varies across datasets, the distribution of graph topology, i.e.
adjacency matrix, resides in a low dimensional manifold. As mentioned in
Section 1, an evident pattern of the adjacency matrices also implies that the
true distribution of $\mathbf{A}$ is of low rank. In this case, the score
matching objective fails to provide consistency estimators. Although running a
full rank diffusion on $\mathbf{A}\in\mathbb{R}^{n\times n}$ alleviates this
issue by extending the support of corrupted data from the manifold to the full
space, it inevitably introduces lethal noise to regions of zero probability
density. As a consequence, the signal-to-noise ratio of regions out of
$\mathrm{supp}(\mathbf{A})$ is essentially zero, which is a catastrophe for
training the denoising score network. Note that such full-rank diffusion is
also inappropriate for the densely connected graph generation. This is because
an isotropically corrupted adjacency matrix encourages delusive message
passing on sparsely connected parts of the graph, which is destructive to the
graph message passing pattern. Thus, standard diffusion can severely impair
representation learning for sparse graph regions.

###  4.2 Graph Spectral Diffusion Model

To address these notorious yet ubiquitous issues, we novelly propose the Graph
Spectral Diffusion Model. For graph topology generation, in contrast to GDSS
which is driven by a full-rank diffusion on the whole space
$\mathbb{R}^{n\times n}$, our GSDM leverages low-rank diffusion SDEs on the
$n$-dimensional spectrum manifold, e.g. the span of $n$-eigenvalues of
$\mathbf{A}$. As we shall see later, GSDM achieves both robustness and
computational efficiency, by exploiting the graph spectrum structure and
running diffusion on an information-concentrated manifold.

######  Definition 2 (Graph Spectral Diffusion SDEs).

Let the spectral decomposition of $\mathbf{A}$ be
$\mathbf{U}\bm{\Lambda}\mathbf{U}^{\top}$, where columns of $\mathbf{U}$ are
the orthonormal eigenvectors and $\bm{\Lambda}$ be the diagonal eigenvalue
matrix, i.e. spectrum. The Forward Spectral Diffusion refers to the following
SDE system

$\displaystyle\begin{cases}\mathrm{d}\mathbf{X}_{t}=&\mathbf{f}^{X}(\mathbf{X}_{t},t)\mathrm{d}t+\sigma_{X,t}\mathrm{d}\mathbf{B}_{t}^{X},\\\
\mathrm{d}\bm{\Lambda}_{t}=&\mathbf{f}^{\Lambda}(\bm{\Lambda}_{t},t)\mathrm{d}t+\sigma_{\Lambda,t}\mathrm{d}\mathbf{W}_{t}^{\Lambda},\end{cases}$
(10) $\displaystyle(\mathbf{X}_{0},\mathbf{A}_{0})\sim\mathcal{G},\
\mathbf{A}_{0}=\mathbf{U}_{0}\bm{\Lambda}_{0}\mathbf{U}_{0}^{\top},\
t\in[0,1],$

where $\mathbf{f}^{X}(\cdot,t):\mathbb{R}^{n\times
d}\mapsto\mathbb{R}^{n\times d}$ is the drift for nodes feature;
$\mathbf{f}^{\Lambda}(\cdot,t):\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ is the
drift for spectrum, which only acts on the diagonal entries;
$\sigma_{X,t},\sigma_{\Lambda,t}$ are the scalar diffusion terms (a.k.a noise
schedule functions); $(\mathbf{B}_{t}^{X})_{t\in\mathbb{R}}$ and
$(\mathbf{B}_{t}^{\Lambda})_{t\in\mathbb{R}}$ are standard Brownian motions on
$\mathbb{R}^{n\times d}$ and $\mathbb{R}^{n}$, respectively; and
$\mathbf{W}_{t}^{\Lambda}\triangleq\mathrm{diag}(\mathbf{B}_{t}^{\Lambda})$ is
a diagonal Brownian motion.

By comparing (10) with (6), one should notice that the initial eigenvector
matrix $\mathbf{U}_{0}$ is fixed along the spectral diffusion. As will be
illustrated later, the evolution of
$\mathbf{A}_{t}\triangleq\mathbf{U}_{0}\bm{\Lambda}_{t}\mathbf{U}_{0}^{\top}$
is driven by a $n$-dimensional Gaussian process. Hence, we prevent the
corrupted adjacency matrix from rampaging around the full space. We are now
ready to establish the reversed time spectral diffusion SDEs.

######  Corollary 2 (Reversed Time Spectral Diffusion SDEs).

The reversed time Spectral Diffusion SDE system of (10) is given by

$\displaystyle\begin{cases}\mathrm{d}\bar{\mathbf{X}}_{t}=&\left(\mathbf{f}^{X}(\bar{\mathbf{X}}_{t},t)-\sigma_{X,t}^{2}\nabla_{\mathbf{X}}\log
p_{t}(\bar{\mathbf{X}}_{t},\bar{\bm{\Lambda}}_{t})\right)\mathrm{d}\bar{t}+\sigma_{X,t}\mathrm{d}\bar{\mathbf{B}}_{t}^{X},\\\
\mathrm{d}\bar{\bm{\Lambda}}_{t}=&\left(\mathbf{f}^{\Lambda}(\bar{\bm{\Lambda}}_{t},t)-\sigma_{\Lambda,t}^{2}\nabla_{\bm{\Lambda}}\log
p_{t}(\bar{\mathbf{X}}_{t},\bar{\bm{\Lambda}}_{t})\right)\mathrm{d}\bar{t}+\sigma_{\Lambda,t}\mathrm{d}\bar{\mathbf{W}}_{t}^{\Lambda},\end{cases}$
$\displaystyle(\bar{\mathbf{X}}_{1},\bar{\bm{\Lambda}}_{1})\sim\pi,\
t\in[0,1],$ (11)

where $\mathrm{d}\bar{t}=-\mathrm{d}t$ is the negative infinitesimal time
step; $(\bar{\mathbf{B}}_{t}^{X})_{t\in\mathbb{R}}$ and
$(\bar{\mathbf{B}}_{t}^{\Lambda})_{t\in\mathbb{R}}$ are reversed time standard
Brownian motions induced by (6); and
$\bar{\mathbf{W}}_{t}^{\Lambda}\triangleq\mathrm{diag}(\bar{\mathbf{B}}_{t}^{\Lambda})$.

Since $\mathbf{U}$ is no longer involved in (11), the boundary condition is
only imposed on the joint distribution of $(\mathbf{X}_{1},\bm{\Lambda}_{1})$
such that $\mathrm{law}(\mathbf{X}_{1},\bm{\Lambda}_{1})=\pi$. This assumption
implies that, the authentic distribution $(\mathbf{X}_{0},\bm{\Lambda}_{0})$
can be recovered from a priori $\pi$ by the reversed time spectral diffusion
SDE. According to score matching techniques [18], we can train two score
networks $s_{\bm{\theta}}(\cdot,\cdot),s_{\bm{\phi}}(\cdot,\cdot)$ to learn
the score functions $\nabla_{\mathbf{X}}\log
p_{t}(\cdot,\cdot),\nabla_{\bm{\Lambda}}\log p_{t}(\cdot,\cdot)$ via
minimizing

$\displaystyle\widehat{\mathcal{E}}(\bm{\theta})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{G}\sim\mathrm{Unif}(\mathcal{S})}\mathbb{E}_{\mathbf{X}_{t}|\mathbf{G}}\|s_{\bm{\theta}}(\mathbf{X}_{t},\bm{\Lambda}_{t})-\nabla\log
p_{t|0}(\mathbf{X}_{t}|\mathbf{X}_{0})\|^{2},$
$\displaystyle\widehat{\mathcal{E}}(\bm{\phi})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{G}\sim\mathrm{Unif}(\mathcal{S})}\mathbb{E}_{\bm{\Lambda}_{t}|\mathbf{G}}\|s_{\bm{\phi}}(\mathbf{X}_{t},\bm{\Lambda}_{t})-\nabla\log
p_{t|0}(\bm{\Lambda}_{t}|\bm{\Lambda}_{0})\|^{2}.$

In nutshell, the proposed GSDM is summarized as three main steps. Details of
GSDM can be found Algorithm 1 and Algorithm 2 in Appendix B.1.

  * 1.

Run forward spectral diffusion model on $(\mathbf{X},\bm{\Lambda})$ by (10).
Train two score networks $s_{\bm{\theta}}(\cdot),s_{\bm{\phi}}(\cdot)$ to
learn score functions shown up in (11).

  * 2.

Generate plausible $(\widehat{\mathbf{X}}_{0},\widehat{\bm{\Lambda}}_{0})$
from $\pi$, via reversing the spectral diffusion SDEs from $t=1$ to $t=0$,
with estimated score functions
$s_{\bm{\theta}}(\widehat{\mathbf{X}}_{t},\widehat{\bm{\Lambda}}_{t}),s_{\bm{\phi}}(\widehat{\mathbf{X}}_{t},\widehat{\bm{\Lambda}}_{t})$.

  * 3.

Generate plausible adjacency matrix via
$\widehat{\mathbf{A}}=\widehat{\mathbf{U}}\widehat{\bm{\Lambda}}_{0}\widehat{\mathbf{U}}^{\top}$,
where $\widehat{\mathbf{U}}$ is uniformly sampled from the observed
eigenvector matrices.

Since the full adjacency matrices are not involved in the computation of
diffusion SDEs, GSDM achieves significant acceleration in both training and
sampling. Moreover, one can further enhance the computational efficiency, by
confining the spectral diffusion to the top-$k$ largest eigenvalues of
$\mathbf{A}$, where $k\triangleq[\alpha n]$. Suppose $\bm{\Lambda}^{k}$ is the
truncated eigenvalue matrix, where only the top-$k$ diagonal entries of
$\bm{\Lambda}$ are preserved, we can define the $\alpha$-quantile GSDM by
substituting the occurrence of $\bm{\Lambda}$ in GSDM with
$\bm{\Lambda}^{(k)}$. As will be seen in the following section,
$\alpha$-quantile GSDM exhibits evidently faster processing speed and
comparable performance to GSDM.

###  4.3 Theoretical Analysis

Here, we provide supportive theoretical evidence for the efficacy of GSDM. In
Proposition 1, we first study the low-rank structure of the spectral diffusion
SDE of adjacency matrices. In Proposition 2, we further prove that our
proposed spectral diffusion enjoys a sharper reconstruction error bound than
the standard graph diffusion model.

######  Proposition 1 (Spectral Diffusion SDEs on Adjacency Matrix).

Suppose
$\mathbf{f}_{\Lambda}(\bm{\Lambda},t)\triangleq-\sigma_{\Lambda,t}^{2}/2\bm{\Lambda}$.
The spectral diffusion SDE system (10) induces an $n$-dimensional SDE system
of the adjacency matrix $\mathbf{A}$ on the full space $\mathbb{R}^{n\times
n}$. Following previous notations, the forward diffusion SDE is given by

$\displaystyle\begin{cases}\mathrm{d}\mathbf{X}_{t}=&\mathbf{f}^{X}(\mathbf{X}_{t},t)\mathrm{d}t+\sigma_{X,t}\mathrm{d}\mathbf{B}_{t}^{X},\\\
\mathrm{d}\mathbf{A}_{t}=&-\frac{1}{2}\sigma_{\Lambda,t}^{2}\mathbf{A}_{t}\mathrm{d}t+\sigma_{\Lambda,t}\mathrm{d}\mathbf{M}_{t},\end{cases}$
(12)

where $(\mathbf{M}_{t})_{t\in[0,1]}$ is a $n$-dimensional centered Gaussian
process on $\mathbb{R}^{n\times n}$, with zero mean and covariance kernel
$\mathcal{K}(s,t):[0,1]\times[0,1]\mapsto\mathbb{R}^{n\times n\times n\times
n}$ as

$\mathcal{K}(s,t)_{i,j,k,l}=\min(s,t)\cdot\sum_{h=1}^{n}\mathbf{U}_{0}[i,h]\mathbf{U}_{0}[j,h]\mathbf{U}_{0}[k,h]\mathbf{U}_{0}[l,h].$

Hence, the conditional distribution of $\mathbf{A}_{t}$ on $\mathbf{A}_{0}$ is
Gaussian

$\displaystyle\mathbf{A}_{t}|\mathbf{A}_{0}\sim
N(\mathbf{A}_{t};\mathbf{A}_{0}e^{-\frac{1}{2}\int_{0}^{t}\sigma_{\tau}^{2}\mathrm{d}\tau},(1-e^{-\int_{0}^{t}\sigma_{\tau}^{2}\mathrm{d}\tau})\mathcal{K}(1,1)),$
(13)

which admits a closed-form probability density function.

######  Remark 1.

The proof is postponed to Appendix A.1. Proposition 1 shows that our spectral
diffusion framework substantially recasts the evolution of adjacency matrix,
by driving the $n^{2}$-dimensional SDE with $n$-dimensional noise
$(\mathbf{M}_{t})_{t\in\mathbb{R}}$. Guided by the graph spectrum, the
diffusion is concentrated to the salient parts of $\mathrm{supp}(\mathbf{A})$
to prevent introducing irreducible noise to the out-of-support regions.

The central question for graph generation is how to measure the quality of the
synthesis data that is recovered from noise with the learned score function.
The key to this question is to establish the reconstruction error bound, i.e.
the expected error between the data reconstructed with ground truth score
$\nabla\log p_{t}(\cdot)$ and the learned scores $s_{\bm{\phi}}(\cdot)$. For
graph topology generation, our GSDM is proven to enjoy a sharper
reconstruction bound than standard graph diffusion. Detailed proof can be
found in Appendix A.2.

######  Proposition 2 (Reconstruction Bounds for Adjacency Matrix Generation).

Following the previous notations, we define the estimated reversed time SDEs
for standard and spectral graph diffusion models as

$\displaystyle\mathrm{d}\widehat{\mathbf{A}}_{t}^{\mathrm{full}}=$
$\displaystyle\left(-\frac{1}{2}\sigma_{t}^{2}\widehat{\mathbf{A}}_{t}^{\mathrm{full}}-\sigma_{t}^{2}s_{\bm{\phi}}(\widehat{\mathbf{A}}_{t}^{\mathrm{full}},t)\right)\mathrm{d}\bar{t}+\sigma_{t}\mathrm{d}\bar{\mathbf{B}}_{t}^{A},$
$\displaystyle\mathrm{d}\widehat{\mathbf{A}}_{t}^{\mathrm{spec}}=$
$\displaystyle\left(-\frac{1}{2}\sigma_{t}^{2}\widehat{\mathbf{A}}_{t}^{\mathrm{spec}}-\sigma_{t}^{2}s_{\bm{\varphi}}(\widehat{\mathbf{A}}_{t}^{\mathrm{spec}},t)\right)\mathrm{d}\bar{t}+\sigma_{t}\mathrm{d}\bar{\mathbf{M}}_{t},$

where both generation methods share the same drift term and noise schedule
$(\sigma_{t})_{t\in[0,1]}$. We further assume that
$\|s_{\bm{\phi}}(\cdot,t)\|_{\mathrm{lip}}=\mathcal{O}(\mathbb{E}_{|\mathbf{A}_{0}}\|\nabla_{\mathbf{A}}\log
p_{t|0}(\widehat{\mathbf{A}}_{t}^{\mathrm{full}})\|_{\mathrm{lip}})$ and
$\|s_{\bm{\varphi}}(\cdot,t)\|_{\mathrm{lip}}=\mathcal{O}(\mathbb{E}_{|\mathbf{A}_{0}}\|\nabla_{\mathbf{A}}\log
p_{t|0}(\widehat{\mathbf{A}}_{t}^{\mathrm{spec}})\|_{\mathrm{lip}})$ holds
almost surly. By reversing both SDEs from $t=1$ to $t=0$, we obtain
$\widehat{\mathbf{A}}_{t}^{\mathrm{full}}$ and
$\widehat{\mathbf{A}}_{t}^{\mathrm{spec}}$, which are two reconstructions of
the authentic $\mathbf{A}_{0}$, with expected reconstruction errors bounded by

$\displaystyle\mathbb{E}\|\mathbf{A}_{0}-\widehat{\mathbf{A}}_{0}^{\mathrm{full}}\|^{2}$
$\displaystyle\leqslant
M\mathcal{E}(\bm{\phi})\cdot\bigg{(}1+n^{2}K\int_{0}^{1}\Sigma_{t}^{-2}\exp\left(n^{2}K\int_{t}^{1}\Sigma_{s}^{-2}\mathrm{d}s\right)\mathrm{d}t\bigg{)},$
$\displaystyle\mathbb{E}\|\mathbf{A}_{0}-\widehat{\mathbf{A}}_{0}^{\mathrm{spec}}\|^{2}$
$\displaystyle\leqslant
M\mathcal{E}(\bm{\varphi})\cdot\left(1+nK\int_{0}^{1}\Sigma_{t}^{-2}\exp\left(nK\int_{t}^{1}\Sigma_{s}^{-2}\mathrm{d}s\right)\mathrm{d}t\right),$

where $M\triangleq C^{2}\|\sigma_{\cdot}\|_{\infty}^{4}$; $K\triangleq
2ML/\mathbb{E}\|\mathbf{A}_{0}\|_{2,2}$; $C,L$ are absolute constants;
$\Sigma_{t}^{2}\triangleq 1-e^{-\int_{0}^{t}\sigma_{s}^{2}\mathrm{d}s}$;
$\mathcal{E}(\cdot)$ is the expected score matching objective defined in (3).

######  Remark 2.

While the error bound of $\widehat{\mathbf{A}}_{0}^{\mathrm{full}}$ is at the
order of $\mathcal{O}(n^{2}\exp(n^{2}))$,
$\widehat{\mathbf{A}}_{0}^{\mathrm{spec}}$ exhibits a much sharper bound of
order $\mathcal{O}(n\exp(n))$. For large-scale graphs with a large number of
nodes $n$, our proposed GSDM enjoys a substantially better performance
guarantee, which coincides with our numerical results. Moreover, under
additional conditions, the error bounds can be significantly improved for
well-trained score networks $\bm{\phi}^{*},\bm{\varphi}^{*}$, by showing that
$\mathcal{E}(\bm{\phi}^{*})\ll\mathcal{E}(\bm{\phi})$ as in Proposition 3. The
detailed proof can be found in Appendix A.3.

######  Definition 3 ($\beta$-smooth).

$f:\mathbb{R}^{m}\mapsto\mathbb{R}^{n}$ is called $\beta$-smooth if and only
if

$\|f(x_{1})-f(x_{2})-\nabla
f(x_{2})^{\top}(x_{1}-x_{2})\|\leqslant\frac{\beta}{2}\|x_{1}-x_{2}\|^{2}$

holds for $\forall\ x_{1},x_{2}\in\mathbb{R}^{m}$.

######  Proposition 3 (Convergence of Score Matching Objective Minimization).

Recall that the score matching objective of a generic sample
$\mathbf{Z}\in\mathbb{R}^{d}$ ($\widehat{\mathbf{A}}^{\mathrm{full}}$ or
$\widehat{\mathbf{A}}^{\mathrm{spec}}$) is defined as

$\displaystyle\mathcal{E}(\bm{\theta};\mathbf{Z})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{Z}_{t}|\mathbf{Z}}\|s_{\bm{\theta}}(\mathbf{Z}_{t},t)-\nabla_{\mathbf{Z}}\log
p_{t}(\mathbf{Z}_{t})\|^{2},$ (14)

and the expected and empirical score matching error are defined as

$\displaystyle\mathcal{E}(\bm{\theta})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{Z}\sim\mathcal{D}}\mathcal{E}(\bm{\theta};\mathbf{Z})$
(15)
$\displaystyle\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{N})\triangleq$
$\displaystyle\mathbb{E}_{\mathbf{Z}\sim\mathcal{S}_{N}}\mathcal{E}(\bm{\theta};\mathbf{Z})$
(16)

where $\mathcal{D}$ is the population distribution of $\mathbf{Z}$, and
$\mathcal{S}\triangleq\\{\mathbf{Z}^{i}\\}_{i=1}^{N}$ is the uniform
distribution over an i.i.d sampled training dataset of size $N$. Suppose
$\mathcal{E}(\bm{\theta})$ is minimized via running standard Stochastic
Gradient Descent (SGD) on training data, i.e. at the $k$-th iteration,
$\bm{\theta}_{k}$ is updated on a mini-batch of size $b$

$\displaystyle\bm{\theta}_{k+1}\triangleq$
$\displaystyle\bm{\theta}_{k}-\eta\nabla_{\bm{\theta}}\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{b}).$
(17)

Assume that almost surely (w.r.t $\mathbf{Z}$),
$\mathcal{E}(\cdot;\mathbf{Z})$ is $\beta$-smooth, and the tangent kernel
$\mathbf{K}_{\bm{\theta}}(\mathcal{S})\in\mathbb{R}^{Nd\times Nd}$ of
$s_{\bm{\theta}}(\cdot)$ satisfies

$\displaystyle\lambda_{\mathrm{min}}\left(\mathbf{K}_{\bm{\theta}}(\mathcal{S})\right)\geqslant\lambda>0,\
\bm{\theta}\in B(\bm{\theta}_{0},R),$
$\displaystyle\mathbf{K}_{\bm{\theta}}(\mathcal{S})[Ni+1:N(i+1),Nj+1:N(j+1)]$
$\displaystyle\triangleq\nabla_{\bm{\theta}}s_{\bm{\theta}}(\mathbf{Z}^{i})^{\top}\nabla_{\bm{\theta}}s_{\bm{\theta}}(\mathbf{Z}^{j}),$

with $R=2N\sqrt{2\beta\mathcal{E}(\bm{\theta}_{0})}/(\mu\delta)$, $\delta>0$.
Then, with probability $1-\delta$ over the choice of mini-batch
$\mathcal{S}_{b}$, SGD with a learning rate
$\eta\leqslant\frac{\lambda/N}{N\beta(N^{2}\beta+\lambda(b-1)/N)}$ converges
to a global solution in the ball $B(\bm{\theta}_{0},R)$ with exponential
convergence rate

$\displaystyle\mathcal{E}(\bm{\theta}_{k})\leqslant\left(1-\frac{\lambda
b\eta}{N}\right)^{k}\mathcal{E}(\bm{\theta}_{0}).$ (18)

##  5 Experiments

TABLE I:  Generation results on the generic graph datasets. We report the MMD
distances between the test datasets and generated graphs. The best results are
highlighted in bold (the smaller the better). Hyphen (-) denotes out-of-
resources that take more than 10 days or are not applicable due to memory
issues.

|  | Community-small | Enzymes | Grid
---|---|---|---|---
|  | Synthetic, $12\leq|V|\leq 20$ | Real, $10\leq|V|\leq 125$ | Synthetic, $100\leq|V|\leq 400$
|  | Deg.$\downarrow$ | Clus.$\downarrow$ | Orbit$\downarrow$ | Avg.$\downarrow$ | Deg.$\downarrow$ | Clus.$\downarrow$ | Orbit$\downarrow$ | Avg.$\downarrow$ | Deg.$\downarrow$ | Clus.$\downarrow$ | Orbit$\downarrow$ | Avg.$\downarrow$
Autoreg. | DeepGMG [19] | 0.220 | 0.950 | 0.400 | 0.523 | - | - | - | - | - | - | - | -
GraphRNN [9] | 0.080 | 0.120 | 0.040 | 0.080 | 0.017 | 0.043 | 0.021 | 0.043 |  |  |  |
GraphAF [4] | 0.18 | 0.20 | 0.02 | 0.133 | 1.669 | 1.283 | 0.266 | 1.073 | - | - | - | -
GraphDF [20] | 0.06 | 0.12 | 0.03 | 0.070 | 1.503 | 1.061 | 0.202 | 0.922 | - | - | - | -
One-shot | GraphVAE [8] | 0.350 | 0.980 | 0.540 | 0.623 | 1.369 | 0.629 | 0.191 | 0.730 | 1.619 | 0.0 | 0.919 | 0.846
GNF [21] | 0.200 | 0.200 | 0.110 | 0.170 | - | - | - | - | - | - | - | -
EDP-GNN [12] | 0.053 | 0.144 | 0.026 | 0.074 | 0.023 | 0.268 | 0.082 | 0.124 | 0.455 | 0.238 | 0.328 | 0.340
GDSS111It [10] | 0.045 | 0.086 | 0.007 | 0.046 | 0.026 | 0.102 | 0.009 | 0.046 | 0.111 | 0.005 | 0.070 | 0.062
Ours | 0.011 | 0.015 | 0.001 | 0.009 | 0.013 | 0.088 | 0.01 | 0.037 | 0.002 | 0.0 | 0.0 | 0.0007

  * 1

The average results of the Enzymes dataset reported in the GDSS original paper
is 0.032. However, the best result we can obtain using the

author’s released code and checkpoint with careful fine-tuning is 0.046.

In this section, we evaluate our proposed GDSM with state-of-the-art graph
generative baselines on two types of graph generation tasks: generic graph
generation and molecule generation, over several benchmark datasets. We also
conduct extensive ablation studies and visualizations to further illustrate
the effectiveness and efficiency of GDSM.

Figure 3: GSDM enjoys a significantly faster convergence rate than GDSS. On
the community-small dataset, our GSDM reaches the SOTA performance within 100
training epochs.

###  5.1 Generic Graph Generation

Datasets We test our model on three generic datasets with different scales,
and we use $N$ to denote the number of nodes: (1) Community-small $(12\leq
N\leq 20)$: contains 100 small community graphs. (2) Enzymes $(10\leq N\leq
125)$: contains 578 protein graphs which represent the protein tertiary
structures of the enzymes from the BRENDA database. (3) Grid $(100\leq N\leq
400)$: contains 100 standard 2D grid graphs. To fairly compare our model with
baselines, we adopt the experimental and evaluation setting from [9] with the
same train/test split.

Baselines We compare our model with well-known or state-of-the-art graph
generation methods, which can be categorized into auto-regressive models and
one-shot models. The auto-regressive model refers to sequential generation,
which constructs a graph via a set of consecutive steps, usually done nodes by
nodes and edges by edges [14]. Under this category, we include DeepGMG [19],
GraphRNN [9], GraphAF [4], and GraphDF [20]. The one-shot model refers to
building a probabilistic graph model that can generate all nodes and edges in
one shot [14]. Under this category, we include GraphVAE [8], Graph Normalizing
Flow(GNF) [21], EDP-GNN [12], and GDSS [10].

Metrics We adopt the maximum mean discrepancy (MMD) to compare the
distributions of graph statistics, such as the degree, the clustering
coefficient, and the number of occurrences of orbits with 4 nodes [9, 10]
between the same number of generated and test graphs.

TABLE II: Generation results on the QM9 and ZINC250k datasets. Results are the
means of three different runs, and the best results are highlighted in bold.
Values denoted by * are taken from the respective original papers. Other
results are obtained by running open-source codes. Val. w/o corr. denotes the
Validity w/o correction metric, and values that do not exceed 50% are
underlined.

|  | QM9 | ZINC250k
---|---|---|---
| Method | Validity (%)$\uparrow$ | Val. w/o corr. (%)$\uparrow$ | NSPDK$\downarrow$ | FCD$\downarrow$ | Time (s)$\downarrow$ | Validity (%)$\uparrow$ | Val. w/o corr. (%)$\uparrow$ | NSPDK$\downarrow$ | FCD$\downarrow$ | Time (s)$\downarrow$
Autoreg. | GraphAF [4] | 100 | 67* | 0.020 | 5.268 | 2.28$e^{3}$ | 100 | 68* | 0.044 | 16.289 | 5.72$e^{3}$
GraphAF+FC | 100 | 74.43 | 0.021 | 5.625 | 2.32$e^{3}$ | 100 | 68.47 | 0.044 | 16.023 | 5.91$e^{3}$
GraphDF [20] | 100 | 82.67* | 0.063 | 10.816 | 5.08$e^{4}$ | 100 | 89.03* | 0.176 | 34.202 | 5.87$e^{4}$
GraphDF+FC | 100 | 93.88 | 0.064 | 10.928 | 4.72$e^{4}$ | 100 | 90.61 | 0.177 | 33.546 | 5.79$e^{4}$
One-shot | MoFlow [3] | 100 | 91.36 | 0.017 | 4.467 | 4.58 | 100 | 63.11 | 0.046 | 20.931 | 25.9
EDP-GNN [12] | 100 | 47.52 | 0.005 | 2.680 | 4.13$e^{3}$ | 100 | 82.97 | 0.049 | 16.737 | 8.41$e^{3}$
GraphEBM [22] | 100 | 8.22 | 0.030 | 6.143 | 35.33 | 100 | 5.29 | 0.212 | 35.471 | 53.72
GDSS [10] | 100 | 95.72* |  0.003* | 2.900* | 1.06$e^{2}$ | 100 |  97.01* | 0.019* | 14.656* | 2.11$e^{3}$
Ours | 100 | 99.9 | 0.003 | 2.650 | 18.02 | 100 | 92.70 | 0.017 | 12.956 | 45.91

Results We show the results in Table I. The results show that our proposed
GSDM significantly outperforms both the auto-regressive baselines and one-shot
baseline methods. Specifically, GDSS is the SOTA graph diffusion model which
performs the diffusion in the whole space of the graph data. Our method
substantially outperforms GDSS in terms of both average performance and
convergence rate (Figure 3), which demonstrates the advantages of performing
SDEs in the spectrum of the graph compared to the whole space.

###  5.2 Molecules Generation

Besides generic graph generation, our model can also generate organic
molecules through our proposed reverse diffusion process. We test our model
with two well-known molecule datasets: QM9 [23] and ZINC250K [24]. Following
previous works [10, 20], the molecules are kekulized by the RDKit library [25]
with hydrogen atoms removed. We evaluate the quality of 10,000 generated
molecules with Frechet ChemNet Distance (FCD) [26], Neighborhood subgraph
pairwise distance kernel (NSPDK) MMD [27], validity w/o correction, and the
generation time. FCD computes the distance between the testing and the
generated molecules using the activations of the penultimate layer of the
ChemNet. (NSPDK) MMD computes the MMD between the generated and the testing
set which takes into account both the node and edge features for evaluation.
Generally speaking, FCD measures the generation quality in the view of
molecules in the chemical space, while NSPDK MMD evaluates the generation
quality from the graph structure perspective. Besides, following [10], we also
include the validity w/o correction as another metric to explicitly evaluate
the quality of molecule generation prior to the correction procedure. It
computes the fraction of the number of valid molecules without valency
correction or edge resampling over the total number of generated molecules. In
contrast, validity measures the fraction of the valid molecules after the
correction phase. Generation time measures the time for generating 10,000
molecules in the form of RDKit. It is a salient measure of the practicability
of molecule generation, especially for macromolecule generation.

TABLE III:  Ablation study on the $\alpha$-quantile eigenvalues. The metrics
used are the same as in Table 1. The results that surpass the baseline methods
in Table 1 are highlighted in bold (the smaller the better). Avg.% denotes the
percentage of average scores achieved compared to using the whole eigenvalues
and eigenvectors set.

| Community-small | Enzymes | Grid
---|---|---|---
| Synthetic, $12\leq|V|\leq 20$ | Real, $10\leq|V|\leq 125$ | Synthetic, $100\leq|V|\leq 400$
$\alpha$ | Deg.$\downarrow$ | Clus.$\downarrow$ | Orbit$\downarrow$ | Avg.$\downarrow$ | Avg.%$\uparrow$ | Deg.$\downarrow$ | Clus.$\downarrow$ | Orbit$\downarrow$ | Avg.$\downarrow$ | Avg.%$\uparrow$ | Deg.$\downarrow$ | Clus.$\downarrow$ | Orbit$\downarrow$ | Avg.$\downarrow$ | Avg.%$\uparrow$
10% | 1.010 | 1.105 | 0.227 | 0.781 | 0.012 | 0.446 | 0.608 | 0.059 | 0.371 | 0.029 | 1.996 | 0 | 1.013 | 1.003 | 0.001
20% | 0.450 | 1.102 | 0.102 | 0.551 | 0.016 | 0.056 | 0.220 | 0.012 | 0.096 | 0.395 | 1.996 | 0 | 1.013 | 1.003 | 0.001
30% | 0.085 | 0.421 | 0.030 | 0.179 | 0.050 | 0.011 | 0.093 | 0.012 | 0.039 | 0.982 | 0.107 | 0 | 0.044 | 0.050 | 0.012
40% | 0.039 | 0.056 | 0.006 | 0.034 | 0.268 | 0.010 | 0.093 | 0.011 | 0.038 | 1.000 | 0.018 | 0 | 0.001 | 0.006 | 0.095
50% | 0.022 | 0.024 | 0.002 | 0.016 | 0.563 | 0.010 | 0.093 | 0.011 | 0.038 | 1.000 | 0.007 | 0 | 0.001 | 0.002 | 0.225
60% | 0.014 | 0.019 | 0.001 | 0.011 | 0.794 | 0.010 | 0.093 | 0.011 | 0.038 | 1.000 | 0.002 | 0 | 0 | 0.001 | 1.000
70% | 0.012 | 0.019 | 0.001 | 0.011 | 0.844 | 0.010 | 0.093 | 0.011 | 0.038 | 1.000 | 0.002 | 0 | 0 | 0.001 | 1.000
80% | 0.011 | 0.016 | 0.001 | 0.009 | 0.964 | 0.010 | 0.093 | 0.011 | 0.038 | 1.000 | 0.002 | 0 | 0 | 0.001 | 1.000
90% | 0.011 | 0.015 | 0.001 | 0.009 | 1.000 | 0.010 |  0.093 | 0.011 | 0.038 | 1.000 | 0.002 | 0 | 0 | 0.001 | 1.000
100% | 0.011 | 0.015 | 0.001 | 0.009 | 1.000 | 0.010 | 0.093 | 0.011 | 0.038 | 1.000 | 0.002 | 0 | 0 | 0.001 | 1.000

Baselines We compare our model with the state-of-the-art molecule generation
models. The baselines include SOTA auto-regressive models: GraphAF [4] is a
flow-based model, and GraphDF [20] is a flow-based model using discrete latent
variables. Following GDSS [10], we modify the architecture of GraphAF and
GraphDF to consider formal charges in the molecule generation, denoted as
GraphAF+FC and GraphDF+FC, for fair comparisons. For the one-shot model, we
include MoFlow [3], which is a flow-based model; EDP-GNN [12] and GDSS [12]
which are both diffusion models.

Results We show the results in Table II. Evidentally, GSDM achieves the
highest performance under most of the metrics. The highest scores in NSPDK and
FCD show that GSDM is able to generate molecules that have close data
distributions to the real molecules in both the chemical space and graph
space. Especially, our model outperforms GDSS, in most of the metrics,
verifying that our proposed spectral diffusion is not only suitable for
generic graph generation but also advisable for molecule designs. Apart from
the visualization of generated graphs in Figure 2, visualizations of generated
molecules are included in Appendix B.3, showing that the proposed GSDM is
capable of generating generic graphs as well as molecules of high quality.

Time Complexity One of the main advantages of our GSDM compared to other
diffusion models (e.g. EDP-GNN and GDSS) is the efficiency in generating
molecules. We show the time spent (in seconds) for generating 10,000 molecules
in Table II, demonstrating that our GSDM takes a significantly lower time in
the inference process compared to EDP-GNN and GDSS. Especially, compared to
GDSS which requires $1.06e^{3}$ and $2.11e^{3}$ seconds to generate 10,000
molecule graphs according to QM9 and Zinc250k, our model only takes 18.02 and
45.91 seconds, which are $\textbf{58}\times$ and $\textbf{46}\times$ faster
respectively. This phenomenon verifies our methodology in designing the
spectral diffusion that not only the spectral diffusion is more effective than
the whole space diffusion, but also more efficient. Such an improvement is
crucial for numerous applications such as drug design and material analysis.

###  5.3 Ablation Studies

To evaluate the effectiveness of GSDM, we conduct extensive ablation
experiments and display elaborate results and discussions in this section.

Figure 4: Ablation studies on different diffusion step numbers.

Ablation studies on the number of diffusion steps. To analyse the robustness
of our proposed GSDM during the reconstruction procedure (i.e. reverse
diffusion process), we compare the performance of our model with GDSS on
varying numbers of diffusion steps using the Community small and Grid dataset,
which represents small and large generic graphs respectively. The default
steps for our model and GDSS during training and evaluation are 1,000 steps.
Ideally, for diffusion models, with the reduction in step numbers, the
performance of the models decreases, while the model of higher robustness
still exhibits a higher performance under different numbers of diffusion
steps. The results are shown in Figure 4. We can observe that GSDM outperforms
GDSS in both datasets under different diffusion steps. Specifically, in the
Grid dataset, GSDM consistently exhibits significantly higher performance than
GDSS. In the community small dataset, although GSDM and GDSS achieve similar
performance at 50 steps, GSDM becomes much more accurate when the number of
steps is higher than 100.

Figure 5: Ablation studies on diffusion schedules. The y-axis denotes the
average performance score ($\downarrow$) and each column denotes a diffusion
schedule configuration. Each box plot summarizes the results of 5 random
trials.

Ablation studies on the type of diffusion schedules. As mentioned in [13, 28]
and [29], the performance of diffusion models highly relies on the diffusion
schedule, i.e. the scheduled noise insertion process or discretization of
certain types of SDEs, which lies at the heart of both training and inference
phases. According to the taxonomy proposed in [13] and [11], mainstream
artificial diffusion schedules are categorized to be either Variance Exploding
(VE) or Variance Preserving (VP). To improve model robustness against the
choice of diffusion schedules, [29] and [28] designed diffusion models with
optimizable diffusion schedules. In this subsection, we conduct systematic
experiments on several datasets to test the robustness of our proposed GSDM
against different diffusion schedules. As illustrated in Figure 5, the state-
of-the-art performance of our GSDM is immune to the choice of diffusion
schedule and it frees us from tedious hyperparameter searching. When comparing
with GDSS, our GSDM exhibits evidently better average performance with much
smaller variance across various configurations. More results and experiment
details are included in Appendix B.2.

(a) Synthetic-1

(b) Synthetic-2

(c) Synthetic-3

Figure 6: The eigenvalue distribution of 3 synthetic datasets. Figure 7:
Experiments on synthetic datasets of which the eigenvalues’ distributions are
shown in Figure 6. The y-axis denotes the MMD ($\downarrow$) of the adjacency
matrices between the generated graphs to the test graphs.

Ablation studies on low-rank approximations of the score-function. As
mentioned in Section 4.2, one can further accelerate the training and sampling
phases, by confining diffusion to the partial spectrum of the graph adjacency
matrix. Such variants are coined as $\alpha$-quantile GSDM in Section 4.2. In
this experiment, we select the top $[\alpha n]$ eigenvalues to conduct the
sampling process with a well-trained GSDM, where $\alpha$ is chosen from
$\\{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0\\}$. The results are shown in
Table III.

Numerical experiments prove that the low-rank $\alpha$-quantile GSDM retains
the state-of-the-art performance among most of the baseline methods.
Especially, for the Enzymes dataset, by merely preserving the top-30%
eigenvalues and eigenvectors, the $0.3$-quantile GSDM can still retain 98.2%
of the performance of the full GSDM. The ablation study justifies that our
proposed GSDM is capable of capturing essential knowledge that resides on low-
dimensional manifolds. It further demonstrates that $\alpha$-quantile GSDM
enables outstanding scalability for large-scale datasets.

Ablation studies on graphs with different eigenvalues distributions. To
analyze how GSDM performs under graphs with different eigenvalue
distributions, we randomly generate 3 types of synthetic graphs with
eigenvalues distributions shown in Figure 6: synthetic-1 has evenly
distributed eigenvalues, and synthetic-2 and synthetic-2 have moderate and
high distinctions in eigenvalues. Due to the predefined eigenvalue
distributions, the edge values of the synthetic graphs are not limited to
$\\{0,1\\}$. Thus instead of using the metrics presented in Section 5.1, we
directly compute the MMD of the adjacency matrices between the generated
graphs and the test graphs. Corresponding results compared to GDSS are shown
in Figure 7. We also include an ablation variant of GSDM by using only
top-50$\%$ quantile eigenvalues. Both GSDM and its ablation variant outperform
the GDSS model under this synthetic setting.

##  6 Conclusion

In this paper, we present a novel graph diffusion model named GSDM, which
consists of diffusion methods on both graph node features and topologies
through SDEs. Specifically, for graph topology diffusion, we design a novel
spectral diffusion model in GSDM, to improve the accuracy of predicting score
functions, and avoid the pitfalls of the conventional diffusion processes on
graphs. Furthermore, we provide theoretical analysis to justify the advantages
in effectiveness and efficiency of GSDM compared to the standard graph
diffusion. To validate our proposed model, we conducted extensive experiments
showing that our proposed GSDM outperforms the state-of-the-art baseline
methods on both generic graph generation and molecule generation with
significantly higher processing speed.

## References

  * [1] Y. Yang, Z. Feng, M. Song, and X. Wang, “Factorizable graph convolutional networks,” in _NeurIPS_ , 2020, pp. 20 286–20 296.
  * [2] H. Wang, T. Xu, Q. Liu, D. Lian, E. Chen, D. Du, H. Wu, and W. Su, “Mcne: an end-to-end framework for learning multiple conditional network representations of social network,” in _KDD_ , 2019, pp. 1064–1072.
  * [3] C. Zang and F. Wang, “Moflow: an invertible flow model for generating molecular graphs,” in _KDD_ , 2020, pp. 617–626.
  * [4] C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, and J. Tang, “Graphaf: a flow-based autoregressive model for molecular graph generation,” _arXiv preprint arXiv:2001.09382_ , 2020.
  * [5] H. Lee, E. Hyung, and S. J. Hwang, “Rapid neural architecture search by learning to generate graphs from datasets,” _arXiv preprint arXiv:2107.00860_ , 2021.
  * [6] H. Liu, L. Jing, J. Wen, P. Xu, J. Wang, J. Yu, and M. K. Ng, “Interpretable deep generative recommendation models.” _J. Mach. Learn. Res._ , vol. 22, pp. 202–1, 2021.
  * [7] H. Wang, J. Wang, J. Wang, M. Zhao, W. Zhang, F. Zhang, W. Li, X. Xie, and M. Guo, “Learning graph representation with generative adversarial nets,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 33, no. 8, pp. 3090–3103, 2019.
  * [8] M. Simonovsky and N. Komodakis, “Graphvae: Towards generation of small graphs using variational autoencoders,” in _ICANN_ , 2018, pp. 412–422.
  * [9] J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec, “Graphrnn: Generating realistic graphs with deep auto-regressive models,” in _ICMLg_ , 2018, pp. 5708–5717.
  * [10] J. Jo, S. Lee, and S. J. Hwang, “Score-based generative modeling of graphs via the system of stochastic differential equations,” _arXiv preprint arXiv:2202.02514_ , 2022.
  * [11] Y. Song and S. Ermon, _Generative Modeling by Estimating Gradients of the Data Distribution_. Red Hook, NY, USA: Curran Associates Inc., 2019.
  * [12] C. Niu, Y. Song, J. Song, S. Zhao, A. Grover, and S. Ermon, “Permutation invariant graph generation via score-based generative modeling,” in _AISTATS_ , 2020, pp. 4474–4484.
  * [13] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, “Score-based generative modeling through stochastic differential equations,” _arXiv preprint arXiv:2011.13456_ , 2020.
  * [14] X. Guo and L. Zhao, “A systematic survey on deep generative models for graph generation,” _arXiv preprint arXiv:2007.06686_ , 2020.
  * [15] N. De Cao and T. Kipf, “Molgan: An implicit generative model for small molecular graphs,” _arXiv preprint arXiv:1805.11973_ , 2018.
  * [16] T. Ma, J. Chen, and C. Xiao, “Constrained generation of semantically valid graphs via regularizing variational autoencoders,” in _NeurIPS_ , 2018.
  * [17] B. D. Anderson, “Reverse-time diffusion equation models,” _Stochastic Processes and their Applications_ , vol. 12, no. 3, pp. 313–326, 1982.
  * [18] P. Vincent, “A connection between score matching and denoising autoencoders,” _Neural Comput._ , vol. 23, no. 7, p. 1661–1674, Jrul 2011.
  * [19] Y. Li, O. Vinyals, C. Dyer, R. Pascanu, and P. Battaglia, “Learning deep generative models of graphs,” _arXiv preprint arXiv:1803.03324_ , 2018.
  * [20] Y. Luo, K. Yan, and S. Ji, “Graphdf: A discrete flow model for molecular graph generation,” in _ICML_ , 2021, pp. 7192–7203.
  * [21] J. Liu, A. Kumar, J. Ba, J. Kiros, and K. Swersky, “Graph normalizing flows,” in _NeurIPS_ , 2019.
  * [22] M. Liu, K. Yan, B. Oztekin, and S. Ji, “Graphebm: Molecular graph generation with energy-based models,” _arXiv preprint arXiv:2102.00546_ , 2021.
  * [23] R. Ramakrishnan, P. O. Dral, M. Rupp, and O. A. Von Lilienfeld, “Quantum chemistry structures and properties of 134 kilo molecules,” _Scientific data_ , vol. 1, no. 1, pp. 1–7, 2014.
  * [24] J. J. Irwin, T. Sterling, M. M. Mysinger, E. S. Bolstad, and R. G. Coleman, “Zinc: a free tool to discover chemistry for biology,” _Journal of chemical information and modeling_ , vol. 52, no. 7, pp. 1757–1768, 2012.
  * [25] G. Landrum _et al._ , “Rdkit: Open-source cheminformatics software,” 2016\. [Online]. Available: http://www.rdkit.org/
  * [26] K. Preuer, P. Renz, T. Unterthiner, S. Hochreiter, and G. Klambauer, “Fréchet chemnet distance: a metric for generative models for molecules in drug discovery,” _Journal of chemical information and modeling_ , vol. 58, no. 9, pp. 1736–1741, 2018.
  * [27] F. Costa and K. De Grave, “Fast neighborhood subgraph pairwise distance kernel,” in _ICML_ , 2010.
  * [28] A. Nichol and P. Dhariwal, “Improved denoising diffusion probabilistic models,” _CoRR_ , vol. abs/2102.09672, 2021.
  * [29] D. P. Kingma, T. Salimans, B. Poole, and J. Ho, “Variational diffusion models,” _CoRR_ , vol. abs/2107.00630, 2021.
  * [30] C. Liu, L. Zhu, and M. Belkin, “Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning,” _CoRR_ , vol. abs/2003.00307, 2020.

##  Appendix A Proof Details

###  A.1 Proof of Proposition 1

###### Proof.

Plugging $\mathbf{A}_{t}=\mathbf{U}_{0}\bm{\Lambda}_{t}\mathbf{U}_{0}^{\top}$
into (12) yields

$\displaystyle\mathrm{d}\mathbf{A}_{t}=$
$\displaystyle-\frac{1}{2}\sigma_{\Lambda,t}^{2}\mathbf{A}_{t}\mathrm{d}t+\sigma_{\Lambda,t}\mathrm{d}\mathbf{M}_{t},$
$\displaystyle\mathbf{M}_{t}\triangleq$
$\displaystyle\mathbf{U}_{0}\mathbf{W}_{t}^{\Lambda}\mathbf{U}_{0}^{\top}=\mathbf{U}_{0}\cdot\mathrm{diag}(\mathbf{B}_{t}^{\Lambda})\cdot\mathbf{U}_{0}^{\top}.$

Since $(\mathbf{M}_{t})_{t\in\mathbb{R}}$ is a linear transformation of
$(\mathbf{B}_{t}^{\Lambda})_{t\in\mathbb{R}}$, the standard Brownian motion on
$\mathbb{R}^{n}$, hence $(\mathbf{M}_{t})_{t\in\mathbb{R}}$ is a rank-$n$
centered Gaussian process in $\mathbb{R}^{n\times n}$. Moreover,
$\mathbf{M}_{t}$ is characterized by its covariance kernel
$\mathcal{K}(s,t):[0,1]\times[0,1]\mapsto\mathbb{R}^{n\times n\times n\times
n}$, which is given by

$\displaystyle\mathcal{K}(s,t)_{i,j,k,l}$
$\displaystyle\triangleq\mathrm{Cov}(\mathbf{M}_{s}[i,j],\mathbf{M}_{t}[k,l])=\mathbb{E}[\mathbf{M}_{s}[i,j]\mathbf{M}_{t}[k,l]]$
$\displaystyle=\mathbb{E}\left(\sum_{h=1}^{n}\mathbf{U}_{0}[i,h]\mathbf{B}_{s}^{\Lambda}[h]\mathbf{U}_{0}[j,h]\right)\left(\sum_{h=1}^{n}\mathbf{U}_{0}[k,h]\mathbf{B}_{t}^{\Lambda}[h]\mathbf{U}_{0}[l,h]\right)$
$\displaystyle=\mathbb{E}\left(\sum_{h=1}^{n}\mathbf{B}_{s}^{\Lambda}[h]\mathbf{B}_{t}^{\Lambda}[h]\mathbf{U}_{0}[i,h]\mathbf{U}_{0}[j,h]\mathbf{U}_{0}[k,h]\mathbf{U}_{0}[l,h]\right)$
$\displaystyle=\sum_{h=1}^{n}\mathbb{E}(\mathbf{B}_{s}^{\Lambda}[h]\mathbf{B}_{t}^{\Lambda}[h])\mathbf{U}_{0}[i,h]\mathbf{U}_{0}[j,h]\mathbf{U}_{0}[k,h]\mathbf{U}_{0}[l,h]$
$\displaystyle=\min(s,t)\sum_{h=1}^{n}\mathbf{U}_{0}[i,h]\mathbf{U}_{0}[j,h]\mathbf{U}_{0}[k,h]\mathbf{U}_{0}[l,h].$

Notice that (10) is a Ornstein–Uhlenbeck process, which admits a closed-form
solution

$\displaystyle\bm{\Lambda}_{t}=\bm{\Lambda}_{0}e^{-\frac{1}{2}\int_{0}^{t}\sigma_{\tau}^{2}\mathrm{d}\tau}+(1-e^{-\int_{0}^{t}\sigma_{\tau}^{2}\mathrm{d}\tau})\mathbf{W}_{1}^{\Lambda}.$
(19)

Hence, plugging (19) into
$\mathbf{A}_{t}=\mathbf{U}_{0}\bm{\Lambda}_{t}\mathbf{U}_{0}^{\top}$ yields

$\displaystyle\mathbf{A}_{t}=\mathbf{A}_{0}e^{-\frac{1}{2}\int_{0}^{t}\sigma_{\tau}^{2}\mathrm{d}\tau}+(1-e^{-\int_{0}^{t}\sigma_{\tau}^{2}\mathrm{d}\tau})\mathbf{M}_{1}.$
(20)

This completes the proof. ∎

###  A.2 Proof of Proposition 2

In preparation of the main proof, we first establish some technical lemmas.

######  Lemma A.1 (Reconstruction Bound for Generic Diffusion).

We first consider the following oracle reversed time SDE on
$(\mathbb{R}^{d},\|\cdot\|)$

$\mathrm{d}\bar{\mathbf{Z}}_{t}=\left(\mathbf{f}(\bar{\mathbf{Z}}_{t},t)-\sigma_{t}^{2}\nabla_{\mathbf{Z}}\log
p_{t}(\bar{\mathbf{Z}}_{t})\right)\mathrm{d}\bar{t}+\sigma_{t}\mathrm{d}\bar{\mathbf{B}}_{t},\
t\in[0,1],$

and we define the corresponding estimated reverse time SDE as

$\mathrm{d}\widehat{\mathbf{Z}}_{t}=\left(\mathbf{f}(\widehat{\mathbf{Z}}_{t},t)-\sigma_{t}^{2}s_{\bm{\phi}}(\widehat{\mathbf{Z}}_{t},t)\right)\mathrm{d}\bar{t}+\sigma_{t}\mathrm{d}\bar{\mathbf{B}}_{t},\
t\in[0,t],$

where $s_{\bm{\phi}}(\cdot)$ is optimized to predict the Stein score function
$\nabla_{\mathbf{Z}}\log p_{t}(\mathbf{Z}_{t})$ by minimizing the score
matching objective

$\min_{\bm{\phi}}\mathcal{E}(\bm{\phi})\triangleq\mathbb{E}_{\mathbf{Z}}\mathbb{E}_{\mathbf{Z}_{t}|\mathbf{Z}}\|s_{\bm{\phi}}(\mathbf{Z}_{t},t)-\nabla_{\mathbf{Z}}\log
p_{t}(\mathbf{Z}_{t})\|^{2}.$

Then for any $\bm{\phi}$, the construction error is bounded by

$\displaystyle\mathbb{E}\|\mathbf{Z}_{0}-\widehat{\mathbf{Z}}_{0}\|^{2}\leqslant$
$\displaystyle C^{2}\|\sigma_{\cdot}\|_{\infty}^{4}\mathcal{E}(\bm{\phi})$
$\displaystyle\cdot\left(1+\int_{0}^{1}F(t)\exp\left(\int_{t}^{1}F(s)\mathrm{d}s\right)\mathrm{d}t\right),$
(21)

where $F(t)\triangleq
C^{2}\sigma_{t}^{4}\|s_{\bm{\phi}}(\cdot,t)\|_{\mathrm{lip}}^{2}+C\|\mathbf{f}(\cdot,t)\|_{\mathrm{lip}}^{2}$
and $C$ is a constant.

###### Proof of Proposition 2.

Assumptions of Proposition 2 imply

$\displaystyle\|\mathbf{f}(\cdot,t)\|_{\mathrm{lip}}=$
$\displaystyle\frac{1}{2}\sigma_{t}^{2},$
$\displaystyle\|s_{\bm{\phi}}(\cdot,t)\|_{\mathrm{lip}}\leqslant$
$\displaystyle L\cdot\mathbb{E}_{|\mathbf{A}_{0}}\|\nabla\log
p_{t|0}(\widehat{\mathbf{A}}_{t}^{\mathrm{full}})\|_{\mathrm{lip}},$
$\displaystyle\|s_{\bm{\varphi}}(\cdot,t)\|_{\mathrm{lip}}\leqslant$
$\displaystyle L\cdot\mathbb{E}_{|\mathbf{A}_{0}}\|\nabla\log
p_{t|0}(\widehat{\mathbf{A}}_{t}^{\mathrm{spec}})\|_{\mathrm{lip}},$

where $L$ is a constant. According to [11, 13], at each time step $t\in[0,1]$,
the oracle conditional score function $\nabla\log p_{t|0}(\cdot)$ is
equivalent to a mapping that maps the input $d$-dimensional random variable
$\mathbf{Z}_{t}$ to $\Sigma_{t}^{-1}\bm{\varepsilon}$. The shown up
$\bm{\varepsilon}$ is a $d$-dimensional standard Gaussian vector that is
independent to $\mathbf{Z}_{t}$, and $\Sigma_{t}$ is the standard deviation of
$\mathbf{Z}_{t}$, which is given by
$\Sigma_{t}\triangleq\left(1-e^{-\int_{0}^{t}\sigma_{s}^{2}\mathrm{d}s}\right)^{\frac{1}{2}}.$
Thus, the expected Lipschitz norm of oracle conditional score function is
bounded by

$\displaystyle\left(\mathbb{E}_{|\mathbf{A}_{0}}\|\nabla\log
p_{t|0}(\mathbf{Z}_{t})\|_{\mathrm{lip}}\right)^{2}$
$\displaystyle\leqslant\mathbb{E}_{|\mathbf{A}_{0}}\|\nabla\log
p_{t|0}(\mathbf{Z}_{t})\|_{\mathrm{lip}}^{2}$
$\displaystyle\leqslant\frac{\Sigma_{t}^{-2}}{\|\mathbf{Z}_{0}\|^{2}}\mathbb{E}\|\bm{\varepsilon}\|^{2}=\frac{\Sigma_{t}^{-2}d}{\|\mathbf{Z}_{0}\|^{2}}.$
(22)

With Lemma A.1 in hand, we only need to plug (22) into (A.1), by substituting
the notations $(\mathbf{Z},d,\|\cdot\|)$ with
$(\widehat{\mathbf{A}}_{t}^{\mathrm{full}},n^{2},\|\cdot\|_{2,2})$ and
$(\widehat{\bm{\Lambda}}_{t}^{\mathrm{spec}},n,\|\cdot\|_{2,2})$ to bound the
Lipschitz norm of the score networks. This leads us to

$\displaystyle\mathbb{E}\|\mathbf{A}_{0}-\widehat{\mathbf{A}}_{0}^{\mathrm{full}}\|^{2}$
$\displaystyle\leqslant
M\mathcal{E}(\bm{\phi})\cdot\left(1+n^{2}K\cdot\int_{0}^{1}\Sigma_{t}^{-2}\exp\left(n^{2}K\int_{t}^{1}\Sigma_{s}^{-2}\mathrm{d}s\right)\mathrm{d}t\right),$
$\displaystyle\mathbb{E}\|\bm{\Lambda}_{0}-\widehat{\bm{\Lambda}}_{0}^{\mathrm{spec}}\|^{2}$
$\displaystyle\leqslant
M\mathcal{E}(\bm{\phi})\cdot\left(1+nK\cdot\int_{0}^{1}\Sigma_{t}^{-2}\exp\left(nK\int_{t}^{1}\Sigma_{s}^{-2}\mathrm{d}s\right)\mathrm{d}t\right),$

where $M\triangleq C^{2}\|\sigma_{\cdot}\|_{\infty}^{4}$ and $K\triangleq
2ML/\mathbb{E}\|\mathbf{A}_{0}\|_{2,2}$. For the spectral diffusion part, the
final proof step is completed by the fact that

$\displaystyle\mathbb{E}\|\mathbf{A}_{0}\\!-\\!\widehat{\mathbf{A}}_{0}^{\mathrm{spec}}\|^{2}\\!\\!=\\!\mathbb{E}\|\mathbf{U}_{0}\\!\left(\bm{\Lambda}_{0}\\!-\\!\widehat{\bm{\Lambda}}_{0}^{\mathrm{spec}}\right)\\!\mathbf{U}_{0}^{\top}\|^{2}\\!=\\!\mathbb{E}\|\bm{\Lambda}_{0}\\!-\\!\widehat{\bm{\Lambda}}_{0}^{\mathrm{spec}}\|^{2},$
$\displaystyle\mathbb{E}\|\mathbf{A}_{0}\|_{2,2}=\mathbb{E}\|\mathbf{U}_{0}\bm{\Lambda}_{0}\mathbf{U}_{0}^{\top}\|_{2,2}=\mathbb{E}\|\bm{\Lambda}_{0}\|_{2,2}.$

This completes the proof. ∎

###### Proof of Lemma A.1.

To bound the expected reconstruction error
$\mathbb{E}\|\mathbf{Z}_{0}-\widehat{\mathbf{Z}}_{0}\|^{2}$, we first analysis
how $\mathbb{E}\|\bar{\mathbf{Z}}_{t}-\widehat{\mathbf{Z}}_{t}\|^{2}$ evolves
as time $t$ is reversed from $1$ to $0$. By definition, it holds that

$\bar{\mathbf{Z}}_{t}\\!-\\!\widehat{\mathbf{Z}}_{t}\\!=\\!\int_{1}^{t}\\!\\!\left(\mathbf{f}(\bar{\mathbf{Z}}_{s},s)\\!-\\!\mathbf{f}(\widehat{\mathbf{Z}}_{s},s)\right)\\!+\\!\sigma_{s}^{2}\\!\left(s_{\bm{\phi}}(\widehat{\mathbf{Z}}_{s},s)\\!-\\!\nabla_{\mathbf{Z}}\log
p_{s}(\bar{\mathbf{Z}}_{s})\right)\mathrm{d}\bar{s}.$

By taking norm and expectation on both sides, we have

$\displaystyle\mathbb{E}\|\bar{\mathbf{Z}}_{t}-\widehat{\mathbf{Z}}_{t}\|^{2}$
$\displaystyle\leqslant\mathbb{E}\\!\int_{1}^{t}\\!\bigg{\|}\\!\left(\mathbf{f}(\bar{\mathbf{Z}}_{s},s)\\!-\\!\mathbf{f}(\widehat{\mathbf{Z}}_{s},s)\right)\\!+\\!\sigma_{s}^{2}\\!\bigg{(}s_{\bm{\phi}}(\widehat{\mathbf{Z}}_{s},s)\\!-\\!\nabla_{\mathbf{Z}}\log
p_{s}(\bar{\mathbf{Z}}_{s})\\!\bigg{)}\\!\bigg{\|}^{2}\\!\mathrm{d}\bar{s}$
$\displaystyle\leqslant
C\mathbb{E}\int_{1}^{t}\left\|\mathbf{f}(\bar{\mathbf{Z}}_{s},s)-\mathbf{f}(\widehat{\mathbf{Z}}_{s},s)\right\|^{2}\mathrm{d}\bar{s}$
$\displaystyle\;\;\;+C\mathbb{E}\int_{1}^{t}\sigma_{s}^{4}\left\|s_{\bm{\phi}}(\widehat{\mathbf{Z}}_{s},s)-\nabla_{\mathbf{Z}}\log
p_{s}(\bar{\mathbf{Z}}_{s})\right\|^{2}\mathrm{d}\bar{s}$
$\displaystyle\leqslant
C^{2}\int_{1}^{t}\sigma_{s}^{4}\cdot\mathbb{E}\left\|s_{\bm{\phi}}(\widehat{\mathbf{Z}}_{s},s)-s_{\bm{\phi}}(\bar{\mathbf{Z}}_{s},s)\right\|^{2}$
$\displaystyle\;\;\;+\sigma_{s}^{4}\cdot\mathbb{E}\left\|s_{\bm{\phi}}(\bar{\mathbf{Z}}_{s},s)-\nabla_{\mathbf{Z}}\log
p_{s}(\bar{\mathbf{Z}}_{s})\right\|^{2}\mathrm{d}\bar{s}$
$\displaystyle\;\;\;+C\int_{1}^{t}\|\mathbf{f}(\cdot,s)\|_{\mathrm{lip}}^{2}\cdot\mathbb{E}\left\|\bar{\mathbf{Z}}_{s}-\widehat{\mathbf{Z}}_{s}\right\|^{2}\mathrm{d}\bar{s}$
$\displaystyle\leqslant\int_{1}^{t}\underbrace{\left(C^{2}\sigma_{s}^{4}\|s_{\bm{\phi}}(\cdot,s)\|_{\mathrm{lip}}^{2}+C\|\mathbf{f}(\cdot,s)\|_{\mathrm{lip}}^{2}\right)}_{F(s)}\cdot\mathbb{E}\left\|\widehat{\mathbf{Z}}_{s}-\bar{\mathbf{Z}}_{s}\right\|^{2}\mathrm{d}\bar{s}$
$\displaystyle\;\;\;+\underbrace{C^{2}\int_{1}^{t}\sigma_{s}^{4}\mathrm{d}\bar{s}\cdot\mathcal{E}(\bm{\phi})}_{G(t)}.$

The proof is completed by applying the Grönwall’s inequality to
$t\mapsto\mathbb{E}\|\bar{\mathbf{Z}}_{t}-\widehat{\mathbf{Z}}_{t}\|^{2}$,
which yields

$\displaystyle\mathbb{E}\|{\mathbf{Z}}_{0}-\widehat{\mathbf{Z}}_{0}\|^{2}$
$\displaystyle\leqslant
G(0)+\int_{0}^{1}G(t)F(t)\exp\left(\int_{t}^{1}F(s)\mathrm{d}s\right)\mathrm{d}t$
$\displaystyle\leqslant
C^{2}\|\sigma_{\cdot}\|_{\infty}^{4}\mathcal{E}(\bm{\phi})\cdot\left(1+\int_{0}^{1}F(t)\exp\left(\int_{t}^{1}F(s)\mathrm{d}s\right)\mathrm{d}t\right).$

∎

###  A.3 Proof of Proposition 3

###### Proof.

Since
$\mathcal{E}(\bm{\theta})=\mathbb{E}_{\mathcal{S}\sim\mathcal{D}^{N}}\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{N})$,
we only need to bound the empirical risk
$\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{N})$. By assumption, denote

$\displaystyle\mathbf{h}\triangleq\begin{pmatrix}&s_{\bm{\theta}}(\mathbf{Z}^{1}_{0})-\nabla\log
p(\mathbf{Z}^{1}_{0}|\mathbf{Z}^{1}_{1})^{\top}\\\ &\vdots\\\
&s_{\bm{\theta}}(\mathbf{Z}^{N}_{0})-\nabla\log
p(\mathbf{Z}^{N}_{0}|\mathbf{Z}^{N}_{1})^{\top}\end{pmatrix}\in\mathbb{R}^{Nd\times
1},$

It holds that

$\|\nabla_{\bm{\theta}}\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{N})\|^{2}=\frac{1}{N^{2}}\mathbf{h}^{\top}\mathbf{K}_{\bm{\theta}}(\mathcal{S})\mathbf{h}\geqslant\frac{\lambda}{N^{2}}\|\mathbf{h}\|^{2}=\frac{\lambda}{N}\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{N}),$

which implies that $\widehat{\mathcal{E}}(\bm{\theta};\mathcal{S}_{N})$
satisfies the $\frac{\lambda}{N}$-Polyak Łojasiewicz condition [30]. Then the
proof is completed by applying Theorem 7 in [30] to
$\widehat{\mathcal{E}}(\bm{\cdot};\mathcal{S}_{N})$. ∎

##  Appendix B Algorithm and Additional Results

Algorithm 1 Training GSDM via minimizing score-matching objective

Input: Score networks $\mathbf{s}_{\bm{\theta},t}(\cdot)$,
$\mathbf{s}_{\bm{\phi},t}(\cdot)$, maximal diffusion time $T$, drift functions
$\mathbf{f}^{X}(\cdot,t),\mathbf{f}^{\Lambda}(\cdot,t)$, noise schedules
$\sigma_{X,t},\sigma_{\Lambda,t}$, learning rate $\eta$ and training epochs
$K$.
Output: Optimized score network parameters $\bm{\theta}_{K},\bm{\phi}_{K}$.

1: Initialize $\bm{\theta}_{0},\bm{\phi}_{0}$

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

3: $(\mathbf{X}_{0},\mathbf{A}_{0})\sim\mathcal{G}$

4: $\bm{\Lambda}_{0}\leftarrow\mathrm{EigenValues}(\mathbf{A}_{0})$

5: $t\sim\mathrm{Unif}([0,T])$

6:
$\mathbf{X}_{t}\sim\int_{0}^{t}f^{X}(\mathbf{X}_{\tau},\tau)\mathrm{d}\tau+\int_{0}^{t}\sigma_{X,\tau}\mathrm{d}\mathbf{B}^{X}_{\tau}$,
$\bm{\Lambda}_{t}\sim\int_{0}^{t}f^{\Lambda}(\bm{\Lambda}_{\tau},\tau)\mathrm{d}\tau+\int_{0}^{t}\sigma_{\Lambda,\tau}\mathrm{d}\mathbf{B}^{\Lambda}_{\tau}$

7:
$\widehat{\mathcal{E}}(\bm{\theta}_{k})\leftarrow\|s_{\bm{\theta}_{k}}(\mathbf{X}_{t},\bm{\Lambda}_{t})-\nabla\log
p_{t|0}(\mathbf{X}_{t}|\mathbf{X}_{0})\|^{2}$

8:
$\widehat{\mathcal{E}}(\bm{\phi}_{k})\leftarrow\|s_{\bm{\phi}_{k}}(\mathbf{X}_{t},\bm{\Lambda}_{t})-\nabla\log
p_{t|0}(\bm{\Lambda}_{t}|\bm{\Lambda}_{0})\|^{2}$

9:
$(\bm{\theta}_{k+1},\bm{\phi}_{k+1})\leftarrow(\bm{\theta}_{k},\bm{\phi}_{k})-\eta(\nabla\widehat{\mathcal{E}}(\bm{\theta}_{k}),\nabla\widehat{\mathcal{E}}(\bm{\phi}_{k}))$

10: end for

11: Return: $\bm{\theta}_{K},\bm{\phi}_{K}$

Algorithm 2 Sampling via GSDM with VP-SDE predictor-corrector solver

Input: Score-based models $\mathbf{s}_{\bm{\theta},t}(\cdot)$ and
$\mathbf{s}_{\bm{\phi},t}(\cdot)$, maximal diffusion time $T$, number of
sampling steps $M$, Langevin-MCMC step sizes $\\{\epsilon_{i}\\}_{i=1}^{M}$,
noise schedules $\\{\beta_{i}\\}_{i=1}^{M}$ and priori distribution $\pi$.
Output: Generated graph data
$(\widehat{\mathbf{X}}_{0},\widehat{\mathbf{A}}_{0})$

1: $t\leftarrow T$

2: $(\widehat{\mathbf{X}}_{T},\widehat{\bm{\Lambda}}_{T})\sim\pi$,
$\widehat{\mathbf{U}}_{0}\sim\mathrm{Unif}(\\{\mathbf{U}\triangleq\mathrm{EigenVectors}(\mathbf{A}),(\mathbf{X},\mathbf{A})\sim\mathrm{Data}\\})$

3: for $m=M-1$ to $0$ do

4:
$\mathbf{S}_{X}\leftarrow\mathbf{s}_{\bm{\theta},t}(\widehat{\mathbf{X}}_{t},\widehat{\bm{\Lambda}}_{t},\widehat{\mathbf{U}}_{0})$,
$\mathbf{S}_{\Lambda}\leftarrow\mathbf{s}_{\bm{\phi},t}(\widehat{\mathbf{X}}_{t},\widehat{\bm{\Lambda}}_{t},\widehat{\mathbf{U}}_{0})$

5: $t^{\prime}\leftarrow t-T/(2M)$

6:
$\widehat{\mathbf{X}}_{t^{\prime}}\leftarrow(2-\sqrt{1-\beta_{m+1}}\widehat{\mathbf{X}}_{t}+\beta_{m+1}\mathbf{S}_{X})+\sqrt{\beta_{m+1}}\mathbf{z}_{X}$,
$\mathbf{z}_{X}\sim N\left(\bm{0},\mathbf{I}\right)$ {Prediction step:
$\mathbf{X}$}

7:
$\widehat{\bm{\Lambda}}_{t^{\prime}}\leftarrow(2-\sqrt{1-\beta_{m+1}}\widehat{\bm{\Lambda}}_{t}+\beta_{m+1}\mathbf{S}_{\Lambda})+\sqrt{\beta_{m+1}}\mathbf{z}_{\Lambda}$,
$\mathbf{z}_{\Lambda}\sim N\left(\bm{0},\mathbf{I}\right)$ {Prediction step:
$\bm{\Lambda}$}

8:
$\mathbf{S}_{X}\leftarrow\mathbf{s}_{\bm{\theta},t^{\prime}}(\widehat{\mathbf{X}}_{t^{\prime}},\widehat{\bm{\Lambda}}_{t^{\prime}},\widehat{\mathbf{U}}_{0})$,
$\mathbf{S}_{\Lambda}\leftarrow\mathbf{s}_{\bm{\phi},t^{\prime}}(\widehat{\mathbf{X}}_{t^{\prime}},\widehat{\bm{\Lambda}}_{t^{\prime}},\widehat{\mathbf{U}}_{0})$

9: $t\leftarrow t^{\prime}-T/(2M)$

10:
$\widehat{\mathbf{X}}_{t}\leftarrow\widehat{\mathbf{X}}_{t^{\prime}}+\epsilon_{i}\mathbf{S}_{X}+\sqrt{2\epsilon_{i}}\bm{z}_{X}$,
$\mathbf{z}_{X}\sim N\left(\bm{0},\mathbf{I}\right)$ {Correction step:
$\mathbf{X}$}

11:
$\widehat{\bm{\Lambda}}_{t}\leftarrow\widehat{\bm{\Lambda}}_{t^{\prime}}+\epsilon_{i}\mathbf{S}_{\Lambda}+\sqrt{2\epsilon_{i}}\mathbf{z}_{\Lambda}$,
$\mathbf{z}_{\Lambda}\sim N\left(\bm{0},\mathbf{I}\right)$ {Correction step:
$\bm{\Lambda}$}

12: end for

13:
$\widehat{\mathbf{A}}_{0}=\widehat{\mathbf{U}}_{0}\widehat{\bm{\Lambda}}_{0}\widehat{\mathbf{U}}_{0}^{\mathbf{T}}$

14: Return: $(\widehat{\mathbf{X}}_{0},\widehat{\mathbf{A}}_{0})$

###  B.1 Algorithm of GSDM

The pseudo codes of training and sampling with GSDM are summarized in
Algorithm 1 and Algorithm 2. In a nutshell, we first train a GSDM from real
data via minimizing score-matching error. On top of that, we are able to
generate graph features and eigen-values of graph adjacency matrices by
reversing the forward spectral SDE. By uniformly sampling eigen-vectors from
training set, we can construct plausible graph adjacency matrix via spectral
composition.

Figure 8: Diffusion schedules.

Figure 9: Ablation study on the choice of noise schedules.

###  B.2 Ablation study on diffusion schedules

In this section, we empirically verify the robustness of our proposed GSDM
under various types of diffusion schedules. As shown in Figure 8, we design
six representative noise schedules with the same initial and final signal-to-
noise ratio (defined in [13, 28]), while exhibiting different behaviour along
the diffusion process. For both VP- and VE-SDE configurations, we train our
proposed GSDM with six representative noise schedules and we evaluate the
average performance scores. Results on Ego-small and Grid in Figure 9 show
that GSDM is robust to the choice of diffusion schedules, and it is able to
achieve SOTA performance without deliberate noise schedule optimization.

Figure 10: Visualization of molecule generation with maximum Tanimoto
similarity of GSDM comparing to GDSS. The left part shows randomly selected
molecules from the training set of QM9 and Zinc250k. For each generated
molecules, we show the Tanimoto similarity value at the bottom.

###  B.3 Visualization of molecule generations

In Figure 10, we show the generated molecules that are maximally similar to
certain training molecules. We compute the molecule similarity using the
Tanimoto similarity based on the Morgan fingerprints, which are implemented
based on REKit [25]. Higher Tanimoto scores indicate that the model is able to
generate more similar molecules as the training set, which reflects the
learning capability of the model. As shown in the figure, compared to the GDSS
model, GSDM is able to generate molecules that have a more similar
distribution as the molecules in the training set.

|  Tianze Luo received the Bachelor degree (First Class Honours) and the
Master degree from Nanyang Technological University, Singapore, in 2017 and
2019, respectively. He is currently working towards an Alibaba Talent
Programme Ph.D. degree with Alibaba-NTU Joint Research Institute, Nanyang
Technological University, Singapore.
---|---
|  Zhanfeng Mo is currently a Ph.D. student in the School of Computer Science
and Engineering of Nanyang Technological University, Singapore. He received
his Bachelor degree in Statistics from University of Science and Technology of
China in 2020. His main research interests include theory and algorithms of
statistical machine learning.
---|---
|  Sinno Jialin Pan is a Provost’s Chair Professor with Nanyang Technological
University (NTU), Singapore. He received his Ph.D. degree in computer science
from the Hong Kong University of Science and Technology (HKUST) in 2011. Prior
to joining NTU, he was a scientist and Lab Head of text analytics with the
Data Analytics Department, Institute for Infocomm Research, Singapore. He
serves as an Associate Editor for IEEE TPAMI, AIJ, and ACM TIST.
---|---