Deep learning on graphs has become a popular research topic with many applications. However, past work has concentrated on learning graph embedding tasks only, which is in contrast with advances in generative models for images and text. Is it possible to transfer this progress to the domain of graphs? We propose to sidestep hurdles associated with linearization of such discrete structures by having a decoder output a probabilistic fully-connected graph of a predefined maximum size directly at once. Our method is formulated as a variational autoencoder. We evaluate on the challenging task of conditional molecule generation.
This paper studies the problem of learning to generate graphs using deep learning methods. The main challenges of generating graphs as opposed to text or images are said to be the following:
(a) Graphs are discrete structures, and incrementally constructing them would lead to non-differentiability (I don't agree with this; see below)
(b) It's not clear how to linearize the construction of graphs due to their symmetries. Based on this motivation, the paper decides to generate a graph in "one shot", directly  outputting node and edge existence probabilities, and node attribute vectors.
A graph is represented by a soft adjacency matrix A (entries are probability of existence of an edge), an edge attribute tensor E (entries are probability of each edge being one of d_e discrete types), and a node attribute matrix F, which has a node vector for each  potential node. A cross entropy loss is developed to measure the loss between generated A, E, and F and corresponding targets.
The main issue with training models in this formulation is the alignment of the generated graph to the ground truth graph. To handle this, the paper proposes to use a simple graph  matching algorithm (Max Pooling Matching) to align nodes and edges. A downside to the algorithm is that it has complexity O(k^4) for graphs with k nodes, but the authors argue that this is not a problem when generating small graphs. Once the best correspondence is found, it is treated as constant and gradients are propagated appropriately.
Experimentally, generative models of chemical graphs are trained on two datasets. Qualitative results and ELBO values are reported as the dimensionality of the embeddings is varied. No baseline results are presented. A further small set of experiments evaluates the quality of the matching algorithm on a synthetic setup.
Strengths:
- Generating graphs is an interesting problem, and the proposed approach seems like an easy-to-implement, mostly reasonable way of approaching the problem.
- The exposition is clear (although a bit more detail on MPM matching would be appreciated)
However, there are some significant weaknesses. First, the motivation for one-shot graph construction is not very strong:
- I don't understand why the non-differentiability argued in (a) above is an issue. If training uses a maximum likelihood objective, then we should be able to decompose the generation of a graph into a sequence of decisions and maximize the sum of the logprobs of the conditionals. People do this all the time with sequence data and non-differentiability is not an issue.
- I also don't agree that the one shot graph construction sidesteps the issue of how to linearize the construction of a graph. Even after doing so, the authors need to solve a matching problem to resolve the alignment issue. I see this as equivalent to choosing an order in which to linearize the order of nodes and edges in the graph.
Second, the experiments are quite weak. No baselines are presented to back up the claims motivating the formulation. I don't know how to interpret whether the results are good or bad. I would have at least liked to see a comparison to a method that generated SMILES format in an autoregressive manner (similar to previous work on chemical graph generation), and would ideally have liked to see an attempt at solving the alignment problem within an autoregressive formulation (e.g., by greedily constructing the alignment as the graph was generated). If one is willing to spend O(k^4) computation to solve the alignment problem, then there seem like many possibilities that could be easily applied to the autoregressive formulation. The authors might also be interested in a concurrent ICLR submission that approaches the problem from an autoregressive angle (https://openreview.net/pdf?id=Hy1d-ebAb). 
Finally, I would have expected to see a discussion and comparison to "Learning Graphical State Transitions" (Johnson, 2017). Please also don't make statements like "To the best of our knowledge, we are the first to address graph generation using deep learning." This is very clearly not true. Even disregarding Johnson (2017), which the authors claim to be unaware of, I would consider approaches that generate SMILES format (like Gomez-Bombarelli et al) to be doing graph generation using deep learning.
Overall, the paper is about an interesting subject, but in my opinion the execution isn't strong enough to warrant publication at this point.