Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper presents new graph generative model (GRAM) which claims to tackle the scalability issue found is most of the published models. The propose architecture can scale on graphs from three perspective - number of graphs, number of nodes/edges and number of node/edge labels. This is achieved by sequentially generating the subgraph using graph attention and graph convolutional layers. While training, each of these subgraph can be trained in parallel. Further, paper applies couple of heuristics to reduce computational time and introduces a new non-domain specific evaluation metric for the generation of node/edge labeled graphs. 

Although the paper claims to propose simplified mechanism, I find the generation task to be relatively very complex in comparison to GraphRNN and GRAN (published at NeurIPS'19). As mentioned below, the use of certain module seems ad-hoc. Further, the results on the new metric is at times inconsistent with other prior metrics. In lieu of this, currently the paper leans towards rejection. I would be happy to improve my score if some of the below-mentioned concerns are addressed.

Clarification:
1. What is the unit for time in Table 1 ? Is it inference time or training time ?
2. In my experience, the change in quantitative number do not necessarily reflect improvement in qualitative output. The metric GK is inconsistent. For example, on grid - GraphRNN is better on three metrics while GRAM gives the best results on GK. On community, there is a wide discrepancies between GraphRNN and GraphRNN-S model for most metrics but for GK.
3. Can you guide me on qualitative results of community and B-A graphs data ? Currently, nothing could be interpreted from these plots. Moreover, why the training set of community graph fails to show 4 commnities ? May be you should modify the data generation process.

Concern and Additional Experiments:
1. Please use standard Grid graph dataset as used in the literature - max |V| = 361. Moreover, I was wondering how do one generate 500 grid graphs with just max 100 nodes ? Since these graphs are not random.
2. Node scalability - GRAM has been employed only on graphs of maximum size 500 nodes. This does not confirm scalability. The advantage of parallel training of GRAM as against sequential GraphRNN should be showcased on large graphs of atleast 5000 nodes. 
3. Please include results on newer models pub lished at NeurIPS'2019 - Graph Recurrent Attention Network (GRAN) and Graph Normalizing flows (GNF).
4. No one model among GRAM is projecting out to be best. On couple of data, GRAM is best, while on others GRAM-A or GRAM-B is better.
5. During inference, GRAM needs to compute the shortest path length among different nodes. This will surely not scale up with increasing nodes. Moreover, from Table 6 it is inconclusive whether that bias term is useful. How does the results look if both the biases are removed ?
6. I note that each input node vector stacks degree and clustering coefficient information. How one obtains this information during inference ? Yet again, it will face scalability issue as above. 
7. The above concern also highlight the fact that the statistics of measured metrics (degree and clustering coefficients) are utilized during training. It seems more like a hack to me. No wonder this leads to performance boost of GRAM. Please share ablation study on this.
8. Please explain how Graph convolutional complements the processing in graph attention. Is both required ? Can you share ablation study on this ?

Minor:
1. The models categorized as unsupervised indeed trains using supervision of edge connectivity. 
2. Frist -> First
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: This paper presents a formulation of graph generative models based on graph attention aimed at scalability of these methods.

The paper is generally written well and I like the overall theme of the paper, however, there are a few key issues with this work and I don't think the paper as it stands is ready for publication:

1) The main motivation expressed in the paper is that graph generative models are generally not scalable and they identify three main areas: (a) graph size (i.e. num nodes); (b) data scalability (i.e. num training samples); (c) label scalability (i.e. num of node or edge types). However, the paper doesn't follow on why the proposed method actually addresses these issues. The derivation doesn't talk about scale until we reach section 3.5 and then we find out that actually the proposed model is O(n^3) in reality. Then there are approximations to make it scale. So for me there is a massive disconnect between the main motivation of the paper and the suggested model. Why not study approximation methods for already existing graph generator models?

2) Following on the theme of scale, the only experimental result discussing this is the time column reported for the training time. So that partially addresses the data scalability. Other baselines as well have reasonable training times specially when it comes to large datasets (e.g. ZINC is that the largest dataset studied with 250K samples and GraphRNN is 2x slower and GraphRNN-S only about 20%). What I was looking for was when you really can train on real-world datasets that other methods basically can't be trained. The datasets chosen all are small hence there's not much issue with scale there. The question about the scalability w.r.t. other aspects (i.e. num nodes and num labels) has not been studied or reported.

3) The approximations suggested in section 3.5 also don't seem to have much impact on the training time. These approximations were motivated by the scale while looking at the training times they barely make any difference. However, they make a big difference in performance metrics specially in smaller datasets. So the question that comes to mind is that what is the role of these approximations w.r.t. the quality of the models? Again this question needs further study.

4) Comparing GraphRNN and GraphRNN-S's modifications with the results from the original paper, it seems they are performing much worse (e.g. deg for the original GraphRNN-S is 0.057 while the reported num here is 0.523 for Protein dataset). The same is true for other metrics. Why is that?

5) As pointed out by an observer, it seems that there are nuances to generation of the graph needing seeds of arbitrary size to be provided, explained deep down in the appendix. If this is the case for generation then it should be discussed in the main part of the paper and contrasted with methods that can start from scratch.

6) In the training configuration part of the appendix, A.7.2 it seems there are discrepancies in number of GPUs as well kinds of GPUs used for each method. When reporting training times in the main section, do you normalise against these?

7) It seems that many hyperparameters mentioned in A.7.2 are chosen in an ad-hoc manner without proper model selection and seem to vary across each different versions of GRAM for each different dataset. How sensitive is the model to these hyperparameters? I suspect if the model was insensitive, you could've fixed them for many of these experiments, but seems that is not the case. So without proper model selection routines, the results may not be representative of what the model discussed.

Minor comment: The model suggested has some similarities to DEFactor model from Assouel et al 2019 in terms of formulation of the problem for labelled graphs (nodes as a matrix and adj as a tensor), though the underlying models are very different, that paper as well targets arbitrary size graph generation and efficiency w.r.t. model parameters.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: # Response to rebuttal

I would like to thank their authors for their rebuttal.

After reading the other reviews, the author response and the revised manuscript, I have decided to keep my score of weak reject for the time being.

In short, while I appreciate the effort the authors put in partly addressing some of the most important comments raised during the review process, I think the paper would greatly benefit from some additional work. In particular:

(1) Given the emphasis on scalability, I still believe the authors should carry out more thorough experiments to characterize the runtime of their approach with respect to different characteristics of the graphs. While the result provided in the response to Reviewer #3 is a first step, I recommend the authors to extend it by (1) varying graph size (in terms of nodes and edges); (2) varying graph type and (3) reporting the speedup with respect to other baselines.

(2) To the best of my knowledge, the ablation experiment in Section A.7.4 does not provide results for the setting in which no graph attention mechanism is used at all, neither for the case where the graph attention mechanism used is identical to GAT (restricted to 1-step neighbourhoods).

(3) While NSPDK might be a reasonable choice, I still am of the opinion that the choice of graph kernel for this purpose is highly arbitrary and, thus, should be investigated further. Given that such a choice is being used to define a performance metric, which moreover is being highlighted as a contribution, the authors should study the robustness of the metric to the choice of graph kernel, as well as its sensitivity to known perturbations.

(4) Finally, I did not see any error bars added to the main results in the paper.

Despite these shortcomings, I would like to reiterate that I believe the proposed approach is promising and, with some additional work, would be a contribution definitely worth publishing. Therefore, I would like to encourage the authors to further revise the manuscript.

# Summary

In this paper, the authors propose an auto-regressive deep generative model for graph-structured data, motivated by the goal of scalability with respect to graph size, graph density and sample size.

In a nutshell, the approach follows closely the ideas in [1, 2], which model graph generation as an auto-regressive process after fixing or sampling an ordering for the nodes. Unlike [1, 2], however, the proposed method makes use of graph convolutions and a graph attention mechanism, closely related to GAT [3], to parametrize the conditional distributions of node/edges given the previously generated graph elements.

The performance of the proposed approach is evaluated in comparison to [1, 2] in several synthetic and real-world datasets, using MMD [4] between generated and held-out test graphs as metric. Unlike [2], which applies MMD on three graph statistics (degree, clustering coefficient and average orbit counts), this manuscript proposes to evaluate MMD using a graph kernel as well [5].

# High-level assessment

The main contribution in this paper is to combine a graph attention mechanism, which can be seen  as a simplification of GAT [3], with deep autoregressive graph models, such as DeepGMG [1] or GraphRNN [2]. In this way, the manuscript has a large conceptual overlap with the method in [6], which can be nevertheless be regarded as concurrent rather than prior work. From a methodological perspective, I believe the contribution is sound and sufficiently novel, although perhaps slightly on the incremental side. 

However, the current version of the manuscript has shortcomings regarding (i) lack of clarity in the exposition of the method’s relation to prior work, low-level implementation details and experimental setup and (ii) insufficient experimental results to back up some of the authors’ claims.

Nonetheless, I believe the proposed approach is promising, and encourage the authors to address or clarify these issues during the author discussion phase.

# Major points / suggestions

1. The manuscript presents the proposed approach in a way that does not clearly differentiate between prior work and original contributions.

In particular, I believe that the ideas in Section 3.1 and 3.2 are almost identical to those in [1, 2], the graph attention mechanism in Section 3.3 can be seen as a minor modification of GAT [3], and Section 3.4 also has a strong conceptual overlap with [1, 2].

I would encourage the authors to be more clear with respect to what is novel and what is borrowed from prior work. Moreover, when slightly departing from prior work (e.g. the modifications applied to the graph attention mechanism in Section 3), I would also encourage the authors to focus on explaining what specifically has changed and what is the rationale behind those design choices, rather than explaining the entire mechanism “from scratch”, leaving up to the reader to figure out what is novel.

2. The paper’s clarity could be improved, with some parts presented in an unnecessarily complicated manner (e.g. the graph attention mechanism) and others without sufficient detail (e.g. the edge estimator module, the zero-ing heuristic for attention or the generation of graphs based on “seed graphs”, which is only mentioned in the appendix).

For example, regarding the graph attention mechanism, I would recommend: (i) explaining more clearly what the “feature vector of node $v_{i}$” is exactly in relation to the notation of Section 3.1; (ii) if the query, key and value matrices are identical, as the text seems to imply, I would rewrite the equations directly in terms of $X$ which would simplify the notation significantly; (iii) perhaps most importantly, the bias functions $b^{Q}$, $b^{K}$ and $b^{V}$ should be defined mathematically and discussed in greater detail and (iv) the output FNN should also be described mathematically. Finally, as mentioned above, I would emphasise the differences between the proposed attention mechanism and GAT.

The edge estimator mechanism is described too imprecisely in Section 3.4.4. While Section A.4 definitely helps, I would recommend defining the entire operation mathematically in Section 3.4.4 as well. Likewise, a precise mathematical definition of GRAM-A in Section 3.5.2 would also be helpful.

Finally, as mentioned in this forum by Prof. Ranu prior to this review’s writing, the graph generation procedure described in Section A.7.2 seems unconventional. I would encourage the authors to both clarify what they mean by “for the convenience of implementation” and to investigate whether the experimental conclusions are affected by this departure from prior practices.

3. Key details about the experimental setup, such as the hyperparameter selection protocol for the proposed approach and baselines, as well as the resulting architectures, seems to be missing, making it difficult to assess if the experimental setup is “fair”. 

In particular, all methods should be allowed to use a similar number of parameters or, alternatively, have their hyperparameters tuned equally carefully for each dataset separately.

4. Most importantly, I believe the experimental results are insufficient to back up some of the claims made in the introduction. 

    4.1. Despite the focus on scalability throughout the motivation, there are no experiments systematically exploring how the runtime at train and test time of the proposed approach and the main baselines scales with respect to sample size, number of nodes per graph and graph density. Moreover, no results are provided for large graphs (e.g. ~5k nodes as in [6]). 

    4.2. The graph attention mechanism was claimed to be an original contribution. However, no results are provided to evaluate its advantages with respect to the different GAT variants nor ablation studies to see its usefulness relative to a variant of the proposed approach using only graph convolutions.

    4.3 The idea of using MMD in conjunction with graph kernels as a performance metric is interesting. However, there is no investigation of key aspects such as (i) its relation to other metrics and (ii) the impact that the choice of graph kernel, among the many available, and/or of graph kernel hyperparameters has on the resulting metric (see [7] for a comprehensive review on graph kernels).

   4.4. Finally, the results have been reported without error bars, making it difficult to quantify the statistical significance of the observed performance differences between approaches.

# Minor points / suggestions

1. I strongly believe the authors should adapt the manuscript to mention [6] and related/concurrent work. Ideally, including it as an additional baseline would be even better, but not necessary given the limited rebuttal time. Nevertheless, this point was not taken into consideration when scoring the manuscript, given how recent [6] is.

# References

[1] Li, Yujia, et al. "Learning deep generative models of graphs." *International Conference on Machine Learning.* 2018.
[2] You, Jiaxuan, et al. "Graphrnn: Generating realistic graphs with deep auto-regressive models." *International Conference on Machine Learning.* 2018.
[3] Veličković, Petar, et al. "Graph attention networks." *International Conference on Learning Representations*. 2018.
[4] Gretton, Arthur, et al. "A kernel method for the two-sample-problem." Advances in Neural Information Processing Systems. 2007.
[5] Costa, Fabrizio, and Kurt De Grave. "Fast neighborhood subgraph pairwise distance kernel." Proceedings of the 26th International Conference on Machine Learning. Omnipress; Madison, WI, USA, 2010.
[6] Liao, Renjie, et al. "Efficient Graph Generation with Graph Recurrent Attention Networks." *Advances in Neural Information Processing Systems.* 2019.
[7] Kriege, Nils M., Fredrik D. Johansson, and Christopher Morris. "A Survey on Graph Kernels." *arXiv preprint arXiv:1903.11835* (2019).
review_title: Official Blind Review #1

Meta-review: The paper proposed an efficient way of generating graphs.  Although the paper claims to propose simplified mechanism, the reviewers find that the generation task to be relatively very complex, and the use of certain module seems ad-hoc. Furthermore, the results on the new metric is at times inconsistent with other prior metrics. The paper can be improved by addressing those concerns concerns. 
Decision: Reject