summaries: This work proposes a new graph neural network architecture with modified rules for message passing, Iterated Graph Neural Network System (IGNNS). The paper then provides a theoretical analysis of the proposed architecture by connecting it with Iterated Function System (IFS), an important research field in fractal geometry. This paper further demonstrates empirically that the proposed architecture outperforms related models on citation network datasets.

summaries: This paper proposes a new framework of GNN which can deal with undirected and directed graphs in a unified way. The authors argue that the size of the symbol space for a message passing path with length n is 2^n, while previous architectures only have constant size. Motivated by this observation, the authors borrow ideas from Iterated Function System to augment the symbol space.

summaries: The paper proposes a new definition of GNNs designed to cope with bi-directional message-passing processes.  To do so, a new symbols space, different from the one adopted by Bidirectional GCN,  is considered, together with an iterated function system. These lead to an architecture composed of 4 steps: an input layer that acts as a classic FC layer; an IFS layer that applies the iterated function system considering the adjacency matrix; a layer to concatenate or sum the expected values of each iteration; and an output layer that combines the results using the functions of the IFS and a new learnable weight matrix.

abstractText: We present Iterated Graph Neural Network System (IGNNS), a new framework of Graph Neural Networks (GNNs), which can deal with undirected graph and directed graph in a unified way. The core component of IGNNS is the Iterated Function System (IFS), which is an important research field in fractal geometry. The key idea of IGNNS is to use a pair of affine transformations to characterize the process of message passing between graph nodes and assign an adjoint probability vector to them to form an IFS layer with probability. After embedding in the latent space, the node features are sent to IFS layer for iterating, and then obtain the high-level representation of graph nodes. We also analyze the geometric properties of IGNNS from the perspective of dynamical system. We prove that if the IFS induced by IGNNS is contractive, then the fractal representation of graph nodes converges to the fractal set of IFS in Hausdorff distance and the ergodic representation of that converges to a constant matrix in Frobenius norm. We have carried out a series of semi-supervised node classification experiments on citation network datasets such as citeser, Cora and PubMed. The experimental results show that the performance of our method is obviously better than the related methods.

authors:
Sami Abu-El-Haija
Amol Kapoor
Bryan Perozzi
Joonseok Lee

title: N-GCN: multi-scale graph convolution for semi-supervised node classification

title: Fractals Everywhere

authors:
Ming Chen
Zhewei Wei
Zengfeng Huang
Bolin Ding
Yaliang Li

title: Simple and deep graph convolutional networks

venue: In International Conference on Machine Learning,

authors:
Jian Du
Shanghang Zhang
Guanhang Wu
José M.F. Moura
Soummya Kar

title: Topology adaptive graph convolutional networks

title: An ergodic theorem for iterated maps

venue: Journal of Ergodic theory and Dynamical Systems,

title: Fractal Geometry: Mathematical Foundations and Applications

authors:
Tsu-Jui Fu
Peng-Hsuan Li
Wei-Yun Ma

title: GraphRel: Modeling Text as Relational Graphs for Joint Entity and Relation Extraction

venue: Association for Computational Linguistics,

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the diffificulty of training deep feedforward neural networks

venue: In AISTATS,

authors:
Caglar Gulcehre
Misha Denil
Mateusz Malinowski
Ali Razavi
Razvan Pascanu
Karl Moritz Hermann
Peter Battaglia
Victor Bapst
David Raposo
Adam Santoro
Nando de Freitas

title: Hyperbolic attention networks

venue: In ICLR,

authors:
William L. Hamilton
Rex Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In NIPS,

title: Fractals and self-similarity

venue: Indiana University Journal of Mathematics,

authors:
Thomas N. Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: In International Conference on Learning Representations (ICLR),

authors:
J. Klicpera
A. Bojchevski
S. Gunnemann

title: Predict then propagate: Graph neural networks meet personalized pagerank

authors:
Johannes Klicpera
Janek Groß
Stephan Günnemann

title: Directional message passing for molecular graphs

authors:
Guohao Li
Chenxin Xiong
Ali Thabet
Bernard Ghanem

title: Deepergcn: All you need to train deeper gcns

authors:
Qimai Li
Zhichao Han
Xiao-Ming Wu

title: Deeper insights into graph convolutional networks for semi-supervised learning

venue: In AAAI,

authors:
Diego Marcheggiani
Ivan Titov

title: Encoding sentences with graph convolutional networks for semantic role labeling

venue: In EMNLP,

title: Fractal Functions, Fractal Surfaces, and Wavelets

authors:
Zhewei Wei Ming Chen
Bolin Ding Zengfeng Huang
Yaliang Li

authors:
V. Nair
G. E Hinton

title: Rectified linear units improve restricted boltzmann machines

authors:
Diederik P.Kingma
Jimmy Lei Ba

title: Adam: A method for stochastic optimizaiton

authors:
Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang

title: Dropedge: Towards deep graph convolutional networks on node classification

venue: In International Conference on Learning Representations,

authors:
F. Scarselli
M. Gori
A.C. Tsoi
M. Hagenbuchner
G. Monfardini

title: The graph neural network model

venue: IEEE Trans. Neural Netw. Learn. Syst,

authors:
M. Schlichtkrull
Thomas Kipf
P. Bloem
R.V. Berg
Ivan Titov
M. Welling

title: Modeling relational data with graph convolutional

venue: networks. ArXiv,

authors:
N. Srivastava
G. Hinton
A. Krizhevsky
I. Sutskever
R. Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting

venue: The Journal of Machine Learning Research,

authors:
Kiran K. Thekumparampil
Chong Wang
Sewoong Oh
Li-Jia Li

title: Attention-based Graph Neural Network for Semi-supervised Learning

venue: arXiv e-prints, art

authors:
Petar Veličković
William Fedus
William L. Hamilton
Pietro Liò
Yoshua Bengio
R Devon Hjelm

title: Deep Graph Infomax

authors:
Keyulu Xu
Chengtao Li
Yonglong Tian
Tomohiro Sonobe
Ken ichi Kawarabayashi
Stefanie Jegelka

title: Representation learning on graphs with jumping knowledge

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec

title: How powerful are graph neural networks

authors:
Keyulu Xu
Jingling Li
Mozhi Zhang
Simon S. Du
Ken ichi Kawarabayashi
Stefanie Jegelka

title: What can neural networks reason about? 2020

authors:
Zhilin Yang
William W. Cohen
Ruslan Salakhutdinov

title: Revisiting semi-supervised learning with graph embeddings

authors:
Chenyi Zhuang
Qiang Ma

title: Dual graph convolutional networks for graph-based semi-supervised classification

venue: In WWW,

heading: 1 INTRODUCTION

text:
GNN (Scarselli et al., 2009) has been proved to be effective in processing graph structured data, and has been widely used in natural language processing, computer vision, data mining, social network and biochemistry. In recent years, GNN has developed a variety of architectures, such as GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018), DGI (Veličković et al., 2019), GIN (Xu et al., 2019), GCNII (Ming Chen et al., 2020) and GEN (Li et al., 2020). These architectures have a common feature, that is, the representation of each node is updated using messages from its neighbors but without distinguishing the direction (or angle) of message passing between two nodes. Recent studies have shown that considering directed message passing between nodes can improve the performance of GNN and achieve success in related fields. For example, DimeNet (Klicpera et al., 2020) considers the spatial direction from one atom to another and can learn both molecular properties and atomic forces. R-GCN (Schlichtkrull et al., 2018) and Bi-GCN (Marcheggiani & Titov, 2017; Fu et al., 2019) are models for directed graph, applied in the field of natural language processing. We note that the above direction based model does not consider the bidirectional mixed passing of messages.
But in real life, message passing is interactive in different directions. For example, node A obtains a message from node B. After processing the message, node A not only passes it to the next node C, but also feeds back to node B. Suppose there are only two directions for message passing, forward and backward, represented by 0 or 1, respectively. The symbol space of the first generation message passing path is {0, 1} = {0, 1}1, and that of the second generation message passing path is {00, 01, 10, 11} = {0, 1}2. Generally, the symbol space of the n-th generation message passing path is {0, 1}n and the size of the symbol space is 2n. This means that the scope of message passing spreads with exponent 2. However, in Bi-GCN (similar to Bi-LSTM) and R-GCN architectures, the symbol space is {{0}n, {1}n}, and its size is 2, which indicates that a lot of information will be lost in the process of message passing (see Appendix A).
How to characterize the above message passing patterns? We use two mappings to represent message passing process in two directions. Then the interactive passing of messages in different directions is equivalent to the composite operation of corresponding mappings. In addition, the direction of
message passing is often random, so we endow the two mappings with an adjoint probability vector to reflect the randomness. Because the symbol space of the iterative path of the Iterated Function System (IFS) with two mappings is also {0, 1}n and the mapping is selected with a certain probability, the iterative process of IFS is similar to the message passing process. In other words, the above message passing pattern can be described perfectly by IFS with probabilities. We naturally present the Iterative Graph Neural Network System (IGNNS), whose core layer is constructed by IFS. Figure 1 describes the differences in message passing patterns among GCN, Bi-GCN and IGNNS. At the same time, we regard undirected graph as a directed graph with equal probability of bidirectional message passing (see Figure 1(a)), so the IGNNS architecture can handle directed graph and undirected graph in a unified way.

heading: 2 PRELIMINARIES

text:
A graph G = (V,E) is defined by its note set V = {v1, v2, ..., vN} and edge set E = {(vi, vj)|vi, vj ∈ V }. Let A ∈ RN denote the adjacency matrix of G, providing with relational information between nodes. A[i, j] denote i, jth element of A, A[i, :] means the ith row, and A[:, j] means the jth column. In this paper, we assume that all nodes of G are self adjacent, that is A[i, i] = 1, i = 1, 2, ..., N . let D = diag(d1, d2, ..., dN ) be the degree matrix of A, where di = ∑N j=1 A[i, j].
Neighborhood Normalization. There are two ways to normalize A. One approach is the following mean-pooling employed by Hamilton et al. (2017) and Veličković et al. (2019) for inductive learning:
Amp = D −1A.
Another approach is the following symmetric normalization employed by Kipf & Welling (2017):
Asym = D − 12AD− 1 2 .
Iterated Function System. A mapping f : RN → RN is said to be a contractive mapping on RN if there exists a constant 0 < c < 1 such that ‖f(x1)− f(x2)‖2 < c‖x1 − x2‖2 for all x1, x2 ∈ RN . An iterated function system (Hutchinson, 1981) is defined by
IFS = {RN ; f1, f2, ..., fm;p}, where each fi : RN → RN is a contractive mapping and p = (p1, p2, ..., pm) is an adjoint probability vector meaning that fi is selected by probability pi for each iteration. Hutchinson (1981) showed that there exists a unique nonempty compact set F such that
F = m⋃ i=1 fi(F).
A =
 1 1 0 01 1 0 10 1 1 1
0 1 1 1
 , A0 =

1 2 1 2 0 0 0 12 0 1 2 0 0 12 1 2
0 0 0 1
 and A1 =

1 0 0 0 1 2 1 2 0 0
0 12 1 2 0 0 13 1 3 1 3
 .
We call F the fractal set or invariant set of IFS. More conclusions on IFS can be found in the Appendix D. It is well known that there exists a unique probability measure µ with support F satisfying the equation
µ = m∑ i=1 piµ ◦ f−1i . (1)
The probability measure µ in (1) is called the self-similar measure of IFS with probability vector p.

heading: 3 IGNNS ARCHITECTURE

text: In this section, we will introduce the architecture of the IGNNS according to the input layer, IFS layer, representation layer and output layer, which is described in Figure 2.

heading: 3.1 INPUT LAYER

text:
Given a graph structure data X ∈ RN×F of G = (V,E), called as the feature matrix of node set V . A row of X represents the F -dimensional feature vector of a node in V . Let W int ∈ RF×H be a learnable parameter matrix, where H is the dimension of the latent space. Then XW int ∈ RN×H . The output of input layer is defined by
X int = σ(XW int) ∈ RN×H , (2)
where σ(·) is the activation function. Generally, ReLU(x) = max(0, x) is used as the nonlinear activation function. Here, each column of X int is regarded as a point in RN , so X int is the set of H points in RN and arranged in a certain order. The vector composed of the ith component of these points (the ith row of X int) is a feature representation of the ith node of graph G.

heading: 3.2 IFS LAYER

text:
Let A be the adjacency matrix of G. Let triu(A) denote the upper triangular matrix of A and tril(A) denote the lower triangular matrix of A. The symmetric normalization of triu(A) and tril(A) are
A0 = D − 12 0 triu(A)D − 12 0 and A1 = D − 12 1 tril(A)D − 12 1 ,
where D0 and D1 are degree matrices of triu(A) and tril(A) respectively. Sometimes, we use the mean-pooling of triu(A) and tril(A), i.e. A0 = D−10 triu(A),A1 = D −1 1 tril(A). Let f0, f1 be the two affine transformations on RN , induced by A0,A1 respectively, defined as follows: f0 : x→ A0x+ b0, x ∈ RN , b0 ∈ R, f1 : x→ A1x+ b1, x ∈ RN , b1 ∈ R,
where b0 and b1 are learnable biases, namely add constants b0 and b1 to each component of A0x and A1x respectively. Constructing iterated function system
IFS = {RN ; f0, f1;p}, where p = (p0, p1) is a learnable adjoint probability vector, satisfying p0 > 0, p1 > 0 and p0+p1 = 1. Using the symbol space Ωm = {0, 1}m, then for each i = (i1, i2, ..., im) ∈ Ωm the length of i is m, denoted as |i| = m, and defining pi = pi1pi2 · · · pim and fi = fi1 ◦ fi2 ◦ · · · ◦ fim . Let n be the number of iterations of IFS. For IGNNS, n is a preset parameter. The iterative process of IFS is described as follows:
The first iteration (|i| = 1). The result of the first iteration is denoted by H(1) = {f0(X int), f1(X int)} = {Hi}|i|=1,
where Hi = fi(X int), ∀i ∈ Ω1. Since IFS selects the iteration branch fi with probability pi, the mathematical expectation of H(1) is computed by
E1 = p0f0(X int) + p1f1(X int) = p0H0 + p1H1 = ∑ |i|=1 piHi.
If choose to use bias in iterations, then H0 = A0X int + b0,H1 = A1X int + b1, where b0 and b1 are learnable H-dimensional vectors.
The second iteration (|i| = 2). Using the results of the first iteration as the input of the second iteration, then the result of the second iteration is denoted by
H(2) = {f0(f0(X int)), f0(f1(X int)), f1(f0(X int)), f1(f1(X int))} = {f00(X int), f01(X int), f10(X int), f11(X int)} = {Hi}|i|=2,
where Hi = fi(X int), ∀i ∈ Ω2. Note that IFS selects the iteration path fi with probability pi, then the mathematical expectation of H(2) is computed by
E2 = ∑ |i|=2 pifi(X int) = ∑ |i|=2 piHi.
We expand the expression of E2 and perceive its powerful feature representation ability. First,
H00 = f0(H0) = A0(A0X int + b0) + b0,H01 = f0(H1) = A0(A1X int + b1) + b0,
H10 = f1(H0) = A1(A0X int + b0) + b1,H11 = f1(H1) = A1(A1X int + b1) + b1.
Then E2 = p00H00 + p01H01 + p10H10 + p11H11
= (p00A00 + p01A01 + p10A10 + p11A11)X int
+ (p00A0b0 + p01A0b1 + p10A1b0 + p11A1b1) + (p00b0 + p01b0 + p10b1 + p11b1),
where Ai = Ai1Ai2 , ∀i = (i1, i2) ∈ Ω2. The n-th iteration (|i| = n). Inductively, we have
H(n) = {Hi}|i|=n, Hi = fi(X int), En = ∑ |i|=n piHi. (3)
Note that Hi ∈ RN×H and each column of Hi is a point in RN , so we regard it as a subset of RN withH elements. Thus H(n) is a subset of RN withH×2n elements (including duplicate elements). Because of Theorem 4.1, we call H(n) the fractal representation with depth n of notes.

heading: 3.3 REPRESENTATION LAYER

text:
After n iterations of IFS layer, the dynamic trajectory of IFS is obtained:
O = {E1,E2, ...,En}.
In general, the global representation R of notes is obtained by time average or concatenation operations on O.
R = 1
n n∑ i=1 Ei ∈ RN×H or R =‖ni=1 Ei ∈ RN×nH ,
where ‖ is the concatenation operator. Because of Theorem 4.2, we call R the ergodic representation of notes. In practice, we adopt weighted time average or weighted concatenation. According to the Theorem C.1, we use heuristic weights (Here, we understand it as the average expansion factor of the distance between two points after affine transformation). Let r = √ ln(N) + γ, where γ ≈ 0.577215664 is the Euler constant. Suppose r = (r1, r2, ..., rn) is a learnable n-dimensional vector with initial value ri = ( 1 r )i−1 . Then the ergodic representation of notes is
R = n∑
i=1
riEi ∈ RN×H or R =‖ni=1 riEi ∈ RN×nH .

heading: 3.4 OUTPUT LAYER

text:
Let W out ∈ RH×P be a learnable parameter matrix, where P is the dimension of the output layer (such as the number of class labels). If R is generated byO concatenation, then let W out ∈ RnH×P . There are two ways to construct output layer, one is to use a Single-Layer Perception (SLP) as output, that is
O = RW out + bout;
the other is to use f0, f1 for Mixed Propagation (MP), that is, let R0 = f0(RW out) and R1 = f1(RW out), where the biases of f0, f1 are removed, then the output
O = p0R0 + p1R1 + bout.
Where the bias bout ∈ RP is an optional learnable parameter vector.

heading: 3.5 INITIALIZATION OF LEARNABLE VARIABLES

text:
The learnable parameters of IGNNS include input layer matrix W int ∈ RF×H , adjoint probability vector p = (p0, p1) ∈ R2 of IFS, biases b0, b1 ∈ RH of IFS layer, weight coefficient r = (r1, r2, ..., rn) of representation layer, matrix W out ∈ RH×P of output layer and bias bout ∈ RP of output layer. Among them, W int and W out are the required learnable parameters, using the initialization described in Glorot & Bengio (2010); b0, b1 and bout are optional learnable parameters with an initial value 0; p is a optional learnable parameter, for undirected graph, setting p0 ∈ [0.5− 0.1, 0.5 + 0.1], and for directed graph, setting (For the reasons, see Appendix G)
p0 = detD1
detD0 + detD1 , p1 = detD0 detD0 + detD1 ;
r is a optional learnable parameter, and its initial value as defined in 3.3. Let n be the number of iterations of IFS. We regard n as the depth of IGNNS. Thus, IGNNS is denoted as
O = IGNNS(X,A;W int, n,p, b0, b1, r,W out, bout) or simply O = IGNNS(X, IFS),
where IFS is induced by relational matrix A. The output of IGNNS can be used as the input of downstream tasks, and can also be connected to other network architectures.

heading: 3.6 THEORETICAL TIME COMPLEXITY OF IGNNS

text:
Let n,N,H, P be defined as above. Let T (·) denote the number of calculations of an object. For input layer,
T (input layer) = NFH +NH = O(NFH).
For IFS layer, during the iterative calculation, we will store the previous calculation results, thus T (H(1)) = 2N2H , T (H(i)) = 2×T (H(i−1)), i = 2, 3, ..., n. It follows that T (H(i)) = 2iN2H, i = 1, 2, ..., n. Similarly, T ({pi||i| = i}) = 2i, i = 1, 2, ..., n. Complete the above calculation, it is easy to see that T (Ei) = 2iNH . Thus
T (IFS layer) = n∑
i=1
( T (H(i)) + T ({pi||i| = i}) + T (Ei) ) = O(2nN2H).
It is easy to verify that T (representation layer) = O(nNH). We assume that the output layer is constructed by mixed propagation, then T (output layer) = O(N2P ) if W out ∈ RH×P , and T (output layer) = O(N2P + nNHP ) if W out ∈ RnH×P . Then
T (IGNNS) = O(2nN2H +N2P ) or O(2nN2H +N2P + nNHP ). In practice, for large graphs, 2nN2H N2P nNHP , thus 2nN2H is the main factor affecting the time complexity of IGNNS. Furthermore, for large graphs of the same size, n is the main important factor affecting time complexity. For citation network datasets such as citeser, Cora and PubMed, we suggest that n ≤ 8 (see Appendix B).

heading: 4 GEOMETRIC PROPERTIES OF IGNNS

text:
The discussion here assumes that affine f0, f1 are contractive. Otherwise, let f0 : x → 1 ‖A0‖F+1A0x + b0 and f1 : x → 1
‖A1‖F+1A1x + b1. In practice, IGNNS does not use contractive affine. If contractive affine is used in IGNNS, it can be seen from the following theorems that the characterization ability of IGNNS decreases with the increase of IFS iterations, which is similar to the performance of Graph Convolution Network (GCN). Such a phenomenon is called over-smoothing (Li et al., 2018b; Xu et al., 2019; Chen et al., 2020), which suggests that as the number of layers increases, the representations of the nodes in GCN are inclined to converge to a certain value and thus become indistinguishable. In order to overcome the over-smoothing problem of deep GNN, people need to use some new methods such as Skip connection (Xu et al., 2018), Drop edge (Rong et al., 2020), Residual connection (Klicpera et al., 2019a), Identity mapping (Chen et al., 2020), Generalized message aggregation functions (Li et al., 2020) and so on. Generally speaking, deep network may lead to the decrease of generalization performance. To analyze which type of deep GNN would achieve better generalization performance, Xu et al. (2020) proposes a guiding theoretical framework.
Theorem 4.1 (Fractal generation) Let H(n) = {Hi}|i|=n, which is a subset of RN with H × 2n elements (including duplicate elements), then
dH(H(n),F)→ 0, n→∞, where dH is the Hausdorff distance defined on H(RN ), the set of all nonempty compact subsets of RN , and F is the fractal set of IFS in IGNNS. In other words, as the number of iterations increases, H(n) will be independent of node feature X , only related to the graph structure described by A.
Let T be the Hutchinson operator on H(RN ), defined as T (B) = f0(B) ⋃ f1(B),∀B ∈ H(RN ). Then the updated rule of H(n) satisfies H(n) = T (H(n−1)) = · · · = Tn(H(0)),
where H(0) = {X int} is a subset of RN with H elements. In fractal geometry, H(n) is used to draw the fractal image on the plane. First, taking initial value H(0) = {x0}, where x0 is a point in plane. For enough n, printing all the points of H(n) on the screen to obtain the approximate fractal image.
Theorem 4.2 (Ergodic property) Let En = ∑ |i|=n piHi be the mathematical expectation of H(n) = {Hi}|i|=n, then En converges to a constant matrix E ∈ RN×H in Frobenius norm, i.e. limn→∞En = E, where E[i, :] = (ei, ei, ..., ei)> ∈ RH and ei ∈ R is a constant, i = 1, 2, ..., N . Furthermore, the time average of the dynamic trajectory O of IFS satisfies
lim n→∞
1
n n∑ i=1 Ei = lim n→∞ En = E
and series ∑∞
i=1 riEi ∈ RN×H converges in Frobenius norm.
Theorem 4.2 shows that as long as the number of iterations is large enough, the embeddings of nodes will be close to linear correlation, and the representation ability of IGNNS will decline. However, in the framework of IGNNS, because the spectral radius ρ(A0) = ρ(A1) = 1, IFS is not contractive in general, and IGNNS still has the ability of depth feature representation.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL TASK: SEMI-SUPERVISED NODE CLASSIFICATION

text: Let Z = softmax(O), where Z ∈ RN and softmax(·) is the softmax activation function, defined as softmax(xi) = 1Z exp(xi) with Z = ∑ i exp(xi), is applied row-wise. For semi-supervised multiclass classification, we employ the following cross-entropy to evaluate error over all labeled examples: L = − ∑ l∈YL ∑P i=1 Y [l, i] lnZ[l, i],where YL is the set of node indices that have labels with P classes, Y [l, :] is a one-hot vector of size P representing the class of node l and Z[l, :] is the row l of the matrix Z.

heading: 5.2 EXPERIMENTAL SETUP

text:
Datasets. In our experiment, we use three standard citation network benchmark datasets for evaluation, including Cora, Citeseer, Pubmed and apply the standard fixed training/validation/testing split (Yang et al., 2016; Kipf & Welling, 2017; Veličković et al., 2018) on above datasets, with 20 nodes per class for training, 500 nodes for validation and 1,000 nodes for testing. In these citation networks, papers are represented as nodes, and citations of one paper by another are denoted as edges. Node features are the bag-of-words vector of papers, and node label is the only one academic topic of a paper. See Table 1 for more details.
Parameter Setting. Random seed for Tensorflow and Numpy is set to 1234. ReLU (Nair & Hinton, 2010) is used as the activation function in input layer and output layer. Dropout (Srivastava et al., 2014) is applied to input layer, IFS layer and output layer. In representation layer, we adopt weighted time average to get the global representation of notes. In output layer, we adopt the method of mixed propagation to get the output of IGNNS. We use the AdamOptimizer (P.Kingma & Ba, 2015) during training. More details of hyper-parameters are shown in Table 2. During training stage, we select the best model to maximize the accuracy of the validation set and use early stopping with a patience of 100 epochs.

heading: 5.3 EXPERIMENTAL RESULT

text:
We compare with those models that strictly follow the standard of experiment setup of semisupervised node classification, i.e. the standard fixed training/validation/testing split (Yang et al., 2016; Kipf & Welling, 2017) is applied on dataset. For baselines, we include recent deep GNN models such as JKNet (Xu et al., 2018), APPNP (Klicpera et al., 2019a), Attention-based models such as GAT (Veličković et al., 2018), AGNN (Thekumparampil et al., 2018) and H-GAT (Gulcehre et al., 2019) , and other models such as TAGCN (Du et al., 2017) and N-GCN (Abu-El-Haija et al., 2018). We also include three state-of-the-art shallow GNN models: Planetoid (Yang et al., 2016), GCN (Kipf & Welling, 2017) and DGCN (Zhuang & Ma, 2018). The detailed results are shown in Table 3.
We can see from Table 3 that the improved performance of model IGNNS in dataset Cora and Citeseer is much higher than that in dataset Pubmed. To understand why this happens, we analyze
the characteristics of these citation networks. We consider two statistical properties of networks, one is the Network Density d(G), which is defined as d(G) = 2LN(N−1) , where N is the number of nodes and L is the number of edges, and the other is the Average Clustering Coefficient C, which is defined as C = 1N ∑ i∈V Ci, where V is the set of nodes, Ci = 2ei ki(ki−1) , ki is the number of the neighbors of node vi and ei is the number of undirected edges between ki neighbors. The small Network Density means the strong global sparsity of the network, and the small Average Clustering Coefficient means the strong sparsity of the neighbors of nodes. The calculation results of the statistical characteristics of the network are shown in Table 4. We can see from Table 4 that Pubmed is more sparse than Cora and Citeseer. The performance of IGNNS benefits from the bidirectional mixed propagation of information between nodes, but this sparsity weakens the gain of IGNNS.

heading: 5.4 PERFORMANCE OF COMPLETELY LINEAR IGNNS

text:
In Nonlinear IGNNS, we use the nonlinear activation function ReLU(x), learn adjoint probability vector p = (p0, p1) by p0 ← ReLU(p0)+0.1ReLU(p0)+ReLU(p1)+0.2 , p1 ← ReLU(p1)+0.1 ReLU(p0)+ReLU(p1)+0.2 and learn the rep-
resentation layer coefficient r = (r1, r2, ..., rn) by ri ← ReLU(ri) with initial value ri = ( 1 r )i−1 where r = √ ln(N) + 0.577215664. In this experiment, to get a completely linear IGNNS, we let all the activation functions be the identity function, i.e. σ(x) = x, and let the adjoint probability vector p = (p0, p1) and the representation layer coefficient r = (r1, r2, ..., rn) be hyperparameters
without learning. For Citeseer, we let p0 = 0.6, and for Pubmed, we use bias for IFS layer. Except for the above changes, experimental task and the other experimental setups remain unchanged as showed in section 5.1 and 5.2 respectively. We can see from Table 5 that the performance of completely linear IGNNS is better than that of baseline model GCN. Compared with other models, completely linear IGNNS is still competitive. This is due to the fact that the IFS can extract more features than spectral filters. For more discussion, Let A be the normalization adjacency matrix of graph G, and let A0 and A1 be defined as in section 3.2. We further assume that the dimension of the hidden space is equal to 1. This means that the input of GNN (GCN or IGNNS) is a point x0 = X
int = XW int ∈ RN×1. Let n be the depth of GNN, for IGNNS, equal to the number of iterations of IFS. For convenience, we ignore the activation function and parameter matrix. Let f(x) = Ax+ b, f0(x) = A0x+ b0 and f1(x) = A1x+ b1. For GCN, the message passing results are {f(x0)}, {f2(x0)}, ..., {fn(x0)}. We see that each iteration only gets one value, i.e. |{fn(x0)}| = 1. For IGNNS, the message passing results are as follows:
{f0(x0), f1(x0)}, {f0(f0(x0)), f0(f1(x0)), f1(f0(x0)), f1(f1(x0))}, ..., {fi(x0)}|i|=n.
If f0 and f1 satisfy separation condition, i.e. f0(x) = f1(y) implies x = y, then |{fi(x0)}|i|=n| = 2n. This means that IGNNS can extract more information than GCN. Even if f0 and f1 are contractive mappings, by Theorem 4.1, we have {fi(x0)}|i|=n → F, where F is the fractal set of IFS induced by f0 and f1. Generally speaking, F is a uncountable compact set. This means that when n is large, the features may still be distinguishable.

heading: 6 CONCLUSION

text: In this paper, we propose a new framework of graph neural networks, IGNNS, which give a connection between Graph Neural Networks and Iterated Function System. We use IFS to simulate the bidirectional message passing process of graph neural network, and obtain the fractal representation and ergodic representation of graph nodes, which are very helpful for downstream tasks. The experiments show that we have achieved good results in semi-supervised node classification task. Interesting directions for future work include pruning the iterative path space {0, 1}n to reduce the computational complexity, coding graph structured data with IFS, and establishing more interesting connections between IFS and graph neural networks.

heading: A THE FRACTAL REPRESENTATION OF GRAPH G WITH ONLY ONE SELF

text:
ADJACENT NODE v.
For the sake of discussion, we assume that the dimension of the hidden space is equal to 1. We assume that messages are sent from node v, propagate in two directions (clockwise and anticlockwise), and are finally received by node v. The received messages in the clockwise direction become one-third of the original, and the received messages in the anticlockwise direction become one-third of the original plus a constant of 23 . It is expressed by mathematical formula as follows
f0(x) = x
3 , f1(x) =
x 3 + 2 3 , x ∈ R.
For Bi-GCN, messages are delivered independently in both directions. In other words, there are two independent channels, and the message passing (transmitting or receiving) can only be carried out by their own channels. Let x0 ∈ R be the initial message. In the clockwise direction, after n passes, the received messages are
x0 3 , x0 32 , ..., x0 3n → 0.
In the anticlockwise direction, the received messages are
x0 3 + 2 3 , x0 32 + 2 32 + 2 3 , ..., x0 3n + n∑ i=1 2 3i → 1.
For IGNNS, the two channels have a connection point at node v. First, node v sends the message x0 in both directions, and the connection point of node v will receive two messages {f0(x0), f1(x0)}. In the second launch, any message (f0(x0) or f1(x0)) can be sent in both directions, so the received messages are
{f0(f0(x0)), f0(f1(x0)), f1(f0(x0)), f1(f1(x0))}.
In summary, After n passes, the received messages are
H(n) = {fi(x0)}|i|=n → C,
where C is the famous Cantor Set. This means that we have not only received one message, but 2n, since f0 and f1 satisfy the separation condition. We can see from Figure 3 that Bi-GCN gets boundary messages and IGNNS gets all messages. Let p = (p0, p1) be the adjoint probability vector, then the mathematical expectation En of H(n) is ∑ |i|=n pifi(x0). We interpret En as the average of all messages received. Now the question is, fractal representation gets enough messages, but is there redundancy in these messages? How to select the valid message from the fractal representation becomes the focus of our research in the next stage.

heading: B ANALYSIS OF TIME COMPLEXITY ON CORA, CITESEER AND PUBMED.

text:
From section 3.6, we have known that the time complexity in Experiment 5.1 isO(2nN2H+N2P ), where n is the number of iterations of IFS (the depth of IGNNS), N is the number of nodes, H is the dimension of the latent space and P is the dimension of the output layer. In this section, we compare the real running time (100 epochs) of IGNNS on Cora, Citeseer and Pubmed. Let H = 8, then 2nN2H is the main factor affecting the time complexity of IGNNS. Let the depth of IGNNS
go from 1 to 8, and compare the real training time on Cora, Citeseer and Pubmed. We can see from Figure 4 that the actual results are basically consistent with the theoretical analysis results.

heading: C FROBENIUS NORM OF MATRIX

text:
Theorem C.1 Let A ∈ RN×N be the adjacency matrix of a graph with no weights, i.e. Ai,j = 1 if there exists an edge i → j in the graph and Ai,j = 0 otherwise, and A1 = D−11 tril(A) (or A1 = D − 12 1 tril(A)D − 12 1 ) as defined in IGNNS, then
‖A1‖F ≥ √ ln(N) + γ,
where γ ≈ 0.577215664 is the Euler constant.
Proof. Case 1: A1 = D−11 tril(A). Let tril(A) = (aij)N×N , D1 = diag(d1, d2, ..., dN ) be the degree matrix of tril(A) and A1 = (bij)N×N . Note that tril(A) is an lower triangular matrix, then di = ∑N j=1 aij = ∑i j=1 aij . Since aij ∈ {0, 1}, we have i ≥ di. Computing the Frobenius Norm of A1 as follows:
‖A1‖2F = N∑ i=1 N∑ j=1 b2ij = N∑ i=1 i∑ j=1 b2ij = N∑ i=1 i∑ j=1 ( aij di )2 . (4)
∀i ∈ {1, 2, ..., N}, note that di elements in {aij}ij=1 are 1 and the rest are 0. It follows that
i∑ j=1 ( aij di )2 = ( 1 di )2 × i∑ j=1 a2ij = ( 1 di )2 × di = 1 di ≥ 1 i . (5)
It follows from (4) and (5) that
‖A1‖2F ≥ N∑ i=1 1 i .
So ‖A1‖F ≥ √∑N i=1 1 i ≈ √ ln(N) + γ, where γ ≈ 0.577215664 is the Euler constant.
Case 2: A1 = D − 12 1 tril(A)D − 12 1 . Computing the Frobenius Norm of A1 as follows:
‖A1‖2F = N∑ i=1 N∑ j=1 b2ij = N∑ i=1 i∑ j=1 b2ij = N∑ i=1 i∑ j=1 a2ij didj . (6)
∀i ∈ {1, 2, ..., N}, it follows from j ≥ dj that
i∑ j=1 a2ij didj ≥ 1 di i∑ j=1 1 j · a2ij . (7)
Note that di elements in {aij}ij=1 are 1 and the rest are 0. It follows from Rearrangement inequality that
i∑ j=1 1 j · a2ij ≥
1
i− di + 1 · a2i(i−di+1) +
1
i− di + 2 · a2i(i−di+2) + · · ·+
1 i · a2ii, (8)
where ai(i−di+1) = ai(i−di+2) = · · · = aii = 1. Thus
i∑ j=1 1 j · a2ij ≥ 1 i · 12 + 1 i · 12 + · · ·+ 1 i · 12 = di × 1 i . (9)
It follows from (6), (7) and (9) that
‖A1‖2F ≥ N∑ i=1 1 i .
Which completes the proof.
D INTRODUCTION TO ITERATED FUNCTION SYSTEM
In order to prove Theorem 4.1 and Theorem 4.2, we will briefly introduce the relevant conclusions on IFS in this section, and we will not give the proof here. More details of IFS Theory can be found in Hutchinson (1981); Elton (1987); Barnsley (1988); Falconer (1990); Massopust (2017).
D.1 FRACTAL SPACE
Let (X; d) be a complete metric space. Let H(X) denote a set consisting of all nonempty compact subsets of X . Hausdorff distanceon dH onH(X) defined by
dH(A,B) = max{max a∈A min b∈B d(a, b),max b∈B min a∈A d(a, b)},∀A,B ∈ H(X). (10)
Theorem D.1 (H(X); dH) is a complete metric space.
We call (H(X); dH) a Fractal space. Let {fi}ni=1 be a set of mappings on (X; d). Hutchinson operator T : (H(X); dH)→ (H(X); dH) defined as
T (B) = n⋃ i=1 fi(B),∀B ∈ H(X). (11)
Theorem D.2 If {fi}ni=1 is a set of contractive mappings on (X; d), then Hutchinson operator T is a contractive mapping on (H(X); dH).
D.2 MARKOV OPERATOR OF IFS
Let (X; d) be a complete metric space. Let M(X) be the set of all probability measures on X . Let C(X) be the set of all continuous functions mapping X to R. We say that f ∈ L̃ip1, if |f(x)− f(y)| ≤ d(x, y),∀x, y ∈ X . It is easy to see that if f ∈ L̃ip1 then f ∈ C(X). Hutchinson metric dM onM defined as
dM (µ, ν) = sup {∣∣∣∣∫ X fdµ− ∫ X fdν ∣∣∣∣ |f ∈ L̃ip1} ,∀µ, ν ∈M(X). (12) Theorem D.3 (M(X); dM ) is a complete metric space.
Let IFS = {X; f1, f2, ..., fn;p}, the Markov operator M :M(X)→M(X) of IFS defined as
Mµ = n∑ i=1 piµ ◦ f−1i , µ ∈M(X). (13)
Theorem D.4 Markov operator M of IFS is a contractive mapping on space (M(X); dM ).
Let measure sequence {µi} ⊂ M and µ ∈M, we call {µi} weakly convergent to µ if the following equation holds:
lim i→∞ ∫ X fdµi = ∫ X fdµ,∀f ∈ C(X), (14)
denoted as µi w−→ µ as i→∞.
Theorem D.5 If µi dM−−→ µ as i→∞, then µi w−→ µ as i→∞.

heading: E THE PROOF OF THEOREM 4.1

text:
Proof. By Theorem D.1, (H(RN ); dH) is a complete metric space. Let T be the Hutchinson operator on H(RN ), defined as T (B) = f0(B) ⋃ f1(B),∀B ∈ H(RN ). By Theorem D.2, T is a contractive mapping on (H(RN ); dH). It follows from the Banach fixed point theorem that there exits a unique compact subset F ofH(RN ) such that
F = T (F) = f0(F) ⋃ f1(F),
which implies that F is the fractal set of IFS. Further more, ∀B ∈ H(RN ), we have Tn(B) dH−−→ F. The above convergence is independent of the choice of initial value. Thus, let H(0) = {X int} = {x1, x2, ..., xH}, xi ∈ RN , we have
H(n) = T (H(n−1)) = · · · = Tn(H(0)) dH−−→ F. The above result indicates that when n is large enough, H(n) is close to the fractal set F of IFS in the sense of Hausdorff distance, and has nothing to do with the choice of initial value H(0).

heading: F THE PROOF OF THEOREM 4.2

text:
Proof. It suffices to prove that ∀j ∈ {1, 2, ...,H} , En[:, j], the j column of En, satisfies
lim n→∞ En[:, j] =  e1 e2 ... eN  N×1 .
For this purpose, let xj be the j column of X int as defined in (2), then xj is a point in RN . Define a Dirac measure as follows:
δx(B) = { 1 x ∈ B, 0 other.
(15)
It is easy to see that δx ∈ M(RN ). The Markov operator M :M(RN )→M(RN ) of IFS, defined as
Mµ = 1∑ i=0 piµ ◦ f−1i , µ ∈M(R N ). (16)
Now take µ0 = δxj , and the results of iterative calculation are as follows:
µ1 = Mµ0 = 1∑ i=0 piµ0 ◦ f−1i = 1∑ i=0 piδxj ◦ f−1i = 1∑ i=0 piδfi(xj) = ∑ |i|=1 piδfi(xj).
µ2 = M 2µ0 = Mµ1 = 1∑ i=0 piµ1 ◦ f−1i = 1∑ i=0 pi( ∑ |i|=1 piδfi(xj)) ◦ f −1 i
= p0p0δf0(f0(xj)) + p0p1δf0(f1(xj)) + p1p0δf1(f0(xj)) + p1p1δf1(f1(xj)) = ∑ |i|=2 piδfi(xj)
Inductively, we have
µn = M nµ0 = ∑ |i|=n piδfi(xj). (17)
By Theorem D.4, it follows from the Banach fixed point theorem that there exits a unique probability measure µ∗ such that
µn dM−−→ µ∗.
The above µ∗ is actually the self-similar measure of IFS. By Theorem D.5, we have µn w−→ µ∗, i.e.
lim n→∞
∫ Fdµn = ∫ Fdµ∗, ∀F ∈ C(RN ).
It follows from (17) and (3) that
∫ Fdµ∗ = lim
n→∞
∫ Fdµn = lim
n→∞
∫ Fd( ∑ |i|=n piδfi(xj))
= lim n→∞ ∑ |i|=n piF (fi(xj))
= lim n→∞ ∑ |i|=n piF (Hi[:, j]), ∀F ∈ C(RN ). (18)
In (18), ∀i ∈ {1, 2, ..., N}, take the continuous function Fi to satisfy
Fi(t) = ti, ∀t = (t1, t2, ..., tN )> ∈ RN .
It follows from (18) that ∀i ∈ {1, 2, ..., N},
lim n→∞ En[i, j] = lim n→∞ ∑ |i|=n piHi[i, j] = lim n→∞ ∑ |i|=n piFi(Hi[:, j])
= ∫ Fi(t)dµ∗(t) = ∫ tidµ∗(t) = ∫ F tidµ∗(t) = ei. (19)
Which combined with simple mathematical analysis technology completes the proof.

heading: G HOW TO SET THE INITIAL VALUE OF ADJOINT PROBABILITY VECTOR?

text:
The geometric meaning of matrix determinant detA is the expansion factor of graph volume under linear transformation A. Let F be the fractal set of IFS as defined in IGNNS. Then
F = f0(F) ⋃ f1(F).
Note that
detAi = volume(fi(F))
volume(F) , i = 0, 1.
It can be seen that if the value of detAi is large, it reflects that fi(F) has a large share in F. therefore, when selecting the iterative function, fi should have a greater probability of being selected. So set
p0 = detA0
detA0 + detA1 , p1 = detA1 detA0 + detA1 ;
Note that A0, A1 are triangular matrixes and the diagonals of triu(A), tril(A) are equal to 1. It follows from A0 = D−10 tril(A) (or A0 = D − 12 0 tril(A)D − 12 0 ) that detA0 = 1 detD0
. Similarly, detA1 =
1 detD1 . It follows that
p0 = detD1
detD0 + detD1 , p1 = detD0 detD0 + detD1 ,
where D0 and D1 are degree matrices of triu(A) and tril(A) respectively.


summaries: 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.

summaries: 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.

summaries: 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.

abstractText: 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 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.

authors:
Noga Alon
Andrey Kupavskii

title: Two notions of unit distance graphs

venue: Journal of Combinatorial Theory, Series A,

authors:
Martin Arjovsky
Soumith Chintala
Léon Bottou

title: Wasserstein generative adversarial networks

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

venue: cite arxiv:1409.0473Comment: Accepted at ICLR

authors:
Yoshua Bengio
Nicholas Léonard
Aaron Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

authors:
Aleksandar Bojchevski
Oleksandr Shchur
Daniel Zügner
Stephan Günnemann

title: Netgan: Generating graphs via random walks

venue: arXiv preprint arXiv:1803.00816,

authors:
Béla Bollobás
Svante Janson
Oliver Riordan

title: The phase transition in inhomogeneous random graphs

venue: Random Structures & Algorithms,

authors:
Zhengdao Chen
Lei Chen
Soledad Villar
Joan Bruna

title: Can graph neural networks count substructures

venue: arXiv preprint arXiv:2002.04025,

authors:
Hanjun Dai
Azade Nazi
Yujia Li
Bo Dai
Dale Schuurmans

title: Scalable deep generative modeling for sparse graphs

venue: arXiv preprint arXiv:2006.15502,

authors:
Nicola De Cao
Thomas Kipf

title: Molgan: An implicit generative model for small molecular graphs

venue: arXiv preprint arXiv:1805.11973,

authors:
Vijay Prakash Dwivedi
Chaitanya K Joshi
Thomas Laurent
Yoshua Bengio
Xavier Bresson

title: Benchmarking graph neural networks

venue: arXiv preprint arXiv:2003.00982,

title: rényi,“on random graphs,

venue: Publicationes Mathematicae,

authors:
Matthias Fey
Jan E. Lenssen

title: Fast graph representation learning with PyTorch Geometric

venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,

title: Generative deep learning: teaching machines to paint, write

venue: compose, and play. O’Reilly Media,

authors:
Gauthier Gidel
Hugo Berard
Gaëtan Vignoud
Pascal Vincent
Simon Lacoste-Julien

title: A variational inequality perspective on generative adversarial networks

venue: arXiv preprint arXiv:1802.10551,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

venue: Advances in Neural Information Processing Systems

authors:
Ishaan Gulrajani
Faruk Ahmed
Martin Arjovsky
Vincent Dumoulin
Aaron Courville

title: Improved training of wasserstein gans, 2017

authors:
Tinghao Guo
Daniel Herber
James T Allison

title: Circuit synthesis using generative adversarial networks (gans)

venue: In AIAA Scitech 2019 Forum,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Identity mappings in deep residual networks

venue: In European conference on computer vision,

authors:
Gao Huang
Zhuang Liu
Laurens van der Maaten
Kilian Q. Weinberger

title: Densely connected convolutional networks, 2018

authors:
Po-Ssu Huang
Scott E Boyken
David Baker

title: The coming of age of de novo protein

venue: design. Nature,

authors:
Mark L Huson
Arunabha Sen

title: Broadcast scheduling algorithms for radio networks

venue: In Proceedings of MILCOM’95,

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax

authors:
A. Katharopoulos
A. Vyas
N. Pappas
F. Fleuret

title: Transformers are rnns: Fast autoregressive transformers with linear attention

venue: In Proceedings of the International Conference on Machine Learning (ICML),

authors:
Nicolas Keriven
Gabriel Peyré

title: Universal invariant and equivariant graph neural networks

venue: In Advances in Neural Information Processing Systems,

authors:
Thomas N Kipf
Max Welling

title: Variational graph auto-encoders

venue: In NIPS Workshop onBayesian Deep Learning,

authors:
Klaus Greff
Aaron Klein
Martin Chovanec
Frank Hutter
Jürgen Schmidhuber

title: The Sacred Infrastructure for Computational Research

venue: Proceedings of the 16th Python in Science Conference,

authors:
Yujia Li
Oriol Vinyals
Chris Dyer
Razvan Pascanu
Peter Battaglia

title: Learning deep generative models of graphs. 2018

authors:
Renjie Liao
Yujia Li
Yang Song
Shenlong Wang
Will Hamilton
David K Duvenaud
Raquel Urtasun
Richard Zemel

title: Efficient graph generation with graph recurrent attention networks

title: What graph neural networks cannot learn: depth vs width

title: Large networks and graph limits, volume 60

venue: American Mathematical Soc.,

authors:
Chris J Maddison
Andriy Mnih
Yee Whye Teh

title: The concrete distribution: A continuous relaxation of discrete random variables

venue: arXiv preprint arXiv:1611.00712,

authors:
Hiroshi Maehara
Vojtech Rödl

title: On the dimension to represent a graph by a unit distance graph

venue: Graphs and Combinatorics,

authors:
Haggai Maron
Heli Ben-Hamu
Hadar Serviansky
Yaron Lipman

title: Provably powerful graph networks

authors:
Christopher Morris
Martin Ritzert
Matthias Fey
William L Hamilton
Jan Eric Lenssen
Gaurav Rattan
Martin Grohe

title: Weisfeiler and leman go neural: Higher-order graph neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Chenhao Niu
Yang Song
Jiaming Song
Shengjia Zhao
Aditya Grover
Stefano Ermon

title: Permutation invariant graph generation via score-based generative modeling

venue: Proceedings of Machine Learning Research, pp. 4474–4484,

title: Random geometric graphs, volume 5

venue: Oxford university press,

authors:
Henning Petzka
Asja Fischer
Denis Lukovnicov

title: On the regularization of wasserstein gans, 2018

title: Learning deep generative models

venue: Annual Review of Statistics and Its Application,

authors:
Akiyoshi Sannai
Yuuki Takai
Matthieu Cordonnier

title: Universal approximations of permutation invariant / equivariant functions by deep neural networks

authors:
Nimrod Segol
Yaron Lipman

title: On universal equivariant set networks

authors:
Hadar Serviansky
Nimrod Segol
Jonathan Shlomi
Kyle Cranmer
Eilam Gross
Haggai Maron
Yaron Lipman

title: Set2graph: Learning graphs from sets

venue: arXiv preprint arXiv:2002.08772,

authors:
Zhuoran Shen
Mingyuan Zhang
Haiyu Zhao
Shuai Yi
Hongsheng Li

title: Efficient attention: Attention with linear complexities

authors:
Martin Simonovsky
Nikos Komodakis

title: Graphvae: Towards generation of small graphs using variational autoencoders

venue: In International Conference on Artificial Neural Networks,

authors:
Dmitry Ulyanov
Andrea Vedaldi
Victor Lempitsky

title: Instance normalization: The missing ingredient for fast stylization, 2017

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in neural information processing systems,

title: The random projection method, volume 65

authors:
Clement Vignac
Andreas Loukas
Pascal Frossard

title: Building powerful and equivariant graph neural networks with structural message-passing

authors:
Sinong Wang
Belinda Z. Li
Madian Khabsa
Han Fang
Hao Ma

title: Linformer: Self-attention with linear complexity, 2020

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

authors:
Carl Yang
Peiye Zhuang
Wenhan Shi
Alan Luu
Pan Li

title: Conditional structure generation through graph variational generative adversarial nets

authors:
Jiaxuan You
Rex Ying
Xiang Ren
William L Hamilton
Jure Leskovec

title: Graphrnn: Generating realistic graphs with deep auto-regressive models

authors:
Dawei Zhou
Lecheng Zheng
Jiawei Han
Jingrui He

title: A data-driven graph generative model for temporal interaction networks

venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining, KDD

authors:
Maehara
Rödl (Maehara
Rödl

venue: R with k = 2∆,

heading: 1 INTRODUCTION

text:
Learning distributions from empirical observations is a fundamental problem in 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 et al., 2019; Niu et al., 2020; Yang et al., 2019). When successfully trained, deep graph generative models carry the potential to transform a 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 in nature (Huang et al., 2016), and automatically synthesizing circuits (Guo et al., 2019).
By and large, there are four properties that a graph generator g should possess: (1) Isomorphism consistency: g should assign isomorphic graphs the same probability—a 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: g should be able to synthesize graphs with tens of thousands of vertices. (4) Novelty: 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 as 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.

heading: 1.1 GEOMETRIC GRAPH GENERATION

text:
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, 1995; Penrose et al., 2003; Bollobás et al., 2007; Lovász, 2012; Alon & Kupavskii, 2014; Glasscock, 2015).
Surprisingly, these classical geometric approaches have so 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-consistent generators. Interestingly, we find that straightforward generators must solve a 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 statistics 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.

heading: 1.2 RELATION TO EXISTING WORK

text:
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, 2018; Liao et al., 2019) tend to memorize the training set in the absence of problem-specific rewards (De Cao & Kipf, 2018). 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 et 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-autoregressive. ScoreMatch samples graphs from a 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., 2018), while being a pure GAN does not operate on distributions of graphs. Instead, it learns to generate random walks on a single large graph using an autoregressive generator and then assembles the graph from these random walks. TagGen (Zhou et al., 2020) uses a similar model on temporal interaction graphs, but instead of learning a generator, it trains a transformer critic to score random temporal walks and then samples from them in parallel via rejection sampling and assembling the final graph. Neither model directly captures a 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 a 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 = {x1, . . . ,xn} of n points as a matrix X with each row corresponding to some point xi in arbitrary order. Functions, such as neural networks, are denoted by lower case letters, such as f, g. Every undirected weighted graph G = (V,E,w) can be defined in terms of a set of n = |V | nodes, a set of edges E with (vi, vj) ∈ E if there exists an edge joining the i-th and j-th nodes, and a weight function w : E → R+ indicating the strength of each connection. A simple graph G = (V,E) is an undirected graph without weights. Finally, the symbol Sn refers to the group of permutations on [n] = (1, . . . , n). All proofs are presented in the appendix.

heading: 2 FUNDAMENTALS OF GEOMETRIC GRAPH GENERATION

text: 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—presented in Section 3.

heading: 2.1 REPRESENTING GRAPHS SPATIALLY

text:
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; Bollobás et al., 2007; Lovász, 2012; Alon & Kupavskii, 2014; Glasscock, 2015).
More concretely, let x1, . . . ,xn be n points in Rk. We determine whether graph G = (V,E) of n = |V | nodes contains edge (vi, vj) ∈ E by testing if κ(xi,xj) = 1, for a similarity function κ.
It is not hard to see that this particular representation is complete1 over the space of undirected graphs: every undirected graph can be represented by n points as long as k is sufficiently large. For instance, if xi is chosen to be the row of the matrix square-root of the adjacency matrixA of the graph G, and κ(xi,xj) = x > i xj , then the representation is complete if and only if k = n.
Surprisingly, the embedding dimension k can favorably depend on the sparsity of the graphs we wish to represent. Indeed, for simple graphs of degree at most ∆, Maehara and Rödl showed that k = 2∆ dimensions suffice (Maehara & Rödl, 1990). This theorem unfortunately relies on a discrete and non-differentiable similarity function κ 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 a weighted undirected graph with adjacency matrix A ∈ [0, 1]n×n and maximum (combinatorial) degree ∆. For any ∈ (0, 1), there exist points x1, . . . ,xn in Rk with k = O ( ∆2 logn
2
) , for which |A(i, j)− (ex>i xj − 1)| ≤ for all i 6= j.
Therefore, any weighted graph can be approximately represented by n points in at most k = O(∆2 log n/ 2) dimensions and this is possible using the differentiable function κ(x,y) = ex >y−1.

heading: 2.2 CHALLENGES OF GEOMETRIC GRAPH GENERATION

text:
In the following, we expose three key challenges inherent to geometric generators.
1A vector representation of a set is complete if and only if there exists a surjective function between the representation vectors and the elements of the set.

heading: 2.2.1 THE CURSE OF INDEPENDENCE

text:
The simplest way of constructing a generator is by sampling each point xi independently from a distribution Dx. We refer to this approach as random graph generation (RGG) (Penrose et al., 2003). It is a direct corollary of our Theorem 1 that RGG can be used to generate any simple graph:
Corollary 1. Fix any weighted undirected graph G = (V,E) of degree at most ∆ and letA be its adjacency matrix. For any ∈ (0, 1), there exists Dx supported on Rk with k = O(∆2 log n/ 2) such that with strictly positive probability, |A(i, j)− (ex>i xj − 1)| ≤ for all i 6= j. In a deep learning context, one may think of modeling Dx by passing a Normal distribution through a learned function, such as a multi-layer perceptron (MLP): xi = g(zi), where zi ∼ N (0, Im), for every i ∈ [n] and with m being the dimension of the latent space. Unfortunately, as it is shown next, such generators cannot satisfactorily control the probability with which each set is generated.
Proposition 1. RGG generates any {x1, . . . ,xn} with xi 6= xj with probability at most O(ne−n). 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.

heading: 2.2.2 MODELING ISOMORPHIC GRAPHS CONSISTENTLY

text:
Naturally, we can introduce dependencies between points by expressing the joint distribution DX of X = [x1, . . . ,xn] > ∈ Rn×k as the push-forward measure of a random Z ∈ Rn×m
X = g(Z), with Z = [z1, . . . ,zn]> and zi ∼ N (0, Im), 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 approximating 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 us consider the case where g is a surjective function, meaning that for every X there exists Z with g(Z) = X . Then, a large subset of its latent space can be devoted to expressing different permutations of the same points:
∀X ∈ Rn×k and π ∈ Sn, ∃Z,Z ′ ∈ Rn×k such that X = g(Z) = πg(Z ′) = πX ′, where Sn is the group of permutations on [n], with |Sn| = n!. In other words, g can generally assign different probabilities toX and πX , even if the corresponding graphs are simply isomorphic.
A more appropriate class of functions are those that are equivariant to permutation:
Proposition 2. If g is permutation equivariant, then for every X and π ∈ Sn, we have Prob(X ∼ DX) = Prob(πX ∼ DX). The above observation is consistent with the findings of Yang et al. (2019). Serviansky et al. (2020) also provides guidelines on how to construct such a function g.

heading: 2.2.3 AVOIDING COLLISIONS

text:
While we seek an equivariant function that maps a random Z to X , learning such functions can prove challenging even in toy examples (cf., Section 3.2). Intriguingly, we recognize that a principal difficulty has to do with ensuring that the points are mapped in an equivariant manner without collisions, i.e., with no two rows zi, zj of Z being mapped to the same output.
For intuition, let us simplify the setting by supposing that we wish to generate the same fixedX for every random input Z. Function g can 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 Z to one ofX . Geometrically, the latter corresponds to moving n points from a random initial position to a fixed final target. For instance, g could select an assignment t : [n] → [n] and match every zi to a target position xt(i), with t(i) 6= t(j) for each i, 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)—otherwise, g cannot ensure that two different input points zi and zj will not collide onto the same target position.
Unfortunately, we argue that both these behaviors are unlikely to be learned in practice: In the first case, one has to learn to ignore any spurious relations that are induced by the random input. In the second case, due to being permutation equivariant, g can rely on the position zi, zj and not the order i, 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 3 presents a geometric graph generator that circumvents these difficulties by allowing the generator to solve the collision avoidance problem at training time, rather than once for every input.

heading: 3 GG-GAN: A GEOMETRIC GRAPH GENERATIVE ADVERSARIAL NETWORK

text: 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 a geometric generator ggg and a graph neural network discriminator dgg, 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.

heading: 3.1 THE GEOMETRIC GRAPH (GG) GENERATOR

text:
The generator of our GG-GAN maps a set of points from an initial configuration to a target position in a permutation equivariant manner. However, to avoid solving a collision avoidance problem for every input, we retain the initial points at fixed, non-random positions, while using a 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, we instead learn a distribution over functions conditioned on a deterministic input in a manner similar to a conditional GAN — though, in contrast to the latter, we also learn the fixed input during training.
Figure 1 illustrates that to generate a graph G of n nodes, our generator takes as an input a fixed learned set Φ = {φ1, . . . ,φn} of points in Rd and a vector z sampled from a Normal distribution:
X = ggg(Φ, z), where z ∼ N (0, Iq),
and Φ ∈ Rn×d is the matrix representation of set Φ. Then, G is determined from X , by sampling each edge (vi, vj) from a Bernoulli random variable with probability κ(xi,xj) = σ(x>i xj), 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 x, the random variables can feature arbitrary dependencies overall, e.g., by setting κ(xi,xj) = κ(xi′ ,xj′) = 1 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 estimation on samples from a 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 an MLP independently on each row ofX .
To generate graphs of different sizes, we model n as a categorical random variable in [nmin, nmax] and fix Φ to contain n points from {φ1, . . . ,φnmax}. The parameters of the categorical distribution, including nmin and nmax, are directly estimated from the training data.
To implement ggg, we concatenate z with everyφi and process the resulting matrix with a permutation equivariant function: X = ggg(Φ‖z) with Φ‖z = [(φ1‖z), . . . , (φn‖z)]>. Different choices are possible on how to instantiate ggg. For instance, ggg could be parametrized by a PointNetST network, which is a universal approximator over the space of equivariant functions (Segol & Lipman, 2020), or based on the constructions of Keriven & Peyré (2019) and Sannai et al. (2019). Inspired of the success of attention for set-based tasks, we use a deep self-attention network.
Let us further justify our generator using the following properties. Expressive power: By construction, our ggg 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 ggg ensures that isomorphic graphs are always sampled with equal probability (see Section 2.2.2). Collision avoidance: Since Φ is deterministic by construction, our generator can avoid collisions by prescribing a different role to each input point φi. There is no need to determine an assignment from Φ toX every time that a graph is generated (see Section 2.2.3), the assignment can be determined once during training.

heading: 3.2 AN ILLUSTRATIVE TOY EXAMPLE: LEARNING TO GENERATE A TARGET SET OF POINTS

text:
To highlight the impact of using fixed vs random points, we perform the following toy experiment.
We generate a single target X and use an equivariant neural network to determine a mapping that can transform any random set Z of points to X , or specifically, zi → xi. 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 et 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 a generator using a 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 Φ, it 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 a batch of 20 such matrices. We determined this change to be beneficial in encouraging the learned model to find differentX that fool the discriminator, and hence, to obtain a higher novelty.

heading: 3.3 THE GEOMETRIC GRAPH DISCRIMINATOR

text:
In a Wasserstein-GAN framework, the discriminator is critical in the approximation of the Wasserstein distance. For this purpose, we use a message-passing neural network (MPNN) discriminator dgg. Since MPNN without node attributes are known to be blind to many relevant properties of a graph’s structure (Xu et al., 2019; Morris et al., 2019; Chen et al., 2020), similar to previous works (De Cao & Kipf, 2018; Yang et al., 2019), we increase the discriminative power of dgg 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 vi’s attribute vector by appending to the corresponding node’s degree the first k entries U(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 a symmetry-breaking mechanism. We further aid the discriminator by explicitly providing it with k-cycle counts (3 ≤ k ≤ 5) as well as the number of nodes present in the graph currently evaluated. Cycles are a prominent graph feature that standard MPNNs cannot distinguish. Both eigenvectors and cycles are computed in a differentiable manner during the forward pass. For further details about the discriminator architecture, we refer to Appendix D.4.
Although, from a pure deep learning perspective, using handcrafted features is undesirable, to our knowledge, no universal and efficient equivariant graph classifier currently exists: MPNN is
Models Molgan-QM9 CommunitySmall-20 Chordal9
Deg. Clust. Cycle AC DA Deg. Clust. Cycle AC DA Deg. Clust. Cycle AC DA
MMD threshold 0.0050 0.1649 0.1167 0.0784 0.0359 2.71E-5 0.0013 1.17E-8 0.0012 0.0002 0.0404 0.0090 0.0670 0.0500 0.1348
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 our framework and to eliminate the need for handcrafted features.

heading: 4 NUMERICAL EVIDENCE

text: 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.

heading: 4.1 MODELLING COMPLEX DEPENDENCIES

text:
Building on the evaluation protocol of You et al. (2018), we computed the maximum mean discrepancy (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
coefficient (DA). We argue that a good generative model should generally score sufficiently well across all MMDs. In our experience, even failing to capture a single statistic can lead to generating graphs with significant visual differences from the dataset. To specify what “sufficient well” means, we set as threshold the MMD between the training and test sets: If a generator is close to this threshold, then we say that it captures well a given graph statistic.
Table 1 summarizes our 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 8 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 likelihood-based 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 structural dependencies. On the other hand, MolGAN is generally apt at generating molecules, but its performance can change when the custom reinforcement learning (RL) loss is not utilized. Moreover, MolGAN’s specialized architecture is not applicable to non-molecular data.
To illustrate the effect of collision avoidance, we 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 a Normal distribution (i.e., rather than having a fixed set and a random context). As seen, though the RS version can model excellently simple statistics (like DA and Clust.), it struggles with more complex ones, such as AC. Figure 3 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 to capture both local and global topological properties.

heading: 4.2 GENERATION NOVELTY

text:
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 to a small set 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 learning-to-memorize the training set. Perhaps due to not being isomorphism consistent, MolGAN achieves low novelty, though we observe a boost via the RL module.
It is also important to note that attaining a high novelty score is challenging only for methods that can closely fit MMD statistics—clearly, 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 3, 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.

heading: 4.3 SCALABILITY

text:
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 (You et 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 ran our models on and (due to time constraints) estimate the GRAN timing based on the speedup reported2 in Liao et al. (2019). For bigg, we extracted their reported timings from their figure 6 using WebPlotDigitizer (Rohatgi, 2020). We perform all measurements by initialising the model and then generating a 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 4 demonstrates that our model is highly efficient, outperforming graphRNN, the estimated GRAN, and even bigg in terms of inference speed even when it is run on CPU. CondGen is competitive with our model on CPU (the publicly available version actually performs the conversion of embeddings into a graph on CPU) which is not surprising since it is also a non-autoregressive model.
We also highlight that the released version of CondGen has over 100× less parameters than our model. Nevertheless, since ConGen also non-autoregressive and uses an outer-product kernel to generate adjacency matrices, in principle it scales with O(n2), similar to GG-GAN. It might be interesting to note that Dai et al. (2020) in theory scales better than our method due to impressive optimizations exploiting sparsity, leading to O((m+ n) log n) scaling for n nodes with m edges. However, for the graph sizes we tested, the constant factor incurred by either their framework or 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 a consequence of specialized optimization and engineering.

heading: 5 CONCLUSIONS

text:
Our work partakes in the geometric graph generation research thread and advocates for learning a distribution over functions rather than transforming a distribution over points. Our methodology yields an isomorphism consistent generator that, as empirically confirmed, possesses favorable scalability, novelty, and expressive power, matching or surpassing various SotA baselines in most cases.
A key direction that we would like to focus in the future is scalability. Herein, we rely on the multi-head attention of Vaswani et al. (2017) that scales with O(n2) in compute and memory. More recent work (Wang et al., 2020; Shen et al., 2018; Katharopoulos et al., 2020) has reduced this complexity to nearly O(n) while maintaining performance, implying low hanging fruit in additional efficiency gains. We are also interested in more sophisticated generator architectures that exploit sparsity, possibly using insights from Dai et al. (2020).
2They report a 6× speedup w.r.t to graphRNN at quality parity on a GTX 1080Ti. We round this up to a 10× speedup in an attempt to be as fair as possible (to account for our more modern hardware).

heading: A DEFERRED PROOFS

heading: A.1 PROOF OF THEOREM 1

text:
For completeness, before presenting the proof, we restate the Theorem of Maehara and Rödl showing that k = 2∆ dimensions suffice (Maehara & Rödl, 1990):
Theorem 2 (Maehara and Rödl (Maehara & Rödl, 1990)). For every undirected simple graph G of degree at most ∆, there exist points x1, . . . ,xn in Rk with k = 2∆, for which κ(xi,xj) = 1 if and only if (vi, vj) ∈ E, i.e., κ(xi,xj) = 1{x>i xj=0}, where 1C is the indicator function of set C.
We move on to our proof. Let q be a function that is strictly increasing and λ-Lipschitz. We consider the matrix C with entries given by the following expression:
C(i, j) = q−1(A(i, j) + η) and A(i, j) = q(C(i, j))− η
for η = q(0). IfA(i, j) ∈ [0, 1], we then also have
0 = q−1(η) = min a∈[η,1+η] q−1(a) ≤ C(i, j) ≤ max a∈[η,1+η] q−1(a) = q−1(1 + η) = q−1(1 + q(0)) = c.
Denote by UΛU> the eigenvalue decomposition of C and write
C = XX> − γI, with X = U(Λ + γI)1/2 ∈ Rn×n
and γ = ‖C‖2. This is always possible since U(Λ + γI)1/2(Λ + γI)1/2U> = U(Λ + γI)U> = UΛU> + γI = C + γI is, by the choice of γ, positive semi-definite.
If we think of the rows x1, . . . ,xn ofX as points, we have
‖xi‖22 ≤ max i Λ(i, i)+γ ≤ 2‖C‖2 ≤ 2 max i n∑ j=1 |C(i, j)| = 2 max i n∑ j=1 |q−1(A(i, j)+η)| ≤ 2c∆.
To proceed, we rely on the following well-known property (Vempala, 2005): If x̄i = Rxi andR is a k× n random matrix whose entries are independently sampled fromN (0, 1√
k ), then for any n points
x1, . . . ,xn ∈ Rn with ‖xi‖22 ≤ δ, we have
P (|x>i xj − x̄>i x̄j | ≥ t δ) < 4n2 exp
( − ( t2 − t3 ) k
4
) for all i, j = 1, . . . , n.
It follows by the probabilistic argument, that choosing k = 8 log(2n)φ(t) with φ(t) = t 2 − t3 suffices for some points x1, . . . ,xn to exist in Rk for which |x>i xj − x̄>i x̄j | ≤ tδ.
In this manner, we work backwards and consider the matrix with elements C̄(i, j) = x̄>i x̄j − γ, which approximates C as follows:
‖C − C̄‖∞ = ‖XX> − X̄X̄>‖∞ ≤ (2c∆) t.
For the matrix with elements Ā(i, j) = q(C̄(i, j))− η, we have
‖A− Ā‖∞ = max i,j ‖q(C(i, j))− η −
( q(C̄(i, j))− η ) ‖∞ ≤ λ‖C − C̄‖∞ ≤ t (2λc∆).
Selecting t = 2λc∆ then yields k = 8 log(2n) φ( /(2λc∆)) and ‖A− Ā‖∞ ≤ .
Let us now consider the shifted exponential function κ(xi,xj) = ex > i xj − 1. We set q(x) = ex, for which η = q(0) = 1 and c = q−1(1 + η) = log(2). Moreover, within the domain [0, c] of interest, the Lipschitz constant of q is given by λ = ec = 2. Substituting the above to the bound gives k = 8 log(2n)φ( /(4 log(2)∆)) . The proof concludes by noting that function φ is lower bounded as t
2 in the domain of interest.

heading: A.2 PROOF OF COROLLARY 1

text: The proof follows trivially by selecting Dx to have uniform measure on the n points that give rise to the graph according to Theorem 1. A more detailed analysis of the probability in question can be found in the proof of Proposition 1.

heading: A.3 PROOF OF PROPOSITION 1

text:
Let X = {x1, . . . ,xn} be the set that we wish to generate and denote by D the distribution in Rk that the random generator is induced from (with m = k). Write also as pi = Prob(xi ∼ D) the probability that the i-th point is drawn from Dx. The probability that X is sampled is given by
Prob(X ∼ Dx) = ∑ π∈Sn pπ1 · · · pπn = n! n∏ i=1 pi,
where π is an element of the permutation group Sn on n elements. The above (log) product is bounded by
log ( n∏ i=1 pi ) = n n∑ i=1 1 n log pi ≤ n log ( n∑ i=1 1 n pi ) ≤ n log ( 1 n ) ,
where the first inequality follows by Jensen and the second is because ∑ i pi ≤ 1. Thus, employing Stirling’s approximation we obtain
log (Prob(X ∼ Dx)) ≤ log (n!)− n log n ≤ n(log n− 1) +O(log n)− n log n = −n+O(log n),
which implies that there exists a constant c for which Prob(X ∼ Dx) ≤ cne−n, as needed.

heading: A.4 PROOF OF PROPOSITION 2

text:
To prove the proposition it suffices to show that Prob(πX) = Prob(X) for any permutation π and anyX = g(Z).
The probability of anyX to be sampled can be expressed as Prob(X) = ∫ 1(g(Z) = X) Prob(Z) dZ,
where 1(g(Z) = X) is the indicator function of event g(Z) = X and the integration is over all Z. Similarly, we have that
Prob(πX) = ∫ 1(g(Z ′) = πX) Prob(Z ′) dZ ′
= ∫ 1(g(πZ) = πX) Prob(πZ) dZ (by the substitution Z ′ = πZ)
= ∫ 1(g(πZ) = πX) Prob(Z) dZ (since Prob(Z) = Prob(πZ))
= ∫ 1(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 1(g(·) = πX) Prob(·) is a real-valued function.

heading: B BATCH INDEX DIVERSITY

text:
As we discussed in the main text, GG-GAN learns a function distribution operating on a 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 5. Notice that if the generator were to ignore the context vector, we would expect no diversity on each batch index (i.e., for the same fixed Φ) across samples. However, as can be seen in the figure, for the QM9, at batch index 0 a circle structure appears to be learned, but overall there is diversity within samples in the same batch for all datasets.

heading: C EXPERIMENTAL DETAILS

heading: C.1 HYPERPARAMETERS

text:
The hyperparameters used in our experiments can be found in Table 3. The baselines were run with code provided in the respective papers, see Appendix D.1. ExtraAdam Gidel et al. (2018) was used for both generator and discriminator with the following parameters: lr=1e-4, betas=(0.5, 0.9999), eps=1e-8, weight decay=1e-3, ema=False, ema start=100, using the standard 5:1 ratio of discriminator to generator updates.
Table 4 summarizes the hyperparameters used for our discriminator (see Table D.4 for an explanation of the architecture) throughout all our experiments. L refers to the number of ResBlocks in the DenseGIN, crh is the hidden layer of the final readout MLP, c l o is the output node feature dimension of the ResBlock l, cli and c l h analogously refer to the input features of each ResBlock and the width of the hidden layer of the SkipGINs inner MLP respectively.

heading: C.2 DATASETS

text:
QM9. The QM9 dataset contains 133,885 organic compounds. Following De Cao & Kipf (2018), our experiments focused on a 5k subset. Most of the graphs in this dataset have 9 nodes.
Chordal. A graph is chordal if every cycle of length at least 4 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 a 5000 subset for training and the rest 6911 for test.
Community. Similarly to Niu et al. (2020), we construct 5000 N=20 node graphs containing 2 communities generated by the Erdos̃-Rényi model Erdös (1959) with p = 0.7. Then, 0.05N edges are added between the communities.

heading: C.3 MODELING COMPLEX DEPENDENCIES

text:
We first define the five discrete distributions that the MMD scores are based on:
• Degree distribution. The degree of a node is the number of connections it has to other nodes. The degree distribution is the probability distribution of these degrees over the entire graph. • Cycle distribution. A cycle is a 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 a graph. • Clustering. The clustering coefficient of a 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 a graph.

heading: C.4 SCALABILITY EXPERIMENT DETAILS

text:
Each method was used to generate a 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 a Nvidia V100 on the same machine. GraphRNN was run with a context of 20 previously generated nodes. We observed roughly linear scaling decrease in nodes per second as we increased the context nc, e.g. with nc = 9 we could generate ≈ 90 nodes per second, with nc = 20 this dropped to ≈ 47 .
D IMPLEMENTATION DETAILS

heading: D.1 EXTERNAL BASELINES

text:
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 al., 2017). For the external baselines we used the following implementations, with the author-provided hyperparameters:
1. MolGAN (De Cao & Kipf, 2018)
2. CondGen (Yang et al., 2019)
3. graphRNN (You et al., 2018)
4. ScoreMatching (Niu et al., 2020)

heading: D.2 WGAN

text: 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 we calculate the penalty on convex combination between the real and fake samples (both nodes and adjacency matrices) using a uniformly sampled interpolation coefficient as is common practice.

heading: D.3 GENERATOR

text:
In the GG-GAN model, the generator is composed of multi-head attention layers, usually between 3 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, we zero the diagonal of the matrix and symmetrize it.
For the PointMLP-GAN model, our generator which outputs the generated points xi is composed of a 3 layer MLP ([128,256,412]) with ReLU activations, skip connections at 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 σ(x>i xj), where σ is the standard sigmoid function.

heading: D.4 DISCRIMINATOR

text:
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 et al., 2018) to increase the networks parameter efficiency and gradient y2low. We first create a primitive which we call SkipGIN: in addition to the standard GIN update prodecure, we add the output of a Linear Transmission (LT) layer as in Segol & Lipman (2020) without non-linearity which serves as a 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)3, ReLU activation4 and a 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 to 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 a single hidden layer MLP which in addition to 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 a ReLU nonlinearity.
3With statistics computed on each node individually in order to avoid correlation in the gradient penalty as discussed in Gulrajani et al. (2017)
4We also experimented with Swish but found no improvement in performance.

title: GG-GAN: A GEOMETRIC GRAPH GENERATIVE ADVERSARIAL NETWORK