The search for new molecules capable of exhibiting specific target properties is a long-standing problem in chemistry. New molecules could improve technologies in many industrial and pharmaceutical areas. For example, new molecules with specific target properties can become new drugs that can improve treatments for diseases or even cure new diseases 1 . Many approaches are used to explore the chemical space such as high throughput screening [1, 2] and evolutionary algorithms [3] . Alternative approaches use Machine Learning models to predict properties of pre-defined or commercial compounds, e.g. using Recursive Neural Networks [4, 5] . In recent years the machine learning community has devoted much effort in the study of machine/deep learning models that are capable of generating candidate molecules that are likely to exhibit some pre-specified properties [6] . Thanks to the development of increasingly effective deep learning models and the presence of large datasets, this approach achieved promising results.
In literature, there are many proposals for generative models for molecules, that are often applied to the drug generation domain. The majority of them are based on the following approaches: 1) variational autoencoders [7] ; 2) generative adversarial networks [8] ; 3) recurrent neural networks [9, 10] ; 4) adversarial autoencoders [11] . To be able to compare all these different families of approaches, some frameworks have been developed as baselines, such us MOSES [12] , and GuacaMol [13] .
In this work, we focus on the variational autoencoder approach, which seems to deliver the best trade-off between generative capabilities and ease of training. In fact, adversarial based models are quite problematic to train, while models based on recurrent neural networks make it difficult to control the "shape" of the latent space and thus its sampling for the generation of novel compounds.
Early works adopting the variational autoencoder approach [14, 15, 16] share the capability of generating new molecules using SMILES [17, 18, 19] representations, which are strings describing the structure of the molecules. In particular, Grammar VAE [15] adds a context-free grammar to the standard variational autoencoder [14] to guide the correct generation of SMILE strings, while Syntax Directed VAE [16] adds a more expressive grammar, the attribute grammar [20] , capable of generating a higher number of valid SMILES strings. Other models propose to directly generate a graph representation of the molecule [21, 22, 23] . Specifically, Junction Tree VAE [21] represents molecules using graphs composed of chemical substructures that are extracted from the training set. New molecular graphs are obtained by first generating a tree-structured scaffold formed by substructures (the junction tree), and then combining the substructures together using a graph message passing network. Regularized Graph VAE [22] transforms the constrained molecule generation problem into a regularized unconstrained problem, applying a generalization of the Lagrangian function in order to move all the constrains into the optimization function. State-of-the-art Constrained Graph VAE (CGVAE) [23] uses a variational autoencoder to generate a latent space normal distribution from which the model samples a point for each atom, differently from previously models that sample only one point per molecule.
A common and crucial feature of the above models is to embed chemical background knowledge, e.g. to increase the number of generated valid molecules Syntax Directed VAE exploits a chemical-based context-free grammar, while CGVAE uses the valence of each atom to guide the generation of the bonds.
Although CGVAE returns state-of-the-art results, we argue that its choice to sample the latent space independently for each atom of the generated molecule, constitutes a limitation of the model. In fact, such independence assumption, due to the chemical/physical laws that govern the chemical realm, is clearly not satisfied in general. Thus, introducing a form of dependence among atoms, should help the model to better learn the distribution of the molecular structures in input.
In order to remove this independence assumption, in this paper we present the Conditional Constrained Graph VAE (CCGVAE) model, in which histograms of valences of the molecules are used to make the generation of atoms from the latent space dependent on the already sampled atoms. Specifically, given a valid target valence histogram for the molecule to be generated, the atom generation process is designed so to keep the current valence histogram obtained by the already generated atoms to stay compatible with the target histogram. Thus, our model is a variant of the CGVAE model, in which the decoder is enhanced to incorporate the histograms of the valences. This paper is organized as follows. In Section II we provide the background information about the CGVAE model. Section III presents our proposal for the generation of atoms driven by the histogram of valences. In Section IV, we discuss the experimental evaluation of the model. Section V concludes the paper. The code used for this work is published online 2 .
Let us start with some definitions. In this paper, we consider molecules represented as graphs. A graph is a tuple G = (V, E, L) where V = {v 1 , . . . , v m } is the set of nodes representing atoms, E is the set of edges representing bonds between atoms, and L is a function associating labels to nodes (the atom type) and edges (the bond type).
Constrained Graph Variational Autoencoder (CGVAE) is a model proposed by Liu et al. [23] . This model is based on the variational autoencoder approach in which there are two main components: the encoder and the decoder. Given in input a molecule, the encoder learns to encode its atoms in a latent space defined by a normal distribution N (0, I), where I is the identity matrix. Since the latent space is defined by a standard normal distribution, it is possible to sample new points, i.e. atoms, from that distribution and to decode them into a valid molecule by the decoder. The decoder does that by incrementally adding bonds among the sampled atoms. Specifically, at the beginning the model randomly selects an initial atom (focus) and adds (valid) bonds with other atoms till a stop criterion is satisfied. Whenever a new bound with an unconnected atom is inserted, the involved atom is inserted into a queue. When the focus atom reaches the stop criterion, an atom is extracted from the queue and it becomes the new focus atom. The generation of new bounds is then resumed with the new focus atom. It should be noticed that, the generation of a new (valid) bound (and its type) at a specific decoding point is conditioned on the current partial molecule built till that point. The decoding process stops when the queue is empty. Finally, eventually isolated atoms are removed, and the obtained molecule is returned as output of the decoder. In addition to that, the model incorporates an optimization component which allows to drive the generation process towards molecules that exhibit a high pre-specified property. This is achieved starting from random points in the latent space (i.e., set of atoms) and performing gradient ascent/descent in latent space with respect to the property of interest.
In the following, we summarize the main computational steps of the model, i.e. encoding, decoding, optimization, and training.
The first computational step of the CGVAE model is constituted by the encoder. At the beginning the encoder receives in input the graph representation of a molecule with |V | = m atoms. Then each atom v ∈ V is encoded in a normal probability distribution parameterized by mean µ v and variance Σ v . Specifically, a Gated Graph Recurrent Neural Network (GGRNN) [24] with residual connections is first used to devise a hidden representation of each atom (node) that embeds the information of its neighbors. Then, the encoder uses two neural networks 3 in order to generate means and variances for each atom from the last updated hidden state values. The vector z v representing the atom v encoded in the latent space is then sampled according to the distribution N (µ v , Σ v ). It should be emphasized that this model generates a probability distribution for each node in the graph, unlike other approaches [14, 15, 16, 21, 22, 25] that generate a probability distribution per molecule. It follows that while in the other models the sampling of a point in the latent space implies the choice of a precise molecule, in this case one sampling in the latent space implies only the choice of a single atom, making it necessary to use more samples in the decoder to perform the generation of a new molecule.
The decoder receives as input a set of vectors {z v } v∈ [1,m] , where each z v represents an atom. During the generation phase, z v 's are sampled from the normal distribution N (0, I ), where I is the identity matrix. During training, the values z v are obtained by the distribution N (µ v , Σ v ), using the reparameterization trick. The nodes are initially not connected with each other and they are associated with a state
in which τ v is supposed to be a one-hot vector indicating the node type, obtained by sampling from a learned softmax transformation from the latent space to the atom type space, i.e. τ v ∼ sof tmax(f (z v )). Actually, in the software implementing the model it is a 100-dimensional vector embedding of the node type.
Once all the atoms hidden states are obtained, a vector H init considering global information conveyed by all initially disconnected nodes is computed at step t = 0 by averaging the vectors {h 0 v } v∈V . Subsequently, at each step t the vector H t is computed by considering only connected nodes, i.e., excluding isolated nodes. The generation of bonds proceeds as described at the beginning of the section.
Whenever a new bond is added and consequently the partially constructed graph is modified, the model uses a Gated Graph Recurrent Neural Network (GGRNN) to update the information of each node, generating new states h t+1 v for each step s ∈ [0, 12]:
where h t v is the hidden representation of the atom v at the time step t and the summation is over all the neighbors of node v connected by an arc of type l for each value of l. E l is a neural network for edges of type l that preserves the dimension.
In order to decide which specific bound (and its type l) to add, the following distribution over candidate edges is used:
is the distance calculated between nodes v and u over the graph currently generated, v ← → u indicates the presence of a bond between the atoms v and u, and v l ← → u indicates the presence of a bond of type l between v and u. With the vector φ t v,u that groups the local information of the nodes and the global information on the graph, the model uses the function C (φ) to obtain the probability of existence of the edge, i.e. the bond, between the two atoms v and u. Moreover it uses the function L l (φ) to obtain the edge's type probabilities. C (φ) and L l (φ) are fully connected networks with a single hidden layer of 250 units and ReLU non-linearities. During the generation of new molecules, the existence and the type of the bonds are sampled from the probabilities returned by the two functions, while during training teacher forcing is used. The probabilities are defined as:
where both C (φ) and L l (φ) are represented by neural networks in which the last layer has a softmax function on the probabilities of outputs weighted with the use of binary masks M t v← →u and m t v l ← →u . Similarly to those used in [15] , they are intended to prohibit bonds that violate certain chemical constraints in the construction of molecules.
As already said at the beginning of the section, the generation of bonds connected to the focus atom at time step t stops when a given criterion is met. The criterion is met when a connection with a special stop-node is created. In this case the generation process proceeds by selecting a new node (i.e., the new focus atom) on which to apply the procedure again. Every time a new atom is connected, it is pushed in a FIFO structure which is queried to obtain the next node to visit. Thus, the model visits graph nodes using a breath first algorithm. At the end of the process, when the FIFO structure is empty i.e. all the (connected) nodes have been visited, all the bonds necessary for the validity of the molecule are completed by adding hydrogen atoms bonded with all the atoms whose valences are not correct. A public online software was used to manage the molecular structure 4 .
CGVAE directly incorporates in the variational autoencoder the neural network O which has the purpose of optimizing the latent space towards molecules that exhibit better values for a target property. Thanks to O it is possible to use gradient ascent/descent 5 on the latent space to find a new set of latent points that is decoded into a molecule with a better value for the target property.
The decoder is trained by supervising the creation of the arcs through breath first search. Thus, a data pre-processing step is needed. Since the idea of this model is to generate the edges from a set of initially disconnected nodes, the model should compute the marginalized probability of each edge with respect to all possible node permutations. Since this would be computationally expensive, Monte Carlo sampling is used to get an estimation. The loss function to minimize is:
where L recon is the decoder loss and L latent is the variational autoencoder KullbackLeibler loss and L opt is the optimization network loss. λ 1 and λ 2 are two constant scalar values set to 0.3 and 10, respectively. In particular, the L recon loss is calculated as the sum of the cross-entropy loss calculated on the predicted atom types probabilities with respect to the real atom types, and the cross-entropy loss calculated on the predicted bonds probabilities with regard to the real bonds at each time step. L opt loss is calculated as the Mean Squared Error between the predicted and the target property values.
This work is based on the CGVAE model (Section II). We started from the Constrained Graph VAE model code made available 6 by the authors, in which we enhanced the decoder. Let us start providing some definitions. report the corresponding histograms of the two molecules. By recalling that Carbon has valence 4, Oxygen has valence 2 and Hydrogen has valence 1, it can be noticed that the histogram of molecule A is compatible with that one of molecule B.
Definition 2 (Histograms distribution): Given a dataset of molecules T r in which each molecule is associated with its histogram of valences, the histograms distribution H T r is the probability distribution obtained considering all the histograms of valences of molecules in T r.
Definition 3 (Histogram compatibility): Let α and β be two histograms of valences belonging to two possibly different molecules, in which ν ∈ N is the maximum atom valence value for both molecules. We say that α is compatible with β:
In other words, histogram α is compatible with a second histogram β if and only if, for each valence, the value present in β is greater than or equal to that in α. Figure 1 shows an histograms compatibility example.
The basic idea is to exploit the histogram of valences to drive the atom type assignment process. Specifically, at the beginning of the generation process, in addition to the number of atoms |V | = m, we provide a reference histogram α 0 with total count equal to m, selected at random from the ones computed from molecules in the training set. The assignment of an atom type to each point sampled from the latent space is then conditioned to the already assigned atom types. As data pre-processing, the model associates to each molecule its histogram of valences and calculates the histograms distribution H considering all the molecules in the training set. Given a molecule in input to the model, we use its histogram of valences and the histograms distribution H T r to condition the decoder during the reconstruction phase. In particular, in order to condition the decoder with the histogram of valences information, we modify the initial part of the decoder which assigns the atom type to each sample from the latent space, so to make it dependent on the atom type assignment history. We do that by introducing a new recurrent component at the first part of the decoder. Figure 2 provides an overview of the CCGVAE structure, where the new decoder is represented by two distinct phases which are placed in succession one after the other. The first phase generates nodes, while the second phase generates bonds. While the second phase stays the same as defined in CGVAE, the first phase is modified as described in the following.
Here we describe how the valence histograms are used to condition the atom type assignment to samples from the latent space. The decoder receives as input the m latent space points z v with v ∈ {1, .., m}, the histograms distribution H T r and a histogram α 0 (of the considered molecule in reconstruction during training, or randomly sampled from H T r in generation). z v is sampled from the distribution N (µ v , Σ v ) during the learning procedure and from N (0, I) during the generation procedure. Let α u 0 the histogram where all the valences are 0 and t ∈ {1, .., m}, then each atom type is predicted using the following procedure:
where:
is a function that receives in input z t , the difference histogram α d t and the updated histogram α u t at each step t. This function maps the input to a new representation e t of the atom t according to the two histograms in input. In the end, this function returns an atom hidden representation R t = [z t , e t ]; • F (R t ) is a function that receives in input an atom hidden representation R t , and generates a probability distribution on the atom types;
is a function that samples the atom type from the distribution returned by the function F applying a binary mask in order to remove all the atoms whose valences have a zero-value in the histogram α d t . At training time teacher forcing is used, while at generation time and at reconstruction time, the binary mask is used in order to improve the accuracy; • Update(τ t , α u t ) is a function that updates the histogram α u t with the valence of the sampled atom type τ t ; • Sample distr (H, α u t ) is a function that, at training time and during the reconstruction task, returns always the histogram α v 0 . During the generation of new molecules this function samples from H a new histogram α t+1 with at least m atoms, such that α u t is compatible with α t+1 If there is no compatible histogram in H, a random sampling is done according to H with no further constraints. The benefit of the above procedure consists in avoiding the generation of a set of atoms that is not compatible with the histograms of valences of the molecules in the training set, in principle constraining learning and generation to focus on the original generating distribution of the training set. . The molecule in input to the encoder goes through the GGRNN with the edge-specific neural network E and then the encoder encodes the molecule in the latent space Z. The first part of the decoder receives in input the sampled points, the initial histogram α 0 and the histograms distribution H. K is a function that generates the embedding part for each atom, while F is a function that generates the atom types probabilities.
This part of the model receives as input the set of nodes generated by the previous phase and, using the same process as CGVAE, starting from a node it proceeds with the generation of the bonds towards the other atoms until the molecule is completed.
Following [26] , we compared our model with several stateof-the-art proposals on two datasets, using different metrics in order to see the potential of each model. In particular, for each model we assessed the ability to reconstruct the input molecules and the ability to generate new ones.
We consider two datasets of molecules: QM9 [27, 28] , composed by about 134,000 organic molecules with a maximum of 9 atoms, and ZINC [29] , composed by 250,000 drug-like molecules with up to 38 atoms. More details on the dataset molecules are reported in Table I . We use the same training and test splits in each dataset for each model. However, differently from [26] , we have chosen a different split of the data in the QM9 dataset as the test set in the original split did not reflect the distribution of molecules present in the training set very well. For this reason, we re-evaluated all the baseline models on the QM9 dataset. Thus, the results we report are slightly different from the ones in literature. Figure 3 shows that, for both the QM9 and ZINC datasets, the histograms compatibility distributions are long tail distributions. Moreover, it is possible to see that very often the molecules have the same histogram of valences i.e. the unique set of the histogram of valences is formed by less then 300 histograms for the QM9 dataset and less than 8000 for the ZINC dataset.
Following the indications of [26] we considered the following metrics:
• Reconstruction that, given an input molecule and a set of generated molecules, computes the percentage of generated molecules that are equal to the one in input; • Validity that, given a set of generated molecules, represents the percentage of them that is valid, i.e. that represent actual molecules; • Novelty that represents the percentage of generated molecules not in the training set; • Uniqueness that represents (in percentage) the ability of the model to generate different molecules in output, and is computed as the size of the unique set of valid generated molecules divided the total number of valid generated molecules; • Diversity that measures how much the generated molecules are different from those in the training set (comparing their substructures). This is a heuristic that uses randomly selected substructures present in the molecules. • Natural Product (NP) which indicates how much the generated molecules structural space is similar to the one (a) dataset QM9.
(b) dataset ZINC. Fig. 3 : For each dataset, in the x-axis is reported the unique set of histograms, while, by focusing a precise histogram, on the y-axis there is the number of molecules (histograms) with which the histogram is compatible.
covered by natural products [30] ; • Solubility (Sol.) which indicates how much a molecule is soluble in water, an important property for drugs; • Synthetic Accessibility Score (SAS) which represents how easy (0) or difficult (100) it is to synthesize a molecule; • Quantitative Estimation Drug-likeness (QED) which indicates in percentage how likely it is that the molecule is a good candidate to become a drug.
The Reconstruction metric is calculated on 5000 test set molecules encoded 20 times in their latent space probability distributions and decoded one time in a molecule. This process was chosen because both the encoder P e (z|x, θ e ) and the decoder P d (x|z, θ d ) contain a probabilistic component and in this way we estimate the model's ability to reconstruct the molecule considering both factors. So we treat the reconstruction joint probability of the molecule x in input as:
where θ e and θ d are the neural networks parameters of the considered model.
Since we are interested in the generation of new molecules, the other metrics are computed using a different process that consists of directly sampling 20,000 points from the standard normal distribution and decoding each point only once. Table II reports the average and standard deviation of the results obtained by the models on both the QM9 and ZINC datasets. The last line of each table reports the properties scores obtained from the molecules in the datasets, while the last column of each table reports the number of epochs required for the model training. Note that, we used the same number of epochs as the CGVAE model. As reported in section IV-A, all the results regarding the QM9 dataset are different from the results reported in [26] due to the different data split used for the training and evaluation of the models, while the results regarding the dataset ZINC are the same. However, for each dataset, all the models use the same split of data and the same procedure for generating the molecules and to perform the reconstruction task. In particular, using a test set in which the molecules are more similar to those in the training set, the models reconstruction ability tends to increase. In fact, in all models except Junction Tree VAE, the reconstruction performances are improved compared to [26] .
We can see from the table that our model improves the reconstruction performance over CGVAE on both the datasets. In particular, the reconstruction increases by 30.91% on the QM9 dataset and by 21.82% on the ZINC dataset. Models based on the SMILES molecule representation, i.e. Character VAE, Grammar VAE and Syntax Directed VAE, usually present better reconstruction values than models based on the molecule graph representation, but have problems to generate valid molecules, i.e. validity values are low. In fact, comparing our model reconstruction values with the other models results, we can see that in the QM9 dataset, CCGVAE is the best among the models that deal directly with the molecular graphs, i.e. Graph VAE, Regularized GVAE, Junction Tree VAE, CG-VAE. Considering the ZINC dataset and only the models that deal directly with the molecular graphs, the Junction Tree VAE model presents the best reconstruction value. This is due to the fact that JTVAE uses common substructures to build the final molecule, so when reconstructing very complex molecules as those in ZINC, it is easier to use substructures than to sample every single atom. However, due to the use of substructures, JTVAE presents a very low value on the diversity metric. Overall, considering all the metrics (reconstruction, validity, novelty, uniqueness and diversity), we can see that also in this case our model shows improved performances compared to CGVAE, trading off higher reconstruction and diversity with a slight decrease in uniqueness. If we consider the molecules' properties, our model presents better values regarding the NP and the Sol. metrics than CGVAE, but in the same way, our model presents worse values on the SAS and the QED metrics. Note that, if we consider the NP metric, in the QM9 dataset our model shows the highest values among the models results. MolGAN, that is the only model based on the generative adversarial approach and applicable only to the QM9 dataset for computational reasons, presents lower results if compared with our model. Overall, our model improves CGVAE in both the datasets, especially the use of the histogram of valences improves the performance on the reconstruction task.
V. CONCLUSIONS We have proposed Conditional Constrained Graph Variational Autoencoder (CCGVAE) that, starting from a state-ofthe-art model, uses the histogram of valences key-idea to guide the generation of the molecules, improving the performances of the base model in different performance metrics.
Future work will analyze and improve the computational time required for training the model. Moreover, we will collaborate with chemists in order to incorporate more background knowledge in the molecule generation process. For each data-set: the symbol '*' denotes models where we used values for the parameters tuned by the authors for that data-set; entries with blue background highlight the best score obtained for each metric; up and down arrows in front of metrics name denote whether the metric should be maximized (↑) or minimized (↓). Average and standard deviation (where applicable) computed on the generated molecules are reported. Property scores for each data-set are reported as well.