GG-GAN: A Geometric Graph Generative Adversarial Network
Authors: Igor Krawczuk
Pedro Abranches
Andreas Loukas
Volkan Cevher
Venue:  (2021)
Keywords: GAN
generative adversarial network
WGAN
GNN
graph neural network
generative model
graph

Abstract: We study the fundamental problem of graph generation. Specifically, we treat graph generation from a geometric perspective by associating each node with a position in space and then connecting the edges based on a similarity function. We then provide new solutions to the key challenges that prevent the widespread application of this classical geometric interpretation: (1) modeling complex relations, (2) modeling isomorphic graphs consistently, and (3) fully exploiting the latent distribution.
Our main contribution is dubbed as the geometric graph (GG) generative adversarial network (GAN), which is a Wasserstein GAN that addresses the above challenges. GG-GAN is permutation equivariant and easily scales to generate graphs of tens of thousands of nodes. GG-GAN also strikes a good trade-off between novelty and modeling the distribution statistics, being competitive or surpassing the state-of-the-art methods that are either slower or that are non-equivariant, or that exploit problem-specific knowledge.

Under review as a conference paper at ICLR 2021
GG-GAN: A GEOMETRIC GRAPH GENERATIVE ADVERSARIAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
We study the fundamental problem of graph generation. Specifically, we treat graph generation from a geometric perspective by associating each node with a position in space and then connecting edges in-between based on similarity function. We then provide new solutions to the key challenges that prevent the widespread application of this classical geometric interpretation: (1) modeling complex relations, (2) modeling isomorphic graphs consistently, and (3) fully exploiting the latent distribution. Our main contribution is dubbed as the geometric graph (GG) generative adversarial network (GAN), which is a Wasserstein GAN that addresses the above challenges. GG-GAN is permutation equivariant and easily scales to generate graphs of tens of thousands of nodes. GG-GAN also strikes a good trade-off between novelty and modeling the distribution statistics, being competitive or surpassing the state-of-the-an methods that either slower or that are non -quivariv,,,,,,, or that exploit problem-specific knowledge.
INTRODUCTION
Learning distributions from empirical observations is a fundamental problem machine learning and statistics (Goodfellow et al. 2014 2016
Salakhutdinov 2015 Foster 2019). A challenging variant entails modeling distributions over graphs discrete objects with possibly complex relational
structure (Simonovsky & Komodakis 2018 You et al.) 2018 De Cao & Kipf 2018 Liao al.,
2019: Niu et al. |020 Yang et al. 2019). When successfully trained, deep graph generative models carry the potential transform wide range of application domains, for instance by finding novel chemical compounds for drug discovery (De Cao & Kipf (2018), designing proteins that do not exist
nature (Huang et al. 2016), and automatically synthesizing circuits (Guo al. 2019).
By and large, there are four properties that a graph generator g should possess: (1) Isomorphism consistency: 9 should assign isomorphic graphs the same probability- property also referred to as permutation equivariance (Niu et al., 2020 Yang et al. 2019). (2) Expressive power: g should be able to model local and global dependencies between nodes and graph edges, e.g., going beyond simple degree statistics and learning structural features and motifs. (3) Scalability: should be able to
synthesize graphs with tens of thousands of vertices. (4) Novelly: g should produce non-isomorphic graphs that are similar to (but not necessarily in) the training set.
Property (1) is important since there exist exponentially many ways to represent the same graph as a vector, inconsistent methods effectively waste a large portion of their capacity in describing different ways to construct the same object. Properties (2) and (3) are critical in large-scale contemporary applications that require going beyond simple degree statistics well as learning structural features and motifs towards simultaneously modeling local and global dependencies between nodes and graph edges (You et al.) 2018). Property (4) is natural since common failure modes for graph generators include memorizing the training set and repeatedly generating the same graphs.
1.1 GEOMETRIC GRAPH GENERATION
Aiming to satisfy these properties, we propose a geometric generator that represents graphs spatially by embedding each node in a high-dimensional metric space and then by connecting two nodes if their positions are sufficiently similar. There is precedence to our approach, as spatial representations of graphs have been heavily used to construct simple models of random graphs, such as random
geometric graphs, unit-disc graphs, unit-distance graphs, and graphons (Huson & Sen [995 Penrose
et al. 2003. Bollobás et al. 2007 Lovász 2012 Alon & Kupavskii 2014
Glasscock 2015).

---

Under review as a conference paper at ICLR 2021
Surprisingly, these classical geometric approaches have far found limited adoption in the context of deep generative graph models. In fact, it is easy to verify empirically that a direct, naive application of these methods yields poor performance, requiring additional conditioning and other stabilizing procedures to train effectively (Yang et al. 2019; Serviansky et al., 2020).
Our work precisely bridges this gap, showing how deep geometric graph generation approaches can perform well. Our contributions are two-fold:
I. We shed light into the fundamental limits and challenges of geometric graph generators (Section 2) We derive sufficient conditions for representing graphs spatially and demonstrate that for sparse graphs the embedding dimension can depend only logarithmically on n. We then identify challenges that arise when building powerful and isomorphism-consiste consistent generators. Interestingly, we find that straightforward generators must solve non-trivial collision avoidance problem for every graph. We present evidence that such generators cannot be easily trained even in simplified supervised settings.
II. We avoid collisions at generation time, while retaining scalability and consistency (Section 3. We propose geometric graph generative adversarial networks (GG-GAN) with new twists. Our numerical evidence demonstrate that our proposed changes can have considerable impact on graph generation quality, and can capture complex relationships. Furthermore, GG-GAN is significantly faster that SotA (autoregressive) models, while also being competitive in terms of captured statisties and novelty. A case in point, our method can generate graphs of 10k nodes in ~ 0.2 seconds, which is 2 orders of magnitude faster than the fastest autoregressive method within the state of the art.
1.2 RELATION TO EXISTING WORK
We argue that despite the impressive progress so far, no current approach satisfactorily meets the four aforementioned properties. Isomorphism inconsistent methods (Kipf & Welling, 2016: You et al. 2018. (Bojchevski et al. 2018: De Cao & Kipf [0188] Liao et al., (019) tend to memorize the training set in the absence of problem-speciff rewards (De Cao & Kipf (0118). Autoregressive variants, in
particular, possess large expressive power, but are limited in scalability as they construct the graph
one node or block at a time (Bojchevski et al. 2018 Li et al. 2018, You al.
2018 Yang et al.
2019; Liao et al. 2019). Clever optimization and exploitation of sparsity can help (Dai et al. 2020 but only to a degree, as can be seen in our experiments.
The closest methods to ours are ScoreMatch (Niu et al. 2020), Set2Graph (Serviansky et al. 2020 and CondGen (Yang et al. 2019), all of which are consistent and non-auuoreeressive. Match samples graphs from learned score function via annealed Langevin dynamics, an approach that we find works well only for small graphs. CondGen combines a variational autoencoder (VAE) with a conditional GAN for improved training stability. NetGAN (Bojchevski et al. 2218)) while being pure GAN does not operate on distributions of graphs. Instead, it learns to generate random walks on single large graph using autoregressive generator and then assembles the graph from these random walks. TagGen (Zhou et al.) (020) uses a similar model on temporal interaction graphs, but instead of learning generator, trains transformer critic score random temporal walks and then samples from them in parallel via rejection sampling and assembling the final graph. Neither model directly captures& graph distribution, but only addresses the distributions of the random walks.
Our work alleviates the need for such modifications or indirect modeling, demonstrating that a pure GAN approach suffices when the generator has been set-up appropriately. Set2Graph also adopts geometric perspective to solve partitioning, Delaunay triangulation, and convex hull problems and not to generate graphs. By identifying and solving the collision avoidance problem, our work improves the efficacy of Set2Graph-type approaches, such as ours, in implicit deep generative modeling.
Notation. In the sequel, upper-case letters refer to sets, and bold-face letters denote vectors and
matrices. We represent any set X = {æI,..., . of n. points as a matrix X with each row corresponding to some point æ; in arbitrary order. Functions, such as neural networks, are denoted by lower case letters, such as f, Every undirected weighted graph G = (V, E, w) can be defined in terms of set of n = [V] nodes, a set of edges E with (v,, vy) E E if there exists an edge joining the i-th and j-th nodes, and a weight function w E + R4 indicating the strength of each connection. simple graph G = (V, E) is an undirected graph without weights. Finally, the symbol 6,, refers to the group of permutations on [n] (I,...; n.. All proofs are presented in the appendix.
2

---

Under review as a conference paper at ICLR 2021
db
Z1
g
909 2)
X
X2
X;
X3
X
(a)
(b)
Figure 1: (a) Methods that attempt learn mapping between random input Z [2] 2n and a target configuration X = [x1,-.. zn need to ensure that no two input points are mapped to the same oulput separately for each draw of Z. Learning to perform collision avoidance is non-trivial for permutation equivariant g. (b) We instead learn a distribution over functions (=e =) operating on a fixed point set o. Our method can learn to assign different role each point Φ; during training, side-stepping the need for collision avoidance at every random draw of z.
2 FUNDAMENTALS OF GEOMETRIC GRAPH GENERATION
This section recalls some basics of geometric graph generation, presents sufficient conditions for representing graphs spatially (Section 2.1). and identifies key challenges (Section 2.2) preventing their wide-spread application. Our observations motivate GG-GAN-pressee in Section
2.1 REPRESENTING GRAPIS SPATIALLY
We can represent graphs simply by placing n nodes in some metric space and then by connecting them if their position satisfies some notion of similarity (Huson & Sen 1995; Penrose et al. 2003 Bollobás et 2007 Lovász 2012 Alon & Kupavskii 2014 Glasscock 2015).
More concretely. let æ1..... be points in R We determine whether graph G = (V, E) of n |V| nodes contains edge (v., v;) E by testing if n(æ;, æz) = 1, for a similarity function k.
is not hard to see that this particular representation is completd oovr the space undirected graphs: every undirected graph can be represented by n points as long as is sufficiently large. For instance, æ; is chosen to the row the matrix square-root of the adjacency matrix of the graph G, and a(x;, x x; æt then the representation is complete if and only if k = n.
Surprisingly, the embedding dimension & can favorably depend on the sparsity of the graphs we wish to represent. Indeed, for simple graphs of degree most A, Maehara and Rödl showed that k = 24 dimensions suffice (Maehara RödI, T990). This theorem unfortunately relies on a discrete and non-differentiable similarity function k and only holds for graphs whose edges have no weights.
As shown next, the aforementioned issues can be overcome by relaxing the node degree dependency:
Theorem 1. Let G be weighted undirected graph with adjacency matrix A E [0, 1| and maximum (combinatorial) degree A. For any e E (0, 1). there exist points #1....; By R&* with O 2²"ogg for which (Aii,) ( 1)] S for all i +
Therefore, any weighted graph can be approximately represented by n points in at most k O(A² n/2) dimensions and this is possible using the differentiable function s(xr y) e 1.
2.2 CHALLENGES OF GEOMETRIC GRAPH GENERATION
In the following, we expose three key challenges inherent to geometric generators.
A vector representation of set is complete if and only if there exists surjective function between the representation vectors and the elements of the set.
3

---

Under review as a conference paper at ICLR 2021
2.2.1 THE CURSE OF INDEPENDENCE
The simplest way of constructing a generator is by sampling each point æ; independently from distribution Dz. We refer to this approach as random graph generation (RGG) (Penrose et al. 2003).
It is a direct corollary of our Theorem | that RGG can be used to generate any simple graph:
Corollary 1. Fix any weighted undirected graph G = (V, E) of degree at most A and let A be its adjacency matrix. For any e E (0, 1). there exists D, supported on E* with
O( 2 l
such that with strictly positive probability, Ai - (e = - 1) S for all + j.
In deep learning context, one may think of modeling D, by passing Normal distribution through a learned function, such as a multi-layer perceptron (MI.)): æ; = g(z)), where 2; ~ NO, m) for every i e [n] and with m being the dimension of the latent space. Unfortunately, as it shown next, such generators cannot satisfactorily control the probability with which each set is generated.
Proposition 1. RGG generates any {zI,...,, 2n with æ; + æj with probability most O(ne
Random graph generators are therefore weak since they sample every point in the set independently of the other points: the larger n is, the smaller the probability that some specific points are sampled.
2.2.2 MODELING ISOMORPHIC GRAPHS CONSISTENTLY
Naturally, can introduce dependencies between points by expressing the joint distribution Dx of X F1, nn E IR TRnk as the push-forward measure of a random E Raxm
x = g Z))
with Z = , xx] and z; ~ NO,,
or by generating each point sequentially conditioned on the previous by some autoregressive model (Li et al. 2018: You et al. 2018 Liao et al.] 2019). In theory, these generators are capable of approx- imating any joint distribution Dx. However, if not selected carefully, these models can waste an exponentially large portion of the generator's capacity in generating graphs that are just isomorphic.
To illustrate the problem, let consider the case where g is surjective function, meaning that for every X there exists Z with 2( = X. Then, a large subset of its latent space can be devoted to expressing different permutations of the same points:
XX Rax and G.,, 3Z, Z' Bank such that x 9 mg TX
where 6, is the group of permutations on [n]], with | different probabilities X and x xX, even if the corresponding graphs are simply isomorphic.
= n!. In other words, can generally assign
more appropriate class of functions are those that are equivariant to permutation:
Gn, have Proposition 2. If g is permutation equivariant, then for every X and Prob(X ~ Dx) = Prob ~ Dx).
The above observation is consistent with the findings of Yang al. (001)) Serviansky et al. (2020) also provides guidelines on how to construct such a function g.
2.2.3 AVOIDING COLLISIONS
While we seek an equivariant function that maps a random Z X, learning such functions can prove challenging even in toy examples (cf., Section 3.2). Intriguingly, difficulty has to do with ensuring that the points are mapped in an equivariant manner without collisions, i.e., with no two rows 2,, Rj of Z being mapped to the same output.
recognize that principal
For intuition, let us simplify the setting by supposing that we wish to generate the same fixed X for every random input Z. Function g achieve this task in two ways: (1) it can memorize the output by disregarding its input, or (2) it can learn to transform each row of to one of X. Geometrically, fixed final target. For instance, could select an assignment t: [n] + [n] and match every z; to a target position Zz(()- with t(i) * t(j) for each j.j. Even though the aforementioned procedure is only an example, we note that any successful g that does not disregard Z should implement some collision avoidance mechanism (implying in turn the existence of an assignment t)- -ttheewiis,, g cannot ensure that two
the latter corresponds to moving points from a random initial position
different input points 2, and zj will not collide onto the same target position.
4

---

Under review as a conference paper at ICLR 2021
0.5
0.5
0.3
rendom
0.4
0.4
rendom context
0.4
0.3
0.2
0.2
-0.1
50
150
50
150
(a) PointMLP
(b) PointNeuST
(c) Self-Attention
Figure 2: Mean-squared error per training step for three permutation equivariant networks tasked with generating single target X. Even with direct supervision, the networks do not learn when starting from randomly drawn points Z (random set-in green). The task is easily solved when starting from a fixed point set 4 and random vector z (random context-in orange).
Unfortunately, we argue that both these behaviors are unlikely to be learned in practice: In the first case, one has learn ignore any spurious relations that are induced by the random input, In the second case, due to being permutation equivariant, 9 can rely on the position 2;, 2j and not the order j.j of the random points to tell them apart. As such, the combinatorial collision avoidance problem needs to be solved anew every time that the points change, i.e., for every generated graph!
Section D presents a geometric graph generator that cireumvents these difficulties by allowing the generator to solve the collision avoidance problem at training time, rather than once for every input.
GG-GAN: A GEOMETRIC GRAPH GENERATIVE ADVERSARIAL NETWORK
We adopt the Wasserstein GAN framework (Arjovsky et al. 2017 to learn an implicit generative model (Goodfellow et al., 2014). Our GG-GAN consists of geometric generator Igy and graph neural network discriminator dgs. as discussed in Sections 3.1 and 3.3 respectively. GG-GAN is isomorphism consistent, scalable, and it avoids the need for collision avoidance at every input.
3.1 THE GEOMETRIC GRAPH (GG) GENERATOR
The generator of our GG-GAN maps set of points from an initial configuration to target position in permutation equivariant manner. However, to avoid solving a collision avoidance problem for every input, retain the initial points at fixed, non-random positions, while using random context vector to determine the type of graph to be generated. Notice that, rather than attempting to learn to transform one distribution over sets to another,
instead learn distribution over functions conditioned on a deterministic input in a manner similar to conditional GAN - though, in contrast the latter, also learn the fixed input during training.
Figure D illustrates that to generate a graph G of n nodes, our generator takes as an input a fixed learned set (e...... .n. of points Rd and vector sampled from a Normal distribution:
95z 1 2), where z z~ ~~000 Ig),
and Raxd is the matrix representation of set &. Then, determined from X, by sampling each edge (ve, Uz) from a Bernoulli random variable with probability <(z;, axx æz)) where is the standard sigmoid function. We stress that this approach can allow for arbitrary dependencies between edges: though any two edges become independent conditioned on a specific the random variables can feature arbitrary dependencies overall, e.g., by setting k(x,, x3) = k( 2.)) = for some z and zero otherwise the two edges will always appear together.
The gradient of the non-differentiable sampling step is approximated using straight-through through estimation samples from concrete distribution (Bengio et al. 2013 Jang et al., 2016 Maddison et al., 2016). similar to the Gumble-softmax trick used in De Cao & Kipf (2018). When applicable, one may also read out node attributes by using MI. independently each row of X.
5

---

Under review as a conference paper at ICLR 2021
To generate graphs of different sizes, we model n categorical random variable in [Mmins Mmax and fix to contain n points from {ø1..... Dn... 7. The parameters of the categorical distribution, including miin and maxx directly estimated from the training data.
To implement 9gg. we concatenate x with every Φ and process the resulting matrix with a permutation equivariant function: X = Ies (P|==) with e 1|= = [(01llz)..... (Φ.. [|] Different choices are possible on how to instantiate 9øz- For instance, 92x could be parametrized by PointNetST network, which is a universal approximator over the space of equivariant functions (Segol & Lipman 2020).
or based on the constructions of Keriven & Peyré (2019) and (Sannai al. (2019). Inspired of the success of attention for set- eat-bsed tasks, we use a deep self-attention network.
Let us further justify our generator using the following properties. Expressive power: By construction, our Aee can learn to model dependencies between output points, enabling it to control the probability with which each graph is generated (see Section 2.2.1 Isomorphism consistency: By Proposition 2 using an equivariant function Igg ensures that isomorphic graphs are always sampled with equal probability (see Section 2.2.2). Collision avoidance: Since deterministic by construction, our generator can avoid collisions by prescribing a different role to each input point Φ; There is no need to determine an assignment from & X every time that a graph generated (see Section 2.2.3). the assignment can be determined once during training.
3.2 AN ILLUSTRATIVE TOY EXAMPLE: LEARNING TO GENERATE A TARGET SET OF POINTS
To highlight the impact of using fixed vs random points, we perform the following toy experiment.
We generate a single target X and use equivariant neural network determine a mapping that can transform any random set Z of points to X, or specifically, 2; - Z;. As shown in Figure 2 standard permutation equivariant architectures (an MLP applied independently on each point, PointNetST (Segol & Lipman 2020), and multi-head attention (Bahdanau et al. 2014 Vaswani ct al. 2017) fail to learn such a mapping.
In contrast, if the random input Z becomes fixed and the randomness is conditioned to a context vector, all networks easily solve the task. An obvious caveat is that generator using fixed & can learn to completely ignore the context vector and instead learn only a fixed number of graphs. We show in Appendix B that this does not happen in practice: when trained on a proper generative task, our generator indeed learns to generate different graphs for different context vectors.
Nevertheless, instead of relying on a single matrix 4, is also possible to learn a small set of such matrices and present them to the generator in batch form. In our experiments, we learn batch of 20 such matrices. We determined this change to beneficial in encouraging the learned model to find different X that fool the discriminator, and hence, to obtain a higher novelty.
3.3 THE GEOMETRIC GRAPH DISCRIMINATOR
In a Wasserstein-Gan -AN framework, the discriminator is critical in the approximation of the Wasserstein distance. For this purpose, use message-passing neural network (MPNN) discriminator dgg- Since MPNN without node attributes are known to be blind to many relevant properties of graph's s structure (Xu al. 2019: Morris et al. 2019 Chen al. 2020), similar to previous works (De Cao & Kipf 2018 Yang et 2019),, we increase the discriminative power of dzz by adding specially selected node and graph features. Adding node attributes can enhance expressive power, even rendering MPNN universal in the limit under a uniqueness condition (Loukas) 2019).
In particular, we build e attribute vector by appending to the corresponding node's 's degree the first k entries (i,: k) of the i-th row of the Laplacian eigenvector matrix, which is sorted in increasing order. Using spectral features has empirically been shown to boost performance (Dwivedi et al. 2020) and it also acts as symmetry- breakkng mechanism. We further aid the discriminator by explicitly providing it with k-cycle counts (3 < k < 5) as well as the number nodes present in the graph currently evaluated. Cycles a prominent graph feature that standard MPNNs cannot distinguish. Both eigenvectors and cycles are computed a differentiable manner during the forward pass. For further details about the discriminator architecture, refer Appendix D.4
Although, from a pure deep learning perspective, using handcrafted features is undesirable, to our knowledge, universal and efficient equivariant graph classifier currently exists: MPNN is

---

Under review as a conference paper at ICLR 2021
Molgan QM9
CommunitySmall 20
Chordal9
Models
Deg.
Clust.
Cycle
AC
DA
Deg.
Clust.
Cycle
AC
Deg.
Clust.
Cycle
AC
DA
MMD threshold
0,0050
0.1649 0.1 167 0.0784 0.0359
2.71 0.0013
1.17E-8 0.0012 0.0002
0.0404
0.0090
0,0670
0.0500
0.1348
MolGAN (RL)
0.0054
0.0560
0.0234
0,1317
0.0342
MoIGAN (no RL
0.0045
0.1830
0.0676
0.1194
0,0866
gNaphR
0.0046 0.1514
0.1257
0.0675
0.0402
0.0008
0.1723
9.5E-6
0.0136
0.0676
0,0463
0.0120
0.0875
0.0492
0.1460
Erdōs: Rényi
0.0438
0.3252
0.2221
0.6575
0.0349
0.0338
0.4421
0.0076
0.7847
0.4624
0.0204
0.0158
0.0396
0.0607
0.1304
Rarahusi-Albert
0.2245 0.0101 0.3667
0,098D
0.1378
0. 1940 0.4773 0.0003 0.9799 1.3517 0.0375
0.0138
0.0274
0.2627
0.0074
SerMatch
0.0638 0.1689 0.06066
0,1412
0.0944
0.0034
0.4181 0.0004
0.5940
0.3152 0,2032
0.0603
0.2929
0,1518
0.9974
CundGEN
0.0954 0.3970 0.5427
1.2002
0.1485
0.1497
0,4759
0.0180 1,1582
1.2712 0.0325
0.0095
0.0147 0.5522
0,0342
PointMLP-GAN
0.0126 0:0614 0.0350
0.1059
0.0602
0.0254
0,4594 0.0015 0.8104 0.3862 0.0260
0.0524
0.0795 0.1235
0.2988
GG-GAN (RS)
0.0143 0.0145 0.0255 0,2992
0.0084
0.0354
0.4339
0.0001 0.6755 0.3968 0.0267
0,0110
0.0219 0.1864 0.2487
GG-GAN
0.0043 0.0703 0.0152 0.0338 0.0065
0.0080
0.4258 0.0003 0.2553 0.3454 0.0391 0.0145 0.0329 0.0411 0.1659
Table 1: Comparing GG-GAN to SotA methods in graph generation. The reported scores (lower is better) measure the MMD between the graph statistics of 512 test and generated graphs. The MMD threshold measures differences between training and test sets; it aims to quantify how small "good" score should be. Green indicates a score not larger than the MMD threshold, and larger scores are annotated with a color gradient from yellow to red (in regular increments up max MMD of 1).
GG-GAN
GraphRNN
GG-GAN (RS)
ScrMatch
CondGEN
Figure 3: Examples (non- hondhhedd of generated graphs on the QM9 dataset. Novel graphs in green, graphs found the training set are in orange, and duplicates are grayed out. GG-GAN exhibits higher novelty than all methods that capture the QM9 distribution (see also Figures and 7
not universal, adding node attributed breaks equivariance, and because more powerful equivariant classifiers manipulate higher-order tensors (Maron et al.) 2019 Morris et al. 2019 Vignac et al. 2020) they carry increased computational and memory requirements. We expect the further advances on GNNs to improve framework and to eliminate the need for handcrafted features.
4 NUMERICAL EVIDENCE
We evaluate GG-GAN's performance to correctly model the distribution statistics as well as to generate novel high-quality graphs. We proceed in three veins, testing how well generators can model complex dependencies, how well generators can scale, and how well generators can identify novel objects, respectively. Consistent with previous works, we focus on the QM9 (n 9) and Community (n 20) datasets. We also introduce the Chordal (n 9) dataset. All three datasets are of small size. which allows us to compare even with the slowest baselines, whose descriptions are in Appendix C.2
4.1 MODELLING COMPLEX DEPENDENCIES
Building the evaluation protocol of You et al. 2018), we computed the maximum mean discrep- ancy (MMD) over 5 standard graph statistics defined in Appendix C.3,, degree distribution (Deg.), cycle distribution (Cycle), clustering (Clust.), algebraic connectivity (AC), and degree assortativity
7

---

Under review as a conference paper at ICLR 2021
Molgan-QQa. QM9
CommunitySmall-2
Chonda19
Models
isomorphism classes
isomorphism classes
isomorphism classes
MoIGAN
318
MolGAN (no RL)
182
graphRNN
132
4200
178
SerMutch
101
5000
12
PointMLP-GAN
26
1474
13
GG-GAN
832
5000
232
Table 2: Number of isomorphism classes not in the training set found within a sample of 5000 generated graphs (higher is better). We report novelty for generators producing graphs with reasonable MMD scores. Chordal9, we verify whether the generated graph is chordal and different from the training set (rather than a direct comparison with the test set).
coefficient (DA). We argue that good generative model should generally score sufficiently well across all MMDs. In our experience, even failing to capture single statistic can lead to generating graphs with significant visual differences from the dataset. To specify what "sufficient well" means, set threshold the MMD between the training and test sets: If generator is close to this threshold, then we say that it captures well a given graph statistic.
Table 1 summarizes
results. As observed, GG-GAN is the model with the most MMD values below the defined threshold, scoring below or equal to the threshold in out of 15 cases (with the second best model achieving good MMDs in 5 out of the 15 cases). This indicates GG-GAN can model well both simple and complex graph statistics. Intriguingly, no model can achieve results below the threshold in the Community dataset, although such dataset is simple and can, theoretically, be modeled exactly with an MLP acting independently on each point (PointMLP-GAN)
In fact, in the Community dataset, the latter achieves poorer performance than GG-GAN, and both are surpassed by graphRNN, perhaps since the latter is trained using a fikelihood-base loss (rather than implicitly as GANs do) which fits well to a random graph with communities. GraphRNN's good overall MMD scores agree with our intuition that autoregressive approaches are capable of modeling complex struetural dependencies. On the other hand, MolGAN generally apt at generating molecules, but its performance can change when the custom reinforcement learning (RL) loss is not utilized. Morcover, MolGAN's specialized architecture is not applicable to non non-molccular data.
To illustrate the effect of collision avoidance, also compare GG-GAN with an ablated random set (RS) version. The latter is identical to GG-GAN in all aspects except that the input set contains points sampled from Normal distribution (i.e., rather than having fixed set and random context). As seen, though the RS version can model excellently simple statistics (like DA and Clust.). it struggles with more complex ones, such AC. Figure visually demonstrates the importance of reproducing all graph statistics (rather than some): whereas the graphs generated by GG-GAN RS differ from those in the dataset, GG-GAN manages capture both local and global topological properties.
4.2 GENERATION NOVELTY
We verify how well the trained generative models can synthesize unique graphs. Specifically, we study the number of isomorphism classes generated that differ from those in training set. Table 2 shows that most models struggle to attain a high novelty score within a sample of 5k graphs. We see that the majority of generated graphs either belong small of isomorphism classes or duplicate the training dataset. GraphRNN, in particular, does not exhibit high novelty in our experiments. This provides evidence that the low MMD scores of graphRNN can (at least partially) be attributed to the training set. Perhaps due to not being isomorphism consistent, MolGAN achieves low novelty, though we observe boost via the RI. module.
Barning-to-memoote
It is also important to note that attaining high novelty score is challenging only for methods that can closely fit MMD statistics-eleate it can be trivial to generate novel graphs, if they share few things in common with the distribution of interest, For this reason, we left CondGEN and GG-GAN (RS) out from the comparison- as seen in Figure most graphs that these methods generated in our experiments statistically and perceptually stood out significantly from the training distribution. On the other hand, GG-GAN's novelty surpasses or matches that of all other methods, while simultaneously achieving competitive MMD scores.
8

---

Under review as a conference paper at ICLR 2021
10a
generation time (seconds)
103
10a
CondGen
GG-GAN
10:4
GG (spu)
GRAN test.)
10-3
bigg (plat)
graphRNN
2500
3000
7500
10000
19500
1500
17500
20000
Nodes
Figure 4: Median generation times for individual graphs of increasing size (lower is better). Dashed lines indicate that the timings are based on reports of previous papers. GG-GAN outperforms autoregressive baselines and the non-autoregressive CondGen by one more orders of magnitude.
4.3 SCALABILITY
Since real life graphs often have orders of thousands or even millions of nodes, the scalability of any generative method is critical. Specifically, graphRNN, GRAN, and bigg Youu al. 2018 Liao et al.) 2019 Dai et al. 2020) aim to push the previous SotA in terms of graph size.
We test our method against CondGen and graphRNN on the same machine we our models on and (due to time constraints) estimate the GRAN timing based on the speedup reported in Liao et al. (2019). For bigg, we extracted their reported timings from their figure 6 using WebPlotDigitizer (Ro- hatgi 2020). We perform all measurements by initialising the model and then generating number of N random graphs (N=100 for ours, N=20 for graphRNN) using an untrained model. We report sizes until n 20k, at which point our model runs out of memory.
Figure demonstrates that our model highly efficient, outperforming graphRNN, the estimated GRAN, and even bigg in terms of inference speed even when it is run CPU. CondGen is competitive with our model on CPU (the publicly available version actually performs the conversion of embeddings into graph CPU) which is not surprising since it is also non-autoregressive model.
We also highlight that the released version of CondGen has over 100x less parameters than our model. Nevertheless, since ConGen also aon-autoregressive and uses outer-product kernel to generate adjacency matrices, in principle it scales with O(n?), similar to GG-GAN. It might be interesting to note that Dai al. (2020) in theory scales better than our method due impressive optimizations exploiting sparsity, leading to O(mm + n) log n) scaling for n nodes with m edges. However, for the graph sizes tested, the constant factor incurred by either their framework their implementation seems to be significant enough that we still outperform them in terms of generation speed. We also highlight that the superior speed of GG-GAN is a consequence of our generator's parallelizability and not consequence of specialized optimization and engineering.
CONCLUSIONS
Our work partakes in the geometric graph generation research thread and advocates for learning distribution over functions rather than transforming a distribution over points. Our methodology yields an isomorphism consistent generator that, empirically confirmed, possesses favorable scalability, novelty, and expressive power, matching or surpassing various SotA baselines in most cases.
key direction that would like to focus in the future scalability. Herein, we rely the multi-head attention of Vaswani et al. (2017) that scales with O in compute and memory. More recent work (Wang al.) 2020 Shen et al., 20188] Katharopoulos al.) (2200) has reduced this complexity to nearly (n) while maintaining performance, implying low hanging fruit in additional efficiency gains. We are also interested more sophisticated generator architectures that exploit sparsity, possibly using insights from Dai et al. (2020).
Thee report 6x speedup w.r. to NN at quality parity GTX 1080Ti. We round this up 10x speedup in an attempt he as fair as possible (to account for modern hardware).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Noga Alon and Andrey Kupavskii. Two notions of unit distance graphs. Journal of Combinatorial Theory, Series A, 125:1-17, 2014.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223, 2017.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate, 2014. cite arxiv:1409.04730ommo oral presentation.
Accepted at ICLR 2015 as
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner,, and Stephan Günnemann. Netgan: Generating graphs via random walks. arXiv preprint arXiv:/803.0m /803.00816 2018.
Béla Bollobás, Svante Janson, and Oliver Riordan. The phase transition in inhomogeneous random graphs. Random Structures & Algorithms, 31(1):3-122, 2007.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint arXiv:2002.044023 2020.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. arXiv preprint arXiv:2006. /5502 2020.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprini arXiv: 11973, 2018.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Paul Erdös. A. rényi, "on random graphs,". Publicationes Mathematicae, 6:290-297, 1959.
WA Falcon. Pytorch lightning. GitHub. Note: http:///tthh...oooyyyymmimiimmmh
3, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
David Foster. Generative deep learning: teaching machines paint, write, compose, and play. O' O'Reilly Media, 2019.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. varia- tional inequality perspective generative adversarial networks. arXiv preprint arXiv: 1XXv:1802.1105/ 2018.
Daniel Glasscock. a graphon? Notices of the AMS, 62(1), 2015.
Ian Goodfellow, Jean Poudic-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Process- ing Systems 27, pp. 26800 Curran Associates, Inc., 2014.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville, Improved training of wasserstein gans, 2017.
Tinghao Guo, Daniel Herber, and James T Allison. Circuit synthesis using generative adversarial networks (gans). In AIAA Scitech 2019 Forum, pp. 2350, 2019.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision, pp. 630-645. Springer, 2016.
10

---

Under review as a conference paper at ICLR 2021
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks, 2018.
Po-Ssu Huang, Scott E Boyken, and David Baker. The coming of age of de novo protein design. Nature, 537(76200:32--377, 2016.
Mark L. Huson and Arunabha Sen, Broadcast scheduling algorithms for radio networks. In Proceed- ings of MILCOM'S '95, volume 2, pp. 647-651. IEEE, 1995.
Eric Jang. Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. 2016.
A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In Proceedings of the International Conference on Machine Learning (ICML), 2020. URL https://aaxxiii org/ abs /2006. 16236
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, pp. 7092-7101, 2019.
Thomas N Kipf and Max Welling, Variational graph auto-encoders, In NIPS Workshop onBayesian Deep Learning, 2016.
Klaus Greff, Aaron Klein, Martin Chovanec, Frank Hutter, and Jürgen Schmidhuber. The Sacred Infrastructure for Computational Research. In Katy Huff, David Lippa, Dillon Niederhut, and M Pacer (eds.). Proceedings of the 16th Python in Science Conference, pp. 49 - 56, 2017. doi: 0at0000/hinnma774666------
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems, pp. 4255 4265-4265, 2019.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. International Conference on Learning Representations, 2019.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Chris J Maddison, Andriy Mnih, and Yee Whye Tch. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.00m 2016.
Hiroshi Maehara and Vojtech Rödl. On the dimension to represent a graph by a unit distance graph. Graphs and Combinatorics, 6(4):365-367, 1990.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019.
Brendan McKay. chordal graphs, 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permu- tation invariant graph generation via acore-based generative modeling. volume 108 of Proceedings of Machine Learning Research, pp. 4474 4484, Online, 26-25 28 Aug 2020. PMLR.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein. Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, nigh-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'lché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035, Curran Associates, Inc., 2019.
11

---

Under review as a conference paper at ICLR 2021
Mathew Penrose et al. Random geometric graphs, volume 5. Oxford university press, 2003.
Henning Petzka, Asja Fischer, and Denis Lukovnicov. On the regularization of wasserstein gans, 2018.
Ankit Rohatgi. Webplotdigitizer: Version 4.3, 2020.
Ruslan Salakhutdinov. Learning deep generative models. Annual Review of Statistics and Its Application, 2(1):361-385, 2015, doi: 10.1
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant / equivariant functions by deep neural networks. CoRR, abs//903.00199, 2019.
Nimrod Segol and Yaron Lipman. On universal equivariant set networks. In International Conference on Learning Representations, 2020.
Hadar Serviansky, Nimrod Segol, Jonathan Shlomi, Kyle Cranmer, Eilam Gross, Haggai Maron, and Yaron Lipman. Set2graph: Learning graphs from sets, arXiv preprint arXiv:2002.08772, 2020.
Zhuoran Shen, Mingyuan Zhang. Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities. CoRR, abs/1812.01143, 2018. URL http:://axiv..r..///
abs abss/812.. 01243
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks, pp. pp. 412-422. Springer, 2018.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Santosh S Vempala. The random projection method, volume 65. American Mathematical Soc., 2005.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. arXiv e-prints, pp. arXiv-2006, 2020.
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In Advances in Neural Information Process- ing Systems, pp. 1340-1351, 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. ICML, 2018
Dawei Zhou, Lecheng Zheng, Jiawei Han, and Jingrui He. A data-driven graph generative model for temporal interaction networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery amp; Data Mining, KDD '20, pp. 401-411, 1,, New York, NY, USA, 2020. Association for Computing Machinery, ISBN 9781450379984, doi: 10.1 10.1145/3394486.440000 3403002..
http:: / /oi 11tp://.....1113333313 htttpp///oll.oogg10111/////33350
3403082
12

---

Under review as a conference paper at ICLR 2021
A DEFERRED PROOFS
A.1 PROOF OF THEOREM 1
For completeness, before presenting the proof, we restate the Theorem of Machara and Rödl showing
that 1: 2A dimensions suffice (Maehara Rödl 1990):
Theorem (Machara and Rödl (Machara & Röd! 1990)). For every undirected simple graph G of degree at most A, there exist points 21..... In in Rº with 2A, for which k(z;, 1 if and only if (Na, U/) E E,, i.e., k(x;, 2.y) = 1 (mTa,= =) where 1 is the indicator function of set C.
We move on to our proof. Let q be a function that strictly increasing and X-Lipschitz. We consider the matrix C with entries given by the following expression:
((i,)) = (A((i) + +n) and A(i.j) 9CC((i,) -1
for 1 = (()). If ((i E [0, 1], we then also have
0 = 9- (n)
min q (a) S C(i,)) max dEly,1tyl
= c.
Denote by U the eigenvalue decomposition of C and write
C=XX 7I, with X U(A + 1) Tx
and ||C||2 This is always possible since U(A + UAU + + 7 is, by the choice of % positive semi-definite.
= -
If we think of the rows 21 21...., In of X as points, have
| max A(i,)) 2|| S 2 max Σ ((..)) = max
Σ j=1
1 (A(i, 2cA.
To proceed, we rely on the following well-known property (Vempala 2005 If o. Rx; and R is k x n random matrix whose entries are independently sampled from N (O, Vk ). then for any n points
F Ti.... En E R with |ı>,1 6, have
(- (t2 ((-
P([x) x, a 2z 2 t8) 4n² exp
for all i,j .2.
4
follows by the probabilistic argument, that choosing k: = (oog(2n) with s(1) = 12 - 13 suffices for d())
some points Ii,..., Fn exist IR for which |æ._ æ, x. x3 S t5.
In this manner, we work backwards and consider the matrix with elements C(i,)) क.. 2; - % which approximates C' as follows:
||C -Clo = XX XX 11 S (2cA)t.
For the matrix with elements A(i,j) = (((,,)) we have
A A oo max [Iq(C(i,,))
(q(C(i.))) m) 11 I
S {2AcAA..
Selecting f 2 then yields l:
8 llg(2n) #(e/(2XeA)) and A AAlloo Sc
Let us now consider the shifted exponential function <(x,, xTy) = e² - We set q(x) o² for which 7 = (0) 1 and -1 7) log(2). Moreover, within the domain |0, c] of interest, the Lipschitz constant of g is given by X = ec = 2. Substituting the above to the bound gives 32g k (T) The proof concludes by noting that function & is lower bounded as f2 in the domain of interest.
13

---

Under review as a conference paper at ICLR 2021
A.2 PROOF OF COROLLARY
The proof follows trivially by selecting D, to have uniform measure on the points that give rise to the graph according to Theorem A more detailed analysis of the probability in question can be found in the proof of Proposition
A.3 PROOF OF PROPOSITION
Let X = (æ1...... In be the set that we wish to generate and denote by D the distribution in R that the random generator is induced from (with m = k). Write also as p; Prob(x; ~ D) the probability that the i-th point is drawn from D,..
The probability that X sampled is given by
Prob (X ~ Dz) =
Σ Pr. ... Ps. n! II Pi
where т is an element of the permutation group 6, on elements. The above (log) product is bounded by
Σ Pi S log (
log II
Pi
logp: S n log
where the first inequality follows by Jensen and the second is because >; S 1. Thus, employing Stirling's approximation we obtain
log (Prob(X ~ -D))) < log (n!) log
n(logn n 1) + Oloo n) log
n + O(logn))
which implies that there exists a constant c for which Prob XX ~ D.)) S one as needed.
A.4 PROOF OF PROPOSITION
To prove the proposition it suffices to show that Prob (n x)) Prob(X) for any permutation æ and any X g(Z).
The probability any to be sampled can be expressed as
Prob / ((((Z) = x) Prob Z) dZ.
where 1 (g(Z)= x) the indicator function of event gZZ) X and the integration is over all Z. Similarly, we have that
/ 1(9(Z') +X) Prob(22 (z') dz'
Prob(T
/ (0((TZ) = x Prob ( dZ
(by the substitution Z' = Z)
/ (0((TZ) X) Prob dZ
(since Prob (Z) Prob (1 Z))
= ((g(Z) = X) Prob Z) dZ
(g is permutation equivariant)
Prob(X),
where the second equality is true since Z = Z is an isometric mapping and (gg(-) = =XX Prob(.) real-valued function.
14

---

Under review as a conference paper at ICLR 2021
QMB
Community
Chordal
GG-GAN
GG-GAN Insex
GG-GAN batch index 5
GG-GAN 10
Figure 5: Random sampled graphs from GG-GAN, and GG-GAN at specific batch indices.
B BATCH INDEX DIVERSITY
As we discussed the main text, GG-GAN learns function distribution operating on fixed batch of point sets. One possible failure mode of this approach is that the generator might learn to ignore the randomly drawn context and simply learn a single fixed mapping for each batch index of the fixed embedding.
To confirm that this does not happen in practice, we sampled graphs from our generator and checked for diversity within the samples drawn from each batch index (0, 5, 10) across the samples. The results are shown in Figure S Notice that if the generator were to ignore the context vector, we would expect diversity on each batch index (i.e., for the same fixed )) across samples. However, be seen in the figure, for the QM9, at batch index a circle structure appears to be learned, but overall there is diversity within samples in the same batch for all datasets.
15

---

Under review as a conference paper at ICLR 2021
C EXPERIMENTAL DETAILS
C.I HYPERPARAMETERS
The hyperparameters used in our experiments can be found in Table The basclines were run with code provided in the respective papers, see Appendix D.I ExtraAdam Gidel et al. (2018) was used for both generator and discriminator with the following parameters: 1r=1e-4, betas= (0.5, 0. 9999), eps=le-8, 8, wttgghhteeayyeeeee 3, ema-False, miaastart=100 using standard 5:1 ratio of discriminator to generator updates.
Molgan- QM9
CommunitSSmll--20
Chordal9
Params.
PoinMLP
GG-GAN
PointMLP
GG-GAN
PoinMMLP
GG-GAN
Batch size Attention layers
20
20
20
50
25
25
Context size
50
25
25
MI.P layers
[128,256.512]
[128,256.512]
[128,256,512]
Optimizer
ExtraAdam
ExtraAdam
ExtruAdam
ExtraAdam
ExtraAdam
ExtraAdam
Table 3: Hyperparameters used in the experiments for PointMLP and GG-GAN
Table summarizes the hyperparameters used for our discriminator (see Table D.4 for an explanation of the architecture) throughout all our experiments. T. refers the number ResBlocks in the
DenseGIN, o, is the hidden layer of the final readout MLP, d is the output node feature dimension of the ResBlock I, ct and c, analogously refer to the input features of each ResBlock and the width of the hidden layer of the SkipGINs inner MLP respectively.
L
%
ResBlock Parameters
7
128
9, c, 64, co
[32, 64, 64, 64, 128, 128), dt d-11
Table 4: Discriminator hyperparameters for experiments
C.2 DATASETS
QM9. The QM9 dataset contains 133,885 organic compounds. Following De Cao & Kipf (2018).
experiments focused 5k subset. Most of the graphs in this dataset have 9 nodes.
Chordal. A graph is chordal every cycle of length at least has an edge connecting two nodes of the cycle, but is not of the cycle itself. This dataset (McKay) 2020) contains 11911 chordal graphs of size 9, from which we also use 5000 subset for training and the rest 6911 for test.
Community.
Similarly to Niu al. (2020), construct 5000 N=20 node graphs containing communities generated by the Rényi model Erdös (1959) with p = 0.7. Then, 0.05 edges added between the communities.
C.3 MODELING COMPLEX DEPENDENCIES
We first define the five discrete distributions that the MMD scores are based on:
The degree of a node is the number of connections it has to other nodes. The degree distribution the probability distribution of these degrees over the entire graph.
Degree distribution.
Cycle distribution. A cycle is non-empty sequence of adjacent nodes in which the only repeated vertices are the first and last vertices. The cycle (length) distribution is the probability distribution of the lengths of all cycles within graph.
Clustering. The clustering coefficient of node is the fraction of all possible triangles through that node that exist in the current graph. The clustering (coefficient) distribution is the probability distribution of the clustering coefficients of all nodes within graph.
16

---

Under review as a conference paper at ICLR 2021
Algebraic connectivity. Algebraic connectivity refers to the second smallest eigenvalue of the combinatorial Laplacian matrix the graph.
Degree assortativity coefficient. The assortativity coefficient is the Pearson correlation coefficient of degree between pairs of linked nodes.
Melga-QM0 QMO
CuamuniySmall-30
Sest
0,0049
0,07404
0.1212
0.0722
0.04236
2.36E-05 D5
2:64-009
9.1E 10
0.0002
0.0002
0.0404
0.0154
0.0670
0.0800
0.1348
0.0056
0.107%
0.1171
(089)
0.0308
8-98-006
2676-08
9-11--1
00031
0.800
Text vet
0,0052
0,0836
0.1118
00590
0.0347
4.365-05
3606-09
3.426-88
0.001
0.000
Table 5: MMD results between the training set and the test sets used.
QM9
Community
Chordal
Dotatet
GG.GAN
GraphoWN
ScrMarch
CondGEN
Figure 6: Random sampled graphs from the models and training dataset.
17

---

Under review as a conference paper at ICLR 2021
Deg:
Clust.
Cycle
Graphs Dataset
Iso.
Molgan-QM9
GG-GAN
0.0063=000029
0.0763=000045
0.0158=00.0099
0.0226:0.0124
0.0212=00.104
1465 67:6661::144444
721.0=233244
AG-GANBE
0.019610.0029
0.011110.0042
0.030710.00035
0.0122::0.022
204.99
PointMPP
0.0104=000032
D.0261=0.0051
0.0403=0000998
0.059
0.057=#0.027
1667.0+422.44
20.33++1.70
PoinMLPP RS
0,004=00.004
0.0425=0000144
0.0525=0.0026
0,1954+0.005
0.0229:000055
474. 374.334-22.66
1451.67=17.44
CommunitySmall-20
GG-GAN
0:44990001228 0.05055000255
000023:0.0019
0,491+00:185
0.5085=00.17 173
0:0000000
4729.33---2 33..333--88777
GG-GAN RS
0.059510.0228
0.4386:0.012
0.000510.0004
0.5757=0.1917
149
0.0010.00
1999.67.10.47
PoinMMP
0.0821 +0.066
0.499:50.0096
0.0053=0.006
0.7704=0.0668 0688
0.3754=0.1071
0.00=0000
2286. 13:2.33--10.999
PointMLP RS
0.0021000094
0.4405:000077
0.01 36:00.005
0.808300011
0.2969:00936
0000:0.00
5000+0
Cherdal9
GG-GAN
0.088510.0007
0.117710.004
0.050410.00199
0,047910.005
0.1895:0.0227
2471 0371.334344.98 7,88
248.67=135.49
0003333-79..8
724.0-74.25
PointMLP
0.0938:00.022
0.0702::0.0105
000011
0.1978:000400 04077
0.0826::0.0201
462.67+212.57
6.67=5544
PoinIMLP RS
0,8453+0.0035
000155=000066
0.028+0.0018
0,1205=000143
0.234700.0108
313.0
856.33+22678
Table 6: Comparison between random context (RC) and random set (RS) models. The mean and standard deviation correspond to the results of 3 of the same model. We also report the generated graphs in the dataset and the isomorphic classes of such models.
MolGAN 318
MclGAN (na RL)
gruphRNN
SerMatch 101
CondGEN
MoinMMPP.GAN
GG-GAN
GG-GAN RS
Molgun- QM9 CommrunitySmall Chordal9
182
132
660
26
832
2046
178
12
1632
13
232
724
Table 7: Number of isomorphism classes not the training set found within a sample 5000 generated graphs (higher is better). In Chordal9, we additionally verify whether the generated graph is chordal or not (rather than a direct comparison with the test set).
C.4 SCALABILITY EXPERIMENT DETAILS
Each method was used to generate single graph for N-times (N = 100 for Condgen and GG-GAN, 20 for graphRNN) and the median was reported. CPU evaluation done with an Intel Xeon Gold 6240. GPU evaluation done on Nvidia V100 on the same machine. GraphRNN was run with a context of 20 previously generated nodes. We observed roughly linear scaling decrease nodes per second as we increased the context e.g. with n. 9 we could generate R 90 nodes per second, with
n. = 20 this dropped to 47.
D IMPLEMENTATION DETAILS
D.1 EXTERNAL BASELINES
All our models are implemented and trained using pytorch and pytorch-lightning (Paszke et al. 2019 Falcon 2019). with experiments tracked using sacred (Klaus Greff et 2017). ). For the external baselines we used the following implementations, with the author-provider hyperparameters:
MolGAN
(ee Cao & Kipf
2018
2. CondGen Yang et al.
2019)
3.
g
You et al. 2018
4. ScoreMatching
Niu et al.
2020
D.2 WGAN
We follow the WGAN-GP approach (Gulrajani et al. 2017) except using the LP penalty from Petzka et al. (2018). In order to penalize the discriminator calculate the penalty convex combination between the real and fake samples (both nodes and adjacency matrices) using a uniformly sampled interpolation coefficient is common practice.
18

---

Under review as a conference paper at ICLR 2021
Community
Chordel
Dataset
G6-GAN
R68
PainENL
GB GG-GANIS
PoinEHLF
Figure 7: Comparison between random context (RC) and random set (RS) models.
D.3 GENERATOR
In the GG-GAN model, the generator composed of multi-head attention layers, usually between and 6 (see table 3) also with skip connections after each layer and instance normalization. For the discretization of the adjacency matrix, we sample each edge from a Bernoulli random variable, as explained in Section 3.1 Afterwards, zero the diagonal of the matrix and symmetrize it.
For the PointMLP GAN model, our generator which outputs the generated points x; is composed of a 3 layer MLP ( (128,256,412)) with ReLU activations, skip connections each layer, and instance normalization between them. The node readout function is a simple linear layer. Similar to GG-GAN, the edge readout function is a (ar. a.)), where is the standard sigmoid function.
19

---

Under review as a conference paper at ICLR 2021
D.4 DISCRIMINATOR
Since for a WGAN we require a powerful discriminator, we started combined insights from multiple papers. We start with the GIN (Xu et al.
2019) message passing block as a strong baseline using
the implementation from Fey & Lenssen 2019), then build a model inspired by DenseNet (Huang al. 2018 to increase the networks parameter efficiency and gradient y2low. We first create primitive which we call SkipGIN; in addition to the standard GIN update prodecure, we add the output of Linear Transmission (LT) layer in (Seool & Lipman (2020) without non-linearity which serves as permutation equivariant skip connection. We then form residual blocks (ResBlock) out of the SKipGIN layers, where each block acts as a pre-activation residual block (He et al.] 2016) using instance normalization (Ulyanov et al. 2017 ReLU activation and SkipGIN in the residual path and a completely linear SkipGIN as the projection. Finally, the output of each of these blocks is collected and concatenated along the feature dimension before being passed into the readout layer. This architecture is somewhere between a full pre-activation ResNet and a Densenet, allowing the readout access features from different depths while also ensuring gradient flow through all components. We refer to this GNN architecture as DenseGIN.
The readout layer is single hidden layer MLP which in addition the sum of concatenated node features from the DenseGIN receives: the 3,4,5 and 6 cycle counts and maps this to the final score, again using ReLU nonlinearity.
'With statistics computed on each node individually in order to avoid correlation in the gradient penalty as discussed in Gulrajani et al. (2017) We also experimented with Swish but found no improvement in performance.
20


Reviews:
[{"review_id": "rA9tt4SS3K", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "The work proposes to use WGAN architecture to learn latent space for generating new graphs with similar properties to the original ones. The authors show that their model is capable to control a probability of each new generated graph. Moreover it’s equivariant function which ensures that isomorphic graphs have the same probability to be generated. These properties are desirable  if we want to generate efficiently new graphs with properties similar to the graphs in the training set.\n\nThe paper is interesting and well-written, designs important properties for the generator of graphs. Usage of GAN in graph generator has been explored in the previous approaches and showed good results for generating graphs with similar properties to a given one [1]. \n\nMy main concern is in numerical evidence section. \n\n•       Datasets. There are essentially 2 real-world datasets with 9 vertices graphs and one artificial dataset with 20 vertices. If a graph has only 9 vertices, there are 12346 non-isomorphic graphs [2]. Your datasets is composed of around 10K graphs, therefore they should have a large portion of isomorphic graphs in train and test. Such repetitions may negatively affect performance of your model as well as baselines [3]. Also, since the graphs are small and consequently the number of non-isomorphic graphs is small, it’s possible to generate all of them quite easily for graph discovery – the main motivation of this paper. It would be more convincing to have a comparison on medium and big graphs. \n\n•       Baselines. Table 1 is not convincing in showing that the proposed method is better than preious approaches. There is a single result (out of 15) where MMD is better than other methods. graphRNN achieves 10 best or second best performances (vs 7 of GG-GAN). Additionally, I would be curious to see other graph generators such as NetGAN [1] (which should scale well for these sizes of graphs) and even simpler baselines such as finding parameters from train set of simple network models (Watts-Strogatz, Barabási–Albert model, Chung-Lu, etc.) and then generating random graphs from these models. \n\n[1] NetGAN: Generating Graphs via Random Walks\n\n[2] http://oeis.org/A000088\n\n[3] Understanding Isomorphism Bias in Graph Data Sets\n https://arxiv.org/abs/1910.12091", "extra_scores": {}, "extra_text": {}}, {"review_id": "n4TYA6grhT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The paper proposes GG-GAN, a GAN-based graph generative model for mimicking the structure distribution of realistic networks.  The authors claimed multiple fascinating properties of GG-GAN, including (1) isomorphism consistency, (2) expressive power, (3) scalability, (4) novelty. Experimental results on three datasets show the performance of GG-GAN in terms of five network properties. In general, the paper is well written and easy-to-follow. And a bunch of add-on theorems is provided to support the rationality of the proposed method. My major concerns are that the paper might over-claimed their contributions and the experimental results show limited improvement over the baseline methods. Here are the detailed comments:\n\n[Novelty]: The studied problem has been (partially) studied in the existing literature (e.g., isomorphism in graphRNN, expressive power in NetGAN, Scalability in TagGen, etc. ). It is unclear to me what the key contributions of this paper on top of existing work. \n\n[Literature review] The authors fail to provide a comprehensive literature review in the context of graph generation. The authors might want to provide an individual section to fully discuss the connection between this paper to the previous work. For example, \n* in terms of isomorphism, what is the difference between GG-GAN and the way employed in graphRNN? Where are the key innovations?\n* in terms of scalability, the authors claimed that \"GG-GAN is significantly faster than autoregressive models\". Have you compared with the recent proposed Transformer-based graph generative model (e.g., TagGen)?\n* ...\n\n[Theoretical analysis] The paper includes a bunch of add-on theorems. But, it seems to me that the connection between them and the proposed GG-GAN is weak. \n\n[Experiments - network quality] The paper shows limited improved over the baseline methods in terms of the quality of the generated graph. Interestingly, the paper fails to compare with NetGAN, which achieves SoTA performance in a list of network properties in the real-world datasets in my practice. \n\n[Experiments - scalability] As scalability is one of the major claims of GG-GAN - \"GG-GAN is significantly faster than the SoTA autoregressive models\", the authors should give a thorough comparison with the existing RNN-based graph generative model (e.g., NetGAN)/Transformer-based graph generative model (e.g., TagGen). Moreover, the authors may want to provide some insightful discussion on why the proposed GAN-based is definitely faster than the autoregressive model. To my best of knowledge, the autoregressive models can be mostly scaled with O(kn), while the GAN-based graph generators are required to fully specify the adjacency matrix A with an O(n^2) parameter space. Please correct me if I am wrong here. \n\n\nOverall, I enjoyed reading this paper. But, without clearing my concerns stated above, I will vote for weak rejection. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "lnCIq70Fc8D", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "In general, this paper deals with an interesting and essential problem to generate geometric graphs under several standards. The whole algorithm seems easy to implement or reproduce. It seems with minor modifications to traditional autoregressor based generative graph models, the proposed framework can effectively model isomorphism as well as delivers certain novelty. The idea of the paper is with novelty and some theorems can support the observations.\n\nHowever, I still have several concerns about the paper, stated as follows:\n\n1) While the paper emphasized that the proposed GG-GAN is capable of producing geometric graphs with under several vital criteria (e.g. novelty, scalability and modeling complex dependencies), one critical factor is missing: mode collapse/generation diversity. Many of the generative models still suffer from mode collapse/generation diversity problem, resulting in a small portion of generated variants than empirical observations. I would recommend the authors to discuss and give more evidence showing the ability of the proposed method to avoid such pitfall.\n\n2) The authors claimed that the proposed method can model complex local and global dependencies among nodes and edges. I understand that such a procedure can handle node dependencies given the design of the generator part. However, I suspect the ability of the proposed method to model complex \"edge dependencies\". To me, the sampling procedure of edges is performed under independent Bernoulli distribution for each edge. Therefore, it's inappropriate the claim that GG-GAN incorporates any mechanism to model dependencies between edges.\n\n3) In corollary 1, the authors proved the existence of some distribution \\mathcal{D}_x. However, it seems that existence of such distribution is naive: we can simply establish distbution with Delta-functions for each node. If I understand right, this corollary is not very informative.\n\n4)  Proposition is under the condition that each node is sampled independently. However, such a sampling mechanism can be easily replaced with a sampling procedure following a point process to avoid the coincide of nodes. I suppose that it would be better to briefly discuss the sampling procedure under this setting. Otherwise, it would be too weak Proposition 1 is.\n\n5) Section 2.2.3 Avoiding Collision is obscure to me. The necessity of such a mechanism is not well understood for me. I suggest the authors to give more details or clarify with some theoretical analysis to justify their claim in this section.\n\n6) Though the authors gave some discussion on the hand-crafted features of nodes, I still think the features employed in GG-GAN is ad-hoc. Hand-crafted features can greatly hinder the capacity of deep learning model and thus weaken the contribution of the paper.\n\n7) I see that to construct the initial input to the generator, an initial fixed point configuration and a unique sampled z for each node are concatenated. I suggest the authors to show what will happen if we sample z separately for each node. This may help to understand the necessity of unique sampling, then further show the mechanism behind it.\n\nI might consider to raise the rating if the authors can address my concerns well.", "extra_scores": {}, "extra_text": {}}, {"review_id": "lRgHen5b29I", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The paper investigates graph generation using adversarial technics. They introduce an algorithm named GG-GAN, based on Wassertain GAN, in order to accurately generates new graphs in hopefully the same distribution as a given dataset. GG-GAN generates points in an euclidian space that is then turned into a graph using a similarity function on the space. This approach is justified by Theorem 1. The authors show that their method successfully generate graphs within the same scope as the input dataset, and show that GG-GAN generates much more new graphs that current state of the art approach.\n\nPros:\n+ The paper is well written, honnest and didactic.\n+ The proposed method is new and is experimentaly efficient.\n\nCons:\n- The experiments could be more convincing: small dimension (<=20), classical graph benchmark.\n- The introduction of $\\phi$ is confusing, and its implications not well justified.\n\nRemarks:\n- Proposition 1 should be clarified with assumption within the theorem statement. The \"probability of being drawn by probability $\\mathcal{D}$\" is not well defined. This should be made very rigourous.\n- Section 2.1: 'complete representation' is not defined. Wouldn't k>=n-1 be enough?\n- Section 3.1: it is not totally clear to the reader why the set $\\phi$ is important in GG-GAN. i do not get how it works. How do you learn such parameters? How does it avoid collisions?\n- Section 3.3: some recent published papers actually give simple tricks for MPNNs in order to achieve universality without going through higher order tensors [1, 2]. It would be interesting to investigate the relationship of these approachs with the concatenation trick in GG-GAN.\n- I am not fully convinced the ethical consideration and impact paragraph is needed here.\n\nQuestions:\n- Experiments: what are the number of non-isomoprhic classes in the considered datasets?\n- You finally sample through a Bernouilli hence non directly differentiable. Why not using the same trick with other methods instead of going for GANs?\n- How does $\\phi$ looks like after training? What happens if we do not learn it and use random vectors instead?\n- When learning several $\\phi$ (\"a batch\") how do you precisely use it for generation?\n\nTypos:\n- many references are incomplete, e.g. \"A variational inequality perspective on generative adversarial networks\" is ICLR'17, \"Improved training of Wassertstein GANs\" is NeurIPS'17, etc\n- ref 'On random graph', Rényi: typo on the accent\n\n[1] Coloring graph neural networks for node disambiguation, IJCAI'20\n[2] Universal Invariant and Equivariant Graph Neural Networks, NeurIPS'19", "extra_scores": {}, "extra_text": {}}, {"review_id": "CZ79gmTaFSm", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "The main contribution of this paper is dubbed as the geometric graph (GG) generative adversarial network (GAN), which is a Wasserstein GAN that addresses the challenges. \nThe proposed method is inspiring and has sufficient theoretical support. This paper is globally well organized and clearly written.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors proposed a geometric graph generator that applies a WGAN model for efficient geometric interpretation. All the reviewers agree that the idea is interesting and the method has the potentials for graph generation tasks. Unfortunately, the experimental part is unsatisfying, which makes the paper on the borderline. More analytic experiments should be designed to verify the properties of the proposed GG-GAN, especially its scalability. Although in the rebuttal phase the authors add a simple example to generate large but simple graphs, we would like to see more experiments and comparisons on more real-world large graphs (even if the performance may not be good, the results will be constructive for both readers and authors to understand the work). 
Decision: Reject