DiGress: Discrete Denoising diffusion for graph generation
Authors: Clement Vignac
Igor Krawczuk
Antoine Siraudin
Bohan Wang
Volkan Cevher
Pascal Frossard
Venue: ICLR 2023 poster (2023)
Keywords: Graph generation
Denoising Diffusion Model
Molecule Generation
Permutation Equivariance
Discrete Diffusion

Abstract: This work introduces DiGress, a discrete denoising diffusion model for generating graphs with categorical node and edge attributes.
Our model utilizes a discrete diffusion process that progressively edits graphs with noise, through the process of adding or removing edges and changing the categories.
A graph transformer network is trained to revert this process, simplifying the problem of distribution learning over graphs into a sequence of node and edge classification tasks.
We further improve sample quality by introducing a Markovian noise model that preserves the marginal distribution of node and edge types during diffusion, and by incorporating auxiliary graph-theoretic features.
A procedure for conditioning the generation on graph-level features is also proposed.
DiGress achieves state-of-the-art performance on molecular and non-molecular datasets, with up to 3x validity improvement on a planar graph dataset. 
It is also the first model to scale to the large GuacaMol dataset containing 1.3M drug-like molecules without the use of molecule-specific representations.

Published as a conference paper at ICLR 2023
DIGRESS: DISCRETE DENOISING DIFFUSION FOR GRAPH GENERATION
Clément Vignac LTS4, EPFL Lausanne, Switzerland
Igor Krawezuk" LIONS, EPFL
Antoine Siraudin LTTS,, EPFL. Lausanne, Switzerland
Lausanne, Switzerland
Bohan Wang LTS4, EPFL Lausanne, Switzerland
Volkan Cevher
Pascal Frossard LTS4, EPFL Lausanne, Switzerland
LIONS, EPFL Lausanne, Switzerland
ABSTRACT
This work introduces DiGress, a discrete denoising diffusion model for generat- ing graphs with categorical node and edge attributes. Our model utilizes discrete diffusion process that progressively edits graphs with noise, through the process adding or removing edges and changing the categories. A graph transformer network is trained to revert this process, simplifying the problem of distribution learning over graphs into a sequence of node and edge classification tasks. We further improve sample quality by introducing Markovian noise model that pre- serves the marginal distribution of node and edge types during diffusion, and by incorporating auxiliary graph-theoretic features. A procedure for conditioning the generation on graph-level features is also proposed. DiGress achieves state-of-the- art performance on molecular and non-molecular datasets, with up 3x validity improvement on a planar graph dataset. It is also the first model to scale to the large GuacaMol dataset containing 1.3M trug-like molecules without the use of molecule-specif. representations.
INTRODUCTION
Denoising diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020) form powerful class of generative models. At high-level, these models are trained to denoise diffusion trajectories, and produce new samples by sampling noise and recursively denoising it. Diffusion models have been used successfully in variety of settings, outperforming all other methods image and video (Dhariwal Nichol, 2021; Ho et al., 2022). These successes raise hope for building powerful mod- els for graph generation, task with diverse applications such molecule design (Liu al., 2018), traffic modeling (Yu & Gu, 2019), and code completion (Brockschmidt et al., 2019). However, generating graphs remains challenging due to their unordered nature and sparsity properties.
Previous diffusion models for graphs proposed to embed the graphs Gaussian noise to the node features and graph adjacency matrix (Niu et al., 2020; Jo et al., 2022). This however destroys the graph's 's sparsity and creates complete noisy graphs for which structural information (such connectivity or cycle counts) can make it difficult for the denoising network to capture the structural properties of the data.
continuous space and add
defined. As result, continuous diffusion
In this work, we propose DiGress, discrete denoising diffusion model for generating graphs with categorical node and edge attributes. Our noise model is Markov process consisting of successive graphs edits (edge addition or deletion, node or edge category edit) that can occur independently on each node or edge. To invert this diffusion process, we train graph transformer network to predict the clean graph from noisy input. The resulting architecture is permutation equivariant and admits an evidence lower bound for likelihood estimation.
We then propose several algorithmic enhancements to DiGress, including utilizing a noise model that preserves the marginal distribution of node and edge types during diffusion, introducing novel
Equul contribution. Contact: fi rst name. last name@epf1.ce

---

Published as a conference paper at ICLR 2023
guidance procedure for conditioning graph generation on graph-level properties, and augmenting the input of our denoising network with auxiliary structural and spectral features. These features, derived from the noisy graph, aid in overcoming the limited representation power of graph neural networks (Xu et al., 2019). Their use is made possible by the discrete nature of our noise model, which, in contrast to Gaussian-based models, preserves sparsity in the noisy graphs. These improve- ments enhance the performance of DiGress on a wide range of graph generation tasks.
Our experiments demonstrate that DiGress achieve state-of-the-art performance, generating a high rate of realistic graphs while maintaining high degree of diversity and novelty. On the large MOSES and GuacaMol molecular datasets, which were previously too large for one-shot models, it notably matches the performance of autoregressive models trained using expert knowledge.
2 DIFFUSION MODELS
In this section, we introduce the key concepts of denoising diffusion models that are agnostic to the data modality. These models consist of two main components: noise model and a denoising neural network. The noise model progressively corrupts a data point x to create a sequence of increasingly noisy data points (z! (a'...., )). It has Markovian structure, where g(2 ..... [2)
q(> II= g(="|===1) The denoising network Øg is trained to invert this process by predicting 2 from 2 To generate new samples, noise is sampled from a prior distribution and then inverted by iterative application of the denoising network.
While early models would directly predict a'-1 from 2' (Sohl-Dickstein et al., 2015), these models were difficult to train due to the dependence of s'-1 on the sampled diffusion trajectories. Ho et al. (2020) considerably improved performance by establishing a connection with score-based models (Song& & Ermon, 2019). They showed that when J q<<<"1/2(, xx)dp is tractable, x be used as the target of the denoising network, which removes an important source of label noise.
For diffusion model to be efficient, three properties are required:
1. The distribution q(= ((= should have a closed-form formula, to allow for parallel training different time steps.
2. The posterior pa (==="1|2* = g(="-1|=*, xx)dpo(e (2r) should have a closed-form expression, so that x can be used as the target of the neural network.
3. The limit distribution dxe = limy- q(="'aa (z) should not depend on so that we can use it as a prior distribution for inference.
These properties are all satisfied when the noise is Gaussian. When the task requires to model categorical data, Gaussian noise can still be used by embedding the data in a continuous space with one-hot encoding of the categories (Niu et al., 2020; Jo et al., 2022). We develop in Appendix A graph generation model based on this principle, and use it for ablation studies. However, Gaussian noise is a poor noise model for graphs as it destroys sparsity as well as graph theoretic notions such as connectivity. Discrete diffusion therefore seems more appropriate to graph generation tasks.
Recent works have considered the discrete diffusion problem for text, image and audio data (Hooge- boom et al., 2021: Johnson et al., 2021; Yang et al., 2022). We follow here the setting proposed by Austin et al. (2021). It considers data point x that belongs to one of d classes and E Rd its one-hot encoding. The noise is now represented by transition matrices (Q) (Q'...,,) Q7) such that (Q')s, represents the probability of jumping from state to state j: -1)= Q
As the process is Markovian, the transition matrix from æ to z' reads Q' Q² As long as Q' is precomputed or has closed-form expression, the noisy states z² can be built from æ using q(2²lx)) æQ' without having to apply noise recursively (Property 1). The posterior distribution q(21-1/20 x) can also be computed in closed-fon form using Bayes rule (Property 2):
q(2
112,,2)) (12" x) x x² (Q') O x x Q'11
(I)
where O denotes a pointwise product and Q' is the transpose of Q (derivation in Appendix D). Finally, the limit distribution of the noise model depends on the transition model. The simplest and most common one is uniform transition (Hoogeboom et al., 2021; Austin et al., 2021; Yang al., 2022) parametrized by Q' = a' I + (1 - d')1,1'//d with at transitioning from to O. When lim a² = 0. (2))2a) converges uniform distribution independently of x (Property 3).
2

---

Published as a conference paper at ICLR 2023
G
G
Q'
G
G
Cross-entropy
G(
Po(Gr-11G)
ABC
Go(G)
Figure 1: Overview of DiGress. The noise model is defined by Markov transition matrices Q' whose cumulative product is Q'. The denoising network dy learns to predict the clean graph from G¹. During inference, the predicted distribution is combined with g(G'-1JG, G*) in order to compute pe(C |G") and sample discrete Gt-l from this product of categorical distributions.
The above framework satisfies all three properties in setting that is inherently discrete. However, while it has been applied successfully to several data modalities, graphs have unique challenges that need be considered: they have varying sizes, permutation equivariance properties, and this date no known tractable universal approximator. In the next sections, we therefore propose a new discrete diffusion model that addresses the specific challenges of graph generation.
DISCRETE DENOISING DIFFUSION FOR GRAPH GENERATION (DIGRESS)
In this section, present the Discrete Graph Denoising Diffusion model (DiGress) for graph gen- eration. Our model handles graphs with categorical node and edge attributes, represented by the spaces X' and E, respectively, with cardinalities and b. We æ; to denote the attribute of node i and æ; E IR to denote its one-hot encoding. These encodings are organised in a matrix X E R"*e xaxxxbb groups the one-hot encoding eij
where n is the number of nodes. Similarly, a tensor of each edge, treating the absence of edge as a particular edge type. We use A' to denote the matrix transpose of A, while A is the value of A time
3.1 DIFFUSION PROCESS AND INVERSE DENOISING ITERATIONS
Similarly to diffusion models for images, which apply noise independently each pixel, we diffuse separately on each node and edge feature. As a result, the state-space that we consider is not that of graphs (which would be too large to build transition matrix), but only the node types X' and edge types E. For any node (resp. edge), the transition probabilities are defined by the matrices [Qx]e lo = q(x² = j|æ²=1 = i) and [Q'rs = q(e' = jlee = i). Adding noise to form G = (X' E simply means sampling each node and edge type from a categorical distribution defined by:
(("'/G*~1) (X'-1Q 1 E'-1Q')) and G(G'(G) = (XQ'x EQ'x.
(2)
for @ Q and Q's- Q.... When considering undirected graphs, we apply noise only to the upper-triangula part of E and then symmetrize the matrix.
The second component of the DiGress model the denoising neural network de parametrized by 0. takes noisy graph G (x E as input and aims to predict the clean graph G, as illustrated in Figure 1. To train σø, we optimize the cross- cross-entropy loss | between the predicted probabilities fc (fx B) for each node and edge and the true graph
= Σ cross-entropyyr..n (r,, A 15I5A
Σ 154,5n
cross-entropy (eij,
(3)
where À + controls the relative importance of nodes and edges. It is noteworthy that, unlike architectures like VAEs which solve complex distribution learning problems that sometimes requires graph matching, diffusion model simply solves classification tasks each node and edge.
Once the network is trained, can be used to sample new graphs. To do so, we need to estimate the reverse diffusion iterations po (G') using the network prediction zcc We model this distribu-
3

---

Published as a conference paper at ICLR 2023
tion product nodes and edges:
Go II
(G*
II
po po
(4)
15i5n
I5tJin
To compute each term, we marginalize over the network predictions:
9o(x5-11' =
pa(a; Iti G*) dp)(xx = Σ
2s = =1 po(x)
x, G*) p
ZEX
where we choose
[q(2 11
z, x!)
if [-/]2, = =0
pa 1-1 Ij =x, GO)
(5)
otherwise.
Similarly, we have po ( (c))))())))))))))))))))))) = Emee
(c). These distributions are used to sample a discrete Gt 1 that will be the input of the denoising network at the next time step. These equations can also be used compute an evidence lower bound on the likelihood, which allows for easy comparison between models. The computations are provided in Appendix C.
3.2 DENOISING NETWORK PARAMETRIZATION
The denoising network takes a noisy graph G = (X,E) as input and outputs tensors X' and E' which represent the predicted distribution over clean graphs. To efficiently store information, layers also manipulate graph-level features y. We chose to extend the graph transformer network proposed by Dwivedi & Bresson (2021), attention mechanisms are natural model for edge prediction. Our model is described in details in Appendix B.1. At a high-level, first updates node features using self-attention, incorporating edge features and global features using FiLM layers (Perez et al., 2018). The edge features are then updated using the unnormalized attention scores, and the graph-level features using pooled node and edge features. Our transformer layers also feature residual connections and layer normalization. To incorporate time information, we normalize the timestep [o, 1] and treat it as a global feature inside y. The overall memory and time complexity of our network is (nz²) per layer, due to the attention scores and the predictions for each edge.
3.3 EQUIVARIANCE PROPERTIES
Graphs are invariant to reorderings of their nodes, meaning that n! matrices can represent the same graph. To efficiently learn from these data, is crucial devise methods that do require aug- menting the data with random permutations. This implies that gradient updates should not change the train data permuted. To achieve this property, two components are needed: a permutation equivariant architecture and permutation invariant loss. DiGress satisfies both properties.
Lemma 3.1. (Equivariance) DiGress is permutation equivariant.
Lemma 3.2. (Invariant loss) Any loss function (such the cross-entropy loss of Eq. (3)) that can be decomposed as E, Ix (p. x2) + E., (E eig) for two functions lx and ig computed respectively on each node and each edge is permutation invariant.
Lemma 3.2 shows that our model does not require matching the predicted and target graphs, which would be difficult and costly. This is because the diffusion process keeps track of the identity of the nodes at each step, it can also be interpreted as a physical process where points are distinguishable.
Equivariance is however not a sufficient for likelihood computation: in general, the likelihood of graph is the sum of the likelihood of all its permutations, which is intractable. To avoid this compu- tation, we can make sure that the generated distribution is exchangeable, i.e., that all permutations of generated graphs are equally likely (Köhler et al., 2020).
Lemma 3.3. (Exchangeability)
DiGress yields exchangeable distributions, i.e., it generates graphs with node features X and ad- jacency matrix A that satisfy P(X, A) P( X, TH Ar) for any permutation
4

---

Published as a conference paper at ICLR 2023
N4
05
T/4
T/2
T/4
t= 0
Figure 2: Reverse diffusion chains generated from model trained on uniform transition noise (top) and marginal noise (bottom). When noisy graphs have the right marginals of node and edge types, they closer to realistic graphs, which makes training easier.
IMPROVING DIGRESS WITH MARGINAL PROBABILITIES AND STRUCTURAL. FEATURES
4.1 CHOICE OF THE NOISE MODEL
The choice of the Markov transition matrices (Q:)eTT defining the graph edit probabilities is arbi- trary, and it is priori not clear what noise model will lead to the best performance. A common model a uniform transition over the classes Q' = a² + (1 - (1,1))) /d, which leads to limit distributions qx and gE that are uniform over categories. Graphs are however usually sparse, mean- ing that the marginal distribution edge types is far from uniform. Starting from uniform noise, we observe in Figure 2 that it takes many diffusion steps for the model produce sparse graph. To improve upon uniform transitions, we propose the following hypothesis: using a prior distribution which is close the true data distribution makes training easier.
This prior distribution cannot be chosen arbitrarily, as it needs to be permutation invariant to satisfy exchangeability (Lemma 3.3). A natural model for this distribution is therefore a product II: x II v of a single distribution u for all nodes and a single distribution o for all edges. We propose the following result (proved in Appendix D) to guide the choice of u and v::
Theorem 4.1. (Optimal prior distribution)
Consider the class C = [Il Il., v, (u,v) P(X) X P(E)} of distributions over graphs that factorize as the product of single distribution over X for the nodes and single distribution over& & for the edges. Let be an arbitrary distribution over graphs (seen tensor of order n-+n?)
and mx, mg its marginal distributions of node and edge types. Then T the orthogonal projection of P on C:
I1, m, X IIis me is
T E arg min P|
II u X
II I5tJ5n
211
(0,0)EC
13i5n
This result means that to get a prior distribution gx x gg close to the true data distribution, we should define transition matrices such that Vi, limy- Qx 1, mxx (and similarly for edges). To achieve this property, we propose to use
Q'x a'a 3 1.m'x and Q' a' + 3 1,m's
(6)
With this model, the probability of jumping from a state to a state j is proportional to the marginal probability of category: j the training set. Since (1m')2 3'1m' for a' = II a and 3 = [1 - a²). We follow the popular cosine schedule a' cos (0.5m(t/T + s) (1+ + s)) with small s. Experimentally, these marginal transitions improves over uniform transitions (Appendix F).
1m', we still have Q' a I +
4.2 STRUCTURAL FEATURES AUGMENTATION
Generative models for graphs inherit the limitations of graph neural networks, and in particular their limited representation power (Xu et al., 2019; Morris et al., 2019). One example of this limitation is the difficulty for standard message passing networks (MPNNs) to detect simple substructures
5

---

Published as a conference paper at ICLR 2023
Algorithm 1: Training DiGress
Input: A graph G = (X, E)
Sample ~ (U, T)
Sample G XQ' EQ
> sample a (discrete) noisy graph
2 [(G' fx p t @o
Structural and spectral features
Forward pass
optimizer. step(Ice((* X) X A E))
Cross Cross-entropy
Algorithm 2: Sampling from DiGress
Sample n from the training data distribution
Sample GO ~qx (n) x (n)
Random graph
for 1= 7 to / do
2 2 ((G 6x 60 + (oo(G" ,)
A. Structural and spectral features
Forward pass Posterior
Go)) + -Ex g(a) o(x:-1pp . x, (x)
iel...., .j........n P Categorical distr.
pale GG) t E. a(e7
1-
Bij = ,, (e)
G Po IG") I1ij -
end
return G
such as cycles (Chen et al., 2020), which raises concerns about their ability to accurately capture the properties of the data distribution. While more powerful networks have been proposed such as (Maron et al., 2019; Vignac et al., 2020; Morris et al., 2022), they are significantly more costly and slower to train. Another strategy to overcome this limitation is to augment standard MPNNs with features that they cannot compute on their own. For example. Bouritsas et al. (2022) proposed adding counts of substructures of interest, and Beaini et al. (2021) proposed adding spectral features, which are known to capture important properties of graphs (Chung & Graham, 1997).
discrete space and its noisy graphs are not complete, allowing for the com- putation of various graph descriptors at each diffusion step. These descriptors can be input to the network to aid in the denoising process, resulting in Algorithms and for training DiGress and sampling from it. The inclusion of these additional features experimentally improves performance, but they are not required for building a good model. The choice of which features to include and the computational complexity of their calculation should be considered, especially for larger graphs. The details of the features used in our experiments can be found in the Appendix B.1.
DiGress operates
CONDITIONAL GENERATION
While good unconditional generation a prerequisite, the ability to condition generation on graph- level properties is crucial for many applications. For example, in drug design, molecules that are easy to synthesize and have high activity on specific targets are of particular interest. One way to perform conditional generation is to train the denoising network using the target properties (Hoogeboom et al., 2022), but it requires to retrain the model when the conditioning properties changes.
To overcome this limitation, we propose new discrete guidance scheme inspired by the classifier guidance algorithm (Sohl-Dickstein et al., 2015). Our method uses a regressor 9n, which is trained to predict target properties yG of clean graph G from a noisy version of G: g,, = ÿ. This regressor guides the unconditional diffusion model Φe by modulating the predicted distribution at each sampling step and pushing it towards graphs with the desired properties. The equations for the conditional denoising process are given by the following lemma:
Lemma 5.1. (Conditional reverse noising process) (Dhariwal & Nichol, 2021)
Denote the noising process conditioned on yG, q the unconditional noising process, and assume that (G y = (GG')) Then we have q(G "G*,, ,G*yG)) x q(G'=1("") G
While we would like to estimate q( (G") q(yG G² by (o P. (7 Gt-1), Pry cannot be evaluated for all possible values of G1-1, To overcome this issue, view G continuous

---

Published as a conference paper at ICLR 2023
Algorithm 3: Sampling from DiGress with discrete regressor guidance.
Input: Unconditional model do. property regressor 9, target y, guidance scale X, graph size Sample G qx (n) x (n)
Random graph
for = Too do
,()
& Structural and apectral features
,x +
Forward pass Regressor model b Guidance distribution
(G')
Po (" exp(
(ap(-1a) -1 (Vo 1 yll2.G-11)
Sample Gt-1 ~ po (G" py (g
Reverse process
end
return G
tensor of order n + n² (so that Va can be defined) and use a first-order approximation. It gives:
log (yya
(os:(((y"))) ()- = log (oyGl") + loggglly) G G*)
c + Σ
v. log qyyG
E
(Ve, logg(uell") eg
SSiS
ISiJEn
for function that does not depend G We make the additional assumption that O(ya) G*) (ggg("), I, where g is estimated by 9n. so that V log (y(()) x -Vall -al-- 12 The resulting procedure is presented in Algorithm 3.
In addition to being conditioned on graph-level properties, our model can be used to extend an exist- ing subgraph task called molecular scaffold extension in the drug discovery literature (Maziarz et al., 2022). In Appendix E, we explain how to do and demonstrate it on simple example.
6 RELATED WORK
Several works have recently proposed discrete diffusion models for text, images, audio, and tributed point clouds (Austin et al., 2021; Yang et al., 2022; Luo et al., 2022). Our work, DiGress, the first discrete diffusion model for graphs. Concurrently, Haefeli al. (2022) designed a model limited to unattributed graphs, and similarly observed that discrete diffusion is beneficial for graph generation. Previous diffusion models for graphs were based on Gaussian noise: Niu et al. (2020) generated adjacency matrices by thresholding continuous value to indicate edges, and Jo et al. (2022) extended this model to handle node and edge attributes.
Trippe al. (2022), Hoogeboom et al. (2022) and Wu et al. (2022) define diffusion models for molecule generation in 3D. These models actually solve point cloud generation task, as they gen- erate atomic positions rather than graph structures and thus require conformer data for training. On the contrary, Xu et al. (2022) and Jing et al. (2022) define diffusion model for conformation generation they input graph structure and output atomic coordinates.
Apart from diffusion models, there has recently been a lot of interest in non-autoregressive graph generation using VAEs, GANs normalizing flows (Zhu et. 2022). (Madhawa al., 2019; Lippe & Gavves, 2021; Luo et al., 2021) are examples of discrete models using categorical normalizing flows. However, these methods have not yet matched the performance of autoregressive models (Liu et al., 2018; Liao et al., 2019; Mercado et al., 2021) and motifs-based models (Jin et al., 2020; Maziarz et al., 2022), which can incorporate much more domain knowledge.
EXPERIMENTS
In our experiments, we compare the performance of DiGress against several state-of-the-art one- shot graph generation methods on both molecular and non-molecular benchmarks. We compare its performance against Set2Graph VAE (Vignac & Frossard, 2021), SPECTRE (Martinkus et al., 2022), GraphNVP (Madhawa et al., 2019), GDSS (Jo et al., 2022), GraphRNN (You et al., 2018), GRAN (Liao et al., 2019), JT-VAE (Jin et al., 2018), NAGVAE (Kwon et al., 2020) and GraphINVENT
7

---

Published as a conference paper at ICLR 2023
Table Molecule generation on QM9. Training time is the time needed reach 99% validity. On small graphs, DiGress achieves similar results to the continuous model but is faster to train.
Method
NLL
Valid
Unique
Training time (h)
Dataset
99.3
100
Set2GrapVVAE
59.9
93.8
SPECTRE
87.3
35.7
GraphNVP
83.1
99.2
GDSS
95.7
98.5
ConGress (ours)
98.9
96.81.2
7.2
DiGress (ours)
69.6
99.0
96.21.1
1.0
(Mercado et al., 2021). We also build Congress, model that has the same denoising network as DiGress but Gaussian diffusion (Appendix A). Our results are presented without validity correction'.
7.1 GENERAL GRAPH GENERATION
Table I: Unconditional generation on SBM and planar graphs. VUN: valid, unique & novel graphs.
Model
Deg +
Clus +
Orb.,
V.U.N.1 1
Stochastic block model
GraphRNN
6.9
1.7
3.1
%
GRAN
14.1
1.7
2.1
25%
GG-GAN
4.4
2.1
2.3
25%
SPECTRE
1.9
1.6
1.6
53%
ConGress
34.1
3.1
DiGress
1.6
1.5
1.7
74%
Planar graphy
GraphRNN
24.5
9.0
2508
0%
GRAN
3.5
1.4
1.8
0%
SPECTRE
2.5
2.5
2.4
25%
ConGress
23.8
8.8
2590
0%
Figure 3: Samples from DiGress trained on SBM and planar graphs.
DiGress
1.4
1.2
1.7
75%
We first evaluate DiGress on the benchmark proposed in Martinkus et al. (2022), which consists of two datasets of 200 graphs each: one drawn from the stochastic block model (with up to 200 nodes per graph), and another dataset of planar graphs (64 nodes per graph). We evaluate the ability to correctly model various properties of these graphs, such as whether the generated graphs are statistically distinguishable from the SBM model or they are planar and connected. We refer to Appendix F for a description of the metrics. In Table 1, we observe that DiGress is able to capture the data distribution very effectively, with significant improvements over baselines on planar graphs. In contrast, our continuous model, ConGress, performs poorly on these relatively large graphs
7.2 SMALL MOLECULE GENERATION
We then evaluate our model on the standard QM9 dataset (Wu et al., 2018) that contains molecules with up to 9 heavy atoms. We 13k for evaluating likelihood on a test set. We report the negative log-likelihood 10k molecules. Novelty results
split of 100k molecules for training, 20k for validation and our model,
validity (measured by RDKit sanitization) and uniqueness discussed in Appendix F. 95% confidence intervals are reported based on five runs. Results are presented in Figure 2. Since ConGress and DiGress both obtain close perfect metrics on this dataset, we also perform an ablation study on a more challenging version of QM9 where hydrogens are explicitly modeled in Appendix It shows that the discrete framework is beneficial and that marginal transitions and auxiliary features further boost performance.
Coode available gi thub. com/ cvi wwwp://wwangggggee.......
8

---

Published as a conference paper at ICLR 2023
Table 3: Molecule generation on MOSES. DiGress is the first one-shot graph model that scales to this dataset. While all graph-based methods except ours have hard-coded rules to ensure high validity, DiGress outperforms GraphInvent on most other metrics.
Model
Class
Val
Unique
Novel
Filterst
FCD
SNNT
Scaft
VAE
SMILES
97.7
99.8
69.5
99.7
0.57
0.58
5.9
JT-VAE
Fragment
100
100
99.9
97.8
1.00
0.53
10
GraphINVENT
Autoreg.
96.4
99.8
95.0
1.22
0.54
12.7
ConGress (ours)
One-shot
83.4
99.9
96.4
94.8
1.48
0.50
16,4
DiGress (ours)
One-shot
85.7
100
95.0
97.1
1.19
0.52
14.8
Table 4: Molecule generation GuacaMol. We report scores, that higher is better for all metrics. While SMILES seem to be the most efficient molecular representation, DiGress is the first general graph generation method that achieves correct performance, as visible on the FCD score.
Model
Class
Valid
Uniquet
Novelf
KL divt
FCDt
LSTM
Smiles
95.9
100
91.2
99.1
91.3
NAGVAE
One-shot
92.9
95.5
100
38.4
0.9
MCTS
One-shot
100
100
95.4
82.2
1.5
ConGress (ours)
One-shot
0.1
100
100
36.1
0.0
DiGress (ours)
One-shot
85.2
100
99.9
92.9
68.0
7.3 CONDITIONAL. GENERATION
Figure Mean absolute error on conditional gen- eration with discrete regression guidance QM9.
To measure the ability of DiGress to condi- tion the generation graph-level properties, we propose a conditional generation setting on QM9. We sample 100 molecules from the test set and retrieve their dipole moment and the highest occupied molecular orbit (HOMO). The pairs (μ,, HOMO) constitute the conditioning vector that we use to generate 10 molecules. To evaluate the ability of model condition correctly, we need estimate the properties of the gener- ated samples. To do so, we use RdKit (Landrum et al., 2006) to produce conformers of the generated graphs, and then Psi4 (Smith et al., 2020) estimate the values absolute eтror between the targets and the estimated values for the generated molecules (Fig. 4).
Target
μ
HOMO
μ & HOMO
Uncondit.
1.71#.04
0.93=.01
1.34=.01
Guidance
0.81
0.56=.01
0.87=.03
and HOMO. We report the mean
7.4 MOLECULE GENERATION AT SCALE
We finally evaluate our model two much more challenging datasets made of more than million molecules: MOSES (Polykovskiy et al., 2020), which contains small drug-like molecules, and Gua- caMol (Brown et al., 2019), which contains larger molecules. DiGress is one-shot generative model that is not based on molecular fragments and that scales to datasets of this size. The metrics used well as additional experiments presented in App. F. For MOSES, the reported scores for FCD, SNN, and Scaffold similarity are computed on the dataset made of separate scaffolds, which measures the ability of the networks to predict new ring structures. Re- sults are presented in Tables 3 and 4: they show that DiGress does not yet match the performance of SMILES and fragment-bar based methods, but performs on par with GraphInvent, an autoregressive model fine-tuned using chemical softwares and reinforcement learning. DiGress thus bridges the important gap between one-shot methods and autoregressive models that previously prevailed.
knowledge the first
CONCLUSION
We proposed DiGress, denoising diffusion model for graph generation that operates discrete space. DiGress outperforms existing one-shot generation methods and scales to larger molecular datasets, reaching the performance of autogressive models trained using expert knowledge.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Nikos Karalias, Éloi Alonso and Karolis Martinkus for their help and useful suggestions. Clément Vignac thanks the Swiss Data Science Center for supporting him through the PhD fellow- ship program (grant P18-11). 1.) Igor Krawczuk and Volkan Cevher acknowledge funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innova- tion programme (grant agreement n n2725594 time-data).
This work is licensed under a Creative Commons "Attribution 3.0 Un- ported" license.
cc
BY
REFERENCES
Jacob Austin, Daniel Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34, 2021. 7
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pictro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 748- 758. PMLR, 2021. 6
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022. 6
Mare Brockschmidt, Miltiadis Allamanis, Alexander L. Gaunt, and Oleksandr Polozov. Generative code modeling with graphs In International Conference Learning Representations (ICLR), 2019.
Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: benchmarking models for de novo molecular design. Journal of chemical information and modeling, 59(3): 1096-1108, 2019. 9
Davide Buffelli, Pietro Liò, and Fabio Vandin. Sizeshiftreg: regularization method for improving lize-generalization in graph neural networks. arXiv preprint arXiv:2207.07885 2022. 21
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10395, 2020. 6,
15
Fan RK Chung and Fan Chung Graham. Spectral graph theory, volume 92. American Mathematical Soc., 1997. 6
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780-8794, 2021. 1,
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs.
AAAI Workshop Deep Learning on Graphs: Methods and Applications, 2021. 4
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffu- sion models for graphs benefit from discrete state spaces. arXiv preprint arX1v:2210.01549.220 2022.
Jonathan Ho. Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 6840-6851. Curran Asso- wwweeediinnnn.u.niineeeeeee ps. cc/ ccc/papper/222//1111 ciates, Inc., 2020. URL. Paaaaaaa parerr.pf... 1,2, 14
4c5bcfec858 (at.://8444.0000701100111001
Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David Fleet. Video diffusion models. arXiv preprint 2rX 2022.
10

---

Published as a conference paper at ICLR 2023
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, 2021.
Emiel Hoogeboom, Vicctor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant dif- fusion for molecule generation in 3d. In International Conference on Machine Learning, pp. 8867-8887. PMLR, 2022. 6, 7, 20
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-2332. PMLR, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning, pp. 9839-4844 PMLR, 2020.
Bowen Jing, Gabriele Corso, Jeffrey Chang, Regina Barzilay, and Tommi Jaakkola. Torsional diffu- sion for molecular conformer generation. arXiv preprint arXiv:2206.01729. 2022. 7
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. arXiv preprint arXiv:2202.02514, 2022. 1, 2. 7, 14, 19, 20
Daniel D Johnson, Jacob Austin, Rianne den Berg, and Daniel Tarlow. Beyond in in-place comuup- tion: Insertion and deletion in denoising probabilistic models. arXiv preprint arXiv:2107.07675. 2021. 2
Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models, Ad- vances in neural information processing systems, 34:21696-21707, 2021. 13, 16
Jonas Köhler, Leon Klein, and Frank Noć. Equivariant flows: Exact likelihood generative learning for symmetric densities. In Proceedings of the 37th International Conference on Machine Learn- ing. ICML, volume 119 of Proceedings of Machine Learning Research, pp. 5361-5370 PMLR, 2020. 4
Youngchun Kwon, Dongseon Lee, Youn-Suk Choi, Kyoham Shin, and Seokho Kang. Compressed graph representation for scalable molecular graph generation. Journal of Cheminformatics, 12 (1):1-8, 2020. 7
Greg Landrum et al. Rdkit: Open-source cheminformatics. 2006.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In NeurIPS, 2019. 7
Phillip Lippe and Efstratios Gavves. Categorical normalizing flows via continuous transfor- mations. In International Conference on Learning Representations, 2021. URL https: //openreview net httpe//fooummmi--GLeeeeeeee
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph varia- tional autocncoders for molecule design. Advances in neural information processing systems, 31, 2018. 1,7
Andreas Lugmayr, Martin Danelljan, Andres Romero, Fisher Yu, Radu Timofte, and Luc Van Gool. Repaint: Inpainting using denoising diffusion probabilistic models. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 11461-11471, 2022. 19
Shitong Luo, Yufeng Su, Xingang Peng, Sheng Wang, Jian Peng, and Jianzhu Ma. Antigen-specifir antibody design and optimization with diffusion-based generative models. bioRxiv, 2022.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 7192-7203, 2021.
11

---

Published as a conference paper at ICLR 2023
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An in- vertible flow model for generating molecular graphs. arXiv preprint 1rXiv:1905.1 2019.
7
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019. 6
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spec- tral conditioning helps overcome the expressivity limits of one-shot graph generators. arXiv preprint arXiv:2204.0666 2022. 7, 8, 19
Krzysztof Maziarz, Henry Richard Jackson-Flux, Pashmina Cameron, Finton Sirockin, Nadine Schneider, Nikolaus Stiefl, Marwin Segler, and Marc Brockschmidt. Learning extend molec- ular scaffolds with structural motifs. In International Conference on Learning Representations (ICLR), 2022. 7, 19
Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology, 2(2):025023, 2021. 7.8
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-46029 2019.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation -euiivarinnivviiinnn graph networks. arXiv preprint 3rXiv:2203.131133 2022.
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. 2,
Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville. Film: Visual reasoning with general conditioning layer. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018. 4
Daniil Polykovskiy. Alexander Zhebrak, Benjamin Sanchez-Lengeling, Sergey Golovanov. Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, et Molecular sets (moses): a benchmarking platform for molecular generation models. Frontiers in pharmacology, 11 11:565644, 2020. 9
Daniel GA Smith, Lori A Burns, Andrew C Simmonett, Robert M Parrish, Matthew C Schieber, Raimondas Galvelis, Peter Kraus, Holger Kruse, Roberto Di Remigio, Asem Alenaizan, et al. Psi4 1.4: Open-source software for high-throughput quantum chemistry. The Journal of chemical physics, 152(18):184108, 2020.
Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML, 2015. 1, 2, 6, 16
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019. 2
Brian Trippe, Jason Yim, Doug Tischer, Tamara Broderick, David Baker, Regina Barzilay, and Tommi Jaakkola. Diffusion probabilistic modeling of protein backbones in 3d for the motif- scaffolding problem. arXiv preprint arXiv:2206. 04100.111111.1 19, 2022.
Clement Vignac and Pascal Frossard. Top-n: Equivariant set and graph generation without ex-
changeability. arXiv preprint arXiv:2 10. 10.02096, 2021. 7, 20
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passingg Advances in Neural Information Processing Systems, 13:14143-14115, 2020. 6
12

---

Published as a conference paper at ICLR 2023
Fang Wu, Qiang Zhang, Xurui Jin, Yinghui Jiang, and Stan Z. A score-based geomettic model for molecular dynamics simulations. CoRR, abw/22044.0672, 2022. doi: 104485500/axx122224466667. URL httph::p///// /tw.///oiio/ org/10........oooooo.ooo..11 0eeg//...55500.... 405.0//5555/......///// 2204. 08672.
Zhengin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chem. Sci., 9:513-530, 2018. doi: 10. 10.1039/C7SC002644A URL http::///... /dxx do org/ 10. 10199/177002266....
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https:
///ppnzeview..../////// net/ wwweet/fooummiite http://teeooooo...r..aaaaaaa...
2,5
Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geometric diffusion model for molecular conformation generation. In International Confer- ence on Learning Representations, 2022. URL PZovXEMzvQC. 7, 17
net. cottfform?idt
Dongchao Yang, Jianwei Yu, Helin Wang, Wen Wang, Chao Weng, Yuexian Zou, and Dong Yu. Diffsound: Discrete diffusion model for text-to-sound generation. arXiv e-prints, pp. arXiv-2207, 2022. 7.7
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrmn: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pp. 5708-5717. PMLR, 2018.
James Jian Qiao Yu and Jiatao Gu. Real-time traffic speed estimation with graph convolutional generative autoencoder. IEEE Transactions Intelligent Transportation Systems, 20(10):3940- 2019. 2019. 1
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. arXiv preprint 2rXiv:2203.06714, 2022.
A CONTINUOUS GRAPH DENOISING DIFFUSION MODEL (CONGRESS)
In this section present diffusion model for graphs that uses Gaussian noise rather than discrete diffusion process. Its denoising network is the same as the one of our discrete model. Our goal is show that the better performance obtained with DiGress is only due the neural network design, but also to the discrete process itself.
A.1 DIFFUSION PROCESS
Consider graph G = (X, E). Similarly to the discrete diffusion model, this diffusion process adds noise independently on each node and each edge, but this time the noise considered Gaussian:
q( xX''X*=)) = -1- (1) and q( ((E(E'-)) -N "ifa"t"EE'" E'-1, (a*lt-1)3)
1
This process equivalently be written:
qx x = N(x ('X,"'XXXXX'")
(E = N(E
(8)
where ! //'-a-1 and (4)))-1--
The variance is chosen as (a¹)2 1 in order to obtain variance-preservingg process (Kingma et al., 2021). Similarly DiGress, when consider undirected graphs, only apply the noise on the upper-triangular part of E without the main diagonal, and then symmetrize the matrix. The true denoising process can be computed in closed-form:
( x²) 1 (X. X'), (0-tt13) I) (and similarly for E),
13

---

Published as a conference paper at ICLR 2023
Algorithm 4: Training ConGress
Input: A graph G = (X, E)
Sample ~ UI.,...,
Sample cx ~ NN0 In)
Sample cg (N00, ((nn-12))) and symmetrize if needed
z + (X, E) or (n)
Add noise
Minimize (B) 00(2", 6)1
Algorithm 5: Sampling from ConGress
Sample from the training data distribution
Sample ex ~ NO0, I,)
Sample Eg NO(0 1)/2) and symmetrize if needed
2T (c)
for 1 = 7' to / do
Sample cx ~ (N( In)
Sample and symmetrize eg ~ (0, 1n(n-1)/2)
T (b + -
Reverse iterations
end
return argmax argmax ED))
with
attt11 10 X a²- (0"1--1) (0t)2
XX (x)
X and gt 0t 0t-1
(10)
of
dt
As commonly done for Gaussian diffusion models, we train the denoising network to predict the noise components êx &g instead of X and È themselves (Ho et al., 2020). Both relate follows:
a' x X" o'éx and à E of éω
(11)
To optimize the network, we minimize the mean squared error between the predicted noise and the true noise, which results Algorithm 4 for training ConGress. Sampling is done similarly to standard Gaussian diffusion models, except for the last step: since continuous valued features obtained, they must be mapped back to categorical values in order to obtain discrete graph. For this purpose, we then take the argmax of x E across node and edge types (Algorithm 5).
Overall, ConGress is very close to the GDSS model proposed in Jo et al. (2022), as it is also Gaussian- diffusion model for graphs. An important difference is that we define a diffusion process that is independent for each node and edge, while GDSS that does not factorize. We observe empirically that simple noise model does not hurt performance, since ConGress outperforms GDSS QM9 (Table 2).
complex noise model
E
Nocda/Edige-rrieee MLP
B NEURAL NETWORK PARAMETRIZATION
Graph Transformer Layar
B.1 GRAPH TRANSFORMER NETWORK
The parametrization of our denoising network is presented in Figure 5. It takes as input a noisy graph (X: E) and predicts a distribution over the clean graphs. We compute structural and spectral features in order to improve the network expressivity. Internally, each layer manipulates nodes features X, edge features E but also graph level features y. Each graph transformer layer is made of graph attention module (presented in Figure 6), as well as fully-connected layers and layer normalization.
Graph Transformer Layer
NodwlEdge-
MLP
x
Structural Spectral features
14
Figure 5: Architec- ture of the denoising

---

Published as a conference paper at ICLR 2023
E'
X'
y'
1
Lin
Lin
Lin
Σ
FILM
FiLM
y
Flatten heads
y
Flatten haads
PNA
PNA
Lin
1
Σ
X
E
y
UrjVg
Softmax
Lin
FiLM
X
E
Outer product
scaling
Lin
Lin
X 7heads
X
X
Figure 6: The self-attention module of our graph transformer network. It takes as input node features X, edge features and global features y. and updates their representation. These features are then passed to normalization layers and fully connected network, similarly the standard transformer architecture. FiLM(M,,. M2) = Mi Wi + (M, W2) C M2 + M2 for learnable weight matrices W1 and W2, and PNA(X) cat (X), min(X), mean (X), sttdt)())) W.
B.2 AUXILIARY STRUCTURAL AND SPECTRAL FEATURES
The structural features that we use can be divided in two types: graph- theoretic (cycles and spectral features) and domain specific (molecular fea-
tures).
Cycles Since message-passing neural networks are unable to detect cycles (Chen et al., 2020), we add cycle counts our model. Because computing traversals would be impractical the more as these features are recomputed at every diffusion step), we use formulas for cycles up to size 6. We build node features (how many k k-cycles does this node belong to?) for up to 5-cycles, and graph-level features (how many it k-ccysles does this graph contain?) for up to k 6. We use the following formulas, where d denotes the vector containing node degrees and ||-||m Frobenius
GPUs (all
15

---

Published as a conference paper at ICLR 2023
norm:
X; diag( (
X diagg(A)) d(d 1) - 1,,
X; = (diag(A) AA)) 2diag( (A0) 3 d A(diag( A(diag(A")) + +diag( +diag(A)))/2
(A))
y/ = X 1n/3
1/ = X 1,/4
y5 X 1,/5
yo Tr -'T 3 + 9 @ A 6 (diag(AA)) diag(AA)) + + 4 Tr A + 4 A²) + A Tr o A²) + (T²
Spectral features We also add the option to incorporate spectral features to the model. While this find that it is not limiting factor for the graphs that
requires (n²²) cigendecomposition, use in our experiments (that have up to 200 nodes). We first compute some graph-level features that relate to the eigenvalues of the graph Laplacian: the number of connected components (given by the multiplicity eigenvalue 0), as well as the first nonzero eigenvalues. We then add node-level features relative to the graph eigenvectors: an estimation of the biggest connected component (using the eigenvectors associated to eigenvalue 0), as well as the two first eigenvectors associated to non zero eigenvalues.
Molecular features On molecular datasets, we also incorporate the current valency of each atom and the current molecular weight of the full molecule.
C LIKELIHOOD COMPUTATION
C
G
G
Figure 7: The graphical model of DiGress and ConGress
The graphical model associated to problem is presented in figure 7: the graph size is sampled from the training distribution and kept constant during diffusion. One can notice the similarity between this graphical model and hierarchical variational autoencoders (VAEs): diffusion models can in fact be interpreted as a particular instance of VAE where the encoder (i.e., the diffusion process) is fixed. The likelihood of a data point & under the model writes:
p()) / p(G") n) !o ....,.''(G")
log pe (G) log
po(G|G") d(G')...,, (12)
nEN
+ log f p(G nG)
T po G') (G d(G' ((..,...,GC GJ) (13)
= logp(nc)
As for VAEs, an evidence lower bound (ELBO) for this integral can be computed (Sohl-Dickstein et al., 2015; Kingma et al., 2021). It writes:
T La(x) Eyear ay [
log (G) 2 logp(ng) DDr. DKI.l((" (G) |l (x())) x qE(nG)]
Prior loss
Reconstruction
Diffusion loss
(14)
with
L.(G) Eyto (Pattllc G) (G
(15)
All these terms can be estimated: logp(ng) is computed using the frequencies of the number of nodes for each graph in the dataset. The prior loss and the diffusion loss are KL divergences be- tween categorical distribution, and the reconstruction loss is simply computed from the predicted probabilities for the clean graph given the last noisy graph G
16

---

Published as a conference paper at ICLR 2023
D PROOFS
True posterior distribution
We recall the derivation of the true posterior distribution q(= 122 ,x,) x z' (Q") o Q
By Bayes rule, we have:
u(= 1=="=11z", 1=,,,)) a)) ==="1=²=1 a(= (xx)
Since the noise is Markovian, (e212"=1,2)) q(="12=-1). A second application of Bayes rule gives (==1|===1) x g(= ((='-12²)g(8
By writing the definition of Q', we then observe that a(= = z² (Q... We also have ((>"~1<x) a Q by definition.
Finally, we observe that (=²)) does not depend on z²-1, It can therefore be seen as part of the normalization constant. By combining the terms, we have q(= x) x (Qty о x Q' as desired.
Lemma 3.1: Equivariance
Proof. Consider graph G' with nodes, and π S,, permutation. acts trivially (T. y), acts on as x.X = n' X and on E as:
(T. (T.E) E (0-,(())xx-000))
Let G (X E noised graph, and (m.X*, n. E') its permutation. Then:
Our spectral and structural features are all permutation equivariant (for the node features) or invariant (for the graph level features): f== t) x.f(G', .t).
The self-attention architecture is permutation equivariant. The FiLM blocks are permuta- tion equivariant, and the PNA pooling function is permutation invariant.
Layer-normalizztion is permutation equivariant.
DiGress is therefore the combination of permutation equivariant blocks. As result, is permutation equivariant: @ (IT.G.. f)) x. To "f'", t)).
Lemma 3.2: Invariant loss
Proof. It is important that the loss function be the same for each node and each edge in order to guarantee that
(I.GGT.GG. Σ (1 +
Σ (g( (T. Ex -x-) 1(0),=-(())) 1(1))
Exx(X, 23) + Σ LE (Eii,,e))s)
15
G((
Lemma 3.3:
Exchangeability
Proof. The proof relies on the result of Xu (2022): a distribution p(G is invariant to the action of group G and the transition probabilities p(G G¹) are equivariant, them p(G") is invariant to the action G. We apply this result to the special case permutations:
The limit noise distribution is the product of i.i.d. distributions each node and edge. It is therefore permutation invariant.
The denoising neural networks is permutation equivariant.
The function (G) > Po (G'-I(')) = Ee (G' G) defining the transition probabilities is equivariant to joint permutations of po (G) and G".
The conditions of (Xu et al., 2022) are therefore satisfied, and the model satisfies P(X, E)
P(r.X, n. ..E) for any permutation
17

---

Published as a conference paper at ICLR 2023
Theorem 4.1: Optimal prior distribution We first prove the following result:
Lemma D.1. Let p be a discrete distribution over two variables. It is represented by a matrix
P E Raxh, Let m and m² the marginal distribution of p. m = Ei= Pij and m = =
Then
(m m²) E arg min ||P u e'11
ue n20.7 u,=1 020.E0y my=1
Proof. We define L(u, v) = | - uu'12 = -is(py-uuuj'' -
We derive this formula to obtain
optimality conditions:
L =0 + Ou.
Σ (pis - u, =
Σ PigU = u/ Σng
Σ Sissus / /E'g
Similarly, we have Byy
= = By Σ, Pijui / ES u..
Since p, u and v are probability distributions, we have Σij Ps.s = 1, Ee = and Σ, 4/ = 1.
Combining these equations, we have:
Ej Piguy E, 13
Σ d Eij Pijuz
u,
Ej 13
Σ 1
Pio Pig)os
1
Σ 1 Σ bzuj
So that:
E, Pios3y b,
Eg Piod 2, azn E,
E, Piyai
Σ Pios =m
Uioo
Piyus
E, aru;
and similarly Ujo big. Conversely, m and m belong to the set of feasible solutions.
We have proved that the product distribution that is the closest to the true distribution of two variables is the product of marginals (for distance). We need to extend this result to product I u x II e of a distribution for nodes and a distribution for edges.
We now view p as a tensor in dimension a a"'"". We denote xx the marginalisation of this tensor across the node dimensions (px E I²"), ), and Dd the marginalisation across the edge dimensions (p g***"). ). By flattening the first dimensions and the n² next, p can be viewed a distribution over two variables (a distribution for the nodes and distribution for the edges). By application of our Lemma, x and o are the optimal approximation of p. However, y is a joint distribution for all nodes and not the product I of single distribution for all nodes.
We then notice that:
112
Σ |/u112 - 2 Σ
(u, + Σ
11 112
(||ul12 2 (w. n
Σ
pp
+ 1
Σ
n
=I|u
Σ
2x 112 + x(xx)
18

---

Published as a conference paper at ICLR 2023
Figure 8: An example of molecular scaffold extension. We sometimes observe long-range consis- tency issues in the generated samples, which is in line with the observations of (Lugmayr et al., 2022) for image data. resampling strategy similar theirs could be used to solve this issue.
for function f that does not depend on u. As E, P. n is exactly the empirical distribution of node types, the optimal u the empirical distribution of node types as desired. Overall, we have made two orthogonal projections: projection from the distributions over graphs to the distributions over nodes, and a projection from the distribution over nodes to the product distributions x ... x u. Since the product distributions forms a linear space contained in the distributions over nodes, these two projections are equivalent to a single orthogonal projection from the distributions over graphs to the product distributions over nodes. A similar reasoning holds for edges.
E SUBSTRUCTURY CONDITIONEL GENERATION
Given subgraph S = (X s; Es) with nodes, we can condition the generation on S by masking the generated node and edge feature tensor at each reverse iteration step (Lugmayr et al., 2022). As model is permutation equivariant, it does not matter what entries masked: we therefore choose the first n, ones. After sampling Gt-l, we update X and E using
X Mx O X, + Mx) O X and E - o E, -1
E
where Mx nx and Mg E Ru masks indicating the n, first nodes. In Figure 8, showcase an example for molecule generation: we follow the setting proposed by (Maziarz et al., 2022) and generate molecules starting from a particular motif called 1,4 --Dihydroquinolinee..
F EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
F.1 ABSTRACT GRAPH GENERATION
The reported metrics compare the discrepancy between the distribution of some metrics test and the distribution of the same metrics generated graph. The metrics measured are degree distributions, clustering coefficients, and orbit counts (it measures the distribution of all substructures of size 4). We do not report raw numbers but ratios computed follows:
Metrics
r = MMD(generatte test)² MMD((raininy, test)
The denominator MMD WMMD(trainnn (training, test)² is taken from the results table of SPECTRE (Martinkus et al., 2022). Note that what the authors report as MMD is actually MMD squared.
Community-20 In Table 5, also provide results for the smaller Community-20 dataset which contains 200 graphs drawn from a stochastic block model with two communities. We observe that DiGress performs very well on this small dataset.
F.2 QM9
Metrics Because it is the metric reported in most papers, the validity metric we report is computed by building molecule with RdKit and trying to obtain valid SMILES string out of it. As explained by Jo et al. (2022), this method is not perfect because QM9 contains some charged molecules which would be considered as invalid by this method. They thus compute validity using a more relaxed definition that allows for some partial charges, which gives them a small advantage.
httpps: hittps://pubchen nobi mmm. wwt.goo///oooooooo coop//ompond//// 1_4-11_4-___-- L__-Dihhyrogggp nol nn
19

---

Published as a conference paper at ICLR 2023
Table Results on the small Community-22 dataset.
Degree
Clustering
Orbit
Ratio.
GraphRNN
4.0
1.7
4.0
3.2
GRAN
3.0
1.6
1.0
1.9
GG-GAN
4.0
3.1
8.0
5.5
SPECTRE
0.5
2.7
2.0
1.7
DiGress
1.0
0.9
1.0
1.0
Table 6: Ablation study on QM9 with explicit hydrogens. Marginal transitions improve over uniform transitions, and spectral and structural features further boost performance.
Model
Valid1
Uniquet
Atom stablef
Mol stablet
Dataset
97.8
100
98.5
87.0
ConGress
8..7
98.410.1
97.2+0.2
69.5
DiGress (uniform)
89.811.2
97.840.2
97.3+0.1
70.542.1
DiGress (marginal)
92.3+2.5
97.9=0.2
97.3+008
66.8=11.8
DiGress (marg. features)
95.4+1.1
97.6+004
98.1+0.3
79.8#5.6
Ablation study We perform an ablation study in order to highlight the role of marginal transitions and auxiliary features. In this setting, also measure atom stability and molecule stability as defined in (Hoogeboom et al., 2022). Results are presented in Figure 6.
Novelty We follow Vignac Frossard (2021) and don't 't report novelty for QM9 in the main table. The reason is that since QM9 is an exhaustive enumeration of the small molecules that satisfy given set of constrains, generating molecules outside this set is not necessarily a good sign that the network has correctly captured the data distribution. For the interested reader, DiGress achieves on average a novelty of 33.4% on QM9 with implicit hydrogens, while ConGress obtains 40.0%.
F.3 MOSES AND GUACAMOL
Datasets For both MOSES and GuacaMol, we convert the generated graphs to SMILES using the code of Jo al. (2022) that allows for some partial charges.
We note that GuacaMol contains complex molecules that are difficult to process, for example be- cause they contain formal charges or fused rings. As result, mapping the train smiles graph and then back to train SMILES does not work for around 20% of the molecules. Even if our model is able correctly model these graphs and generate graphs that are similar, these graphs can- not be mapped to SMILES strings to be evaluated by GuacaMol. More efficient tools for processing complex molecules as graphs are therefore needed truly achieve good performance on this dataset.
Metrics Since MOSES and Guacamol are benchmarking tools, they come with their set of metrics that we use to report the results. We briefly describe this metrics: Validity measures the proportion of molecules that pass basic valency checks. Uniqueness measures the proportion of molecules that have different SMILES strings (which implies that they are non-isomorphic). Novelty measures the proportion of generated molecules that not in the training set. The filter score measures the proportion of molecules that pass the same filters that were used to build the test set. The Frechet ChemNetDistance (FCD) measures the similarity between molecules in the training set and in the test set using the embeddings learned by neural network. SNN is the similarity to nearest neighbor, as measured by Tanimoto distance. Scaffold similarity compares the frequencies of Bemis-Murcke scaffolds. The KL. divergence compares the distribution of various physicochemical descriptors.
Likelihood Since other methods did not report likelihood for GuacaMol and MOSES, did not include our NLL results in the table neither. We obtain a test NLL of 129.7 on QM9 with explicit hydrogens, 205.2 on MOSES (on the separate scaffold test set) and 308.1 on GuacaMol.
20

---

Published as a conference paper at ICLR 2023
Table 7: Proportion of valid and unique molecules obtained when sampling larger molecules than the maximal size in the training set. Interestingly. DiGress performs very well GuacaMol and poorly on MOSES. We hypothesize that this due to GuacaMol being more diverse dataset, which forces the network to learn to generate good molecules of all sizes.
Dataset statistics
Valid and unique (%)
Rmmin
Naverage
max
7max +
Raax + 10
Tmmax +
20
MOSES
8
21.7
27
2.6
2.2
0.0
GuacaMol
2
27.8
88
87.3
85.6
80.5
Non curated samples generated by DiGress trained on planar graphs (top) and graphs drawn from the stochastic block model (bottom).
Figure 9:
Size extrapolation While the vast majority of molecules in QM9 have the same number of atoms, molecules MOSES and Guacamol have varying sizes. On these datasets, would like know if DiGress can generate larger molecules than it has been trained on. This problem is usually called size extrapolation in the graph neural network literature.
To measure the network ability to extrapolate, we set the number of atoms to generate to T'mx + k. where mmax is the maximal graph size in the dataset and [5, 10, 20). We generate 24 batches of 256 molecules (=6144 molecules) in each setting and measure the proportion of valid and unique molecules all these molecules are novel since they are larger than the training set.
The results are presented in Table 7. We observe an important discrepancy between the two datasets: DiGress is very capable of extrapolation on GuacaMol, completely fails on MOSES. This can be explained by the respective statistics of the datasets: MOSES features molecules that are relatively homogeneous size. On the contrary, GuacaMol features molecules that are much larger than the dataset average. The network is therefore trained more diverse examples, which conjecture is why it learns some size invariance properties. The major difference in extrapolation ability that we obtain clearly highlights the value of large and diverse datasets.
We finally note that our denoising network was not designed to be size invariant, as it for example features sum aggregation functions each layer. Specific techniques such SizeShiftReg (Buffelli et al., 2022) could also be used to improve the size-extrapolation ability DiGress needed for downstream applications.
G SAMPLES FROM OUR MODEL
21

---

Published as a conference paper at ICLR 2023
OH
OH
Figure 10: Non curated samples generated by DiGress, trained QM9 with implicit hydrogens
(top), and explicit hydrogens (bottom).
Figure 11: Non curated samples generated by Guacamol (top) and Moses (bottom). While there some failure (disconnected molecules invalid molecules), model is the first autoregressive method that scales to these datasets that are much more complex than the standard QM9,
22


Reviews:
[{"review_id": "xd3xF01c8y", "reviewer": "Reviewer_br8Y", "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": "The paper presents DiGress, a diffusion model for graph generation. Apart from using graph-based architectures, the key idea is to start with a noise model that preserves the marginal distribution of node and edge types rather than using uniform noise. Then the denoising network is augmented with structural features. Finally, conditional generation is enabled by guidance procedures. Empirical results shows that the performance of DiGress matches the performance of autoregressive models on some molecular datasets.", "summary_of_the_review": "The method section of the paper is written nicely, but there are some confusions surrounding the experimental sections. ", "strength_and_weaknesses": "Strength:\n- The paper is written clearly and the idea behind non-uniform diffusion noise addition makes sense, and is empirically confirmed.\n- The proposed architecture handles node-level, edge-level and graph level features and has some nice properties, such as equivariance, and exchangeability.\n- The diffusion model framework allows for easy use of classifier-based / classifier-free guidance for conditional generation.\n\nWeakness:\n- The method does not deal with growing graphs like in autoregressive models. \n- The sampling procedure is not entirely clear (in algorithm 3). While the distribution $p(G^{t-1} | G^t) p(y | G^{t-1})$ can be sample from Langevin dynamics, it is not sure if that is actually used -- more likely it is similar to the sampling procedure of diffusion models, which would not guarantee that $G^{t-1}$ is sampled from that distribution described above. \n- Some of the experimental results seem odd. In Table 1. the V.U.N. for ConGress is 0% meaning that it generates nothing that is valid, unique and novel graphs. In Table 4, the validity of Congress is 0% and FCD is also 0, which seems quite odd because FCD is better if it is lower (that is also a typo? also KL div is pointed upwards as well).\n- The performance between ConGress and DiGress differ by a lot, which seems odd as usually the discrete case converges to continuous case as number of timesteps goes to infinity.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CYujY3Y8cdG", "reviewer": "Reviewer_7EF5", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 a discrete diffusion model for graph generation by combining discrete diffusion [Austin 2021] and graph transformer [Dwivedi and Bresson 2021]. Its main novelties are:\n - The diffusion model is discrete: sampling of node and edge features is performed after adding noise.\n - The denoising network is a graph transformer. It is permutation equivariant and generalizes to graphs of different sizes (sec 3.3). \n - Since \"having no edge\" is encoded as a categorical edge feature, choosing a uniform noise model does not preserve the sparsity of the graph. Instead, the paper proposes a noise model that preserves the marginal distribution of node and edge types during.\n - Conditional generation is made possible through regressor guidance.", "summary_of_the_review": "The paper is well-written, the contribution is novel, and should be of interest to a broad graph generation and diffusion audience. The method proposed is well-motivated and the empirical evaluation is thorough. I recommend accept.", "strength_and_weaknesses": "=== Strength ===\n\nThis paper fills a known gap in the literature, between discrete diffusion [Austin 2021] and diffusion for graph data [Niu 2020]. As a result, the approach is well-motivated, and contributes greatly to the literature on deep graph generation. The model is analyzed thoroughly, especially on permutation equivariance and invariance. The ablation studies are thorough: the benefit of discrete (over continuous) diffusion, marginal (over Gaussian) noise, and conditional (over unconditional) generation are well-established.\n\n=== Minor weaknesses ===\n\nWhat is z in the algorithms?\n\nI understand the omission of graph transformer network, but the discussion about sampling after adding noise should not be omitted. After all, it is the main reason why the diffusion model is \"discrete.\"\n\nI would like to see an evaluation on training on small graphs and testing on large graphs, similar to those in \"Learning the Travelling Salesperson Problem Requires Rethinking Generalization\".", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BpuIpVbc2pL", "reviewer": "Reviewer_SeWu", "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 paper introduces DiGress, a discrete diffusion-based generative model for graphs. The noise model sequentially corrupts the graph structure by modifying the categories of edges and nodes. The denoising model is a Transformer that leverages additional features. Experiments on graph and (conditional) molecule generation demonstrate the efficacy of DiGress.", "summary_of_the_review": "Although I have concerns regarding clarity and performance gains over current art, this is an interesting contribution to one-shot molecular generation. Thus, I am inclined to accept the paper.\n", "strength_and_weaknesses": "Strengths\n- The paper also introduces a continuous version (ConGress) and uses it for ablation purposes, showing that the discrete version produces better results.\n- The proposed method yields good results for general graph generation, outperforming SPECTRE (ICML, 2022).\n\nWeaknesses\n- The proposed method does not advance the current art --- widely used molecule generation methods (e.g., JT-VAE) outperform the proposed approaches.\n- Experiments on conditional generation are somewhat weak, with no extensive comparison with other baselines.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "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: Accept: poster