Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper introduces a generative model for graphs. The three main decision functions in the sequential process are computed with neural nets. The neural nets also compute node embeddings and graph embeddings and the embeddings of the current graph are used to compute the decisions at time step T. The paper is well written but, in my opinion, a description of the learning framework should be given in the paper. Also, a summary of the hyperparameters used in the proposed system should be given. It is claimed that all possible types of graphs can be learned which seems rather optimistic. For instance, when learning trees, the system is tweaked for generating trees. Also, it is not clear whether models for large graphs can be learned. The paper contain many interesting contributions but, in my opinion, the model is too general and the focus should be given on some retricted classes of graphs. Therefore, I am not convinced that the paper is ready for publication at ICLR'18.

* Introduction. I am not convinced by the discussion on graph grammars in the second paragraph. It is known that there does not exist a definition of regular grammars in graph (see Courcelle and Engelfriet, graph structure and monadic second-order logic ...). Moreover, many problems are known to be undecidable. For weighted automata, the reference Droste and Gastin considers weighted word automata and weighted logic for words. Therefore I does not seem pertinent here. A more complete reference is "handbook of weighted automata" by Droste. Also, many decision problems for wighted automata are known to be undecidable. I am not sure that the paragraph is useful for the paper. A discussion on learning as in footnote 1 shoud me more interesting.
* Related work. I am not expert in the field but I think that there are recent references which could be cited for probablistic models of graphs.
* Section 3.1. Constraints can be introduced to impose structural properties of the generated graphs. This leads to the question of cheating in the learning process.
* Section 3.2. The functions f_m and g_m for defining graph embedding are left undefined. As the graph embedding is used in the generating process and for learning, the functions must be defined and their choice explained and justified.
* Section 3. As said before, a general description of the learning framework should be given. Also, it is not clear to me how the node and graph embeddings are initialized and how they evolve along the learning process. Therefore, it is not clear to me why the proposed updating framework for the embeddings allow to generate decision functions adapted to the graphs to be learned.  Consequently, it is difficult to see the influence of T. Also, it should be said whether the node embeddings and graph embeddings for the output graph can be useful.
* Section 3. A summary of all the hyperparameters should be given.
* Section 4.1. The number of steps is not given. Do you present the same graph multiple times. Why T=2 and not 1 or 10 ?
* Section 4.2. From table 2, it seems that all permutations are used for training which is rather large for molecules of size 20. Do you use tweaks in the generation process.
* Section 4.3. The generation process is adapted for generating trees which seems to be cheating. Again the choice of T seems ad hoc and based on computational burden.
* Section 5 should contain a discussion on complexity issues because it is not clear how the model can learn large graphs.
* Section 5. The discussion on the difficulty of training shoud be emphasized and connected to the --missing-- description of the model architecture and its hyperparameters.
* acronyms should be expansed at their first use
review_title: Learning deep generative models for graphs

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors introduce a sequential/recurrent model for generation of small graphs. The recurrent model takes the form of a graph neural network. Similar to RNN language models, new symbols (nodes/edges) are sampled from Bernoulli or categorical distributions which are parameterized by small fully-connected neural networks conditioned on the last recurrent hidden state. 

The paper is very well written, nicely structured, provides extensive experimental evaluation, and examines an important problem that has so far not received much attention in the field.

The proposed model has several interesting novelties (mainly in terms of new applications/experiments, and being fully auto-regressive), yet also shares many similarities with the generative component of the model introduced in [1] (not cited): Both models make use of (recurrent) graph neural networks to learn intermediate node representations, from which they predict whether new nodes/edges should be added or not. [1] speeds this process up by predicting multiple nodes and edges at once, whereas in this paper, such a multi-step process is left for future work. Training the generative model with fixed ground-truth ordering was similarly performed in [1] (“strong supervision”) and is thus not particularly novel.

Eqs.1-3: Why use recurrent formulation in both the graph propagation model and in the auto-regressive main loop (h_v -> h_v’)? Have the authors experimented with other variants (dropping the weight sharing in either or both of these steps)?

Ordering problem: A solution for the ordering problem was proposed in [2]: learning a matching function between the orderings of model output and ground truth. A short discussion of this result would make the paper stronger.

For chemical molecule generation, a direct comparison to some more recent work (e.g. the generator of the grammar VAE [3]) would be insightful.

Other minor points:
- In the definition of f_nodes: What is p(y)? It would be good to explicitly state that (boldface) s is a vector of scores s_u (or score vectors, in case of multiple edge types) for all u in V.  
- The following statement is unclear to me: “but building a varying set of objects is challenging in the first place, and the graph model provides a way to do it.” Maybe this can be substantiated by experimental results (e.g. a comparison against Pointer Networks [4])?
- Typos in this sentence: “Lastly, when compared using the genaric graph generation decision sequence, the Graph architecture outperforms LSTM in NLL as well.”

Overall I feel that this paper can be accepted with some revisions (as discussed above), as, even though it shares many similarities with previous work on a very related problem, it is well-written, well-presented and addresses an important problem.

[1] D.D. Johnson, Learning Graphical State Transitions, ICLR 2017
[2] R. Stewart, M. Andriluka, and A. Y. Ng, End-to-End People Detection in Crowded Scenes, CVPR 2016
[3] M.J. Kusner, B. Paige, J.M. Hernandez-Lobato, Grammar Variational Autoencoder, ICML 2017
[4] O. Vinyals, M. Fortunato, N. Jaitly, Pointer Networks, NIPS 2015
review_title: Revisiting auto-regressive models for graph generation

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors proposed a graph neural network based architecture for learning generative models of graphs. Compared with traditional learners such as LSTM, the model is better at capturing graph structures and provides a flexible solution for training with arbitrary graph data. The representation is clear with detailed empirical studies. I support its acceptance.

The draft does need some improvements and here is my suggestions.
1. Figure 1 could be improved using a concrete example like in Figure 6. If space allowed, an example of different ordering leads to the same graph will also help.

2. More details on how node embedding vectors are initialized. How does different initializations affect results? Why is nodes at different stages with the same initialization problematic?

3. More details of how conditioning information is used, especially for the attention mechanism used later in parse tree generation.

4. The sequence ordering is important. While the draft avoids the issue theoretically, it does has interesting results in molecule generation experiment. I suggest the authors at least discuss the empirical over-fitting problem with respect to ordering.

5. In Section 4.1, the choice of ER random graph as a baseline is too simplistic. It does not provide a meaningful comparison. A better generative model for cycles and trees could help.

6. When comparing training curves with LSTM, it might be helpful to also include the complexity comparison of each iteration.
review_title: A promising generative model for graphs

Meta-review: Predicting graphs is an interesting and important direction, and there exist essentially no (effective) general-purpose techniques for this problem.  The idea of predicting nodes one by one, though not entirely surprising, is interesting and the approach makes sense. Unfortunately, I (and some of reviewers) less convinced by evaluation:

-  For example, evaluation on syntactic parsing of natural language is very weak. First of all, the used metric -- perplexity and exact match are non-standard and problematic (e.g., optimizing exact match would largely correspond to ignoring longer sentences where predicting the entire tree is unrealistic).  Also the exact match scores are very low (~30% whereas 45+ were achieve by models back in 2010).

- A reviewer had, I believe, valid concerns about comparison with GrammarVAE, which were not fully addressed.

Overall, I believe that it is interesting work, which regretfully cannot be published as a conference paper in its current form.

+ important / under-explored problem
+ a reasonable (though maybe not entirely surprising / original) approach
- issues with evaluation


Decision: Invite to Workshop Track