Generative Diffusion Models on Graphs: Methods and Applications

1 Introduction

Graphs can represent the rich variety of relationships (i.e., edges) between real-world entities (i.e., nodes). They have been widely used in a diversity of domains [Xia et al., 2021], such as social networks [Derr et al., 2020; Fan et al., 2019a], molecular graph structure [Wu et al., 2022b], and recommender systems [Fan et al., 2022a; Fan et al., 2020], aiming to model association information and structural patterns among various real-world objects [Barab´asi, 2013]. Due to the prevalence of graphs, graph generative models, with the goal of learning the given graph distributions and generating novel graphs, have attracted significant attention in various applications [Zhang et al., 2020], such as drug discovery and semantic parsing in NLP. Typically, most existing graph generative methods can be classified into two groups: autoregressive generation and one-shot generation [Jo et al., 2022]. Particularly, autoregressive generation methods are designed to generate desired graphs in a sequential process, while oneshot generation methods generate the entire graph with topology structure and node/edge feature in one single step. In general, graph generation faces three fundamental challenges - (1) Discreteness: The graph structure is naturally discrete, resulting in calculation difficulties of models' gradients [Guo and Zhao, 2022; Zhang et al., 2020]. To this end, the most widely used optimization approaches cannot be directly applied to perform back-propagation training for graph generation in an end-to-end fashion. (2) Complex Intrinsic Dependencies: Unlike image data, nodes are not independent and identically distributed (or i.i.d.). In other words, these complex graph structural dependencies are inherent relationships among instances (e.g., nodes and edges) [Niu et al., 2020; Guo and Zhao, 2022]. Such complexity of graph structure introduces tremendous challenges in generating desired graphs. (3) Permutation Invariant: Since nodes are naturally unordered in most graphs, there are at most N! different equivalent adjacency matrices representing the same graph with N nodes [Niu et al., 2020].

∗Wenqi Fan is the corresponding author.

Traditional graph generation methods rely on leveraging hand-crafted graph statistics (e.g., degrees and clustering coefficients properties), and learning kernel functions or engineered features to model the structural information [Xia et al., 2021]. Driven by recent advances in Deep Neural Networks (DNNs) techniques, deep generative models, such as variational autoencoder (VAE) [Simonovsky and Komodakis, 2018], Generative Adversarial Networks (GAN) [De Cao and Kipf, 2018], and normalizing flows [Luo et al., 2021b], have largely improved the generation performance for graphstructured data. For example, GraphVAE trains two graph neural networks (GNNs) as an encoder and a decoder to estimate the graph distribution [Simonovsky and Komodakis, 2018], and MolGAN introduces a GAN-based framework for molecular generation [De Cao and Kipf, 2018]. Although these deep generative methods have achieved promising results, most of them still have several limitations. For example, VAE approaches struggle with the estimation of posterior to generate realistic large-scale graphs and require expensive computation to achieve permutation invariance because of the likelihood-based method [Bond-Taylor et al., 2021]. GAN methods are more prone to mode collapse with graph-structured data and require additional computation to train a discriminator [De Cao and Kipf, 2018; Wang et al., 2018]. The flow-based generative models are hard to fully learn the structural information of graphs because of the constraints on the specialized architectures [Cornish et al., 2020]. Thus, it is desirable to have a novel generative paradigm for deep generation techniques on graphs.

In recent years, denoising diffusion models have become an emerging generative paradigm to enhance generative capabilities in the image domain [Cao et al., 2022; Yang et al., 2022]. More specifically, inspired by the theory of non-equilibrium thermodynamics, the diffusion generative paradigm can be modelled as Markov chains trained with variational inference [Yang et al., 2022], consisting of two main stages, namely, a forward diffusion and a reverse diffusion. The main idea is that they first develop a noise model to perturb the original input data by adding noise (i.e., generally Gaussian noise) and then train a learnable reverse process to recover the original input data from the noise. Enhanced by the solid theoretical foundation, the probabilistic parameters of the diffusion models are easy-to-tractable, making tremendous success in a wide range of tasks [Cao et al., 2022; Yang et al., 2022].

Recent surveys on deep diffusion models have focused on the image domain [Cao et al., 2022; Yang et al., 2022; Croitoru et al., 2023]. Therefore, in this survey, we provide a comprehensive overview of the advanced techniques of deep graph diffusion models. More specifically, we first briefly introduce the basic ideas of the deep generative models on graphs along with three main paradigms in diffusion models and their key applications i.e., molecule generation and protein modeling. At last, we discuss the future research directions for diffusion models on graphs. To the best of our knowledge, this survey is the very first to summarize the literature in this novel and fast-developing research area.

2 Preliminaries

The general architecture of these deep generative models on graphs is illustrated in Figure 1. In general, a graph is represented as G=(X,A), consisting of N nodes. A∈RN×N is the adjacency matrix, where Aij = 1 when node vi and vj are connected, and 0 otherwise. X∈RN×d denotes the node feature with dimension d. Under diffusion context, G0 refers to the original input graph, while Gt refers to the noise graph at the t time step.

2.1 Deep Generative Models on Graphs

Variational Autoencoders (VAEs). As the very first deep generative model, variational autoencoders have been successfully applied to graphs, where VAE aims to train a probabilistic graph encoder qϕ(z|G) to map the graph space to a low-dimensional continuous embedding z, and a graph decoder pθ(G|z) to reconstruct new data given the sampling from z [Simonovsky and Komodakis, 2018].

Generative Adversarial Networks (GAN). GAN is to implicitly learn the graph data distribution with the min-max game theory [Wang et al., 2018] with two neural networks: generator and discriminator. Specifically, the generator attempts to learn the graph distribution and generate new graphs, while the discriminator tries to distinguish the real graph from the generated graph. Due to the discrete nature of graphs, most GAN-based methods are optimized by reinforcement learning techniques.

Normalizing Flows. The normalizing flow leverages a sequence of invertible functions f(x) to map the graph samples (i.e., adjacency matrices and/or edge features) to latent variables z and learns the graph distribution by tracking the change of density with Jacobian matrix [Liu et al., 2019]. The inverse function f -1 (z) yields new samples from latent variables by reversing mapping f(x). The function f specifies an expressive bijective map which supports a tractable computation of the Jacobian determinant [Cornish et al., 2020]. Generally, the training process would estimate the loglikelihoods of each graph sample and update the parameter of f -1 (z) by maximizing log-likelihoods with gradient descent. Limitations. Despite the great success, most existing deep generative models are still facing challenges in graph generation. For instance, VAE models generate graphs based on likelihood, which requires a massive graph-matching process or an explicit estimation of the likelihood of each possible node alignment when achieving permutation invariant [Simonovsky and Komodakis, 2018]. In practice, GANbased generative models on graphs easily fall into mode collapse, which can limit both the scale and novelty of generated graphs [De Cao and Kipf, 2018]. As for normalizing flow, the bijective model structure limits its ability to capture large-scale node-edge dependencies [Cornish et al., 2020].

2.2 DiffusionModels

In general, there are three paradigms of diffusion models: Score Matching with Langevin Dynamics (SMLD), Denoising Diffusion Probabilistic Model (DDPM) and Score-based Generative Model (SGM). SMLD and DDPM leverage the score matching idea and nonequilibrium thermodynamics respectively to learn different reverse functions of the diffusion process. SGM generalizes the discrete diffusion steps into the continuous scenario and further models the diffusion process with the Stochastic Differential Equations (SDE).

SMLD. As the first representative version of the diffusion model, SMLD [Song and Ermon, 2019] proposes a novel generative model mechanism that first progressively adds random noise to the data distribution to a predefined prior (usually Gaussian noise), and then reverses the diffusion process by learning the gradient of the data distribution ∇x log p(x). The SMLD perturbs the original distribution with a sequence of random Gaussian noises of incremental scales that can be modelled as qσ(˜x|x) := N ( ˜x|x, σ2 I ). This noise scheme facilitates an accurate score matching by preventing the noised distribution from a low-dimensional manifold and providing sufficient training data in low data density regions with large-scale noise. In the gradual denoising process, SMLD proposes a Noise Conditional Score Network (NCSN) sθ(xt, σ) to approximate the score jointly. With the annealed Langevin dynamics, NCSN is able to yield new samples from the Gaussian distribution as follows:

DDPM. Enhanced by the variational inference, the denoising diffusion probabilistic model (DDPM) [Ho et al., 2020] constructs two parameterized Markov chains to diffuse the data with predefined noise and reconstruct the desired samples from the noise. In the forward chain, the DDPM gradually perturbs the raw data distribution x0 ∼ q (x0) to converge to the standard Gaussian distribution zt under a pre-designed mechanism. Meanwhile, the reverse chain seeks to train a parameterized Gaussian transition kernel to recover the unperturbed data distribution. Mathematically, the forward process q can be defined as follows:

where βt ∈ (0, 1) represents the variance of the Gaussian noise added at time step t. With αt = 1-βt, -αt = ∏ti=1 αi, the marginal can be written as:

where ϵ denotes the Gaussian noise. These equations enable the DDPM to sample the noised latent xt at an arbitrary step conditioned on x0 [Vignac et al., 2023]. The reverse Gaussian transitions pθ parameterized by θ can be defined as:

The neural network will be trained to optimize the variational upper bound on negative log-likelihood, which can be estimated by the Monte-Carol algorithm [Vignac et al., 2023]. As a result, the DDPM would sample from the limit distribution, and then recursively generate samples xt using the learned reverse chain.

SGM. The score SDE formula describes the diffusion process in continuous time steps with a standard Wiener process.

The forward diffusion process in infinitesimal time can be formally represented as [Song et al., 2021]:

where w denotes a standard Wiener process (a.k.a., Brownian motion), and g(·) denotes the diffusion coefficient, which is assumed to be a scalar independent of x. The reversetime SDE describes the diffusion process running backwards in time to generate new samples from the known prior xT , which is shown as follows:

The only unknown information in reverse-time SDE is the score function ∇x log p(x), which can be approximated by a time-dependent score-based model sθ(x, t) by optimizing denoising score-matching objective:

where p0t(xt|x0) denotes the probability distribution of xt conditioned on x0, t is uniformly sampled over [0, T], x0 ∼ p0(x) and xt ∼ p0t(xt|x0). The score-based diffusion model through SDE unifies the SMLD and DDPM into a continuous version.

Furthermore, the probability flowODE [Song et al., 2021] designs a deterministic reverse-time diffusion process, whose marginal probability density is identical to the SDE formula. This method largely accelerates the sampling process considering that it allows to perform Gaussian sampling at adaptive time intervals with discretization strategy rather than at successive time steps, and thus the number of estimations of score function is reduced. The reverse-time ODE is defined as below:

3 Generative DiffusionModels on Graphs 3.1 SMLD on Graphs

EDP-GNN [Niu et al., 2020] is the very first score matching based diffusion method for undirected graph generation. Through fitting a neural network to estimate the different scales of Gaussian noise added to the upper triangular segment of the symmetric adjacency matrices, EDP-GNN learns the score function of the adjacency matrices distributions of the graphs. By using a similar annealed Langevin dynamics implementation as SMLD [Song and Ermon, 2019], the adjacency matrices are generated from the sampled Gaussian noise. Inspired by the GIN method [Xu et al., 2019], EDP-GNN also introduces a multi-channel GNN layer to obtain node features with the message-passing mechanism and an MLP output layer including a noise-conditioned term to prevent separately training the score network at each noise scale. ConfGF [Shi et al., 2021] is the first work adapting the SMLD-based diffusion work to the molecular confirmation generation problem. Unlike EDP-GNN, whose target is to generate adjacency matrices, ConfGF focuses on generating atomic coordinates (node feature) R given the molecular graph G. Due to the roto-translation equivalent property, ConfGF maps a set of atomic coordinates to a set of interatomic distances l. By injecting the Gaussian noise over l, ConfGF learns the score function of interatomic distance distributions. Similar to EDP-GNN, the score function is later combined with the annealed Langevin dynamics to generate new atomic coordinate samples.

3.2 DDPMon Graphs

The adaption of denoising diffusion probabilistic models on graphs is mainly focusing on designing the appropriate transition kernel of the Markov chain. The previous diffusion models usually embed the graphs in continuous space, which might lead to structural information loss. Haefeli et al. propose a denoising diffusion kernel to discretely perturb the data distribution. At each diffusion step, each row of the graphs' adjacency matrices is encoded in a one-hot manner and multiplied with a double stochastic matrix Qt. In the reverse process, the model includes a re-weighted ELBO as the loss function to obtain stable training. With discrete noise, the sampling process is largely accelerated. Furthermore, DiGress [Vignac et al., 2023] extends the DDPM algorithm to generate graphs with categorical node and edge attributes. The conditional probabilities for the noisy graphs can be defined as follows:

where Gt = (Xt, Et) refers to the noisy graph composed of a node attribute matrix Xt and an edge attribute tensor Et. QXt and QEt refer to the noise added to the node and edge, respectively. This Markov formulation allows sampling directly at an arbitrary time step without computing the previous steps. In the denoising process, DiGress incorporates the cross-entropy to measure the distance between the predicted distribution and the input graph distribution with respect to node and edge, so as to train the parameterized graph transformer network ϕθ. Thus, the modeling of graph distribution is simplified to a sequence of classification. In addition, operating on discrete steps allows DiGress to leverage various graph descriptors, such as spectral features, to guide the diffusion process. Overall, DiGress is capable of yielding realistic large-scale graphs depending on the overall or partial graph. Moreover, the E(3) Equivariant Diffusion Model (EDMs) is able to operate on both continuous and categorical features of the graph by training an equivariant network [Hoogeboom et al., 2022]. The EDMs jointly inject the Gaussian noise to the latent variables zt = [zxt , zht ] of nodes coordinates (continuous) xi and the other features h (categorical). As an extension of EDMs, Equivariant Energy-Guided SDE (EEGSDE) [Bao et al., 2023] introduces a novel property prediction network that serves as a guiding mechanism in the generative process. This network is concurrently trained alongside the reverse diffusion process, with its gradient serving as an additional force to enhance the overall performance. Current generative models struggle to effectively capture the complexities of interatomic forces and the presence of numerous local constraints. To address this issue, the proposed approach in MDM [Huang et al., 2022b] utilizes augmented potential interatomic forces and incorporates dual equivariant encoders to effectively encode the varying strengths of interatomic forces. Additionally, a distributional controlling variable is introduced to ensure thorough exploration and enhance generation diversity during each diffusion/reverse step. Although the diffusion method is initially designed for a oneshot generative manner, the GRAPHARMmodel proposes an autoregressive diffusion model to generate graphs by sequentially predicting each row in the adjacency matrix [Kong et al., 2023]. The GRAPHARM masks nodes and corresponding edges in forward diffusion whose order is determined by a diffusion ordering network qϕ(σ|G0). In the reverse process, the GRAPHARM denoises only one node at each step (i.e., sequentially generates one row in the adjacency matrix) with the help of the graph attention network [Liao et al., 2019].

3.3 SGMon Graphs

Although EDP-GNN develops a score-based generative model to derive the adjacency matrix of the graph, the estimation for the score function depends on the noise scales at the discrete steps, which restricts its capacity to produce largescale graphs. GraphGDP [Huang et al., 2022a] leverages the variance-preserving SDE to disturb the adjacency matrix to random graphs. In the reverse process, Position-enhanced Graph Score Network (PGSN) incorporates the features of both nodes and edges and graph position information for permutation equivariant score estimation. Notably, GraphGDP defines a transformation in the forward process to associate continuous distribution with discrete graphs, which allows the model to learn additional graph information of intermediate diffusion steps. Moreover, GDSS [Jo et al., 2022] proposes a continuous-time SDE system to model the diffusion process over nodes and edges simultaneously, where Gaussian noise is directly added to the adjacency matrix and node features. The forward diffusion process on the weighted graph G at each infinitesimal time step can be modelled as:

where ft represents the linear drift coefficient. To reduce the computation in the reverse diffusion process, GDSS introduces a reverse-time SDE system with respect to nodes and edges as:

where ∇Xt log pt(Xt,At) and ∇At log pt(Xt,At) are the partial score functions, indicating the gradients of the joint log-density connecting the adjacency matrix A and node feature matrix X. A corresponding object function is proposed to jointly estimate the log density of nodes and edges:

where sθ,t(Gt) and sϕ,t(Gt) are the MLP advanced by the graph multi-head attention blocks [Baek et al., 2021a] to learn the long-term relationship. The GDSS approximates the expectation in Eq.(10) with Monte Carlo estimation, which requires fewer computation and sampling steps compared to the Langevin dynamics [Jo et al., 2022]. To further improve the generation quality, GDSS proposes an integrator to correct the estimated partial score by the score-based MCMC estimation. Note that GDSS is the very first diffusion framework that enables the generation of a whole graph based on node-edge dependency. However, the standard diffusion process would eliminate the features of the sparse graphs in a few steps, which may cause the score estimation uninformative in the reverse process. To address such limitation, a Graph Spectral Diffusion Model (GSDM) [Luo et al., 2022b] is introduced to perform the low-rank Gaussian noise insertion, which can gradually perturb the data distribution with less computation consumption while achieving higher generation quality. To be specific, in the diffusion process, GSDM performs spectral decomposition on the adjacency matrix A to obtain diagonal eigenvalue matrix Λ and eigenvectors U (i.e., A = UΛU⊤). Meanwhile, since the top-k diagonal entries in Λ can maintain most of the graph information, GSDM conducts the diffusion on the corresponding top-k largest eigenvalues in A for efficient computation. In addition, SGGM introduces a latent-based generative framework on the graph [Yang et al., 2023], which first encodes the high-dimensional discrete space to lowdimensional topology-injected latent space via a pre-trained variational graph autoencoder and then adopts score-based generative model for the graph generation.

4 Applications

In this section, we aim to review key applications for diffusion models on graphs, such as molecule and protein generations in chemistry and biology domains. The Figure 2 illustrates diffusion models on molecule and protein generation tasks. In Table 1, we summarize these applications.

4.1 Molecule Modeling

The goal of molecule modeling is to employ graph learning techniques for the purpose of representing to better perform downstream tasks, such as molecule generation [Hoogeboom et al., 2022]. In general, molecules can be naturally represented as graphs (e.g., atom-bond graphs), in which atoms are represented as nodes and chemical bonds are represented as edges. As such, graph learning techniques can be applied to analyze and manipulate molecular structures for various downstream tasks, such as drug discovery, computational chemistry, materials science, bioinformatics, etc. Furthermore, molecular graph modeling can be used to generate new molecules with desired properties by using advanced graph learning techniques such as VAE [Ma and Zhang, 2021], GNNs [Han et al., 2022], and reinforcement learning (RL) [Zhou et al., 2019]. Particularly, molecule modeling can be further classified into two tasks, namely, molecule conformation generation and molecular docking.

Molecule Conformation Generation

A molecule can be represented by three-dimensional geometry or conformation, in which atoms can be denoted as their Cartesian coordinates. The biological and physical characteristics of the molecule are significantly influenced by its threedimensional structure. Meanwhile, molecular conformations possess roto-translational invariance. As a result, several techniques avoid directly modeling atomic coordinates by using intermediary geometric variables, such as atomic distances, bond angles, and torsion angles, which also have rototranslational invariance [Shi et al., 2021]. However, as they seek to indirectly model these intermediate geometric variables, they may be subject to limitations in either the training or inference process. To address this issue, GeoDiff [Xu et al., 2022] treats atoms as particles in a thermodynamic system and simulates the diffusion process in nonequilibrium thermodynamics. By learning to reverse the diffusion process, the sampled molecules gradually diffuse backwards into the target conformation. Dynamic Graph Score Matching (DGSM) [Luo et al., 2021a] uses score matching based on a 2D molecular graph to generate the conformation structure of a molecule by modeling the local and long-range interactions of atoms.

Torsional Diffusion [Jing et al., 2022] defines the diffusion over a torus to represent torsion angles, providing a more natural parameterization of conformers. Besides, Torsional Diffusion leverages the torus as a representation of torsion angles for conformations generation. By incorporating a probabilistic analysis that enables probability calculations and atom classification, E(3) Equivariant Diffusion Model (EDMs) [Hoogeboom et al., 2022] enables the model to learn the denoising process in continuous coordinates and improve the generation of molecular conformations. As an extension of EDMs, equivariant energy-guided stochastic differential equations (EEGSDE) [Bao et al., 2023] adds energy functions to the model as a guide to fully learn the geometric symmetry of molecules to generate 3D molecular conformations.

In addition to adding energy guidance and learning the atomic coordinates of molecules and torsion angles, other domain knowledge can be introduced into the model for enhancing the molecular representation learning. For example, to model interatomic interactions in molecular representation, MDM [Huang et al., 2022b] considers the role of atomic spacing in iteratomic forces for molecular representation. More specifically, MDM treats atomic pairs with atomic spacing below a certain threshold as covalent bonds, as chemical bonds govern interatomic forces when atoms are close enough to each other. For atomic pairs with atomic spacing above a certain threshold, the van der Waals force is proposed to govern the interatomic forces. Additionally, to enhance the diversity of molecule generation, they introduce latent variables that are interpreted as control representations in each diffusion/reverse step of the diffusion model. DiffBridges [Wu et al., 2022b] designs an energy function with physical information and a statistical prior for molecule generation. It differs from other methods in its incorporation of physical prior into bridges, as opposed to learning diffusions as a combination of forward-time diffusion bridges.

Transformer architectures have achieved notable success in the fields of computer vision (CV) and natural language processing (NLP), such as ViT [Dosovitskiy et al., 2020], BERT [Kenton and Toutanova, 2019], GPT [Brown et al., 2020]. Similarly, graph transformer [Dwivedi and Bresson, 2021] is incorporated into discrete diffusion model with discrete diffusion [Austin et al., 2021] for graph generation. In particular, DiGress uses graph-based architectures and a noise model that preserves the marginal distribution of node and edge types [Vignac et al., 2023], rather than using uniform noise as a starting point. A denoising network is then augmented with structural features, enabling conditional generation through guidance procedures.

Since most existing molecular generation approaches generate graphs that are likely similar to training samples, Molecular Out-of-distribution Diffusion (MOOD) [Lee et al., 2022] incorporates out-of-distribution (OOD) control in the generative stochastic differential equation (SDE), to generate a new molecule graph that is distinct from those in the training set. GDSS [Jo et al., 2022] learns the underlying distribution of graphs by deriving score matching objectives tailored for the proposed diffusion process, enabling the estimation of the gradient of the joint logdensity w.r.t. each component.

Molecular Docking

Molecular docking is a computational method for predicting the preferred orientation of one molecule to a second molecule (typically a protein) when binding to each other. It's used in drug discovery to find the best fit of a small molecule into the active site of a target protein.

Autoregressive models are widely adopted to generate 3D molecules for the protein binding pocket [Shin et al., 2021]. However, autoregressive models might struggle with capturing complex relationships and interactions between residues in the pocket. To address these challenges, DiffBP [Lin et al., 2022] generates 3D molecular structures in a nonautoregressive manner while satisfying the physical properties of the molecule, based on the protein target as a constraint. Using diffusion models and SE(3)-equivariant networks, TargetDiff [Guan et al., 2023] learns atomic types and atomic coordinates to generate protein target molecules with satisfying geometric properties.

Fragment-based drug discovery is also a widely adopted paradigm in drug development, which can provide promising solutions for molecular docking by generating 3D molecules fragment-by-fragment and incorporating diffusion models. For instance, FragDiff [Peng et al., 2023] generates 3D molecules fragment-by-fragment for pockets. In each generation step, FragDiff generates a molecular fragment around the pocket. The atom types, atom coordinates and bonds on this fragment are predicted. Then the fragments are gradually joined together to produce the complete molecule. Given some fragments, DiffLink [Igashov et al., 2022] generates the rest of a molecule in 3D. The generator of DiffLink is an E(3) equivariant denoising diffusion model to generate fragments. It is conditioned on the positions of the fragment atoms, and optionally also on the protein pocket that the molecule should fit into. Finally, DiffLink splices these fragments into a complete drug candidate molecule. Similar to the transformation of sentiment classification tasks into generative tasks in the NLP field [Liu et al., 2023], DiffDock [Corso et al., 2022] uses diffusion model to form docking pose prediction problem as a generation problem and executes a reverse diffusion process using separate ligands and proteins as inputs by randomly selecting the initial states and ranking them.

4.2 ProteinModeling

Protein modeling is to generate and predict the structure of proteins. This task is instrumental in comprehending the function and interactions of proteins, and is widely used in the fields of drug discovery and the design of novel proteins with specific characteristics. Previously, proteins have been represented as sequences of amino acids, leading to successes in modeling proteins using language models [Ferruz et al., 2022]. With the advent of diffusion models in image generation [Ramesh et al., 2021], a growing number of applications using diffusion models in protein modeling have emerged.

Protein Generation

The objective of computational protein design is to automate the generation of proteins with specific structural and functional properties. This field has experienced significant advancements in recent decades, including the design of novel 3D folds [Jumper et al., 2021], enzymes [Giessel et al., 2022] and complexes [R´eau et al., 2023].

Pre-training protein representations on enormous unlabeled protein structures have drawn more and more interest from researchers. Siamese Diffusion Trajectory Prediction (SiamDiff) [Zhang et al., 2022] obtains counterparts by adding random structural perturbations to natural proteins and diffuses them structurally and sequence-wise through the pretraining process. The diffusion process of the original protein and its counterpart is referred to as two related views. In this process, SiamDiff uses the noise of one view to predict the noise of the other view to better learn the mutual information between the two views. In contrast to pre-training techniques, ProteinSGM [Lee and Kim, 2022] applies conditional generation, paint credible backbones and functional sites into structures of predetermined length to generate proteins. ProSSDG [Anand and Achim, 2022] combines the protein's structure and sequence to generate proteins with the desired 3D structures and chemical properties. Based on a brief description of the protein's topology, ProSSDG generates a complete protein configuration.

Despite recent developments in protein structure prediction, it is still difficult to directly generate a variety of unique protein structures using DNNs techniques. DiffFold [Wu et al., 2022a] generates protein backbone stuctures by imitating natural folding progress. DiffFold develops new structures by denoising from a chaotic, unfolded state towards a stable folded shape. In addition, DiffFold represents protein backbone structure as a sequence of sequential angles representing the relative orientation of the component amino acid residues.

A stable protein backbone that has the motif is referred to as a scaffold. It can greatly benefit from building a scaffold that supports a functional motif. SMCDiff [Trippe et al., 2023] uses a particle filtering algorithm for conditional sampling of protein backbone structures, where priority is given to backbone structures more consistent with the motif.

Immune system proteins (called antibodies) attach to particular antigens like germs and viruses to defend the host. The complementarity-determining regions (CDRs) of the antibodies play a major role in regulating the interaction between antibodies and antigens. DiffAntigen [Luo et al., 2022a] jointly generates the sequence and structure of the CDRs of an antibody, based on the framework region of antibody and the target antigen. DiffAntigen is able to regulate the generation at the antigen structure, not just in the framework region. Additionally, it can also predict the side-chain orientation. RFdiffusion [Watson et al., 2022] combines a diffusion model with a protein prediction model, RoseTTAFold [Baek et al., 2021b]. During the forward diffusion progress, RFdiffusion perturbs the 3D structural coordinates locally to enhance the model's representational capacity.

Protein-ligand Complex Structure Prediction

The prevalence of protein-ligand complexes makes predicting their 3D structure valuable for generating new enzymes and drug compounds. NeuralPLexer [Qiao et al., 2022] predicts the structure of protein-ligand complexes by combining multi-scale induced bias in biomolecular complexes with diffusion models. It takes molecular graphs as ligand input and samples 3D structures from a learned statistical distribution. To overcome the difficulties of high-dimensional modeling and to extend the range of protein-ligand complexes, DiffEE [Nakata et al., 2022] proposes an end-to-end diffusion generative model, which is based on pre-trained protein language model. DiffEE is able to generate a variety of structures for protein-ligand complexes with correct binding pose.

5 Future Challenges and Opportunities

There are increasing efforts to develop diffusion models on graphs. Next we discuss potential future research directions. Conditional Generation for Graph Diffusion Models. Incorporating conditions into generative models is critical to guide desired generation. In graph domain, to generate molecules and proteins with specified properties, it is significant to set certain constraints on the design of graph generative models. Thus, introducing extra information as conditions into graph diffusion models has become an imperative research direction. One type of extra knowledge can be formed by a knowledge graph [Chen et al., 2022], which can assist in controlling the generation process to obtain desired graphs, and enhancing the diversity of graph generation.

Trustworthiness for Graph Diffusion Models. Recent years have witnessed growing concerns about AI models' trustworthiness [Liu et al., 2022; Dai et al., 2022; Chen et al., 2023]. As one of the most representative AI-powered applications, graph generation might cause unintentional harm to users and society in various real-world tasks, especially those in safety-critical fields such as drug discovery. Therefore, how to build trustworthy graph diffusion models has become critical in both academia and industry

Evaluation Metrics. The evaluation of graph generation remains a challenge. Most existing metrics are usually based on graph statistics and properties (e.g., node' degree and sparsity) [O'Bray et al., 2022], which are not fully trustable. Meanwhile, validity and diversity for graph generation are important in different applications. Thus, efforts are desired to quantitatively measure the quality of generated graphs.

Graph Diffusion Applications. Most existing graph diffusion techniques are used for molecule and protein generation, while many applications on graphs are rarely explored, such as Recommender Systems, Graph Anomaly Detection, and Causal Graph Generation For example, graph learning techniques have been successfully used for recommendations (i.e., distributions) [Fan et al., 2019b; Fan et al., 2022b]. Thus, diffusion models on graphs have the potential to better generate recommendation lists for users. Anomalies refer to graph objects such as nodes, edges, and sub-graphs. Recent works have shown that diffusion models can be leveraged to purify image data for better adversarial robustness [Xiao et al., 2022]. Thus, graph diffusion models provide great opportunities to improve graph anomaly detection.

6 Conclusion

As one of the most advanced generative techniques, diffusion models have achieved great success in advancing various generative tasks, particularly in the image domain. Similarly, many efforts have been devoted to studying graph generation based on diffusion model techniques. However, it lacks a systematic overview and discussion of the state-of-the-art diffusion models on graphs. To bridge this gap, we provided a comprehensive overview of deep diffusion models on graphs including representative models and applications. We also discussed some promising future research directions.

Acknowledgments

The research described in this paper has been partly supported by NSFC (project no. 62102335), General Research Funds from the Hong Kong Research Grants Council (Project No.: PolyU 15200021 and 15207322), internal research funds from The Hong Kong Polytechnic University (project no. P0036200 and P0042693), Collaborative Project no. P0041282, and SHTM Interdisciplinary Large Grant (project no. P0043302). This research is also supported by the National Science Foundation (NSF) under grant numbers CNS1815636, IIS1845081, IIS1928278, IIS1955285, IIS2212032, IIS2212144, IOS2107215, and IOS2035472, the Army Research Office (ARO) under grant number W911NF21-1-0198, the Home Depot, Cisco Systems Inc, Amazon Faculty Award, Johnson&Johnson, and SNAP.