Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

review_title: Interesting topic, but paper isn't ready yet

final_score: rating: 7: Good paper, accept
review_content: This work proposed an interesting graph generator using a variational autoencoder. The work should be interesting to researchers in the various areas. However, the work can only work on small graphs. The search space of small graph generation is usually very small, is there any other traditional methods can work on this problem? Moreover, the notations are a little confusing.  
review_title: An interesting Graph Generator

final_score: rating: 7: Good paper, accept
review_content: The authors propose a variational auto encoder architecture to generate graphs.  

Pros:
- the formulation of the problem as the modeling of a probabilistic graph is of interest 
- some of the main issues with graph generation are acknowledged (e.g. the problem of invariance to node permutation) and a solution is proposed (the binary assignment  matrix)
- notions for measuring the quality of the output graphs are of interest: here the authors propose some ways to use domain knowledge to check simple properties of molecular graphs 

Cons: 
- the work is quite preliminary
- many crucial elements  in graph generation are not dealt with: 
 a) the adjacency matrix and the label tensors are not independent of each other, the notion of a graph is in itself a way to represent the 'relational links' between the various components
 b) the boundaries between a feasible and an infeasible graph are sharp: one edge or one label can be sufficient for acting the transition independently of the graph size, this makes it a difficult task for a continuous model. The authors acknowledge this but do not offer ways to tackle the issue
 c) conditioning on the label histogram should make the problem easy: one is giving away the number of nodes and the label identities after all; however even in this setup the approach fails more often than not 
 d) the graph matching procedure proposed is a rough patch for a much deeper problem
- the evaluation should include a measure of the capacity of the architecture to :
 a) reconstruct perfectly the input
 b) denoise perturbations over node labels and additional/missing  edges  
review_title: interesting step in generative ANN architectures  for graphs 

Meta-review: The authors present GraphVAE, a method for fitting a generative deep model, a variational autoencoder, to small graphs.  Fitting deep learning models to graphs remains challenging (although there is relevant literature as brought up by the reviewers and anonymous comments) and this paper is a strong start.

In weighing the various reviews, AnonReviewer3 is weighed more highly than AnonReviewer1 and AnonReviewer2 since that review is far more thorough and the reviewer is more expert on this subject.  Unfortunately, the review from AnonReviewer1 is extremely short and of very low confidence.  As such, this paper sits just below the borderline for acceptance.  In general, the main criticisms of the paper are that some claims are too strong (e.g. non-differentiability of discrete structures), treatment of related work (missing references, etc.) and weak experiments and baselines.  The consensus among the reviews (even AnonReviewer2) is that the paper is preliminary.  The paper is close, however, and addressing these concerns will make the paper much stronger.

Pros:
- Proposes a method to build a generative deep model of graphs
- Addresses a timely and interesting topic in deep learning
- Exposition is clear

Cons:
- Treatment of related literature should be improved
- Experiments and baselines are somewhat weak
- "Preliminary"
- Only works on rather small graphs (i.e. O(k^4) for graphs with k nodes)
Decision: Reject