Overcoming Order in Autoregressive Graph Generation for Molecule Generation
Authors: Edo Cohen-Karlik
Eyal Rozenberg
Daniel Freedman
Venue: Accepted by TMLR ()

Abstract: Graph generation is a fundamental problem in various domains, and is of particular interest in chemistry where graphs may be used to represent molecules. Recent work has shown that molecular graph generation using recurrent neural networks (RNNs) is advantageous compared to traditional generative approaches which require converting continuous latent representations into graphs. One issue which arises when treating graph generation as sequential generation is the arbitrary order of the sequence which results from a particular choice of graph flattening method: in the chemistry setting, molecular graphs commonly have multiple SMILES strings corresponding to the same molecule. Inspired by the use case of molecular graph generation, we propose using RNNs, taking into account the non-sequential nature of graphs by adding an Orderless Regularization (OLR) term that encourages the hidden state of the recurrent model to be invariant to different valid orderings present under the training distribution. We demonstrate that sequential molecular graph generation models benefit from our proposed regularization scheme, especially when data is scarce. Our findings contribute to the growing body of research on graph generation and provide a valuable tool for various applications requiring the synthesis of realistic and diverse graph structures.

Published in Transactions on Machine Learning Research (07/2024)
Overcoming Order in Autoregressive Graph Generation for Molecule Generation
Edo Cohen-Karlik
Verily Research
School of Computer Science, Tel Aviv Universily
Eyal Rozenberg
eyaarosemberryiyyooll..cmm
Verily Research
Daniel Freedman
danieefreedmonn@@goooee.co
Verily Research
Reviewed OpenReview: https: openreviee..eeeee.e.mmmmm net/ forum? id= BK6Ge10tRy
Abstract
Graph generation is fundamental problem in various domains, and is of particular in- terest in chemistry where graphs may be used to represent molecules. Recent work has shown that molccular graph generation using recurrent neural networks (RNNs) is advan- lageous compared to traditional generative approaches which require converting contimuous latent representations into graphs. One issue which arises when treating graph genera- tion as sequential generation is the arbitrary order of the sequence which results from particular choice of graph flattening method: in the chemistry setting, molecular graphs commonly have multiple SMILES strings corresponding the same molecule. Inspired by the use case of molecular graph generation, we propose using RNNs, taking into account the non-sequential nature of graphs by adding an Orderless Regularization (OLR) term that encourages the hidden state of the recurrent model to be invariant to different valid or- derings present under the training distribution. We demonstrate that sequential molccular graph generation models benefit from our proposed regularization scheme, especially when data is scarce. Our findings contribute to the growing body of research on graph generation and provide valuable tool for various applications requiring the synthesis of realistic and diverse graph structures.
Introduction
Graphs are powerful representations of complex relationships and structures. While graphs have many application domains, we are particularly interested in their use in chemistry, in which setting graphs may used to represent molecules. A dedicated class of architectures, Graph Neural Networks (GNNs), has been developed to handle the specific properties of graphs. Graphs are naturally versatile objects, but such versatility comes at the cost of lack of structure and no naturally induced order. Most GNN architectures therefore operate applying neural architecture at the node level followed by an aggregation step which takes into account the local neighborhood structure of the graph. By stacking multiple such layers, GNN is able to perform node-level graph-level tasks that take into account the entire structure of the graph.
The ability lo generate realistic and structured graphs is essential for various applications ranging from drug design (De Cao & Kipf, 2018; Du et al., 2022b; Honda et al., 2019; Jin et al., 2018; Madhawa et al., 2019; Shi et al., 2020; You et al., 2018as Zang & Wang, 2020) program synthesis (Brockschmidt al., 2018; Hindle al., 2016; Chen et al., 2021a; Allamanis et al., 2017; Hellendoorn al., 2019; Yin & Neubig, 2017:
Bielik et al., 2016; Dai et al., 2018). In recent years wide variety of generative models have been developed,

---

Published in Transactions on Machine Learning Research (07/2024)
including generative adversarial networks (GANs), variational autocncoders (VAEs), normalizing flows, and diffusion models. These algorithms devise different strategies to learn continuous mappings from a latent distribution to space of realistic examples. Unfortunately, graphs do not admit a natural representation in a contimuous space; consequently, the discrete and unordered nature of graphs make them less amenable to the methods mentioned above for the task of graph generation. different type of generalive model relies on autoregressive architectures which enable processing a sequence and generating the next element: for example, these architectures are commonly used for large language models. Generally, autoregressive models are applicable when the generated objects admit sequential order.
In this work we focus on sequential generation of graphs using autoregressive neural architectures. A strong motivating factor for choosing autoregressive archilectures is that we are particularly interested in molecular graph generation; and in this context Flam-Shepherd et al. (2022) have shown that sequential generation is favorable compared other approaches. The specific representation we consider is depth-first search (DFS) trajectories of graphs. The reasons for this choice of representation is twofold: (a) DFS is a natural way of flattening graphs into sequences; (b) in the chemistry community DFS is used to convert molecules into strings. However, issue arises when converting graphs into sequences: there many DFS trajectories for given graph. Indeod, for many graph flattening methods, there is an arbitrariness in the order of the sequence which results (Vinyals et al., 2015; Chen et al., 2021b).
In order to alleviate the dependency on a specific trajectory, we add a regularization term dubbed Orderless Regularization (OLR) which ensures the learnt model is invariant to different DFS orderings of the same graph. For the sake of training with OLR, one needs to generate different DFS trajectories with a common end-vertex which is known to be hard (Beisegel et al., 2019). While motivation originates from the use-case of drug discovery and molecular graph generation, we provide general formalism of the notion of graph-level invariance and devise an efficient algorithm to generate common end-vertex trajectories under certain constraints. Finally, we demonstrate empirically that our regularization term is beneficial when the amount of training data is limited by considcring the use case of small molecule generation.
The reminder of the paper is structured as follows: in Section 2 we provide background and intuee the concepts, definitions, and notations used throughout the paper. Section goes into the details of OLR over DFS trajectories. Scction 4 is devoted to related work. In Scction 5 we provide empirical evidence for the effectiveness of OLR. Section 7 provides concluding remarks.
2 Background
In this section we formally define the problom of graph generation, the notations and definitions necessary to present our proposed method. We denote matrices by bold uppercase letters, M Raxm, vectors by bold lowercase letters, v, and the 7th entry of o by us. We proceed with a general formulation of recurrent models.
2.1 Recurrent Models
Let X, H. and y' be the spaces of inputs, hidden states, and outputs, respectively. Given input sequence x (#1 (.,)) E X", recurrent model consists of two functions, the state update function fa Hx - H,
h fu(h;,
(2.1)
and the output function fo: fl x X X
y: = folte, x2).
(2.2)
where ho E H. We overload the notation and denote the hidden state and output of a recurrent model over a sequence as fu(x) and [x(x) respectively.
The formulation presented of recurrent models broad and able to capture RNNs as well as more complex architectures such as Gated Recurrent Units (GRUs, (Chung et al., 2014)) and Long-Short Term Memory networks (LSTMss, (Hochreiter & Schmidhuber, 1997)). For example, in the case of very simple, vanilla
2

---

Published in Transactions on Machine Learning Research (07/ 2024)
RNN,
h1+1 (Ah4 + Bax)
(2.3)
and
yr = ,CC + -De;)
(2.4)
where A, B, C, D are matrices with the appropriate dimensions and Tn, By are standard non-linearities such as sigmoid or tanh.
2.2 Graph Generation
A graph is given by G = (V,E) where V is a set of nodes (or vertices) and & S V is a set of tuples denoting the nodes connected by an edge in the graph. Additionally, for each v E V, denote by Ie e R" the features of node v. Similarly, eur E I denotes the features of the edge (u,v) E E. For example, a molecular graph, nodes are atoms, and their features will contain the element; and edges correspond to bonds, and their features will contain the bond types (single, double, ctc.).² Another example is of social networks, where nodes corresponds to users and their features to user profiles; and edges correspond to connections between users and their features contain metadata on this connection.
The topic of designing neural networks to operate specifically on graphs is dominated by Graph Neural Networks (GNNs) which mostly rely on a message-passing scheme to propagate information between nodes. While these architectures are extremely successful node level and graph level prediction, they are not as prevalent in the context of graph generation, and many such approaches are restricted small graphs (though (Davies et al., 2023) is notable exception).
Formally, the task of graph generation is usually concerned with learning to model distributions: concretely, given a set of N graphs { originating from an underlying distribution the goal of graph generation is to devise an algorithm that generates new graphs from the underlying distribution p. Prior work has mostly adapted successful generative methods over a continuous space to the domain of graphs (Gómez- Bombballl et al., 2018; Blaschke et al., 2018; Kadurin et al., 2017; Prykhodko al., 2019). In this work we focus on using recurrent models which can be employed naturally to generale discrete objects. Crucially, Flam el al. (Flam-Shepherd al., 2022) have shown that sequential generation is favorable compared to competing approaches in the context of molecular graph generation.
2.3 Sequential Graph Generation
When applying recurrent models for graph generation, the graph first needs to be "flattened" into sequence. As there is no natural order for graph, one must artificially induce such an order; for example, the approach taken by (You et al., 2018b) considers generation of breadth-first search (BFS) trajectories. While there are many ways to convert a graph into a sequence, in this work we focus on depth-first search (DFS); a strong motivation for this choice is that this is the method used to convert graph molecules into a linear representation called SMILES strings (Weininger, 1988). By convention, the output of the DFS algorithm is a spanning tree and we consider the induced order of the graph as the order in which the vertices were visited during the DFS run (also known pro-order traversal).
In what follows we formally define the concepts discussed.
Definition 2.1. Given connected graph G = =VVE) with |V] = n, we say the permutation π E Sn is a valid ordering of G if it is possible to run DFS over G and visit the vertices in the order induced by n. Denote the sequence corresponding to a valid ordering π of G by
s(G, n) (U=(I),.... Uz(m)))
(2.5)
Denote the set of all such sequences for a given graph G by
- (s(G, : n is valid ordering of G}.
(2.6)
I NNte that the bias term may be cncapsulated into the input processing matrices by expanding the input with an additional dimension and assigning fixed value of that coordinate.
2 Molecular node and edge features may contain other properties as well.
3

---

Published in Transactions on Machine Learning Research (07/2024)
Clearly, for non-trivial graph S(G) will contain many sequences. In this work we have special interest in sequences that share the same end vertex.
Definition 2.2. Let ((G,)) denote all sequences terminating at node v, formally,
S(G, u) = (s e S(G) 8n = ta
(2.7)
In case there are no volid DFS trajectories terminating as certain node v, S(G, = = by definition.
In the following section we discuss the desired properties for recurrent models when used for graph generation.
3 Structure Agnostic Recurrent Models
Recurrent models are natural choice when generating discrete objects such as text. On the other hand, graphs discrete objects with naturally induced order. In Section 2 we described mapping between graphs and sequences; and in particular, the fact that many different sequences correspond to the same graph. In this section we present our method that overcomes the issues described.
3.1 Generating Depth-First Search Traversals
In this work we use recurrent models to generale DFS traversals of graphs. Clearly when generating DFS traversal, the next node to be generated depends the nodes generated thus far and in particular the last generated node. An important observation is that the output of the recurrent model should be invoriant to different valid orderings corresponding to the same subgraph as long as they lead to the same node. The following definition formalizes this notion,
Definition 3.1. We say recurrent model is structure invariant with respect to connected graph G if
Vee V, Vs S2 S(G,)) it is the case that fo(s1) fo
(3.1)
If the above condition is satisfied for all D, we say that the recurrent model is structure invariant with respect to distribution D.
Figure 1 depicts graph and two different DFS traversals sharing the same root and terminal node. A recurrent model processing the two DFS traversals will ideally generate the same node that will be attached to node D.
Definition 3.1 describes the structure invariance property with respect to a graph. Since recurrent models generate the traversal sequentially, we would like this property to hold at any moment during generation, i.e. we want to modify Definition 3.1 to take into account partial DFS traversals.
Definition 3.2. For connected groph G, we say connected subgraph & = G is induced by DFS over G if there erists a valid ordering E Sn of G, and k & n such that (U+(1)...., is a valid ordering of G. Denote the set of all DFS induced subgraphs over G by GDFS(G).
At this stage, reader might question the necessity of Definition 3.2 and why GDFS(G) differs from the set of all connected subgraphs of G. We note that for general connected graph GDrs(G) does not correspond to the set of all connected subgraphs.
Proposition 3.3. For connected graph G,
GDFs(G) * {G GG G and & is connected)
(3.2)
Figure 2 depicts a graph and two connected subgraphs, one which is induced by DFS and the other that cannot be obtained by a DES traversal.
With the notion of DFS induced subgraphs in hand, we now present the following definition of total structure invariance:

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
A
6
B
C
D
4
E
E
Figure 1: Illustration of two DFS traversals of the same graph starting from node A and terminating at node D, blue lines denote traversal order. (Left) traversal resulting in the sequence A(BEF)(C) (Right) traversal resulting in the sequence ((C)) The parentheses denote the opening and closing of branches when traversing the tree; with this syntax it is possible reconstruct the tree from such sequences. Note that multiple sequences correspond to the same tree, a fact that lies at the heart of this work.
2
A
B
C
D
C
F
Figure 2: Mustration of the same graph with two connected subgraphs: (Teft) subgraph which is not induced by DFS. (Right) subgraph induced by DFS, arrows depict traversal resulting in the sequence BA(CF)D.
Definition 3.4. We say recurvent model is totally structure invariant with respect to connected groph G, if
YH GDrs(G), Ve V(G), VsL. S(G,v) v) it is the case that fo(s1) fo(sz).
(3.3)
If the above condition is satisfied for all G D, we say that the recurrent model is totally structure invariant with respect to distribution D.
5

---

Published in Transactions on Machine Learning Research (07/2024)
Note that per Definition222, the condition vacuously holds for non terminal nodes.
In the next section we discuss how to train recurrent models which are totally structure invariant with respect to given training distribution over graphs.
3.2 Regularizing Towards Total Structure Invariance
Motivated by the observation discussed in Section 3.1, we propose training recurrent models that are to- tally structure invariant with respect to the underlying distribution over graphs. It would be appealing to characterize the class of all totally structure invariant functions and optimize over those. Unfortunately, it is difficult to attain a crisp characterization of structure invariance as this property depends on the training distribution.
Instead, we propose encouraging total structure invariance via regularization. Specifically, we would like to minimize the following auxiliary loss
Eg (on-s B s (fo(s)) fo(s2))
(3.4)
which we refer to as Orderless Regularization (OLR). Examining Equation 3.4, we note that sampling from GDFs(G) is easily done by randomly selecting a root node and running DFS with stochastic decision making, On the other hand, given & and u sampling from S(G,v) is hard and has been shown to be NP-complete (Beisegel et al., 2019).
3.3 Sampling Trajectories with Common End Vertex
The problem of generating all DFS trajectories that terminate the same vertex is hard and there are no known efficient algorithms for this task. In order to overcome this obstacle we apply heuristic for computing such trajectories. We highlight that our proposed scheme is not equivalent to uniform sampling over all possible trajectories; however, in Section 5 we show that the resulting regularization scheme is effective empirically.
Next, we formally show that for practical graphs there exists efficient algorithms generate such trajectories.
Definition 3.5. Let G = E) be an arbitrary graph. G is said to be k-edge-connected if the subgraph G' = (V, connected for all & & such that [ε] < and 38 s.t. |8) = k and G' is not connected.
Proposition 3.6. There is an efficient algorithm to find distinct DFS trajectories with common end verter for any k-edge connected graph for 2.
We note that in many real world tasks, graph are rarely k-edge connected for k > 2. For example, in the ZINC molecular dataset, more than 99.5% of molecular graphs are 1-edge connected.
Proof Sketch. Find a min-cut: by the definition of L-edge-connected graphs the min-cut includes a single crossing edge v). By removing (u, v) the graph partitioned into two connected components, G1 and G2 containing and respectively. Run DFS G₁ with u the rool vertex to result in (u1,-.., uk), and similarly for G2 to result in (U1,..., vm) (where i1 & and un u). We can now construct DFS traversal G by 'gluing' together the sequences as,
(U1, U1 Uk, 02
Um)
(3.5)
We can run another (stochastic) DFS on G from u to obtain (ua())...., Ua(k)) where γ Sa and #(1) We can construct a second DFS sequence as in Equation 3.5,
(01, Ma(l).... (a(k): U2 .., vm)
(3.6)
We have created two valid DFS sequences that both terminate at Um-
3 and denote the size of partitions and satisfy + m Vl.

---

Published in Transactions on Machine Learning Research (07/2024)
See Appendix A for the full details and the case of 2-edge connected graphs. Note that our method for generating distinct DFS trajectories is not exhaustive and there may be additional trajectories not detected via the algorithm induced by the proof sketch.
4 Related Work
In this section we discuss several relevant topics to graph generation. For a comprehensive review on graph generation see (Guo & Zhao, 2022; Zhu et al., 2022).
One Shot Generation Classic generative architectures (e.g. Variational autoencoders (VAFs) (Kingma & Welling, 2013), Generative adversarial networks (GANs) (Goodfellow et al., 2020), etc.) work by learning a continuous mapping from a latent distribution to generate new examples with similar properties to the training distribution. These models usually incorporate a neural architecture that maps directly from the latent space to the domain of the training data (c.g. images) and therefore the output space must be predetermined. These properties pose a challenge when applied to the domain of graphs, as the latter are discrete objects with variable size and prior work (Assouel et al., 2018; De Cao & Kipf, 2018; Du et al., 2022a; Fan & Huang, 2019; FlammShepheed et al., 2020; Guo et al., 2020; Honda et al., 2019; Ma et al., 2018; Madhawa et al., 2019; Shi et al., 2020; Simonovsky & Komodakis, 2018; Zou & Lerman, 2019) has used a one-shot generation strategy. That is, the output space is limited by design to a specific representation of graphs (i.e. adjacency matrix or adjacency list) of specific size and the output is generated in a single forward pass. While the onc-shot strategy has its merits, there are a few significant drawbacks such as the inability to generate graphs with arbitrary large number of nodes.
naturally induced order. In order to circumvent these caveats,
Sequential Generation The idea of using autoregressive models for graph generation is not new and there have been several works in this vein. GraphRNN (You et al., 2018b) proposes generating BFS trajectories in order to limit the number of possible orderings per graph. Other works take a different approach of generating odges in an autoregressive manner (Bacciu et al., 2020; Goyal et al., 2020). Additional approaches include MolecularRNN (Popora et al., 2019) which incorporates a reinforcement learning environment to generate nodes and edges sequentially. Yet another approach includes scquentially generating subgraph structures (Jin et al., 2018; Liao et al., 2019; Podda et al., 2020). Another recent work (Bu et al., 2023) treats the induced order as a problem of dimensionality reduction and attempts to learn mappings from graphs to sequences. In this work we argue that the most effective inductive bias for the use of autoregressive models to generate graphs is to be invariant to diffcrent orderings possible under the training distribution.
Molecule Generation One of the most prominent uses of graph generation, which is used for evaluation in this work, is that of molecule generation. Molecular generation is applicable the development of syn- thetic materials, drug development and more. Molecules are 3D objects which are naturally represented as point clouds* with corresponding geometric approaches (Garcia Satorras et al., 2021; Simm et al., 2020a;b; Hoogeboom et al., 2022) which utilize inherent symmetrics in the architectures employed. While 3D repre- sentations are richer and carry significant information that does not transfer to 1D and 2D representations, they are costly to obtain and therefore the corresponding amount of data is limited as compared to 1D and 2D representations, which are ubiquitous. Another aspect of molecule generation is when the generation is conditioned to satisfy certain properties. For example, (Skalic et al., 2019; Zhang et al., 2022; Rozenberg & Freedman, 2023) generate molecules that are conditioned to bind to specific ligand structures, (Kang & Cho, 2018; Zang & Wang, 2020) generate molecules that fulfill certain chemical properties. In this work we consider the task of de-novo generation (Arás-Pous et al., 2019; Lim et al., 2018; Pogány et al., 2018; Tong et al., 2021) where the objective is to generate molecules with similar properties to those in the training data.
Permutation Invariant Recurrent Models Another relevant topic is the use of autoregressive models
for problems over sets which, like graphs, lack a natural order. There have been many works focusing on
4In a point-cloud representation of malecule each point represents atom and bonds are implicit from the distances between atoms.
7

---

Published in Transactions on Machine Learning Research (07/2024)
Table 1: Wiener Index results for training with and without OLR. We report Mean Absolute Error (MAE) and accuracy (computed by rounding the output to the nearest integer). For both metries considered, training with OLR dramatically improves performance.
MAE (1)
Accuracy (1)
Vanilla
2.24 (0.12)
0.18 (0.02)
OLR
1.32 (0.10)
0.28 (0.04)
problems over sets. The most prominent of these is DeepSets (Zaheer et al., 2017) which applies a deep neural network on each element of the set and then aggregates the result with permutation invariant operator (e.g. sum or max), finally applying another deep neural network on the aggregated result. There have also been autoregressive works designed for sets: Murphy el. al. (2018) use RNNSs on different per- mutations and output the average. While this requires n! orderings for set of size n, the authors have presented several approximation tochniques and justified them empirically. Cohen-Karlik et al. (2020) have shown that while DeepSets are universal, some permutation invariant functions require unbounded width to implement successfully and have proposed using RNNs with a regularization term which enforces per- mutation invariance. In this work we extend the concepts introduced in previous works into the realm of drug design and sequential graph generation, where a desired property models is to hold invariance for certain permutations
induced by the data distribution. In the work of Cohen-Karlik et al. (2020) the regularization is geared towards fully permutation invariant models; that is, their work may be viewed as specific case of graph-aware regularization where the data is represented by fully connected graphs. In this work we generalize these concepts and formalize the problem for graphs with more general structures. As a result, the straightforward regularization term proposed in (Cohen-Karlik et al., 2020) cannot be used, and a more sophisticated regularization scheme is required. Specifically, using the lens of DFS trajectories of graph, we suggest regularizing over valid sequences and devise an efficient approximation for generating such sequences.
5
Experiments
5.1 Wiener Index
In order to gauge the effectiveness of OLR, conducted straightforward experiment designed to predict the Wiener index of graphs. The Wiener index is a topological metric for molecules, involving the summation of distances between all pairs of vertices within a given graph. These graphs are symbolically represented as strings, using parentheses as exemplified in Figure 1.5 We employed a Long Short- Term Memory (LSTM) model with hidden width of 100, trained as a regression task. During training, we used graphs containing nodes and a training set consisting of 50 examples; our aim was to determine the effectiveness of OLR in the case when daia is extremely scarce. The network was trained until convergence with perfect training accuracy and evaluated on test set consisting of 200 data points. We report the average mean absolute error and accuracy as computed by rounding the networks output. As can be seen in Table 1, using OLR improves results significantly.
To further investigate the effect of training with OLR, we visualize the embeddings of the hidden state when the inputs are different representations drawn from two different graphs. desired property that different representations of the same graph are clustered together; we show that this phenomenon does indeed occur, ratustrated in Figure 3. This experiment. demonstrates that the training with OLR results in models that are significantly more invariant to different orderings of the same graph, desired property for models trained for the task of graph generation.
As the Wiener index of graph does involve node features, we omit the node labeling from the representation which yields string of only opening and elosing parentheses.
8

---

Published in Transactions on Machine Learning Research (07/ (204))
With OLR
Without OLR
3
lavel
1.0
38.0
25. 0
X
0.5
1-
*
x
*
-2
-1.0-
x
-1.5
x x
x
-2.0
-0.5
Figure 3: t-SNE visualizations of hidden states when training with and without OLR. Data is generated as different representations
two graphs (i.e. different DFS trajectorics of the same graph), the first with a Wiener index of 34, and the second with 38, (Left) training with OLR yields hidden states that are clearly clustered into two groups. (Right) training without regularization, there is no apparent separation in the embedding space between the two groups.
5.2 De Novo Molecule Generation
A prominent application of graph generation is that of molecule design. Graph generation tasks range from de novo generation where the objective to generale molecules with similar properties to given dataset, to conditional generation for which the task is to generate graph given a socond graph with specific characteristics, i.e. a ligand that binds to a specific target. Our empirical evaluation focuses on the former. We evaluate proposed regularization method the MOSES benchmark (Polykovskiy et al., 2020) and compare to relevant baselines. Our implementation is based on the work of CharRNN which use three layers of the LSTM architecture each with hidden dimension of 600 (for complete details refer to (Segler et al., 2018)). We find a consistent improvement when adding OLR to the objective of autoregressive models.
The data curated by (Polykovskiy et al., 2020) is refined from the ZINC dataset (Sterling & Irwin, 2015) which contains approximately 4.6. molecules. The authors filter the data based on molecular weights, number of rotational bonds, lipophilicity, etc. to result. in total of 2M molecules. The authors provide partitions of the data into train, test and scaffold test to allow fair evaluation."
Computing Trajectories OLR works by feeding two different trajectories that terminate at the same node. While this calculation is feasible to perform during the forward pass it introduces a computational bottlenock. In order to circumvent this issuc we employ the following calculations offline. For cach molccule we first. index all min-culs and randomly select one. We then generate multiple (10) traversals terminating the same node as described in Section 3.3 and write the sequences into a file along with the original molecule from which the trajectorics derived from. When loading the data, two trajectories are selected at random and used as inputs to the OLR objective described in Section 3.2.
Data Filtering Our offline computation of trajectorics in Section 5.2 requires that there are min-cuts that induce sufficient number of different DFS traversals terminating at the same node. While 99.9% of the molecules in MOSES have at least two such trajectories, we filter the data to remain with molecules
TThe scaffold of molecule is the structure induced by its ring systems along with the connectivity pattern between these systems. The scaffold test partition contains molecules with structures that did not appear the train and partitions. The scaffold allows for the evaluation of how well the model can generate previously unobserved scaffolds..
9

---

Published in Transactions on Machine Learning Research (07/2024)
Table 2: Generation results at validity threshold of 0.8 for LSTM and GRU architectures. Leading result highlighted in bold for each metric. Rank Average is the average position of each method over all metries considered. As can be seen, OLR outperforms the baselines considered for both architectures. Refer to the text for further details.
LSTM
GRU
Metric
Canonical
Rand.
OLR + Rand,
Canonical
Rand.
OLR. + Rand.
Unique@ IK (1)
0.8930
1.0
1.0
0.805
1.0
1.0
Unique@100 10K (1)
0.6182
0.9975
0.9981
0.5314
0.9965
0.9967
FCD/Tesi (1)
1.1208
0.8568
0.7784
1.2616
0.9602
0.9752
SNN/Test (t)
0.5599
0.4967
0.4936
0.5718
0.4948
0.4978
Prag/Test (t)
0.9953
0.9947
0.9958
0.9945
0.9940
0.9961
Scaf/ Test (1)
0.6370
0.8246
0.8220
0.5857
0.8252
0.8159
TCD/TestSF (1)
1.8318
1.4236
1.3089
1.921
1.7269
1.7022
SNN/TestSF (1)
0.5234
0.4795
0.4769
0.5352
0,4755
0.4785
Frag/TestS3 (1)
0.9920
0.9919
0.9926
0.9911
0.9908
0.9932
Scaf/TestSF (1)
0.0245
0.1185
0.0931
0.0250
0.1028
0.1123
IntDiv (t)
0.8527
0.8508
0.8537
0.8499
0.8535
0.8531
IntDiv2 (1)
0.8457
0.8449
0.8479
0.8424
0.8475
0.8471
Filters (1)
0.9889
0.9705
0.9702
0.9908
0.9678
0.9702
Novelty (t)
0.8969
0.9797
0.9809
0.8787
0.9787
0.9748
Rank Average
2.28
2.07
1.57
2.42
1.92
1.57
which have at least 10 different trajectories satisfying the criteria defined. After filtering we are left with approximately 500K molecules for training, and 55K for test and scaffold test partitions. We note that in following soctions we show our mothod most effective when training data scarce and therefore the filtering process does not limit the applicability of our proposed regularization scheme.
Results Our results for training with OLR compared to other baselines trained the same data are shown in Table 2. The most relevant baselines is CharRNN (Segler et al., 2018) which is an autoregressive model trained on Canonical SMILES. We further compare to a randomized version of CharRNN inspired by the finding of (Arús-Pous et al., 2019) which show that augmenting the data by using randomly gener- ated SMILFS representations of the same molecule improves performance. We also attempted to compare our method other non-autoregressive models such as those based on Variational Autoencoders (VAEs) (Blaschke et al., 2018; models did not produce valid molecules when trained with 1000 examples, so we do not report these results. We use the metrics defined by the MOSES benchmark (Polykovskiy et al., 2020); see Appendix B for a thorough description of these metrics.
et al., 2018; Kadurin et al., 2017); however,
found that the
In order to demonstrate the effectiveness of OLR we use 1000 randomly sampled data points from the training set and evaluate over the entire test set. When training with small amounts of data there is a trade- off between the validity of the generated molecules and the uniqueness and other metrics. Our evaluation considers the best performing models for each method providing the validity of the generated molecules exceeds 80%.
Results are depicted in Table 2. As can be seen, adding randomized variants of the molecules outperforms the original work of (Segler et al., 2018) which train an RNN as a language model using only canonical SMILES. Furthermore, adding the OLR objective execeds the performance of randomized SMILEES. In order clearly depict the performance difference, we calculate the rank of each method on each metric considered. The average rank of each method is added the last row of Table 2.
10

---

Published in Transactions on Machine Learning Research (07/2024)
6 Discussion
Graph generation poses unique challenges due to the discrete and unordered nature of graphs, which differ from continuous data typically handled by generative models. While various generative approaches such as GANs, VAEs, and autoregressive models have been successful in other domains, their application to graph generation requires careful consideration of the inherent structural complexities. Our work focuses on sequential graph generation using autoregressive architectures, motivated particularly by applications in molecular graph generation.
The choice of depth-first search (DFS) trajectories as the reprosentation for graph sequences offers a struc- tured approach aligned with the nature of graph exploration and has relevance in chemical informatics where molecules are often represented as SMILES sequences. However, the multitude of possible DFS trajectories for given graph poses a challenge when devising a regularization scheme to ensure model invariance.
The introduction of Orderless Regularization (OLR) addresses this challenge by promoting model robustness against different DFS orderings of the same sub-graph. By incorporating OLR into the training process, we mitigate the dependency on specific DFS trajectories and enhance the generalization capabilities of the autoregressive model. This regularization term proves particularly beneficial in scenarios with limited training data, as demonstrated empirically in our study on small molecule generation.
The computational aspect generating DFS trajectories with a common end-vertex, a prerequisite for training with OLR, presents a notable challenge. However, our devised algorithm efficiently tackles this challenge under specified constraints, facilitating effective training with OLR.
While our approach shows promise in small molecule generation, its generalizability to larger and more complex graphs warrants further investigaatin. Scalability issues may arise with increasingly heterogeneous graphs, necessitating advancements in algorithmic techniques or adaptations of OLR. Additionally, the de- pendence on specific constraints for generating DFS trajectories highlights a potential limitation, prompting exploration of alternative regularization techniques or exlensions OLR to handle diverse graph structures.
An avenue for future research involves investigating the suitability of OLR for diverse autoregressive archi- tectures, including Transformers. Adapting OLR to Transformer-basod models nccessitates adjustments due to the absence of hidden state, which serves as the foundation for enforcing invariance in recurrent archi- tectures. Furthermore, Transformers are permutation invariant architectures by design. A straightforward approach to encorporate OLR in Transformers would be to add positional encodings to the sequences and enforce invariance by penalizing the gap in the output of the model over different sequences representing the same graph. To test the applicability of OLR for Transformers, we repeat the Wiener index experiment (Soction 5.1) with the recurrent architccture replaced by a Transformer. We find that rogularization docs not yield an improvement in results for an architecture with a comparable number of parameters: the accuracy is 0.12 compared to 0.28 achieved by an LSTM with OLR. One explanation for the gap in performance is the fact that regularization is performed on partial sequences which admit only certain positional embeddings and the model cannot extrapolate the desired behaviour to positional embeddings corresponding to unseen string orders.
These results indicates that Transformers require a different approach to adequately regularize towards structure invariance. A possible method for biasing Transformers towards graph invariance would be design positional encodings that are aware of the structure of the graph, an approach which may have connections to Attention GNNs (Velivckovic et al,, 2017; Zhang et al., 2018; Lee et al., 2018). Consequently, the extent to which Transformer models can leverage the advantages of OLR or other regularization methods remains uncertain and is a promising direction for future work.
7 Conclusions
In this work we highlight the innate gap that every autoregressive model for graph generation must mitigate the induced order on graphs. We propose a different approach to previous works by introducing novel regularization scheme that encourages learning hypotheses that are invariant to different DFS orderings. We demonstrate empirically that our proposed method improves performance for autoregressive models and is
11

---

Published in Transactions on Machine Learning Research (07/2024)
especially effective when the available datasets are small, as is the case in many real world problems. We believe that our approach can contribute to the applicability of autoregressive models such (e.g. State-space models) for graph generation and that similar ideas may be incorporated in various generation strategies beyond the scope of this work.
References
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. arXiv preprint arXiv:1711.000 2017.
Josep Arús-Pous, Simon Viet Johansson, Oleksii Prykhodko, Esben Jannik Bjerrum, Christian Tyrchan, Jean-Louis Reymond, Hongming Chen, and Ola Engkvist. Randomized smiles strings improve the quality of molecular generative models. Journal of cheminformatics, 11(1):1 13, 2019.
Rim Assouel, Mohamed Ahmed, Marwin H Segler, Amir Saffari, and Yoshua Bengio. Defactor: Differentiable edge factorizattion-baseed probabilistic graph generation. arXiv preprint arXic:1811. 1.7966, 2018.
Davide Bacciu, Alessio Micheli, and Marco Podda. Edge-based soquential graph generation with recurrent neural networks. Neurocompullnng, 416:177 189, 2020.
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaz Krnc, Nevena Pivac, Robert Scheffter, and Martin Strehler. On the end-vertex problem of graph searches. Discrele Mathemalics & Theorelical Compuler Science, 21, 2019.
Guy W Bemis and Mark Murcko. The properties of known drugs. 1. molecular frameworks. Journal of medicinal chemistry, 39(15):288) 28887-2383,, 1996.
Pavol Bielik, Veselin Raychev, and Martin Vechev. Phog: probabilistic model for code. In International conference on machine learning, 2933 2942. PMLR, 2016.
Thomas Blaschke, Marcus Olivecrona, Ola Engkvist, Jürgen Bajorath, and Hongming Chen. Application of generative autoencoder in de novo molecular design. Molecular informatics, (7(1-)):770112,, 2018.
Mare Brockschmidt, Miltiadis Allamanis, Alexander Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXie preprint orXiv:1805.08.0 08490, 2018.
Jie Bu, Kazi Sajeed Mehrab, and Anuj Karpatne. Let there be order: Rethinking ordering in autoregressive graph generation. arXiv preprint orXiv:2305. 15562, 2023.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on (2021). arXiv preprint arXiw:2107.08377, 2021a.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco JR. Ruiz, and Liping Liu. Order matters: Probabilistic modcling of node sequence for graph generation. arXiv preprint 2Xix:2066006188 2021b.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. arXiv preprint arXiv:1412.9555 2014.
Edo Coren-Karlik, Avichai Ben David, and Amir Globerson. Regularizing towards permutation invariance in recurrent models. Advances in Neural Information Processing Systems, 33:18364 18374, 2020.
Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, and Le Song. Syntax-directed variational autoencoder for structured data. arXiv preprint arXiv:1802.08777 2018.
Alex O Davies, Nirav S Ajmeri, et al. Hicrarchical gnns for large graph generation. arXiv preprint arXiv:2306.1144 11412, 2023.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs arXiv preprint or Xio: 1805. 11973, 2018
12

---

Published in Transactions on Machine Learning Research (07/2024)
Jörg Degen, Christof Sogssheid-Gerlaade Andrea Zaliami, and Matthias Rarey. On the art of compiling and using drug-like's chemical fragment spaces. ChemMedlChem: Chemistry Enabling Drug Discovery, 3(1): 1503 1507, 2008.
Yuanqi Du, Xiaojic Guo, Hengning Cao, Yanfang Yc, and Liang Zhao. Disentangled spatiotemporal graph generalive models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6541-6549, 2022a.
Yuanqi Du, Xiaojie Guo, Amarda Shehu, and Liang Zhao. Interpretable molecular graph generation via monotonic constraints. In Proceedings of the 2022 SIAM International Conference Data Mining (SDM), pp. 73 81. SIAM, 2022b.
Shuangfei Fan and Bert Huang. Labeled graph generative adversarial 00X2:0190.003200, 2019.
networks.
arXiv preprinl
Daniel Tlam-Sheppherd Tony Wu, and Alan Aspuru- Guzik. Graph deconvolutional gentrnttttiaaneeattiiiioo arXiv preprint arXiv:2008.07087, 2020.
Daniel Flam-Shepherd, Kevin Zhu, and Alán Aspuru-Guzik. Language models can learn complex molecular distributions. Noture Communications, 13(1):3293, 2022.
Victor Garcia Satorras, Emiel Hoogeboom, Fabian Fuchs, Inggar Posner, and Max Welling, E (n) equivariant normalizing flows. Advances in Newral Information Processing Systems, 34:4181 4192, 2021.
Rafael Gómoz-Bombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hornández-Lobato, Benjamín Timothy D Hirzel, Ryan P Adams,
Sánchez--engeliing Dennis Sheberla, Jorge and Alán Aspuru-Guzik Automatic chemical design using data-driven continuous representation of molecules. ACS central science, 4(2):268-21) 276, 2018.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communicattioss of the ACM, 63(11): 139-144, 2020.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ramu. Graphgen: a scalable approach to domain-ognostic labeled graph generation. In Proceedings of The Web Conference 2020, pp. 1253 1263, 2020.
Xiaojic Guo and Liang Zhao. A systematic survey on deep generative models for graph generation. JEEE Transactions on Pallern Analysis and Machine Intelligence, 2022.
Xiaojie Guo, Liang Zhao, Zhao Qin, Lingfei Wu, Amarda Shehu, and Yanfang Ye. Interpretable deep graph generation with node-edge co-disentanglement. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & dala mining, pp. 1697 1707, 2020.
Vincent J Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. Global relational models of source code. Tn International conference on learning representations, 2019.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to local nash equilibrium. Advances in neural infor- mation processing systems, 30, 2017.
Abram Hindle, Earl T Barr, Mark Gabel, Zhendong Su, and Premkumar Devanbu. On the naturalness of software. Communications of the ACM, 59(5):122 1111 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 988):1735-118) 1997.
Shion Honda, Hirotaka Akita, Katsuhiko Ishiguro, Toshiki Nakanishi, and Kenta Oono. Graph residual flow for molecular graph generation. arXiv preprint 1909: 13521, 2019.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In International conference on machine learning, pp. 8867-88788888 8887. PMLRR 2022.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-2222222222 23322. PMLR, 2018.
Artur Kadurin, Alexander Aliper, Andrey Kazemnov, Polina Mamoshina, Quentin Vanhaelen, Kuzma Khrabrov, and Alex Zhavoronkov. The cornucopia of meaningful leads: Applying deep adversarial au- tocncoders for new molccule development in oncology. Oncotaryet, 8(7):10883, 2017.
Seokho Kang and Kyunghyun Cho. Conditional molecular design with deep generative models. Journal of chemical information and modeling, 59(1):43 52, 2018.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arx:::3112.6114 2013.
Greg Landrum. Rdkit: Open-source cheminformatics, 2006. Google Scholar, 2006.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Pro- ceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 1666 1674, 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
Jacchang Lim, Scongok Ryu, Jin Woo Kim, and Woo Youn Kim. Molccular generative model based on conditional variational autoencoder for de novo molecular design. Journal of cheminformatios, 10(1):1-9, 2018.
Tengfei Ma, Jie Chen, and Cao Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. Advances in Newral Information Processing Systems, 31, 2018.
Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invertible flow model for generating molecular graphs. arXic preprint orXiv:1905. 11600, 2019.
Andreas Mayr, Günter Klambauer, Thomas Unterthiner, Marvin Steijaert, Jörg K Wegner, Hugo Ceulemans, Djork-Arné Clevert, and Sepp Hochreiter. Large-scale comparison of machine learning methods for drug target prediction on chembl. Chemical science, 9(24):5441 5451, 2018.
Ryan I. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ríbeiro. Janossy pooling: Learning deep permutation-invaiinl functions for variablo-size inputs. arXiv preprint arXiv:1811.0190 2018.
Marco Podda, Davide Bacciu, and Alessio Micheli. deep generative model for tragment-basee molecule generation. In International Conference on Artificial Intelligence and Statistics, pp. 2240-2250. PMLR, 2020.
Peter Pogány, Navot Arad, Sam Genway, and Stephen D Pickett. De novo molecule design by translating from reduced graphs smiles. Journal of chemical information and modeling, 59(3):1136-111 1146, 2018.
Daniil Polykovskiy, Alexander Zhebrak, Benjamin Ganchez-Lengehing Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, et al. Molec- ular sets (moses): a benchmarking platform for molecular generation models. Frontiers in pharmacology, 11:565644, 2020.
Mariya Popova, Mykhailo Shvets, Junier Oliva, and Olexandr Isayev. Molccularrnn: Generating realistic molecular graphs with optimized properties. ar preprint drXi::1905.13372 13372, 2019.
Oleksii Prykhodko, Simon Viet Johansson, Panagiotis-Christ Christos Kotsias, Josep Arús-Pous, Esben Jannik Bjerrum, Ola Engkvist, and Hongming Chen. A de novo molecular generation method using latent vector based generative adversarial network. Journal of Cheminformalics, 11(1):1-13, 2019.
14

---

Published in Transactions on Machine Learning Research (07 (07/2024)
David Rogers and Mathew Hahn. Extendedd-comnectvitty fingerprints. Journal of chemical information and modeling, 50(5):742-755 2010.
Eyal Rozenberg and Daniel Freedman. Semi-equivariant conditional normalizing flows, with applications target-aware molecule generation. Machine Learning: Science and Technology, 4(3):035037, 2023.
Marwin HS Segler, Thierry Kogej, Christian Tyrchan, and Mark 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: flow-based autorogressive model for molecular graph generation. arXiv preprint arXiv:2001.000 099082, 2020.
Gregor Simm, Robert Pinsler, and José Miguel Hernández-Lobato. Reinforcement learning for molecular design guided by quantum mechanies. In International Conference on Machine Learning, pp. 8959-8969. PMLR, 2020a.
Gregor NC Simm, Robert Pinsler, Gábor Csányi, and José Miguel Hernández-Lobato Symmelry-awaar actor-critic for 3d molecular design. arXiv preprint 1227772011.12747, 2020b.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autocncoders. In Artificial Newral Networks and Machine Learning-ICANN ICANN 2018: 27th International Conference on Artificial Newral Networks, Rhodes, Greece, Oclober 4-7, 2018, Proceedings, Part I 27, pp. 412 422. Springer, 2018.
Miha Skalic, Davide Sabbadin, Boris Sattarov, Simone Sciabola, and Gianni De Fabritiis. From target to drug: generative modeling for the multimodal structure-based ligand design. Molecular pharmaceutics, 16 (10):4282 4291, 2019.
Teague Sterling and John J Irwin. Zine 15-ligand discovery for everyone. Journal of chemical information and modeling, 55(11):2324-2337 2015.
Xiaochu Tong, Xiaohong Liu, Xiaoqin Tan, Xutong Li, Jiaxin Jiang, Zhaoping Xiong, Tingyang Xu, Hualiang Jiang, Nan Qiao, and Mingyue Zheng. Generative models for de novo drug design. Journal of Medicinal Chemistry, 64(19):14011-1402) 2021.
Leonid Nisonovich Vaserstein. Markov processes over denumerable products of spaces, describing large systems of automata. Problemy Peredachi Informatsii, 5(3):64 72, 1969.
Petar Velivckovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint oxXiv:1710. 10903, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. anXiv preprint axXio:1511.06391 2015.
David Weininger. Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules. Journal of chemical information and compuler sciences, 28(1):31 36, 1988.
Pengchong Yin and Graham Ncubig. A syntactic ncural model for genoral-purpose code gencration. arXiv preprint arXiv:1704.01699 2017.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. Advances in neural information processing systems, 31, 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International conference on machine learning, pp. 5708 5717. PMLR, 2018b.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexan- der Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
15

---

Published in Transactions on Machine Learning Research (07 (07/2024) 2024)
U
v
Figure 4: Proof illustration S has cycle and two different trajectories starting from and ending with w (urw and uwrr). Concalenating with the trajectory from z to we oblain two different DFS trajectories with a shared suffix.
Chengxi Zang and Fei Wang. Moflow: an invertible flow model for generating molecular graphs. In Pro- ceedinng of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 617 626, 2020.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning large and spatiotemporal graphs. arXiv preprint arXiv:1803.0720, 2018.
Zaixi Zhang, Yaosen Min, Shuxin Zheng, and Qi Liu. Molecule generation for target protein binding with structural motifs. In The Eleventh International Conference on Learning Representations, 2022.
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on doep graph generation: Methods and applications. arXiv preprint arXio:2203.067 06714, 2022.
Dongmian Zou and Gilad Lerman. Encoding robust representation for graph generation. In 2019 Interna- tional Joint Conference on Neural Networks (IJCNN), pp. 1-9. IEFE, 2019.
A Missing Proofs
In this section show how construct distinct DFS trajectorics with common end vertex for 2 2-edge connected graph conditioned that the graph is not cycle.
Proof. From our assumption that the graph is not a cycle, there exists at least two nodes with degree >> 3. Denote by C = (s, T) a minimal cut of size 2 (such a cut exists from our assumption that the graph is 2-comnected). Denote the edges the minimal cut by e1 = (u, v) and 62 = (w,2) such that u, w and v E T. Next, we claim that at least one of the partitions contains a cycle, otherwise there is path connecting S and T' since there are nodes in the graph which have degree of in the original graph with a path between them. Assume with out loss of generality that S is the partition with cycle, thercfore there are at least. different traversals of S that start with and end with w. There is also trajectory wetw z and c. Putting together, there are at least 2 trajectories of the entire graph with common suffix which is the traversal of T. Figure 4 illustrates the proof concept.
B Metric Details
In this section we provide details for the metrics reported in Table 2.
16

---

Published in Transactions on Machine Learning Research (07 (07/2024)
A few of the similarity measures (SNN and IntDiv) are based the Tanimoto coefficient. In order to compute the Tanimoto coefficient, the molecules are mapped to a vector of fingerprints where each bit in the vector represents the presence (or absence) of specific fragment. 7 For molecules A, B, denote their fingerprints by mA and my respectively, the Tanimoto coefficient is then calculated as the Jaccard index of the two vectors,
MA O m&
mA mBl
[(AAmBB)
(B.1)
MA U mBl
mal
mBl
mA O mB
We denote the Tanimoto coefficient of molecules A, by T)..
Unique@K report the fraction of uniquely generated valid SMILES strings amongst the K molecules generated (validity is determined by the RDKit library). We generate 30, 000 molecules for each model and report for = 1, 000 and K = 10, 000. High uniqueness values ensure the models do not collapse into repeatedly producing the same set of molecules.
Fréchet ChemNet Distance (FCD) is metric for evaluating generative models in the chemical context, the method based the well established Fréchel Inceplion Distance (FID) metric used to evaluate the performance of generative models in computer vision (Heusel et al., 2017).
Fréchet distance measure the - distance (Vaserstein, 1969) from the distributions induced by laking the activations of the last layer of relevant deep neural net. In the case of FCD, molecule activations are probed from ChemNet (Mayr et al., 2018). Given a set of generated molecules, denote by G the set of vectors as obtained by the activations ChemNet, one can calculate the mean and covariance JG and Eg. Similarly, denote PR and ΣR the mean and covariance of the set of molecules in the reference set, the FCD is calculated follows,
FCD(G, =|mG pRl + Tr (Io + ER 2(E
(B.2)
where Tr(M) denotes the trace of the matrix M. Low FCD values indicate that the generated molecules distribute similarly to the reference set.
Similarity to Nearest Neighbor (SNN) is the average of the Tanimoto coelficient of the generated molecule set denoted by G and their respective nearest neighbor in a reference set of molecules denote by R. High SNN indicates the generated molecules have similar structures to those in the reference set. This metric is in the range [o, 1].
Fragment similarity (Frag) is a fragment similarity measure based on the BRICS fragments (Degen et al., 2008). Denote the set of BRICS fingerprints vectors of the generated molecules by G and similarly R for the reference molecules. The fragment similarity is defined as the cosine similarity of the sum vectors,
Frag(G,B) R) cosine
Σg. 7. 9EG
(B.3)
PER
The Frag measure is in the range of [o, 1J, values closer to indicate that the generated and reference molecule set have similar distribution of BRICS fragment.
Scaffold similarity (Scaff) is similar to the fragment similarity, instead of the BRICS fragment, Scaff is based mapping molecules to their Remis-Murcks scaffolds (Bemis & Murcko, 1996). 8 The measure also has range of [0, 1], values closer to indicate that the generated molecule set has similar distribution of scaffold to the reference set.
The molecular fingerprints obtained from RDKit (Landrum, 2006) and based the oxtennded-commuetiiity finger- prints (Rogers & Hahn, 2010).
8 Muucko Murcko scaffold the ring structure molecule along with the bonds connecting the rings, Le. the molecule without the side chains.
17

---

Published in Transactions on Machine Learning Research (07/2024)
Internal diversity (IntDiv) is mesure of the chemical diversity within generated set of molecules G. This metric indicates
1/p
IntDiv,= =
B)) A,BEG
Σ
(B.4)
G
We report the internal diversity for 1,2. This mcasure is in the range [0, 1]. Low values indicate lack of diversity in the generated molecules, i.e. that the model outputs molecules with similar fingerprints.
Filters is the fraction of generated molecules that pass a certain filtering that has been applied to the training data. The metric is the range of [0, 1], high values indicate that the model has learnt to generate molecules which avoid the structures omitted by the filtering process.
Novelty is the fraction of generated molecules that does not appear in the training set. This measure is in the range of [0, 1] and is indication of the whether the model overfits the training data.
18


Reviews:
[{"review_id": "RY2Ruit6qY", "reviewer": "Reviewer_77ej", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The motivation is great: while there have been many discussions about the relationship between permutation symmetry and GNNs for a given graph, it seems interesting and promising to consider invariance to different generation trajectories in the context of graph generation.\n2. The proposed regularizer is simple and general: it is independent of specific choice of models, which might be helpful to develop other models with such a property of invariance.\n3. The reported numerical results in Table 1,2 are good compared with some baselines.\n\nCons:\n1. As the regularizer is general and independent of specific choices of models, it would be good to evaluate this method on more models. For now, the conducted experiments are a little limited, making the results less convincing. A good example would be Table 1 in [1], where their method is also free of architectures.\n\n2. The definition 3.5 of $k$-edge-connected seems different from what was intended. It needs an additional condition ''there exists $|\\widetilde{\\mathcal{E}}|=k$ such that the induced $G'$ is disconnected''. It current definition is not correct as any $(k+1)$-edge-connected graph is also $k$-edge-connected for any $k$. Btw, I am not sure, if the new condition is added, whether the original condition is needed any more, since DFS can still be conducted on disconnected graph.\n\n3. In Definition 3.4 and (3.4), more clarification of *totally structure invariant* is needed from two aspects.\n\n    a. For any $\\\\widetilde{G}\\\\in\\\\mathcal{G}_{DFS}(G)$, any vertex $v\\\\in\\\\widetilde{G}$ does not necessarily have a DFS trajectory in $G$ that ends with $v$. This seems a little misaligned with the motivation of this work in Def 3.1.\n\n    b. Similar to the previous point, any vertex $v\\\\in\\\\widetilde{G}$ does not necessarily have a DFS trajectory in $\\\\widetilde{G}$ that ends with $v$. This might raise some questions in the implementation.\n\n4. Similar to the above point 3.b, Prop 3.6 is about sampling different trajectories ending at a certain common vertex, but can this kind of sampling be done for any vertex $v$ in subgraph $\\\\widetilde{G}$?\n\nReference:\n\n[1] Lim et al. Sign and Basis Invariant Networks for Spectral Graph Representation Learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work aims to design a method that is invariant to the ordering of different DFS trajectories when generating graphs using RNNs. \n\n1. With definitions of several necessary concepts about the ordering of DFS and induced subgraphs, it proposes a regularizer that penalizes the distance between model outputs on different DFS trajectories, which is hopefully to induce a related invariant property. \n\n2. It shows the efficiency of sampling different DFS trajectories with common end vertex on two classes of graphs. \n\n3. The proposed method is experimentally verified on two tasks including molecular generation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above concerns. All of the four points will have a significant impact on the evaluation.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "olKAMG88IK", "reviewer": "Reviewer_mLu8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. Addressing the order invariance issue in graph generation is a critical challenge, as the sequence in which nodes are generated can significantly impact the performance of generative models. The paper introduces a simple solution by adding an auxiliary loss term, to mitigate the dependence on node sequence order. \n2. The paper is well-written, offering clear and concise explanations of the motivation and the proposed methodology.\n\n## Weaknesses \n\n1.  The limited experimental evaluation in the paper is a significant shortcoming. The comparison is made against just one baseline model, which does not fully test the strengths and potential weaknesses of the OLR approach against the array of methods available in the field. Moreover, the choice to use only one type of RNN and to conduct experiments on a single dataset restricts the depth of insight into how the OLR method would perform in different settings or with different types of data. Overall, expanding the experimental results by adding more baselines and more datasets can improve the message of the paper. \n\n2. A weakness in the paper is the limited novelty of the OLR approach, especially when considering the prior introduction of a similar regularization concept aimed at achieving permutation invariance from Cohen-Karlik et al., 2020. This earlier work suggests that the core idea of using regularization to mitigate order sensitivity in RNNs has already been explored, potentially diminishing the perceived innovation of the OLR method. Addressing this, a more thorough discussion of how OLR distinguishes itself from previous approaches and contributes new insights or improvements would be beneficial to strengthen the paper's novelty claim.\n\n3. The paper's exclusive focus on Recurrent Neural Networks (RNNs) for graph generation, without discussing the potential applicability or comparison with Transformer models, is a weakness. Given the substantial advances and successes of Transformers in various domains of machine learning, including graph processing and generation, their omission from the discussion limits the breadth of the paper's exploration into modern architectures. This oversight may leave readers questioning whether the OLR method could be adapted to Transformer-based models, which are known for their superior handling of sequences and relational data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper titled \"Overcoming Order in Autoregressive Graph Generation\" presents a new approach to graph generation that addresses the challenge of order invariance in sequential graph generation models. It introduces an Orderless Regularization (OLR) term to recurrent neural networks (RNNs) that encourages the model to learn representations invariant to different orderings of graph sequences. This is particularly useful in applications like molecular graph generation where the sequence order can be arbitrary. The authors demonstrate the effectiveness of OLR through experiments on the Wiener index prediction and de novo molecule generation, showing that it improves performance, especially in data-scarce scenarios.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It's crucial to broaden the experimental validation by comparing the OLR method with more baseline models, incorporating different types of RNNs, and utilizing a variety of datasets. This would provide a more comprehensive understanding of the method's performance across different contexts and improve confidence in its generalizability and effectiveness. To deepen the experimental validation of the OLR method, the authors should aim to answer the following questions, either through theoretical analysis or additional experiments:\n- How does the OLR method compare with state-of-the-art models across different domains? This would involve not just other RNN-based approaches but also models that might use different underlying architectures or methodologies for graph generation.\n- What is the impact of using different RNN architectures (such as LSTM, GRU, etc.) on the effectiveness of the OLR method? \n- Can the OLR method maintain its performance across diverse datasets, including those with varying sizes, complexities, and domain-specific characteristics? This could involve testing on datasets from different fields, such as social network graphs, biochemical molecule structures, and communication networks, to evaluate the method's robustness and flexibility.\n- What are the computational requirements and scalability of the OLR method across different settings? Evaluating the method's performance in terms of time and resource efficiency, especially as the size of the graph increases, is essential for assessing its practical applicability.\n\n2. Add a detailed comparison with the regularization approach introduced by  Cohen-Karlik et al., 2020. Highlighting the specific advancements or differences brought by OLR is essential to clarify its novelty and contribution to the field.\n\n3. The paper would greatly benefit from including a discussion about the potential integration and comparison of the OLR method with Transformer models. This should explore how the OLR approach might be adapted for or compared with Transformer architectures, which have shown considerable success in sequence and relational data modeling.", "broader_impact_concerns": "not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qIvruVW2Up", "reviewer": "Reviewer_kS9K", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n*Paper tackles an interesting problem for sequential graph generation \n\nWeaknesses:\n\n*Experimental setup is a bit unclear\n\n*Some concerns about the evaluation", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new regularization scheme for sequential graph generation by recurrent neural networks, called Orderless Regularization (OLR), that encourages the hidden state of the RNN to be invariant to different node orderings in the training graphs. Experiments show OLR improves the performance sequential graph generation models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "*A key question that I have is how do we know the representations we obtain with OLR regularization is invariant? The performance improvements in the regression and graph generation tasks could just be due to regularization, and not due to any invariance imbued in the representations. For example, if one were to encode pairs of molecule SMILES that encode the same graph structure but are from different orderings, would we expect a more similar pair of embeddings with OLR? \n\n*I would like some more clarity on what the input graphs are for each of the evaluation settings. The molecule generation task makes more sense to me (SMILES of a set of molecules curated by Polykovskiy). What about the Wiener index task? How are these graphs generated? And are the graphs represented simply as text codes? \n\n*In the Wiener index task, the dataset size is restricted to be very small (50 training, 200 test). How does the performance gap of vanilla and vanilla + OLR change as the dataset sized is increased, eg to 500, 5000, 50000 training examples. (I just arbitrarily picked some numbers)\n\n*Table 2: Would be good to see Canonical + OLR to see the effect of the OLR regularization in the absence of any input data augmentation.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The proposed approach of regularizing auto-regressive models based on different orderings is interesting, and complemented by thorough empirical evidence.

However, two out of three reviewers raised concerns regarding the experiments, namely on the limited set of datasets considered, and more importantly other models to compare to.

A small note on the Transformer discussion in Section 6, since it is not clear to me why the proposed method doesn't apply to Transformers. In particular, with causally masked attention and positional embeddings, these models are no longer permutation invariant, and if I understand correctly, the regularization applies only to the last hidden layer before the final prediction, which can certainly be done in an auto-regressive Transformer as well?

Please address the above in a minor revision, either by further clarifying why the method doesn't apply to Transformers, or by including some simple experiments on auto-regressive (causal) Transformers. These seem important for the thoroughness of the experiments since they are currently the most widely adopted sequential architecture, and thus an important baseline to include for the TMLR community.
Decision: Accept (poster)