Iterated graph neural network system
Authors: Hanju Li
Venue:  (2021)

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

Under review as a conference paper at ICLR 2021
ITERATED GRAPH NEURAL NETWORK SYSTEM
Anonymous authors Paper under double-blind review
ABSTRACT
We present Iterated Graph Neural Network System (IGNNS), new framework of Graph Neural Networks (GNNs), which can deal with undirected graph and directed graph in 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 to use a pair of affine transformations to characterize the process of message passing between graph nodes and assign an adjoint prob- ability 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 geomet- ric 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 series of semi-supervised node classification experiments on citation network datasets such as citeser, Cora and PubMed. The experimen- tal results show that the performance of our method is obviously better than the related methods.
INTRODUCTION
GNN (Scarselli 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 variety of architectures, such as GCN
Kipf & Welling 2017). GraphSAGE (Hamilton et al., 2017). GAT (Veličković et al. 2018). DGI
(Veličkové et 2019). GIN (Xu et al. 2019). GCNIT Ming Chen et al.) 2020) and GEN (Li al.,
2020). These architecture have 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 another and can learn both molecular properties and atomic forces. R-GCN (Schlichtkrull et al. 2018) and Bi-GCN (Marcheggiani & Titov| [017 Fu et al., (209)) 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.
These
But in real life, message passing is interactive in different directions. For example, node A obtains message from node B. After processing the message, node not only passes the next node C, but also feeds back to node B. Suppose there are only two directions for message passing, for- ward and backward, represented by 0 or respectively. The symbol space of the first generation message passing path is (0. (0.1)- (0, 1) and that of the second generation message passing path {00, 01, 10, 11} = {0, 112. Generally, the symbol space of the n-th generation message passing path is {0, 11"h and the size of the symbol space is 2". 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}", {1)"). 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 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

---

Under review as a conference paper at ICLR 2021
INGUN
Figure Message passing patterns. Where the symbol H is the representations of all the notes. (a) An undirected graph is transformed into directed graph in a natural way. (b) Regardless of direction, simply gather information from neighbors.
(c) Mcssage is passed in the same direction (forward or backward), and get two hidden representations independently. (d) Message passing not only occurs in the same direction, but also occurs interactively in different directions, which is more in line with the actual situation. For example, in layer node 2 passes the processed message fi (m2) to node 1, and then, in layer2, node processes the received message fi (m²) and returns the processed message [o( (mz)) to node 2.
message passing is often random, so we endow the two mappings with 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}" and the mapping is selected with a certain prob- ability, 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 natural- ly present the Iterative Graph Neural Network System (IGNNS), whose core layer is constructed describes the differences in message passing patterns among GCN, Bi-GCN and IGNNS. At the same time, regard undirected graph as a directed graph with equal probability of bidirectional message passing (see Figure [ [a)), so the IGNNS architecture can handle directed graph and undirected graph in unified way.
by IFS. Figure [
2 PRELIMINARIES
A graph G = (V, E) is defined by its note set V {vi, 02 U2....,NNi aND and edge set E {(vs, vy)lu,, "i E V}. Let
R denote the adjacency matrix 9, providing with relation- al information between nodes. Aii denote i, jth element of A, A means the ith row, and | means the jth column. In this paper, we assume that all nodes of G are self adjacent, that 1, 1, 2 ..., N. let D diag(di, d2,... ..., dx) be the degree matrix of A, where d. Σ Ali,jl.
A
N
Neighborhood Normalization. There are two ways normalize A. One approach the following mean-pooling employed by Hamilton et al. (2017) and Veličković al. (2019) for inductive learning:
Amp D A
Another approach the following symmetric normalization employed by Kipf & Welling 2017
A Asym DD- AD-
Iterated Function System. A mapping f RR + R is said to be a contractive mapping on R there exists constant An iterated function system (Hutchinson 1981) is defined by
1 such that [ - [(x2) ll el|2n s2ll2 for all x1, E RV
IFS - (R>;; f1, f2, fm. fm::),
N > V is a contractive mapping and p = (p1. P2. .... Pm ) is an adjoint probabil- ity vector meaning that ft is selected by probability p, for each iteration. Hutchinson (1981 showed that there exists a unique nonempty compact set F such that
where each ft R
F =
U f())). i=l
2

---

Under review as a conference paper at ICLR 2021
A
X
An X
A X
00
fo(X) - Aux by.
fi(X) - A b
Tril
Fractal Regeisentation
Hgo
fo
P0
fo
Hg
fi
X
Matmul
Wint
ReLU
Xint
P1
Hio
fo
fi
Input laver
H11
IPS layer
Machematical
expectation
fa
MEAN CONCAT
OUTPUT
fi
Dynamic trajectory
P1
Wout
Outpat
Representation layer
Figure 2: An overview of IGNNS. The upper part of the Figure describes how to generate two affine
transformations on IR1, where the mean-pooling method to normalize A, Po
0.6, p1 0.4,
0
0
0
0
0
0
A
0
1
0
1
1
Ao
=
0
0
0
and A =
7 1
0
0
1 1
We call F' the fractal set or invariant set IFS, More conclusions on IFS can be found in the Ap- pendix D It is well known that there exists unique probability measure with support FF satisfying the equation
Pill f-!
The probability measure y T called the self-similar measure of IFS with probability vector p.
3
IGNNS ARCHITECTURE
In this section, we will introduce the architecture the IGNNS according to the input layer, IFS layer, representation layer and output layer, which is described in Figure 2
3.1 INPUT LAYER
Given a graph structure data X E NXF g (V, called as the feature matrix node set V. row of X represents the F-dimensional feature vector of node in V. Let Wint E Fx be learnable parameter matrix, where H the dimension of the latent space. Then X Wint g N The output of input layer defined by
i O (XWin)) NxH
(2)
where (--) is the activation function. Generally, ReLU(()) = max(0, x) is used as the nonlinear activation function. Here, each column of X is regarded as point in RV so X is the set of H points I N and arranged points (the ith row of X int is feature representation of the ith node of graph G.
certain order. The vector composed of the ith component these

---

Under review as a conference paper at ICLR 2021
3.2 IFS LAYER
Let A be the adjacency matrix of G. Let triul A) denote the upper triangular matrix of A and Iril( A) denote the lower triangular matrix of A. The symmetric normalization of triu( A) and Iril(A) are
briul triml A)D and A, DJ (rr
Do
where Do and Dj are degree matrices of (A) and tril(A) respectively. Sometimes, we use the mean-pooling of triu(A) A) and tril A), i.e. Ao Do (Iri(AA), A, tril(i Let fo, fi be the two affine transformations on R.,, induced by Ao. A1 respectively, defined as follows:
So x Agx + bp, x E IRN,, by E /i > A + b IR,,, ,,, E RR where bn and b are learnable biases, namely add constants bn and 6y to each component of Aox and A1 respectively. Constructing iterated function system
IFS {R fo. f1;p)
where p = (Po, P1) is learnable adjoint probability vector, satisfying Po > 0, Pi > 0 and po + Using the symbol space 2m = {0, 1 then for each (in, 12, ..., im) E Qm the length is m, denoted ji] m, and defining pt Pi, Pi.. and fi fú o fiz ....o S.m. Let be the number of iterations IFS. For IGNNS, n a preset parameter. The iterative process of IFS is
described as follows:
The first iteration (iil = 1). The result of the first iteration denoted by
( = (fo(x""), (i(i"))) =
[H
where H; = fi( "I)",,,, vi E Ωz Since IFS selects the iteration branch fi with probability ps, the mathematical expectation of H[()) is computed by
Ei Po xi) + p fi (X Ho pi Hi
Σ H.H.
1|=1
If choose bias in iterations, then Ho A. int bo: Hi AiXin in b1, where by and b are learnable -iddimensional vectors.
The second iteration (jil 2). Using the results of the first iteration the input of the second iteration, then the result of the second iteration denoted by
(2)
(), xi""), (x")) (Ji()))))) (J(((X)))) (foo(Xi"") fur (xi""), f1o (x="",,, fui(X
= {Hi) i
where H, f(xim,,, vi E Ω2g Note that IFS selects the iteration path fi with probability Pl, then the mathematical expectation of (2)2) is computed by
Eg Σ Pi
Σ P.H.,
2
1==2
We expand the expression of Eg and perceive its powerful feature representation ability. First,
Hoo (oHH)) An An mt + bo) + bo, Ho1 fol (H)) = Ao (1 X inl + b1) + bo.
H10 (Ho) An, + bo) + b, H. f (H)) Ai (A, inl + bi) + b
Then
E2 Poo + poi Hol P1oH10 + H
= (p00A00 + Pol 1 + A10 10 + P11 P1 An)
+ Ap + Asb A (1)Abbi + (poobo + Porbo Plob1 + P11b1),
where A, = A, Aig, (i1 E 92.
The n-th iteration (ji) n.). Inductively, we have
H ( [Hi)i Hi = (XiiI), E, Σ P.H.
(3)
=I=n
Note that H, NxH and each column of H; point in N so we regard subset N with H elements. Thus (())) is a subset of N with H x 2" elements (including duplicate elements).
Because of Theorem 4.1 call (n) the fractal representation with depth of notes.

---

Under review as a conference paper at ICLR 2021
3.3 REPRESENTATION LAYER
After nt iterations of IFS layer, the dynamic trajectory of IFS is obtained:
[E E2, ..., E.).
In general, the global representation R of notes is obtained by time average concatenation opera- tions on O.
R
1 n1 Σ
E, E
R 1=1 E, R-NxHH
call R the ergodic representation of notes. In practice, we adopt weighted time average or weighted concatenation. According to the Theorem C.1 we heuristic weights (Here, we understand it as the average expansion factor of the distance between two points after affine transformation). Let r / (nn(N) + +. where y s 0.577215664 is the Euler constant. Suppose r = (r1, (21,72,.., f2,..., F')) is a learnable n-dimensional vector
where is the concatenation operator. Because of Theorem 4.2
with initial value r; (+) = Then the ergodic representation of notes is
Σ
E. N or R i= r, E NxOH
3.4 OUTPUT LAYER
Let W E #xx be learnable parameter matrix, where P is the dimension of the output layer (such as the number of class labels). If R generated by O concatenation, then let Wouu E R There ways to construct output layer, one is to Single-Layer Perception (SLP) output, that is
0 RW bouts
the other is to use fo. fi for Mixed Propagation (MP), that is, let Ro fo(RWouy) and R fi (RWoat), where the biases of fo, f1 are removed, then the output
0 po Ro p Ri bout-
Where the bias ban E 1R. is an optional learnable parameter vector.
3.5 INITIALIZATION OF LEARNABLE VARIABLES
The learnable parameters of IGNNS include input layer matrix Win E FF adjoint proba- bility vector p (po. E I² of IFS, biases bu, bj E R of IFS layer, weight coefficien- r = (r T2, ra) of representation layer, matrix Wouu E RxP of output layer and bias Duut E R. of output layer. Among them, Wint and Wourt are the required learnale parameters, using the initialization described in Glorot Bengio (2010); by, b, and b are optional learnable parameters with initial value 0: p is optional learnable parameter, for undirected graph, setting Po E [0.5 0.1, 0.5 + 0.1], and for directed graph, setting (For the reasons, see Appendix
det D Po det Do + det D2 P1 det Do + det D
det Do
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 as the depth of IGNNS. Thus, IGNNS denoted
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.
O 1-INNNS X, A; Wini n, p, bo. b Woul bous) or simply
3.6 THEORETICAL TIME COMPLEXITY OF IGNNS
Let n, N, H. be defined as above. Let T(-) denote the number of calculations of object. For input layer.
T(input layer) NFH NH O(NFH).

---

Under review as a conference paper at ICLR 2021
For IFS layer, during the iterative calculation, we will store the previous calculation results, thus
T(HHA) H, T(HH() ) 2 ( = 2, n..,
n. It follows that T(H)()) ) N
1,2,..,, n. Similarly, T( T(ppi [pi = i)} 2i, 1, ..... Complete the above caleulation, it is easy
to see that TEE)) = 2' N.H. Thus
T(IFS layer)
Σ (T(HO) + T(p( -3) + - 0
is easy to verify that (rrepresentation layer) = O(nNH). We assume that the output layer is constructed by mixed propagation, then T(output layer) = O(N2P) if Wan E R Rxxx, and T(output layer) = O(N2P nNHP) if Woa E RRHHPP. Then
TIGNNSS) O(2" N2 N2P) or O(2"N² N
In practice for large graphs, 2 N > NºP > nNHP, thus N is the main factor affect- ing 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 < (see Appendix
GEOMETRIC PROPERTIES OF IGNNS
The discussion here assumes that affine fu- fi are contractive. Otherwise, let fo A Mo Agæ= + by and fi : x + || A1 + by In practice, IGNNS does not use contrac- tive 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- weo-thio (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 certain value and thus become indistinguishable of deep GNN, people need to use some new methods such as Skip connection
order to overcome the over-smoothing problem (2188), 2018)) Drop
edge (Rong et al., 2020). Residual connection (Kiicpera 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 al. (2020) proposes guiding theoretical framework.
Theorem 4.1 (Fractal generation) Let H (Hi) M which is subset RN with H x 2 elements (including duplicate elements), then
dh (H(()), [[) 0, n 00
where du is the Hausdorff distance defined on H(BIN),, ). the set of all nonempty compact subsets of RN, and E is the fractal set of IFS in IGNNS. In other words, as the number of iterations increases, (())) will be independent of node feature X, only related to the graph structure described by A.
Let T be the Hutchinson operator on H(RR)), defined as T(B) = fo(B)UU(()) AB E H(RR)).
Then the updated rule of (H))) satisfies
(n) T(H(--1) ... =.. ITT
where ()) = {xri is a subset of IR with H elements. In fractal geometry, ([)) is used to draw
the fractal image on the plane. First, taking initial value H)))) = { where xo is a point in plane. For enough n, printing all the points of (( on the screen to obtain the approximate fractal image.
Theorem 4.2 (Ergodic property) Let E,, EmH=a DiH be the mathematical expectation of (m)) Hi)) M= then En, converges to a constant matrix E E RRNH in Frobenius norm, i.e. lim E. = E, where =]i (ei, Ct,...,,,) e,)T E R and R is constant, 1,2,.... N. Furthermore, the time average of the dynamic trajectory O of IFS satisfies
lim ΣE
E.
lim E, E
and series Di= E, E N converges in Frobenius norm.

---

Under review as a conference paper at ICLR 2021
Table 1: Summary statistics of the benchmark datasets used in the experiment.
Dataset
Nodes
Edges
Features
Classes
Training
Validation
Testing
Cora 2708
5429
1433
140
500
1000
Citeseer
3327
4732
3703
6
120
500
1000
Pubmed
19717
44338
500
3
60
500
1000
Theorem 4.2 shows that as long 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 p(Ao) p(A1) IFS is not contractive in general, and IGNNS still has the ability of depth feature representation.
5 EXPERIMENTS
5.1
EXPERIMENTAL TASK: SEMI-SUPERVISER NODE CLASSIFICATION
Let Z = softmax O), where Z E R and softmax(-) is the softmax activation function, defined softmax(2;) 2 exp(I;; with Z = Σ, exp(2;), is applied row-wise. For semi-supervised multiclass classification, we employ the following cross-entropy to evaluate error over all labeled examples: L = Eiev, Σ Y[, In Zí1, i), where Y, is the set of node indices that have labels with P classes, [(,: is one-hot vector of size P representing the class of node I and 2 [[, :] is the row of the matrix Z.
5.2 EXPERIMENTAL SETUP
Datasets. In our experiment, we use three standard citation network benchmark datasets for eval- uation, including Cora, Citeseer, Pubmed and apply the standard fixed training/vaiddtiion/esingg split (Yang et al. 2016 Kipf & Welling 2017 Veličković 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 one paper by another are denoted as edges. Node features are the bag-of- of-words vector of papers, and node label is the only one academic topic of a paper. See [able 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, adopt weighted time average to get the global representation of notes. In output layer, we adopt the method of mixed propagation get the output of IGNNS. We use the AdamOptimizer (P.Kingma & Bal 2015) during training. More details of hyper- parameterss 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.
5.3 EXPERIMENTAL RESULT
We compare with those models that strictly follow the standard of experiment setup of semi- supervised node classification, i.e. the standard fixed training/validaaionnesttgg split (Yang al. 2016 Kipf & Welling 2017) is applied on dataset. For baselines, we include recent deep GNN models such as JKNet (uu et al.) 2018), APPNP (Klicpera al.] 2019a), Attention- models such GAT (Veličković et al. 2018), AGNN (Thekumparampil et al. 2018) and H-GAT (Gulcehre cct 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-an shallow GNN models: Planetoid (Yang et al. (016))
GCN Kipf & Welling 2017) and DGCN (Zhuang & Ma 2018). The detailed results are shown in
Table 3
We can see from Table 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

---

Under review as a conference paper at ICLR 2021
Table 2: hyper--arameters in experiment.
Setting
Cora
Citeseer
Pubmed
Neighborhood Normalization
symmetric
mean-pooling
symmetric
Learning rate Initial value of po
0.005
0,002
0.01
0.5
0.5
0.5
Dropout
0.9
0.9
0.8
Weight decay
5e-3
5e-3
5e-3
Epochs
1000
1000
1000
Hidden dimensions
48
72
72
Number of iterations in IFS layer
4
Learnable adjoint probability vector False
True
False
Learnale representation layer coefficient
True
True
True
Use bias for IFS layer
True
False
False
Use bias for output layer
False
False
False
Table 3: Summary of classification accuracy (%) results on Cora, Citeseer and Pubmed. The results are taken from the corresponding papers. The first value in brackets indicates the total training time in seconds and the second value in brackets indicates the average training time in seconds per epoch.
Method
Cora
Citeseer
Pubmed
Planetoid ( Yang et al.
2016
75.7
64.7
77.2
GCN Kipf & Welling
2017
81.5
70.3
79.0
GAT Velickovic et 2018)
83.0
72.5
79.0
TAGČN (Du et al.
2017
83.3
71.4
81.1
JKNet (Xu
al. 2018)
81.1
69.8
78.1
AGNN
Thekumparam
et al.
2018
83.1
71.7
79.9
N-GCN
Abu-EE-Haupe et al. 2018
83.0
72.2
79.5
DGCN
Zhuang & Ma
2018)
83.5
72.6
80.0
APPNP
Klicpera et al.
2019a)
83.3
71.8
81.1
H-GAT
Gulcehre et al.
2019)
83.5
72.9
IGNNS
(ours)
86.3(44s, 0.17s)
75.1 0.16s)
80.5(221s, 1.47s)
the characteristics of these citation networks. We consider statistical properties of networks, 2h
one is the Network Density d(G), which is defined as d(g) N(N-Ij+ where N is the number of nodes and L is the number of edges, and the other is the Average Clustering Coefficient C, which defined as C = t Σiev C₁, where is the set of nodes, C, = IIj k; is the number of the neighbors of node and is the number of undirected edges between k; 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 We can see from Table 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.
5.4 PERFORMANCE OF COMPLETELY LINEAR IGNNS
In Nonlinear IGNNS, we use the nonlinear activation function ReLU(x), learn adjoint probability Rel.U
vector p (po, p1) by po Rel.Upp-) PI RelLU and learn the rep- resentation layer coefficient r = (r1, F2, (,,, by Ti < ReI.U(r;) with initial value r; = (2)* - where //n(N) 0.577215664. In this experiment, to get completely linear IGNNS, let all the activation functions be the identity function, i.c. o(x) = x, and let the adjoint probability vector p (po. P1) and the representation layer coefficient (r1, r2,..., be hyperparameters
RelUU( )+00.1
8

---

Under review as a conference paper at ICLR 2021
Table 4: Statistical characteristics of the networks. Bold for minimum.
Statistical characteristics
Cora
Citeseer
Pubmed
Network Density
0.00144000 0.24067330
0.00084514 0.14147102
0.00022805
Average Clustering Coefficient
0.06017521
Table Performance of completely linear IGNNS on Cora, Citeseer and Pubmed.
Method
Cora
Citeseer
Pubmed
GCN Kipf & Welling 2017 IGNNS(Linea)
81.5
70.3
79.0
83.9
72.4
79.9
without learning. For Citeseer, we let = 0.6, and for Pubmed, we use bias for IFS layer. Ex- cept 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 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 Ao and A1 be defined 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 To Xintt X Wint E Nx1 Let 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) Ar b. fo(x) Aox + and fi are
Ai + b1. For GCN, the message passing results
(sxr)), U (zo)). (xo))
We see that each iteration only gets one value, i.c. [(f"(z))) 1. For IGNNS, the message passing results are as follows:
(o(zz)) (zo)), (()o),
(f((6(zo)), (o(f (i (((2))))
((fi
If fo and fi satisfy separation condition, i.c. fo(x) = (v) implies = y. then ((f(zz)) )ij 2". This means that IGNNS can extract more information than GCN. Even if fo and fi are con- tractive mappings. by Theorem 4.1 we have (fi(z)) - F, where IF is the fractal set of IFS induced by fo and fi. Generally speaking, IF is uncountable compact set. This means that when large, the features may still distinguishable.
CONCLUSION
In this paper, we propose new framework of graph neural networks, IGNNS, which give a con- nection between Graph Neural Networks and Iterated Function System. We use IFS simulate the bidirectional message passing process of graph neural network, and obtain the fractal representa- tion 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]" to reduce the computational complexity, coding graph structured data with IFS, and establishing more interesting connections between IFS and graph neural networks.
REFERENCES
Sami Abu-FilHaija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN: multi-scale graph convolution for semi-super node classification. CoRR, abs/1802.08888. 2018. URL http:
M.F. Bamsley. Fractaly Everywhere. Academic Press, 1988.

---

Under review as a conference paper at ICLR 2021
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.
Jian Du, Shanghang Zhang, Guanhang Wu, José M. F. Moura, and Soummya Kar. Topology adaptive graph convolutional networks. CoRR, abs/1710.10370 2017. URL http://arxiv. /rrg abs/ 20s0/110... 10370
J.H. Elton. An ergodic theorem for iterated maps. Journal of Ergodic theory and Dynamical Systems, 7:481-488, 1987.
K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, 1990.
Tsu-Jui Fu, Peng-Hsuan Li, and Wei-Yun Ma. GraphRel: Modeling Text Relational Graphs for Joint Entity and Relation Extraction. Association for Computational Linguistics, July 2019. URL
https: wwwp/wwwwwww...c..////// http://wwww.....r..c.oooooo/////
Xavier Glorot and Yoshua Bengio. Understanding the diffificulty of training deep feedforward neural networks. In AISTATS, volume pp. 249-256, 2010.
Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, and Nando de Freitas. Hyperbolic attention networks. In ICLR, 2019.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Hutchinson. Fractals and similariii Indiana University Journal of Mathematics, 30:713-747, 1981.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
J. Klicpera, A. Bojehevski, and S. Gunnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019a.
Johannes Kliepera, Janek GroB, and Stephan Günnemann. Directional message passing for molec-
ular graphs. In International Conference Learning Representations (ICLR), 2020.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem Deepergen: All you need to train deeper gens. 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018b.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In EMNLP, 2017.
P.R. Massopust. Fractal Functions, Fractal Surfaces, and Wavelets. Academic Press, 2017.
Zhewei Wei Ming Chen, Bolin Ding Zengfeng Huang, and Yaliang Li. Simple and deep graph convolutional networks. 2020.
V. Nair and G. E Hinton. Rectified linear units improve restricted boltzmann machines. In ICML, 2010.
Diederik P.Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimizaiton. In ICLR, 2015.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2020. URL https: //wpee/eeeeeeeeeeeeeeeeemeeeeeee net. wow.mr tt
Scarselli, M. Gori, A.C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Trans. Neural Netw. Learn. Syst, 20(1):61-88) 2009.
10

---

Under review as a conference paper at ICLR 2021
M. Schlichtkrull, Thomas Kipf, Bloem, R. V. Berg, Ivan Titov, and M. Welling. Modeling rela- tional data with graph convolutional networks. ArXiv, hts//703300103 2018.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1): 1929-1958, 2014.
Kiran K. Thekumparampil, Chong Wang. Sewoong Oh, and Li-Jia Li. Attention- based Graph Neural Network for Semi-supervised Learning. arXiv e-prints, art. arXiv: 1803.003333 March 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, accepted as poster.
2018.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. In International Conference on Learning Representations, 2019.
URL httphhttsss/oppeeeiiieee
net met//ooumm? babrum?id=rke (edddrkiziiiee Z91AcKQ
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Keyulu Xu, Weihua Hu, and Jure Leskovec. How powerful are graph neural networks. In ICLR, 2019.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? 2020.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervisee learning with graph embeddings. In International Conference on Machine Learning. 2016.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph- based cemi-supervised classification. In WWW, 2018.
A THE FRACTAL REPRESENTATION OF GRAPH & WITH ONLY ONE SELF ADJACENT NODE v.
For the sake of discussion, assume that the dimension of the hidden space is equal 1. We assume that messages are sent from node propagate in two directions (clockwise and anticlock- wise), 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 constant of 2 It expressed by mathematical formula as follows
3
2
fo(z) (z)
f1(z)
IE
For Bi-GCN, messages are delivered independently 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 Zi R be the initial message. the clockwise direction, after passes, the received messages are
Zo Zo
Zo
3
32
3
In the anticlockwise direction, the received messages are
2
2
2
30
2 3
1.
31
32
3
For IGNNS, the two channels have connection point node First, node sends the message 2o in both directions, and the connection point of node v will receive two messages {f((z)) fz)))) In the second launch, any message (fo(zo) fi fi())) can be sent in both directions, so the received messages are
(Jo(fo(za)) folh (zo)), (( (())))

---

Under review as a conference paper at ICLR 2021
Initial message
1.4
Bi-GCN (Clockwise)
Bi-GCN (Anticiockwwise)
1.2
Fractal representation of IGNNS
1.0
i
i
0.8
0.4
0.0
Initial message Xo
1/4
1.0
?
?
?
:
1
:
Received message
0.6
GCN (Clockwise) Bi-GCN (Anticlockwise) Fractal representation of IGNNS
0.4
0.2
|
I
0.0
2
5
7
8
Depth of network
Figure 3: Comparison of feature extraction ability between Bi-GCN and IGNNS. Bi-GCN gets boundary messages and IGNNS gets all messages.
In summary, After n passes, the received messages are
H (((ra)))=== C,
where C is the famous Cantor Set. This means that we have not only received one message, but 2", since fu and fi satisfy the separation condition. We can see from Figure that Bi-GCN gets boundary messages and IGNNS gets all messages. Letp (Po.P) be the adjoint probability vector, then the mathematical expectation E,, of H())) is Eji= (=fi( We interpret E,, as the average of all messages received. Now the question is, fractal representation gets enough messages, but is there redundancy these messages? How to select the valid message from the fractal representation becomes the focus of our research in the next stage.
B ANALYSIS OF TIME COMPLEXITY ON CORA, CITESEER AND PUBMED.
From section 3.6 we have known that the time complexity in Experiment 5.1 is N2
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, compare the real running time (100 epochs) of IGNNS on Cora, Citeseer and Pubmed. Let H = 8, then 2n 2 H is the main factor affecting the time complexity of IGNNS. Let the depth of IGNNS
12

---

Under review as a conference paper at ICLR 2021
hidden=8, epoch=100
cora
citeseer
600
pubmed
500
Training time(s)
300
200
100
0
3
Depth of IGNNS
Figure Real training time on Cora, Citeseer and Pubmed.
go from and compare the real training time on Cora, Citeseer and Pubmed. We can see from Figure that the actual results are basically consistent with the theoretical analysis results.
C FROBENIUS NORM OF MATRIX
Theorem C.1 Lei A E ERNN be the adjacency matrix of graph with no weights, i.e. Ai, there exists edge i j in the graph and A 0 otherwise, and A Dj tril(A) (or A DJ tri) as defined in IGNNS, then
|| 2 vIn(N)+ +%
where y x 0.577215664 is the Euler constant.
Proof. Case 1: Ai DJ tr), Let tril(A) (a.))NxN, Di diag d1, de...., dp) be the degree matrix of tril(A) and A₁ = (by))xxN- Note that tril( A) is an lower triangular matrix, then d, Σ aij- Ej= Aij. Since di {0, 1]. we have i 2 d. Computing the Frobenius Norm of A as follows:
N
2
agj
|
(4)
de
Vi E (1,2,.., N), note that d, elements in {ai5} are and the rest are O. It follows that
aij
1 1
a
d,
2
(5)
d;
de
d
13

---

Under review as a conference paper at ICLR 2021
It follows from
and 5 that
N
|| 11
2
So |Ail|F 2 V V ; R / /In(N) 7, where y 0.577215664 is the Euler constant.
Case 2: A Dj D tril(A) Computing the Frobenius Norm of A as follows:
N
N
N
|
(6)
d,dj
1=1
j=1
f=
j=1
i=1==
Vi {1,2, NJ, it follows from j 2 dy that
Σ d:d dg
d
Note that de elements in {ais lj=1 are 1 and the rest are O. It follows from Rearrangement inequality that
$ Σ
1
1
dij
d (((i-d++1) i- d, +2 aiii-d,t2 +
a
(8)
de +
7
1=1
where 0;(i-d;-1) ai(i-d;+2)
Oj Thus
1
1
1
+
12
12 = d: x
(9)
i
j=1
It follows from 6b. and
9 that
N
A
11 N
1=1
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 (2117).
D.1 FRACTAL SPACE
Let (X;d) complete metric space. Let H(X) denote a set consisting all nonempty compact subsets of X. Hausdorff distanceon dæ H(X) defined by
dA B) maxfmax min d(a, b), max min d(a, (),, VA, H(X))
(10)
A be
Theorem D.I (H(X);dı) dz) is a complete metric space.
We call (H(X):dw) Fractal space. Let {ff]== be set of mappings on (X; Hutchinson operator T: (H(()):d)) + (H(X); dm) defined as
T(B) Ü ((B), H(X).
(1I)
1=1
Theorem D.2 If (f.)" is set of contractive mappings on (X; d), then Hutchinson operator T is a contractive mapping on (H(X))da).
14

---

Under review as a conference paper at ICLR 2021
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 ((X) be the set of all continuous functions mapping X to R. We say that f Lipl, if (f(x) - -()) [()) & d(x. y). Ve, E X. It is easy to see that f E Lipl then f E C(X). Hutchinson metric dM M defined as
dss(p, sup {/ fdp. J sav Lipl } VU, M(X).
(12)
Theorem D.3 (M is complete metric space.
Let IFS = [X; f.... fai P). the Markov operator M MM(X) - MMX) of IFS defined as
Mu Σ Piu J JT' E(X)).
(13)
1=1
Theorem D.4 Markov operator M of IFS is contractive mapping on space (M(X); dar)
Let measure sequence {ui} C M and μ E M, we call { weakly convergent to μ the following equation holds:
lim [ 8000
[dps / Idu,
(14)
denoted as 14; ">> as + oc.
Theorem D.5 If 44 du,, a + oo, then #t - μ as cc.
E THE PROOF OF THEOREM
Proof. By Theorem D.1 (H du) is complete metric space. Let T be the Hutchinson operator on H.RN), defined as (BB) = fo (B) (B)) fi vB H(RM). By Theorem D.2. T is YB
contractive mapping on (H ); dH ). It follows from the Banach fixed point theorem that there exits a unique compact subset F of H(R such that
F = T(F)
Jo (F) (R),),
which implies that IF is the fractal IFS. Further more, VB E H(R have (BB di, F. The above convergence is independent of the choice of initial value. Thus, let H) {
(2 .... hH) h. 34 E RN, we have
(n) ((H
T (H)
du F.
The above result indicates that when n is large enough, (*) is close to the fractal set F of IFS in the sense of Hausdorff distance, and has nothing to with the choice of initial value H()).
THE PROOF OF THEOREM
Proof. It suffices prove that Vj {1.2, ..., H3 Em[[,.], the column of E,, satisfies
e1
lim En
CN
Nx1
For this purpose, let xy be the j column of int as defined in 2), then 2, is a point in N Define
Dirac measure as follows:
[1 [
B,
8B(B)
(15)
0 other.
15

---

Under review as a conference paper at ICLR 2021
It is easy to see that 82 EM(RN). The Markov operator M (M M(RM) of IFS, defined
as
My Σ fo' . e M(R")
(16)
Now take no = òæ, and the results of iterative calculation are as follows:
P1 = Mpo
Pipo o 17 E prsz, o SJ = Σ prop(ce)) = Σ
Σ
00
1m0
1m0
--1
M¹ Mp1 Σ Pijl fr Σ P. Σ Piò ((a)) ff
N2
1
popoOjo((((a;))) + (oP10)((((3,)) + (iPoO + (1P10)((1())))))
Σ p())(s))
11/2
Inductively, we have
Un. M
Σ piOMay))
(17)
By Theorem D.4 it follows from the Banach fixed point theorem that there exits unique probability measure such that
dM
Pn
Pa-
The above μ.d is actually the self-similar measure of IFS. By Theorem D.5 have phn _ Mnx L.e.
f Edji = = lim n+000
Fddp.. VF C(RM).
It follows from
and that
J Ed
= lim n000
Fdum
= lim n
Fd( Σ (())))))
[1|=n
lim
Σ (:F((((a)))
n-000
lil=n
lim
p. FHH(H
AF C(R
(18)
In 18 vi (1,2,...,N) N), take the continuous function F, to satisfy
Et(t) = t,, vt (t1, t2 tN) E N.
It follows from
18 that Vi (1,2,...,N) N).
lim Exii.l
= lim
Σ H[i = lim Σ (.F((HH(:
000
m00
n
=
W==n
/ F.(t))pu.(t) (xdp, (td)))()
t,du. (t) es-
(19)
Which combined with simple mathematical analysis technology completes the proof.
16

---

Under review as a conference paper at ICLR 2021
G How TO SET THE INITIAL VALUE OF ADJOINT PROBABILITY VECTOR?
The geometric meaning of matrix determinant det A is the expansion factor of graph volume under linear transformation A. Let If be the fractal of IFS as defined in IGNNS, Then
F (F (IF).
Note that
volume (F((F)
det A,
0,
volume(F)
can be seen that the value of det A, is large. it reflects that (FF has large share in therefore, when selecting the iterative function, f. should have greater probability of being selected. So set
dct Ao det Ao + det A
det A
det Ao det A
Note that Ao. A, are triangular matrixes and the diagonals of triu (A), tril(A) are equal to follows from Ao Dj (r) (or Ao Do tr 2) that det An det De Similarly, det A1 det Di It follows that
det D1
det Do
P1 det Do det D1 where Do and D are degree matrices of triu A) and tril(A) respectively.
Po det Do det D
17


Reviews:
[{"review_id": "xQhaZs2yMeu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper 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. \n\nRoughly speaking, the main idea is to use 2 linear mappings f_0 and f_1 which correspond to the two directions. For the given input vector x, in each of the n iterations, we apply one of the two linear mappings randomly (the probability of applying each mapping is a learnable parameter), and we use the expectation of the resulting vector as the representation. The authors argue that the resulting symbol space could have sufficient size if n is sufficiently large. \n\nThe main idea looks reasonable and interesting. My major concern is about the experiment part (and thus my recommendation would just be weak acceptance) . The authors only perform experiments on three datasets, and it is unclear if the same approach will be effective on other datasets/settings. Moreover, although we see performance improvement on two of the three datasets, necessary discussion about the experimental results is missing. It would be great if the authors could explain why the proposed method improves the performance on Cora and Citeseer, and achieves worse performance compared to some of the baselines on Pubmed, to give the readers a better idea when this new framework would be effective. \n\n***Post Rebuttal***\nI have read authors' response and other reviewers' reviews. After reading it is still unclear to me why sparsity of the networks could affect the performance of the proposed framework. Therefore I would like to keep my original score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "H0Uqn3euSt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis 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.\n\nPros:\n\n1.The proposed architecture achieves empirical improvement on citation network datasets.\n\n2.This work also provides some theoretical analysis for the proposed architecture: it analyzes the geometric properties of IGNNS from the perspective of dynamical system.\n\n\nCons:\n1.It seems unclear to me how the theoretical analysis via IFS could be used to explain the empirical performance gain on citation networks.\n\n2.According to the formulas in equation (3) and above on page 4, it seems that the mathematical expectation $E_n$ is still linear (affine) w.r.t. to the input $X^{\\text{int}}$. Then if we use a learnable matrix to learn such combinations of matrices $A_i$ and probability vector $p_i$, would this be equivalent to applying an MLP to for each the message passing iteration (the adjacency information in $A_i$  is accessible to update the MLP via backpropagation)?\n\n3.In Figure 1, how would the message passing in d) be different compared to the message passing in c) after two iterations?\n\n4.It would be nice for the authors to provide a theoretical analysis on the computational complexity for the proposed architecture IGNNS.\n\n5.It would be nice for the authors to provide discussions with relevant works [1-3] on graph neural networks. [1] proposes a generalized aggregation function that allows successful and reliable training of very deep GCNs and how the proposed theorems in work could unify the mixed results (as Thm 4.1 and 4.2 state that the characterization ability of IGNNS would decrease with the increase of IFS iterations). [2] proposes a method for directional message passing as well. [3] proposes a theoretical framework for analyzing which type of GNN would achieve better generalization performance on the given task, which is also related to this paper for explaining the performance gain by IGNNS.\n\n6.The quality of the writing could be much more improved. It would be nice for the authors to provide:\na) better intuitions on its analysis using IFS (e.g. what is the physical meaning of the fractal set in IFS and why is it important). \nb) more connections between its proposed architecture and the empirical experiment section (e.g. how the proposed theorem could explain the performance gain connections)\nThere are also grammar mistakes in the paper which may hinder the understanding of the readers (e.g. last sentence in the abstract).\n\n[1] Li, Guohao, et al. \"Deepergcn: All you need to train deeper gcns.\" arXiv preprint arXiv:2006.07739 (2020).\n\n[2] Klicpera, Johannes, Janek Groß, and Stephan Günnemann. \"Directional message passing for molecular graphs.\" arXiv preprint arXiv:2003.03123 (2020).\n\n[3] Xu, Keyulu, et al. \"What Can Neural Networks Reason About?.\" arXiv preprint arXiv:1905.13211 (2019).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4nbRwGYPslj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall, this paper proposes Iterated Graph Neural Network System, which provides a novel way for computing GNN messages.\n\nHowever, there lack enough discussions with existing multi-layer GNNs. \nThe paper mentions that \"the message passing in the two directions is independent and lacks of interaction\". While this is true for a single layer GNN, when the GNN is multi-layer, the messages sent in deeper layers contains fused information from multiple directions. \nFurthermore, if skip connections are used, the messages sent in deeper layers can have even richer information.\nThese discussions are lacking in the current paper.\n\nMoreover, the evaluation is very insufficient.\nFirstly, the paper mentions a General Framework in Section 5, including a new model R-IGNNS. However, no evaluation is made at all. I would regard the experiments as incomplete.\nAdditionally, there is no further analysis or ablation study provided. While the performance improvement seems to be hugel, without those analysis, it is really hard to understand where the improvement comes from.\n\nMore comments:\n1 \"Therefore, the above architectures can not deal with directed graph directly\". I believe this is not the case: existing GNNs can naively work with directed graphs by doing message passing following the edge direction.\n\n2 The paper mentions after Eq (3) that H^(n) has H x 2^n elements. Will it be a scalability concern?", "extra_scores": {}, "extra_text": {}}, {"review_id": "3JSklwPNdKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The 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.\nExperiments on citations datasets show significantly better results than those obtained by many different related works.\n\nThe paper proposes an interesting approach, but personally, I found the document a bit foggy in some parts. On page 2, iterated function systems are introduced, but the definition does not explain what the f_i functions are, how many functions there may be and how the probabilities are related to the functions. This detail can be assumed in section 3.2 when the expected values are computed using the probabilities from the p set. However, in this section there are undefined symbols, such as p_{00}, p_{01}, etc., which make it difficult to follow the explanation of the step.\n\nIn section 3.2, a short discussion of the value of n (the number of iteration) should be added to say whether this value depends on the input graph, on the values of the H matrices in each iteration or something else.\n\nIn section 3.3, to compute the global representation R one can decide between two different definitions. These two definitions are very different and combine the results of each iteration. However, it is not clear to me how I should decide which one to use. I would like to see in the paper an explanation of what they represent and why it is more useful to calculate an average or a concatenation of the results of each iteration instead of considering only the results of the last iteration (which should depend on all the previous one).\n\nAs regards the experiments, the results seem promising, but information on trining time should be added.\nUnfortunately, however,  the description of the datasets used is too simplified.  It should explain how the nodes are extracted from those available in the datasets and why only 20 nodes per class are extracted. It seems that only very few nodes are considered despite the availability of a large number of them. In addition, details about the edges connecting the nodes and the features can also be useful, as not all the edges/features will be considered since only 20 nodes per class are used. It is necessary to explain if these nodes belong to only one class or to several classes because there could be unbalance problems. Also, it is not specified which function is used in the representation layer.\nIt would be interesting to understand what happened for the Pubmed dataset. Probably the result depends on the small percentage of nodes considered.\n\nPros\n- The results seem interesting\n\nCons\n- Overall the proposal seems interesting, but its description lacks important definitions.\n- Code and datasets are not available. Unfortunately, this does not help to evaluate the proposal.\n\nTypos\nThe second line of section 3.4: labels instead of lebels\nIn theorem 4.2 furthermore instead of further more\nIn the references, arXiv URLs are not well-formed.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers found the new framework interesting. However, reviewers are unsatisfied with empirical evaluations. More experiments and discussion are needed.
Decision: Reject