Don't stack layers in graph neural networks, wire them randomly
Authors: Diego Valsesia
Giulia Fracastoro
Enrico Magli
Venue:  (2021)
Keywords: Graph neural networks
random architectures

Abstract: Graph neural networks have become a staple in problems addressing learning and analysis of data defined over graphs. However, several results suggest an inherent difficulty in extracting better performance by increasing the number of layers. Besides the classic vanishing gradient issues, recent works attribute this to a phenomenon peculiar to the extraction of node features in graph-based tasks, i.e., the need to consider multiple neighborhood sizes at the same time and adaptively tune them. In this paper, we investigate the recently proposed randomly wired architectures in the context of graph neural networks. Instead of building deeper networks by stacking many layers, we prove that employing a randomly-wired architecture can be a more effective way to increase the capacity of the network and obtain richer representations. We show that such architectures behave like an ensemble of paths, which are able to merge contributions from receptive fields of varied size. Moreover, these receptive fields can also be modulated to be wider or narrower through the trainable weights over the paths. We also provide extensive experimental evidence of the superior performance of randomly wired architectures over three tasks and five graph convolution definitions, using a recent benchmarking framework that addresses the reliability of previous testing methodologies.

Under review as a conference paper at ICLR 2021
DON'T STACK LAYERS IN GRAPH NEURAL NETWORKS, WIRE THEM RANDOMLY
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have become a staple in problems addressing learning and analysis of data defined over graphs. However, several results suggest an inherent difficulty in extracting better performance by increasing the number of layers. Besides the classic vanishing gradient issues, recent works attribute this to a phenomenon peculiar to the extraction of node features in graph-based tasks, i.e., the need to consider multiple neighborhood sizes at the same time and adaptively tune them. In this paper, we investigate the recently proposed randomly wired architectures in the context of graph neural networks. Instead of building deeper networks by stacking many layers, we prove that employing a randomly-wired effective way increase the capacity of the network
architecture can be and obtain richer representations. We show that such architectures behave like an ensemble of paths, which are able to merge contributions from receptive fields of varied size, Moreover, these receptive fields can also be modulated to be wider or narrower through the trainable weights over the paths. We also provide extensive experimental evidence of the superior performance of randomly wired architectures over three tasks and five graph convolution definitions, using a recent benchmarking framework that addresses the reliability of previous testing methodologies.
INTRODUCTION
Data defined over the nodes of graphs are ubiquitous. Social network profiles (Hamilton et al. 2017 molecular interactions (Duvenaud et al. 2013), citation networks (Sen et al.] 2008). 3D point clouds (Simonovsky & Komodakis] [017] are just examples of a wide variety of data types where describing the domain as a graph allows to encode constraints and patterns among the data points. Exploiting the graph structure is crucial in order to extract powerful representations of the data. However, this not a trivial task and only recently graph neural networks (GNNs) have started showing promising approaches to the problem. GNNs (Wu et al. (020) extend the deep learning toolbox to deal with the irregularity of the graph domain. Much of the work has been focused on defining a graph convolution operation (Bronstein et al.) 2017). i.e., a layer that well-defined over the graph domain but also retains some of the key properties of convolution such as weight reuse and locality. A wide variety of such graph convolution operators has been defined over the years, mostly based on neighborhood aggregation schemes where the features of a node are transformed by processing the features of its neighbors. Such schemes have been shown to be as powerful as the Weisfeiler-Lehmal graph isomorphism test (Weisfeiler & Lehman 1968 Xu al. 2019). enabling them simultaneuosly learn data features and graph topology.
However, contrary to classic literature on CNNs, few works (Li et al. 2019a Dehmamy et al. 2019 Xu et al. 2018: Dwivedi et al, 2020) addressed GNNs architectures and their role in extracting powerful representations. Several works, starting with the early GCN (Kipf & Welling 2017), 7), noticed an inability to build deep GNNs, often resulting in worse performance than that of methods that disregard the graph domain, when trying to build anything but very shallow networks. This calls for exploring whether advances on CNN architectures can be translated to the GNN space, while understanding the potentially different needs of graph representation learning.
Li et al. (2019)) suggest that GCNs suffer from oversmoothing as several layers are stacked, resulting in the extraction of mostly low-frequee wwwfrequency features. This is related to the lack of self-loop information in this specific graph convolution. It is suggested that ResNet-like like architectures mitigate the problem as the skip connections supply high frequency contributions. Xu et al. (2018) point out that the
size of the receptive field of node, i.e., which nodes contribute to the features of the node under

---

Under review as a conference paper at ICLR 2021
Figure I: Random architectures aggregate ensembles of paths. This creates a variety of receptive fields (effective neighborhood sizes on the domain graph) that are combined to compute the output. Figure shows the domain graph where nodes are colored (red means high weight, blue low weight) according the receptive field weighted by the path distribution of domain node. The receptive field is shown at all the architecture nodes directly contributing to the output. Histograms represent the distribution of path lengths from source to architecture node.
consideration, plays a crucial role, but it can vary widely depending on the graph and too large receptive fields may actually harm performance. They conclude that for graph-based problems would be optimal to learn how to adaptively merge contributions from receptive fields of multiple size. For this reason they propose an architecture where each layer has skip connection to the output so that contributions at multiple depths (hence sizes of receptive fields) can be merged. Nonetheless, the problem of finding methods for effectively increasing the capacity of graph neural networks is still standing, since stacking many layers has been proven to provide limited improvements (Li et al. 2019b Oono Suzuki 2019
Alon Yahay 2020, NT & Maehara 2019).
In this paper, we argue that the recently proposed randomly wired architectures (Xie et al. 2019) are ideal for GNNs. In randomly wired architecture, "layers" are arranged according to a random directed acyclic graph and data are propagated through the paths towards the output. Such architecture ideal for GNNs because realizes the intuition offXu et al. (2118) of being able of merging receptive fields of varied size. Indeed, the randomly wired network can be seen their jumping network approach where layer outputs can not only jump to the network output but other layers as well, continuously merging receptive fields. Hence, randomly wired architectures provide a way of effectively scaling up GNNs, mitigating the depth problem and creating richer representations. Fig. shows graphical representation of this concept by highlighting the six layers directly contributing to the output, having different receptive fields induced by the distribution of paths from the input.
extreme generalization of
Our novel contributions can be summarized as follows: i) we are the first to analyze randomly wired architectures and show that they are generalizations of ResNets when looked at ensembles of paths (Veit et al.) 2016); ii) we show that path ensembling allows to merge receptive fields of varied size and that it can do so adaptively, i.e., trainable weights on the architecture edges can tune the desired size of the receptive fields to be merged to achieve an optimal configuration for the problem; iii) we introduce improvements to the basic design of randomly wired architectures by optionally embedding path that sequentially goes through all layers in order promote larger receptive fields when needed, and by presenting MonteCarlo DropPath, which decorrelates path contributions by randomly dropping architecture edges; iv) we provide extensive experimental evidence, using a recently introduced benchmarking framework (Dwivedi et al., 2020) to ensure significance and reproducibility, that randomly wired architectures consistently outperform ResNets, often by large margins, for five of the most popular graph convolution definitions on three different tasks.
2

---

Under review as a conference paper at ICLR 2021
2
BACKGROUND
2.1 GRAPH NEURAL NETWORKS
major shortcoming of CNNs that they are unable to process data defined on irregular domains. In particular, one case that is drawing attention is when the data structure can be described by graph and the data are defined as vectors on the graph nodes. This setting can found in many applications, including 3D point clouds (Wang et al. 2019 Valsesia al. 2019), computational biology (Alipanahi ct al. 2015 2015 Duvenaud et al. 2015), and social networks (Kipf & Welling 2017). However, extending CNNs from data with a regular structure, such as images and video, graph-structured data is not straightforward if one wants to preserve useful properties such as locality and weight reuse.
GNNs redefine the convolution operation so that the new layer definition can be used on domains described by graphs. The most widely adopted graph convolutions in the literature rely on message passing. where weighted aggregation of the feature vectors in neighborhood is computed. The GCN (Kipf & Welling, 2017) is arguably the simplest definition, applying the same linear transformation all the node features, followed by neighborhood aggregation and non-linear activation:
(1+1) =o
Σ Wh JEN.
[
Variants of this definition have been developed, e.g., GraphSage (Hamilton 2017) concatenates the feature vector of node i to the feature vectors of its neighbors, so that sell-inlormation can also be exploited: GIN (Xu al. 2019) uses a multilayer perceptron instead of a linear transform, replaces average with sum to ensure injectivity and proposes different way of computing the output by using all the feature vectors produced by the intermediate layers. These definitions are all isotropic because they treat every edge in the same way. It has been observed that better representation capacity can be achieved using anistropic definitions, where every edge can have a different transformation, at the cost of increased computational complexity. The Gated GCN (Bresson & Laurent (017) and GAT (Veličković et al. 2017) definitions fall in this category.
2.2 RANDOMLY WIRED ARCHITECTURES
In recent work, Xie et al. (2019) explore whether it possible to avoid handcrafted design of neural network architectures and, at the same time, avoid expensive neural architecture search methods (Elsken et al. 2019), by designing random architecture generators. They show that "layers" perform- ing convolution, normalization and non-linear activation can be connected in a random architecture graph. Strong performance is observed on the traditional image classification task by outperforming state-of-the-arc architectures. The authors conjecture that random architectures generalize ResNets and similar constructions, but the underlying principles of their excellent performance are unclear, well whether the performance translates to tasks other than image recognition to operations other than convolution on grids.
RANDOMLY WIRED GNNS
In this section, we first introduce randomly wired architectures and the notation we are going to use. We then analyze their behavior when viewed as ensembles of paths.
h0)
A randomly wired architecture consists of a directed acyclic graph (DAG) connecting a source architecture node, which fed with the input data, to sink architecture node. One should not confuse the architecture DAG with the graph representing the GNN domain: to avoid any source of confusion we will use the terms architecture nodes (edges) and domain nodes (edges), respectively. A domain node is node of the graph that is fed input to the GNN. An architecture node is effectively a GNN layer performing the following operations (Fig. _ i) aggregation of the inputs from other architecture nodes via a weighted sum as in (Xie et al. 2019):
h
h(0
olw
nfw,
Σ
RELU
GCONV
BN
( Σ
wig h (
Σ aww,)) i= 1 --1 (I)
JEA:
JEA.
Figure 2: An architecture node is equivalent to a GNN layer.
3

---

Under review as a conference paper at ICLR 2021
being sigmoid function, A, the set of direct predecessors of the architecture node i, and Way a scalar trainable weight; il) a non-linear activation; iii) a graph-convolution operation (without output activation); iv) batch normalization.
The architecture DAG is generated using a random graph generator. In this paper, we will focus on the Erdös-Reny' model where the adjacency matrix of the DAG is strietly upper triangular matrix with entries being realizations of a Bernoulli random variable with probability p. If multiple input architecture nodes are randomly generated, they are all wired a single global input. Multiple output architecture nodes are averaged to obtain a global output. Other random generators may be used, e.g. small-world and scale-free random networks have been studied in (Xie et al. 2019). However, a different generator will display a different behavior concerning the properties we study in Sec. 3.1
3.1 RANDOMLY WIRED ARCHITECTURES BEHAVE LIKE PATH ENSEMBLES
It has already been shown that ResNets behave like ensembles of relatively shallow networks, where one can see the ResNet architecture as a collection of paths of varied lengths (Veit et al. 2016). More specifically, in a ResNet with n layers, where all layers have a skip connection except the first one and the last one, there are exactly 2'--2 paths, whose lengths follow a Binomial distribution (i.e., the number of paths of length I from layer k to the last layer is ("==z")) and the average path length is
4 + Veit al. 2016)). In this section, we show that randomly wired neural network can also be considered as an ensemble of networks with varied depth. However, in this case, the distribution of the path length is different from the one obtained with the ResNet, as shown in the following lemma (proof in the supplementary material).
Lemma 3.1. Let us consider a randomly wired network with L architecture nodes, where the architecture DAG is generated according to a Erdös-Renyi graph generator with probability p. The average number of paths of length 1 from node k to the sink, where k < L, is ([N ( (4T2=1) p'
and the average total number of paths from node l to the sink is E[N = p(1 + p) 1-
We can observe that if p = 1, the randomly wired network converges to the ResNet architecture. This allows think of randomly wired architectures generalizations of ResNets as they enable increased flexibility in the number and distribution of paths instead of enforcing the use of all 24-2
3.2 RECEPTIVE FIELD ANALYSIS
In the case of GNNs, we define the receptive field of domain node as the neighborhood that affects the output features of that node. As discussed in Sec. [ the work in (Xu et al. 2018) highlights that one of the possible causes of the depth problem in GNNs is that the size of the receptive field is not adaptive and may rapidly become excessively large. Inspired by this observation, in this section we analyze the receptive field of randomly wired neural network. We show that the receptive field of the output is combination of the receptive fields of shallower networks, induced by each of the paths. This allows to effectively merge the contributions from receptive fields of varied size. Moreover, we show that the trainable parameters along the path edges modulate the contributions of various path lengths and enable adaptive receptive fields, that can be tuned by the training procedure.
We first introduce a definition of the receptive field of a feedforward graph neural network]]
Definition 3.1. Given feedforward graph neural network with L layers, the receplive field of radius L of a domain node is its L-hop neighborhood.
In a randomly wired architecture, each path induces a corresponding receptive field whose radius depends the length of the path. Then, the receptive field at the output of the network is obtained by combining the receptive fields of all the paths. In order to analyze the contribution of paths of different lengths the receptive field of the network, we introduce the concept of distribution of the receptive field radius of the paths. Notice that if we consider a feedforward network with L layers, the distribution of the receptive field radius is delta centered in L.
The following lemma allows to analyze the distribution of the receptive field radius in randomly wired architecture.
We use the term 'feedforward neural network" to indicate architecture made of simple line graph, without skip connections: this is representation of one path.
4

---

Under review as a conference paper at ICLR 2021
0.14
9.15
Unne grited
0122
Weigtted
-limeeghttd Sequential
0.1
WWightes Sequental Reshet
Properim toeipate
Desibuton
0.3
(Reshatl
0.08
0.04
0.02
20
40
50
100
60
100
Receptive Field Redius
Path length
Figure 3: Distribution of receptive field radius (p 0.4, Wij = 1 for unweighted, wij = 0.5 for weighted).
Figure Path distribution as function of archi- tecture edge probability.
By of the output y of a randomly wired architecture with respect the Lemma 3.2. The derivative input 2o is
dy
Σ dyp 3ro
- PEP
Our Σ Wis
Σ
X
Oye
Ooo
O.o
pEp
PEP (iJ)ESP
1=2
pEp!
where Up is the output of path p. By is the output of path p when consider all the aggregation weights equal to 1, Xp architecture nodes, Pl is the set paths from source sink of length and Ed is the set of edges of the path p.
Aye
dil,, P is the set of all paths from source to sink, is the number of
8xo
Proof. Direct computation.
From Lemma 3.2 we can observe that the contribution of each path to the gradient is weighted by its corresponding architecture edge weights. Thus, we can define the following distribution p of the receptive field radius:
- wiy for 1 2,..., PI
PEP!
PEP! ((J)EE
Dūg where we have assumed that the gradient Tie depends only on the path length, done in (Veit et al. 2016). This is reasonable assumption if all the architecture nodes perform the same operation. The distribution of the receptive field radius therefore influenced by the architecture edge weights. 3
example of how such weights Wi = for all and j. we obtain that the radius distribution is equal to the path length distribution. In order to provide some insight into the role of parameter p in the distribution of the receptive field radius, we focus on this special case and analyze the distribution of the path lengths a randomly wired architecture by introducing the following Lemma (proof in the supplementary material).
modify the radius distribution. If we consider
Lemma 3.3. Let us consider randomly wired network with L architecture nodes, where the architecture DAG is generated according average length of the puths from node k to the sink is B[((k)] x T 1) 2
Erdös-Renyi graph generator with probubility p. The
Therefore, if p and Way = 1 for all and the radius distribution centered in 4 (as in ResNets), instead when p < 1 the mean of the distribution is lower. The This shows that, differently
Binomial distribution
path length distribution for different values is shown in Fig. from feedforward networks, the receptive field of ResNets and randomly wired architectures is combination of receptive fields of varied sizes, where most of the contribution is given by shallow paths, i.e. smaller receptive fields. The parameter p of the randomly wired neural network influences the distribution of the receptive field radius: lower p value skews the distribution towards shallower paths, instcad higher p value skews the distribution towards longer paths.
After having considered the special case where wij = 1 for all and j. now focus on the general case. Since the edge architecture weights are trainable parameters, they can be adapted to optimize the distribution of the receptive field radius. This is of the strongest advantages provided by randomly wired architectures with respect to ResNets. This is particularly relevant in the context of GNNs, where may have non-uniform growth of the receptive field caused by the irregularity
5

---

Under review as a conference paper at ICLR 2021
of the graph structure (Xu et al. 2018). Notice that the randomly wired architecture can be seen as a generalization of the jumping knowledge networks proposed in (Xu et al. 2018), where all the architecture nodes, not only the last one, merge contributions from previous nodes. We also remark that, even if we modify the ResNet architecture by adding trainable weights to each branch of the residual module, we cannot retrieve the behaviour of the randomly wired architecture. In fact, the latter has intrinsically more granularity than a ResNet: the expected number of architecture edge weights of randomly wired network is pfLL+), instead a weighted ResNet has only 2(L - 2) weights. Idcally. we would like to weight each path independently (i.e., directly optimizing the value of Ap in Eq. (3.2). However, this is unfeasible because the number of parameters would become excessively high and the randomly wired architecture provides an effective tradeoff. Given an architecture node, weighting in different way each input edge is important because to each edge corresponds a different length distribution of the paths going through such edge, as shown by the following Lemma (proof in supplementary material).
Lemma 3.4. Let us consider a randomly wired network with n architecture nodes, where the architecture DAG is generated according to a Frdös-Reny) graph generator with probability p. Given an edge {i,j} between the architecture nodes and j where i < j. the average length of the paths from the source to the sink going through that edge is El[ly] x 1 (L (i -))
3.3 SEQUENTIAL. PATH
In the previous sections we have shown that a randomly wired architecture behaves like an ensemble of paths merging contribution from receptive fields of varied size, where most of the contribution is provided by shallow paths. As discussed previously, this provides numerous advantages with respect to feedforward networks and ResNets. However, some graph- based tasks may actually benefit from larger receptive field (Li et al. 2019b).. so is interesting to provide randomly wired architectures with mechanisms to directly promote longer paths. Differently from ResNets. in randomly wired neural network with L. architecture nodes the longest path may be shorter than L, leading to a smaller receptive field. In order to overcome this issue, we propose to modify the generation process of the random architecture by imposing that it should also include the sequential path, i.c., the path traversing all architecture nodes. This design of the architecture skews the initial path length distribution towards longer paths, which has the effect of promoting their usage. Nevertheless, the trainable architecture edge weights will ultimately define the importance of such contribution. Fig. shows an example of how including the sequential path changes the distribution of the receptive field radius.
3.4 MONTECARLO DROPPATH LEGULARIZATION
The randomly wired architecture offers new degrees of freedom to introduce regularization techniques. In particular, one could delete a few architecture edges during training with probability Prrop as a way avoid oo-adptationn of architecture nodes. This reminiscent of DropOut (Srivastava al. 2014) and DropConnect (Wan et al.) (013). although it is carried out at higher level of abstraction, i.e., connections between "layers" instead of neurons. is also reminiscent of techniques used in Neural Architecture Search (Zoph et al. 2018) and the approach used in ImageNet experiments in (Xie et al. 2019), although implementation details are unclear for the latter.
We propose to use MonteCarlo approach where paths are also dropped in testing. Inference is performed multiple times for different realizations of dropped architecture edges and results are averaged. This allows to sample from the full predictive distribution induced by DropPath, in MonteCarlo DropOut (Gal & Ghahramani 2015). It is worth noting that MonteCarlo DropPath decorrelates the contributions of paths in Eq. (3.2) even if they share architecture edges (proof in supplementary material), thus allowing finer control over the modulation of the receptive field radius.
EXPERIMENTAL RESULTS
Experimental evaluation of GNNs is topic that has recently received great attention. The emerging consensus is that benchmarking methods routinely used in past literature are inadequate and lack reproducibility. In particular, Vignac et al. (2020) showed that commonly used citation network datasets like CORA, CITESEER, PUBMED are too simple and skew results towards simpler archi- tectures or even promote ignoring the underlying graph. TU datasets are also recognized to be too small (Errica et al. 2019) and the high variability across splits does not allow for sound comparisons across methods. In order to evaluate the gains offered by randomly wired architectures across wide variety of graph convolutions and tasks, we adopt a recently proposed GNN benchmarking framework (Dwivedi et al. 2020), that has introduced new datasets and allows for reproducible experiments.

---

Under review as a conference paper at ICLR 2021
Table I: ZINC Mean Absolute Error.
Table 2: CLUSTER Accuracy.
1=8
==
=
==
16
L = 32
GCN
0,465#0.012
0,445=0.022
0.426#0.011
GCN
48.71 13.04
48.57
55.62
RAN-GON
0.4477.6.
0.398
0.385
RAN-GCN
58.61
13.15
62.24
2104
63.32
10099
2.1a
3.70
8.3r
1.70
2.
GIN
0.44420.017
0.461
0.46120.022
20.022
0.633#0.050
GIN
49.93
49.04
2.55
44.96
3.55
RAN-GIN
0.398
004
0,426
02000
10.15
RAN-GIN
54.38
56.58
6
56.19222.21
1.0z
3.0p
2.0c
GatedGCN
0.339
28.4100014
0.277#0.025
GatedGCN
63.10
70.09
1.89
71.94 1.51
RAN-GatedGCN
0.310
0.218 4.7e
10.017
0.215
RAN-GatedGCN
63.
2..455
72.13
74.32
GraphSage
0.363#0.005
0.355=0.00
0.351 000
GraphSage 66.2220.73
71.50
1.03
70.23=1.77
RAN-GraphSage
0.368,0000
0.340
0.340
00,000
0.333
2:0.05
RAN-GraphSage 67.21
71.90
2000
72.56
6,0g
GAT
0.416
0.384
0.357 011
GAT
54.35 60.68
55.1144.31
RAN-GAT
0.4 0.90
0.392577012
0.368
RAN-GAT
63.38217.
69.68 2.1c
1.58
70.93
55
We focus testing five of the most commonly used graph convolution definitions: GCN (Kipf) Welling, 2017), GIN (Xu et al. 2019 Pl Gated GCN (Bresson & Laurent 2017). GraphSage (Hamilton et al. 2017). 7, GAT (Velicković et al. 2017). We select three representative tasks introduced by (Dwivedi et al. ) graph regression on the ZINC dataset, node classification on the CLUSTER dataset, and graph classification with superpixels on CIFARIO. To ensure reproducibility, we use exactly the same setting as (Dwivedi et al. 2020). We are interested in the performance differences between the baseline ResNet architecture, i.e., feedforward architecture with skip connections after every layer, and the randomly wired architecture. It was already shown in (Dwivedi et al. 20200) that ResNet GNNs significantly outperform architectures without residual connections. We remark that other works proposed methods to build deeper GNN (Rong et al. 2019: Zhao & Akoglu 2019 Gong al. 2020), but such techniques can be regarded as complementary to our work. We do not attempt to optimize specific method, nor we are interested in comparing one graph convolution to another. fair comparison is ensured by running both methods with the same number of trainable parameters and with the same hyperparameters. In particular, the learning rate of both methods is adaptively decayed between 10-3 3 and 10 by halving according to the value of the validation loss, with a patience of 5 epochs. Stopping criterion is validation loss not improving for 5 epochs after reaching the minimum learning rate. We average the results of all experiments over 4 runs with different weight initializations and different random architecture graphs, drawn with p 0.6. We also evaluate results for multiple values of the total number of layers (architecture nodes) L, in order to show that randomly wired GNNs allow more effective increase in capacity. The random architectures use sequential paths (Sec. (.2) in the ZINC experiment, sequential paths and DropPath in the CLUSTER experiment, and only DropPath in CIFARI The reason for these choices is that the regression task in ZINC and the node classification task in CLUSTER are particularly sensitive to the size of the receptive field, as observed by analyzing the experimental receptive radius (supplementary material). On the other hand, CIFAR10 is bottlenecked by overfitting, and it greatly henefits from the regularizing effect of DropPath, as also observed on CLUSTER. The number of DropPath iterations in testing was fixed to 16.
4.1 RANDOM GNN BENCHMARKING
The results presented in this section show that randomly wired GNNs have compelling performance in many regards. First of all, they typically provide higher accuracy or lower error than their ResNet counterparts for the same number of parameters. Moreover, they are more effective at increasing capacity than stacking layers: while they are essentially equivalent ResNets for very short networks, they enable larger gains when additional layers are introduced.
Table [ shows the results obtained on the ZINC dataset. The metric is mean absolute error (MAF), so lower is better. The superscript reports the standard deviation among runs and the subscript reports the level of significance by measuring how many baseline standard deviations the average value of the
GGNN and AN-GIN compute the output as (Xu et al. 2018 using the contributions of all architecture
nodes.
We do not use DropPath for RAN-GIN on any experiment as we observed unstable behavior.
7

---

Under review as a conference paper at ICLR 2021
Table 3: CIFARIO Accuracy.
L=8
=
== 32
GCN
20.2
54.7422.52
54.76*0.53
Table Median relative gain over 4.
RAN-GCN
57.81
10.08
57.29
0.44
58.49 7,00
1.9g
==8
16
L 32
GIN
48.59*1.00
47.14
1.75
36.90
ResNet
+7.88%
+17.06%
+ 17.99%
RAN-GIN
22.522.30
52.07
42.73
1.27
7,98
ZINC
Random
+14.22%
+21.81%
+24.36%
GatedGCN
68.27
69.16++0.0
69.46
+0.47
ResNet
+17.90%
+ +15.80%
+ 14.26%
RAN-GatedGCN
68.866.76
72.00
73.50
#8.08 b.6a
CLUSTER
4.30
Random
+20.75%
+30.07%
+32.41 %
GraphSage
65.58 40.46
66.
66.12#0.11
65.33
ResNet
-0.81%
-0.11%
1.22%
RAN-GraphSage
65.31
0.0e
28.38
66.
66.10..24
11111
67.68
0.337 6.9la
CIFARIO
Random
+1.31%
+3.58%
+4.10%
GAT
64.43
30.33
63.61
+0.66
64.62
RAN-GAT
66.185.44 5.3a
20000
66.27
66.01
#0.38
2.10
Table 5: Comparison against SIGN and PPNP GCN (no residuals)
Num. param.
GCN
RAN-GCN
PPNP
SIGN
ZINC
1 180k
0.526
0.465
0.447
0.746
0.566
CLUSTER
180k
22.23
48.71
58.61
33.00
48.35
CIFAR10
180k
51.16
54.85
57.81
36.37
52.49
ZINC
360k
0.537
0.445
0.398
0.750
0.555
CLUSTER
360k
19.26
48.57
62.24
37.37
48.51
CIFAR10
360k
49.86
54.74
57.29
36.68
53.55
ZINC
720k
0.649
0.426
0.385
0.804
0.574
CLUSTER
720k
20.90
55.62
63.32
28.77
49.14
CIFARIO
720k
47.47
54.76
58.49
38.54
53.72
random architecture deviates from the average value of the baseline. Results are in bold they are at least T significant. The results show that the randomly wired GNNs typically outperform the ResNet baseline by significant margins. Table@
the node classification accuracy on the CLUSTER dataset. It can be seen that the random architectures achieve very significant improvements on this dataset, especially for RAN-GCN, RAN-GIN and RAN-GAT. Table 3 the classification accuracy CI when the images converted to graphs using superpixels. Also in this case, the randomly wired architecture greatly outperforms the baseline, in some cases achieving gains higher than 5a. Finally, Table shows the relative performance gain (relative improvement in accuracy or mean absolute error), averaged over all the graph convolution definitions, with respect short 4-layer network, where random wiring and ResNets almost equivalent (results in supplementary material). We can notice that deeper ResNets always provide lower gains with respect their shallow counterpart than the randomly wired GNNs. Moreover, we observe monotonically increasing gains for random GNNs while deeper ResNets are either unable to significantly extract more performance beyond
16 or even provide worse results than the L network. This supports our claim that the randomly wired architecture is superior way increase GNN capacity,
Finally, we compare the proposed method against two other frameworks for GNNs, namely PPNP Klicpera et al. (2018) and SIGN Rossi et al. (2020), which propose different approaches for solving the oversmoothing problem. Due to the significant differences the approaches, providing a fair comparison is challenging. We decided to equalize the number of parameters across the methods, since notions as number of layers or features cannot translated all the frameworks (180k,360k,72)) 720k parameters correspond to the L = 8, 16, 32 settings in the previous tables). Table ?? shows the obtained results. We can observe that both PPNP on node classification and SIGN on all tasks outperform the standard GCN architecture without skip connections, but they cannot outperform GCN with residual connections and the randomly wired GCN.
8

---

Under review as a conference paper at ICLR 2021
Table 6: Edge probability, L 16, RAN-GCN.
p 0.2
p 0.4
0.6
p 0.8
ZINC
0.440=#0.025
0.427#00025
0.409=0.010
0.415#20012
CLUSTER 19.87=1.64
60.71#2.22
62.75*2232
62.93=2.75
CIFAR10
56.53=0.61
56.21 +0.48
57.44#0.16
56.06=045
Table 7: DropPath on CIFARIO, RAN-
Table 8:
DropPath CIFARIO, RAN-
GatedGCN. No sequential path embedding.
GatedGCN. No sequential path embedding.
= 8
=
16 == 32
Phop
None 08.0720.90
70.78 10.38
72.75 10033
0.005
0.01
0.02
0.03
DropPath 68.86-1166 72.00
70.50
70.78
70.90=0.46
72.00
71.55=0.83
71.09=1.77
Table 9: Sequential path embedding on CLUSTER, RAN-GatedGCN. No DropPath.
=
= 16
L = 32
Fully random
56.93
66.50
70.38
Random+SSquential 63.30
68.89
+1.87
71.65
4.2 ABLATION STUDY
4.2.1 EDGE PROBABILITY
We first investigate the impact of the probability of drawing an edge in the random architecture. Table shows the results for basic random architecture without DropPath nor embedded sequential path. It appears that an optimal value of exists that maximizes performance. This could be explained by a tradeoff between size of receptive field and the ability to modulate it.
4.2.2 DROPPATH
The impact of DropPath on CIFARIO is shown in Table 7
We found the improvement due to DropPath be increasingly significant for higher number of architecture nodes, expected due the increased number of edges. The value of the drop probability Purop = 0.01 was not extensively cross-validated. However, Table88shows that higher drop rates lowered performance.
4.2.3 EMBEDDED SEQUENTIAL. PATH
The impact embedding a sequential path as explained in Sec. 3.2 is shown in Table 9 It can be observed that its effect of promoting receptive fields with larger radius is useful this task. We remark that, while we do not report results due to space constraints, this is not always the case and some tasks (e.g., CIFAR1O) do not benefit from promoting larger receptive fields.
CONCLUSIONS
We showed how randomly wired architectures can boost the performance of GNNs by merging receptive fields of multiple size. Consistent and statistically sigmificant improvements over wide range of tasks and graph convolutions suggest considering them the go-to choice for new models.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Babak Alipanahi, Andrew Delong, Matthew T Weirauch, and Brendan Frey. Predicting the sequence specificities of dna-and ma-binding proteins by deep learning. Nature biotechnology. 33 (8):831-838 2015.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205, 2020.
Xavier Bresson and Thomas Laurent. Residual gated
graph convnets.
arXiv preprint
arXiv:1711.07553, 2017.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 14(4):18-42, 2017.
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. In Advances in Neural Information Processing Systems, pp. 15387-15397, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molccular fingerprints. In Advances neural information processing systems, pp. 2224 2232, 2015.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks (vl). arXiv preprint arXiv:2003.00998> 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55):1-21, 2019.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:1912.0988: 2019.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. arXiv preprint arXiv: 550. 142, 2015.
Shumwang Gong, Mehdi Bahri, Michael M Bronstein, and Stefanos Zafeiriou. Geometrically principled connections in graph neural networks. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11415-11424 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018
Guohao Li, Matthias Müller, Guocheng Qian, Itzel C Delgadillo, Abdulellah Abualshour, Ali Thabet, and Bernard Ghanem. Deepgens: Making GCNs go as deep as CNNs. arXiv preprint 2019a.
Guohao Li. Matthias Muller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs go as deep as CNNs? In Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276. 2019b.
Hoang NT and Takanori Maehara, Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 095550 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv: 1905. 2019.
10

---

Under review as a conference paper at ICLR 2021
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2019.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. //198, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9) 93, 2008.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters convolutional neural networks on graphs. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 29-38, 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15()):1999-1958 2014.
Diego Valsesia, Giulia Fracastoro, and Enrico Magli. Learning Localized Generative Models for 3D Point Clouds via Graph Convolution. In International Conference on Learning Representations (ICLR) 2019, 2019.
Andreas Veit, Michael J Wilber, and Serge Belongie. Residual networks behave like ensembles of relatively shallow networks. In Advances in neural information processing systems, pp. 550-558, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2017.
Clément Vignac, Guillermo Ortiz-Jiménez, and Pascal Frossard. On the choice of graph neural network architectures. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8489-8888888 8493. IEEE, 2020.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International conference on machine learning, pp. 1058-1066. 2013.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. ACM Transactions on Graphics (TOG), 38(5): 146, 2019.
B. Weisfeiler and A Lehman. A reduction of graph canonical form and an algebra arising during this reduction. Nauchno-Technicheskay Informatsia, 22-): 1968.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1284-1293, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv: 1909.1101110000 1ttp:/999..22...... 2019.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018
11


Reviews:
[{"review_id": "vf_YylV5YO2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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\nThe paper proposes a new method for building graph convolutional neural networks. It shows, that during the building of the network, instead of stacking many layers and adding the residual connection between them, one could employ a randomly-wired architecture, that can be a more effective way to increase the capacity of the network and thus it could obtain richer representations. The proposed method is an interesting direction in the field of graph convolutional neural networks. The new method could be seen asa generalization of the residual networks and the jumping knowledge networks.\n\n=============================================================================\n\nPros:\n\n1. The paper proposes a novel, randomly-wired architecture for building the graph convolutional neural networks. Moreover authors analyze proposed randomly-wired architectures and show that they are generalizations of ResNets.\n\n2. The authors provide the theorethical analysis of the radius of te receptive field of GCN. They show that by using randomly-wired network, together with trainable weights on the architecture edges and sequential path, the network could tune the desired size of the receptive fields to be merged to achieve an optimal configuration for the problem.\n\n3. The authors propose the MonteCarlo DropPath regularization - a novel regularization method for randomly-wired architectures, that is related to dropout, however is carried out at a higher level of abstraction.\n\n4. The authors provide a comprehensive experimental results of the proposed method - they compare various GCN architectures, created on traditional and randomly-wired way, on three representative tasks - graph regression, graph classification and node classification. Moreover they show, that randomly-wired GCNs gets better results than ResNet GCNs on almost all tested cases. Moreover the authors shows that deeper randomly-wired GCNs always provide bigger gains with respect to their shallow counterpart than ResNet GCNs.\n\n=============================================================================\n\nCons:\n\n1. Figure 1 is not clear to me. I am not sure what the colored point cloud is about. The authors should consider rewriting a description of this figure.\n\n2. In the final version of the paper, the ablation study should be reported on all datasets (however the authors remark that, they do not report results on this version of paper due to space constraints).\n\n3. I would like to see the more extensive analysis of DropPath, e.g what are the scores for different levels of the drop probability.\n\n=============================================================================\n\nQuestions during rebuttal period:\n\n1. Why the authors use different types of GCNs during the ablation study?\n\n=============================================================================\n\n=============================================================================\n\nReasons for score: \n \nOverall, I vote for accepting this paper. The idea proposed by the authors is novel and confirmed theoretically and experimentally.\nMy major concern is about ablation study and the clarity of one figure. Hopefully the authors can address my concern in the rebuttal period. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "lepHU9hYuZb", "reviewer": "AnonReviewer3", "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": "Summary: \nThe authors proposed to randomly wire the GNN layers. They claim it can not only resolve over-smoothing problem but also enable the varied size of receptive fields.\n\nPros:\n1.\tReally great looking graphics.\n\nCons: \n1.\tThe motivation of why should we use Erdos-Renyi (ER) graph to generate DAG for the random rewiring is not clear.\n2.\tHow can we learn from the results of the DAG statistics (such as averaged path length) is unclear. I don’t understand how this can help us design or improve the proposed architecture.\n3.\tThe experimental results seem inconsistent to [1], where the authors claim to follow their experiment setting.\n\nDetailed comments:\n\nThe main weakness of this paper is its motivation. I do not see any theoretical reasoning that we should use ER graph instead of the other choice of random graph generator. The authors mention that small world and scale-free networks have been studied and use in [2], but I don’t see any detailed comparison why the ER graph is a more preferred choice. Even in the experiment section, I do not aware of any comparison which is unsatisfactory. \n\nThe other weakness is that the “theoretical analysis” mentioned in this paper neither leads to any reasoning in model design nor guarantee in performance. What can we learn from knowing Lemma 3.1 and 3.3? How do they explain why using ER graph for random wiring is favorable? I do not even see it helps on choosing the hyperparameter $p$.\n\nThe final but most questionable part is the experiment section. The authors claim that they adopt a recently proposed GNN benchmarking framework [1]. However, the reported results are significantly different and much worse than those reported in [1]. For example, GCN ($L=16$) has 68.5% of accuracy in the experiment on CLUSTER dataset in [1] (Table 2, Node classification). In contrast, the authors report GCN accuracy for only 48.57%. Of course, the hyperparameters might be chosen differently from [1], but then the question would be why not optimize it according to [1]? Also, why not report the performance of more shallow $L$ (say $L=2$ or $4$) which is a more common choice? All these inconsistency makes me hard to believe the proposed methodology   would work.\n\nReference:\n\n[1] “Benchmarking Graph Neural Networks,” Dwivedi et al., arXiv preprint arXiv:2003.00982, 2020.\n\n[2] “Exploring randomly wired neural networks for image recognition.,” Xie et al., In Proceedings of the IEEE International Conference on Computer Vision, pp. 1284–1293, 2019.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9q8J98wcmro", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper utilizes Randomly Wired architectures to boost deep GNNs. Theoretical analyses verify that randomly wired architectures behave like path ensemble and it enables adaptive receptive field. Experimental results on three non-popular datasets demonstrate the strength of the proposed model. Overall, the idea is interesting. Yet this paper can be made better through the following aspects:\n\n1. This paper contains confusing equations and notations. For example, in Eq 1., why w_ij equals \\sigma(w_ij). What's the meaning of domain nodes and how do we connect the architecture nodes and the domain nodes. What's the definition of \\mathcal{A}?\n \n2. This paper only proposes the recursion formula but omits some basic definitions, i.e. the definition of h^{(i)}. Where does the recursion start?  Is there an initialized h^{(0)}?\n\n3. The algorithm framework is not clearly depicted. How do R-GCNs accomplish the graph propagation process?\n \n4. Insufficient experimental comparisons. How do R-GCNs and GCNs perform when L=2. How do R-GCNs perform on standard node classification datasets, such as Cora, Citeseer, and Reddit, since deep GCNs fail particularly on node  classificaiton. How do R-GCNs perform against other deep frameworks such as APPNP and JKNet, both of which resort to more sophisticated skip connections than ResGCN.\n\n#############post-rebuttal############\n\nI have carefully checked all other reviewers' comments, the authors' response, and the revised version. Thank the authors for their detailed feedback. They have addressed my concerns on the unclear presentation. However, joining the comments from other reviewers (particularly R3), I still think there are two major issues that prevent me from further increasing my score.\n\nQ1. It is still unclear why the proposed model can tackle the over-smoothing issue in existing deep GCNs.\n\nThis paper has theoretically revealed the benefit of adaptive ensemble paths towards better trainability. Given the claim in Introduction, it is still unclear why such benefit can be used to relieve over-smoothing, particularly due to the missing analysis of the output dynamics. As already pointed out by R3, [3] has set up a nice notion of framework on explaining how over-smoothing happens and why deep GCN fails. It is a pity that this paper has not put their analyses into this framework and discussed the relation with the over-smoothing issue. Actually, a more in-depth discussion of over-smoothing on general GCNs (including ResGCN, APPNP) has also provided in an arXiv preprint paper [4]. It does show that the residual networks are capable of slowing down the convergence speed to the subspace and thus alleviating over-smoothing. Since the idea of random wiring is initially proposed in CNNs, the contribution of this paper that we expect is to answer how this idea can be utilized to solve the specific weakness in the graph domain.\n\nQ2. The experimental evaluations are still unconvincing.\n\nIt is thankful that the authors have additionally provided the performance of SIGN and APPNP in the revised version. Yet, the reported accuracies of APPNP seem weird and much worse than other baselines. I do not agree with the authors' response that APPNP is not intended to address the over-smoothing problem. As experimentally shown in [5] and theoretically analyzed in [4], keeping the connection between each middle layer and the input layer is able to prevent the output from converging to the subspace caused by over-smoothing, and thereby deliver desired performance with the increase of depth. As this paper has conducted experiments on a newly-public benchmark under inconsistent experimental setting up (raised by R3), it is hard to justify the significance of the proposed idea compared with previous methods, specifically given the irrational observations on APPNP.\n\nHence, I still believe this paper is below the acceptance line. \n\n[3] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020. \n[4] Tackling Over-Smoothing for General Graph Convolutional Networks, arXiv 2020. [5] Simple and Deep Graph Convolutional Networks, NIPS 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5wfNmF-sWYm", "reviewer": "AnonReviewer1", "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": "Summary:\n\nThis paper extends the technique of randomly wired neural nets from [1] to Graph Neural Networks and show that they perform better than tradtional GNN architectures. They demonstrate the improved capacity of this architecture via a number of experiments on the benchmark in [2] and ablation studies.\n\nReason for score:\n\nPros:\n\n  - The paper evaluates the technique on a widely accepted benchmark for Graph Neural Networks.\n  - Diminishing model performance in GNNs with increased number of layers is an important problem and it looks like randomly wired GNNs provide monotonically increasing performance for up to  L = 32\n  - The models generated using random wiring outperform the baseline model across a large number of settings such as the graph convolution operator used and the number of layers\n  - Augmenting the randomly wired networks with a sequential path is interesting.\n  - Ablation experiments are extensive and convincing.\n  \nCons:\n \n  - The novelty is only incremental, building on the core idea from [1], but the results are strong so this is not a big issue.\n  - Why didn't the paper test on other tasks from the benchmark in [2] like PATTERN and TSP? A full set of experiments would rule out the possibility that the benchmark tasks were cherry picked.\n  \nOverall:\n\n  Extension of an existing method to GNNs which produces strong results. I vote to accept this paper.\n \nQuestions:\n\n - How many iterations of inference do you'll do for MonteCarlo DropPath during testing?\n \n \nReferences:\n\n[1] Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neuralnetworks for image recognition. In Proceedings of the IEEE International Conference on ComputerVision, pp. 1284–1293, 2019.\n\n[2] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to use randomly wired architectures [1] in the context of GNNs and introduces a method for sampling random architectures based on the Erdős–Rényi model. The authors further include a theoretical analysis and two methodological contributions: sequential path embeddings and DropPath, a regularizer. Results are reported on two graph datasets (ZINC and CLUSTER) and on GNN-based CIFAR10 image classification.

The reviewers agree that the empirical results presented in the paper are compelling. The value of the contribution largely lies in this aspect, namely the empirical analysis of an existing technique (randomly wired architectures) in the context of GNNs, in addition to several smaller empirical methodological contributions. I agree with the reviewers in that the nature of the contribution and the otherwise limited novelty calls for a more extensive and detailed empirical evaluation (ideally incl. e.g. FLOPS, wall-clock time, memory usage) across a wide range of datasets and careful ablation studies, and I encourage the authors to improve on this aspect in a future version of the paper. The theoretical analysis is interesting, but, as pointed out by the reviewers both during the reviews and the later discussion period, does not add sufficient value to the main empirical contribution of the paper to push the paper beyond the acceptance threshold and does not satisfactorily address the question of how the method addresses the oversmoothing problem in GNNs.

[1] Xie et al., Exploring randomly wired neural networks for image recognition (ICCV 2019)

Decision: Reject