Autoregressive Diffusion Model for Graph Generation
Authors: Lingkai Kong
Jiaming Cui
Haotian Sun
Yuchen Zhuang
B. Aditya Prakash
Chao Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph generation
diffusion based generative model

Abstract:  Diffusion-based graph generative models have recently obtained promising results for graph generation. However, existing diffusion-based graph generative models are all one-shot generative models that apply Gaussian diffusion in the  dequantized adjacency matrix space. Such a strategy can suffer from difficulty in model training, slow sampling speed, and incapability of incorporating constraints. We propose an \emph{autoregressive diffusion} model for graph generation. Unlike existing methods, we define a node-absorbing diffusion process that operates directly in the discrete graph space. For forward diffusion, we design a \emph{diffusion ordering network}, which learns an optimal node absorbing ordering from graph topology. For reverse generation, we design a \emph{denoising network} that uses the reverse node ordering to efficiently reconstruct the graph by predicting one row of the adjacency matrix at a time. Based on permutation invariance of graph generation, we show that the two networks can be jointly trained by optimizing a simple lower bound of data likelihood. Our experiments on six diverse datasets show that our model achieves better or comparable generation performance with previous state-of-the-art, and meanwhile enjoys fast generation speed.

Under review as a conference paper at ICLR 2023
AUTOREGRESSIVE DIFFUSION MODEL FOR GRAPH GENERATION
Anonymous authors Paper under double-blind review
ABSTRACT
Diffusion-basse bratus graph generative models have recently obtained promising results for graph generation. However, existing diffusion-based graph generative models are all one-shot generative models that apply Gaussian diffusion in the dequan- tized adjacency matrix space. Such strategy can suffer from difficulty in model training, slow sampling speed, and incapability of incorporating constraints. We propose an autoregressive diffussio model for graph generation. Unlike existing methods, we define node-absorbing diffusion process that operates directly in the discrete graph space. For forward diffusion, we design a diffusion ordering network, which learn an optimal node absorbing ordering from graph topology. For reverse generation, we design a denoising network that uses the reverse node ordering efficiently reconstruct the graph by predicting one row of the adja- cency matrix at time. Based on permutation invariance of graph generation, we show that the two networks can be jointly trained by optimizing a simple lower bound of data likelihood. Our experiments on six diverse datasets show that our model achieves better or comparable generation performance with previous state- of-the-art, and meanwhile enjoys fast generation speed.
INTRODUCTION
Generating graphs from target distribution is a fundamental problem in many domains such as drug discovery (Li et al., 2018), material design (Maziarka et al.) 2202)). social network analysis (Grover et al. 2019), and public health (Yu et al. 2020). Deep generative models have recently led promising advances this problem. Different from traditional random graph models (Erdos) et al. 1960 Allert & Barabási] 2002), these methods fit graph data with powerful deep generative models including variational auto-encoders (Simonovsky Komodakis 2018), generative adversar- ial networks (Maziarka et al. 2020), normalizing flows (Madhawa et al.) 2019), and energy- -based models (Liu et al. 2021). These models are learned to capture complex graph structural patterns and then generate new figh-fi graphs with desired properties.
Recently, the emergence of probabilistic diffusion models has led to interest diffusion- based graph generation (Jo et al., (022). Diffusion models decompose the full complex transformation between noise and real data into many small steps of simple diffusion. Compared with prior deep gener- ative models, diffusion models enjoy both flexibility
modeling architecture and tractability of the model's probability distributions. To the best of our knowledge, there are two existing works on diffusion-based graph generation:
Niu al. (2020) model the adjacency matrices using score matching at different noise scales, and uses annealed Langevin dynamics to sample new adjacency matrices for generation; Jo et al. (2022) propose continuous-ting graph diffusion model that jointly models adjacency matrices and node features through stochastic differential equations (SDEs).
However, existing diffusion- based graph generative models suffer from three key drawbacks: (1) Generation Efficiency. The sampling processes Niu et al. (2020):Do et al. (2022) are slow, as Niu eet al. (020)) requires a large number diffusion noising levels and Jo et al. (2022) needs to solve a complex system SDEs. (2) Continuous Approximation. They convert discrete graphs to continuous state spaces by adding real-valued noise to graph adjacency matrices. Such dequantization can distort the distribution of the original discrete graph structures, thus increasing the difficulty of model training. (3) Incorporating constraints. They are both one-shot generation models and hence cannot easily incorporate constraints during the one-shot generation process.

---

Under review as a conference paper at ICLR 2023
We propose an autoregressivve graph generative model named GRAPHARM via autoregressive diffu- sion on graphs. Autoregressive diffusion (ARM) (Hoogeboom et al. 2022a) is an absorbing diffu- sion process (Austin et al. 202I) for discrete data, where exactly dimension of the data decays to the absorbing state at each diffusion step. In AMMM we design aode-absorbing autoregres- sive diffision for graphs, which diffuses a graph directly in the discrete graph space instead of in the dequantized adjacency matrix space. The forward pass absorbs one node in each step by masking it along with its connecting edges, which repeated until all the nodes are absorbed and the graph becomes empty. We further design a diffusion ordering network in GRAPHARM, which is jointly trained with the reverse generator to learn an optimal node ordering for diffusion. Compared with random ordering as in prior ARM models (Hoogeboom et al.) 2022a), the learned diffusion ordering not only provides a better stochastic approximation of the true marginal graph likelihood, but also eases generative model training by leveraging structural regularities.
The backward pass in GRAPHARM recovers the graph structure by learning to reverse the node- absorbing diffusion process with denoising network. The reverse generative process is autore- gressive, which makes GRAPHIARM easy to handle constraints during generation. However, a key challenge is to learn the distribution of reverse node ordering for optimizing the data likelihood. We show that this difficulty can be circumvented by just using the exact reverse node ordering and op- timizing simple lower bound of likelihood, based on the permutation invariance property of graph generation. The likelihood lower bound allows for jointly training the denoising network and the diffusion ordering network using reinforcement learning procedure and gradient descent.
The generation speed of GRAPHARM is much faster than the existing graph diffusion models (Jo al. 2022, Niu et al., 2020). Due the autoregressive diffusion process in the node space, the number of diffusion steps in GRAPHARM is the same as the number of nodes, which is typically much smaller than the sampling steps in (Jo et al. 2022, Niu et al., 2020). Furthermore, at each step of the backward pass, we design the denoising network to predict one row of the adjacency matrix at one time. The edges to be predicted follow a mixture of Bernoulli distribution to ensure dependencies among each other. This makes GRAPHARM much more efficient than most previous autoregressive graph generation models.
Our key contributions are follows: (1) To the best of our knowledge, our work is the first autore- gressive diffusion-based graph generation model, underpinned by a new node self-absorbing diffu- sion process. (2) GRAPHARM learns optimal node generation ordering and thus better leverages the structural regularities for autoregressive graph diffusion. (3) We validate our method on both synthetic and real-world graph generation tasks, which we show that GRAPHARM outperforms existing graph generative models and is efficient in generation speed.
2 BACKGROUND
Diffusion Model and Absorbing Diffusion Given training instance In E R. sampled from the underlying distribution (data(@o)) diffusion model defines a forward Markov transition kernel (<::/a;-11 to gradually corrupt training data until the data distribution transformed into a simple noisy distribution. The model then learns to reverse this process by learning denoising transition kernel parameterized by a neural network po (0:-11 (z:))
Most existing works on diffusion models use Gaussian diffusion for continuous-state data. To apply Gaussian diffusion on discrete data, one can use dequantization method by adding small noise to the data. However, dequantization distorts the original discrete distribution, which cause difficulty in training diffusion-basee models. For example, dequantization on graph adjacency matrices can destroy graph connectivity information and hurt message passing. Austin al. (2021) Hoogeboom et al.] (022)) introduce several discrete state space diffusion models using different Markov transition matrices. Among them, the absorbing diffusion is the most promising one due to its simplicity and strong empirical performance.
Definition 1 (Absorbing Discrete Diffusion). An absorbing diffusion is a Markov destruction pro- cess defined in the discrete state space. Al transition time step i, each element x. in dimension i is independently decayed into an absorbing state with probabilities atl).
The absorbing state can be a [MASK] token for texts or gray pixel for images (Austin et al. 202
The diffusion process will converge to stationary distribution that has all the mass the absorbing
2

---

Under review as a conference paper at ICLR 2023
state. The reverse of the absorbing diffusion is learned with categorical distribution generate the original data. Typically, the decaying probabilities ((t) need to be small and the diffusion steps T need to be large to attain good performance.
Autoregressive Diffusion Model Although absorbing diffusion directly operates on the discrete data, it still needs a large number of diffusion steps and thus its generation process can be slow. Autoregressive diffusion model (ARM) (Hoogeboom et al.] (022a) describes fixed absorbing dif- fusion process where the generative steps is equal to the dimensionality of the data, e.g., the number of pixels in an image the number of tokens in piece of text.
Definition 2 (Autoregressive Diffusion). An autoregressive diffusion is a stochastic absorbing pro- cess where exactly one dimension decays to the absorbing state at a time. The absorbing diffusion repeated until all the D dimensions are absorbed.
An equivalent way to describe this process is to first sample a permutation E Sp. where SD represents the set of all permutations of the dimension indices 1..... D. Then each dimension of the data decays in that order towards the absorbing state. The corresponding generative process then models the variables in the exact opposite order of the permutation. ARM amounts to absorbing diffusion with continuous time limit, as detailed in Appendix
While ARM offers an efficient and general diffusion framework for discrete data, two key questions remains to be addressed for applying ARM for graphs: (1) How do we define absorbing states for inter-dependent nodes and edges in graphs without losing the efficiency of ARM? (2) While ARM imposes uniform ordering for arriving at an order-agnostic variational lower bound (VLB) of like- lihood, random ordering fails to capture graph topology. How do we obtain a data-dependent ordering that leverages graph structural regularities during generation? In the next section, we ad- dress these two challenges in our proposed GRAPHARM model.
METHOD
A graph is represented by the tuple G = (V,E) with node set V = (Vi,-.. ,v, and edge set E (t),,y)(es uy)les, Un E V)J. We denote by [V] and = [E] the number of nodes and edges in G respectively. Our goal is to learn a graph generative model from a set of training graphs. We assume the graphs are unattributed and focus on graph topology generation.
3.1 AUTOREGRESSIVE GRAPH DIFFUSION PROCESS
Due to the dependency between nodes and edges, it is nontrivial apply absorbing diffusion Austin et al. T02T) in the discrete graph space. We first define absorbing node state on graphs as follows:
Definition 3 (Absorbing Node State). When node U; enters the absorbing state, (1) it will be masked and (2) it will be connected to all the other nodes in G by masked edges.
Instead of only masking the original edges, we connect the masked node e; to all the other nodes with masked edges as we cannot know v; 's original neighbors in the absorbing state. With the ab- sorbing node state defined, we then need a node decay ordering for the forward absorbing pass. A naïve strategy is to use a random ordering sampled from a uniform distribution as in (Hoogeboom al. 2022a). In the reverse generation process, the variables will be generated in the exact reverse order, which also follows a uniform distribution. However, such strategy is problematic for graphs First, different graph datasets have different structural regularities, and it is key to leverage such reg- ularities to ease generative learning. For example, sommunity-structured graphs typically consist of dense subgraphs that are loosely overlapping. For such graphs, it is an easier learning task to generate community first and then add the others, but random node ordering cannot leverage such local structural regularity, which makes generation more difficult. Second, to compute the like- lihood, we need to marginalize over all possible node orderings due to node permutation invariance. will be more sample efficient we can use an optimized proposal ordering distribution and use importance sampling compute the data likelihood.
To address this issue, we propose to use a diffusion ordering network (a Go) such that, at each diffusion step I, we sample from this network to select node (t())) to be absorbed and obtain the
3

---

Under review as a conference paper at ICLR 2023
Masked edge
Masked node
2 qo Ga)
(o(o(2))(o,,m
Pa(Ci(Ga)
Gn
G1
G2
G₁
Figure I: The autoregressive graph diffusion process. In the forward pass, the nodes are autoregres- sively decayed into the absorbing states, dictated by an ordering generated by the diffusion ordering network (o)) In the reverse pass, the generator network Po((G((2+11 reconstructs the graph structure using the reverse node ordering.
corresponding masked graph G. (Figure 1. This leads to the following definition of our graph autoregressive diffusion process:
Definition (Autoregressive Graph Diffusion Process). In autoregressive graph diffusion, the node decay ordering is sampled from a diffusson ordering network qs qo (oo) parameterized by 6. Then, exactly one node decays to the absorbing state a time according to the sampled diffusion ordering. The process proceeds until all the nodes are absorbed.
The diffusion ordering network follows recurrent structure (a Go) = II 90(0, Guu ((t))) At each step f, the distribution of the t-th node o, conditioned on the original graph Go and the generated node ordering up to L
i.e.,T<<t)- We encode the structural information in the graph. To capture the partial ordering, we add positional encodings into node features (Vaswani et al. (017) as (Chen al. 2021). We denote the updated node embedding of node ey after passing the GNN as h; and parameterize qø (0 Go. (<t)) as categorical distribution:
graph neural network (GNN) to
exp(h!)
go(or|Go,
Everas exp(hş)
where VM is the set of node indices that have been masked.
With 9o (a Go), GRAPHARM can learn to optimize node ordering for diffusion. However, this also requires us to infer the reverse generation ordering in the backward pass. Inferring such reverse generation ordering difficult since we do not have access the original graph Go in intermediate backward steps. In Section 3.3 we show that it is possible to circumvent inferring this generation ordering by leveraging the permutation invariance of graph generation.
3.2 THE REVERSE GENERATIVE PROCESS
In the generative process, denoising network po (Ge Gr+ will denoise the masked graph in the
reverse order of the diffusion process. We design pe GG G as graph attention network (GAT)
(Veličković et al., 2018: Liao et al.) 2019) parameterized by 6, so that the model can distinguish the masked and unmasked edges. For clarity, we use the vallina GAT to illustrate the computing process. However, one can adopt any advanced graph neural network with attentive message passing.
At time f. the input to the denoising network po Do(GlGG+4) is the previous masked graph G A direct way to use G which contains all the masked nodes with their corresponding masked edges. However, during the initial generation steps, the graph is nearly fully connected with masked edges. This has two issues: (1) the message passing procedure will be dominated by the masked edges which makes the messages uninformative. (2) Storing the dense adjacency matrix is memory expensive, which makes the model unscalable to large graphs. Therefore, during each generation step, we only keep the masked node to be denoised with its associated masked edges, while ignoring the other masked nodes. We refer the modified masked graph Gy, shown in Figure
The denoising network first uses an embedding layer to encode each node i into a continuous embedding space, i.e., h; Embedding(e)) (v.). At 1-th message passing, update the embedding of
4

---

Under review as a conference paper at ICLR 2023
Masked edge
Masked node
GAT
G+11
G
Po(G((Goa)
Mixture Bernoulli
Ge
Figure 2:
The generation procedure step & with the denoising network Pe pa (Gr(G+41):
node v; by aggregating the attentive messages from its neighbor nodes:
exp(LeakyRal.Uja (h ELENs exp(LeakyReLU(a")) (Wh, Wh,))* h; = ReLU
Oi.j =
Σ JEN,
on, Why
(2)
where W is the weight matrix, a is the attention vector. In Eq 2 the attention mechanism enables the model to distinguish the message comes from a masked edge. After L rounds of message passing, we obtain the final embedding h for each node, then we predict the edges between the new node Vo(t) with all previously denoised nodes (U>(>e)}- One choice to sequentially predict these edges in You et al. 2018b) Shi et al. 2020). However, this sequential generation process takes (n?)) steps, which infffciint. Instead, we predict the connections of the new node to all previous nodes at once using mixture of Bernoulli distribution as in (Liao et al. (019).. The mixture distribution can capture the dependencies among edges be generated meanwhile reduce the autoregressive generation steps O(n).
3.3 TRAINING OBJECTIVE
We use approximate maximum likelihood as the training objective for GRAPHARM. We first derive the variational lower bound (VLB) of likelihood as:
log pe (Go) log (f pCGa..)
g (Go)
g Go) dG1:n
> BggGr Go) (ogp(Gimm) +log - log dogg((Gin)GGo)
Σ Po KL(g(o), "o. ,0, Gn)),
= (o
(3)
where Go:n denotes all values of G, for /. = 0, ... and p(ar, ...
(n) is the distribution of the generation ordering. detailed derivation Eq. is given in Appendix A.3
As we can see from Eq. introducing the diffusion ordering network requires to infer reverse gen- eration ordering p(a), Tn Gn. This difficult we do have the original graph Go in the intermediate generation process. However, since graph generation is node permutation invariant, we do need learn such generation ordering explicitly. Note that the first term in Encourrgee the model to generate the nodes in the exact reverse ordering of the diffusion process. This pushes the generation ordering p(a).... an Fn/G,) close to the diffusion ordering go (o( ... a,,) (G)) during training and the KI KL-ddieegeence term will converge to O. Therefore, we can ignore the KI.-divergence term and finally arrive at simple training objective:
Terain Eggy. danoslooi" G..) Σ Po
Compared with the random diffusion ordering, our design has two benefits: (1) We can automati- cally learn the optimal node generation ordering which leverages the structural information in the graph. (2) We can consider the diffusion ordering network as optimized proposal distribution of importance sampling for computing the data likelihood, which more sample-efficient than an uniform proposal distribution.

---

Under review as a conference paper at ICLR 2023
3.4 PARAMETER OPTIMIZATION
Learning the parameters of GRAPHARM is challenging, because we need to evaluate the expecta- tion of the likelihood over the diffusion ordering network. We use reinforcement learning (RL) procedure by sampling multiple diffusion trajectories, thereby enabling training both the diffusion ordering network (o Go) and the denoising network pe (G₃ (G++1) using gradient descent.
Specifically, at each training iteration, we explore the diffusion ordering network by creating M diffusion trajectories for each training graph G Each trajectory is sequence of graphs (G(..)) IStSn where the node decay ordering is sampled from ( The denoising network pa (G(GG( is then trained minimize the negative VLB using stochastic gradient descent (SGD):
7 M
V Σ ΣΣ log pe (G((.m) (((T))
0 0
(5)
iEBu
where Birain is the a minibatch sampled from the training data.
To evaluate the current diffusion ordering network, create M trajectories for each validation graph and compute the negative VLB of the denoising network to obtain the corresponding rewards R7 Eie E. logpo (((T)) Then, the diffusion ordering network can be updated with common RL optimization methods, e.g., the REINFORCE algorithm (Willims 1992):
712 M
Σ
R2" log go Go))
(6)
In practice, one can also explore other advanced RL technique, e.g., PPO2, (Schulman et al. 2017) but we find that the simple REINFORCE algorithm has already achieved outstanding performance. The detailed training procedure is summarized in Algorithm Appendix. A.4
3.5 COMPARISON WITH OM
OM (Chen al. 2021 also models the node ordering for autoregressive graph generation, but method differs from OM in two aspects. (1) The motivations are different. Our method is motivated by autoregressive diffusion and treats the graph sequences in the diffusion process as the latent variable; OM treats the node ordering as the latent variable and infers its posterior distribution in a way similar to Variational autoencoder (VAE). (2) Our training objective much simpler than OM. First, we do not need to compute the complicated graph automorphism, which requires some approximation algorithms to compute. Second, our training objective does not involve the entropy of the node ordering distribution. Existing works [Lucas et al. 2019b a have shown that the entropy term in the VAE objective can easily cause posterior collapse.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Dataset. We evaluate the performance of GRAPHARM on six diverse graph generation benchmarks,
covering both synthetic and real-world graphs from different domains: (1) Community-small (You
al. 2018b), (2) Caveman (You) 2018), (3) Cora (Sen al. 2008). (4) Breast (Gonzalez-Malerva
et al. 2011), (5) Enzymes (Schomburg et al. 2004) and (6) Ego-small (Sen et 2008). For each dataset, we use 80% of the graphs as training set and the rest 20% as test sets. Following (Liao al.,
2019). we randomly select 20% from the training data as the validation set. We generate the same amount of samples as the test set for each dataset. More details can be seen in Appendix
Baselines. We compare GRAPHARM with the following baselines: DeepGMG (Li et al. 2018) and GraphRNN (You et al.) 2018b) are RNN-based autoregressive graph generation models.
GraphAF (Shi et al.] (020) and GraphDF (Luo et al. 2021) are flow-based autoregressive models.
GRAN (Lao et 2019 is an autoregressive model conditioned on blocks. OM (Chen et al. 2021) is an autoregressive model that infers node ordering using variational inference. Graph (Si- monovsky & Komodakis 2018) is an one-shot model based on VAE. EDP-GNN (Niu et al. 2020
and GDSS (Jo et al. 2022) scored-based one-shot methods.

---

Under review as a conference paper at ICLR 2023
Community-small
Caveman
Cora
Model
Deg.
Clus.
Orbit
Time/s
Deg.
Clus.
Orbit
Time/s
Deg.
Clus.
Orbit
Time/s
DeepGMG
0.220 0.950 0.400
496.6
1.752
1.642
0.2122
530.2
GraphRNN
0,080 0.120 0.040
16.4
0.371
1.035
0.033
27.0
1.689
0.608
0.308
33.3
GraphAF
0,180 0.200 0.020
19.3
0.269
0.587
0.422
20.5
0.176
0.080
0.094
108.5
GraphDF
0.060 0.120 0.030
10.3
0.077
0.373
0.051
18.5
0.454
0.074
0.256
129.7
Gra
0.350 0.980 0.540
0.2
1,402
1.086
1.391
0.2
1.521
1.740
0.788
0.3
GNF
0,200 0.200 0.110
GRAN
0,060 0.110 0.050
1.8
0.043 0.130
0.018
2.5
0.125
0.272
0.127
5.1
OM
0,047 0.130 0.008
2.0
0.032
0.076
0.027
3.0
0.249
0.201
0,145
5.6
EDP-GNN
0.053
0.144 0.026
2898.7
0.032
0.168
0.030
1823.4
0.093
0.269
0.062
4655.
GDSS
0.045
0.086
0.007
435.1
0.019
0.048
0.006
514.0
0.160
0.376
0.187
421.4
GRAPHARM
0.038
0.090 0.003
1.9
0.048 0.022 0.014
2.7
0.281
0.134 0.114
4.5
Breast
Enzymes
Ego-small
Model
Deg.
Clus.
Orbit
Time/s
Deg.
Clus.
Orbit
Time/s
Deg.
Clus.
Orbit
Time/s
DeepGMG
0.040 0.100 0.020
477
GraphRNN
0.103
0.138
0.005
31.0
0.017
0.062
0.046
19.2
0.090 0.220 0.003
18.7
GraphAF
0.111
0.407
0.003
53.1
1.669
1.283
0.266
28.6
0.030 0.110 0.001
6.9
GraphDF
0.283
0.078
0.035
62.4
1.503
1.061
0.202
39.8
0.040 0.130 0.010
10.2
GrR
1,591
1.993
1.050
0.2
1.369
0.629
0.191
0.7
0.130 0.170 0.050
0.3
GNF
0.030 0.100 0.001
GRAN
0.073
0.413
0.010
2.1
0.054
0.078
0.017
3.2
0.030 0.029 0.014
1.2
OM
0.042
0.140
0.005
2.8
0.051
0.083
0.024
2.4
0.024 0.035 0.018
1.4
EDP-GNN
0.131
0.038
0.019
3694.2
0.023
0.268
0.082
2155.5
0.052 0.093 0.007
3851.9
GDSS
0.113
0.020
0.003
858.4
0.026
0.061
0.009
443.0
0.021
0.024 0.007
260.9
GRAPHARM
0.031
0.046
0.002
2.3
0.033
0.059
0.019
3.5
0.016 0.014 0.012
1.2
Table 1: Generation results on the six datasets for all the methods. We report the MMD distance between the test datasets and generated graphs. Best results are bold and the second best values underlined (smaller the better). "_" denotes out-of-resource. that take more than 10 days to run.
Parameter Settings. We use ADAM with 31 = 0.9 and B 0.999 as the optimizer. The learn- ing rate is set for 10 - and 5 x 10-4 4 for the denoising network and diffusion ordering network respectively all the datasets. For fair comparison, attention network architecture as the baseline GRAN; the diffusion ordering network uses the same graph attention network architecture the baseline OM. As OM is compatible with any existing autoregressive methods, we use the strongest autoregressive baseline GRAN as its backbone. More implementation details and parameter settings provided in in Appendix A.6
denoising network uses the same graph
Evaluation metrics. Following previous work (You et al.) 2018b Jo et al. 2022), we measure generation quality using the maximum mean discrepancy (MMD) the generated graphs and the test graphs. Specifically, we compute the MMD of degree distribution, clustering coefficient, and orbit occurrence numbers of 4 nodes between the generated set and the test set. We also report the generation time of different methods.
distribution distance between
4.2 EXPERIMENTAL RESULTS
Main Results Table I shows the generation performance on the six benchmarks for all the meth- ods. (1) As we can see, our method can outperform or achieve competitive performance compared with the baselines. In terms of efficiency, our model is on par with the most efficient autoregressive baseline GRAN, and 10- 100X faster than other baselines except for the one-shot baseline Graph- VAE. However, GraphVAE's generation quality is much worse than ours as it generates all edges independently from the latent embedding and cannot well capture complex edge dependencies. (2) GDSS is the strongest baseline. However, its generation is extremely slow as it needs to solve complex SDE system in the reserve process. Our GRAPHARM model is more than 100 times faster than GDSS in generation on almost all the datasets. The other graph diffusion model EDP-GNN even slower than GDSS as its generation process uses annealed Langevin Dynamics with many different noise levels. (3) GRAPHARM also outperforms existing autoregressive graph generative models by large margins. This because they adopt a fixed node ordering when training the gener- ative model while GRAPHARE RM automatically learns an optimal generation ordering for the graph.
7

---

Under review as a conference paper at ICLR 2023
Though OM also learns node ordering distribution, GRAPHARM consistently outperforms it on all the datasets. This is because OM uses the VAE objective which may suffer from posterior collapse, while GRAPHARM has much simpler training objective based on autoregressive diffusion.
Constrained Graph Generation In this set of experiments, study GRAPHARM'S capa- bility in constrained graph generation by com- paring it with the strongest one-shot and autore- gressive baselines. We use the Caveman dataset for constrained graph generation, with the con- straint that the maximum node degree is no larger than 6. The detailed setup Appendix A.7 Table. D shows the constrained generation performance on the Caveman dataset. GDSS and EDP-GNN are both one-shot generative model and thus they cannot guarantee the con- straints are satisfied during sampling. We find that more than half of their generated samples invalid. For autoregressive baselines, we apply the degree checking procedure on the two strongest baselines, Le.NGRAN and OM. As can see, GRAPHAARM can generate constrained samples that are closer to the data distribution. This is useful for many real-world applications. For example, when designing the contact networks of patients and healthcare workers hospitals, a constraint of degrees for healthcare workers can help avoid superspreaders and potential infectious disease outbreaks (Jang et al., 2019 Adhikari et al. 2019).
Method
Validity Deg.
Clus.
Orbit
EDP-GNN
39%
GDSS
34%
GRAN
100%
0.208
0.231
0.158
OM
100%
0.190
0.168
0.132
GRAPHARM
100%
0.179
0.135
0.141
Table 2:
Constrained graph generation results on the Caveman dataset.
Evaluation of Log likelihood We further evaluate the expected negative log-likelihood (NLL) across node permutations on the test sets. For GRAN, we sample 1000 node per- mutations from the uniform distribution. For OM and GRAPHARM, we sample 1000 node permutations from the ordering network. Ta- ble 3 shows the expected NL.. on the test sets for Community-small and Breast. As shown, GRAPHARM can achieve competitive results with OM and outperform GRAN by large margins. This is because both OM and GRAPHARM learn an optimal node ordering distribution; sampling from this distribution is more sample efficient than the uniform distribution. Though GDSS and EDP-GNN are also diffusion based graph generative model, they cannot provide the likelihood. Note that GDSS involves system of SDEs and cannot directly use the proba- bility flow ODE [Song et al. 2021) to compute the likelihood. This can be a drawback in some density-based based downstream tasks, e.g., outlier detection.
Community-sme small Breast
GRAN
23.04
247.18
OM
16.82
187.22
EDP-GNN
N/A
N/A
GDSS
N/A
N/A
GRAPHARM
15.79
190.34
Table Test set negative log- likeliihddood (NLL) on Community-smon small and Breast datasets. N/A repre- sents the model cannot provide the NLL.
Effect of Diffusion Ordering We further val- idate the superiority of the leamned diffusion ordering in GRAPHARRM over random node ordering for graph generation. We compare GRAPHARN PPHHAMM RM with an ablation OA-ARM, which uses random node ordering (Hoogeboom al. 2022a) for graph generation. Table 4 shows the generation performance and generation or- dering of GRAPHARM and OA-ARM on the Community-smen dataset. As shown, with the random generation ordering, the generation performance drops significantly. This be- cause random generation ordering fails to leverage the structural regularities in the graphs and thus learning the generative model is much more difficult. To evaluate the node generation order- ing, the spectral graph clustering method to partition the nodes into two clusters for each
Deg.
Clus.
Orbit
Counts
OA-ARM GRAPHARM
0.159
0.372
0.291
6.9
0.038
0.090
0.003
2.6
Table 4: Generation performance and node gener- ation ordering of GRAPHARM and OA-ARM on the Community-small dataset. Counts represents the average number of nodes that cross different clusters during the generation procedure.
8

---

Under review as a conference paper at ICLR 2023
generated graph and then count the cross-cluster steps during the generation procedure. As can see, the average number of nodes that cross different clusters of our method is much smaller than OA-ARM. This demonstrates that method tends first to generate one cluster and then adds another cluster while OA-ARM just randomly generates the graph. Therefore, the generation or- dering of GRAPHARM can better capture graph topology regularity than OA-ARM. Figure B (in Appendix [A.I) visualize the graph generative process of GRAPHARM and OA-ARM. As we can see, GRAPHIRRM first generates one community and then moves to another; while OA-ARM ran- domly generates the graph and fails to capture the underlying graph distribution.
5 ADDITIONAL RELATED WORK
Graph Generation. One-shot graph generative models generate all edges between nodes once. Models based on VAES (Simonovsky & Komodakis 2018: Liu et al.] 2018 Ma et al.) 2018) and GANs (Cao & Kipf 2022] Maziarka et 2020) generate all edges independently from latent em- beddings. This independence assumption can hurt the quality of the generated graphs. Normalizing flow models (Zang & Wang 2020 Madhawa et al., 2019) are restricted invertible model archi- tectures for building a normalized probability. The other class is autoregressive graph generative models, which generate a graph by sequentially adding nodes and edges. Autoregressive generation can be achieved using recurrent networks (Li et al., 2018:; You et al.] 2018b) Popova et al., 2019), VAEs (Liu et al., 2018 Jin et al., 2018 2020), normalizing flows (Shi et al. 2020 Luo et al. 2021 and RL (You et al. 201 8ap. By breaking the problem into smaller parts, these methods are more apt at capturing complex structural patterns and can easily incorporate constraints during generation. However, key drawback of them is that their training is sensitive node ordering. Most exist- ing works pre-define a fixed node ordering by ad-hoc such as random breadth- first search (BFS) ordering (You et al. 2018b Shi et al. 2020 Luo al. 202T). which cannot preserve permutation invariance and also be suboptimal for generation.
Diffusion and Score-Based Generation. Diffusion models have emerged as a new family of pow- erful deep generative models. Denoising diffusion probabilistic modeling (DDPM) Dickstnn et al. 2015 Ho et al., 2020) perturbs the data distribution into a Gaussian base distribution through an forward Markov noising process, and then learns to recover data distribution via the reverse tran- sition of the Markov chain. Closely related to DDPM is score-based generation (Song & Ermon 2019), which perturbs data with gradually increasing noise, and then learns to reverse the perturba- tion via score matching. [Song et al. 22021) generalize diffusion models to continuous-tin -time diffusion using forward and backward SDEs. Diffusion and score- based models has been successfully devel- oped for problems including image synthesis (Dhariwal & Nichol 2021). text-to-image synthesis (Ramesh et al., 2022 Saharia al. 2022), and molecular conformation modeling (Xu et al. 2021 Hoogeboom et al. 2022b). Few works have studied diffusion-basee graph generation. To the best of our knowledge, Niu et al. (2020): Jo et al.] (2022) are the only two works in this line. Different from these two works, our model is the first autoregressive diffusion model for graph generation, which defines diffusion directly in the discrete graph space.
LIMITATIONS AND DISCUSSION
We have proposed a new autoregressive diffusion model for graph generation. The proposed model GRAPHARR defines a node-absorbing diffusion process that directly operates in the discrete graph spaces. We designed a diffusion ordering network that learns an optimal ordering for this diffu- sion process, coupled with a reverse denoising network that performs autoregressive graph recon- struction. We derived simple variational lower bound of the likelihood, and showed that the two networks can be jointly trained with reinforcement learning. Our experiments have validated the generation performance and efficiency of GRAPHARM.
We discuss several limitations and possible future extensions of GRAPHARM: (1) Generating at- tributed graphs. Our work has been focused on generating graph structures only. However, it is possible to extend GRAPIAARM for attributed graph generation by changing the Bernoull-mmixtree distribution to multinomial-mixtue distribution. (2) Handling more complex constraints. We have shown that the autoregressive procedure of GRAPHARM can handle constraints better than one- shot generative models. However, practical graph generation applications can involve complex constraints on gloee properties such as graph spectrum. How to handle such global-level constraints remains challenging for our model and existing graph generative models.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Caveman dataset.
master/ Btaper/creeee_egeeeee .py 2018.
Bijaya Adhikari, Bryan Lewis, Anil Vullikanti, José Mauricio Jiménez, and B Aditya Prakash. Fast and near-optimal monitoring for healtheare acquired infection outbreaks. PLoS computational biology, 1509)e1007225) 2019.
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks, Reviews of modern physics, 74( (1,1 2002.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete spate-spaces. Advances in Neural Information Processing Systems, 34:1 1981-119933, 2021.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs ICML 2018 workshop Theoretical Foundations and Applications of Deep Generative Models, (arXiv:1805.1197) 2022. doi: 10.48550/arXiv.1800 11973.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, and Liping Liu. Order matters: Probabilis- tic modeling of node sequence for graph generation. In International Conference Machine Learning. pp. 1630-1639. PMLR, 2021.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780-8794, 2021.
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Laura Konzalez-Malerve Jaehong Park, Lihua Zou, Yanhui Hu, Zahra Moradpour, Joseph Pearl- berg, Jacqueline Sawyer, Hallam Stevens. Ed Harlow. and Joshua LaBaer. High-throo thghtthroughput ectopic expression screen for tamoxifen resistance identifies an atypical kinase that blocks au- tophagy. Proceedings of the National Academy of Sciences, (08(5)2058-2065) 2011.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pp. 2434 2444. PMLR, 2019.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows
and multinomial diffusion: Learning categorical distributions. Advances in Neural Information
Processing Systems, 34:12454-1246
2021.
Emiel Hoogeboom, Alexey A. Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and
Tim Salimans. Autoregressive diffusion models. In International Conference on Learning Rep- resentations, 2022a.
Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling, Equivariant dif- fusion for molecule generation in 3d. In International Conference Machine Learning, pp- 8867-8887. PMLR, 2022b.
Hankyu Jang, Samuel Justice, Philip M Polgreen, Alberto M Segre, Daniel K Sewell, and Sriram V Pemmaraju. Evaluating architectural changes alter pathogen dynamics in dialysis unit. In 2019 JEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 961-968. IEEE, 2019.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autocncoder for molecular graph generation. In Proceedings of the International Conference on Machine Learn- ing, pp. 2323 2332, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. International conference on machine learning, pp. 4839-48444 PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score- generative modeling of graphs via the system of stochastic differential equations. arXiv preprint arXiv:2202.02514, 2022.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 3xXiv:1803.0332444 2018.
Renjie Liao, Yujia Li, Yang Song. Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
Meng Liu, Keqiang Yan, Bora Oztekin, and Shuiwang Ji. Graphebm: Molecular graph generation with energy-based models. In Energy Based Models Workshop-ICI. 2021, 2021.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph varia- tional autoencoders for molecule design. Advances in neural information processing systems, 31, 2018.
James Lucas, George Tucker, Roger Grosse, and Mohammad Norouzi. Understanding posterior collapse in generative latent variable models. 2019a.
James Lucas, George Tucker, Roger Grosse, and Mohammad Norouzi. Don't blame the elbo! linear vae perspective on posterior collapse. Advances in Neural Information Processing Systems, 32, 2019b.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. International Conference on Machine Learning, pp. 7192-7203. PMLR, 2021.
Tengfei Ma. Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. Advances in Neural Information Processing Systems, 31, 2018.
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invert- ible flow model for generating molecular graphs. arXiv preprint arXiv: /600, 2019.
Eukasz Maziarka, Agnieszka Pocha, Jan Kaczmarczyk, Krzysztof Rataj, Tomasz Danel, and Michal Warchot. Mol-cyclegan: generative model for molecular optimization. Journal Cheminfor- matics, 12(1):1-18, 2020.
Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. In International Con- ference on Artificial Intelligence and Statistics, pp. 4474-4484. PMLR, 2020.
Mariya Popova, Mykhailo Shvets, Junier Oliva, and Olexandr Isayev. Molecularrnn: Generating realistic molecular graphs with optimized properties. arXiv:1905.13333 [cs, q-bio, stat), 2019.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents, 2022.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kam- yar Seyed Ghasemipour, Burcu Karagol Ayan, S. Sara Mahdavi, Rapha Gontijo Lopes, Tim Sali- mans, Jonathan Ho. David J. Fleet, and Mohammad Norouzi. Photorealistic text-to-image diffu- sion models with deep language understanding. 2022.
Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 32(suppl 1):D431-D433 2004.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (T00::0770064777 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rai -add Collective classification in network data. Al magazine, 29(3):93-95 2008

---

Under review as a conference paper at ICLR 2023
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. International Confer- ence Learning Representations, 2020. URL https::/openrevittt net S SleaMKHYPr
htrpeenreveee.nnttoouul...... formmidd-
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. International conference on artificial neural networks, pp. 412-422. Springer, 2018.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learn- ing. pp. 2256-2265 PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. Stte:s/se/ppeeeeeeeeeeeeeeeerrra
Ronald J Williams. Simple statistical gradiet algorithms for connectionist reinforcement learning. Machine learning, 8(3):229 256 1992.
Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geo- metric diffusion model for molecular conformation generation. In International Conference on Learning Representations, 2021.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for coal-directed molecular graph generation. Advances in neural information processing systems, 31, 80.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generat- ing realistic graphs with deep autoregressive models. In International conference machine learning, pp. 3708-5717 PMLR, 2018b.
Hao Yu, Xu Sun, Wei Deng Solvang, and Xu Zhao. Reverse logistics network design for effective management of medical waste in epidemic outbreaks: Insights from the coronavirus disease 2019 (covid-19) 19) outbreak in wuhan (china). International journal of environmental research and public health, 17(5):1770, 2020.
Chengxi Zang and Fei Wang. Moflow: an invertible flow model for generating molecular graphs In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 617-626, 2020.
12

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 VISUALIZATION OF GENERATION ORDERING
Figure 3 shows the graph generative process of GRAPHARM and OA-ARM. As we can see, GRAPHARM first generates one community and then moves to another; while OA-ARM randomly generates the graph and fails to capture the underlying graph distribution.
OA-ARM GraphARM
Step
Step 7
Step 9
Step 11
Step 12
Step
Step 7
Step 9
11
Step 12
Figure 3: The graph generative process of GRAPHARM and OA-ARM for community generation. As we can see, GRAPHARM first generates one community and then adds another one, which show that GRAPIIARM captures graph structural topology for generation. In contrast, OA-ARM generates the graph with random order.
A.2 CONNECTION BETWEEN AUTOREGRESSIVE DIFFUSION AND ABSORBING DIFFUSION
While ARM appears different from classic diffusion, it amounts to absorbing diffusion with contin- uous time limit. Starting from state Zo. can define a continuous-tine absorbing process, where each element x (6) independently decays into an absorbing state with continuous -immmuuuuu--meeeeeee probabilities (l). This stochastic process is equivalent using a finite set of D random transition times { ) for recording the time where x; was absorbed. was shown by Hoogeboom et al. (2022a) that modeling the reverse generation of this process does not need to be conditioned the precise values of the transition times T, Hence, when training the reverse generative model, we only need to model Ir, based Ir,+1 while ignoring т& This allows for writing the variational lower bound (VLB) of likelihood as an expectation over an uniform ordering in an autoregressive form:
logp(xr)) 2 Eg-
logp (Z) (Z)())))
A.3 DERIVATION OF EQ. 3
Following CCen al. 2021 let us define (G1.)) as the set of all node orderings that give the
same graph sequence G1:., I.c., II (G1.n) {aim : G.(a)a)) = G,, =t= 1....,,.7. n where G. ( the masked graph time step under the node ordering di.- Following (Chen
2021
the conditional p( ( is uniform distribution, i.e., p(
[[ Vo
II (G1..). Then, we have the following two equations CCen et 2021
po (G T1mn) |II [ po (Gin);
(G 11. Go) = (GT 4s (m
To derive the VLB, we first prove that for any function of Goens i.e., (GGon) its expectation over the diffused graph sequence is equal to the expectation over the node diffusion orderings. That is:
Egg (Go) (Go.n) Bag ((Go...
((Go.))
(10)
13

---

Under review as a conference paper at ICLR 2023
Proof.
(g. Go) (Gon)
Σ
f(Goon) (Ginn Go)
Gin
Σ
[gGon)go |G))
(G
G
1
E
[I
Gin
Σ
E
(o (o)
Gin OLe ETT()
Σ
((Gmm)golOLm(Go)
Lo (o)
(11)
The third last row is because iterating over the double loops of all the graph sequences and the corresponding node orderings is equal iterating over all possible node orderings.
Then, our VLB can be written as:
log (Go) log (f pollGan
Lo 1 (o)
dG dG1m Im
Lo 1.m Gp)
(Gen(l)) (log Po (G.n)) ) + log po G1m) log g0 (o(Gim//u))
Eq_ " EEg (log Pa (G (:n) - log Pa (Go (m) - log go
Egg 'Ey (egllai (log
Imm) + log pe ( log go 1G Go))
Fg. " Eyslorn (log [7 (G 1mm) + log Gol GGol Gim) log (G (g. (G))
-Fysloin (log (G po G p( G..,p( + to G1.n)
- log (T 140 (1
+ logp(a Gn) + log,p(Gn)
- log qo +
(C
= -al lo (0 (Go)
Fys In (Go)
(n) logp log q (o Go))
Ea (n Go))
po (Go logp G..) log (o Go))
-Eg (Go)
log pe (G(())) KL(gg(01m (olioi/n/Goolooiiiiioo Gn))..
(12)
We use Ge(ari)) to denote the masked graph at time step under the node ordering dim- In the fifth last row, we have logp(G,, = because G, a deterministic graph wherein all the nodes are masked. For brevity, directly use pe Gr+)) to represent (G(G:((o.n)GG441annnn in Eq. since din already appears in the expectation over qo (omm
A.4 TRAINING ALGORITHM OF GRAPHARM
We reinforcement learning (RL) procedure by sampling multiple diffusion trajectories, thereby enabling training both the diffusion ordering network (o(o(Go) and the denoising network (e(G((r(41) using gradient descent.
Specifically, at each training iteration, we explore the diffusion ordering network by creating M diffusion trajectories for each training graph G(a) Each trajectory is sequence of graphs
14

---

Under review as a conference paper at ICLR 2023
(G(.m)) hisssn where the node decay ordering is sampled from (a(a//Go) The denoising network po Po(Gr is then trained to minimize the negative VLB using stochastic gradient descent (SGD):
0g 0
7/1 M
Σ Σ
log po (G. ((
(13)
where Birain is the a minibatch sampled from the training data.
To evaluate the current diffusion ordering network, we create M trajectories for each validation graph and compute the negative VLB of the denoising network to obtain the corresponding rewards R. EieB,, E, logpo (l ( Then. the diffusion ordering network can be updated with common RI. optimization methods, e.g., the REINFORCE algorithm (Williams) 1992):
1/2 M
RTT log (o(o)
(14)
The detailed training procedure is summarized Algorithm
Algorithm Training procedure of GRAPHIAR
Require: Diffusion ordering network (o Go), Denoising network pe po(Ge G++1)
1: for training iterations do
2: Sample a minibatch B from the training set
3: for each i for each m E [1, .M do 01, o, (o(G)
Brain do
4:
5:
Obtain corresponding diffusion trajectories (Gft Jisesn end for 0, t 0 - 91 DiE En logpo ( (m)m) (G(Hm)
6:
7:
8:
9:
end for
10:
Sample minibatch from the validation set for each i E Val do
11:
12:
for each E [1, M1] do
13:
T1. og ~ (o)
Obtain corresponding diffusion trajectories (c(t:m)) Jistsn end for
14:
15:
Compute the reward RTTh = - E, logpe (G. G+11 do d; + Φj-1 M
Em R, (o))
18: end for
19:
end for
A.5 EXTENDED RELATED WORK
Graph Generation. One-shot graph generative models generate all edges between nodes at once. Models based on VAEs (Simonovsky & Komodakis 2018; Liu et al.) 2018 Ma et al. 2018) and GANs (Cao & Kipi 2022, Maziarka et al., 2020) generate all edges independently from latent em- beddings. This independence assumption hurt the quality of the generated graphs. Normalizing flow models (Zang & Wang 2020 Madhawa et al. (019) are restricted to invertible model archi- tectures for building a normalized probability. Another drawback shared by all one-shot generation models is that they cannot incorporate constraints during generation due to the one-shot process.
The other class is autoregressive graph generative models, which generate a graph by sequentially adding nodes and edges. Autoregressive generation can be achieved using recurrent networks (Li af. 2018: You et al., 2018b Popova et al., 2019) VAEs (Liu et al., 2018 Jín et al. 2018 2020). normalizing flows (Shi et al., 2020 Luo et al.) 2021). and RL. (You et al. 2018a). By breaking
the problem into smaller parts, these methods are more apt at capturing complex structural patterns
and can easily incorporate constraints during generation. However, a key drawback of them is that their training is sensitive to node ordering. Most existing works pre-define a fixed node ordering by ad-hoc such as random breadth-firs search (BFS) ordering (You al. [018b] Shi et al. 2020 Luo et al., (202I) which cannot preserve permutation invariance and also be suboptimal for generation. Chen et al. (2021) propose to learn the node generation ordering using variational inference (VI).
15

---

Under review as a conference paper at ICLR 2023
Diffusion and Score-Based Generation. Diffusion models have emerged new family of pow- erful deep generative models. Denoising diffusion probabilistic modeling (DDPM) Sohh-Dicksteinn et al. 2011 Ho al. 2020) perturbs the data distribution into a Gaussian base distribution through an forward Markov noising process, and then learns to recover data distribution via the reverse tran- sition of the Markov chain. Closely related to DDPM is score-based generation (Song & Ermon 2019), which perturbs data with gradually increasing noise, and then learns to reverse the perturba- tion via score matching. [Song et al. (2021) generalize diffusion models to continuous-time diffusion using forward and backward SDEs. Diffusion and score- bosee models has been successfully devel- oped for problems including image synthesis (Dhariwal & Nichol 2021), text-to-image synthesis (Ramesh et al., 2022 (Saharia et al. 2022). and molecular conformation modeling (Xu et al. 2021
Hoogeboom et al. 2022b).
A few works have proposed discrete diffusion models that operate directly in discrete state spaces through multinomial diffusion that uses categorical noise (Hoogeboom et al., 2021), discrete ab- sorbing diffusion (Austin et al., 2021 autoregressive diffusion (Hoogeboom al. 2022a). Our GRAPIIARM model extends autoregressive diffusion in two ways: (1) It defines autoregressive ab- sorbing diffusion processes permutation invariance property in graph generation. Few works have studied diffusion- based graph generation. To the best of our knowledge, [Nuu et al. (2020); Jo al. (2022) are the only two works in this line. Niu et al. (2020) perturb the adjacency matrices with gradually increasing noise levels, and Jo et al. 2022) model diffusion on both the adjacency matrices and node features using continuous- time SDE-based diffusion. Different from these two works, our model is the first autoregressive diffusion model for graph generation, which defines diffusion directly in the discrete graph space.
graphs; (2) It learns optimal absorbing node ordering via the
A.6 IMPLEMENTATION DETAILS
Model optimization: We use ADAM with 81 = 0.9 and B = 0.999 as the optimizer. The learn- ing rate is set for 10 and 5 x 10 4 for the denoising network and diffusion ordering network respectively on all the datasets. We perform model selection based on the average MMD of the three metrics on the validation set.
For fair comparison, our denoising network uses the same graph attention network architecture as the baseline GRAN which has 7 layers and hidden dimensions 128; the diffusion ordering network uses the same graph attention network architecture as the baseline OA which is a vallina GAT (Veličković al. 2018) that has 3 layers with 6 attention heads and residual connections. The hidden dimension is set to 32. As OM is compatible with any existing autoregres- sive methods, we use the strongest autoregressive baseline GRAN as its backbone.
Network architecture:
Hyper-parameters: We set the number of trajectories M as 4 for all the datasets. Both GRAPHARM and GRAN use 20 as the number of Bernoulli mixtures. For GRAN, we use block size 1 and stride 1 to achieve the best generation performance. For GDSS, we choose the best signal-to-noise ratio (SNR) from {0.05, 0.1, 0.15, 0.2) and scale coefficient from {0.1, 0.2, 0.3, 0.4, 0.5, 0.6. 0.7. 0.8, 0.9. 1.0] based on the average MMD of degree, clustering co- efficient and orbit as in Jo et al. 2022). For EDP-GNN, we use 6 noise levels {o,) = [1.6, 0.8, 0.6, 0.4, 0.2, 0.1] suggested In the original work (Niu et al. 2020). For OM, we use as the sample size for variational inference as suggested in the original work (Chen et al. 2021)
A.7 EXPERIMENT SETUP FOR CONSTRAINED GRAPH GENERATION
We use the Caveman dataset for the constrained generation experiment. We set the constraint as that the maximum node degree is no larger than 6. To generate graphs under this constraint with GRAPIIARM, we add degree checking into the generation process. Specifically, when generating new node and its connecting edges, we first check whether the constraint will be violated on previous nodes new edges are added to them. If so. the corresponding edges will be dropped; otherwise we proceed to check the constraint on the new generated node and randomly remove the extra edges that exceed the limit.
16

---

Under review as a conference paper at ICLR 2023
A.8 DATASET STATISTICS
We evaluate the performance of GRAPHARM on six diverse graph generation benchmarks, covering both synthetic and real-world graphs from different domains: (1) Community-small (You al.
2018b), containing 100 graphs randomly generated community graphs with 12 < [V S 20: (2)
Caveman YYuu 2018). containing 200 caveman graphs synthetically generated with
V 10:
with 9 < I 87, extracted from Cora network (Sen et al, 2008 using random walk; (4) Breast, including 100 chemical graphs with 12 - [V| S 18, sampled
(3) Cora, containing 200
from
Gonzalez-Malerve et al. (2011); (5) Enzymes, including 563 protein graphs with 10 s [V|
125 from BRENDA database (Schomburg et al. 2004); (6) Ego-small, containing 200 small sub-
graphs with 4 < V S 18 sampled from Citeseer Network Dataset (Sen et al. 2008
For each
dataset, we use 80% of the graphs as training set and the rest 20% as test sets. Following 2019). randomly select 25% from the training data the validation set.
Liao et al.
A.9 APPROXIMATION ERROR OF THE KL-DIVERGENCE TERM EQ. 3.
To evaluate the approximation error, we compute the KL-divergence between the diffu- sion ordering and the generation ordering at each time step and then sum together, i.e., Approximation error= Σ, KL (q(rr]Go. (<t)) (e(o))))))))) Specifically, at each time step we use GRAPHARM first generate graph Go and record the corresponding node generation ordering a. Since we do not explicitly model distribution of the node index during the generation procedure, we determine the index the generated node Go by its connectivity to the unmasked nodes in G.. Finally, we forward the generation network multiple times to obtain an empirical distribution for p(a, Table 5 provides the approximation error versus the training iterations. As we can see, with the training progresses, the approximation error indeed becomes smaller and approaches to zero.
Training iterations
100
200
500
2000
3000
Appriximation error
0.343
0.262
0.131
0.093
0.061
0.049
Table 5: Approximation error between the generation ordering and the diffusion ordering on the community-small dataset.
17


Reviews:
[{"review_id": "ZhRr5YwYN_L", "reviewer": "Reviewer_dB1j", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new graph generative model based on an autoregressive diffusion model. It shows good performances in a list of tasks. ", "summary_of_the_review": "The work devises a new graph generative model from the perspective of autoregressive diffusion models. However, it does not seem to add much to the original formulation. The model design is a contribution: it is efficient and shows good performance in several tasks. \n\n[After discussion:] the notation system of the submission is not well defined, and the derivation is problematic. ", "strength_and_weaknesses": "Strength: \n\n+ the new model has a formulation of autoregressive diffusion model. \n+ the model is very efficient\n+ the model shows good generation performances in a list of tasks. \n\nWeaknesses\n\n- Though the formulation is motivated differently, it has a large overlap with (Chen et al., 2021). The diffusion ordering network is roughly the same as the variational distribution of node orders in (Chen et al., 2021). The variational lower bound is also very similar to (Chen et al. 2021). The difference is actually because this work neglects the difference between graph sequences and node orders: a graph sequence is not equivalent to a node ordering, which is analyzed by (Chen et al., 2021). \n- The generative procedure is also similar to the standard autoregressive generative procedure: every time adding a new node and the edges connecting to this new node. I don't see the benefit of describing this procedure using the diffusion process. \n- There are several flaws in the analysis. The first one is the difference mentioned above, then the variational lower bound is not exactly correct. The second one is the complexity of generation: the complexity of this model should still be O(n^2) (the analysis below equation 2). Anyhow the model needs to make a decision for each node pair. The running time is saved by reducing the number of calls of neural networks (from O(n^2) to O(n)). \n\n[After a careful study of the submission and a discussion with authors], I find a critical derivation error in the submission. In particular, the submission bases its derivation on equation 8, which is from (Chen et al., 2021), but the term $p(G_{1:n}, \\sigma_{1:n})$ in this submission is different from that in the previous work, so the derivation is incorrect.   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YPq6US0i5y1", "reviewer": "Reviewer_EBGH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an autoregressive diffusion model (ARM) that leverages the absorbing discrete diffusion as the diffusion process on graphs. Since node ordering is involved in the diffusion process, the generative process needs to learn the reversed node ordering for the graph generation. The paper exploits the objective function in the KL divergence and uses a reinforcement learning procedure to bypass the inference complexity. Empirical results demonstrate superior performance compared with baseline methods.", "summary_of_the_review": "This paper proposes a diffusion process on discrete graphs that derives an autoregressive generative process with inferred node ordering. Empirical results are good, but my concern is its similarity with previous node ordering inference algorithms.", "strength_and_weaknesses": "1. This paper introduces a discrete autoregressive diffusion process on graphs that is exchangeable in node ordering. The number of steps required is proportional to the number of nodes, thus improving sampling efficiency over previous graph sampling methods.\n\n2. The paper resolves the node ordering inference problem involved in the inference process by exploiting the variational lower bound property. The method is similar to \"Order matters: probabilistic modeling of node sequence for graph generation.\" by (Chen et al. 2021). \n\n3. Empirical results demonstrate superior performance in generation quality and time complexity.\n\nWeaknesses:\n1. The paper does not clearly explain the \"optimal node generation ordering\" learned from the posterior. An example demonstrated in Figure 3 in the appendix shows that GraphRAM tends to generate one community and then generate the other community. But more insight is required to check why that ordering is preferred in GraphRAM.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "J6grcbPRTp", "reviewer": "Reviewer_uUZJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "- This paper proposed an autoregressive diffusion-based graph generation model. \n- Its performance outperforms SOTAs. \n- GRAPHARM also has low complexity.", "summary_of_the_review": "- This paper gives a new method for the graph generation.\n- The well-designed model obtains better performance.", "strength_and_weaknesses": "### Strength \n- This paper gives a new method for the graph generation.\n- The well-designed model obtains better performance.\n\n### Weaknesses\n- It does not well explain what autoregressive diffusion is.\n- Theoretical analysis is not sufficient", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GtC3NiMTh6G", "reviewer": "Reviewer_KoQP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors proposed an autoregressive diffusion model for the graph generation. A node-absorbing diffusion process was introduced. For the forward diffusion a diffusion ordering network was suggested, and for the reverse diffusion a denoising network was designed. These two networks can be trained jointly with a simplified log-likelihood loss. Experiments have shown the competitive results of the proposed method when compared to several existing methods. ", "summary_of_the_review": "The authors proposed an autoregressive diffusion model for the graph generation. The analysis is solid and the proposed method has been compared with several SOTA methods and showed its competitive performance. The paper can be further improved by adding more explanations and discussions (see the comments in Weaknesses above). ", "strength_and_weaknesses": "Strength:\n\nA new node-absorbing diffusion process has been introduced, and a data-dependent ordering can be learned via the optimization. The proposed method has been compared with several SOTA methods and shown its competitive results including the generation time.\n\n\n\n######################\n\nWeaknesses:\n\n. Section 2: The authors mentioned that the absorbing diffusion is the most promising generation method. Can you add some explanation on that?\n\n. Section 3.1: The diffusion ordering network produces the probability of the node at time t via equation (1). Can you explain why such an ordering would reflect the topology/regularities of the graph?\n\n. Section 3.3: The proposed training objective has ignored the KL-divergence term in equation (3). Can you evaluate such approximation error, ie. calculate the actual KL-divergence and check whether it indeed approaches zero?\n\nExperiments:\n\n. Table 1: The performance of the proposed GRAPHARM on Cora is not competitive. Can you explain that?\n\n. Effect of Diffusion Ordering: Can you illustrate the proposed ordering visually to give a sense that it does reflect the topology/regularities of the graph when compared to the random ordering? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject