Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors proposed a generative model of random walks on graphs. Using GAN, the architecture allows for model-agnostic learning, controllable fitting, ensemble graph generation. It also produces meaningful node embeddings with semi-interpretable latent spaces. The overall framework could be relevant to multiple areas in graph analytics, including graph comparison, graph sampling, graph embedding and relational feature selection. The draft is well written with convincing experiments. I support the acceptances of this paper.

I do have a few questions that might help further improve the draft. More baseline besides DC-SBM could better illustrate the power of GAN in learning longer random walk trajectories. DC-SBM, while a generative model, inherently can only capture first order random walks with target degree biases, and generally over-fits into degree sequences. Are there existing generative models based on walk paths?

The choice of early stopping is a very interesting problem especially for the EO-creitenrion. In Fig3 (b), it seems assortativity is over-fitted beyond 40k iterations. It might be helpful to discuss more about the over-fitting of different graph properties.

The node classification experiment could use a bit more refinement. The curves in Fig. 5(a) are not well explained. What is the "combined"? The claim of competitive performance needs better justification according to the presentation of the F1 scores.

The Latent variable interpolation experiment could also use more explanations. How is the 2d subspace chosen? What is the intuition behind the random walks and graphs of Fig 6? Can you provide visualizations of the communities of the interpolated graphs in Fig 7? 
review_title: A pioneering work with great potential

final_score: rating: 6: Marginally above acceptance threshold
review_content: I am overall positive about the work but I would like to see some questions addressed. 

Quality: The paper is good but does not address some important issues. The paper proposes a GAN model to generate graphs with non-trivial properties. This is possibly one of the best papers on graph generation using GANs currently in the literature. However, there are a number of statistical issues that should be addressed. I fear the paper is not ready yet, but I am not opposed to publication as long as there are warnings in the paper about the shortcomings.

Originality: This is an original approach. Random walks sometimes are overused in the graph literature, but they seem justified in this work. But it also requires extra work to ensure they are generating meaningful graphs.

Significance: The problem is important. Learn to generate graphs is a key task in drug discovery, relational learning, and knowledge discovery.

Evaluation: The link prediction task is too easy, as links are missing at random. It would be more useful to predict links that are removed with an unknown bias. The graph (wedge, claw, etc) characteristics are good (but simple) metrics; however, it is unclear how a random graph with the same size and degree distribution (configuration model) would generate for the same metrics (it is not shown for comparison). 

Issues that I wish were addressed in the paper: 
a)	How is the method learning a generator from a single graph? What are the conditions under which the method is likely to perform well? It seems to rely on some mixing RW conditions to model the distinct graph communities. What are these mixing conditions? These are important questions that should have at least an empirical exploration.
b)	What is the spatial independence assumption needed for such a generator? 
c)	Would this approach be able to generate a lattice? Would it be able to generate an expander graph? What about a graph with poorly connect communities? Is there any difficulties with power law graphs? 
d)	How is the RW statistically addressing the generation of high-order (subgraph) features?
e)	Can this approach be used with multiple i.i.d. graphs? 
f)	Isn’t learning the random walk sample path a much harder / higher-dimensional task than it is necessary? Again, the short walk may be capturing the communities but the high-dimensional random walk sample path seems like a high price to pay to learn community structure.
g)	Clearly, with a large T (number of RW steps), the RW is not modeling just a single community. Is there a way to choose T? How larger values of T to better model inter-community links? Would different communities have different choices of T? 
h)	And a related question, how well can the method generate the inter-community links?
i)	The RW model is actually similar to an HMM. Would learning a mixture of HMMs (one per community) have similar performance?

review_title: Positive about manuscript but it needs improvement

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a WGAN formulation for generating graphs based on random walks. The proposed generator model combines node embeddings, with an LSTM architecture for modeling the sequence of nodes visited in a random walk; the discriminator distinguishes real from fake walks.

The model is learned from a single large input graph (for three real-world networks) and evaluated against one baseline generative graph model: degree-corrected stochastic block models. 

The primary claims of the paper are as follows:
i) The proposed approach is a generative model of graphs, specifically producing "sibling" graphs
ii) The learned latent representation provides an interpretation of generated graph properties
iii) The model generalizes well in terms of link and node classification

The proposed method is novel and the incorporated ideas are quite interesting (e.g., discriminating real from fake random walks, generating random walks from node embeddings and LSTMs). However, from a graph generation perspective, the problem formulation and evaluation do not sufficiently demonstrate the utility of proposed method. 

First, wrt claim (i) the problem of generating "sibling" graphs is ill-posed. Statistical graph models are typically designed to generate a probability distribution over all graphs with N nodes and, as such, are evaluated based on how well they model that distribution. The notion of a "sibling" graph used in this paper is not clearly defined, but it seems to only be useful if the sibling graphs are likely under the distribution. Unfortunately, the likelihood of the sampled graphs is not explicitly evaluated. On the other hand, since many of the edges are shared the "siblings" may be nearly isomorphic to the input graph, which is not useful from a graph modeling perspective. 

For claim (i), the comparison to related work is far from sufficient to demonstrate its utility as a graph generation model. There are many graph models that are superior to DC-SBM, including KPGMs, BETR, ERGMs, hierarchical random graph models and latent space models. Moreover, a very simple baseline to assess the LSTM component of the model, would be to produce a graph by sampling links repeatedly from the latent space of node embeddings. 

Next, the evaluation wrt to claim (ii) is novel and may help developers understand the model characteristics. However, since the properties are measured based on a set of random walks it is still difficult to interpret the impact on the generated graphs (since an arbitrary node in the final graph will have some structure determined from each of the regions). Do the various regions generate different parts of the final graph structure (i.e., focusing on only a subset of the nodes)?   

Lastly, the authors evaluate the learned model on link and node prediction tasks and state that the model's so-so performance supports the claim that the model can generalize. This is the weakest claim of the paper. The learned node embeddings appear to do significantly worse than node2vec, and the full model is worse than DC-SBM. Given that the proposed model is transductive (when there is significant edge overlap) it should do far better than DC-SBM which is inductive. 

Overall, while the paper includes a wide range of experimental evaluation, they are aimed too broadly (and the results are too weak) to support any specific claim of the work. If the goal is to generate transductively (with many similar edges), then it would be better to compare more extensively to alternative node embedding and matrix factorization approaches, and assess the utility of the various modeling choices (e.g., LSTM, in/out embedding). If the goal is to generate inductively, over the full distribution of graphs, then it would be better to (i) assess whether the sampled graphs are isomorphic, and (ii) compare more extensively to alternative graph models (many of which have been published since 2010).  

review_title: Claims and evaluation need some work

Meta-review: This paper proposes an implicit model of graphs, trained adversarially using the Gumbel-softmax trick.  The main idea of feeding random walks to the discriminator is interesting and novel.  However,
1) The task of generating 'sibling graphs', for some sort of bootstrap analysis, isn't well-motivated.
2) The method is complicated and presumably hard to tune, with two separate early-stopping thresholds that need to be tuned
3) There is not even a mention of a large existing literature on generative models of graphs using variational autoencoders.
Decision: Reject