A Hierarchy of Graph Neural Networks Based on Learnable Local Features
Authors: Michael Lingzhi Li
Meng Dong
Jiawei Zhou
Alexander M. Rush
Venue:  (2020)
Keywords: Graph Neural Networks
Hierarchy
Weisfeiler-Lehman
Discriminative Power

Abstract: Graph neural networks (GNNs) are a powerful tool to learn representations on graphs by iteratively aggregating features from node neighbourhoods. Many variant models have been proposed, but there is limited understanding on both how to compare different architectures and how to construct GNNs systematically. Here, we propose a hierarchy of GNNs based on their aggregation regions. We derive theoretical results about the discriminative power and feature representation capabilities of each class. Then, we show how this framework can be utilized to systematically construct arbitrarily powerful GNNs. As an example, we construct a simple architecture that exceeds the expressiveness of the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theory on both synthetic and real-world benchmarks, and demonstrate our example's theoretical power translates to state-of-the-art results on node classification, graph classification, and graph regression tasks. 

Under review as a conference paper at ICLR 2020
A HIERARCHY OF GRAPH NEURAL NETWORKS BASED ON LEARNABLE LOCAL FEATURES
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are a powerful tool to learn representations on graphs by iteratively aggregating features from node neighbourhoods. Many variant models have been proposed, but there is limited understanding on both how to compare different architectures and how to construct GNNs systematically. Here, we propose hierarchy of GNNs based on their aggregation regions. We derive theoretical results about the discriminative power and feature representation ca- pabilities of each class. Then, we show how this framework can be utilized to systematically construct arbitrarily powerful GNNs. As an example, we construct simple architecture that exceeds the expressiveness of the Weiseeiler-Lehman graph isomorphism test, We empirically validate our theory on both synthetic and real-world benchmarks, and demonstrate our example's theoretical power translates to strong results on node classification, graph classification, and graph regression tasks.
INTRODUCTION
Graphs arise naturally in the world and are key to applications in chemistry, social media, finance, and many other areas. Understanding graphs is important and learning graph representations is key step. Recently, there has been an explosion of interest in utilizing graph neural networks (GNNs), which have shown outstanding performance across tasks (c.g. Kipf & Welling (2016). Veličkovid eet al. ()017)) Generally, we consider node-feature GNNs which operate recursively to aggregate representations from neighbouring region (Gilmer et al.) 2017).
In this work, propose representational hierarchy of GNNs, and derive the discriminative power and feature representation capabilities in each class. Importantly, while most previous work has focused on GNNs aggregating over vertices in the immediate neighbourhood, we consider GNNs aggregating over arbitrary subgraphs containing the node. We show that, under mild conditions, there only in fact small class of subgraphs that are valid aggregation regions. These subgraphs provide systematic way of defining a hierarchy for GNNs.
Using this hierarchy, we can derive theoretical results which provide insight into GNNs. For example, show that matter how many layers added, networks which only aggregate over immediate neighbors cannot Iearn the number of triangles in a node's neighbourhood. We demonstrate that many popular frameworks, including GCN (Kipf & Welling, 2016), GAT (Veličković al. 2017). and N-GCN (Abu-El-Haija et al. 2018) are unified under our framework. We also compare each class (WL) isomorphism test (Weisteiler & Lehman 1968), and conclude our hierarchy is able to generate arbitrarily powerful GNNs. Then we utilize it to systematically generate GNNs exceeding the discriminating power of the 1-WL test.
using the Weisfeiler-Lehmen
Experiments utilize both synthetic datasets and standard GNN benchmarks. We show that the method is able to learn difficult graph properties where standard GCNs fail, even with multiple layers. On benchmark datasets, our proposed GNNs are able achieve strong results on multiple datasets covering node classification, graph classification, and graph regression.
Throuuhoutt the paper we GCN specifically refer the model proposed in Kipf & Welling (0116)

---

Under review as a conference paper at ICLR 2020
2
RELATED WORK
Numerous works (see Li et al. (2015), Atwood & Towsley (2016), Defferrard et al. (2016), Kipt Welling (0016), Niepert al. (2016), Santoro et al. (201 Veličković et al. (201 Verma & Zhang (2018), Zhang et al. (201 8a). Ivanov & Burnaev (2018). Wu et al. (2019a) for examples) have constructed different architectures to learn graph representations. Collectively, GNNs have pushed the oftt--ofttheart on many different tasks graphs, including node classification, and graph dlassffiation/regression However, there are relatively few works that attempt to understand or categorize GNNs theoretically.
Scarselli et al. (2009) presented one of the first works that investigated the capabilities of GNNs. They showed that the GNNs are able to approximate large class of functions (those satisfying preservation of the unfolding equivalence) on graphs arbitrarily well. A recent work by Xu et al. (2018) also explored the theoretical properties of GNNs. Its definition of GNNs is limited to those that aggregate features in the immediate neighbourhood, and thus is special case of our general framework. We also show that the paper's 's conclusion that GNNs are at most as powerful as the Weisfeiler-Lehmer test fails to hold in simple extension.
Survey works including Zhou et al. (2018) and Wu et al. (2019b) give an overview of the current field of research in GNNs, and provide structural classifications of GNNs. We differ in our motivation to categorize GNNs from a computational perspective. We also note that our classification only covers static node feature graphs, though extensions to more general settings are possible.
The disadvantages of GNNs using localized filter propagate information analyzed in Li et al. (0018). One major problem is their incapability of exploring global graph structures. To alleviate this. there has been two important works in expanding neighbourhoods: N-GCN (Abu-El-Haija et 2018) feeds higher-degree polynomials of adjacency matrix to multiple instantiations of GCNs, and Morris al. (2018) generalizes GNNs to k-GNNs by constructing a set-based k: WL to consider higher-order neighbourhoods and capture information beyond node-level. We compare architectures constructed using our hierarchy to these previous works in the experiments, and show that systematic construction of higher-order neighbourhoods brings advantage across different tasks.
BACKGROUND
Let G (V, E) denote an undirected and unweighted graph, where |V| N, and E Q. Unless otherwise specified, we include self-loops for every node E V. Let A be the graph's adjacency matrix. Denote d(u, v) as the distance between two nodes and on a graph, defined as the minimum length of walk between u and We further write d, as the degree of node and N NVv the set of nodes in the direct neighborhood of e (including itself).
Graph Neural Networks (GNNs) utilize the structure of graph G and node features X E R xP to learn refined representation of each node, where is input feature size, i.c. for each node E V. we have features X, E IR..
A GNN is function that for every layer at every node aggregates features over connected subgraph G, C containing the node v, and updates hidden representation H(!) = [1]] 1
Formally, define the Ith layer of GNN (with ( X,):
Agg G. (H())))
A = Com(n a("))
where is the restriction symbol over the domain G,,, the aggregation subgraph. The aggregation function Agg(-) invariant with respect the labeling of the nodes. The aggregation function, Agg(-), summarizes information from a neighbouring region G., while the combination function Com(-) joins such information with the previous hidden features to produce a new representation.
For different tasks, these GNNs combined with output layer to coerce the final output into an appropriate shape. Examples include fully-connected layers (Xu et al.) 2018), convolutional layers (Zhang et al. 2018a), and simple summation (Verma & Zhang 2018). These output layers
2

---

Under review as a conference paper at ICLR 2020
task-dependent and not graph-dependent node level output HTL) of the final Lth layer as the output of the GNN.
would omit these in framework, and consider the
We consider three representative GNN variants in terms of this notation, where W is a learnable weight matrix at layer !
Graph Convolutional Networks (GCNs) (Kipf & Welling 2016
Agg(-) (E)(
h (1-1)
Com(.) = ReLu (eLLu(a!WW)))
Graph Attention Networks (GAT) (Veličković et al. 2017
Agg(-) = Σ
softmax aEN(e)
(MLP(M(-D) (L-1), he- 1 h (1-1)
Com(.) = ReLu(a (()))())(())))))))
(v)(v)
N-GCN -Abu-EI-Hann et al.
2018)
(2-layer case):
Agg(-)
Σ Σ h(-1)
Com(-) ReLu(a!OW(())
(I)
(2EN(m1)
4 HIERARCHICAL FRAMEWORK FOR CONSTRUCTING GNNS
Our proposed framework uses walks to specify a hicrarchy of aggregation ranges. The aggregation function over node G' is permulation-invariaan function over connected subgraph Gy- Consider the simplest case, using the neighbouring vertices u E NV)),, utilized by many popular architectures (e.g. GCN, GAT). Then G, in this case is star-shaped subgraph, illustrated below We refer to that as Di (v), which in terms of walks, is the union of all edges and nodes in length-2 walks that start and end
in Figure [
To build a hierarchy, we consider benefits of longer walks. The next simplest graph feature is the triangles in the neighbourhood of v. Knowledge on connections between the neighbouring nodes of v necessary for considering triangles. A natural formulation using walks would be length-3 walks that start and end at v. A length-3 returning walk outlines a triangle, and the union of all length-3 returning walks induces subgraph, formed by all nodes and edges included in those walks. This is illustrated in Figure ass (v)).
Definition 1. Define the set of all walks of length S m returning define (v) as the subgraph formed by all the edges and nodes in Wzr(v), while L (v) is defined as the subgraph formed by all the nodes and edges in W2)+1(u).
Wm (m) For k Zt,
Intuitively, La(u) (v) is a subgraph of G consisting of all nodes and edges in the k-hop neighbourhood of node v. and (v) only differs from (v) by excluding the edges between the distance-k: neighbors of v. We explore this further in Section An example illustration of the neighbourhoods defined above is shown in Figure T
This set of subgraphs naturally induces hierarchy with increasing aggregation region: Definition 2. The D-L hierarchy of aggregation regions for a node v, (v) in gruph G is, in increasing order:
AD-L(U) = (Di()). ... (D.)),, Where Di(1) S (i)) D2(u) L2(0)
(1)
Next, we consider the properties of this hierarchy. One important property is completeness that the hierarchy can classify every possible GNN. Note that there is no meaningful complete hierarchy if G, is arbitrary. Therefore, we propose to limit our focus to those G, that can be defined as a function of the distance from v. Absent specific graph structures, distance is a canonical metric between vertices and this definition includes all examples listed in Section 3 With such assumption, we can show that the D-L hierarchy is complete:
For simplicity present the version without feature normalization using node degrees.
3

---

Under review as a conference paper at ICLR 2020
Figure 1: Illustration of D-L aggregation regions. Dashed cireles represent neighborhoods of different hops. From left to right: D1, L1, D2, and L2. Both D₁ and L include nodes within the k-hop neighborhood, but Dr does not include edges between nodes on the outmost ring whereas Lg does.
Theorem 1. Consider a GNN defined by its action at each layer:
Agg G. (H(I-1)
h Com (hg (111) a
a
Assume G. can be defined as a univariate function of the distance from Then both of the following statements are true for all =+:
Df S Go S (v),, then G. E (DD((t,LL<v))
lf S G. S. DR+i(U), then G.
This theorem shows that one cannot create aggregation region based on node distance that is "in between" the hierarchy defined. With Theorem I, we can use the D-L aggregation hierarchy to create hierarchy of GNNs based on their aggregatioon regions.
Definition 3. For ls z+, G(Dx) is the set of all graph neural networks with aggregation region G. = (x(v) that is not a member of G[L,)- G(Lx) is the set of all graph neural networks with aggregation region G. = Lx(v) that not member of G(Dx-1).
We explicitly exclude those belonging to lower aggregation region order to make the hierarchy well-defined (otherwise GNN of order ((D;) is trivially one of order G(L,)). We also implicitly define Do Lo
4.1 CONSTRUCTING D-L GNNs
The D-L Hierarchy be used both to classify existing GNNs and also construct new models. We first note that all GNNs which aggregate over immediate neighbouring nodes fall in the class of (D)). For example, Graph Convolutional Networks (GCNs) defined in Section B is in G(D;) since its aggregation is Agg(-) Σue (,)) h (1-1), and similarly the N-GCN example that these classes are defined by the subgraph used by Agg, but does not imply that these networks reach the maximum discriminatory power of their class (defined in the next section).
G(D2). Note
We can use basic building blocks to implement different levels of GNNs. These examples are not meant to be exhaustive and only serve as glimpse of what could be achieved with this framework. Examples. For every le E Z+:
Any GNN with Agg(-)
Σ
(A* (4t)vul((--)) GNN of class (Dx).
wEDa(e)
Any GNN with Agg(.)
Σ
(oat)))a is GNN of class (Txa).
(ED
4

---

Under review as a conference paper at ICLR 2020
Any GNN with Agg(-) (A28+1) you h(-1) is GNN of class (
Intuitively, (A*) vou counts all k-length walks from v to u, which includes all nodes in the k-hop neighbourhood. The difference between the first and the second example above is that in the second one, we allow (k + 1) -lennhh walks from the nodes in the k-hop neighbourhood. which promotes to be class of ((Lx), Note the simplicity of the first and the last examples: in matrix form the first is A (1-11) while the last form is Diag( A 12 H(1-1)
The building blocks can be gradually added to the original aggregation function. This is particularly useful if experimenter knows there are higher- properties that necessary to compute, for instance to incorporate knowledge of triangles, one can design the following network (see Section for more details):
Wi (H + we Diag(A"). 1 (11-1)
(3)
where W1, w2 E R are learnable weights.
THEORETICAL PROPERTIES
We can prove interesting theoretical properties for each class of graph neural networks on this hierarchy. To do this, we utilize the Seisfeiler-ehhmal test, a powerful classical algorithm used to discriminate between potentially isomorphic graphs. In interest of brevity, its introduction is included the Appendix in Section 8.I
We define the terminology of "discriminating graphs" formally below:
Definition 4. The discriminative power of a function f over graphs G is the set of graphs St such
that for every pair of graphs G2 S/g. the function has f(G,) f(22) iff G. = G2 and f(G,) & f(G2) isf G1 # G2. We say f decides G1, G2 as isomorphic if ((G)) = f(G2) and vice versa.
Essentially, S/ the set of graphs that f can decide correctly whether any two of them are isomorphic or not. We say f has a greater discriminative power than if S 2 Sg. Now we first introduce theorem proven by Xu et al. (2018):
Theorem 2. The maximun discriminative power of the set of GNNs G(D1) is strictly less than or equal to the I-dimensional WL test.
Their framework only included G(Di) GNNs, and they upper bounded the discriminative power of such GNNs. With our generalized framework, we are able to prove a slightly surprising result:
Theorem 3. The maximum discriminative power of the set of GNNs in G(L)) is strictly greater than the I I-dimensional WL test.
This result is central understanding GNNs. Even though the discriminative power of G(Di) is strictly less than or equal to the 1-WL test, Theorem 3 shows that just by adding the connections between the immediate neighbors of each node (L1 Di), we can achieve theoretically greater discriminative power.
One particular implication is that GNNs with maximal discriminative power in G(L,) can count the number of triangles in graph, while those in (DD;) cannot, matter how many layers added. This goes against the intuition that more layers allow GNNs to aggregate information from further nodes, as ((D,) is unable aggregate the information of triangles from the Li region, which is
important in many applications (see Frank & Strauss 1986), T'surraaaiis et al. (201T). Becchetti
al. 2008 Eckmann & Moses (2002).
Unfortunately, this is the only positive result
able to establish regarding the WL test the k-dim WL-test is not a local method for & > 1. Nevertheless, we are able to prove that our hierarchy admits arbitrarily powerful GNNs through the following theorem:
5

---

Under review as a conference paper at ICLR 2020
GNN Class
Computational Complexity
Maximum Discriminatory Power
Possible Learned Features
((D))
$ =(Op)
SI-WL
Node Degree
>I-WL
All Cliques
((L1)
O Np)
All graphs of S nodes
Length 3 cycles (Triangles)
> >1-WL
Length walks
((22)
O(Pp)
All graphs of S nodes
Length 4 cycles
>1-WL All graphs of I nodes
Length walks
((D))
S <(k0p)
Length 2k eycles
>I-WL
((L,)
< O(AN + Np)
Length 2/: + cycles
graphs k nodes
Table 1:
Properties of different GNN classes. Shows the upper bound computational complexity when the maximum discriminatory power is obtained. Here we assume hidden size p is the same as feature input size. Final column contains some examples of features that can be learned by each class.
Theorem 4. For all Z+, there exists GNN within the class of 9 (Lx) that able to discriminate all graphs with S le + nodes.
This shows that as k oo, we are able to discriminate all graphs. We record the full set of results proven Table The key ingredients for proving these results are contained in Appendix [8.3 and 8.4 Here see that at the ((L)) class, theoretically definition are fully connected). As we gradually move upward in the hierarchy, we are able to learn more far-reaching features such as higher length walks and cycles, while the discriminatory power improves. We also note that the theoretical complexity increases as increases.
are able to learn all cliques (as cliques by
6 EXPERIMENTS
We consider the capability of two specific GNNs instantiations that are motivated by this frame- work: W1 (!-111) + u2 Diag( (A3). (1111 (GCN-L1) and w, (1-11) + wy Diag( A4)) H1-1) W3 (3 (GCN-D2). These can be seen as extensions of the GCN introduced in Kipf & Welling (2016). The first, GCN-LI, equips the GNN with the ability to count triangles. The second, GCN-D2, can further count the number of 4-cycles. We note their theoretical power below (proof follows from Theorem 3):
Corollary 1. The maximum discriminative power of GCN-LI and GCN-D2 is strictly greater than the I I-dimensional WL test.
We compare the performance of GCN-LI, GCN-D2 and other state-of-art GNN variants on both synthetic and real-world tasks For the combine function of GCN, GCN-LI, and GCN-D2, use Com(-) = MLP (k)) where MLP is a multi-layer perceptron (MLP) with LeakyRel Relu activation similar Xu al. (2018).
All of our experiments are run with Py 1.2.0, PyTorch-Geomette 1.2.1, and we use NVIDIA Tesla P100 GPUs with 16GB memory.
6.1 SYNTHETIC EXPERIMENTS
To verify our previous claim that in our proposed hierarchy, GNNs from certain classes are able to learn specific features more effectively, we created tasks: predict the number of triangles and number of 4-cycles in the graphs. For each task, the dataset contains 1000 graphs and is generated in a procedure as follows: We fix the number of nodes in each graph be 100 and use the Erdös-Rényi random graph model to generate random graphs with edge probability 0.07. Then we count the number of patterns of interest. In the 4-cycle dataset, the average number of 4-cycles in each graph is 1350 and in the triangle dataset, there are 54 triangles average in each graph.
"hhe code is available a public github repository. Reviewers have anonymized access through supplemen- tary materials. The synthetic datasets are included in the codebase as well.

---

Under review as a conference paper at ICLR 2020
MSE Triangles
MSE # Cycles (x10*)
Predict Mean (Buseline)
125.4 10.7
36.4 =
GCN (2-layer)
506.2 + 80.9
142.3 = 19.8
GCN (3-layer)
485.0 92.4
136.7 = 18.5
GCN-LI (I-layer)
61.2 + 11.6
45.2 6.0
GCN-D2 (1-layer)
57.9 + 18.0
3.0 + 1.0
Table 2: Results of experiments on synthetic datasets (i) Count the number of triangles in the graph
(ii) Count the number of cycles in the graph. The reported metric MSE over the testing set.
Dataset
Category
# Graphs
# Classes
# Nodes Avg.
Edges Avg
Task
Cora Yang al.
2016
Citation
2,708
5,429
NC
Citeseer Yang et al.
2016
Citation Citation
3,327
4,732
PubMed Yang ct al. 2016
19,717
44,338
NC
NCI1 (Shervashidze al.
2011
Bio
4.110
29.87
32.30
GC
Proteins (Kersting ct al.
2016
Bio
1,113
39.06
72.82
PTC-MR (Kersting ct al.
2016
Bio
344
14.29
14.09
GC
MUTAG (Borgwardt al
2005
Bio
188
17.93
19.79
GC
QM7b [Wu 2018
Bio
7,210
16.42
244.95
QM9 [Wa et al. 2018
Bio
133,246
12
18.26
37.73
GR
Table Details of benchmark datasets used. Types of tasks are: NC for node classification, GC for graph classification, GR for graph regression.
We perform 10-fold tross-validation and record the average and standard deviation of evaluation metrics across the 10 folds within the cross-validation. We used 16 hidden features, and trained the networks using Adam optimizer with 0.001 initial learning rate, L2 regularization À 0.0005. We further apply early stopping on validation loss with a delay window size of 10. The dropout rate 0.1. The learning rate scheduled reduce 50% if the validation accuracy stops increasing for 10 epochs. We utilized two-layer MLP in our combine function for GCN, GCN-LI and GCN-L2, similar to the implementation in Xu al. (0018). For training stability, we limited w1, u22 E (0, 1) in our models using the sigmoid function.
Results In our testing, we limited GCN-LI and GCN-D2 to a I-layer network. This prevents GCN- LI and GCN-D2 from utilizing higher order features to reverse predict the triangles and 4-cycles. Simultaneously, we ensured GCN had the same receptive field as such networks by using 2- and 3-layer GCNs, which provided GCN with additional feature representational capability. The baseline is model that predicts the training mean on the testing set. The results are in Table 2. GCN completely fails to learn the features (worse than simple mean prediction). However, we see that GCN-LI effectively learns the triangle counts and greatly outperforms the mean baseline, while GCN-D2 is similarly able in providing a good approximation on the count of 4-cycles, without losing the ability count triangles. This validates the "possible features learned in Table [
6.2 REAL--WOLLD BENCHMARKS
We next consider standard benchmark datasets for (i) node classification, (ii) graph classification, (iii) graph regression tasks. The details of these datasets are presented in Table 3.
The setup of the learning rate scheduling and L-2 regularization rate are the same as in synthetic tasks. For the citation tasks, used 16 hidden features, while we used 64 for the biological datasets. Since our main modification is the expansion of aggregation region, our main comparison benchmarks are k-GNN (Morris et al. 2018)) and N-GCN (Abu-El-Haija et al. 2018), two previous best attempts in incorporating aggregation regions beyond the immediate nodes. Note that we can view a mnth order N-GCN as aggregating over D1, ... DDm
We further include results GAT (Vemma & Zhang 2018), GIN (Xu et al. 2018b), GNTK (Du et al. 2019), WL-subtree (Shervashidze et al. 2011). SHT-PATH. (Borgwardt & Kriegel 2005) and PATCHYSAN (Niepert al. 2016) show best performing architectures.
2018), RetGK (Zhang et al.,
7

---

Under review as a conference paper at ICLR 2020
Dataset
Cora
Citeseer
PubMed
NCII
Proteins
PTC-MR
MUTAG
QM7b
QM
GAT
83.0 + 0.7 77.6 1.1
72.5 + 0.7
79.0 0.3
74.5 + 3.5
73.7 5.6"
60.2 3.0"
84.0 8.0"
91.7 + 5.5"
115.0 + 17.5"
GIN
66.1 + 0.9
77.0
82.7 + 1.7
76.2 - 2.8
64.6 :: 7.0
89.4 8.6
WL-OA
86.1
75.3
63.6
84.5
PSAN
78.5 1.8
75.8 2.7
60.0 = 4.8
92.6 + 4.2
RetGK
84.5 + 0.2
75.8 0.6
62.5 = 1.6
90.3 + 1.1
GNTK
84.2 + 1.2
+5.6++4.22 4.2
67.9 + 6.9
90.0 + 8.5
S S-PATH
73.0 + 0.5
75.0
0.5 0.5
58.5 + 2.5
85.7 2.5
N-GCN
83.0
72.2
79.5
75.8 + 1.9"
76.5 1 1.5"
61.0
85.0 6.9 6.9
82.0 +: 5.4"
120.7 8.5
k-GNN
81.6 0.4"
0.4"
71.5
11.6::00 0.5* 0.5
79.8 4: 0.3*
76.2
75.5
60.9
86,1
75.1 8.5
104.2 + 10.4
GCN
8.
70.3 1.2
79.0 0.4
73.2 2
59.0 2.0
82.2
104.3 15.6
160.2 15.4
GCN-L1
82.5 22.5 0.3
0.3
80.2 + 0.2
79.5 1.6
77.6 = 3.8
64.1 + 2.5
86.8 + 8.3
52.4 12.44:0 4.3
78.5 + 8.6
GCN-D2
$2.9
72.3 0.3
80.2 + 0.3
77.0 2.0
77.0 = 3.0
64.6 4.1
87.8 + 5.6
49.0 + 2.9
72.3 = 13.0
Table 4: Results of experiments on real-world datasets. The reported metrics are accuracy on classification tasks and MSE on regression tasks. Figures for comparative methods are from literature except for those with * which come from our own implementation. The best-performing architectures are highlighted in bold.
Baseline neural network models use I 1-layer perceptron combine function, with the exception of k-GNN, which uses a 2-layer perceptron combine function. Thus, illustrate the effectiveness the framework, we only utilize 1-layer perceptron combine function for all tasks for our GCN models, with the exception of NCI1. 2-layer perceptrons seemed necessary for good performance NCI1, and thus we implemented all neural networks with 2-layer perceptrons for this task to ensure fair comparison. We tuned the learning rates E {0.001, 0.005, 0.01, 0.05] and dropout rates {0.1, 0.5). For numerical stability, normalize the aggregation funetion using the degree of v only. For the node classification tasks, we directly utilized the final layer output, while we summed over the node representations for the graph-level tasks.
Results Experimental results real-world data summarized in Table 4. According to experiments, GCN-LI and GCN-D2 noticeably improve upon GCN across all datasets, due to its ability combine node features in more complex and nonlinear ways. The improvement is statistically significant on the 5% level for all datasets except Proteins. The results of GCN-LI and GCN-D2 match the best performing architectures in most datasets, and lead in numerical averages for Cora, Proteins, QM7b, and QM9 (though not statistically significant for all).
Importantly, the results also show a significant improvement from the two main comparison ar- chitectures, k-GNN and N-GCN. We see that further expanding aggregation regions generates diminishing returns on these datasets, and the majority of the benefit is gained in the first-order extension (L,)). This is in contrast to N-GCN which skipped L, only used D-type aggregation regions (D2, D3 :--) which is an incomplete hierarchy of aggregation regions. The differential in results illustrates the power of the complete hierarchy proven Theorem [
We especially would like to stress the outsized improvement of GCN-LI on the biological datasets. As described in [ GCN-LI able to capture information about triangles, which are highly relevant for the properties of biological molecules. The experimental results verify such intuition, and show how knowledge about the task can lead to targeted GNN design using our framework.
7 CONCLUSION
We propose theoretical framework to classify GNNs by their aggregation region and discriminative power, proving that the presented framework defines a complete hierarchy for GNNs. We also provide methods to construct powerful GNN models of any class with various building blocks. Our experimental results show that example models constructed in the proposed way can effectively learn the corresponding features exceeding the capability of 1- I-WL algorithm in graphs. Aligning with theoretical analysis, experimental results show that these stronger GNNs can better represent the complex properties of number of real-world graphs.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sami Abu-El-Haijp Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-gen: Multi-scale graph convolution for semi-supervised node classification. arXiv preprint 0rXiv:1802.08885 2018.
James Atwood and Don Towsley. Diffussion-convllutiona neural networks. In Advances in Neural Information Processing Systems, pp. 2993-2001, 2016.
Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semi-streaming algo- rithms for local triangle counting in massive graphs. Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 16-24. ACM, 2008.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM pp. 8-pp. IEFF, 2005.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peterr Kriegel. Protein function prediction via graph kernlss Bioinformatics, 21(suppl_1) i47-i56, 2005.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Simon S Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. arXiv preprint arXiv:1905.13192, 2019.
Jean-Pierre Eckmann and Elisha Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. Proceedings of the national academy of sciences, 99(9):5825-5822 2002.
Ove Frank and David Strauss. Markov graphs. Journal of the american Statistical association, 81 (395):832-8422 842, 1986.
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 260-271. Springer, 2017.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1263-1272. JMLR. org, 2017.
Frank Harary. A survey the reconstruction conjecture. Graphs and combinatorics, pp. 18-28. Springer, 1974.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. arXiv preprint 1rXiv:1805.11901 2018.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL http::::/gaaaaaeeeeee/e// cs tu-duorodd
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.0290) 2016.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. arXiv:1801.07600 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint / 2015.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. arXiv preprint arXiv: 01111 2018

---

Under review as a conference paper at ICLR 2020
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-20222 2016.
Md Abdur Razzaque, Choong Seon Hong, Mohammad Abdullah-Al- and Oksam Chae. A fast algorithm calculate powers of boolean matrix for diameter computation of random graphs. In International Workshop on Algorithms and Computation, pp. 58-69. Springer, 2008.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. simple neural network module for relational reasoning. In Advances in neural information processing systems, pp. 4967-4976, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20 (1):81-102, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lhmma graph kernels. Journal of Machine Learning Research, 12(Sep): 2539 2561, 2011.
Charalampos E Tsourakakis, Petros Drineas, Eirinaios Michelakis, loannis Koutis, and Christos Faloutsos. Spectral counting of triangles via element sparsification and triangle-based link recommendation. Social Network Analysis and Mining, 1(2):5-81,, 2011.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /7/0. /0903, 2017.
Saurabh Verma and Zhi-Li Zhang. Graph capsule convolutional neural networks, arXiv preprint 1rXiv:1805.08090 2018.
Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Ingmar Posner, and Michael Osborne. On the limitations representing functions on sets. arXiv preprint arXiv:1901. 1901.0900, 2019.
Boris Weisfeiler and Andrei A Lehman. reduction of a graph to a canonical form and an algebra arising during this reduction. Wanuchno-Technicheskeee Informatsia, 209):12-16, 1968.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr. Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint 1rXiv:1902.0715. 2019a.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark molecular machine learning. Chemical science, 9(2):113 530. 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint 19X0:0900.00056 2019b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.00826 2018.
Zhilin Yang. William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with 2016.
graph embeddings. arXiv preprint
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirtt-Second AAAI Conference on Artificial Intelligence, 2018a.
Zhen Zhang, Mianzhi Wang. Yijian Xiang, Yan Huang, and Arye Nehorai. Retgk: Graph kernels based on return probabilities of random walks. In Advances in Neural Information Processing Systems, pp. 3964-3974 2018b.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint
2018.
10

---

Under review as a conference paper at ICLR 2020
8 APPENDIXES
8.1 INTRODUCTION TO WEISPEILER-LEHMAN TEST
The 1-dimensional Ceisfeiler-Lehmann (WL) test is an iterative vertex classification method widely used checking graph isomorphism. In the first iteration, the vertices are labeled by their valences. Then at each following step, the labels of vertices are updated by the multiset of the labels of themselves and their neighbors. The algorithm terminates when a stable set labels is reached. The details of I-dimensional Weisfeiler-Lehman (WL) is shown in Algorithm 1. Regarding the limitation of 1 1-dimensional Weisfeiler- (WL), Cai et al. (1992) described families of non-isomorphic graphs which 1-dimensional WL test cannot distinguish.
Algorithm 1 I-dimensional Weisfeiler-Lehmann (WL)
(V', E'), initial labels lo(v) for all VUV" 2: Output: stablized labels ((v) for all v E V
Input: G = EV, G'
E),
3: while (4v)) has not converged do
p Until the labels reach stabalization
4: for E V U V do
5:
M,(u) = multi-set (Ll(())euENO
6: end for
7: Sort Mv)r) and concatenate them into string (;(
8: 4(v) = fs{(v))) where is any function s.t. f(s:(v) f(s((w)) = s((u) s;(w)
9:
end while
The k-dimensional Weisfeiler-Lehman (WL) algorithm extends the above procedure from operations on nodes to operations on tuples VGG)..

---

Under review as a conference paper at ICLR 2020
8.2 PROOF OF THEOREM
Theorem. Consider GNN defined by its action at each layer:
Agg G. (H( My Com(h) d
Assume Gu can be defined as a univariate function of the distance from v. Then both of the following statements are true for all Z=
D&(v)) G. S (v), then G, E (P&(v),TT(u))
If Go S Dx)1(v), then G, E (D++1(0). (u))
Proof. We would prove by contradiction. Assume, in contrary, that one of the statements in Theorem iss false. Let & E Z Then would separate these two cases below:
Dz(v) & Go & Lu(v) Assume that Gy satisfies such relationship. Since L&(v) and (v)
only differ by the set CR(U) fey E E d(i,u) = d(j. v) = k}, G, can only contain this set partially. Let MR(v) & Ca(v) be the non-empty maximal subset of Cx(U) that is contained in
Go. Since Ma (v) + CR(v), there exists m, n with d(v, m) = d(t, n)) such that emn E (v(v) but Cmn E M& (v). Consider non-identity permutation of vertices fixing v. Then since G, is defined only using the distance function, and it needs to be permutation invariant, all esy with d(i, v) = =(j. v) = k must be Cu(v) and not in Mx) But then My( is empty, a contradiction.
(v) Go ç (D+1( Assume that G. satisfies such relationship. Consider the set difference between D2+ and Lu),, denoted as subgraph C& (v):
Ck(e) = ((())=(V( EE (v)) = (fu d(u, v) = k}. fess I (d(u, 1), d(c.))) E ((k, 1), 1k. +
(5)
Then G, can only contain this set partially. Let (v) & C& (v) be the maximal subset of Ca(vv) that contained in Gy. Since Mu( * (v), at least one of the followings must be true:
There exists with d(u, v) = k such that u E (v) but & M&(v).
There exists m, n with d(v, m) k. d(v, n) k such that eyn Cv(vv) but Cmn & My(u)
For the first case, consider a non-identity permutation the vertices fixing v. Then since G, is permutation invariant and defined only using the distance, then thus all vertices w with d(w, v) are in C (v) but not in (v). This implies V.M (v) is empty.
Using the same logic for the second case, one can conclude that ej with d(v, and d(v, m) k must be in (v) but not in M& (v). That means E (v) is empty.
Therefore, we can conclude that least one of (v) and Fr (v) is empty. Since both cannot be empty (as that means G, (v)), we must have either V. V (v) = or EM (w) 0. With the former case M2(v) (v) is not valid subgraph (as some edges to nodes with distance k: + from are in the set, but the nodes are not), and with the latter case k + 1 from e are in the set but none of the edges are), so neither of them are valid aggregation regions in our framework (our definition of GNN requires the region to be a connected graph). Thus, we reach a contradiction.
not connected (as the nodes with distance
12

---

Under review as a conference paper at ICLR 2020
8.3 PROOF OF THEOREM
Theorem. The maximum discriminative power of the set of GNNs in ((L)) is strictly greater than the I I-dimensional WL test.
Proof. We first note that GNN with the aggregation function (in matrix notation):
Agg(-) () = Diag( (
(6)
a ((L,) )-class GNN. Then note that ( (A*); is the number of length 3 walks that start and end at i. These walks must be simple 3-cycles, and thus (A*); twice the number of triangles that contains
(since for a triangle {i, j. k. there would be two walks i - j - k - i and i - k - j + i). Fürer (2017) showed that 1-WL test cannot measure the number of triangles can), so there exist graphs G1 and G2 such that 1-WL test cannot differentiate but the GNN above can due different number of triangles in these two graphs (an example are two regular graphs with the same degree and same number of nodes).
graph (while 2- WL test
Now Xu et al. (018) proved that G(Di) has maximum discriminatory power of 1-W1,, and since L1 2 D1, the maximum discriminatory power of ((L1) least as great than that of ((1)), which is 1-WL.
Thus combining these two results give the required theorem.
We here note the computational complexity of A using naive matrix multiplication requires ((N3) multiplications. However, by exploiting the sparsity and binary nature of A, there exist algorithms that can calculate 4 with O(2N) additions (Razzaque et al. (2008)) and we thus derive a more favorable bound.
8.4 PROOF OF THEOREM
Theorem. For all E+, there exists a GNN within the class of ((Lx) that is able to discriminate all graphs with + nodes.
Proof. We would prove by induction k. The base for k is simple.
Assume the statement is true for all & S k' - 1. Let prove the case for k = kk' 2 2.
We would separate the proof into three cases:
G₁ and G2 are both disconnected.
One of G1, G2 is disconnected.
G1 and G2 are both connected.
If we create appropriate GNNs to discriminate graphs in each of the three cases (say fi, f2. fa), then the concatenated function f := [f1, f2, fal can discriminate all graphs. Therefore, we would prove the induction step separately for the three cases below.
8.4.1
G1 AND G2 DISCONNECTED
We would use the Graph Reconstruction Conjecture as proved the disconnected case (Harary 1974):
Lemma 1. For all 2 2, two disconnected graphs G1, G2 with VV = V/l k are isomorphic if and only the l sized subgraphs for these two graphs isomorphic.
13

---

Under review as a conference paper at ICLR 2020
Let G1 and G2 be any two disconnected graphs with k' + nodes. By the induction assumption, there exist a GNN in ((vx) such that discriminates all graphs with k nodes. Denote that fw + RR
Then by Lemma above, we know that G₁ and G2 are isomorphic iff: (G(())) ... fx(( +)) = (Gx)) ... Se
Where GI, ... Gh'+1 are the k' + subgraphs of G₁ with size k', and similarly for G2. Then we define:
K'+1 GG) (fw(()))
i=1.-..+
fw fG+ (f . [G)
Then, by Theorem 4.3 in Wagstaff et al. 2019), f (G) is injective, permutationiinvaric function on {fr (G'), for (G ( }) Therefore, f (G) is GNN with aggregation region of Lx44 that can discriminate G1 and G2. Thus, the induction step is proven.
8.4.2 G1 AND G2 CONNECTED
In the case where both G and G2 are connected, let U1, Mj be two vertices from each of the two graphs. Note that since G1 and G2 have + nodes, by definition Lxs, we have L (vi) = Gi and (wz) G2. Since 11, U1 are arbitrary, every node in the two graphs has aggregation region of its entire graph. Then we define the Aggregation function as followed:
Ag LO()
Where AL is the adjacency matrix restricted to the (v) subgraph, and LO(A) returns the lexicographical smallest ordering of the adjacency matrix row-major vector among all isomorphic permutations (where nodes are relabeled) For example, take:
A A= A 0)
There are two isomorphic permutations of this adjacency matrix, which are:
(i ( } i
The row-major vectors of these two adjacency matrices are 1, and [0, 1, 1, 1]. in which [0, 1, 1, 1] is lexicographical smaller, so LO(A) 1, 1,1,1. 1]. Note that this function is permutation invariant.
Then for G1 and G2 connected, AL (v) is always the adjacency matrix of the full graph. Therefore if G2 and G2 are connected and isomorphic, then their adjacency matrices are permutations of each other, and thus their lexicographical smallest ordering of the row-major vector form of the adjacency matrix are identical. The converse is also clearly true the adjacency matrix determines the graph.
Therefore, this function discriminates all connected graphs of k' + nodes, and the induction step is proven.
8.4.3 G1 DISCONNECTED AND G2 CONNECTED
In the case where G₁ is disconnected and Gz is connected, we define the aggregation function as the number of vertices in L (v), denoted V (igr(t)):
Agg(v) (V)
'Strictly speaking, for consistency the output length, we would require padding to length of (k' + 1)² the adjacency matrix restricted to the Ly (v) subgraph is not the full adjacency matrix. However, since we only care about the hehavior of the function when G1 and G2 are both connected, this scenario never happens, it is material for any part of the proof below.
14

---

Under review as a conference paper at ICLR 2020
This is permutation irrnutation-invariantt function. Note that for the connected graph G2 and any vertex in G2, this function returns Ag = k' + 1 as Lx((1) G2. Therefore, every node has the same embedding k' + 1.
On the other hand, for the disconnected graph G1, let 10 Um be the connected components of G1. Then for a vertex E U, it is clear that Tg-(1) (u) = U,, and thus Agg(u) (u) = VV, I for all u E U,- And since Vv, < k + by construction, Agg(u) < k' + 1 for all u E U., so the embedding of G₁ and 22 are never equal when G1 connected and G2 disconnected.
Therefore, this function discriminate all graphs of k' + nodes in which one is connected and one is disconnected, so the induction step is proven.
15


Reviews:
[{"review_id": "rygpeIGAKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a generalized framework for GNN. It proposes a representational hierarchy of GNNs. (D-1, L-1,..D-n, L-n). L-k is the k-hop neighborhood including all edges. And D-k is L-k without edges between the outermost nodes. The discriminative power of a network using L-1 is > WL-1. On various graph classification/regression tasks, the proposed method shows good performance. Show promising result on QM7b QM9 graph regression task  (counting triangles, cycles etc) which are highly relevant to the proposed method.\n\nSome concerns:\n\n1, the theoretical results seem a bit incremental compared with (Xu et al. 2018).\n\n2. it would be nice to comment on how this will affect cases with nontrivial node features and general node classification tasks.\n\n3.  the empirical results are not very convincing. On standard datasets/tasks, the baselines are not state-of-the-arts. The results only show the advantage of the proposed idea over basic GCNs. Synthetic and results on QM7b QM9 are specific for triangles and cycles which is the model designed for. Overall, it is not very clear what the proposed idea brings to GNN in a general setting.\n\nGiven these concerns, I am leaning toward weak reject at this moment. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "r1gNFCj0FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a general class of GNN. The new model class generalizes the aggregation step to multiple levels of neighbors. The new model generalizes existing models. Theoretically, the paper shows the generalized models enjoy better discriminative power. The paper also conducts experiments to demonstrate the effectiveness of the new model class.\n\n\nComments:\n1. The design of new models is straightforward, and the theoretical analysis is trivial, given Xu et al. 2019. The paper would be improved if the author(s) can provide optimization or generalization analysis.\n\n2. The statement about experiments is misleading. The paper claims SOTA results on several datasets. However, this paper does not report recent SOTA results:\nhttps://arxiv.org/abs/1809.02670\nhttps://arxiv.org/abs/1810.00826\nhttps://arxiv.org/abs/1905.13192\n\n3. The use of the phrase \"random walk\" is weird. As there is no randomness at all.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xXObBAFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes minor modifications to Graph Convolutional Networks (GCNs) that as proven by the authors enable learning of local features in networks, namely the aggregation over powers of the adjacency matrix (effectively counting random walks within the neighborhood) and aggregating over connections within nodes in the neighborhood.\n\nGCNs are of interest to \nThe paper is well written and clear.\nThe mathemeatical derivations are clearly structured.\nThe authors provide a large set of experiments on simulated and real data from different domains and relevant supervised tasks (node classifiation, graph classification and graph regression).\nSource code is provided.\n\nexperimental results:\n- For the simulation in Table 2, a 1-layer network seems like it would hield an advantage for the unstructured Erdös Renyi graphs. As I understand, the proposed GCN should by construction count the triangles (target variable) for each node embedding and then predict a linear function of those aggregated. My intuition says that this may even be an advantage over adding more layers. The text states the opposite. Here it would be interesting to see the effect of adding layers, or aggregating over longer random walks.\nHere, it would be important to get the prediction of an untrained baseline in addition to the GCN baseline (e.g. the expected number of triangles/4cycles based on number of nodes in the Erdös Renyi model) to understand the scale the Mean Squared Error lives on and what the relative improvement means.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a modification to GCNs that generalizes the aggregation step to multiple levels of neighbors, that in theory, the new class of models have better discriminative power. The main criticism raised is that there is lack of sufficient evidence to distinguish this works theoretical contribution from that of Xu et al. Two reviewers also pointed out the concerns around experiment results and suggested to includes more recent state of the art SOTA results. While authors disagree that the contributions of their work is incremental, reviewers concerns are good samples of the general readers of this paper— general readers may also read this paper as incremental. We highly encourage authors to take another cycle of edits to better distinguish their work from others before future submissions. 

Decision: Reject