Scalable Generative Models for Graphs with Graph Attention Mechanism
Authors: Wataru Kawai
Yusuke Mukuta
Tatsuya Harada
Venue:  (2020)
Keywords: Graph Generative Model
Attention Mechanism

Abstract: Graphs are ubiquitous real-world data structures, and generative models that approximate distributions over graphs and derive new samples from them have significant importance. Among the known challenges in graph generation tasks, scalability handling of large graphs and datasets is one of the most important for practical applications. Recently, an increasing number of graph generative models have been proposed and have demonstrated impressive results. However, scalability is still an unresolved problem due to the complex generation process or difficulty in training parallelization. 
In this paper, we first define scalability from three different perspectives: number of nodes, data, and node/edge labels. Then, we propose GRAM, a generative model for graphs that is scalable in all three contexts, especially in training. We aim to achieve scalability by employing a novel graph attention mechanism, formulating the likelihood of graphs in a simple and general manner. Also, we apply two techniques to reduce computational complexity. Furthermore, we construct a unified and non-domain-specific evaluation metric in node/edge-labeled graph generation tasks by combining a graph kernel and Maximum Mean Discrepancy. Our experiments on synthetic and real-world graphs demonstrated the scalability of our models and their superior performance compared with baseline methods.

Under review as a conference paper at ICLR 2020
SCALABLE GENERATIVE MODELS FOR GRAPHS WITH GRAPH ATTENTION MECHANISM
Anonymous authors Paper under double-blind review
ABSTRACT
Graphs are ubiquitous real-world data structures, and generative models that ap- proximate distributions over graphs and derive new samples from them have sig- nificant importance. Among the known challenges in graph generation tasks, scal- ability handling of large graphs and datasets is one of the most important for prac- tical applications. Recently, have been proposed and have demonstrated impressive results. However, scal- ability is still an unresolved problem due to the complex generation process difficulty in training parallelization. In this paper, we first define scalability from three different perspectives: number of nodes, data, and node/edge labels. Then, we propose GRAM, a generative model for graphs that is scalable in all three con- texts, especially in training. We aim achieve scalability by employing a novel graph attention mechanism, formulating the likelihood of graphs in a simple and general manner. Also, we apply two techniques reduce computational com- plexity. Furthermore, we construct a unified and www-ddoma--sscciiee evaluation metric in node/edge-labeles graph generation tasks by combining a graph kernel and Maximum Mean Discrepancy. Our experiments synthetic and real-world graphs demonstrated the scalability of our models and their superior performance compared with baseline methods.
increasing number of graph generative models
INTRODUCTION
Graphs are ubiquitous and fundamental data structures in the real world, appearing in various fields, such as social science, chemistry, and biology. Moreover, in applications such as drug discovery and network simulation, graph generative models that can approximate distributions over graphs on a specific domain and derive new samples from them are very important. Compared with generation tasks for images or natural language, graph generation tasks significantly more difficult; this is due to the necessity of modeling complex local/global dependencies among nodes and edges as well as the intractable properties of graphs themselves, such as discreteness, variable number of nodes and edges, and uncertainty of node ordering.
Among the several challenges involved in graph generation tasks described ahove, scalability is one of the most important for applications in a wide range of real-world domains. In this paper, we define scalability from three perspectives: graph scalability, data scalability, and label scalability. Graph scalability denotes scalability to large graphs with many nodes within the limit of practical time/space complexity, especially in training. Data scalability denotes scalability large datasets containing many data. Label scalability denotes scalability to graphs with many node/edge labels. Besides these, is possible the total number of nodes in a dataset. However, because these are closely related to the above three defined perspectives, we consider them as mutually exclusive and collectively exhaustive division.
consider other viewpoints, such edge number, graph diameter, and
In recent years, an increasing number of graph generative models based on machine learning have been proposed. They have demonstrated great performances in several tasks, such as link pre- diction, molecular property optimization, and network structure optimization (Li et al.) 2018 You Grover et al. [2018] Luo et al. 2018 You et al. 2018a Liu et al. 2018 Simonovsky & pro- posed model is scalable in all three contexts. For example, DeepGMG (Li et al. 2018) can generate only small graphs, and GraphRNN (You et al. 20T8b) cannot consider node/edge labels. Besides,
ett al. 2018b
Komodakis 2018 Wang et al. 2017
al. 2018). However, to the best of our knowledge,

---

Under review as a conference paper at ICLR 2020
both models have weak compatibility with parallel training, which is key to efficient training large dataset.
In this work, we propose the Graph Generative Model with Graph Attention Mechanism (GRAM) for generating graphs that is scalable in all three contexts, especially during training. Given a set of graphs, our model approximates their distribution in an unsupervised manner. To achieve graph scal- ability, we employ an autoregressive sequential generation process that is flexible to variable nodes and edges, and formulate the likelihood of graphs in a simple manner simplify the generation process. Besides, we apply two techniques to reduce computational cost: breadth-first search (BFS) and zeroing attention weights in edge estimation. Regarding data scalability, we apply a novel graph attention mechanism that simply extends the attention mechanism used in natural language process- ing (Vaswani et al., 2017 to graphs. This graph attention mechanism does not include sequentially dependent hidden states as the recurrent neural network (RNN) does, which improves the paralleliz- ability of training significantly. Compared with other graph attention mechanisms (Veličković al.) 2018 Abu-EEl-aaja et al. 2018 [shiguro et al. 2019), ours is architecturally simple, computation- ally lightweight, and general, I.c., its applicability is not limited to generation tasks. Finally, for label scalability, formulate the likelihood of graphs assuming multiple node/edge labels. Also, we use graph convolution//attntion layers, whose numbers of parameters do not depend directly on the number of labels.
Moreover, we introduce a unified non-domain-specific evaluation metric for generation tasks of node/edge-labeled graphs. Because such method does not currently exist, prior works relied domain-specific metrics or visual inspection, which made unified and objective evaluations difficult. Thus, we construct unified evaluation metric that dispenses with domain-specific knowledge and considers not only the topology but also node/edge labels by combining a graph kernel and Maxi- mum Mean Discrepancy (MMD) (Gretton et al.) 2012). Although similar statistical test based on MMD via graph kernel was used for schema matching of protein graphs in Kriegel et al. (2006), to the best of our knowledge, this work is the first to use as an evaluation metric for graph generation tasks.
Our experiments on synthetic and real-world graphs demonstrated that our models can scale up to handle large graphs and datasets that previous methods had difficulty with; our models demonstrated superior results to those of baseline methods.
To summarize, the contributions of this work are as follows:
We propose GRAM, a graph generative model that scalable, especially in training.
We propose novel graph attention mechanism that is general and architecturally simple as a key portion of the generative model.
We define scalability in graph generation from three perspectives: number of nodes, data, and labels.
We construct unified con-domain-specinne evaluation metric for node/edge-labeled graph generation tasks by combining a graph kernel and MMD.
2 RELATED WORK
Although there are several traditional graph generative models (Erdös & Rényi 1959: Albert & Leskovec et al. 2010 Robins et al.) 2007 Airoldi al.) 2209), we focus here on recent machine cerming-basedd models, which have outperformed traditional models in various tasks.
Barabási 2002
In terms of their generation process, existing graph generative models can be classified into least two types: tensor generation models and sequential generation models. Tensor generation models (Simonovsky & Komodakis 2018 De Cao Kipf 2018 Grover al. (008)) generate graph by outputting tensors that correspond to the graph. These models are architecturally simple and easy to optimize for small graphs. However, they face difficulty in generating large graphs owing to the non-unique correspondence between graph and tensors, limitations in the pre-defined maximum number nodes, and the increasing number of parameters depending on the maximum graph size. In contrast, sequential generation models, such as DeepGMG (Li et al.) 2018), GraphRNN ct al. 2018b), generate graphs by adding nodes and edges one-by-one, which alleviates the above problems and generates larger graphs. To achieve graph scalability, we employ the latter. However,
2

---

Under review as a conference paper at ICLR 2020
to generate graph with nodes and edges, DeepGMG requires at least O operations be- cause of its complex generation process. GraphRNN reduces this time complexity to (n.)) with dataset-specific value M by utilizing the BFS. However, it cannot handle node/edge labels, mainly because it omits the feature extraction process, and relies mainly on the information the hidden states of the RNN. Moreover, these models include sequentially dependent hidden states, which make training parallelization difficult. In contrast, our model employs a graph attention mechanism without sequentially dependent hidden states. This improves the parallelizability of training sig- nificantly. Also, by applying two approximation methods, we reduce the complexity to almost a linear order of n while conducting a rich feature extraction. comparison of our models' and the baselines' complexities is given in Table 2 in Section
As another division, there are unsupervised learning approaches and reinforcement learning ap- proaches. Given samples of graphs, unsupervised learning models (Li et al. 2018 You et al. [018b] Simonovsky & Komodakis) 2018 Grover et al. 2018) approximate the distribution of them in an unsupervised manner. Reinforcement learning models (Luo et al. 2018 You et al. 201 Sa De Cao & Kipl 2018 Liu et al. 2018 Li et al. 2018) learn to generate graphs to maximize given return, such as QED (Bickerton et al., 2012). Although reinforcement learning approaches have demon- strated promising results on several tasks, such as molecular generation and network architecture optimization, we employ an unsupervised approach; this is because it considered to be more ad- vantageous when new samples that share certain properties with training samples are required or when the reward functions cannot be designed (e.g., family of pharmaccutical molecules against a certain disease is known, but the mechanism by which they work is not entirely known).
3 PROPOSED METHOD
An outline of this section is as follows: In Section 3.1 we first describe notations and define the considered graph generation task. In Section 3.2 formulate the likelihood of graphs. In Section we present our proposed graph attention mechanism, which is the key portion of our model and is used in feature extraction and edge estimation. In Section 3.4 we present our scalable graph generative model, GRAM. We describe two techniques to reduce the computational cost of edge estimation: BFS in Section 3.5.T and zeroing attention weights in Section 3.5.2 In Section 3.6 describe the training and propose an evaluation metric.
3.3
3.1 NOTATIONS AND PROBLEM DEFINITION
In this work, we define a graph G (V, as data structure that consists of a node set V {uI...., v and an edge set E = {eu,li,j E [1). For simplicity, we focus on undirected graphs. We assume nodes and edges are associated with node/edge labels and denote the number of them as a and b, respectively. For graph representation, we employ tensor representation. Specifically, given node ordering x, we represent pair of a graph and node ordering (G, x) as a pair of tensors (X", )"). Note that assume the existence of node ordering in graphs, and is a permutation function over nI.. X E {0, 1)mxa, whose i-th row is a one-hot vector corresponding to the label of Ur((), stores information about nodes. AT E {0, 1 whose (i, element is one-hot vector corresponding to the label of (())) stores information about edges. If no edge exists between (x) and Ux(); we replace with a zero vector. An example illustrated in Figure 3 in Section A.2. Note that (G, R) and (X*,A*) are in unique correspondence. Finally, for simplicity, we do not consider self-looping or multiple edges. A possible extension to self-looping edges would involve adding step to estimate them. For multiple or directed edges, we can prepare additional labels that correspond to them. In the remainder of this paper, for clear notation, we assume (i)) = i and omit the superscript x.
The target graph generation task is as follows: given samples from a distribution of graphs p(G), approximate the distribution (p Rz p) such that we can derive new samples from it (G ~ pGG)
3.2 LIKELIHOOD FORMULATION OF GRAPHS
To approximate distributions graphs in autoregressive manner, formulate the likelihood of a pair of a graph and node ordering (G, π) and decompose it into a product of conditional proba- bilities. Because (G, T) uniquely defines (X, A) and vice versa, we have p(G, π) = p(X, A), which
3

---

Under review as a conference paper at ICLR 2020
is decomposed into a product of conditional probabilities as
(I) where Acs,cca E 1R--Ix=-xxx represents a partial tensor A (1 S i.j < 8), and other notations follow this. For simplicity, we omit the slice notation for the last dimension of each tensor. In addition, (X<.: Acs.<s) uniquely defines a subgraph of G, which we denote as Ges. With this for- mulation, the likelihood of graph G is defined marginal, p(G) = (G, = P(X, A). Also, we represent (X<s,A Ass,es) as Ges in the following equations.
A) - AT= PX, <s),
Act, Xes
During training, given samples from p(G),
model approximates the joint probability p(X, A).
More precisely, it approximates p(X, .A) by approximating the conditional probabilities p(X,, Ges)) and p p(Ar,s/ (Ac,, Xs, Gzs). As for p(X1, (((X1,A1,1) 11.1). we use a sampling distribution from the training data. Although the choice of π provides room for discussion, we adopt the BFS used in You et al. 2018b).
On inference, we sequentially sample X, and 2 2,..., L,..., 1) from the approx- imated distribution, and we get (X, A) when the EOS output. This can be viewed as sampling from the approximated distribution (G, ~ p(G, rt). In particular, by focusing only on G, we can view as sampling from the marginal ~ (G)).
3.3 GRAPH ATTENTION MECHANISM
The aim of employing a graph attention mechanism is to efficiently take in the information of distant nodes by attention. Our graph attention mechanism extends the attention mechanism used in natural language processing (Vaswani et al.) 2017) to graphs. However, one of the significant differences between graphs and sentences is that we cannot define absolute coordinates in a graph, which makes it difficult to embed positional information in nodes as in Vaswani et al. (2017). To alleviate this problem, we focus on multi-head attention as in Vaswani et al. (0177). and we use relative positional information between nodes: we introduce bias terms in projection to subspaces, which are functions of the shortest path length between two nodes. The operation of graph attention is illustrated in Figures andd 6 Section A.4
2017). we denote matrices into which n query, key, and value vectors are stacked as Q = (q), .... qn) (E Ruxda), K )., Raxdx),, ), and V = (V1,..., ( Raxdy), ), respectively. Note that we use V to represent the value matrix, not node set. Also, we assume that the i-th row of each matrix corresponds the feature vector of node Us. Note that the operation of graph attention is permutation invariant. Denoting the dimensions of the output vector and the subspace as do and ds. respectively, the graph attention mechanism is defined as GMultiHcad K, V) = Concct head,; W
Following Vaswani et al.
(E Rnxdo)
(2)
where head, = GAAtenttin K, where H represents the number of projections di-dimensional subspaces. GAttention(:::) is defined as GAttention(Q, V) = (0), On
(E Ruxds)
(h = (1=1,... H)
The operation of
(E Raxds)
(3)
where o, = Σド (e:) (WV v, + b (c,,e)) Each attention weight vector e; is calculated as
Rds)
(i 1 I.....))
C; = softmax(s:) (s;)
(R)
(i = I,,.., n) (4)
where (8t) dx - (W + 6a (v,, v,)) k, + + (v,, +b"(,, vj))
(E R)
(j= 1,.1,...,
The parameters to be learned are four weight matrices (e(E Rdxxda), W (E Rdsxdx), WV(E Rdssdr), ( Hd and three bias terms - 1 bK ,, Rdo). We used different pa- rameters for each head.
To consider the geometric relation between two nodes, we used functions of the shortest path length between ii and vj as (v,,,))) u/),, ) 6K uy), and by (,), v2). Furthermore, because path length is discrete, we used different weight parameters for each path length. Examples of other possible approaches include using network flow or functional approximation. Specifically, setting b = 6 = 6y = 0 yields the original multi-head attention. As in Vaswani al. (2017). we added two- layer feedforward neural network (FNN), which is applied after the above operations. We denote these operations, including the FNN, as the graph attention mechanism in the following sections.
4

---

Under review as a conference paper at ICLR 2020
Fasture Extractor
Node Estmator
Edge Estimotor
[AA,,l=
Grach
Grach Actention
M
(1 banns
Acxesa
H
Figure 2: (-th feature traction block.
Figure 1: s-th step of the generation process.
3.4
GRAM: SCALABLE GENERATIVE MODELS FOR GRAPIIS
GRAM approximates a distribution over graphs in an autoregressive manner. It utilizes the graph attention mechanism to improve the parallelizability of training. The s-th step of the generation process is illustrated in Figure [ a larger and more detailed version is given in Figure in Section A.3 A detailed analysis of computational complexity is included in Section A.1
3.4.1
MODEL. OVERVIEW
In the following sections, we focus on the s-th step, i.e., the generation of v, and {ei,s).... ..., 1,-1,s.- The architecture of GRAM consists of three networks: feature extractor, node estimator, and edge estimator. The feature extractor calculates node feature vectors and graph feature vector by sum- ming them. The node estimator predicts the label of the new node U.. The edge estimator predicts the labels of new edges {EI,s,,.. ..., 1s-1.s) between previously generated nodes {UI,..., Va- } and the new node Ug. In other words, the node estimator approximates p(X, <G,,), and the edge estimator approximates p(Ar,el Acci, X,, G<s) in Equation
3.4.2 FEATURE EXTRACTOR
Given a pair (Xee. Ace,ce). the feature extractor calculates s node feature vectors H (h",..,,h"" ho- ) and graph feature vector h of the corresponding subgraph Ge.. Here, h de- notes the feature vector of node v, and we use h(()) represent the output vector of the 1-th block. This consists of L feature extraction blocks and a graph pooling layer. In this work, we used L = 3.
feature extraction block composed of graph convolution layer and a graph attention layer stacked in parallel, as illustrated in Figure We aim to extract local information by graph convo- lution layers and global information by graph attention lavers. Although there are various types of graph convolutions, convolutes the features of neighboring nodes and edges into each node and edge in graph. A graph attention layer operates self-attention, where query/key/value vectors all node feature vectors. To reduce computational cost, we restricted the range of attention to path length r. Also, to exploit low-level features, we stacked degree and clustering coefficients, which are non-domain-specifer statistics in graphs, into each input node vector. Calculation of these graph statistics and BFS is required only once before training and is relatively fast compared with training time.
employed the used in Johnson et al. (2018). Roughly speaking, this
The graph pooling layer computes a graph feature vector h by summing all node feature vectors in the subgraph. To improve expressive power in aggregation, we used a gating network as in et al. (2018). Specifically, the operation in the graph pooling layer is defined as
hc i= (gpoot
(5)
where Spoot is two-layer FNN, and is sigmoid function.
3.4.3 NODE ESTIMATOR
The node estimator predicts the label of new node u., More specifically, it predicts X, from h as
X. softmax(gN
(E Ra+1)
(6)
where INE is a three-layer FNN, and the output dimension, including the EOS, is a 1. We terminate the generation process when the EOS output.
Recause Johnson al. (018 assume directed graphs as input, we ignore go in Figure 3 of that paper.
5

---

Under review as a conference paper at ICLR 2020
3.4.4 EDGE ESTIMATOR
The edge estimator predicts the labels of the new edges (ei,s)..,, between previously gen- erated nodes (.1: and the new node v.. More precisely, it predicts Ar,a (t 1,..,, 1)
from h he h" and previously predicted edge labels in this step
A = softmax(gEE h. h." h(2)) (E (ERR+1) (I=1,-.,8-1) (7)
where h. is the embedded vector of the predicted label of Us i.e., X.. The vector h&, is calculated by a source-target attention in which the query vector Concal (hj, h3) and the key/value vectors [Concat(h", h²" _T I,..., t 1}. where h is embedded vector of the predicted label of 6r,,, i.c., A7,s. Thereby, we aim to express the dependency on Act,s in Equation [T The operation is illustrated in Figure [6] in Section A.4 We three-layer FNN 9EE, where the output dimension is b b+ 1, including the "no edge" label. When the "no edge" label is output, we do not add an edge and we Ar.. 0.
3.5 REDUCING COMPUTATIONAL COMPLEXITY IN EDGE ESTIMATION
To generate a graph with n nodes, the edge estimation process requires O(n) operations for one edge, resulting in (n²²) operations for one step and (n²)) operations in total. This is significant obstacle to achieving graph scalability. Here, we present two methods to reduce complexity in edge estimation: BFS and zeroing attention weights; these can be combined independentl.
3.5.1
COMPLEXITY REDUCTION VIA BREADTH FRIST SEARCH
As in You et al. (2018)). we utilize the BFS node ordering, but our implementation gives a stricter upper bound. More precisely, when estimating new edge Ct,s (L 1....& 8 1), nodes that can be connected to the new node V, are restricted to "frontier nodes" V [r/]min({i] q is connected to 1 S T S 8-1] under π = BFS With this property. we need only consider Vy instead of the whole {U,,..., Ve-1] when estimating Et,s. This reduces the complexity of edge estimation to (nn3²), where 8 = [Vyl- A proof and example are included in Section A.5 Finally, we denote this variant as GRAM-B.
3.5.2 COMPLEXITY REDUCTION VIA ATTENTION WEIGHTS ZEROING
As another method, we use approximation inspired by empirical observation. Specifically, our inspection of each attention weight during estimation of new edge 61,s (t =t= 1, l.., 8 8- revealed that the nodes predicted to have connection to U2 (i.e., Vneedge {o, Ar,s 0, 1,..., ...... t- 1}) have near-zero weights, while the nodes predicted to have connection (i.e., Vhaveedge = (wr|Ar, * 0,
1,...,/-11 1)) have larger weights. This suggests that among [v1, ("1, Viaveedge are important predict the new edge et.e, while Vuocdge are not. Hence, we deterministically set the weights of the latter to zero, which means we do not consider them in graph attention. With this approximation, the complexity is reduced to (n²a), where = \Vnveedgel |. In addition, because a S. deg(v,) holds, we can assume that a < when dog(u,) < n, which is often the case in many real-world graphs. A more detailed discussion and an example are included in Section A.6 Finally, we denote this variant as GRAM-A and the combination the two as GRAM-AB, which has complexity (nax3).
3.6 TRAINING AND EVALUATION
The loss function is the negative logarithm of Equation and the training is done in the usual autoregressive manner. In particular, for one graph, forward/backward propagation n node esti- mations and at most nın 1 edge estimations can be processed parallelly (i.c., in ((1) sequential operations) by using ground-trutt -rutt labels and proper masking.
To evaluate the quality of generation, evaluation metrics based on MMD with graph statistics were used in You et al. (2018b). However, these metrics cannot consider node/edge labels, and it is difficult to determine which one is important not. Therefore, we construct unified evaluation metric GK-MMD that can consider not only topology but also node/edge labels by combining a graph kernel and MMD.

---

Under review as a conference paper at ICLR 2020
MMD is test statistic determine whether two sets of samples from the distribution p and q derived from the same distribution (i.e.. whether = 9). When its function class F is a unit ball in reproducing kernel Hilbert space (RKHS) H. derive the squared MMD as
MMD2 pp p] = Ex,z' (k(, x²]] 2 [k y)] + E (k(,31))((
(8)
where -): is the associated kernel function (Gretton al. 2012
Graph kernels are kernel functions over graphs and we used the neighborhood subgraph pairwise distance kernel (NSPDK) (Costa & Grave 2010), which measures the similarity of two graphs by
matching pairs of subgraphs with different radii and distances. Because NSPDK is pesitive-definite kernel (Costa& & Grave 20T0), it follows that it defines unique RKHS H (Aronszajn 1950). This allows us to calculate the squared MMD using Equation g
Because NSPDK considers low/high-level topological features and node/edge labels, GK-MMD can be used as a unified evaluation metric for node/edge-labeled graph generation tasks.
4 EXPERIMENTS
We performed experiments on four types of synthetic graphs and three types of real-world graphs with various topologies, graph sizes, dataset sizes, and numbers of node/edge labels. We evaluated the quality of generation and the actual computational cost required.
As synthetic graphs, used four types of random graphs: grid, lobster, community (Fortunato) 2010), and Barabási-Albert (B-A) (Barabási & Albert 1999). We generated 700 graphs with num- bers of nodes in the range 50 < V S 100. We split them into training/test/validaiii data at 500:100: To make the problem more realistic, we deterministically labeled nodes and edges according their properties, such as degree or distance from backbone. Detailed configurations, including model-specifie parameters and node/edge labeling, are described in Section A.7
We used three types of real-world graphs: molecular, ego, and protein. For the molecular graphs we used 250k samples from the ZINC database (Sterling & Irwin, 2015) provided by Kusner et al. (2077). The ego graphs are ego networks from the Citeseer networks (Sen al., 2008). The protein graphs represent protein structures with amino acids as nodes (Dobson & Doig 2003). For the ego and protein datasets, we used data provided by You et al. (2018b).
We compared our models with DeepGMG (Li et al. 2018), GraphRNN, and GraphRNN-S (You (et al.] 200 as recent deep learning-basee baselines. We modified the GraphRNN and GraphRNN- S models so that they output multiple node/edge labels. Because we target the unsupervised learning graph generation task and most of the datascts we used are node/edge-labcled, we did not conduct comparison with reinforcement learning-basse methods traditional models, which are incapable of handling node/edge labels, except for GraphRNN and its variant.
To evaluate the quality of generation, we calculated squared GK-MMD score between generated graphs and test graphs. We also used the squared MMD score of the three types of graph statistics used in You et al. (2018b): distributions of degree, clustering coefficient, and orbit count; however, these metrics do not consider node/edge labels. A lower MMD score indicates a better quality of approximation in terms of the given statistic. For the molecular graphs, we generated 10k samples and calculated the ratios of generated graphs that are valid as molecules (valid [%]), unique samples (unique [%]), and novel samples, i.e., valid, unique, and unseen in the training data (novel [%]). We also reported training time [hour].
The results are listed in Table [ We did not train DeepGMG on the ego, protein and molecu- lar datasets due to its impractical training time (estimated to take over 90 hours). Instead, for the molecular dataset, we used generated graphs provided by the author for evaluation. Although Deep- GMG achieved high valid/unique score and low GK-MMD score in the molecular dataset, it failed for larger graphs. This is likely because its feature extraction method is based only on graph convo- lution, which gives only local information, it works well only small graphs, such as those of molecules. Moreover, its training is slow due to its sequentially dependent hidden states.
GraphRNN and its variant achieved low topological MMD scores for simple topology graphs like grid. However, their performances were poor on other graphs with more complex topologies or rules. This is likely because they do not calculate node/edge features, which limited their expressive
7

---

Under review as a conference paper at ICLR 2020
Results synthetic graphs (top) and real-world graphs (bottom). The dataset size N, max- imum graph size |V |mlaxx and the number of node/edge labels b are shown as (N, Immxx a, b).
Table I:
Grid (500, 100, 3, 2)
Community (500,
100, 4,
B-A (500, 100, 2, 3)
deg.
clus,
orbit
GK
time
deg.
clus.
orbit GK
time
deg.
clus.
orbit
GK
time
DeepGMG
1.315
le-5
0.682 0.409
15.9 1.515 1.074 1.118 0.233
9.2 1.839
1.568 1.075 0.257
9.1
GraphRNN
5e-4
0
2e-5 0.289
1.9
0.011
0.121
0.024 0.061
3.9
0.359
0.096 0.130 0.025
3.4
GraphRNN-S
0.040
8c-4
0.001
0.287
1.1
0.633
0.195
0.427
0.062
2.5
0.581
0.159 0.158 0.037
2.6
GRAM
0.105
0.002
0.013 0.287
0.8 0.011 0.025 0.009
0.016
1.0
0.034
0.009
0.024
0.015
1.0
GRAM-A
0.314
0.007 0.099 0.295
0.7 0.031
0.004 0.038 0.016
0.9 0.061
0.094
0.045
0.015
GRAM-B
0.029
0.002 0.011
0.287
0.7
0.029
0.056
0.015 0.019
0.9
0.063
0,005
0.031
0.015
1.0
GRAM-AB
0.357 0.015 0.126 0,309
0.7
0.164 0.080 0.080 0.020
0.9
0.044
0.015 0.031 0.020
0.9
Ego (605, 399, 1. 1)
Protein (734, 500, 89, 1)
Molecular (250k, 38, 9,
deg.
clus.
orbit
GK
time
dog.
clus.
orbit
GK
time
valid unique novel
GK
time
DeepGMG
84.5
99.1
83.8
0.0201
GraphRNN
0.117 0.615 0.043 0.028
16.0
0.040
1.256
0.506
0.011
22.4
11.1
100,0
11.1
0.0284
20.5
GraphRNN-S
0.306
0.337 0.314 0.067
11.4
0.523
1.247 0.123 0.019
13.7
26.2
99.9
26.2
0.0551
12.4
GRAM
0.141 0.160 0.058 0.034
2.5 0.154
0.232
0.257 0.013
6.9
92.7
100,0
92.7
0.0198
9.5
GRAM-A
0.139 0.268 0.062 0.031
2.0 0,224
0.569 0.425 0.011
4.9
95.0
100.0
95.0
0.0198
9.4
GRAM-B
0.108
0.083 0.033 0.017
2.0
0.154
0.247 0.040 0.010
4.6
94.3
100.0
94.2
0.0206
8.5
GRAM-AB
0.269 0.182 0.249 0.017
2.0
0.046
0.049 0.111 0.010
4.7
94.9
99.8
94.8
0.0206
8.4
power In other words, the feature extraction process is inevitable for the generation of complex graphs.
In contrast, our models achieved overall lower MMD scores on most of the datasets, which means that the distance between the approximated distribution and the test set is relatively small in terms of topological and node/edge label features. Also, from the results on the molecular dataset, we can see that the generation is diverse while capturing the strict valence rule via unsupervised learning. This is likely due to the bias term of graph attention in edge estimation: it enables models to control the valence and type of rings. In terms of training time, there is significant acceleration compared with the baselines. This is mainly owing to the graph attention mechanism, which reduces the number of sequential operations during training to almost constant and enables efficient parallelized training.
Besides, we can observe the impact of the two computational reduction techniques on the actual computational time. They were also more efficient in terms of memory usage, requiring less than half that of the original model. Surprisingly, although there is generally some trade-off between training speed and performance, GRAM-B performed better than the original model on the grid and ego datasets, and GRAM-A performed better the molecular dataset. This is likely because each approximated model has its own strong topology for which both performance is boosted and computational cost is reduced. On average, the proposed models performed better on large graphs. More detailed discussions are included in Sections A.5 and A.66.
From the above results, we can see the scalability of our models for large graphs and datasets and multiple node/edge labels, which the baseline methods have difficulty in handling. Note that al- though our approximated models have some trade-off between performance and training speed, they still achieved superior or competitive results over the baselines in most cases. Also, we found an interesting correlation between GK-MMD score and topological MMD scores or visual similarity, which supports the validity of this metric. The detailed setting of the experiments, additional results, visualization, and an ablation study are included in Section A.7
CONCLUSION
In this work, we tackled the problem of scalability as it is one of the most important challenges in graph generation tasks. We first defined scalability from three perspectives, and then we proposed scalable graph generative model named GRAM along with some variants. Also, we proposed a novel unified
graph attention mechanism evaluation metric for node/edge-labes labeled graph generation tasks. In an experiment using synthetic and real-world graphs, we verified the scalability and superior performances of our models.
key portion of the model and constructed GK-MMD
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sami Abu-El- Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alexander A Alemi Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems 31. 2018.
Edo M Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodels. Advances in Neural Information Processing Systems 21. 2009.
Réka Albert and Alsert-László Barabási. Statistical mechanics of complex networks. Rev. Mod.
Phys., 74:47-97, Jan 2002.
N. Aronszajn. Theory of reproducing kernels. Transactions the American Mathematical Society, 68(3):337-404, 1950.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
G. Richard Bickerton, Gaia V. Paolini, Jérémy Besnard, Sorel Muresan, and Andrew L. Hopkins. Quantifying the chemical beauty of drugs. Nature Chemistry, 4:90 EP -, 01 2012.
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In Pro- ceedings of the 27th International Conference on International Conference on Machine Learning, 2010.
Nicola De Cao and Thomas Kipf. MolGAN: An implicit generative model for small molecular graphs. arXiv e-prints, art. arXiv: 1973, 2018.
Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(():771 783, 2003. ISSN 0022-2836.
Paul Erdös and Alfréd Rényi. On random graphs, Publicationes Mathematicae (eaeemmaaiaeeDDebeeee (Debrecen), 6: 290-297, 1959.
Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5):5--774, 2010.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel tao-sample test. J. Mach. Learn. Res., 13:723-773, 2012.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative Generative Modeling of Graphs. arXiv e-prints, arXiv:1803.10455 2018.
Katsuhiko Ishiguro, Shin-ichi Maeda, and Masanori Koyama. Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networks. arXiv e-prints, art. arXiv:1902.01020, 2019.
Justin Johnson, Agrim Gupta, and Fei-Fei. Image generation from scene graphs. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2018.
Hans-Peter Kriegel, Karsten M. Borgwardt, Arthur Gretton, Bernhard Schölkopf, Malte J. Rasch, and Alex J. Smola. Integrating structured biological data by Kernel Maximum Mean Discrepancy. Bioinformatics, 42744))e4---57, 07 2006.
Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar Variational Autoen- coder. arXiv e-prints, art. arXiv: D.XXv:1703.0192: 700.01125, 2017.
Jure Leskovee, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: An approach to modeling networks. Mach. Learn. Res., 11:985-1042, March 2010.
Yibo Li, Liangren Zhang, and Zhenming Liu. Multi-objective de novo drug design with conditional graph generative model. Journal of Cheminformatics, 10(1):33, 2018.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning Deep Generative Models of Graphs. arXiv e-prints, art. 1XXv:1803.00322 2018.

---

Under review as a conference paper at ICLR 2020
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph varia- tional autoencoders for molecule design. In Advances in Neural Information Processing Systems 31. 2018.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Yan Liu. Neural architecture optimization. In Advances in Neural Information Processing Systems 31. 2018.
Garry Robins, Pip Pattison, Yuval Kalish, and Dean Lusher. An introduction to exponential random graph (p") models for social networks. Social Networks, 29(2):173 191, 2007.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using
variational autoencoders. In ICANN, 2018.
Teague Sterling and John J. Irwin. Zinc 15 ligand discovery for everyone. Journal of Chemical Information and Modeling, 55(1 35(11))2324-2337, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems 30. 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
Hongwei Wang. Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. GraphGAN: Graph Representation Learning with Generative Adversarial Nets. arXiv 2017.
e-prints, art.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional pol- icy network for goal-directed molecular graph generation. Advances in Neural Information Processing Systems 31. 2018a.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generat- ing realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018, 2018b.
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 COMPLEXITY ANALYSIS
In this section, we compare the computational complexity of the training of our models with that of existing models. Following Vaswani et al. (2017), we consider two factors: total computational complexity and minimum sequential operations with parallclization. Note that we assume all matrix- vector products be computed in constant time. Table summarizes the results.
To generate a graph with n nodes and m edges, DeepGMG (Li et al. 2018) requires at least O(m)²) operations. Because the initialization of the state of the new node depends the state in the previous step, DeepGMG's s minimum required sequential operations is Onn)). On the other hand, GraphRNN You et al. 2018b) requires (nTM) operations with dataset-specific constant value M, utilizing the properties of the BFS and relying mainly on the hidden states of the RNN. However, its minimum number of sequential operations is On + MM because of the sequential dependency of the hidden states of the RNN: moreover, it cannot generate node/edge-labeled graphs.
Next, evaluate GRAM and its variants. We denote the average number of nodes/edges within distance of one node as N,/M, and reuse the and B defined in Section 3.5
In one step, the feature extractor requires O + nN,) operations, considering graph convolution layer requires (m), and a graph attention layer requires OnnN,). However, comparing the node only nodes within distance
features in Ges with those in G<s+1 G, U Us U (ei.s....,.--- T. of Us change their features. Utilizing this property, we conduct feature extraction only for rl- neighboring nodes of the previously added node and reuse features for the other nodes, by which the number of feature extraction operations is reduced to O(n(M,L + N,).
Also, the node estimator requires ((n) operations in total. In edge estimation, GRAM requires (n²) operations, GRAM-B requires O(132), GRAM-A requires O(n'a), and GRAM-AB re- quires 3(na3).
Therefore, the total complexity of GRAM is Onn + n(M,L + N,L.,)), that of GRAM-B is AB is +n,32+((M, + N.))). that of GRAM-A is O(n"a+n(MM NN,,NN,), and that of GRAM- N,). Note that all the estimation operations of the node estimator and the edge estimator can be parallelized training because our model has no sequentially dependent hidden states like the RNN does.
From the above analysis. we can see that our models require fewer operations than DeepGMG when N, assuming NrL and Mrt are nearly constant and sufficiently smaller than and m, respectively, the total complexities of GRAM-B and GRAM-AB can be regarded almost linear in n, which is competitive with GraphRNN, but ours keep the feature extraction. More importantly, all estimation operations can be parallelized, which facilitates training using multiple computing nodes. Therefore, we can expect graph scalability and data scalability of our models. We also expect label scalability because our models are flexible to a variable number labels by modifying only the dimensions of the input and output layers.
holds, which is the often case, while keeping rich feature extraction. In addition,
Table 2: Total computational complexity and minimum sequential operations during training.
Method
Total Complexity
Minimum Sequential Operations
DeepGMG
Omm)²)
O(n))
GraphRNN
O(nM)
O + M)
GRAM
Onn + n(MpL + N.)
(1)
GRAM-B
On.32 +n(MeL + N,L.N))
0(1)
GRAM-A
O(n'a -n(MA + N.LN.))
((1)
GRAM-AB
O(na + n(MxL + NoLN.))
((1)
11

---

Under review as a conference paper at ICLR 2020
A.2 EXAMPLE OF TENSOR REPRESENTATION
An example of tensor representation is illustrated in Figure 3
Um(3)
(T(1)
Fr(d)
(e(3)
Vn(5)
G
X*
A
nG,
(X7, (77)
Figure 3: Example of tensor representation. n, a, and b denote the numbers of nodes, node labels, and edge labels, respectively. X E {0, 1]mxa, whose i-th row is one-hot vector corresponding to the label Un((), stores information about nodes. A E {0, 1]2xnxx whose (i.j)-th element one-hot vector corresponding to the label of (x())x())) stores information about edges. If no edge exists between (=(i) and Uz(s), we replace with zero vector. Note that (G, xT) and (X* A7) correspond uniquely.
A.3 DETAILED MODEL PIPELINE
detailed pipeline of GRAM is illustrated Figure
Feature Extractor
Node Estimator
Edge Estimator
Graph Attention
(Arx 1, I.... t-
Extratioon Block
Graph Pooling
Linesr
Feature
h
Linesr
Aea
(t m 1.... 1)
Acxcs
1hs
Gcs
Figure 4: s-th step of the generation process (s 6, = 3). In its s-th step, given subgraph Ge our model estimates the new node Us and new edges {ci.s...., Cg-1,=} to add next. Specifically. it takes tensor pair (X Ass,ss) as input and predicts the label of the new node X, and the labels of the new edges A,, (t = 1...., 1). In detail, first, the feature extractor calculates and a graph feature vector h from a tensor pair (X Acx.<s). Next, the node estimator predicts the label of the new node X, from the graph feature vector. When the EOS is output, the generation is terminated. Finally, the edge estimator predicts the labels of the new edges Ar, (t 1,... s 1) from the node feature vectors, the graph feature vector, the embedded vector of the predicted node label, and the embedded vectors of previously predicted edge labels in this step.
s - 1 node feature vectors H" = (h"...,h""_)
12

---

Under review as a conference paper at ICLR 2020
A.4 ILLUSTRATION OF GRAPH ATTENTION
The graph attention mechanism in feature extraction (self attention) is illustrated in Figure and that in edge estimation (source target attention) is illustrated in Figure
A
Output feature vector
Projection space
(ci)
(csh
(ci)
Elementbiie product
(e)
(c Attention weights
product
Projection to subspaces
W 6
W.KK 8
WV
A
V
k;
kg
0/
Query vector
Key vectors
Value vectors
h 121-13
-0-1)
A
Input feature vectors
Figure 5: Operation of graph attention in the 1-th feature extraction block, where query, key, and
value vectors are all node feature vectors (i.c., Q = K = = H" (h (t-()) ...., h
"((-1))r) ")") (self
attention). For simplicity, we focused on query/output vector and one subspace.
13

---

Under review as a conference paper at ICLR 2020
B
Output feature vector
1y
Projection to output spoce
sum
Elementwise product
Attention weights
soltmax
product
Projection subspaces
Wr 6
W K 8
W.Y 6"
Concat(h 4i.)
Coneat(h", Aç, A(.))
Conccat (Ne. h N5
Concat (b., AS,
ConcatiAA N
Query vector
Key vectors
Value vectors
hp
h
Ay
Previously generated edges in this step
Figure 6: Operation of graph attention in the estimation of the new edge Et,s (s = 6, = 3). The query vector is Con h"), and the value and key vectors are {Concat(h") h" hr,))r 1,...,t 1}, where he the feature vector of the node Vt, h" is the embedded vector of the predicted label of the new node Us, X,, and hf is the embedded vector of the predicted
label of the new edge 67,,, Ar In other words, Q Concat(h,, h?)T, K V Concat(h" (Concat(h", ho h Concattt. hi h) (source target attention).
14

---

Under review as a conference paper at ICLR 2020
A.5 GRAM-B: UTILIZING CREADTH-FIRST SEARCH NODE ORDERING
In this section, brief and intuitive proof for the proposition in Section 3.5.1 given along with additional discussion how much the computational complexity is actually reduced by this ap- proximation and its strong topology.
A.5.1 PROOF
Consider the BFS tree in the left of Figure Suppose there is at least one con- nection between the new node Us and the non-frontier nodes V Vy. where Vy {u>l min( is connected to vz-13)
- (right of Figure 7 Then, under the sumption BFS node ordering, V, must be visited/generated before U--1, which a contradiction. Therefore, the nodes that have connections between the new node Us limited to the frontier nodes V (middle of Figure
Breacth-finst search tree
Possible connections
Impossible connections
Gesa
V
VJ
Us
Us
U/-2 U,-1
9-1
Uz-1
Figure 7: BFS tree example Gee (left), possible connections to the new node v, (middle), and impossible connections to the new node Us (right).
A.5.2 DISCUSSION
The average values of B = |Vy for each dataset are listed in Table 3 In both the synthetic and real-world graphs, we can see that | is relatively small compared to (approximately 1/10 1/3). Therefore, considering the results in Table 2 the average computational cost of GRAM-B is estimated to approximately 1/100- 1/9 that of GRAM, which significant reduction.
In the experiment, GRAM-B performed better than its original model on the grid and ego datasets. This likely because these graphs have simple topologies and their BFS trees also have typical simple patterns. Therefore, restricting the range of edge estimation to the frontier nodes Vy made the problem easier for the model. Thus, we expect GRAM-B's performance to boosted when the topologies of the graphs and their BFS trees have simple patterns.
Table 3: Average values of a and 3 and the number of nodes n per graph for each dataset.
Grid
1.8
9.0
72.2
Lobster
1.0
4.2
76.0
Community
2.7
23.5
74.2
B-A
3.8
31.9
72.7
Molecular
1.1
3.6
23.2
Ego
2.1
45.8
141.1
Protein
2.5
25.7
260.2
15

---

Under review as a conference paper at ICLR 2020
A.6 GRAM-A: ZEROING ATTENTION WEIGHTS
Here, we provide an additional discussion on the actual computational complexity reduction by this approximation and its strong graph types. Figure 9 illustrates the attention weight zeroing in edge estimation.
Figure& shows the two distributions of attention weights in one step of edge estimation (i.e., in the calculation of her)) the grid dataset. The blue represents the distribution of weights for nodes that are predicted to have no connection to the new node U, (i.e., [v>[A orange represents the distribution of weights for those predicted to have connection to the new node (i.e.. [ A * O, = L..... t - 1).. From this figure, we can see that the former distribution is sharper around zero compared with the latter, most of whose weights take near-zero values. Similar results were observed for the other datasets.
0, T = I,..., t t-1)), 1}), and the
The average values of for each dataset are listed in Talbe 3 In both the synthetic and real-world graphs, we can see that a is less than 4 and approximately 1/ 100 ~ 1/20 of n. Thus, considering the results in Table 2 the computational cost of GRAM-A is estimated to approximately 1/100 1/20 that of GRAM on average, which a dramatic reduction.
In the experiment, GRAM-A performed better than GRAM the molecular dataset. This is likely because these graphs have strict rules or distinct patterns in incident edges to a node, such as the valence rule, and focusing only on the actual generated edges is both sufficient and makes the prob- lem simpler. Thus, we expect that GRAM-A will demonstrate better performance when the graphs follow certain strict rule on incident edges of their nodes.
80
60
no. edge have, edge
2-
attention weight
Figure 8: Distributions of attention weights in edge estimation on the grid dataset. The blue rep- resents the distribution of nodes predicted have connection to the new node, and the orange represents that of nodes predicted to have connection. More than 90 % of attention weights are less than 0.05 for the former distribution, whereas approximately 70 % of attention weights are less than 0.05 and more than 15 % are larger than 0.95 for the latter. Note that the scale of the y-axis is different between the top and halves.
A.7 EXPERIMENTAL SETTING DETAILS
A.7.1 DATASET CONFIGURATION
Here, the detailed configurations the synthetic graphs are described. Samples from each synthetic graph dataset are illustrated in Figures TO 11 12 and 13 (color is best). Different color corresponds to different node/edge labels on each dataset.
Grid We used 2D grid graphs with the number of nodes in the range 50 A V < 100. Each node was labeled according its degree, yielding 3 types of node labels: "comer". "edge", and
16

---

Under review as a conference paper at ICLR 2020
e2,s (no edge, ignore in graph attention)
Ct,s
Figure 9: Ilustrationn of attention weight zeroing. In the estimation of Ct,s+ we ignore nodes that are predicted to have no connection with Us (U2 or 2 in this case) and set their attention weights to zero deterministically.
"inside". Each edge was labeled according to its geometric direction, yielding 2 types of edge labels: "horizontal" and "vertical".
Lobster We used lobster graphs with the number of nodes in the range 50 < V < 100. We set probability of adding an edge to the backbone p1 0.7, and probability of adding an edge one level beyond the backbone P2 = 0.3. Each node was labeled according to its distance from backbone, yielding types of node labels: "leaf", "branch", and "backbone". Each edge was labeled according to its incident nodes, yielding 2 types of edge labels: "leaf-branch" and "branch-backkonee"
Community We used 4-community graphs (Fortunato) 2010) with the number of nodes in the range 50 < [V] 100. We set number of communities [ = 4. number of nodes in community = |V/44, probability of intra-connection pix. = 0.23, and probability of inter-connection Pout = 0.023. Each node was labeled according to the community it belongs to, yielding 4 types of node labels: "communityl". "community2", "community3", and "community4". Fach edge was laheled according its incident nodes, yielding 2 types of edge labels: "intra-community connection" and "inter-community connection".
B-A We used Barabási-Aloon (B-A) graphs (Barabási & Albert 1999) with the number of nodes in the range 50 < [V| < 100. We set number of edges to connect a new node and existing nodes as m 4. Each node was labeled according to whether its degree falls the top 50% or bottom 50%, yielding 2 types of node labels: "hub" and "exterior". Each edge was labeled according to its incident nodes, yielding 3 types of edge labels: "hub-hub", "hub-exterior", and "exterior-exterior".
A.7.2 TRAINING CONFIGURATION
Here, we give details of the training configurations. We essentially used the default settings for the baseline methods.
For all datasets, DeepGMG was trained using single GPU for 10 epochs with batch size because its generation process is so complex that batch implementation is difficult.
GraphRNN and GraphRNN-S were trained using single GPU for 96000 iterations with batch size 32. For the molecular dataset, considering its relatively large dataset size, we increased the number of iterations to 1536000.
For the convenience of implementation, we started the generation process from seed subgraphs with the number of nodes Nmiu- For the synthetic graph datasets, we trained our models using a single GPU for 100 epochs with batch size 32, and we used r = 2 and N Nmii = 10. For the molecular dataset, we trained our models using 2 GPUs for epochs with batch size 256, and we used
and Nmin = 5. For the ego dataset, we trained our models using 2 GPUs for 25 epochs, and we used r = 2 and Nmin 12. We used batch size 4 for GRAM and batch size 8 for GRAM-A, GRAM-B, and GRAM-AB. For the protein dataset, we trained our models using GPUs for 25 epochs, and we used r = 2 and Nmin 12. We used batch size for GRAM and batch size 32 for GRAM-A, GRAM-B, and GRAM-AB. Due to the code dependencies, Tesla P100 was used for DeepGMG, GraphRNN, and GraphRNN-S, and Tesla V100 was used for GRAM and its variants. Empirically, the choice between the two gave significant difference in computation time for cases.
17

---

Under review as a conference paper at ICLR 2020
In evaluation, reported average of runs for each score. To calculate GK-MMD score for the molecular dataset, we used 100 samples from the generated graphs and 100 samples from the test set for fast evaluation. We reported an average of 10 runs.
A.7.3 ADDITIONAL EXPERIMENT RESULT
The results on the lobster dataset are listed in Table + As on other datasets, GRAM and its variants demonstrated competitive results in terms of topological MMDs, and better performance in terms of GK-MMD.
Table 4: Results on lobster dataset. Dataset size N, maximum graph size VV Mamx and the number of node/edge labels a, b shown as (N, |V Imax: a, b).
Lobster (500, 100, 3, 4)
deg.
clus.
orbit
GK
time
DeepGMG
0.958
8e-5
0.035
0.527
13.5
GraphRNN
1e-4
0
0
0.203
2.2
GraphRNN-S
0.020
0.023
4e-4
0.221
1.4
GRAM
0.001
5e-4
6e-5
0.049
0.9
GRAM-A
0,001
0.001
8c-4
0.043
0.8
GRAM-B
0.001
8e-5
2e-4
0.048
0.7
GRAM-AB
0.001
2e-5
7e-5
0.047
0.7
In addition, considering that the molecular dataset is a subset of the druglike category in ZINC database (Sterling & Irwin 2015), we reported the average QED scores (Bickerton al.) (012) of the training samples and the generated samples. QED score measures the drug likeliness of the molecular.
Table summarizes the results. We can see the generated molecular graphs of our models have higher QED compared with those of baselines, and near to that of the training set. Note that our models do not rely reinforcement learning methods and utilize neither the information of QED nor valence rule; they learned only through unsupervised learning.
Table 5: Average QED score.
QED
Train
0.732
DeepGMG
0.644
GraphRNN
0.563
GraphRNN-S
0.496
GRAM
0.722
GRAM-A
0.722
GRAM-B
0.691
GRAM-AB
0.694
A.7.4
ABLATION STUDY
To examine the effectiveness of the bias terms in the graph attention mechanism, conducted an ablation study. Specifically, we evaluated two variants: GRAM without bias terms of graph attention in edge estimation, and GRAM without bias terms of graph attention in feature extraction.
The results are listed in Table 6. On all the synthetic graph datasets, removing bias terms in edge estimation degraded its performance. From this, edge estimation for the better quality of generation. Also, removing bias terms in feature extraction degraded the performance the B-A dataset. This is likely because its expressive power is limited.
the importance of the bias terms in
18

---

Under review as a conference paper at ICLR 2020
On the other hand, the drop in the performance by removing bias terms in feature extraction is minor on the grid, lobster and community dataset. Considering the properties of these random graphs, this is likely because only local features were enough for these cases.
Table 6: Results of ablation study.
Grid
Community
deg.
clus.
orbit
GK
deg.
clus.
orbit
GK
GRAM
0.105
0.002
0.013
0.287
0.011
0.025
0.009
0.016
w/o bias in feature extraction
0.111
0.001
0.009
0.287
0.006
0.007
0.016
0.016
w/o bias in edge estimation
0.247
0.272
0.190
0.306
0.066
0.037
0.038
0.017
B-A
Lobster
deg.
clus.
orbit
GK
deg.
clus.
orbit
GK
GRAM
0.034
0.009
0.024
0.015
0.001
5e-4
6e-5
0.049
w/o bias in feature extraction
0.034
0.020
0.033
0.016
0.003
le-4
2e-4
0.054
w/o bias in edge estimation
0.050
0.035
0.042
0.017
0.002
3e-4
8e-5
0.054
A.7.5 VISUALIZATION OF GENERATED GRAPHS
Visualizations of generated graphs each dataset shown in Figures T0 best). We used the same visualization method for all graphs. Different color corresponds to different node/edge labels each dataset.
L and 14 (color
The graphs generated by GraphRNN are quite similar to those in the training set terms of their topology. However, they completely failed to capture node/edge label patterns in most cases.
In contrast, the graphs generated by GRAM are similar to training samples in terms both topology and node/edge label pattens.
A.8 LIMITATIONS AND FUTURE WORK
While our models demonstrated superior performance on most of the datasets, they have some lim- itations. example, on inference, one wrong prediction of node/edge label may collapse all the following generation processes, resulting in bizarre graph generated. This is deficit of its rich fea- ture extraction process. possible solution to this problem is, for example, to employ beam search. By applying beam search inference, avoid the above undesirable situations.
get rid of samples with quite lower likelihood and
Additionally, although reduced the computational complexity of the models by a significant amount, the feature extraction process still requires large amount of computation. To this chal- lenge, some methods proposed in the field of image processing and natural language processing would help to alleviate it.
19

---

Under review as a conference paper at ICLR 2020
Train
GraphRNN
GRAM
Figure 10: Generated graphs (grid).
Train
GraphRNN
GRAM
Figure 11: Generated graphs (lobster).
20

---

Under review as a conference paper at ICLR 2020
Train
GraphRNN
GRAM
Figure 12: Generated graphs (community).
Train
NN
GRAM
Figure 13: Generated graphs (B-A).
21

---

Under review as a conference paper at ICLR 2020
Train
gad rogg Boof prog
GraphRNN
DeepGMG
GRAM
ddo
Figure 14: Generated molecular graphs.
22


Reviews:
[{"review_id": "rklrTtQRFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Response to rebuttal\n\nI would like to thank their authors for their rebuttal.\n\nAfter 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.\n\nIn 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:\n\n(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.\n\n(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).\n\n(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.\n\n(4) Finally, I did not see any error bars added to the main results in the paper.\n\nDespite 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.\n\n# Summary\n\nIn 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.\n\nIn 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.\n\nThe 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].\n\n# High-level assessment\n\nThe 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. \n\nHowever, 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.\n\nNonetheless, I believe the proposed approach is promising, and encourage the authors to address or clarify these issues during the author discussion phase.\n\n# Major points / suggestions\n\n1. The manuscript presents the proposed approach in a way that does not clearly differentiate between prior work and original contributions.\n\nIn 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].\n\nI 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.\n\n2. 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).\n\nFor 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.\n\nThe 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.\n\nFinally, 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.\n\n3. 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”. \n\nIn 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.\n\n4. Most importantly, I believe the experimental results are insufficient to back up some of the claims made in the introduction. \n\n    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]). \n\n    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.\n\n    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).\n\n   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.\n\n# Minor points / suggestions\n\n1. 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.\n\n# References\n\n[1] Li, Yujia, et al. \"Learning deep generative models of graphs.\" *International Conference on Machine Learning.* 2018.\n[2] You, Jiaxuan, et al. \"Graphrnn: Generating realistic graphs with deep auto-regressive models.\" *International Conference on Machine Learning.* 2018.\n[3] Veličković, Petar, et al. \"Graph attention networks.\" *International Conference on Learning Representations*. 2018.\n[4] Gretton, Arthur, et al. \"A kernel method for the two-sample-problem.\" Advances in Neural Information Processing Systems. 2007.\n[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.\n[6] Liao, Renjie, et al. \"Efficient Graph Generation with Graph Recurrent Attention Networks.\" *Advances in Neural Information Processing Systems.* 2019.\n[7] Kriege, Nils M., Fredrik D. Johansson, and Christopher Morris. \"A Survey on Graph Kernels.\" *arXiv preprint arXiv:1903.11835* (2019).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkxBHx7gcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nAlthough 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.\n\nClarification:\n1. What is the unit for time in Table 1 ? Is it inference time or training time ?\n2. 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.\n3. 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.\n\nConcern and Additional Experiments:\n1. 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.\n2. 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. \n3. Please include results on newer models pub lished at NeurIPS'2019 - Graph Recurrent Attention Network (GRAN) and Graph Normalizing flows (GNF).\n4. 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.\n5. 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 ?\n6. 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. \n7. 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.\n8. Please explain how Graph convolutional complements the processing in graph attention. Is both required ? Can you share ablation study on this ?\n\nMinor:\n1. The models categorized as unsupervised indeed trains using supervision of edge connectivity. \n2. Frist -> First", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "ByeCx3AAFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a formulation of graph generative models based on graph attention aimed at scalability of these methods.\n\nThe 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:\n\n1) 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?\n\n2) 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.\n\n3) 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.\n\n4) 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?\n\n5) 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.\n\n6) 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?\n\n7) 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.\n\nMinor 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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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