# Latent Graph Diffusion:
A Unified Framework for Generation and Prediction on Graphs

Cai Zhou  Xiyuan Wang  Muhan Zhang

###### Abstract

In this paper, we propose the first framework that enables solving graph
learning tasks of all levels (node, edge and graph) and all types (generation,
regression and classification) with one model. We first propose Latent Graph
Diffusion (LGD), a generative model that can generate node, edge, and graph-
level features of all categories simultaneously. We achieve this goal by
embedding the graph structures and features into a latent space leveraging a
powerful encoder which can also be decoded, then training a diffusion model in
the latent space. LGD is also capable of conditional generation through a
specifically designed cross-attention mechanism. Then we formulate prediction
tasks including regression and classification as (conditional) generation,
which enables our LGD to solve tasks of all levels and all types with provable
guarantees. We verify the effectiveness of our framework with extensive
experiments, where our models achieve state-of-the-art or highly competitive
results across generation and regression tasks.

Graph generation, theory of latent diffusion model, general purpose graph
model

##  1 Introduction

Graph generation has become of great importance in recent years, with
important applications in many fields, including drug design (Li et al., 2018)
and social network analysis (Grover et al., 2019). However, compared with the
huge success of generative models in natural language processing (Touvron et
al., 2023) and computer vision (Rombach et al., 2021), graph generation is
faced with many difficulties due to the underlying non-Euclidean topological
structures. Existing models fail to generate structures and features
simultaneously (Niu et al., 2020; Jo et al., 2022), or model arbitrary
attributes (Vignac et al., 2022).

Moreover, while general purpose foundation models are built in NLP (Bommasani
et al., 2021) which can solve all types of tasks through the generative
framework, there are no such general purpose models for graph data, since
current graph generative models cannot address regression or classification
tasks. People even have to train separate models for different levels (node,
edge, and graph) of graph learning tasks. Therefore, it is beneficial and
necessary to build a graph model that can solve (a) tasks of all types,
including generation, classification and regression; (b) tasks of all levels,
including node, edge, and graph-level.

##### Our work.

To overcome the difficulties, we propose Latent Graph Diffusion, the first
graph generative framework that is capable of solving tasks of various types
and levels. Our main contributions are summarized as follows.

  * •

We present Latent Graph Diffusion (LGD), which applies a score-based diffusion
generative model in the latent space encoded through a powerful pretrained
graph encoder, thus overcoming the difficulties brought by discrete graph
structures and various feature categories.

  * •

Using a specially designed graph transformer, LGD is able to generate node,
edge, and graph features simultaneously in one shot with all feature types. We
also design a special cross-attention mechanism to enable controllable
generation.

  * •

We conceptually formulate regression and classification tasks as conditional
generation, and theoretically show that latent diffusion models can solve them
with provable guarantees. This unified task formulation enables LGD to perform
both generation and prediction tasks through generative modeling.

  * •

Experimentally, LGD achieves state-of-the-art or highly competitive results
across various tasks, which verifies the effectiveness of our framework.

##  2 Related Work

##### Diffusion models.

Recently, score-based generative models have demonstrated promising
performance across a wide range of generation tasks. These models start by
introducing gradually increasing noise to the data, and then learn the reverse
procedure by estimating the score function, which represents the gradient of
the log-density function with respect to the data. This process allows them to
generate samples effectively. Two notable works in the realm of score-based
generative models are score-matching with Langevin dynamics (SMLD) (Song &
Ermon, 2019) and the denoising diffusion probabilistic model (DDPM) (Ho et
al., 2020). SMLD estimates the score function at multiple noise scales and
generates samples using annealed Langevin dynamics to reduce the noise. In
contrast, DDPM models the diffusion process as a parameterized Markov chain
and learns to reverse the forward diffusion process of adding noise. Song et
al. (2020b) encapsulates SMLD and DDPM within the framework of stochastic
differential equations (SDE). Song & Ermon (2020) and Song et al. (2020a)
further improved the scalability and sampling efficiency of score-based
generative methods. More recently, Stable-Diffusion (Rombach et al., 2021)
applied diffusion models to the latent space encoded by pretrained
autoencoders, significantly improving computational efficiency and the quality
of generated images. Our work has further applied latent space to graph tasks
and also improved the generation quality.

##### Diffusion models for graphs.

In the context of graph data, Niu et al. (2020) were the first to generate
permutation-invariant graphs using score-based methods. They achieved this by
introducing Gaussian perturbations to continuous adjacency matrices. Jo et al.
(2022) took this step further by proposing a method to handle both node
attributes and edges simultaneously using stochastic differential equations
(SDEs). However, these diffusion models rely on continuous Gaussian noise and
do not align well with discrete graph structures. To address this limitation,
Haefeli et al. (2022) designed a diffusion model tailored to unattributed
graphs and observed that discrete diffusion is beneficial for graph
generation. Addressing this issue even more effectively, DiGress (Vignac et
al., 2022), one of the most advanced graph generative models, employs a
discrete diffusion process. This process progressively adds discrete noise to
graphs by either adding or removing edges and altering node categories.
Additionally, Limnios et al. (2023) proposes a method to scale DiGress by
sampling a covering of subgraphs within a divide-and-conquer framework. To
overcome the difficulties, instead of utilizing discrete noise, our work uses
continuous noise in latent space, making our model structure well aligned with
general diffusion models and achieves better performance. Our generative
framework supports both DDPM and SMLD. Given their equivalence in SDE
formulations (Song et al., 2020b), we focus on DDPM and its extensions in our
main text for illustration. More details on SMLD-based methods and SDE
formulations can be found in Appendix A.

##  3 Latent Graph Diffusion

As discussed in Section 1 and Section 2, existing graph diffusion models fail
to generate both graph structures and graph features simultaneously. In this
section, we introduce our novel Latent Graph Diffusion (LGD), a powerful graph
generation framework which is the first to enable simultaneous structure and
feature generation in one shot. Moreover, LGD is capable of generating
features of all levels (node-level, edge-level and graph-level) and all types
(discrete or categorical, continuous or real-valued).

##### Notations.

Given $n\in\mathbb{N}$, let $[n]$ denote $\\{1,2,3,...,n\\}$. For a graph $G$
with $n$ nodes, we denote the node set as ${v_{i}},i\in[n]$, and represent the
node feature of $v_{i}$ as ${\bm{x}}_{i}\in\mathbb{R}^{d_{v}}$. In the context
of node pairs $(v_{i},v_{j})$, there can be either an edge $e_{ij}$ with its
edge feature ${\bm{e}}_{ij}\in\mathbb{R}^{d_{e}}$ or no edge connecting
$v_{i}$ and $v_{j}$. To jointly model the structures and features (of node,
edge, graph level), we treat the case where no edge is observed between
$v_{i}$ and $v_{j}$ as a special edge type. We denote this as $e_{ij}$ with an
augmented feature ${\bm{e}}_{ij}={\bm{e}}^{\prime}\in\mathbb{R}^{d_{e}}$,
where ${\bm{e}}^{\prime}$ is distinct from the features of existing edges,
resulting in a total of $n^{2}$ such augmented edges. We represent all node
features as ${\bm{X}}\in\mathbb{R}^{n\times d_{v}}$ where
${\bm{X}}_{i}={\bm{x}}_{i}$, and augmented edge features as
${\bm{A}}\in\mathbb{R}^{n\times n\times d_{e}}$ where
${\bm{A}}_{i,j}={\bm{e}}_{ij}$ (adjacency matrix with edge features). Graph-
level attributes, denoted ${\bm{g}}\in\mathbb{R}^{d_{g}}$, can be represented
by a virtual node or obtained by pooling over node and edge attributes (see
Section 3.2 for details). For brevity, we temporarily omit graph-level
attributes in the following text. Note that all attributes can be of arbitrary
types, including discrete (categorical) and continuous (real-valued).
Moreover, our methods for solving classification and regression tasks with a
latent diffusion model are generic and can be extended to non-graph data. In a
more general context, we use ${\mathbf{x}}$ to represent the data and
${\mathbf{y}}$ to represent the labels to be predicted.

###  3.1 Overview

Simultaneous generation of structures and features in the original graph space
is challenging due to discrete graph structures and diverse graph features at
various levels and types. Therefore, we apply our graph diffusion models in
the latent space $\mathcal{H}$ rather than operating directly on the original
graphs. Graphs are encoded in the latent space using a powerful pretrained
graph encoder $\mathcal{E}_{\phi}$ parameterized by $\phi$. In this latent
space, all $n$ nodes and $n^{2}$ ”augmented edges” have continuous latent
representations. The node and edge representations are denoted as
${\bm{H}}=({\bm{Z}},{\bm{W}})$, where ${\bm{Z}}\in\mathbb{R}^{n\times d}$ and
${\bm{W}}\in\mathbb{R}^{n\times n\times d}$, with $d$ representing the hidden
dimension.

${\bm{H}}=({\bm{Z}},{\bm{W}})=\mathcal{E}_{\phi}({\bm{X}},{\bm{A}})$ (1)

To recover the graph structures and features from the latent space
$\mathcal{H}$, we employ a light-weight task-specific decoder
$\mathcal{D}_{\xi}$, which is designed to be lightweight and is parameterized
by $\xi$. This decoder produces the final predicted properties of the graph
for specific tasks, including node, edge, and graph-level attributes. It is
important to note that we consider the absence of an edge as a specific type
of edge feature. Furthermore, we can derive graph-level attributes from the
predicted node features $\hat{{\bm{X}}}$ and edge features $\hat{{\bm{A}}}$,
as explained in detail in Section 3.2.

$(\hat{{\bm{X}}},\hat{{\bm{A}}})=\mathcal{D}_{\xi}(\hat{{\bm{H}}})$ (2)

To ensure the quality of generation, the latent space $\mathcal{H}$ must meet
two key requirements: (a) it should be powerful enough to effectively encode
graph information, and (b) it should be conducive to learning a diffusion
model (Rombach et al., 2021), thus should not be too scattered nor high-
dimensional. Consequently, both the architectures and training procedures of
the encoder $\mathcal{E}_{\phi}$ and the decoder $\mathcal{D}_{\xi}$ are of
utmost importance. We will dive into the architecture and training details in
Section 3.2.

After pretraining the encoder and decoder, we get a powerful latent space that
is suitable for training a diffusion model. We can now train the generative
model $\mathbf{\epsilon}_{\theta}$ parametrized by $\theta$ operating on the
latent space. As explained, the generative model could have arbitrary
backbone, including SDE-based and ODE-based methods. For illustration, we
still consider a Denoising Diffusion Probabilistic Model (DDPM) (Ho et al.,
2020), while other generative methods can be analyzed similarly. In the
forward diffusion process, we gradually add Gaussian noise to the latent
representation ${\bm{H}}=({\bm{Z}},{\bm{W}})$ until the latent codes converge
to Gaussian. In the backward denoising process, we use a denoising model
parameterized by $\mathbf{\epsilon}_{\theta}$ parametrized by $\theta$ to
reconstruct the latent representation of the input graph, obtaining
$\hat{{\bm{H}}}$. The network $\theta$ can be a general GNN or graph
transformer, depending on tasks and conditions (see Section 4). In the most
general case, we use a graph transformer enhanced by expanded edges; see
Section 3.3 for architecture and training details.

In conclusion, we have successfully overcome the challenges posed by discrete
graph structures and diverse attribute types by applying a diffusion model in
the latent space. Unlike Niu et al. (2020); Jo et al. (2022), where Gaussian
noise is added directly to the adjacency matrix, our approach of introducing
Gaussian noise is more appropriate within the continuous latent space.
Furthermore, we have addressed the issues of limited graph representation
capacity and restricted transition probabilities, as described in Vignac et
al. (2022) due to the finite categories of nodes and edges. Our method also
differs from Xu et al. (2023), where their model can only generate nodes and
requires additional computations to predict edges based on the generated
nodes. In contrast, our model is the first to be capable of simultaneously
generating all node, edge, and graph-level attributes in a single step.

###  3.2 Autoencoding

##### Architecture.

In principle, the encoder can adopt various architectures, including Graph
Neural Networks (GNNs) and graph transformers. However, to generate structures
and features at all levels effectively, the encoder must be able to represent
node, edge, and graph-level features simultaneously. As discussed in Section
3.1, to generate samples of high quality, the latent space $\mathcal{H}$
should be both powerful and suitable for training a diffusion model. To
fulfill these criteria, we employ a specially designed augmented edge-enhanced
graph transformer throughout this paper, as elaborated in Section 3.3. In
cases where input graph structures and features are complete, we also allow
the use of message-passing-based Graph Neural Networks (MPNNs) and positional
encodings (PEs) during the pretraining stage. However, it is important to note
that these techniques are not applicable during the training of the diffusion
model, as the structures of the noised graphs become corrupted and ill-
defined. Typically, we choose the dimension $d$ of the latent space
$\mathcal{H}$ from the range of $[4,8,16]$. For more discussions of this
choice, see Appendix D.

Since the latent space is already powerful, the decoder can be relatively
simple. The decoder is task-specific, and we pretrain one for each task along
with the encoder. In generation tasks, the decoder is responsible for
recovering the structure and features of the graph. In classification tasks or
regression tasks, it serves as a classifier or regression layer, respectively.
In all cases, we set the decoder for each task as a single linear layer.

##### Training.

Following Rombach et al. (2021) and Xu et al. (2023), we jointly train the
encoder and decoder during the pretraining stage. This training process can be
carried out in an end-to-end manner or similar to training autoencoders. The
training objective encompasses a reconstruction loss and a regularization
penalty.

$\mathcal{L}=\mathcal{L}_{recon}+\mathcal{L}_{reg}$ (3)

The decoder $\mathcal{D}$ reconstructs the input graph from the latent
representation, denoted
$(\hat{\bm{X}},\hat{\bm{A}})=\mathcal{D}({\bm{H}})=\mathcal{D}(\mathcal{E}({\bm{X}},{\bm{A}}))$.
The specific form of the reconstruction loss $\mathcal{L}_{recon}$ depends on
the type of data, such as cross-entropy or Mean Squared Error (MSE) loss. We
can employ masking techniques to encourage the encoder to learn meaningful
representations. It is worth noting that downstream classification or
regression tasks can be seen as a special case of reconstructing the masked
graph; for more details, refer to Section 4.

To prevent latent spaces from having arbitrarily high variance, we apply
regularization. This regularization can take the form of a KL-penalty aimed at
pushing the learned latent representations towards a standard normal
distribution (referred to as KL-reg), similar to the Variational Autoencoder
(VAE) (Kingma & Welling, 2013). Alternatively, we can employ a vector
quantization technique (referred to as VQ-reg), as seen in (van den Oord et
al., 2017; Yang et al., 2023a).

###  3.3 Diffusion model

##### Architecture.

Note that during both the forward and backward diffusion processes, we either
add noise to the latent representations of nodes and edges or attempt to
denoise them. Consequently, the corrupted latent representations do not have a
clear correspondence with the original node and edge information.
Consequently, message-passing neural networks (MPNNs) and similar methods
cannot work, as their operations rely on edges.

To address the ambiguity of edges in the noised graph, we require operations
that do not depend on edge indexes. Graph transformers prove to be suitable in
this context, as they compute attention between every possible node pair and
do not necessitate edge indexes. However, we can still incorporate
representations of augmented edges into the graph transformers through special
design. To facilitate the joint generation of node, edge, and graph-level
attributes, we adopt the most general graph transformer with augmented edge
enhancement. Our model shares a philosophy similar to GRIT (Ma et al., 2023)
and EGT (Hussain et al., 2021). Formally,

${\bm{e}}_{ij}^{l+1}=\sigma\Big{(}\rho\big{(}\kappa({\bm{Q}}{\bm{x}}_{i}^{l},{\bm{K}}{\bm{x}}_{j}^{l})\odot{\bm{E}}_{w}{\bm{e}}_{ij}^{l}\big{)}+{\bm{E}}_{b}{\bm{e}}_{ij}^{l}\Big{)}\in\mathbb{R}^{d^{\prime}}\\\
\alpha_{ij}={\rm
Softmax}_{j\in[n]}({\bm{W}}_{A}{\bm{e}}_{ij}^{l+1})\in\mathbb{R}\\\
{\bm{x}}_{i}^{l+1}=\sum_{j\in[n]}\alpha_{ij}({\bm{V}}{\bm{x}}_{j}^{l}+{\bm{E}}_{v}{\bm{e}}_{ij}^{l+1})\in\mathbb{R}^{d^{\prime}}$
(4)

where $l$ represents the number of attention layers, which has been omitted
for simplicity in the weight matrices. The matrices
${\bm{Q}}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{K}}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{V}}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{E}}_{w}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{E}}_{b}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{W}}_{A}\in\mathbb{R}^{1\times d^{\prime}}$,
${\bm{E}}_{v}\in\mathbb{R}^{d^{\prime}\times d}$ are all learnable weight
matrices in the attention mechanism. The attention kernel $\kappa$ can be an
element-wise addition, as seen in (Ma et al., 2023), or the commonly used
Hadamard product. The symbol $\odot$ denotes the Hadamard product (element-
wise multiplication). The optional non-linear activation function $\sigma$ can
be applied, such as ReLU, or the identity mapping can be used if no non-linear
activation is desired. The function $\rho({\bm{x}})$ is optional and defined
as $\sqrt{{\rm ReLU}({\bm{x}})}-\sqrt{{\rm ReLU}(-{\bm{x}})}$, which aims to
stabilize the training by preventing large magnitudes in the gradients.

To reduce computational complexity, we provide a simplified version where
${\bm{W}}_{A}$ is set to $\mathbf{1}\in\mathbb{R}^{d^{\prime}}$, which
suffices to sum the latent dimension. In this case, the attention mechanism
reduces to the standard inner product if the kernel $\kappa$ is chosen to be
the Hadamard product. Additionally, in simplified attention, ${\bm{E}}_{v}$
can also be set to an identity matrix.

In the edge-enhanced transformer described in Equation 4, we explicitly
maintain representations for all nodes and augmented edges. These
representations are denoted as ${\bm{X}}\in\mathbb{R}^{n\times d}$ and
${\bm{A}}\in\mathbb{R}^{n\times n\times d}$, where ${\bm{X}}_{i}={\bm{x}}_{i}$
and ${\bm{A}}_{i,j}={\bm{e}}_{ij}$, with $d$ being the hidden dimension in the
corresponding layer. The attention mechanism can be naturally extended to a
multi-head case, similar to standard attention. Additionally, residual
connections and feedforward layers can be incorporated for both nodes and
edges. When representing graph-level attributes, we have two options: (a)
utilizing the virtual node trick, where a virtual node is used to represent
the graph-level feature; or (b) obtaining the graph-level feature by pooling
the node/edge features. It is straightforward to verify that Equation 4
exhibits permutation equivariance for both nodes and edges, and permutation
invariance for graph-level attributes.

##### Training and sampling.

Training the latent diffusion model follows a procedure similar to the one
outlined in Appendix A, with the primary distinction being that training is
conducted in the latent space. During this stage, both the encoder and the
decoder remain fixed. Denoting ${\bm{H}}_{0}=\mathcal{E}({\bm{X}},{\bm{A}})$,
in the forward process, we progressively introduce noise to the latent
representation, resulting in ${\bm{H}}_{t}$.

$\mathcal{L}_{LGD}(\epsilon_{\theta}):=\mathbb{E}_{\mathcal{E}({\bm{X}},{\bm{A}}),\epsilon_{t}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\Big{[}||\epsilon_{\theta}({\bm{H}}_{t},t)-\epsilon_{t}||_{2}^{2}\Big{]}$
(5)

where we implement the function $\epsilon_{\theta}^{(t)}$ as described in
Equation 19 using a time-conditional transformer, as detailed in Equation 4.
There is also an equivalent training objective in which the model
$\epsilon_{\theta}$ directly predicts ${\bm{H}}_{0}$ based on ${\bm{H}}_{t}$
and $t$, rather than predicting $\epsilon_{t}$.

$\mathcal{L}_{LGD}(\epsilon_{\theta}):=\mathbb{E}_{\mathcal{E}({\bm{X}},{\bm{A}})}\Big{[}||\epsilon_{\theta}({\bm{H}}_{t},t)-{\bm{H}}_{0}||_{2}^{2}\Big{]}$
(6)

In the inference stage, we directly sample a Gaussian noise in the latent
space $\mathcal{H}$, and sample ${\bm{H}}_{t-1}$ from the generative processes
iteratively as described in Appendix A. After we get the estimated denoised
latent representation $\hat{\bm{H}}_{0}$, we use the decoder to recover the
graph from the latent space, which finishes the generation process.

###  3.4 Conditional generation via cross attention

Similarly to other generative models (Rombach et al., 2021), our LGD is also
capable of controllable generation according to given conditions ${\bm{y}}$ by
modeling conditional distributions $p({\mathbf{h}}|{\bm{y}})$, where
${\mathbf{h}}$ is the random variable representing the entire latent graph
representation for simplicity. This can be implemented with conditional
denoising networks $\epsilon_{\theta}({\mathbf{h}},t,{\bm{y}})$, which take
the conditions as additional inputs. Encoders and decoders can also be
modified to take ${\bm{y}}$ as additional input to shift latent
representations towards the data distribution aligned with the condition
${\bm{y}}$. Xu et al. (2023) simply parameterize the conditioning by
concatenating ${\bm{y}}$ to node features, yet this simple method is limited
to simple conditioning forms and may suffer from lack of expressiveness.
Analogously to (Rombach et al., 2021), we propose to incorporate conditions
through the powerful cross-attention mechanism.

##### General conditions.

Formally, we preprocess ${\bm{y}}$ from various data types and even modalities
(e.g. class labels or molecule properties) using a domain specific encoder
$\tau$, obtaining the latent embedding of the condition
$\tau({\bm{y}})\in\mathbb{R}^{m\times d_{\tau}}$, where $m$ is the number of
conditions and $d_{\tau}$ the hidden dimension. The cross attention is
implemented by

${\bm{x}}^{l+1}_{i}={\rm
softmax}(\frac{({\bm{Q}}_{h}{\bm{x}}^{l}_{i})({\bm{K}}_{h}\tau({\bm{y}}))^{\top}}{\sqrt{d^{\prime}}})\cdot{\bm{V}}_{h}\tau({\bm{y}})\\\
{\bm{e}}^{l+1}_{ij}={\rm
softmax}(\frac{({\bm{Q}}_{e}{\bm{e}}^{l}_{ij})({\bm{K}}_{e}\tau({\bm{y}}))^{\top}}{\sqrt{d^{\prime}}})\cdot{\bm{V}}_{e}\tau({\bm{y}})$
(7)

where ${\bm{Q}}_{h},{\bm{Q}}_{e}\in\mathbb{R}^{d^{\prime}\times d}$,
${\bm{K}}_{h},{\bm{V}}_{h},{\bm{K}}_{e},{\bm{V}}_{e}\in\mathbb{R}^{d^{\prime}\times
d_{\tau}}$ are learnable weight matrices. Residual connections and feedforward
layers are also allowed. The cross-attention mechanism is able to process
multiple conditions with different data structures, and becomes an addition in
the special case where there is only one condition.

The conditional LGD is learned via

$\mathcal{L}_{LGD}:=\mathbb{E}_{\mathcal{E}({\bm{X}},{\bm{A}}),{\bm{y}},\epsilon_{t}\sim\mathcal{N}(\mathbf{0},\mathbf{I}),t}\Big{[}||\epsilon_{\theta}({\bm{H}}_{t},t,\tau({\bm{y}})-\epsilon_{t}||_{2}^{2}\Big{]}$
(8)

if the denoising network is parameterized to predict the noise;
$\epsilon_{\theta}$ can also predict ${\bm{H}}_{0}$ conditioning on
${\bm{H}}_{t},t,\tau({\bm{y}})$ analogous to Equation 6.

##### Masked graph.

Consider the case where we have a graph with part of its features known, and
we want to predict the missing labels which can be either node, edge, or graph
level. For example, in a molecule property prediction task where the molecule
structures and atom/bond types are known, we want to predict its property.
This can be modeled as a problem of predicting a masked graph-level feature
(molecule property) given the node and edge features. In this case, the
condition is the latent representation of a graph that is partially masked. We
denote the features of a partially masked graph as
$({\bm{X}}^{c},{\bm{A}}^{c},{\bm{g}}^{c})$, where the superscript $c$ implies
that the partially masked graph is the “condition”,
${\bm{X}}^{c}_{i}={\bm{x}}^{c}_{i}$, ${\bm{A}}^{c}_{i,j}={\bm{e}}_{ij}^{c}$,
${\bm{g}}^{c}$ are observed node, edge and graph-level features respectively.
The missing labels we aim to predict are denoted as ${\bm{y}}$, then the
complete graph $({\bm{X}},{\bm{A}},{\bm{g}})$ can be recovered by
$({\bm{X}}^{c},{\bm{A}}^{c},{\bm{g}}^{c})$ and ${\bm{y}}$. Intuitively, this
is similar to image inpainting, where we hope to reconstruct the full image
based on a partially masked one. Therefore, we can model the common
classification and regression tasks as a conditional generation, where we want
to predict the label ${\bm{y}}$ (or equivalently, the full graph feature
$({\bm{X}},{\bm{A}},{\bm{g}})$) given the condition
$({\bm{X}}^{c},{\bm{A}}^{c},{\bm{g}}^{c})$, see Section 4 for formal
formulations.

In this case, as the condition is a graph as well (though it might be
partially masked), we propose a novel cross-attention for graphs. We assume
the latent dimension of the conditioning graph and that of the graph to be
generated are identical (otherwise we could use linear layers to project the
features of the conditioning graph), and use characters without superscript
$c$ to denote the graph being generated from noise (the superscript $l$ is
still the number of layer), then

${\bm{e}}_{ij}^{l+1}=\sigma\Big{(}\rho\big{(}\kappa({\bm{Q}}{\bm{x}}_{i}^{l},{\bm{K}}{\bm{x}}_{j}^{c})\odot{\bm{E}}_{w}({\bm{e}}_{ij}^{l}+{\bm{e}}_{ij}^{c})\big{)}\\\
+{\bm{E}}_{b}{\bm{e}}_{ij}^{c}+{\bm{G}}_{e}{\bm{g}}^{c}\Big{)}\in\mathbb{R}^{d^{\prime}}\\\
\alpha_{ij}={\rm
Softmax}_{j\in[n]}({\bm{W}}_{A}{\bm{e}}_{ij}^{l+1})\in\mathbb{R}\\\
{\bm{x}}_{i}^{l+1}=\sum_{j\in[n]}\alpha_{ij}({\bm{V}}{\bm{x}}_{j}^{c}+{\bm{E}}_{v}{\bm{e}}_{ij}^{l+1})+{\bm{W}}_{h}{\bm{x}}_{i}^{c}+{\bm{G}}_{h}{\bm{g}}^{c}\in\mathbb{R}^{d^{\prime}}$
(9)

where learnable weight matrices
${\bm{Q}},{\bm{K}},{\bm{V}},{\bm{E}}_{w},{\bm{E}}_{b}\in\mathbb{R}^{d^{\prime}\times
d}$, ${\bm{W}}_{A}\in\mathbb{R}^{1\times d^{\prime}}$,
${\bm{E}}_{v}\in\mathbb{R}^{d^{\prime}\times d^{\prime}}$, attention kernel
$\kappa$, activation $\sigma$ and signed-square-root operation $\rho$ are
identical to those in Equation 4; the new notations
${\bm{G}}_{e},{\bm{G}}_{v},{\bm{W}}_{h}\in\mathbb{R}^{d^{\prime}\times d}$ are
also learnable weight matrices. The cross-attention Equation 9 and the self-
attention Equation 4 have two major differences: (a) cross-attention uses the
features of the conditioning masked graph as the keys and values of the
attention; (b) to make the model aware of the node/edge correspondence between
the conditioning graph and the main graph to be generated, cross-attention has
a node-wise and edge-wise addition of the conditioning node/edge features
${\bm{x}}_{i}^{c},{\bm{e}}_{ij}^{c}$ to the node/edge features
${\bm{x}}_{i}^{l},{\bm{e}}_{ij}^{l}$ of the main graph. We formally provide
the formulation and training details of modeling regression/classification
tasks as conditional generation given a partially masked graph in Section 4.

##  4 Unified Task Formulation as Graph Generation

Based on graph generative model on the latent space, we can address generation
tasks of all levels (node, edge, and graph) using one LGD model. In this
section, we detail how tasks of different types can be formulated as
generation, thus becoming tractable using one generative model.

###  4.1 Regression and classification as conditional generation

In this subsection, we use the notation ${\mathbf{x}}$ to denote the known
data, and ${\mathbf{y}}$ to denote the labels to be predicted in the task. We
use this unified notation not only for simplicity; actually, the formulation
in this subsection is generic and not limited to graph data. Our framework is
the first to show that diffusion models can provably solve regression and
classification tasks.

From a high-level perspective, unconditional generation aims to model
$p({\mathbf{x}})$, while conditional generation aims to model
$p({\mathbf{x}}|{\mathbf{y}})$. For classification and regression tasks,
traditional deterministic models give point estimates to minimize
classification or regression loss. However, from a generative perspective,
predicting a point estimation is not the only solution; we can also model the
complete conditional distribution $p({\mathbf{y}}|{\mathbf{x}})$. Since
modeling (conditional) distribution is exactly what generative models are
capable of (and good at), it is possible to solve classification and
regression tasks utilizing generative models.

Actually, the classification and regression tasks can be viewed as conditional
generation tasks. Intuitively, we only need to exchange the positions of data
${\mathbf{x}}$ and ${\mathbf{y}}$ in the conditional diffusion model; then we
obtain a diffusion model that approximates $p({\mathbf{y}}|{\mathbf{x}})$. In
this case, we use the data ${\mathbf{x}}$ as the condition and want to
generate ${\mathbf{y}}$ given the condition ${\mathbf{x}}$. We add Gaussian
noise to ${\mathbf{y}}$ in the diffusion process, and we use the denoising
network to reverse the process. In the parameterization where the denoising
network $\epsilon_{\theta}$ directly outputs the target instead of the noise
analogous to Equation 6, i.e.
$\hat{\mathbf{y}}=\epsilon_{\theta}({\mathbf{y}}_{t},t,{\mathbf{x}})$, then
the diffusion objective is

$\mathcal{L}(\epsilon_{\theta}):=\mathbb{E}_{{\mathbf{x}},{\mathbf{y}},t}\Big{[}||\epsilon_{\theta}({\mathbf{y}}_{t},t,{\mathbf{x}})-{\mathbf{y}}||_{2}^{2}\Big{]}$
(10)

It is straightforward to extend the above method to latent diffusion models,
where the only difference is that the diffusion model operates in the latent
space of ${\mathbf{x}},{\mathbf{y}}$. Since the formulation is generic, the
method is also applicable to graph data; see Section 4.2. More details on
formal formulations and theoretical analysis of solving
regression/classification tasks with latent diffusion models are given in
Appendix B.

Converting deterministic tasks such as regression and classification into
generation has potential advantages. First, generative models are capable of
modeling the entire distribution, thus being able to provide information
confidence interval or uncertainty by multiple predictions; in comparison,
traditional deterministic models can only give point estimates. Empirically,
generative models are often observed to have larger capacity and generalize
well on large datasets. Specifically for latent diffusion models, since the
generative process is performed in the expressive latent space, the training
of diffusion models could be much faster than training a deterministic model
from scratch, and we obtain a powerful representation of the data that can be
used in other downstream tasks. Moreover, now that the deterministic tasks
could be unified with generation, thus can be simultaneously addressed by one
unified model, which is the precondition of training a foundation model. We
refer readers to Section 5 and Appendix D for detailed experimental
observations.

###  4.2 Generation and prediction with LGD

Now we summarize our Latent Graph Diffusion framework, which is able to (1)
solve tasks of all types, including generation, regression, and classification
through the framework of graph generation; and (2) solve tasks of all levels,
including node, edge and graph level,

First, since LGD is an internally generative model, it is able to perform
unconditional and conditional generation as discussed in Section 3. For
nongenerative tasks including regression and classification, we formulate them
into conditional generation in Section 4.1, thus can also be solved by our LGD
model. In particular for graph data, we want to predict the labels ${\bm{y}}$
which can be node, edge, or graph level and of arbitrary types, given the
condition of a partially observed graph
${\bm{X}}^{c},{\bm{A}}^{c},{\bm{g}}^{c}$. To better align with the second
target of full graph generation, we model this problem as predicting
$p({\bm{X}},{\bm{A}},{\bm{g}}|{\bm{X}}^{c},{\bm{A}}^{c},{\bm{g}}^{c})$, where
$({\bm{X}},{\bm{A}},{\bm{g}})=({\bm{X}}^{c},{\bm{A}}^{c},{\bm{g}}^{c},{\bm{y}})$
is the full graph feature that combines the observed conditions and the labels
to be predicted. In other words, the condition can be viewed as a partially
masked graph whose masked part is the labels ${\bm{y}}$, and our task becomes
graph inpainting, i.e. generate full graph features conditioning on partially
masked features.

Now we have formulated all tasks as generative modeling. The feasibility of
the second goal to predict all-level features is naturally guaranteed by the
ability of our augmented-edge enhanced transformer architecture described in
Section 3. We leave the discussion of the possibility of solving tasks from
different domains to Appendix C.

##  5 Experiments

###  5.1 Generation task

We first conduct experiments on traditional generation tasks to verify the
effectiveness of our Latent Graph Diffusion model. We consider both
unconditional generation and conditional generation tasks.

####  5.1.1 Unconditional generation

##### Datasets and evaluation metrics.

For both unconditional and conditional generation, we use QM9 (Ramakrishnan et
al., 2014), one of the most widely adopted datasets in molecular machine
learning research, which is suitable for both generation and regression tasks.
QM9 contains both graph and 3D structures together with several quantum
properties for 130k small molecules, limited to 9 heavy atoms. In our
experiments, we do not consider 3D information for our LGD, but it still
outperforms the 3D baselines.

In the unconditional molecular modeling and generation task, we measure the
model’s ability to learn the distribution of molecular data and generate
molecules that are both chemically valid and structurally diverse. Following
the common setting (Xu et al., 2023), we report the validity and uniqueness,
which are the percentages of valid (measured by RDKIT) and unique molecules
among the generated molecules. We generate 10k molecules for each method. We
leave further discussions on relaxed validity (Jo et al., 2022) and novelty in
Appendix D.

Table 1: Unconditional generation results on QM9. Shown is the mean $\pm$ std
of 3 runs with different random seeds.

Model | Validitiy (%) | Uniqueness (%) | Valid & Unique (%)
---|---|---|---
Set2GraphVAE | 59.9 | 93.8 | 56.2
SPECTRE | 87.3 | 35.7 | 31.2
GraphNVP | 83.1 | 99.2 | 82.4
GDM-Aug* | 90.4 | 99.0 | 89.5
EDM* | 91.9 | 98.6 | 90.7
GeoLDM* | 93.8 | 98.8 | 92.7
LGD (ours) |  95.5$\pm$ 0.4 | 97.7$\pm$ 0.5 |  93.3 $\pm$ 0.5

##### Baselines.

For baseline models, we select one-shot (non-autoregressive) generative
models, including Set2GraphVAE (Vignac & Frossard, 2022), SPECTRE (Martinkus
et al., 2022), GraphNVP (Madhawa et al., 2019). We also compare with 3D
generative models which use 3D coordinates of the molecules, including GDM-Aug
(Hoogeboom et al., 2022), EDM (Hoogeboom et al., 2022), GeoLDM (Xu et al.,
2023). Generating with 3D information is much easier, thus it shall not be
directly comparable with generative models without 3D information, so we use *
to mark out these 3D methods in Table 1. The baseline results are adopted from
corresponding papers.

##### Results.

The results are shown in Table 1. Our model achieves the best results in both
validity and joint evaluation of validity & uniqueness. This verifies the
advantages of our latent diffusion model and the ability to generate nodes and
edges simultaneously. It is worth mentioning that our LGD works in a much more
difficult setting compared with GeoLDM (Xu et al., 2023). First, LGD generates
both atoms (nodes) and bonds (edges) simultaneously in one shot, while GeoLDM
only generates atoms (nodes), and then computes bonds (edges) according to
pair-wise atomic distances and atom types. Second, we do not use any 3D
information. Despite the hard setting, LDG still achieves better results in
validity, which verifies the effectiveness of our framework.

####  5.1.2 Conditional generation

##### Datasets and evaluation metrics.

We still use the QM9 dataset for our conditional generation task, where we aim
to generate target molecules with the desired chemical properties. We follow
the settings of (Xu et al., 2023) and split the training set into two parts,
each containing 50k molecules. We train the latent diffusion model and
separate property prediction networks $\omega$ (with architectures described
in Equation 4) on two halves, respectively. For evaluation, we first generate
samples using the latent diffusion model given the conditioning property $y$,
and use $\omega$ to predict the property $\hat{y}$ of the generated molecules.
We measure the Mean Absolute Error between $y$ and $\hat{y}$, and experiment
with six properties: Dipole moment $\mu$, polarizability $\alpha$, orbital
energies $\epsilon_{HOMO},\epsilon_{LUMO}$ and their gap $\Delta\epsilon$, and
heat capacity $C_{v}$.

##### Baselines.

We report EDM (Hoogeboom et al., 2022) and GeoLDM (Xu et al., 2023) as
baseline models. We also incorporate (a) the MAE of the regression model
$\omega$ of ours and (Xu et al., 2023), which can be viewed as a lower bound
of the generative models; (b) Random, which shuffle the labels and evaluate
$\omega$, thus can be viewed as the upper bound of the MAE metric; (c) $N_{\rm
atoms}$, which predicts the properties based only on the number of atoms in
the molecule.

Table 2: Conditional generation results on QM9 (MAE $\downarrow$)

Model | $\mu$ | $\alpha$ | $\epsilon_{\textrm{HOMO}}$ | $\epsilon_{\textrm{LUMO}}$ | $\Delta\epsilon$ | $c_{\textrm{v}}$
---|---|---|---|---|---|---
$\omega$ (Xu et al., 2023) | 0.043 | 0.10 | 39 | 36 | 64 | 0.040
$\omega$ (ours) | 0.058 | 0.06 | 18 | 24 | 28 | 0.038
Random | 1.616 | 9.01 | 645 | 1457 | 1470 | 6.857
$N_{\rm atom}$ | 1.053 | 3.86 | 426 | 813 | 866 | 1.971
EDM | 1.111 | 2.76 | 356 | 584 | 655 | 1.101
GeoLDM | 1.108 | 2.37 | 340 | 522 | 587 | 1.025
LGD | 0.879 | 2.43 | 313 | 641 | 586 | 1.002

##### Results.

As shown in Table 2, even if we do not use 3D information and generate both
atoms and bonds in one simultaneously, LGD achieves the best results in 4 out
of 6 properties. The results verify the excellent controllable generation
capacity of LGD.

###  5.2 Prediction with conditional generative models

In this subsection, we show that utilizing our unified formulation, our LGD
can also perform well on prediction tasks, including regression and
classification. To the best of our knowledge, we are the first to address
regression and classification tasks with a generative model efficiently.

####  5.2.1 Regression

##### Datasets and evaluation metrics.

For regression task, we select ZINC12k (Dwivedi et al., 2020), which is a
subset of ZINC250k containing 12k molecules. The task is molecular property
(constrained solubility) regression, measured by MAE. We use the official
split of the dataset.

##### Baselines.

Note that we are the first to use generative models to perform regression
tasks, therefore no comparable generative models can be selected as baselines.
Therefore, we choose traditional regression models, including GIN (Xu et al.,
2018), PNA (Corso et al., 2020), DeepLRP (Chen et al., 2020), OSAN (Qian et
al., 2022), KP-GIN+ (Feng et al., 2022), GNN-AK+ (Zhao et al., 2021), CIN
(Bodnar et al., 2021) and GPS (Rampásek et al., 2022) for comparison.

##### Results.

We train our LGD model and test inference with both DDPM and DDIM methods.
While the generated predictions are not deterministic, we only predict once
for each graph for a fair comparison with deterministic regression models. We
will show in Appendix D that ensemble techniques can further improve the
quality of prediction. As shown in Table 3, LDM (with DDPM) achieves the best
results, even outperforming the powerful graph transformers GPS (Rampásek et
al., 2022). We observe that inference with DDIM is much faster, but may lead
to a performance drop, which aligns with previous observations (Song et al.,
2020a; Cao et al., 2023). Moreover, our LGD requires much less training steps
compared with GraphGPS, see Appendix D for more detailed discussions on
experimental findings.

Table 3: Zinc12K results (MAE $\downarrow$). Shown is the mean $\pm$ std of 5
runs.
Method | Test MAE
---|---
GIN | $0.163\pm 0.004$
PNA | $0.188\pm 0.004$
GSN | $0.115\pm 0.012$
DeepLRP | $0.223\pm 0.008$
OSAN | $0.187\pm 0.004$
KP-GIN+ | $0.119\pm 0.002$
GNN-AK+ | $0.080\pm 0.001$
CIN | $0.079\pm 0.006$
GPS | $0.070\pm 0.004$
LGD-DDIM (ours) | $0.081\pm 0.006$
LGD-DDPM (ours) | $\textbf{0.065}\pm 0.003$

####  5.2.2 Classification

##### Datasets and evaluationg metrics.

For classification task, we choose ogbg-molhiv (Hu et al., 2020), which
contains 41k molecules. The task is a graph binary classification to predict
whether a molecule inhibits HIV virus replication or not, and the metric is
AUC. We use the official split of the dataset.

##### Baselines.

For ogbg-mohiv, PNA (Corso et al., 2020), DeepLRP (Chen et al., 2020), NGNN
(Zhang & Li, 2021), KP-GIN (Feng et al., 2022), $I^{2}$-GNN (Huang et al.,
2022), CIN (Bodnar et al., 2021) and SUN(EGO) (Frasca et al., 2022) are
selected as baselines.

##### Results.

As shown in Table 4, LGD reveal comparable performance compared with state-of-
the-art models. A possible reason is that ogbg-molhiv adopts scaffold split
which is not a random split method, leading to imbalance samples in
train/validation/test sets. As generative models directly model the
distribution, a distribution shift may negatively influence the performance.

Table 4: ogbg-molhiv results (AUC $\uparrow$). Shown is the mean $\pm$ std of
5 runs.
Method | Test AUC
---|---
PNA | $79.05\pm 1.32$
DeepLRP | $77.19\pm 1.40$
NGNN | $78.34\pm 1.86$
KP-GIN+-VN | $78.40\pm 0.87$
$I^{2}$ -GNN | $78.68\pm 0.93$
CIN | $\textbf{80.94}\pm 0.57$
SUN(EGO) | $80.03\pm 0.55$
GPS | $78.80\pm 1.01$
LGD-DDPM (ours) | $78.49\pm 0.96$

##  6 Conclusions

We propose Latent Graph Diffusion (LGD), the first graph generative framework
that is capable of solving tasks of all types (generation, regression and
classification) and all levels (node, edge, and graph). We encode the into a
powerful latent space and train a latent diffusion model to generate graph
representations with high qualities. Leveraging specially designed graph
transformer architectures and cross-attention mechanisms, LGD can generate
node, edge, and graph features simultaneously in both unconditional or
conditional settings. We further formulate regression and classification tasks
as conditional generation, and show that latent diffusion models can complete
them with provable theoretical guarantees. We experimentally show that LGD is
not only capable of completing these tasks of different types and levels, but
also capable of achieving extremely competitive performances. We believe that
our work is a huge step towards building graph foundation models, and hope
that it could inspire more extensive future research.

## Impact statements

The goal of this paper is to advance the field of Machine Learning. There are
some potential societal consequences of our work, none of which we feel must
be specifically highlighted here.

## References

  * Benton et al. (2023) Benton, J., Deligiannidis, G., and Doucet, A.  Error bounds for flow matching methods.  _ArXiv_ , abs/2305.16860, 2023.  URL https://api.semanticscholar.org/CorpusID:258947044.
  * Bodnar et al. (2021) Bodnar, C., Frasca, F., Otter, N., Wang, Y. G., Lio’, P., Montúfar, G., and Bronstein, M. M.  Weisfeiler and lehman go cellular: Cw networks.  In _Neural Information Processing Systems_ , 2021.
  * Bommasani et al. (2021) Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Cao et al. (2023) Cao, Y., Chen, J., Luo, Y., and ZHOU, X.  Exploring the optimal choice for generative processes in diffusion models: Ordinary vs stochastic differential equations.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=1mJQq6zYaE.
  * Chen et al. (2023) Chen, M., Huang, K., Zhao, T., and Wang, M.  Score approximation, estimation and distribution recovery of diffusion models on low-dimensional data.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 4672–4712. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/chen23o.html.
  * Chen et al. (2022) Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R.  Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions.  _arXiv preprint arXiv:2209.11215_ , 2022.
  * Chen et al. (2020) Chen, Z., Chen, L., Villar, S., and Bruna, J.  Can graph neural networks count substructures?  _CoRR_ , abs/2002.04025, 2020.  URL https://arxiv.org/abs/2002.04025.
  * Corso et al. (2020) Corso, G., Cavalleri, L., Beaini, D., Lio’, P., and Velickovic, P.  Principal neighbourhood aggregation for graph nets.  _ArXiv_ , abs/2004.05718, 2020.
  * Dan et al. (2023) Dan, T., Ding, J., Wei, Z., Kovalsky, S. Z., Kim, M., Kim, W. H., and Wu, G.  Re-think and re-design graph neural networks in spaces of continuous graph diffusion functionals.  2023\.
  * Deveney et al. (2023) Deveney, T., Stanczuk, J., Kreusser, L. M., Budd, C., and Schonlieb, C.-B.  Closing the ode-sde gap in score-based diffusion models through the fokker-planck equation.  _ArXiv_ , abs/2311.15996, 2023.  URL https://api.semanticscholar.org/CorpusID:265456014.
  * Dwivedi et al. (2020) Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X.  Benchmarking graph neural networks.  _ArXiv_ , abs/2003.00982, 2020.
  * Feng et al. (2022) Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M.  How powerful are k-hop message passing graph neural networks.  _ArXiv_ , abs/2205.13328, 2022.
  * Frasca et al. (2022) Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H.  Understanding and extending subgraph gnns by rethinking their symmetries.  _ArXiv_ , abs/2206.11140, 2022.
  * Grover et al. (2019) Grover, A., Zweig, A., and Ermon, S.  Graphite: Iterative generative modeling of graphs.  In _International conference on machine learning_ , pp. 2434–2444. PMLR, 2019.
  * Haefeli et al. (2022) Haefeli, K. K., Martinkus, K., Perraudin, N., and Wattenhofer, R.  Diffusion models for graphs benefit from discrete state spaces.  _ArXiv_ , abs/2210.01549, 2022.
  * Ho et al. (2020) Ho, J., Jain, A., and Abbeel, P.  Denoising diffusion probabilistic models.  _ArXiv_ , abs/2006.11239, 2020.
  * Hoogeboom et al. (2022) Hoogeboom, E., Satorras, V. G., Vignac, C., and Welling, M.  Equivariant diffusion for molecule generation in 3d.  _ArXiv_ , abs/2203.17003, 2022.  URL https://api.semanticscholar.org/CorpusID:247839510.
  * Hu et al. (2019) Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V. S., and Leskovec, J.  Strategies for pre-training graph neural networks.  _arXiv: Learning_ , 2019.
  * Hu et al. (2020) Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J.  Open graph benchmark: Datasets for machine learning on graphs.  _ArXiv_ , abs/2005.00687, 2020.
  * Huang et al. (2022) Huang, Y., Peng, X., Ma, J., and Zhang, M.  Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs.  _arXiv e-prints_ , art. arXiv:2210.13978, October 2022.  doi: 10.48550/arXiv.2210.13978.
  * Hussain et al. (2021) Hussain, M. S., Zaki, M. J., and Subramanian, D.  Global self-attention as a replacement for graph convolution.  _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2021.  URL https://api.semanticscholar.org/CorpusID:249375304.
  * Jo et al. (2022) Jo, J., Lee, S., and Hwang, S. J.  Score-based generative modeling of graphs via the system of stochastic differential equations.  In _International Conference on Machine Learning_ , 2022.
  * Kingma & Welling (2013) Kingma, D. P. and Welling, M.  Auto-encoding variational bayes.  _CoRR_ , abs/1312.6114, 2013.
  * Lee et al. (2022) Lee, H., Lu, J., and Tan, Y.  Convergence of score-based generative modeling for general data distributions.  _ArXiv_ , abs/2209.12381, 2022.  URL https://api.semanticscholar.org/CorpusID:252531877.
  * Li et al. (2023a) Li, A. C., Prabhudesai, M., Duggal, S., Brown, E. L., and Pathak, D.  Your diffusion model is secretly a zero-shot classifier.  _ArXiv_ , abs/2303.16203, 2023a.  URL https://api.semanticscholar.org/CorpusID:257771787.
  * Li et al. (2023b) Li, P., Li, Z., Zhang, H., and Bian, J.  On the generalization properties of diffusion models.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023b.  URL https://openreview.net/forum?id=hCUG1MCFk5.
  * Li et al. (2018) Li, Y., Zhang, L., and Liu, Z.  Multi-objective de novo drug design with conditional graph generative model.  _Journal of cheminformatics_ , 10:1–24, 2018.
  * Limnios et al. (2023) Limnios, S., Selvaraj, P., Cucuringu, M., Maple, C., Reinert, G., and Elliott, A.  Sagess: Sampling graph denoising diffusion model for scalable graph generation.  _ArXiv_ , abs/2306.16827, 2023.
  * Liu et al. (2022) Liu, X., Gong, C., and Liu, Q.  Flow straight and fast: Learning to generate and transfer data with rectified flow.  _ArXiv_ , abs/2209.03003, 2022.  URL https://api.semanticscholar.org/CorpusID:252111177.
  * Ma et al. (2023) Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P. H. S., and Lim, S. N.  Graph inductive biases in transformers without message passing.  _ArXiv_ , abs/2305.17589, 2023.
  * Madhawa et al. (2019) Madhawa, K., Ishiguro, K., Nakago, K., and Abe, M.  Graphnvp: An invertible flow model for generating molecular graphs.  _arXiv preprint arXiv:1905.11600_ , 2019.
  * Martinkus et al. (2022) Martinkus, K., Loukas, A., Perraudin, N., and Wattenhofer, R.  SPECTRE: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 15159–15179. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/martinkus22a.html.
  * Niu et al. (2020) Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S.  Permutation invariant graph generation via score-based generative modeling.  In _International Conference on Artificial Intelligence and Statistics_ , 2020.
  * Qian et al. (2022) Qian, C., Rattan, G., Geerts, F., Morris, C., and Niepert, M.  Ordered subgraph aggregation networks.  _ArXiv_ , abs/2206.11168, 2022.
  * Ramakrishnan et al. (2014) Ramakrishnan, R., Dral, P. O., Rupp, M., and von Lilienfeld, O. A.  Quantum chemistry structures and properties of 134 kilo molecules.  _Scientific Data_ , 1, 2014.
  * Rampásek et al. (2022) Rampásek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D.  Recipe for a general, powerful, scalable graph transformer.  _ArXiv_ , abs/2205.12454, 2022.
  * Rombach et al. (2021) Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B.  High-resolution image synthesis with latent diffusion models.  _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 10674–10685, 2021.
  * Song et al. (2020a) Song, J., Meng, C., and Ermon, S.  Denoising diffusion implicit models.  _ArXiv_ , abs/2010.02502, 2020a.
  * Song & Ermon (2019) Song, Y. and Ermon, S.  Generative modeling by estimating gradients of the data distribution.  _ArXiv_ , abs/1907.05600, 2019.
  * Song & Ermon (2020) Song, Y. and Ermon, S.  Improved techniques for training score-based generative models.  _ArXiv_ , abs/2006.09011, 2020.
  * Song et al. (2020b) Song, Y., Sohl-Dickstein, J. N., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B.  Score-based generative modeling through stochastic differential equations.  _ArXiv_ , abs/2011.13456, 2020b.
  * Touvron et al. (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * van den Oord et al. (2017) van den Oord, A., Vinyals, O., and Kavukcuoglu, K.  Neural discrete representation learning.  _ArXiv_ , abs/1711.00937, 2017.
  * Vignac & Frossard (2022) Vignac, C. and Frossard, P.  Top-n: Equivariant set and graph generation without exchangeability.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=-Gk_IPJWvk.
  * Vignac et al. (2022) Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P.  Digress: Discrete denoising diffusion for graph generation.  _ArXiv_ , abs/2209.14734, 2022.
  * Xu et al. (2018) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  _ArXiv_ , abs/1810.00826, 2018.
  * Xu et al. (2023) Xu, M., Powers, A., Dror, R. O., Ermon, S., and Leskovec, J.  Geometric latent diffusion models for 3d molecule generation.  In _International Conference on Machine Learning_ , 2023.  URL https://api.semanticscholar.org/CorpusID:258436871.
  * Yang et al. (2023a) Yang, L., Tian, Y., Xu, M., Liu, Z., Hong, S., Qu, W., Zhang, W., Zhang, B. C. M., and Leskovec, J.  Vqgraph: Graph vector-quantization for bridging gnns and mlps.  _ArXiv_ , 2023a.
  * Yang et al. (2023b) Yang, R., Yang, Y., Zhou, F., and Sun, Q.  Directional diffusion models for graph representation learning.  _ArXiv_ , abs/2306.13210, 2023b.
  * Yuan et al. (2023) Yuan, H., Huang, K., Ni, C., Chen, M., and Wang, M.  Reward-directed conditional diffusion: Provable distribution estimation and reward improvement.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=58HwnnEdtF.
  * Zhang & Li (2021) Zhang, M. and Li, P.  Nested graph neural networks.  _ArXiv_ , abs/2110.13197, 2021.
  * Zhao et al. (2021) Zhao, L., Jin, W., Akoglu, L., and Shah, N.  From stars to subgraphs: Uplifting any gnn with local structure awareness.  _ArXiv_ , abs/2110.03753, 2021.

##  Appendix A Background on Diffusion Models

In this section we provide more background knowledge on diffusion models,
including formal formulation of the families of DDPM (Ho et al., 2020) and
SMLD (Song & Ermon, 2019) methods, as well as their unified formulation
through the framework of SDE (Song et al., 2020b) or ODE (Song et al., 2020a).

###  A.1 Denoising diffusion probabilistic models

Given samples from the ground truth data distribution $q({\mathbf{x}}_{0})$,
generative models aim to learn a model distribution
$p_{\theta}({\mathbf{x}}_{0})$ that approximates $q({\mathbf{x}}_{0})$ well
and is easy to sample from. Denoising dffusion probabilistic models (DDPMs)
(Ho et al., 2020) are a family of latent variable models of the form

$p_{\theta}({\mathbf{x}}_{0})=\int p_{\theta}({\mathbf{x}}_{0:T}){\rm
d}{\mathbf{x}}_{1:T}$ (11)

where

$p_{\theta}({\mathbf{x}}_{0:T}):=p_{\theta}({\mathbf{x}}_{T})\prod_{t=1}^{T}p_{\theta}^{(t)}({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t})$
(12)

here ${\mathbf{x}}_{1},\dots,{\mathbf{x}}_{T}$ are latent variables in the
same sample space (denoted as $\mathcal{X}$) as the data ${\mathbf{x}}_{0}$.

A special property of diffusion models is that the approximate posterior
$q({\mathbf{x}}_{1:T}|{\mathbf{x}}_{0})$, also called the forward process or
diffusion process, is a fixed Markov chain which gradually adds Gaussian noise
to the data according to a variance schedule $\beta_{1},\dots,\beta_{T}$:

$q({\mathbf{x}}_{1:T}|{\mathbf{x}}_{0}):=\prod_{t=1}^{T}q({\mathbf{x}}_{t}|{\mathbf{x}}_{t-1})$
(13)

where

$q({\mathbf{x}}_{t}|{\mathbf{x}}_{t-1}):=\mathcal{N}({\mathbf{x}}_{t};\sqrt{1-\beta_{t}}{\mathbf{x}}_{t-1},\beta\mathbf{I})$
(14)

The forward process variance $\beta_{t}$ can either be held constant as
hyperparameters, or learned by reparameterization (Ho et al., 2020). One
advantage of the above parameterization is that sampling ${\mathbf{x}}_{t}$ at
an arbitrary timestep $t$ has a closed form,

$q({\mathbf{x}}_{t}|{\mathbf{x}}_{0})=\mathcal{N}({\mathbf{x}}_{t};\sqrt{\bar{\alpha}_{t}}{\mathbf{x}}_{0},(1-\bar{\alpha}_{t})\mathbf{I})$
(15)

where $\alpha_{t}:=1-\beta_{t}$ and
$\bar{\alpha}_{t}:=\prod_{s=1}^{t}\alpha_{s}$.

In the generative process, the model parameterized by $\theta$ are trained to
fit the data distribution $q({\mathbf{x}}_{0})$ by approximating the
intractable reverse process $q({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t})$. This can
be achieved by maximizing a variational lower bound:

$\max_{\theta}\mathbb{E}_{q({\mathbf{x}}_{0})}[\log
p_{\theta}({\mathbf{x}}_{0})]\leq\max_{\theta}\mathbb{E}_{q({\mathbf{x}}_{0},{\mathbf{x}}_{1},\dots,{\mathbf{x}}_{T})}[\log
p_{\theta}({\mathbf{x}}_{0:T})-\log q({\mathbf{x}}_{1:T}|{\mathbf{x}}_{0})]$
(16)

Utilizing the closed-form expression, we can express ${\mathbf{x}}_{t}$ as a
linear combination of ${\mathbf{x}}_{0}$ and a noise variable
$\epsilon\sim\mathcal{N}(\mathbf{0},\mathbf{I})$:

${\mathbf{x}}_{t}=\sqrt{\bar{\alpha}_{t}}{\mathbf{x}}_{0}+\sqrt{1-\bar{\alpha}_{t}}\epsilon$
(17)

Note that $\bar{\alpha}_{t}$ is a decreasing sequence, and when we set
$\bar{\alpha}_{T}$ sufficiently close to $0$,
$q({\mathbf{x}}_{T}|{\mathbf{x}}_{0})$ converges to a standard Gaussian for
all ${\mathbf{x}}_{0}$, thus we can naturally set
$p_{\theta}({\mathbf{x}}_{T}):=\mathcal{N}(\mathbf{0},\mathbf{I})$.

The expressivity of the reverse process is ensured in part by the choice of
conditionals in $p_{\theta}({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t})$. If all the
conditionals are modeled as Gaussians with trainable mean functions and fixed
variances as in (Ho et al., 2020), then the objective in Equation 16 can be
simplified to

$\mathcal{L}_{\gamma}(\epsilon_{\theta}):=\sum_{t=1}^{T}\lambda_{t}\mathbb{E}_{{\mathbf{x}}_{0}\sim
q({\mathbf{x}}_{0}),\epsilon_{t}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\Big{[}||\epsilon_{\theta}^{(t)}(\sqrt{\bar{\alpha}_{t}}{\mathbf{x}}_{0}+\sqrt{1-\bar{\alpha}_{t}}\epsilon_{t})-\epsilon_{t}||_{2}^{2}\Big{]}$
(18)

where $\epsilon_{\theta}:=\\{\epsilon_{\theta}^{(t)}\\}_{t=1}^{T}$ is a set of
$T$ number of functions, each
$\epsilon_{\theta}^{(t)}:\mathcal{X}\rightarrow\mathcal{X}$ indexed by $t$ is
a denoising function with trainable parameters $\theta^{(t)}$;
$\lambda:=[\lambda_{1},\dots,\lambda_{T}]$ is a positive coefficients, which
is set to all ones in (Ho et al., 2020) and (Song & Ermon, 2019), and we
follow their settings throughout the paper.

In the inference stage for a trained model, ${\mathbf{x}}_{0}$ is sampled by
first sampling ${\mathbf{x}}_{T}$ from the prior
$p_{\theta}({\mathbf{x}}_{T})$, followed by sampling ${\mathbf{x}}_{t-1}$ from
the above generative processes iteratively. The length of steps $T$ in the
forward process is a hyperparameter (typically $T=1000$) in DDPMs. While large
$T$ enables the Gaussian conditionals distributions as good approximations,
the sequential sampling becomes slow. DDIM (Song et al., 2020a) proposes to
sample from generalized generative process as follows,

${\mathbf{x}}_{t-1}=\sqrt{\bar{\alpha}_{t-1}}\bigg{(}\frac{{\mathbf{x}}_{t}-\sqrt{1-\bar{\alpha}_{t}}\epsilon_{\theta}^{(t)}({\mathbf{x}}_{t})}{\sqrt{\bar{\alpha}_{t}}}\bigg{)}+\sqrt{1-\bar{\alpha}_{t-1}-\sigma^{2}_{t}}\cdot\epsilon_{\theta}^{(t)}({\mathbf{x}}_{t})+\sigma_{t}\epsilon_{t}$
(19)

When
$\sigma_{t}=\sqrt{(1-\bar{\alpha}_{t-1})(1-\alpha_{t}/\alpha_{t-1})/(1-\alpha_{t})}$
for all $t$, the generative process becomes a DDPM, while $\sigma_{t}=0$
results in DDIM, which is an implicit probabilistic model that samples with a
fixed procedure, thus corresponding to ODE (Song et al., 2020a). In our work,
both DDPM and DDIM are considered in our generative process.

###  A.2 Score matching with Langevin dynamics

Although we mainly illustrate our framework using the family of DDPM and DDIM
in the main text, the family of score matching with Langevin dynamics (SMLD)
(Song & Ermon, 2019) methods are also applicable in our LGD.

Score matching methods estimates the score (gradient of log-likelihood) of the
data using a score network
$s_{\theta}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ by minimizing the
objective

$\mathbb{E}_{q({\mathbf{x}})}\Big{[}||s_{\theta}({\mathbf{x}})-\nabla_{\mathbf{x}}\log
q({\mathbf{x}})||_{2}^{2}\Big{]}$ (20)

Given the equivalence of SMLD and DDPM explained in Section A.3, we do not
distinguish the two families of generative models in most cases of the paper.
We also sometimes use the notation $\epsilon_{\theta}$ to represent both the
denoising network in DDPM and the score network in SMLD.

###  A.3 Unified formulation through the framework of SDE and ODE

Song et al. (2020b) formulates both SMLD and DDPM through the system of SDE.
The authors further propose ODE samplers which are deterministic compared with
SDE, so does (Song et al., 2020a). Liu et al. (2022) use ODE-based rectified
flow to sample with high efficiency. Cao et al. (2023) and Deveney et al.
(2023) analyze the connections and comparisons between ODE and SDE based
methods.

In particular, the diffusion process can be modeled as the solution to an SDE:

${\rm d}{\mathbf{x}}={\mathbf{f}}({\mathbf{x}},t){\rm d}t+g(t){\rm
d}{\mathbf{w}}$ (21)

where ${\mathbf{w}}$ is the standard Wiener process (a.k.a., Brownian motion),
${\mathbf{f}}(\cdot,t):\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ is a vector-
valued function called the drift coefficient of ${\mathbf{x}}(t)$, and
$g(\cdot):\mathbb{R}\rightarrow\mathbb{R}$ is a scalar function called the
diffusion coefficient of ${\mathbf{x}}(t)$. Note that the end time $T$ of the
diffusion process described in the SDE has a different meaning in the number
of discrete diffusion steps in DDPM, and we denote the latter as
$N\in\mathbb{N}$ in the SDE formulations.

To sample from the backward process, we consider the reverse-time SDE which is
also a diffusion process,

${\rm
d}{\mathbf{x}}=[{\mathbf{f}}({\mathbf{x}},t)-g(t)^{2}\nabla_{\mathbf{x}}\log
p_{t}({\mathbf{x}})]{\rm d}t+g(t){\rm d}\bar{\mathbf{w}}$ (22)

where $\bar{\mathbf{w}}$ is a standard Wiener process in which time reverse
from $T$ to $0$. Again, here $T$ is the end time of the diffusion process,
which is different from the number of discrete diffusion steps in DDPM). ${\rm
d}t$ is an infinitesimal negative timestep, which is discretized in
implementation of DDPM, i.e. each time step is $h:=T/N$ where $N$ is the
number of discrete steps in DDPM.

###  A.4 Related work on theoretical analysis of diffusion models

The empirical success of diffusion models aroused researchers’ interest in
theoretical analysis of them recently. Chen et al. (2023) and Yuan et al.
(2023) provide some theoretical analysis on score approximation and reward-
directed conditional generation, respectively. Li et al. (2023b) provide
generalization bound of diffusion models. Li et al. (2023a) provide empirical
evidence that diffusion models can be zero-shot classifiers. Benton et al.
(2023) analyzes the error bound of flow matching methods, and Lee et al.
(2022); Chen et al. (2022) analyzed the convergence of SDE-based score
matching methods.

##  Appendix B Theoretical Analysis

In this section, we provide our novel theoretical analysis on the guarantees
of solving regression or classification tasks with a conditional latent
diffusion model in Section 4. Our theory is generic and is not limited to
graph data.

As described in the main text, while training the conditional latent diffusion
for prediction tasks with labels, we aim to generate the latent embedding of
labels ${\bm{y}}$ conditioning on the latent embedding of data ${\bm{x}}$. We
first consider regression tasks in our analysis, where the label is a scaler
$y$; classification tasks can be analyzed in a similar manner. We use a
slightly different notation compared with the original DDPM formulation in (Ho
et al., 2020); instead, we use $N$ to denote the maximum number of discrete
diffusion steps in a DDPM (which is denoted as $T$ in (Ho et al., 2020)), and
instead use $T$ to denote the end time in the SDE which controls the diffusion
process.

According to the reasons in Section 4.2, we choose to model the joint
distribution of ${\bm{x}},y$, thus use $\tau({\bm{x}},y)\in\mathbb{R}^{d}$ to
jointly encode the data and the label, and use
$\mathcal{E}({\bm{x}})\mathbb{R}^{d}$ to embed the data (condition) only. Here
we suppose the output of each encoder is a $d$-dimensional vector. The
diffusion model is trained to generate $\tau({\bm{x}},y)$ conditioning on
$\mathcal{E}({\bm{x}})$. We suppose two encoders share one decoder
$\mathcal{D}_{w}$ which is linear layer parameterized by $w\in\mathbb{R}^{d}$.
First we have the assumptions on the reconstruction errors of the
autoencodings.

######  Assumption B.1.

(First and second moment bound of autoencoding errors.)

$\displaystyle\epsilon_{1}:=\mathbb{E}_{q}[||w^{\top}\tau({\bm{x}},y)-y||]<\infty$
(23) $\displaystyle
m_{1}^{2}:=\mathbb{E}_{q}[||w^{\top}\tau({\bm{x}},y)-y||^{2}]<\infty$ (24)
$\displaystyle\epsilon_{2}:=\mathbb{E}_{q}[||w^{\top}\mathcal{E}({\bm{x}})-y||]<\infty$
(25) $\displaystyle
m_{2}^{2}:=\mathbb{E}_{q}[||w^{\top}\mathcal{E}({\bm{x}})-y||^{2}]<\infty$
(26)

Typically, $\epsilon_{2}$ is just the MAE of a traditional deterministic
regression model; $\epsilon_{1}\ll\epsilon_{2}$ since $\tau$ takes $y$ as
inputs and thus has an extremely small reconstruction error. B.1 generally
holds and can be verified across all experiments.

To show why a generative model can perform better than the regression model,
i.e. could have a smaller error than $\epsilon_{2}$, we continue to make the
following mild assumptions on the data distribution $q$, which also generally
holds for practical data..

######  Assumption B.2.

(Lipschitz score). For all $t\geq 0$, the score $\nabla\ln q_{t}$ is
$L$-Lipschitz.

Finally, the quality of diffusion obviously depends on the expressivity of
score matching network (denoising network) $\epsilon_{\theta}^{(t)}$.

######  Assumption B.3.

(Score estimation error). For all $k=1,\dots,N$,

$\mathbb{E}_{q_{kh}}[\epsilon_{\theta}^{kh}-\nabla\ln q_{kh}]\leq\epsilon_{\rm
score}^{2}$ (27)

where $h:=T/N$ is the time step in the SDE.

This is the same assumption as in (Chen et al., 2022). In our main paper the
denoising network is a powerful graph transformer with architectures described
in Equation 4, which can well guarantee a small score estimation error.
However, detailed bounds of $\epsilon_{\rm score}$ is beyond the scope of this
paper.

Finally, we consider a simple version of embedding the condition, where the
denoising network $\epsilon_{\theta}$ still samples in the same way as
unconditional generation, except that we directly add the embedding of
condition to the final output of $\epsilon_{\theta}$. In other words,

$\epsilon_{\theta}^{(t)}({\bm{z}},\mathcal{E}({\bm{x}}))=\epsilon_{\theta}^{(t)}({\bm{z}})+\mathcal{E}({\bm{x}}))$
(28)

where ${\bm{z}}$ is the latent being sampled.

Now we give our main theorem of the regression MAE of the latent diffusion.
The theorem is proved through the SDE description of DDPM as in Section A.3,
where we use $T$ to denote the end time of diffusion time in the SDE, $N$ the
number of discrete diffusion steps in DDPM implementation, and
$\gamma^{d}:=\mathcal{N}(\mathbf{0},\mathbb{I}_{d}$ as a simplified notation
of a random variable from the standard Gaussian distribution.

######  Theorem B.4.

Suppose B.1, B.2, B.3 hold, and the step size $h:=T/N$ satisfies $h\preceq
1/L$ where $L\geq 1$. Then the mean absolute error (MAE) of the conditional
latent diffusion model in the regression task is bounded by

$\displaystyle{\rm MAE}$
$\displaystyle\leq\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y)||]+\epsilon_{1}$
(29) $\displaystyle\preceq\underbrace{\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)}_{\text{convergence of forward
process}}+\underbrace{(L\sqrt{dh}+L(m_{1}+m_{2})h)\sqrt{T}}_{\text{discretization
error}}+\underbrace{\epsilon_{\rm score}\sqrt{T}}_{\text{score estimation
error}}+\underbrace{\epsilon_{1}}_{\text{encoder error}}$ (30)

where $q_{z}$ is the ground truth distribution of
${\bm{z}}:=w^{t}\big{(}\tau({\bm{x}},y)-\mathcal{E}({\bm{x}})\big{)}$.

###### Proof.

Conditioning on $\mathcal{E}({\bm{x}})$, the diffusion model
$\epsilon_{\theta}$ aims to generate the refined representation
$\tau({\bm{x}},y)$. Denote the generated embedding as
$\hat{\tau}({\bm{x}},y)$, then

$\displaystyle{\rm MAE}:$
$\displaystyle=\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-y||]$ (31)
$\displaystyle=\mathbb{E}_{q}[||(w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y))+(w^{\top}\tau({\bm{x}},y)-y)||]$
(32)
$\displaystyle\leq\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y)||]+\mathbb{E}_{q}[||w^{\top}\tau({\bm{x}},y)-y||]$
(33)
$\displaystyle=\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y)||]+\epsilon_{1}$
(34)

We only need to prove the bound of
$\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y)||]$.
Note that the generation is conditioned on $\mathcal{E}({\bm{x}})$. Instead of
cross attention, we consider a simple method to incorporate the condition,
which use a residual connection that directly add the condition
$\mathcal{E}({\bm{x}})$ to the feature being denoised. Then the conditional
generation is equivalent to the unconditional generation which samples the
distribution of $\tau({\bm{x}},y)-\mathcal{E}({\bm{x}})$ from noise. It
suffice to show the unconditional generation error of
$\tau({\bm{x}},y)-\mathcal{E}({\bm{x}})$. Using the notation

$\displaystyle{\bm{z}}_{1}:=w^{\top}\tau({\bm{x}},y)-y$ (35)
$\displaystyle{\bm{z}}_{2}:=w^{\top}\mathcal{E}({\bm{x}})-y$ (36)

where

$\displaystyle\mathbb{E}_{q}[||{\bm{z}}_{1}||]=\epsilon_{1}$ (37)
$\displaystyle\mathbb{E}_{q}[||{\bm{z}}_{1}||^{2}]=m_{1}^{2}$ (38)
$\displaystyle\mathbb{E}_{q}[||{\bm{z}}_{2}||]=\epsilon_{2}$ (39)
$\displaystyle\mathbb{E}_{q}[||{\bm{z}}_{2}||^{2}]=m_{2}^{2}$ (40)

We then have

$\displaystyle{\bm{z}}:=w^{\top}\big{(}\tau({\bm{x}},y)-\mathcal{E}({\bm{x}})\big{)}={\bm{z}}_{1}-{\bm{z}}_{2}$
(41)

To complete our derivation, consider the following lemma proposed in (Chen et
al., 2022),

######  Lemma B.5.

(TV distance of DDPM) (Chen et al., 2022). Suppose that B.1, B.2, B.3 hold.
The data to be generated ${\bm{z}}$ has the ground truth ground truth
distribution $q_{z}$ and the estimated distribution by the diffusion model is
$p_{z}$. The second moment bond
$M^{2}:=\mathbb{E}_{q_{z}}[||\cdot||^{2}]>\infty$. Suppose that the step size
$h:=T/N$ satisfies $h\preceq 1/L$ where $L\geq 1$. Then the total variance
(TV) distance satistfies

${\rm TV}(p_{z},q_{z})\preceq\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)+(L\sqrt{dh}+LMh)\sqrt{T}+\epsilon_{\rm
score}\sqrt{T}$ (42)

The proof of the lemma is in (Chen et al., 2022).

Back to our derivation, utilizing the Cauchy inequality, we have

$\displaystyle\mathbb{E}_{q_{z}}[||{\bm{z}}||^{2}]$
$\displaystyle=\mathbb{E}_{q_{z}}[||{\bm{z}}_{1}-{\bm{z}}_{2}||^{2}]$ (43)
$\displaystyle\leq\mathbb{E}_{q_{z}}[||{\bm{z}}_{1}||^{2}]+\mathbb{E}_{q_{z}}[||{\bm{z}}_{2}||^{2}]+2\mathbb{E}_{q_{z}}[||{\bm{z}}_{1}{\bm{z}}_{2}||]$
(44) $\displaystyle\leq m_{1}^{2}+m_{2}^{2}+2m_{1}m_{2}<\infty$ (45)

thus

$\displaystyle{\rm
TV}(p_{z},q_{z}):=\frac{1}{2}\mathbb{E}_{q_{z}}||\hat{\bm{z}}-{\bm{z}}||\preceq\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)+(L\sqrt{dh}+L(m_{1}+m_{2})h)\sqrt{T}+\epsilon_{\rm
score}\sqrt{T}$ (46)

where $\hat{\bm{z}}\sim p_{z}$ is the estimated embedding of ${\bm{z}}$
generated by the diffusion model. Recall the condition embedding is
implemented via simply adding the condition to the generated $\hat{\bm{z}}$,
i.e.
$w^{\top}\hat{\tau}({\bm{x}},y)=\hat{\bm{z}}+w^{\top}\mathcal{E}({\bm{x}})$,
we have

$\displaystyle\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y)||]$
(47) $\displaystyle=$
$\displaystyle\mathbb{E}_{q}[||\hat{\bm{z}}-\big{(}w^{\top}\tau({\bm{x}},y)-w^{\top}\mathcal{E}({\bm{x}})\big{)}||]$
(48) $\displaystyle=$
$\displaystyle\mathbb{E}_{q_{z}}[||\hat{\bm{z}}-{\bm{z}}||]$ (49)
$\displaystyle\preceq$ $\displaystyle\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)+(L\sqrt{dh}+L(m_{1}+m_{2})h)\sqrt{T}+\epsilon_{\rm
score}\sqrt{T}$ (50)

where we omit the constant factor $2$ in Equation 46. Finally we complete our
proof,

$\displaystyle{\rm MAE}$
$\displaystyle\leq\mathbb{E}_{q}[||w^{\top}\hat{\tau}({\bm{x}},y)-w^{\top}\tau({\bm{x}},y)||]+\epsilon_{1}$
(51) $\displaystyle\preceq\underbrace{\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)}_{\text{convergence of forward
process}}+\underbrace{(L\sqrt{dh}+L(m_{1}+m_{2})h)\sqrt{T}}_{\text{discretization
error}}+\underbrace{\epsilon_{\rm score}\sqrt{T}}_{\text{score estimation
error}}+\underbrace{\epsilon_{1}}_{\text{encoder error}}$ (52)

∎

We now give more interpretations to Theorem B.4. The first term $\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)$ is the error of convergence of the forward
process, which can be exponetially small when we have enough SDE diffusion
time $T$, or equivalently, $\bar{\alpha}$ is efficiently small to make $q_{T}$
close enough to the standard Gaussian
$\gamma^{d}:=\mathcal{N}(\mathbf{0},\mathbf{I}_{d})$.

The second term $(L\sqrt{dh}+L(m_{1}+m_{2})h)\sqrt{T}$ is the discretization
error, since when implementing the DDPM we have to use discrete $N$ steps to
simulate the ODE. It is interesting to see that this term is affected by both
the latent dimension $d$ and the second moment of the variation encoding
errors $m_{1}$ and $m_{2}$ (i.e. the reconstruction MSE loss of labels and
conditions). The results implies that a lower dimension of the latent space
$\mathcal{H}$ is more suitable for learning a diffusion model. However, note
that the reconstruction MSE loss $m_{1},m_{2}$ may also be affected by $d$:
when the rank of data is high, a low dimension latent space may not represent
the data well, and the projection made by the decoder $w\in\mathbb{R}^{d}$ is
likely to cause information loss, thus increasing $m_{1}$ and $m_{2}$.
Therefore, the latent dimension $d$ should be carefully chosen, which should
not be neither too low (poor representation power and large reconstruction
error) nor too high (large diffusion error). This verifies the intuition
discussed in Section 3.

The third term is the score estimation error, which is related to the
expressivity of denoising (score) networks. Empirically, the graph transformer
in Equation 4 we adopted is powerful in function approximation. In the
language of distinguishing non-isomorphic graphs, our transformer is at least
as powerful as $1$-order Weisfeiler-Lehman test (Xu et al., 2018). More
theoretical analysis of the transformer architecture is beyond the scope of
the paper, yet our architecture reveals strong performance in experiments.

The last term is the error brought by autoencoding. However, as $\epsilon_{1}$
is the reconstruction MAE of $\tau$ which aims to encode the labels,
$\epsilon_{1}$ is typically much smaller than the MAE of regression models
$\epsilon_{2}$. Our experimental observations support the above assumption.
Therefore, the conditional generation model outperforms the traditional
regression model as long as

$\sqrt{{\rm
KL}(q_{z}||\gamma^{d})}\exp(-T)+(L\sqrt{dh}+L(m_{1}+m_{2})h)\sqrt{T}+\epsilon_{\rm
score}\sqrt{T}+\epsilon_{1}\preceq\epsilon_{2}$ (53)

This can be achieved by searching hyperparameters of the diffusion model,
including $T,N,h$. Intuitively, a sufficiently small $h$ (or equivalently,
sufficiently large number of diffusion steps $N$) would lead to a small error.
Following (Chen et al., 2022), suppose ${\rm
KL}(q_{z}||\gamma^{d})\exp(-T)\leq{\rm poly}(d)$, $m_{1}+m_{2}\leq d$, then by
choosing $T\asymp\ln({\rm KL}(q_{z}||\gamma^{d})/\epsilon)$ and
$h\asymp\frac{\epsilon^{2}}{L^{2}d}$ and hiding logarithmic factors, we have

${\rm MAE}\leq O(\epsilon+\epsilon_{\rm score}+\epsilon_{1})$ (54)

where $\epsilon$ is the error scale we desire. In this case, we need
$N=\Theta(\frac{L^{2}d}{\epsilon^{2}})$ number of discrete diffusion steps. If
$\epsilon_{\rm score}\leq O(\epsilon)$ and $\epsilon_{1}\leq O(\epsilon)$,
then ${\rm MAE}\leq\epsilon$.

##  Appendix C Pretrain, Finetune and In-Context Learning Framework

##### A complete training framework.

In this section, we will describe the overall architecture and training
procedure of the general purposed graph generative model LGD. As described
before, the entire model consists of a powerful graph encoder $\mathcal{E}$
and latent diffusion model $\theta$, which are shared across different tasks
and need to be pretrained. As for different downstream tasks, we can adopt
finetuning or prompt tuning strategies. In both cases, we need to train a
lightweight task-specific graph decoder $\mathcal{D}$. We need to update the
parameters of $\mathcal{E}$ and $\theta$ while finetuning. In prompt tuning,
however, we keep these pretrained parameters fixed and only train a learnable
prompt vector concatenated with input features of prompt graphs, which enables
in fact the first in-context learning ability for pretrained graph models.

In the pretraining stage, we need to train the graph encoder $\mathcal{E}$ and
the generative model $\theta$ across a wide range of tasks. These two parts
can be trained simultaneous or sequential, as well as through different
paradigm. Here, $\mathcal{E}$ includes the initial tokenization layer as well
as a powerful graph learner backbone (e.g. a GNN or graph transformer) that
encodes input graph into a semantic meaningful latent space for all downstream
tasks. Pretrain of $\mathcal{E}$ consists of both unsupervised learning and
supervised learning trained on downstream tasks with labels. The unsupervised
loss includes both contrastive loss $\mathcal{L}_{contrast}$ and
reconstruction loss of self-masking $\mathcal{L}_{recon}$. The supervised
learning is jointly trained with a downstream classifier or regression layer
(that will not be used later), according to classification entropy loss
$\mathcal{L}_{ce}$ or regression MSE/MAE loss $\mathcal{L}_{regress}$.

We train the diffusion model $\theta$ in a supervised manner. Extra tokens are
applied to represent masked values or attributes that need to be predicted. In
traditional generation tasks, the training procedure is similar to stable-
diffusion, where we compute loss between predicted denoised graph and the
input graph in the latent space encoded by $\mathcal{E}$. As for
classification and regression tasks, we only input part of graph features, and
expect the model to reconstruct the input features while predicting those
missing features. For example, in a link prediction task, the input graph
contains all node features and only part of edges. Then the model need to
reconstruct the known input features and simultaneously predict the rest
links. Therefore, the loss is the summation of reconstruction loss (in the
latent space) and the corresponding classification or regression loss.

For tasks of different levels and types, note that the reconstructed graph
representation in the latent space contains all node and edge features that
are powerful enough for any downstream tasks. Thus only a (lightweight) task
specific decoder $\mathcal{D}$ is needed, like a classifier for a
classification task and a regression layer for a regression task. The node and
edge level attributes can be directly obtain based on corresponding latent
representation, while graph attributes is available by pooling operations, or
by adding a virtual node with trainable graph token for every task. To train a
task specific decoder, we can either finetune along with the entire pretrained
model on the target dataset (whole dataset and few shot are both possible), or
only train them with prompt vectors while fixing the parameters of pretrained
graph encoder $\mathcal{E}$ and generative model $\theta$.

##### Domain adaptation.

We now present the potential of our framework in domain adaptation, while
leaving the experiments for future work. To deal with graphs from various
domains, we create a graph dictionary for all common node and edge types in
graph datasets, such as atom name in molecular graphs. The vectorization is
via the first embedding layer of the graph encoder network $\mathcal{E}$,
which is analogous to text tokenization in LLM. For those entities rich in
semantic information, we can also make use of pretrained foundation models
from other domains or modals through cross attention mechanism in the latent
diffusion model.

After finishing pretraining the powerful graph encoder $\mathcal{E}$ and the
latent generative model $\theta$, we need to adapt the entire model to target
tasks. Previously, a widely adopted paradigm in graph learning field is the
pretrain-finetune framework. During the finetune procedure, we jointly train
the task specific decoder $\mathcal{D}$, and finetune $\mathcal{E}$ and
$\theta$ on the target task. However, finetuning has at least the following
drawbacks: (1) significantly computation cost compared with prompting, since
we need to compute gradients of all parameters; (2) may lead to catastrophic
forgetting of the pretrained knowledge, thus performing worse on other tasks
and possibly requiring one independent copy of model parameters for each task.

Prompting is another strategy to adapt the pretrained model to downstream
tasks, which designs or learns a prompt vector as input while keeping the
pretrained $\mathcal{E}$ and $\theta$ fixed. Compared with finetuning,
prompting requires much less computation resources since we only need to learn
an input vector. Here we introduce a graph prompt mechanism which is the first
to allow for real in-context learning. In the target task, we provide prompt
example graphs with labels, whose input node and edge features are
concatenated with a learnable task-specific prompt vector. The prompt vectors
are learned through this few shot in-context learning, which adapt the model
better to the task without retraining or finetuning. Besides, to keep the
hidden dimension aligned, we also concatenate a prompt vector in the pretrain
and finetune stages, which can be serve as initialization of downstream prompt
vectors in similar tasks.

##  Appendix D Experimental Details and Additional Results

###  D.1 Experimental details

We now provide more details of the experiments in Section 5, including
experimental settings and implementation details.

####  D.1.1 General settings

##### Diffusion process.

In all experiments, we use a diffusion process with $T=1000$ diffusion steps,
parameterized by a linear schedule of $\alpha_{t}$ and thus a decaying
$\bar{\alpha}_{t}$. For inference, we consider both (a) DDPM; (b) DDIM with
$200$ steps and $\sigma_{t}=0$. Instead of predicting the noises, we use the
parameterization where denoising (score) networks $\epsilon_{\theta}$ is set
to directly predict the original data ${\mathbf{x}}_{0}$. We set
$\lambda=\mathbf{1}$ in Equation 19 as most literature for simplicity.

##### Model architectures.

For all tasks, we use the encoder $\mathcal{E}_{\phi}$ with the augmented-edge
enhanced graph transformer as described in Equation 4. For regression and
classification tasks, as the input graph structures are complete, we can also
add positional encoding and MPNN modules to the encoder. For all tasks, each
task-specific decoder $\mathcal{D}_{\xi}$ is a single linear layer for
reconstruction or prediction. Due to the discussion in Appendix B, we choose
the dimension of the latent space from $[4,8,16]$.

For denoising (score) network $\epsilon_{\theta}$, due to the reason explained
in Section 3.3, MPNNs and PEs are ill-defined in the corrupted latent space
$\mathcal{H}_{t}$ and are hence not applicable. Therefore, we use pure graph
transformer architectures for $\epsilon_{\theta}$. For unconditional
generation, each layer computes self-attention as in Equation 4. For
conditional generation, each module consists of a self-attention layer, a
cross-attention layer, and another self-attention layer. For QM9 conditional
generation tasks where the conditions are molecular properties, we use an MLP
as the conditioning encoder $\tau$ and the cross-attention in Equation 7. For
regression on Zinc and classification on ogbg-molhiv, since the conditions are
masked graphs, we use the specially designed cross-attention in Equation 9. In
these cases, the conditioning encoder $\tau$ is shared with the graph encoder
$\mathcal{E}_{\phi}$. To enable good representation of both masked graphs and
the joint representation of graphs with labels, we randomly mask the labels in
the pretraining stage, so that both $\mathcal{E}_{\phi}({\bm{X}},{\bm{A}})$
and $\mathcal{E}_{\phi}({\bm{X}},{\bm{A}},{\bm{y}})$ have small reconstruction
errors - though the latter is typically much smaller than the former one. We
do not add virtual nodes in QM9 datasets, and the graph feature is obtained by
(sum or mean) pooling the nodes (and optionally, edges). For Zinc and ogbg-
molhiv, we add a virtual node where we embed the graph-level label via the
encoder to obtain target refined full graph representations, and we use an
embedding layer for class labels and an MLP for regression labels. All
networks have ReLU activations, and we use layer norm instead of batch norm
for all transformers for training stability.

####  D.1.2 Task specific settings

##### Unconditional generation on QM9.

Here we provide other hyperparemeters for the experiments of QM9 unconditional
generation. We use an encoder with 96 hidden features and 5 layers. The
denoising network has 256 hidden channels and 6 self-attention layers. We
train the model for 1000 epochs with a batch size of 256. We adopt the cosine
learning rate schedule with 50 warmup epochs, and the initial learning rate is
$1e-4$.

##### Conditional generation on QM9.

We train a separate model for each target. The encoders have 3 layers and 96
hidden channels. The denoising networks have 4 cross-attention modules (8
self-attention layers and 4 cross-attention layers in total) and 128 hidden
channels. We train for 1000 epochs with a batch size of 256, and the cosine
learning rate schedule with initial learning rate $1e-4$.

##### Regression on Zinc.

The encoder has 64 hidden channels and 10 layers, augmented with GINE (Hu et
al., 2019) and RRWP positional encodings (Ma et al., 2023). The score network
has 64 hidden channels and 4 cross-attention modules (8 self-attention layers
and 4 cross-attention layers in total). We train the diffusion model for 2000
epochs with a batch size of 256, and a cosine learning rate with 50 warm-up
epochs and initial value $1e-4$. We also conduct ablation studies on Zinc, see
Section D.2.

##### Classification on ogbg-molhiv.

Same as Zinc, the encoder has 64 hidden channels and 10 layers, augmented with
GINE (Hu et al., 2019) and RRWP positional encodings (Ma et al., 2023). The
score network also has 64 hidden channels and 4 cross-attention modules. We
train the diffusion model for 500 epochs with a batch size of 256, and a
cosine learning rate with 20 warm-up epochs and initial value $1e-4$. We
observe overfitting phenomenon in the early stage, which may be caused by the
imbalanced distribution between training set and test set, see Section D.3 for
discussions.

###  D.2 Ablation studies

We conduct ablation studies on Zinc dataset to investigate (a) the impacts of
the dimension $d$ of the latent embedding; (b) whether ensemble technique
helps to improve the prediction quality as the generation is not
deterministic.

##### Dimension of the latent embedding.

We use encoders with output dimension (i.e. the dimension of the latent
embedding for LGD) $4,8,16$ respectively, and inference with the fast DDIM for
3 runs with different random seeds in each setting.

Table 5: Ablation study on latent dimension on Zinc (MAE $\downarrow$). Shown
is the mean $\pm$ std of 3 runs.
Latent dimension | Test MAE
---|---
4 | $0.081\pm 0.006$
8 | $0.080\pm 0.006$
16 | $0.084\pm 0.007$

According to the results in Table 5, LGD-DDIM reveals similar performance with
these latent dimensions, while $d=16$ leads to a slight performance drop. This
coordinates with our theoretical analysis in Appendix B, as large dimensions
of latent space may cause large diffusion errors. It would be interesting to
see the performances in a much smaller (e.g. $d=1$) or much larger (e.g.
$d=64$) latent space.

##### Ensemble of multiple generations.

One possible issue with solving regression and classification tasks with a
generative model is that the output is not deterministic. To investigate
whether the randomness improve or hurt the performance, we test with DDIM
using a same trained model which ensembles over $1,5,9$ predictions
respectively. We use the median of the multiple predictions in each case.

Table 6: Ablation study of ensembling on Zinc (MAE $\downarrow$). Shown is the
mean $\pm$ std of 3 runs.
# of ensembled predictions | Test MAE
---|---
1 | $0.081\pm 0.006$
5 | $0.081\pm 0.006$
9 | $0.079\pm 0.006$

As shown in Table 6, ensembling over multiple predictions has almost no
impacts on the performance. This is somewhat surprising at the first glance.
It shows that the diffusion model can often output predictions around the mode
with small variances, thus modeling the distributions well. As mentioned in
the main text, the SDE-based DDPM also outperforms ODE-based DDIM, aligns with
previous empirical and theoretical studies that the randomness in diffusion
models could lead to better generation quality (Cao et al., 2023).

###  D.3 Experimental findings and discussions

##### Evaluation metrics in unconditional molecule generation.

We now further discuss the evaluation metrics of unconditional molecule
generation with QM9 dataset. In the main text we report the widely adopted
validity and uniqueness metrics as most literature do. However, it is notable
that the validity reported in Table 1 (and also in most papers) is computed by
building a molecule with RdKit and calculating the propertion of valid SMILES
string out of it. As explained in (Jo et al., 2022), QM9 contains some charged
molecules which would be considered as invalid by this method. They thus
compute a more relaxed validity which allows for partial charges. As a
reference, GDSS-seq and GDSS (Jo et al., 2022) achieve $94.5\%$ and $95.7\%$
relaxed validity, respectively; in comparson, our LGD achieves $95.8\%$
relaxed validity, which is also better. We do not report the novelty result
for the same reasons as explained in (Vignac et al., 2022). This is because
QM9 is an exhaustive enumeration of the small molecules that satisfy certain
chemical constrains, thus generating novelty molecules outside the dataset may
implies the model has not correctly learned the data distribution.

##### Experimental findings.

In our experiments, we observe many interesting phenomenon, which are listed
below. We hope these findings could give some insights into further studies.

  * •

Regularization of the latent space. We experimentally find that exerting too
strong regularization to the latent space, e.g. a large penalty of KL
divergence with the standard Gaussian, would lead to performance drop of the
diffusion model. This is understandable as the latent space should not only be
simple, but also be rich in information. Strong regularizations will cause the
model to output a latent space that is too compact, thus hurt the
expressiveness. We find in our experiments that a layer normalization of the
output latent representations tends to result in better generation qualities,
while KL or VQ regularization are not necessary.

  * •

Rapid convergence. We find that our latent diffusion model tends to converge
rapidly in the early training stage. Compared with non-generative models such
as GraphGPS (Rampásek et al., 2022), LGD typically needs only
$\frac{1}{5}\sim\frac{1}{3}$ number of epochs of them to achieve similar
training loss, which makes the training of LGD much faster. We attribute this
to the advantages of the powerful latent space, as the diffusion model only
needs to “refine” the representation on top of the condition that is already
close to ground truth.

  * •

Generalization. Interestingly, we find that while LGD usually have good
predictions (in both train and test set) in the early stage of training, the
test loss may increase in the final stages, forming a “U” curve in test loss.
This is obviously a sign of overfitting due to the strong capacity of
diffusion models to model complex distributions. If the distribution shift
between train and test set becomes larger (e.g. ogbg-molhiv compared with
Zinc), the overfitting phenomenon gets more obvious. This implies that LGD is
extremely good at capturing complex distributions, and thus has the potential
to scale well to larger datasets that fits with the model capacity.

##  Appendix E Discussions

###  E.1 More discussions on graph generative models

Among graph generative models, although some auto-regressive models reveal
better performance, they are usually computationally expensive. Moreover, one
worse property of auto-regressive graph generative models cannot maintain the
internal permutation invariance of graph data. On the other hand, some one-
shot graph generative models are permutation invariant, but those based on
VAEs, normalizing flows and GANs tend to under-perform autoregressive models.
Currently, graph diffusion generative models are the most effective methods,
but they have to overcome the difficulty brought by discreteness of graph
structures and possibly attributes. Consequently, (Niu et al., 2020) and (Jo
et al., 2022) can only generate the existence of edges via comparing with a
threshold on the continuous adjacency matrix $\mathbf{A}\in\mathbb{R}^{n\times
n}$. Besides, (Niu et al., 2020) cannot deal with node or edge features, while
(Jo et al., 2022) can only handle node attributes. As the cost of
discreteness, (Vignac et al., 2022) is only able to model categorical node and
edge features. All these score-based or diffusion models are unable to provide
all types of node and edge (and even graph) features, including categorical
and continuous ones. Overall, our LGD is the first to enable generating node,
edge and graph-level features of all categories in one shot.

Some concurrent works provide some insights and implications on graph
generation. Yang et al. (2023b) incorporates data-dependent, anisotropic and
directional noises in the forward diffusion process to alleviate transforming
anisotropic signals to noise too quickly. The denoising network directly
predicts the input node features from perturbed graphs, and Yang et al.
(2023b) also propose to use diffusion models for unsupervised graph
representation learning by extracting the feature maps obtained by the
decoder. Dan et al. (2023) estalishes a connection between discrete GNN models
and continuous graph diffusion functionals through Euler-Lagrange equation. On
top of this, Dan et al. (2023) propose two new GNN architectures: (1) use
total variation and a new selective mechanism to reduce oversmoothing; (2)
train a GAN to predict the spreading flows in the graph through a neural
transport equation, which is used to alleviate the potential vanishing flows.

###  E.2 Future work

Our work manages to solve tasks of all types and all levels using only one
unified model. We believe that it is a significant breakthrough, and a huge
leap towards building a graph foundation model. However, to build a literal
foundation model, we need to train a single model that can handle different
datasets, even from different domains. This requires expensive computation
resources, more engineering techniques and extensive experiments, which we
leave for future work.

It is also interesting to explore the possibility of applying diffusion models
to regression and classification tasks in other fields, such as computer
vision. Although Li et al. (2023a) also mention the idea of doing
classification with diffusion models, their formulation is complex and
computational costly as they have to enumerate all classes. Their method is
also limited to classification cannot be extended to regression tasks due to
the continuous regression target. In comparison, our formulation is much
simpler and more efficient, and is applicable to both regression and
classification tasks. We also derive error bounds for the conditional latent
diffusion models in these tasks, see Appendix B. It remains to see whether
diffusion models could outperform traditional non-generative models in all
task types, both inside and outside the graph learning field.