Spanning Tree-based Graph Generation for Molecules
Authors: Sungsoo Ahn
Binghong Chen
Tianzhe Wang
Le Song
Venue: ICLR 2022 Spotlight (2022)
Keywords: molecule generation
tree generation
graph generation
deep generative model
de novo drug design

Abstract: In this paper, we explore the problem of generating molecules using deep neural networks, which has recently gained much interest in chemistry. To this end, we propose a spanning tree-based graph generation (STGG) framework based on formulating molecular graph generation as a construction of a spanning tree and the residual edges. Such a formulation exploits the sparsity of molecular graphs and allows using compact tree-constructive operations to define the molecular graph connectivity. Based on the intermediate graph structure of the construction process, our framework can constrain its generation to molecular graphs that satisfy the chemical valence rules. We also newly design a Transformer architecture with tree-based relative positional encodings for realizing the tree construction procedure. Experiments on QM9, ZINC250k, and MOSES benchmarks verify the effectiveness of the proposed framework in metrics such as validity, Frechet ChemNet distance, and fragment similarity. We also demonstrate the usefulness of STGG in maximizing penalized LogP value of molecules.

Published as a conference paper at ICLR 2022
SPANNING TREE-BASED GRAPH GENERATION FOR MOLECULES
Sungsoo Ahn', Binghong Chen', Tianzhe Wang", Le Song
POSTECH, Georgia Institute of Technology. "Biomap. "MBZUAI sungsoo ahn@postech ac. kr, {binghong, tianzhe @gatech edu, dasongle@gmail.
com com
ABSTRACT
In this paper, we explore the problem of generating molecules using deep neural networks, which has recently gained much interest in chemistry. To this end, we propose a spanning tree-based graph generation (STGG) framework based on formulating molecular graph generation as a construction of a spanning tree and the residual edges. Such formulation exploits the sparsity of molecular graphs and allows using compact crcsttnstree operations to define the molecular graph connectivity. Based on the intermediate graph structure of the construction process, our framework can constrain its generation to molecular graphs that satisfy the chemical valence rules. We also newly design a Transformer architecture with tree-based relative positional encodings for realizing the tree construction procedure. Experiments on QM9, ZINC250K, and MOSES benchmarks verify the effectiveness of the proposed framework in metrics such validity, Fréchet ChemNet distance, and fragment similarity. We also demonstrate the usefulness STGG in maximizing penalized LogP value of molecules.
INTRODUCTION
Researchers have extensively studied graph generative models, dating back to the early works of Erdös Rényi (Erdös et al., 1959). Recently, models based on deep neural networks (DNNs) have gained much attraction due to their expressive power in learning graph dataset. The molecule-generating DNNs stand out among them for their success in the task of drug discovery.
Recent works have proposed palleull-geenratiing DNNs based on string-based and graph-based representations (Segler et al., 2018; Jin et al., 2018; You et al., 2018; Shi et al., 2020; Jin al., 2020). For example, Segler et al. (2018) proposed to train language models on the domain sspcifcc linear string representation of molecules, i.e., simplified molecular-input line-entry system (SMILES, Weininger 1988). Since the string- based models ignore the inherent graph structure, recent works explore the graph-basee based generation that (a) atom-by-atoon (You et al., 2018; Shi al., 2020; Luo et al., 2021) or (b) nubstructure-basee (Jin et al., 2018; 2019; 2020) operations.
Notably, the substructure-based generative models (Jin et al., 2018; 2019; 2020) successfully exploit the molecular prior knowledge: the graphs sparsely connected and can be represented junction tree with molccular substructure as building blocks. Based on such knowledge, the models construction operators which (a) require fewer number of steps to generate
use the junction the whole molecular graph and (b) guarantee generating molecules that satisfy the chemical valence rules. However, despite such advantages, a recent benchmark (Polykovskiy al., 2020) suggests that they do not outperform the existing methods in terms of learning the data distribution, even when compared with the simple SMILES-bar based language models. We hypothesize that this due to the models using a coarse -rarindd representation of the molecule and they may lack the ability to learn the inner semantics of each substructure- based building block.
Contribution. this work, we propose a novel framework, coined spanning tree-based graph generation (STGG), for fine-gratd fine-grained generation of molecules while exploiting their sparsity.' Mainly inspired from the SMILES representation of molccules, our idea is to generate the molecular graph
While our framework designed for general sparse graphs, focus on the molecular graphs in this paper.

---

Published as a conference paper at ICLR 2022
Figure 1: (left) Benzaldehyde, (middle) its spanning tree (blue) and residual edges (red), and the corresponding constructive decisions (right). Open circle represent atoms and bonds in the molecule.
composition of spanning as building blocks. Such a formulation allows our framework to utilize compact tree-constructive operations define the molecular graph connectivity. See Figure 1 for illustration of how formulate the generation of a molecular graph as sequence of tree-constructive operations.
and the corresponding residual edges with atoms and bonds
Since our framework maintains the molecular graph structure during construction, it can pre-determine decisions that (a) violate the graph construction rule and (b) lead molecules that violate the chemical valence rule. Such criteria allow control over the generative model to guarantee generating valid molecular graphs by forbidding invalid actions. This is in contrast to prior works (Shi al., 2020; Luo et al., 2021) that generate the molecular graph atom-by-atom but determines the validity of construction operations through a sample-rejection scheme.
To recognize the spanning tree-based representation used our STGG framework, we propose Transformer architecture (Vaswani et al., 2017) with tree-based relative encoding. Inspired by recent works (Villmow et al., 2021; Lukovnikov & Fischer, 2021; Ying et al., 2021) on tree-based and graph-based Transformers, our framework expresses the relative position between two vertices as the number forward and reverse edges in the shortest path between them. We also introduce an attention-based mechanism for constructing residual edges.
We experiment on popular graph generation benchmarks of QM9, ZINC250K, and MOSES to validate the effectiveness of our algorithm. In the experiments on QM9 and ZINC, our STGG framework outperforms the existing graph-based generative models by large margin. In the MOSES benchmark, our algorithm achieves superior performance compared to both string-based and graph- based methods for majority of the metrics, e.g., Fréchet ChemNet distance (Preuer al., 2018) and negment-based similarity. We also conduct experiments on the offline optimization task for high penalized octanol-water partition coefficient and achieve competitive results.
SPANNING TREE-BASED GENERATION OF GRAPHS (STGG)
2.1 OVERVIEW
In this section, we introduce our spanning tree-based graph generation (STGG) framework to sequentially generate a molecule as a composition spanning tree and residual edges. To this end, we propose compact cree-constructive operations inspired by the simplified molecular-input line-entry system (SMILES, Weininger, 1988). contrast the existing SMILES- based molecular generative methods, our framework (a) allows inferring the intermediate graph structure and (b) is generally applicable to graph types other than molecules. particular, (a) further enables our framework to control the construction process such that the sequential operations comply with tree-constructive grammar and only generate molecules satisfying the chemical valence rule.
Molecular graph representation. To apply our framework, we represent a molecule as a bipartite graph 9 (A, B, where A and B are the set of vertices associated with atoms and bonds of the molecule, respectively.? Each edge {a, b) E E is assigned for each adjacent pair of atom and bond. We assign attributes &a E Xatton and ra Noond for vertices a A and b E B to indicate the corresponding atom type and bond order, respectively. For example, { ["C", "N", "O"} C Xaton and ["_" "="} Xnona See Figure I for an example of such molecular graph representation.
Molecular graph from sequence of decisions. To generate the molecular graph G (A, E) our framework makes sequence of decisions di....,dy dr to generate spanning tree T = (Ar, Br
Many existing works, e.g., (Shi al., 2020), non-bipartite graph with bonds assigned edges.
2

---

Published as a conference paper at ICLR 2022
attach atom
attach bond
branch start
branch end
bond terminate
"C" Katon
Boond
("
")
d Frea
[eos]
Table I: Operations (top) and example of corresponding decisions (bottom) used in STGG.
C-C(=0) (-C=MC-O#C-C+2)
C-C(+0) (-C+-)-
C-C(=0) (-CemC-C#Q-C-2)
Spranch
[| Frea
Scranch = []. frae = |]
Seranch = DI Crae
C-C(-0) (-C+=C-O=C-O-2)
C-C(-0) (-C+=C-C-C---2) [1], Leae =
C-C(-0) (-Cx=0-O=0-C-a
Scranch = Crux
Stranch
Serunch [ Lree
C-C(=0) (-C=-C-O=C-C+2)
C-C(=0) (-C#=C-C=C-C-2)
C-C(=0) (-Ck=C-C=C-C-2) Suranck [1], frea
Scranch = [1], Lrea =
Suranck [1], frea =
[2]
C-C(=0) (-=+=0-==O-0=2)
C-C(=0) (-C+=0-C=0----2) Suranhh [1], fres =
c-0(=0) (-C*=0-0=0-C=2)
Sweach [1]. free
Seranch [1 Cres
Figure 2: Demonstration of executing sequence of decisions C-C(=0) (-C+-C-C-C-O22) Here, we use the numbers 1 and to mark vertices for the purpose of illustration. Next, {"C", "O"}, ("_", "="), " "(". ")", "*", and "2" correspond attach, atom, attach bond, branch start, branch_end end, rew.rreaaatoooo and res ben_ operations, respectively. The decision "2" denotes res bond operation selecting the vertex marked by "2" Decisions that are not executed at the respective time- step are faded out (gray). Location of the pointer vertex ipoint is indicated by an arrow (red).
and set of residual edges & = EY each iteration, seven types of decisions are applicable, i.e., attach atom, attach bond, branch start, branch end, res atom, res bond, and terminate. See Table for examples of decisions and the corresponding operations. We provide detailed description of the graph construction process Section 2.2.
Generating valid molecular graphs. Without any control, model may generate decisions that (a) do not comply with the grammar of STGG (b) leads to molecule violating the chemical valence rule. To prevent this scenario, we conduct two criteria for determining validity of the given decision for (a) and (b). We further elaborate this in Section 2.3.
2.2 DECISION PROCESS FOR SPANNING BEE-BASED GRAPH GENERATION
We explain how STGG framework incorporates the decisions d1 di...., .d to build the spanning tree T = (Ar, Ey and residual edges En from scratch. To this end, our framework introduces the state information of (a) a pointer vertex ipaine E AT U By for specifying the target of
3

---

Published as a conference paper at ICLR 2022
Algorithm Tree-basee generation of molecular graphs
1: Input: sequence of decisions dı, ,
2: Output: graph 9 = (A, B, E), atom attributes (aa and bond attributes {mA}SES
3: Set AT 0, B +- 0, ET 0, En +- 0, and ' <- (AT, BT, BT,
Initialize the empty graph.
4: Set Crea as an empty list and Seranca as an empty stack.
5: fort= fort= do
6: if d4 E Naton then
D Add a new alom vertex.
7:
Create a new atom vertex a set t AU {b} and za t- di. If [ > 0, set ET + ET U Ha, [point]].
8:
Edgge is added when free is not empty.
9:
Set ipoint f- a.
10:
if d, E Xyous then
b Add a new bond vertex. BT + BT U (b), and ny d.. Create new bond vertex b and set ET ET ((b, Epoint Br Set spoint +- b.
11:
12:
13:
> Add pointer vertex into the queue. if di E C.m. then Pop di from Lrea and update &R t- ER ([tooin,, } }}. Add a new residual edge.
if "*" then Insert époint into Lrex-
14:
15:
if d. = "(" then Insert épaint into Spranch-
b Add pointer vertex into the stack. Update pointer vertex from the stack.
16:
if d.
then Set ipoint pop(Seranca)
17:
Set A AT. B Br, and & ET ER.
the next operation, (b) a stack Seranch that stores vertices to use later as a starting point of a "branch" in the spanning tree, and (c) list Lras that stores vertices to use later for constructing residual edges.
In what follows, we describe the seven types of operations, i.e., attach. atom, attach_ bond, branch. start, branch end, res atom, res bond, and terminate, corresponding to decision values d E Xatea U Xoond U Lres ("(", ")" "*", "[eos]" "} in detail. See Table 1 for the pairs of operations and the corresponding decisions. We also provide an example of the graph construction process in Figure
Attaching atom and bond vertices to the spanning tree If the decision specifies one of the atom or bond attributes, i.e., d E Xaton or d E Xrona, it applies the corresponding attach atom and attach_ bond operations, respectively. To be specific, the attach_atom operation adds new atom vertex into the spanning tree T as neighbor of the pointer vertex épointer i.e., Ar < Ar U {a),,ET + &T U {a, ipointer). The value is set as the new atom attribute, i.c., Va f- d. The newly added vertex is set as the next pointer vertex, i.e., (pointer similarly adds a new bond vertex. For example, a line graph can be expressed as a sequence of attach atom and attach bond operations, e.g., C-C-C where "C" E XA and "-" Xg.
a. The attach_ bond operation
Branching out the spanning tree. To express graph structures with vertices of degree larger than two, our framework utilizes pairs of the branch start and the branch end operations with decision values of (" and ")" ", respectively. To be specific, the branch_start operation inserts the current pointer vertex into a stack Soranch of vertices. Then the branch_en operation pops vertex from the new pointer vertex. For example, a graph with one atom vertex
the stack Scranch and sets of degree three is constructed from a sequence of decisions C-C(-C) (-C).
Adding residual edges. To construct cyclic molecular graphs, our framework generates residual edges based on pairs of res_atom operation and res_ res_bond operation, corresponding to decision values of "*" and d E Cres. respectively. To be specific, the res atom operation inserts the current (atom) pointer vertex into a list Cras- Next, when the decision value res_bond operation, the corresponding vertex dl is popped from the list Lrea and forms a new residual edge with the current (bond) pointer vertex, i.c., ER + ER. U {{d, ipointer)] }}. For an example, a cyclic molecular graph is constructed from a sequence of decisions C+-0-D-1, where "1" indicates res. bond operation with decision of the first atom vertex with attribute "C"
Lres is received for the
Termination. The decision [eos]* applies the terminate operation to finish the construction.
We provide the full algorithm in Algorithm 1. We also provide an algorithm to extract a sequence of decisions for constructing given graph in Appendix A. Such algorithm is used to obtain sequence of decisions as targets for training the generative model under the STGG framework.
4

---

Published as a conference paper at ICLR 2022
MatMul
fforward
SoftMax
A
backward
Scale
@forward =2, Qbackward =
MatMul
Øeeq
C-C(=
Linear
Linear K
Linear R
H
Øeeq
(a) Attention module
(b) Relative positional encoding
Figure 3: Attention module and the relative positional encoding used in our framework.
2.3
MASKING OUT INVALID DECISIONS FOR A VALID MOLECULAR GRAPII
Based on Algorithm I, we develop two criteria for determining whether if sequence of decisions leads to (a) valid generation molecular graph and (b) generation of a molecule satisfying the valence rule. Such criteria used mask out invalid decisions to guarantee generating valid molecular graph.
Validity of graph generation. To determine whether if a sequence of decisions lead to a valid generation of a molecular graph, we propose an algorithm that outputs a of valid decisions given the previous decision d, stack of pointer vertices Spranch, and list of atom vertices Cres during execution of Algorithm In what follows, provide brief description of grammars enforced by the algorithm. We also provide the detailed algorithm in Appendix B.
The branch.end operation only appears when the stack of pointer vertex Spranch is non-empty.
The operations res.aton and res bond are atom specifci and bond-specific. hence they only appear when the pointer vertex is located at an atom vertex and a bond vertex, respectively.
All the bond vertices have degree two, hence branch start and branch end operations only appear when the pointer vertex is located at an atom vertex.
The stack do not contain duplicates of the pointer vertex the same time.
Here, we note that our criteria for valid molecular graph generation not enforce branches and rings to be closed, e.g., C*=C-C#N is allowed by our criteria. This does not violate the validity since our Algorithm may still define valid molecular graph by ignoring the open branches and the open rings during construction, i.e., C==C-C#N generates a molecule identical to that of C=C-C#N.
Validity of satisfying the valence rule. To consider chemical validity of molecules, offers the ability to constrain the generation on molecules that satisfy the valence rule for each atom. That the generated graph G (A,, B, E") satisfies the constraint v(xa) 2 EdEN(a) o(xs) for every atom vertex a AA where v(x.)) denotes the valence of an atom type Fa and o(1²) denotes the bond order. To this end, we keep record r(a) of available valence for each atom E A and update them for each decision. For example, when bond vertex is newly added, record the neighboring atom vertex is updated by r(a) v(a) o(zs). The main idea is to forbid actions that lead to negative values of ra)). We provide detailed algorithm Appendix
framework
TRANSFORMER ARCHITECTURE FOR FREE-BASER GENERATION
In this section, describe our deep neural network architecture for generating sequence of decisions di,..., dy under the STGG framework. To accurately recognize the decision process, we employ the rree-based relative positional encodings the intermediate spanning tree T. We also introduce an attention mechanism to express a probability distribution over Lres which depends on intermediate state of the algorithm.
5

---

Published as a conference paper at ICLR 2022
3.1 TREE- BASED POSITIONAL ENCODING FOR MULTI- HEAD ATTENTION LAYERS
Each intermediate layer in our model is combination of a multi-head self-attention module and a position-wise feed-forward neural network similar to that of Vaswani et al. (2017). The main difference is on how we modify the architecture incorporate tree-based positional encodings. To be specific, let H = [ ..... _ E RTx the hidden dimension and he E RR 1xé is the hidden representation at position t. The input H is projected by three matrices We E Rx WK Rx and Wy R the corresponding representations Q, K and V. respectively. A single self-attention head is then calculated as
denote the input of a self-attention module where d is
Q = HWQ. = HHWWK
HWv,
A QK P. Pait22 2 (1)
(3) (e Ohackrane (tr .s) + Z tta)
(2)
VtK
Attention H)) = SoftMax A)V,
(3)
where Attention H) is ouiput of the attention head, M is the triangular mask to forbid the model from accessing future information while making prediction, and e denotes the element- multiplication between matrices.
Furthermore, P is the newly introduced relative positional encoding. It is summation over the trainable embedding vectors 2²),2z (2))) (z)) indexed by relative position values of @torvard (/1, 12), Sbaccoara (41, 12), and (se 12). To be specific, the tree-based relative positions Prorvard (f1, (2) and Pbackvard (f1, denotes the number of forward and backward edges in the span- ning tree path between pointer vertices at the 41tth and f2-th time step. The direction of edge is decided by order of generation in the STGG framework. Such an encoding was inspired from recent works (Villmow et al., 2021; Lukovnikov & Fischer, 2021; Ying et al., 2021) 1) using Transformers to recognize graphs and trees. Finally, the sequence- based relative position deeg(t1, = t1 t2 denotes the relative difference of time-steps for the decisions.
3.2 ATTENTION FOR UPDATING RESIDUAL EDGES.
Our model generates a categorical distribution over the space of X Xaten U Xoon V Crea U {" (", ")", "*", [eos]"], }. It is relatively feright-forward to output unnormalized probability over values of Xaton U Xoona U { {" (", ")", "*"} using a linear classifier on top of the Transformer model. However, it is non-trivial to assign probability values for res bond operation, i.e., decisions values of d E Lres, since Lres varies between different time-steps. To handle this case, we use an attention-base based mechanism for assigning unnormalized probability to decision values in the list Crea- To be specific, at the final layer of our model, we obtain the following probability distribution p(d).
p(d) x (m)(d) (d) exp(wII (dg(d) (d) exp(h, WWWTA)
vd E Naton U Xpona U {" (", ""","""""""""""" "*"},
(4)
Vd E Crea,
where Wa E RIX a decision-specifie vector, W1, W2 E R are weight matrices, and is the decision embedding, i.e., output of the Transformer layer corresponding to the previously made decision. Furthermore, ha is the embedding corresponding to a past decision d E Cree Finally, (d), (d) are the mask for excluding invalid decisions that violate the validity of graph generation and valence rule, respectively. The masks are obtained using the criteria explained in Section 2.3. We use the mask during both training and evaluation of the model; this differs from existing graph- generative models which forbid invalid decisions only at evaluation using a sample-rejection scheme.
RELATED WORKS
SMILES-based molecular generative models. Several studies proposed to generate a SMILES al., 2016; Segler et al., 2018: Kim et al., 2021) or grammar-based (Kusner et al., 2017; Dai et al., 2018) models. While our STGG is largely inspired from such works, our STGG allows realizing the intermediate graph structure of the molecule being constructed while the SMILES-base based models cannot. This difference allows the adoption of structure- aware deep neural networks to STGG. To be specific, the difference between STGG and the SMILEES-base models appears from newly introduced graph construction procedure using a pointer vertex ppoint. a vertex-liss L, and a vertex-stack S. They allow recognizing an incomplete sequence of decisions as a graph and assigning positions each decision. In contrast,
representation of molecules using string-based (Cómez-Bombaree

---

Published as a conference paper at ICLR 2022
Table 2: Experimental results on ZINC250K and QM9 datasets.
ZINC250K
QM9
МETHOD
CORRECTABLE
VALID
UNIQUE
NOVEL
VALID
UNIQUE
NOVEL
GCPN (You et 5018)
0.20
1.0000
1,0000
MRNN (Popova 2019)
0.65
0.9989
1.0000
DRAPHNVP (Madhawa
0.426
0.948
L,0000
0.831
0.992
0.582
GRF (Honds 2019)
0.734
0.537
1,0000
0.845
0.66
0.586
GRAPHAT (Shietal., 2000
0.680
0.991
1,0000
0.67
0,9415
0.8883
MOFLOW (Zang & Wang, 2020)
0,680
0.991
1,0000
0.8896
0.9853
0.9604
GRAPHCNF (Ligge & Cheves, 2011)
0,9635
0.9998
0.9998
GRAPHDF (Can 2011)
0.8903
0.9916
1.0000
0.8267
0.9762
0.9810
MMILES-TRANSFORE
0,9558
0.9998
0,9946
0,9908
0.9629
0.6939
STGG (oun)
0.9950
0.9999
0.9989
1.0000
0.9676
0.7273
an incomplete SMILES string does not define a graph structure and assigning positions to each character is non-trivial.
Graph-based molecular generative models. Researchers have developed large variety of molecu- lar graph generation frameworks based on atom-wise and bond-wise operations (You et al., 2018; Kajino, 2019; Popova et al., 2019; Madhawa et al., 2019; Honda et al., 2019; Shi al., 2020; Zang & Wang, 2020; Luo et al., 2021). Our STGG framework simplifies the decision space of such models by exploiting the tree-like graph structures of molecules. To be specific, STGG requires O([A] |BB) decisions for constructing a molecule while the existing atom-by-aton graph generative models typically require ([A4 decisions. This implies that our generative model requires smaller number of decisions for sparse graphs like molecules, i.e., when [B] is small. Furthermore, our work is the first to successfully train Transformer architecture (Vaswani et al., 2017) for graph-based molecule generation.
In another line of research, several works (Jin et al., 2018; 2019; 2020) proposed generative models based on using the junction-tree representation with molecular substructures as building blocks. Based on such representation, such works utilize tree-constructive operations to generate the full graph. Since they operate on such a coarse-grained molecular representation, they typically require fewer number of building blocks generate the whole molecule. In comparison, framework utilizes a more fine mme-grained molecular representation and may additionally learn the inner semantics of substructures that are used building blocks for the junction tree.
STGG
EXPERIMENT
In this section, we report the experimental results of the proposed spanning tree-based graph gener- ation (STGG) framework. In Section 5.1 and 5.2, we compare with the existing graph generative models in the ZINC250K (Irwin et al., 2012) and QM9 (Ramakrishnan et al., 2014). We provide ablation studies on each component of our method using the ZINC250K dataset. Section 5.2, we compare with the existing molecule generative models using the MOSES benchmark (Polykovskiy et al., 2020). Finally, in Section 5.3, we provide our results on the molccular optimization task with respect to the penalized octanol-water partition coefficient function (PLoGP). We provide the implementation details and illustration of the generated molecules in Appendix and E, respectively.
5.1 MOLECULE GENERATION ON ZINC250K AND QM9 DATASETS
We first compare to the literature standard for the molecular generation task in the ZINC250K and the QM9 datasets. To this end, we train our generative model on the respective datasets and sample 10,000 molecules to measure (a) the ratio of valid molecules (VALID), (b) the ratio of unique molecules (UNIQUE), and (c) the ratio of novel molecules with respect to the training dataset (NOVEL). We compare with the numbers reported by recently proposed graph generative models (Shi et al., 2020; Luo et al., 2021). We also provide an additional baseline of a transformer architecture trained to generate the SMILES representation for the molecule "SMILES-TRANSFORME TRANSFORMER)).
We mark CORRECTABLE for methods which can optionally use sample-rejection scheme forbid decisions that violate the chemical rules at evaluation. Note that our framework can train the generative model under the valence correction mask during training, while existing graph generative
7

---

Published as a conference paper at ICLR 2022
Table 4: First set of experimental results for the MOSES benchmark.
METHOD
VALED
UNIQUET
UNIQUE2
INTDIV
INTDIV2
FILTERS
NOVEL
TRAINING DATASET
1.0000
1.0000
1.0000
0.8567
0.8508
1.0000
0.0000
HMM (Poiykenokiy etal. 2000)
0.0760
0.6230
0.5671
0.8466
0.8104
0.9024
0.9994
NGRAM (holykoosiy et al,, 2020)
0.2376
0.9740
0,9217
0.8738
0.8644
0,9582
0.9694
COMBINATORIAL (Lin 2017)
1,0000
0.9983
0,9909
0.8732
0.8666
0,9557
0,9878
CHARRNN (Segler
0.9748
1.0000
0.9994
0.8562
0.8503
0.9943
0,8419
AAE (Polykonsky 20300
0.9368
1,0000
0.9994
0.8557
0.8499
0.9960
0.7931
VAE (Pulykoviliy ct 20221)
0.9767
1,0000
0.9984
0.8558
0.8498
0.9970
0.6949
JT-VAE (linctal, 2018)
1.0000
L,0000
0.9996
0.8551
0.8493
0.9760
0.9143
LATENTGAN (Pyyhocko et 2019)
0.8966
1.0000
0.9968
0.8565
0.8505
0.9735
0.9498
STGG (sum)
1.0000
1,0000
0.9987
0.8556
0.8496
0.9976
0.6727
Table 5: Second set of experimental results for the MOSES benchmark.
FCD (L)
SNN (f)
FRAG (f)
SCAP (t)
METHOD
TEST
TESTSF
TEST
TESTSF
TEST
TESTSF
TEST
TESTSF
TRAINING DATASET
0.0080
0,4755
0.6419
0,5859
1,0000
0.9986
0.9907
0.0000
HMM (Pulykmnkkly stal, 2000)
24.466
25,431
0.3876
0,3795
0.5754
0.5681
0.2065
0.0490
NGRAM (Nalyamikky es 200m
5.5069
6.2306
0.5209
0.4997
0.98466
0.9815
0.5302
0.0977
COMRINATORIAL (fir 2017)
4.2375
4.5113
0,4514
0.4388
0.9912
0,9904
0.4445
0.0865
CHARRNN (Sogler 2018)
0.0732
0.5204
0.6015
0.5649
0.9998
0,9983
0.9242
0.1101
AAE (Polykardiyy 2000)
0.5555
1.0572
0.6081
0,5677
0.9910
0.9905
0.9022
0.0789
VAE (Polykooakry zt 2000)
0.0990
0.5670
0.6257
0.5783
0,9994
0.9984
0.9386
0.0588
VA- Uin et sl., 2018)
0.3954
0,9382
0.5477
0.5194
0.9965
0,9947
0.8964
0.1009
LATENTGAN (Pylhnodho 2010)
0.2968
0.8281
0.5371
0.5132
0.9986
0.9972
0.8867
0.1072
STGG (curs)
0,0680
0.5032
0.6359
0.5851
0.9998
0.9984
0.9416
0.0389
models use the valence correction only at evaluation. However, for comparison, we do not use the valence correction mask during training in this experiment.
We report the experimental results in Table 2. In the table, we observe that our STGG framework outperforms all the existing molecular graph generative models for high VALID at the cost of relatively lower NOVEL. In particular, our generative model can achieve 100% ratio of valid molecules in the QM9 dataset even without any correction procedure. Such result highlights the how our model can effectively learn the chemical rules and model the underlying distribution.
Table 3: Ablation ZINC250K.
Method
VALID
UNIQUE
NOVEL
A
0,9296
0.9995
0.9984
0,9814
0.9995
0.9955
S+T
0,9834
0.9997
0.9961
S+T+G
0.9950
0.9999
0.9989
S+T+G+V
1.0000
0.9992
0.9927
Finally, our STGG framework performing better than the SMaLES-based transformer implies how the performance of our generative model stems from the STGG framework, rather than using the Transformer architecture.
Ablation studies. We also conduct ablation studies on the ZINC250K dataset to verify the effectiveness of our method. To this end, we report the experimental results of our method without specific components. To be specific, we ablate the effects of using sequential relative positional encoding (S), tree- based relative positional encoding (T), graph-construction mask (G), and valence rule mask (V). We also consider an additional baseline of using the absolute positional encoding (A) in the original Transformer architecture (Vaswani et al., 2017). In Table 3 and Figure 4, one can observe how each component of our algorithm is crucial for achieving high VALID, In particular, the tree encoding is essential for the performance, showing the importance of tree-based representation that we use in our model.
0.30
0.04
0.0
SIT-G
0.00
S+T-GHV
0.96
Epocts
Figure 4: Ablation on ZINC250K.
5.2 MOLECULE GENERATION ON THE MOSES BENCHMARK
We also compare our method on the MOSES benchmark with the existing models. The MOSES benchmark offers a large collection of metrics to access the overall quality of generated molecules. To be specifie, in addition to VALID, UNIQUE, NOVEL, we consider internal diversity of molecules (INTDIV), ratio of samples being accepted to chemical filters (FILTERS), Frétchet ChemNet Distance (FCD), nearest neighborhood similarity (SNN), frament similarity (FRAG), and Scaffold similarity
8

---

Published as a conference paper at ICLR 2022
Figure 5: Molecular optimization results with the top-3
property scores denoted by 1ST, 2ND, and 3RD.
PLoGP
Method
OFFLINE
1ST
2ND
3RD
GVAE (Kusner 2017))
2.94
2.89
2,80
SD-VA VAE 2018)
4.04
3.50
2.96
4.56, 7 4 5.06, Y=
JT-VAE E
5.30
4.93
4.49
MIIG VAE (Kagino.
5.56
5,40
5.34
1
GRAPHAF (Shi et al. 2020)
12.23
11.29
11.05
GRAPHDF etal, 20013
13.70
13.18
13.17
5.72, 7 = 23.32, y =
STGG. 7 4 (ours)
4.56
4.55
4.53
STGG, 7 = 5 (murs)
5.06
4.89
4.86
STGG, 7 (surs)
5.72
5.15
Figure 6: Optimized 1sT molecules
STGG. 7 (ours)
23.32
18.75
16.50
(SCAF). The similarity metries of FCD, SNN, FRAG, SCAF measured with respect to the test dataset of molecules and the scaffolds extracted from them.
In Table 4 and 5, we provide our experimental result. Here, one can observe how our algorithm out- performs the existing works for 10 out of 15 metrics including FILTERS, FCD-TEST, TCD-TESSSF, SNN-TEST, SNN-TESTSF, TRAG-TEST FRAG-TESTSF, and SCAF-TEST. This highlights the ability of our STGG framework to successfully learn the training distribution.
5.3 MOLECULAR OPTIMIZATION FOR PENALIZED OCTANOI.-WATH. PARTITION CORFFICIENT
Finally, demonstrate the usefulness of our STGG framework for the task of molecular optimization. To this end, we consider the literature standard of maximizing the penalized octanol-water partition coefficient (PI.OGP). However, several works (Gao & Coley, 2020; Coley, 2020) have noted how the existing algorithms on this benchmark may not be practical, since PLOGP is ill-defined as scoring function for molecules; this scoring function may assign high values "unrealistic" molecules that are unstable and hard to synthesize in practice.
To consider this aspect, we propose a new algorithm which can control the quality of molecules by trading off scores and realistic-ness of molecules. Using this algorithm, we demonstrate how our STGG is capable of generating both (a) high-scoring molecules and (b) realistic molecules with reasonably high score. At high-level, we train a conditional generative model pp(m)) under the STGG framework with PLOGP as the condition 7. At the test time, sample from a high value to obtain high-scoring molecules. Such an algorithm is inspired from the recent offline reinforcement learning algorithms (Schmidhuber, 2019; Kumar& & Levine, 2020; Chen et al., 2021; Janner et al., 2021). We fully describe our molecular optimization algorithm in Appendix
In Table and Figure 6, we report the result of our molecular optimization experiment. We provide additional illustrations of the generated molecules in Appendix G. Here, our STGG model is able to generate molecules with considerably high PLOGP scores outside the training distribution. Furthermore, in Figure and Appendix G. one can observe how increasing 7 gradually changes the optimized molecule from realistic structures to large, chain-like, and unrealistic structures." Given such results, one may conclude that our STGG combined with the offline optimization algorithm can successfully make a trade-off between high PLoGP and realistic-ness of the generated molecules. However, we also remark that our results do not imply our optimization results to be strietly better than the baselines; we believe it is necessary to develop and incorporate quantitative measures for realistic-ner -ees of molecules to fairly evaluate the molecular optimization algorithms. We believe such research to be important future direction.
CONCLUSION
In this paper, we propose STGG which is the first spanning tree-based framework for the generation of molecules using the Transformer architecture. The key idea using the spanning tree for graph generation applies any graph type outside the molecules; we believe such extension of our work to be both promising and interesting. We also propose an offline algorithm for molecular optimization which allows the trade-off between the high score and the realistic-ness of molecules. We leave more investigation of the newly proposed optimization algorithm as future work.
"This is in agreement with prior works (Shi al., 2020; Ahn al., 2020; Luo et al., 2021).

---

Published as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
We provide explicit description of our algorithm in Algorithm 1, Appendix 2, 3, and 4. We list the hyper-parameters, the hardware used for the experiments, and the data-processing information in Appendix D. We provide illustrations of the molecules generated for the experiments in Figure 6, and Appendix E, G. We submit the full implementation of our STGG framework and the baselines used in our experiments supplementary material.
REFERENCES
Sungsoo Ahn, Junsu Kim, Hankook Lee, and Jinwoo Shin. Guiding deep molecular optimization with genetic exploration. Advances in Neural Information Processing Systems, 33, 2020.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Michael Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. arXiv preprint arXiv:2 2021.
Connor W Coley. Defining and exploring chemical spaces. Trends in Chemistry, 2020.
Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song. Syntax-directed variational autoencoder for structured data. In International Conference on Learning Representations, 2018. aeee/forum?.dd-SyyShhZZ
URL htttps://opeereee
P Erdös, A Rényi, et al. On random graphs. In Publicationes mathematicae 6, volume 1, pp. 290-297, 1959.
Wenhao Gao and Connor W Coley. The synthesizability molecules proposed by generative models. Journal of Chemical Information and Modeling, 2020.
Rafacl Jomez-Boomarelll Jorge -paraague,,, Timothy D Hirzel, David Duvenaud. Dougal Maclaurin, Martin A Blood-Forsythe, Hyun Sik Chae, Markus Einzinger, Long-Gwang Ha, Tony Wu, et al. Design of efficient molecular organic light-emitting diodes by high-throughput virtual 2016.
screening and experimental approach. Nature materials,
Shion Honda, Hirotaka Akita, Katsuhiko Ishiguro, Toshiki Nakanishi, and Kenta Oono. Graph residual flow for molecular graph generation. arXiv preprint arXiv: a9Xi:: 1352/, 2019.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Michael Janner, Qiyang Li, and Sergey Levine. Reinforcement learning big sequence modeling problem. arXiv preprini arXiv:2106.00 02039, 2021.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference Machine Learning, pp. 2018.
Wengong Jin, Kevin Yang, Regina Barzilay, and Tommi Jaakkola. Learning multimodal graph-to- graph translation for molecule optimization. In International Conference Learning Representa- tions, 2019, URL /tstps://oppnreeeee
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. In International Conference on Machine Learning, pp. to appear, 2020.
Hiroshi Kajino. Moleeular hypergraph grammar with its application molecular optimization. In International Conference on Machine Learning. pp. 3183-31919 PMLR, 2019.
Hyunseung Kim, Jonggeol Na, and Won Bo Lee. Generative chemical transformer: attention makes neural machine learn molecular geometric structures via text. arXiv preprint arXiv:2103.002133 2021.
Aviral Kumar and Sergey Levine. Model inversion networks for model- based optimization, 2020. URL https: / wttp://www......o.rr/./ss.sssaa.
10

---

Published as a conference paper at ICLR 2022
Matt J Kusner, Brooks Paige, and José Miguel Hemáádezz-obato. Grammar variational autoencoder. In Interaational Conference on Machine Learning, pp. 1945-1954, 2017.
Phillip Lippe and Efstratios Gavves. Categorical normalizing flows via continuous transformations. In International Conference on Learning Representations, 2021. URL net
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph variational autoencoders for molecule design. In Advances in Neural Information Processing Systems, pp. 7795-7804, 2018.
Tairan Liu, Misagh Naderi, Chris Alvin, Supratik Mukhopadhyay, and Michal Brylinski. Break down in order to build up: decomposing small molecules for fragment-basee based drug design with e molfrag. Journal of chemical information and modeling, 5774)6627-631, 2017.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International
Conference on Learning Representations, 2019. htattts:///penneiiee...tt
Bkg6RiCqY7.
Denis Lukovnikov and Asja Fischer. Insertion-based tree decoding. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pp. 3201-3213,2022
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. GraphDF: A discrete flow model for molecular graph generation. In International Conference on Machine Learning, 2021.
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invertible flow model for generating molecular graphs. arXiv preprint arXiv: 2019.
Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-Lengeling, Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Simon Johansson, Hongming Chen, Sergey Nikolenko, Alan Aspuru- Guzik, and Alex Zhavoronkov. Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models. Frontiers Pharmacology. 2020.
Mariya Popova, Mykhailo Shvets, Junier Oliva, and Olexandr Isayev. MolecularRNN: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv:/905. 13372, 2019.
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Günter Klambauer. Fréchet ChemNet distance: metric for generative models for molecules in drug discovery. Journal of chemical information and modeling, 58(9): 1741, 2018.
Oleksii Prykhodko, Simon Viet Johansson, Panagiotis-Chrisn Chrristos Kotsias, Josep Arús-Pous Esben Jan- nik Bjerrum, Ola Engkvist, and Hongming Chen. A de novo molecular generation method using latent vector based generative adversarial network. Journal of Cheminformutiic, 11(1):1-13, 2019.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1::17, 2014.
Juergen Schmidhuber. Reinforcement learning upside down: Don't predict rewards-just map them to actions. arXiv preprint arXiv: 2019.
Marwin HS Segler, Thierry Kogej, Christian Tyrchan, and Mark P Waller. Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS central science, 4(1): 120-131, 2018.
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang. GraphAF: a flow-based autoregressive model for molecular graph generation. In International Conference Learning Representations, 2020. URL https: http::::///pppeeeeiiee
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
11

---

Published as a conference paper at ICLR 2022
Johannes Villmow, Adrian Ulges, and Ulrich Schwanecke. A structural transformer with relative positions in trees for -eseueeeee tasks. In 2021 International Joint Conference on Neural Networks (IJCNN), pp. 1-10. IEEE, 2021.
David Weininger. SMILES, chemical language and information system. introduction method- ology and encoding rules. Journal of chemical information and computer sciences, 28(1):31-36, 1988.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform bad for graph representation? arXiv preprint arXiv:2106.05234, 2021.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in Neural Information Processing Systems, pp. 6410-6421, 2018.
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 617-626, 2020.
12

---

Published as a conference paper at ICLR 2022
A EXTRACTING SEQUENCE OF DECISIONS FROM MOLECULAR GRAPH
In this section, we explain algorithm for finding sequence of decisions construct given molecular graph g (A. B, E). The high-level idea is to first perform depth-firs' search on G find spanning tree (A, B, ET) and the corresponding set of residual edges ER E\, Then the algorithm traverses the spanning tree T according to the depth-first search tree while (a) allocating aranch_stare and branch. end for vertices with degree higher than two and (b) adding res asmoom and res _ondd operations for any vertex covered by residual edge {a, b} E &R.
To this end, we utilize stack Sats that stores the list of vertices in G and branching tokens ") a vertex, the algorithm
to visit. At each iteration, an element of stack Sata popped. adds the corresponding decision for attach_aton and attach_bond operations. If the vertex has more than two successors with respect to the spanning tree T, the successors are inserted into the stack Sare with surrounding " (" and ") tokens. If the vertex has only successor, the successor inserted into the stack without an additional operation. When the branching tokens {"(",") "} popped from the stack, the algorithm adds the corresponding decision value to the sequence of decisions. We describe the full scheme Algorithm 2.
Algorithm Generating sequence of decisions for molecular graphs
1: Input: graph G = (A, E), atom attributes [xa JaCA, and bond attributes {aa (18)
2: Find spanning tree T (A, 1, ET) of & based on depth-fire order set &n + E Er. Initialize an empty sequence of decisions
4: Choose the root of insert in empty stack Seranch-
5: do
6: Pop i from Suranch-
7: if A U B then
8: Append x; to D.
Decision to altach the atom vertex. Decisions for residual edges.
9: for j E {ilj E ((), (1,5) E { do
If A, append
D.
11:
If B, append
12:
Let V denote (ili E (V)),. ATUTUBT
Successors of in depth-first order. b Allocate decision to record pointer vertex.
13:
If [V] > 1, insert " (" to Seranhh Insert vertices
14:
Seranch-
> Allocate successors to visit later.
15:
[ > 1, insert ")" Seranch.
Allocate decision return the pointer vertex.
16:
if E ["(", """"""""" } then
17:
Append to D. while (Sermcal > 0
18:
19: Output: sequence of decisions D di,..., dr to reconstruct G.
13

---

Published as a conference paper at ICLR 2022
B ALGORITHMS FOR GRAPH MASKING
To determine whether a sequence of decisions lead to a valid generation of a molecular graph, propose algorithm that outputs set of valid decisions given the current decision d, stack of pointer vertices S, and list of atom vertices L during execution of Algorithhm 1. We provide the full description in Algorithm
Algorithm 3 Determination of grammar violation
1: Input: current decision stack Strarhh and list Lres.
2: Output: List of candidate decisions D that are valid.
3: if d E Naton then
4: Set D <- Nnan-
D. When the atom veriex is followed by bond vertex. When the atom vertex has more than one successors. When the atom vertex has neighhoring residual edge. The ") decision appears only when Seranch non-empty Allow termination.
Set +- DU ("(}}
<- DU ["*"]
Sacancal > 0, set D + ("))))
8:
Set + DU [eos]")
9:
if E Abana then
10: Set + Natan
D. When the bond vertex is followed by atom vertex. When the bond vertex has neighhoring residual edge.
Set <- U fres
12: if d "*" then
13:
Set D + Noans
When the atom vertex is followed by bond vertex.
14: Set D + U {"(")
> When the atom vertex has more than one successors. When the atom vertex has a neighhoring residual edge. ") decision appears only when Seranch non- non-empty Allow termination.
15: Set + DU ["*"}
If Sur > set - (")")
17: Set DU [eos]"):
18: ifd E L... then
19:
Set +- D)-
b Residual edge is only constructed at end of each brunch.
20: ir "(" then
21: Set Xboud.
b Branch always starts with bond vertex. Allow termination.
22: Set D + D U (" [[[eos]")
23: ifd ")" then
Set + Xoana ")"",")")
Branch is followed by start or end of another branch. Allow termination.
25: Set + DU ( [eoos]]
We also establish theoretical result on how the sequence decisions generated from Algorithm is always valid sequence of decisions for Algorithm 1. To this end, we define a valid molecular graph as follows.
Definition A valid molecular graph G = (A, B) is a connected bipartite graph where the number of vertices adjacent any bond vertex E B is exactly two, i.e., [W(b] 2.
Such a definition implies how a molecule should have exactly two atoms connected bond. Combined with additional conditions to guarantee the well-hehavior of Algorithm on sequence of decisions, we obtain the following result.
Theorem 1.
Let = (A, E), S, and C graph, a stack of vertices, and a list of vertices being updated by Algorithm and sequence of decisions di...., dr. If the sequence of decisions satisfies the criteria defined by Algorithm 3, the following properties are satisfied.
PL At the t-th step of Algorithm 1, |8| if ")
P2 At the I-th step of Algorithm 1, de E if E AUB.
P3 When dr = [eos], the graph G is a valid molecular graph.
Here, P1 and P2 implies how the operations Algorithm are well-defined for di, di,..., dr.
14

---

Published as a conference paper at ICLR 2022
Proof. First, P1 is enforeed by the step in Algorithm 3 which forbids the decision value of ") " when the stack empty. Next, P2 is enforced by the step selecting decision values from the current list of vertices L.
To enforce P3, when dr [eos], G (a) has to be connected bipartite graph and (b) the number of vertices adjacent to any bond vertex has to be exactly two. For (a), Algorithm allows the decision of de Xaton U L. only when the pointer vertex is bond vertex, i.e., d E Xand Similarly, de E Mandd is allowed only when E Naton U ("*", " (""). For (b), the algorithm does not allow adding bond vertex b B to the list of vertices C, which is required for any vertex with degree higher than two. Termination is not allowed when there exists bond vertex with degree smaller than two.
15

---

To this end, we propose an algorithm which iteratively updates a record r(a) of available valence for each atom vertex E A. The key idea is to (a) update the record accordingly for each addition of atom and bond orders and (b) pre-allocate valence for the branch_ster stacctstttttt and res atom operations by the amount of minimum bond order E o(x). The second part (b) is required since the branch_start and res_atom operations indicate future bond vertices to be added as a neighbor of Published as a conference paper at ICLR 2022
C ALGORITHM FOR VALENCE MASKING
To consider chemical validity of molecules, our framework offers the ability to constrain its generation on molecules that satisfy the valence rule for each atom. That is, the generated graph G = (A, B, E) satisfies the constraint vIra) 2 (oeN(a)) o(2s) for every atom vertex A where vzza) denotes the valence of an atom type Za and o(25) denotes the bond order.
the current atom vertex. We provide the full description in Algorithm 4.
Algorithm 4 Determination of valence rule violation
Input: Intermediate tree T (Ar, By, Er). current pointer vertex lgoines previous pointer vertex époint. current decision d, previous decision d, and record r(-) of available valence.
2: Output: Newly updated and the list D of decisions that violates the valence rule.
3: if d Naton then
4: Set r(ipoin)) + v(d).
Initialize record by atom valence. b Update record using previously added bond vertex. > Rejecc bond orders higher than the record.
5: Set ((ppoi))) f- T(ppotne) - o(d).
6:
Set D + {a/2 E Noans, o(x) > r-
7:
if ((post)) < min Nooo o(z) then
8:
Set D DU (", "*"].
Reject decisions requiring minimal amount of valence.
9:
if d E Xione then
10:
if d * " then
11:
Set ((ggan)) + ((doinn))) o(d).
b Update record of previously added atom vertex.
else
13:
Set r(ppiatt) + r(ppotas) o(d) + M o(z).
Update previously added vertex considering pre-allocated valence.
14:
Set D +- [xf E Naton, v(x) < r((potn))))-
bo Reject atom valence lower than bond order.
15: Set + DU faræ E free; r(x) o(d) ging o(x)}-
> Reject residual edge candidates with valence lower than bond order.
16:
if d "(" then
17: Set r(poosnt) <- r(pp122)) - minggn o(z).
Pre-allocate minimum bond order.
18: Set + farØ E Noand, oxx) > r r(6posnt)
> Reject bond orders higher than the record.
19: d ")" then
20: Sct +
21: if d "*" then
22: Set r(ipoin)) r(ppoiae) min olz).
Pre-allocate minimum bond order. Reject bond orders higher than the record.
23:
Set D + fxl/ E Xoand, o(x) > r r(pposne))
24:
if Leea then
25:
Set (d) <- r(d) + min o(x) olI
Update record of previously added atom vertex.
26: Set +
Given Algorithm 3 and 4, we establish the following theoretical guarantee.
Definition 2. A valid molecular graph G = (,)) satisfies the valency rule if v(xa) 2 EDEN o(x6) for every atom vertex a E A.
Theorem 2. Let G (,,, be graph being updated by Algorithum and sequence of decisions di....,d dr. If the sequence of decisions satisfies the criteria defined by Algorithm and 4, the corresponding graph G satisfies the valency rule.
16

---

Published as a conference paper at ICLR 2022
Proof. To prove the validity of our algorithms, we show that (1) r(a) I v(za) EdEA(()) o(1b) and (2) r(a)= O any time-step applying Algorithm 4 the sequence decisions di...... dr.
For (I), we note that a record of atom is initialized ((aa))E)eee) o(1²) whenever it is newly added to the graph & by decision. Furthermore, whenever a new edge is added by attach.bore and res bond operation, the corresponding bond order o(2)) is deducted from the record. Importantly, a minimum bond order mi. o(x) also added to the record for attach bond operation consecutive to a branch_stars operation or res_bond operation. We note how this does not harm (I) since the minimum bond order has already been deducted (or pre-allocated) by the corresponding branch start and res atom operations, respectively.
For the case of (2), one can observe that Algorithm 4 filters out the atoms and bonds that will deduct the record of the corresponding atom to be negative. This completes proves the correctness of our theorem.
17

---

Published as a conference paper at ICLR 2022
D IMPLEMENTATION DETAILS
In this section, provide specific details how implement the STGG framework for experiments.
Training detail. For all the experiments, we train the Transformer under STGG framework for 100 epochs with batch size of 128 for all the dataset. We the A (Loshchilov & Hutter, 2019)
optimizer with constant learning rate of 10-4. We use three and six Transformer layers for {QM9, ZINC250K) and MOSES, respectively. The rest of Transformer-relater configurations follow that of the original work (Vaswani et al., 2017); we use the attention module with embedding size of 1024 with eight heads, MLP with dimension of 2048, and dropout with probability of 0.1. Using a single Quadro RTX 6000 GPU, it takes approximately three, ten, and 96 hours to fully train the models on QM9, ZIKC and MOSES datasets, respectively.
Pre-processing- For the whole dataset, we use the following set atom vocabularies Xaton "CH", "CH2", "CH-", "CH2-", "C", "N-", "NH-", "N" "NH". "N+" "NH+", "NH2+", "NH3+" "O-". "O". "O+", "DH+", "F", "P", "PH", "PH2". "P+", "PH+", "S-", "S", "S+", "SH". "SH+" "CI" "Br". "I" }. Note that assign different features for the number of explicit hydrogens and formal charges. This allows our algorithm to properly allocate maximum valence for each atom feature. Next, we the bond vocabulary X = ("-", "=" "#"), corresponding to bond orders of single, double, and triple, respectively. For explicit calculation of the atom valence during molecular construction, we train our models on kekulized molecules, i.e. aromatic bonds are fixed to single or double bonds.
atom numbers with different
18

---

Published as a conference paper at ICLR 2022
E EXAMPLE OF GENERATED MOLECULES
3o
u
Figure 7: Example of molecules generated from the QM9 dataset.
poc
of
Xo
Figure 8: Example of molecules generated from the ZINC250K dataset.
ob ondo a00 p20 tho son Ad juor
AQo Iud dorte the syo 3ح tho uho
Ino poato sco eap mep Doo
Figure 9: Example of molecules generated from the MOSES dataset.
19

---

Published as a conference paper at ICLR 2022
F OFFLINE OPTIMIZATION OF MOLECULES
In this section, describe our offiin molecular optimization algorithm mainly inspired by existing works in offline reinforcement learning (Schmidhuber, 2019; Chen et al., 2021; Janner et al., 2021) and offline model-based optimization (Kumar & Levine, 2020).
For maximizing reward function defined molecule, our algorithm consists of simple steps. First, our offline optimization algorithm trains a conditional generative model pm h)) where m is the molecule and y the reward function evaluated on the offline dataset of molecules. Next, the cwward-cndiitioal generative model samples highly-rewarding molecules by generation conditioned on high values of y. In particular, we set the value of y to extrapolate outside the training dataset. Based on the highly expressive power of Transformer architecture, our algorithm can successfully generate highly-rewe rewarding molecules.
20

---

Published as a conference paper at ICLR 2022
G ADDITIONAL EXPERIMENTAL RESULTS ON MOLECULAR OPTIMIZATION
GLOpX doowo Rgo go
Mag Ramo wolf
Figure 10: Top-16 molecules generated under condition
= 4.
Sora toroo oloRo q
J
Fronp
ootor
auooo
Figure 11: Top-16 molecules generated under condition 5.
880
Figure 12: Top-16 16 molecules generated under condition 7
Figure 13: Top-16 16 molecules generated under condition 7 = 7.
21

---

Published as a conference paper at ICLR 2022
H
COMPARISON WITH CG-VAE
Table 6: Experimental results for the QM9 benchmark.
MЕTHOD
VALID
UNIQUE
NOVEL
FCD
SNN (f)
PRAG
SCAF (1)
CG-VAE 2018)
1.0000
0.9857
0.9435
1.8515 0,5851
0.3940
0.9484
0.6628
STGG
1,0000
0.9561
0.6978
0.9998
0.9984
0.9416
Table 7: Experimental results for the ZINC benchmark.
METHOD
VALID
UNIQUE
NOVEL
FCD (L)
SNN (1)
FRAG (t)
SCAF (1)
CG- GG-V et.. 2018)
1.0000
1.0000
0,9982
11.335
0.2656
0.8118
0.2411
STGG (ouzs)
1.0000
0.9996
0.9978
0.2778
0,4664
0,9932
0,7192
In this section, we additionally compare our STGG framework with the 2018), which is another utom-by-atom graph generative model that allows masking out the action space to generate molecules satisfying the valence rules. Compared to Table 2, we additionally use the FCD, SNN, Frag, Scaf metrics to measure the faithfulness of the generative models for learning underlying distribution of molecules. Note that the VALID metric used in Table is insufficient to compare the faithfulness of STGG and CG-VAE since they both enjoy the guarantec to generate molccules satisfying the valence rule.
model (Liu et al.,
In Table 6 and 7, one can observe that our algorithm highly outperforms the CG- VAE in terms of faithfully learning the underlying distribution of molecules at the cost of relatively lower UNIQUE. For example, FCD score of our STGG for learning the ZINC dataset is 0.2775 while that of the CG-VA VAE is 11.33, This highlights the expressive power of STGG framework.
22


Reviews:
[{"review_id": "q4pQWx36VtK", "reviewer": "Reviewer_nQAs", "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": "Strength:\n * Comprehensive evaluation. The method is evaluated on standard ZINC250K, QM9, MOSES benchmarks and compared with many previous baselines. The model is able to achieve state-of-the-art results on most of the metrics.\n\nWeakness:\n * As noted in the paper, SMILES strings are also constructed by spanning tree algorithms. As shown in Figure 2, there is very little difference between generating a spanning tree versus generating a SMILES string. The only difference between STGG and SMILES string is the adoption of a tree-based transformer.\n * STGG is a node-by-node graph generation method following the depth-first order (DFS) of a graph. CG-VAE (Liu et al. 2018) is also a node-by-node graph generator, but following the breadth-first order (BFS). It would be great if authors can compare STGG with CG-VAE given their similarity.", "summary_of_the_paper": "This paper proposes a spanning tree based generative model (STGG) for molecular graphs. STGG sequentially generate a molecule's spanning tree and fill in the residual edges on the way. The spanning tree construction is similar to the standard SMILES representation, but the model operates on a molecular graph rather than a SMILES string. STGG adopts a tree-based transformer with relative positional encoding for tree generation, and a attention-based predictor for residual edge prediction. The method is evaluated on standard ZINC250K, QM9, and MOSES benchmarks and outperform existing baselines.", "summary_of_the_review": "This paper has different pros and cons. I vote for weak accept because the empirical results seem convincing. Adding comparison with CG-VAE is important and I hope the authors can address this concern during rebuttal.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dI5tzuq3h5W", "reviewer": "Reviewer_4r4T", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "## Strengths\n### + Reasonable approach to construct a molecule based on spanning-tree representation\nWhile there are a number of approaches to generate a graph based on spanning-tree representation (i.e., SMILES), most of them treat a SMILES representation as a text and do not exploit the spanning tree. The method proposed in this paper explicitly uses the spanning-tree representation to construct a molecule, and it seems a very reasonable approach to construct a molecule, if inspired from SMILES.\n\n### + Clarification on the known flaws in the penalized log P score\nI appreciate the authors clarify the limitation of this benchmark task and propose an alternative evaluation scheme. As stated in Section 5.3, this benchmark does not serve as a proper benchmark task, but not many researchers do not discuss it. This statement is very important to the community.\n\n\n## Weaknesses\n### - Relationship to the existing work\nI appreciate the authors summarize the relationship to the existing work in Section 4. I understand that the proposed generation procedure is different from the existing ones, but I don't understand why the difference is important. For example, the authors state that \"Our STGG framework differs from this line of research since it proposes a new type of graph-based operations for generating the molecular graph\", but do not clarify how it is different, and why the difference is important. Such a comparison is important for readers to understand the essence of the proposed method.\n\n### - No theoretical guarantee to generate valid molecules\nI am not convinced with the mechanism to comply the valence rule, and I wonder if there is a theoretical guarantee that this mechanism can comply the rule or there is a counter-example where this mechanism cannot guarantee it.\nWhen constructing a ring, it is desirable that the tail atom has one remaining valence, and the ring closes by adding a residual edge. Is it possible that the tail atom has no remaining valence and the ring cannot be closed? For example, C*=C-C≡C seems not to be rejected by the mechanism, but we cannot close the ring.\n% This may be a question, rather than weakness. If there is any misunderstanding, please correct it.\n\n### - Relationship to the classical VAE+BO approaches\nAs discussed in Section 5.3, one of the major issues in the plogP optimization task is that unrealistic molecules can optimize the score. I consider there had been an implicit agreement that the optimized molecules should resemble the training data, which leads to the classical molecular optimization method combining VAE trained on the real-world molecules and Bayesian optimization. As far as I am aware of, the method by Kajino [Kajino, 19] achieves the best scores among the methods using this approach. While the proposed method can control the trade-off between the score and realisticness, it seems the proposed method is not better than VAE+BO approaches in this setting.\n\n[Kajino, 19] Molecular Hypergraph Grammar with Its Application to Molecular Optimization, ICML-19.\n\n---\n\nGiven the discussion below, all of my concerns have been addressed.", "summary_of_the_paper": "This paper presents a method to construct a molecular graph, which is inspired by a spanning tree. In specific, a molecule is constructed by a sequence of actions, each of which adds an atom, adds a bond, starts/ends a branch, adds residual edges for a circular structure, and terminates. The generative process is controlled by a transformer-based neural network, which is specialized to tree construction procedure.\nThe empirical studies show that the proposed method can learn the distribution of molecules comparably or better than the existing methods, and can be used to molecular optimization.", "summary_of_the_review": "I am tending to reject this paper because of the following reason.\nWhile the proposed method is very reasonable if inspired by SMILES, its novelty within the literature of graph-based models is less clear, and thus, I am not very enthusiastic about the proposed method. I would increase the score if I were convinced of the contribution of this work to the literature of graph-based models more clearly. So, I would like the authors to clarify which aspect of the proposed graph generation method is important and why. In addition, I would like to ask the authors to discuss why they don't take the VAE+BO approach to molecular optimization, which can implicitly constrain the output to be similar to the training molecules.\n\n---\n\nNov 21. Updated the score to 5, given the first response by the authors. But still not positive to accept this paper because of the inconsistency in the experiment on molecular optimization.\n\n--\n\nNov 24. Since all of my concerns have been addressed in the current version, I would recommend to accept this paper.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QqOJUGltsB3", "reviewer": "Reviewer_PBPv", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\nI think this work has a lot of novelty and merit. The idea of using a transformer which can view earlier decisions with attention mechanisms increases the possibility of valid molecular generation. This also forms a conceptual departure from highly sequential or reinforcement learning-based methods. They show their results on 3 datasets MOSES, QM9 as well as ZINC250 K. As can be seen in the results, many previous methods do not run well on QM9 and are often overfit for 1-2 benchmarks. The authors also perform ablation tests which show the improvements with several of their design choices including the use of graph structure, the use of a transformer and the use of graph construction and valence masks. \n\nWeaknesses:  \nAlthough the ablation studies that are used by the author validate some of the design decisions they don't validate or establish the need for several of their most novel decisions: 1. The two-pronged system of first generating spanning trees and then residual edges, 2. the use of a bipartite graph rather than one that uses edges to represent bonds, 3. the use of spanning trees themselves. In addition I would like to see some results on how long it takes to train this transformer model as opposed to other models, due to what I believe is a highly increased number of parameters given the positional encoding and the attention mechanisms. \n\n\n\n", "summary_of_the_paper": "This paper proposes a new paradigm of graph generation, a transformer network sequentially generates a sequence of decisions to generate a spanning tree for a bipartite graph. These decisions have 7 forms such as attach atom, attach bond, branch start,  etc. After the spanning tree, they add residual edges. The authors also have a focus on generating valid graphs (which is seen in the results) in which they mask out invalid decisions during the generation process itself. \n\n", "summary_of_the_review": "Interesting proposal, needs more validation. ", "strength_and_weaknesses": "", "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": "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": "-YehbZ1IdrZ", "reviewer": "Reviewer_xNX3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Strengths**\n* The proposed method is quite novel. The key idea is to represent the molecular graph as a sequence of decisions according to a **novel spanning tree-based grammar**. Compared to SMILES-based molecular generative methods, STGG allows inferring the intermediate graph structures and takes the graph structure into consideration. The method is general and can be applied to other graph structures.\n* The paper is well written. The experiments of the work are comprehensive and well designed. In particular, for PLOGP molecular optimization, they adopt an offline optimization algorithm, which is interesting to me.\n* The code is already provided in the Supplementary Material\n\n**Weaknesses or Questions**\n* What is the main advantage of STGG over atom-by-atom graph generative models? The Table2 indicates that STGG tend to generate molecules with low novelty and the main advantage is validity.\nThe authors mention that atom-by-atom methods determine the validity via sample-reject. But actually, we can also mask out invalid decisions for atom-by-atom methods by keeping a record of valency and bond information.\n* **Concerns on training data**: To get the training data, the authors use algorithm2 presented in Appendix A to obtain the sequence of decisions from graph structures. For each graph structure, how many sequences do you get? Do you fix the random seed of this algorithm, or generate the sequence on the fly in each batch with different randomness? My key point is that if the training sequence is generated on the fly for each batch with random DFS, the training data for SMILES-TRANSFORMER should also be augmented (instead of using canonical smiles) for a fair comparison in Table 2.", "summary_of_the_paper": "The paper proposes a novel spanning tree-based graph generation (STGG) framework. The key idea is to represent the molecular graph as a sequence of decisions according to a **novel spanning tree-based grammar**, and then model these decision sequences using the transformer.\n\nTo accommodate such a novel algorithm, several interesting techniques are involved, e.g., representing molecules as bipartite graphs, using tree-based positional encoding for transformer. The authors claim that the proposed method allows generating valid molecular structures and inferring the intermediate graph structure.", "summary_of_the_review": "I think the paper reaches the bar of ICLR for the reasons listed above.\nHowever, several concerns remain to be addressed.", "strength_and_weaknesses": "", "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": "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:

Meta-review: This paper proposes a spanning tree-based graph generation framework for molecular graph generation, which is an interesting problem. The tree-based approach is efficient and relatively effective in molecular graph generation tasks, and the empirical results are convincing. There were some concerns during the initial reviews, but all of them have been addressed during the discussion phase. Thus, I recommend this work be accepted.
Decision: Accept (Spotlight)