Old can be Gold: Better Gradient Flow can Make Vanilla-GCNs Great Again
Authors: AJAY KUMAR JAISWAL
Peihao Wang
Tianlong Chen
Justin F Rousseau
Ying Ding
Zhangyang Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Deep Graph Neural Networks
Gradient Flow
Initialization
Isometric Learning

Abstract: Despite the enormous success of Graph Convolutional Networks (GCNs) in modeling graph-structured data, most of the current GCNs are shallow due to the notoriously challenging problems of over-smoothening and information squashing along with conventional difficulty caused by vanishing gradients and over-fitting. Previous works have been primarily focused on the study of over-smoothening and over-squashing phenomena in training deep GCNs. Surprisingly, in comparison with CNNs/RNNs, very limited attention has been given to understanding how healthy gradient flow can benefit the trainability of deep GCNs. In this paper, firstly, we provide a new perspective of gradient flow to understand the substandard performance of deep GCNs and hypothesize that by facilitating healthy gradient flow, we can significantly improve their trainability, as well as achieve state-of-the-art (SOTA) level performance from vanilla-GCNs. Next, we argue that blindly adopting the Glorot initialization for GCNs is not optimal, and derive a topology-aware isometric initialization scheme for vanilla-GCNs based on the principles of isometry. Additionally, contrary to ad-hoc addition of skip-connections, we propose to use gradient-guided dynamic rewiring of vanilla-GCNs with skip connections. Our dynamic rewiring method uses the gradient flow within each layer during training to introduce on-demand skip-connections adaptively. We provide extensive empirical evidence across multiple datasets that our methods improve gradient flow in deep vanilla-GCNs and significantly boost their performance to comfortably compete and outperform many fancy state-of-the-art methods. Codes are available at:  https://github.com/VITA-Group/GradientGCN.

Old can be Gold: Better Gradient Flow can Make Vanilla-GCNs Great Again
Ajay Jaiswal", Peihao Wang", Tianlong Chen, Justin F. Rousseau, Ying Ding, Zhangyang Wang
University of Texas at Austin
fajayjaiswal, peihaowang, tianlong chen, atlaswanng/uteeas.. edu Kjustin.ruusset ying. danstin utw.us.exee...e
Abstract
Despite the enormous success of Graph Convolutional Networks (GCNs) in mod- eling graph-structured data, most of the current GCNs shallow due the notoriously challenging problems of over-smoothening and information squashing along with conventional difficulty caused by vanishing gradients and over-fitting Previous works have been primarily focused on the study of over-smoothening and over-squashing phenomena in training deep GCNs. Surprisingly, in comparison with CNNs/RNNs, very limited attention has been given to understanding how healthy gradient flow can benefit the trainability of deep GCNs. this paper, firstly, we provide a new perspective of gradient flow to understand the substandard per- formance of deep GCNs and hypothesize that by facilitating healthy gradient flow, we can significantly improve their trainability, as well as achieve state-of-the-e (SOTA) level performance from vanilla-GCN [. Next, we argue that blindly adopting the Glorot initialization for GCNs is not optimal, and derive topology- aware isometric initialization scheme for vanilla- GCNs based on the principles of isometry. Additionally, contrary to ad-hoc addition of skip-connections, we propose to use gradient-guide
dynamic rewiring vanilla-GCNs with skip connections. Our dynamic rewiring method uses the gradient flow within each layer during training to introduce on-der on-demand skip-commi cip-connections adaptively. We provide extensive empirical evidence across multiple datasets that our methods improve gradient flow in deep vanilla- Muilla-GCNs and significantly boost their performance to comfortably compete and outperform many fancy state-of ofettheartt methods. Codes are available at: hhtps: thub. com/ VVITA-CropO//// CradientGCN)
Introduction
Graphs are omnipresent and Graphs convolutional networks (GCNs) and their variants 4
6,77 8 9 10] are a powerful family of neural networks which can learn from graph-structured data. GCNs have been enormously successful numerous real-world applications such as recommenda-
tion systems [2), social and academic networks [3
5 14), modeling proteins for drug
discovery [5 16 12), computer vision 17 [8], etc. Despite their popularity, training deep GCNs
notoriously hard and many classical GCNs II 3 [9] achieve their best performance with shallow
depth and completely bilk trainability with increasing stacks of layers and non-lineanee non-linearity 22 21).
Previous works have focused on studying the roadblocks of training deep GCNs from the perspective of over- wee-shoothnning [20 21 and information bottleneck [22] and many approaches broadly catego-
rized as architectural 23 24 20 25
and regularization & normalization [26 27 28 29 tweaks has
been proposed for mitigation. In recent work, (30) theoretically validated that the deeper GCN model is at least as expressive as the shallow GCN model, as long as deeper GCNs are trained properly.
Equal Contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Furthermore, B1 studied the training difficulty of GCNs from the perspective of graph signal energy loss, and proposed modifying the GCN operator, from the energy perspective but it failed to recover the full potential of vanilla-GCNs. Surprisingly, unlike traditional neural networks (CNNs and RNNs), limited effort has been given to understand hurdles in the trainability of deep GCNs from the signal propagation perspective, i.e. gradient flow. In this paper, we comprehensively show that deep GCNs suffer from poor gradient flow (error signals) under back- packkpropagation across multiple datasets and architectures, which significantly hurt their trainability and lead to substandard performance. Further, we are motivated to explore an orthogonal direction: Can we make vanilla-GCn [T] go deeper and comparable/better than SOTA, by improvising healthy gradient flow during training?
In this work, we firstly look into the effect of initialization (surprisingly overlooked) in GCNs, and find that blindly adopting the Glorot initialization [32 from CNNs has critical impacts on the gradient flow of GCN training, especially for deep GCNs. When the initial weights are not chosen appropriately. the propagation of the input signal into the layers of random weights can result in poor error signals under back- prop-proongttion 33 Inspired from the signal propagation perspective, we leverage the principle of isometry 334 35 to derive a theoretical initialization scheme for vanilla-GCNs, by incorporating the
graph topological information which yields a remarkably easy-to-compute form.
Skip-connections have been very resourceful to train deep convolutional networks 36 37 by
38 20 have identified their benefits for deep GCNs. Although their benefits are known, most of the existing works attempt to add skip- connections in an ad-hoc and non-optinal fashion in deep GCNs which creates additional overhead of storing multiple activations during training along with substandard performance. Secondly, we study layerwise gradient flow during the training of deep vanilla-GCN GCllls and identify that there exist some layers which receive almost zero error signal (i.e. gradients) during backpropagation and lose trainability and expressiveness. We use computationally efficient Gradient Flow (p-norm of gradients within a layer) metric to dynamically identify such layers during training and propose principled way of injecting skip-connections on-demand to facilitate healthy gradient flow deep GCNs.
improving the gradient flow, and recently some works [23 24
Our main contributions can be summarized as:
Deep GCNs suffer from poor gradient flow during training. We rigorously investigate the gradient flow during the training of GCNs and observe that GCNs suffer from poor gradient flow which worsens with the increase in depth. We hypothesize that by improving the gradient flow in deep vanilla-GCNs, along with effectively improving their trainability, we can achieve SOTA-level performance from vanilla-GCNs O.
Topology-Aware Isometric Initialization of GCNs. Unlike blind adoption of Glorot initialization 32 for GCNs, we derive a theoretical initialization scheme for vanilla-GCNN [1 based the principle of isometry, which relates benign initial parameters with graph topology. We experimentally validate that our new initialization strategy significantly improves the gradient flow in deep GCNs and provide huge performance benefits.
Gradient-Guided Dynamic Rewiring of GCNs. Contrary to ad-hoc addition of skip- comnections to improve GCNs performance, in this paper, we leverage Gradient Flow to introduce dynamic rewiring strategy of anilla-GGNNs with skip-connections. Our new rewiring improves gradient flow, reduces the overhead of storing multiple intermediate activations (dense, initial residual. jumping skips), as well as outperforms many ad-hoc skip connection mechanisms.
2 Methodology
In this section, we aim to discuss the trainability of deep GCNs from the signal propagation per- spective, i.c. gradient flow. We will provide a detailed introduction and theoretical derivation of our topology-aware isometric initialization. Furthermore, we will present novel way incorporate skip-connections using Gradient Flow to improve the trainability of deep GCNs.
2.1 Preliminaries
We begin by formulating Graph Convolutional Networks (GCN) along the way introducing our notation. Let G (V,E) be simple and undirected graph with vertex set V and edge set E. Let

---

0.5
0.5
Glorct initialization Our initialization
Vanilla GCN
Gradient Flow
0.4
Cradient Flow
0.4
Gradient- Rewired GCN
0.3
0.3
Final Acc 80
2%
Final 77.9%
0.2
0.1
0.1
Final Acc 26,
0.0
0.0
20
60
100
120
20
40
60
80
100
120
Epoch
Epoch
Figure 1: (a) Comparison of Gradient flow in 10-layer vanilla-Ge GCN with default (Glorot initialization) and our Topology-Awar initialization. (b) Comparison of Gradient flow in 10-layer GCN and GCNs with our new Gradient Flow Guided Rewiring.
A E R N be the associated adjacency matrix, such that As = 1 1f (i. E E, and Au = 0 otherwise. N = V is the number of nodes. We also define d, = Σ, A.j the node degree of the i-th vertex. Let X E RCXN be the node feature matrix, whose i-th column represents a d-dimension feature vector for the i-th node. GCNs aim to learn an embedding for each node via learnable graph convolutional filters 2 A graph convolutional layer can be formulated as
X) W I),
where adding I to adjacency matrix is known as the self-loop trick M. W E CC matrix of this layer, and C" is the dimension of output channel. An L-layer GCN cascades L layer of graph convolutional layers followed by non-linear activations:
x is the weight
Y f() oo f(L-1) ..... f(2) o ( (G,
(2)
where Y E CC is the final output of the GCN, and (-) denotes non-linear activation, which typically chosen as ReLU. Although there exists lots of message- passging based Graph Neural Networks (GNNs), which are incorporated with highly sophisticated mechanisms, such as attention and gating 33 40), the focus of our work only lies on the most classical GCN model (Eq. - that exactly follows the rigorous definition of graph convolutions [4]. As we will show in our experiments, our proposal will bring this theoretically clean GCN back to the SOTA performance.
2.2 Understanding Gradient Flow in Deep GCNs
0.07
Gradient flow and its associated problems such as ex- ploding and vanishing gradients have been extensively explored in the dynamics of learning of neural networks
0.06
Gradient Flow
0.05
W/l
special category of neural networks, which uses "graph convo- lution" operation (linear transformation of all neighbors of a node followed by non-linear activation) to learn the graph representation. Despite being powerful in learning high-quality node representations, GCNs have limited ability to extract information from high-order neighbors and significantly lose their trainability and
(CNNs/RNNs) [32 33 355) GCNs (
0.04
Layer
Layer 10
0.03
W
Layer
0.02
Final Acc
81.2%
Final 26.3%
26.3%
0.01
20
40
60
00
100
120
Epoch
Figure 2: Gradient flow of Manill-GGNN
(layer 1,10,16) trained on Cora.
performance. Recently, many works [0 21 22 24]
have been proposed to address this issue from the perspective of over-smoothing and information bot- tleneck, However, the signal propagation perspective to understand the trainability and performance of GCNs has been highly overlooked compared to the attention it has received for CNNs/RNNs.
Gradient flow is used to study the optimization dynamics of neural networks and it has been widely known that healthy gradient flow facilitates better optimization 32
33 35| 42). Consider an L-layer GCN (see Eq. 2 we denote the weight parameter for the 1-th layer (() as W.. Suppose we have cost function L. we calculate the gradient across each layer and effective gradient flow (GF) as:
OL
OL
UL
91
W1 9:
9t. WL L
(3)
W
L
1
Gradient Flow: GF,,
Σ
(4)
T.
n=1
Here we consider A is symmetrically normalized by default.
3

---

where for every layer 1, Dc represents gradients of the learnable parameters W and we have used aw, 2 in our experiments. Figure Saaneerrepp represents the gradient flow during training of vanilla-GCNs with layer 4, 6, and 10 on the Cora dataset. Figure iilusttatss the comparison of validation loss and gradient flow in vanillaGGNNs with 2 and 10 layers on Cora, Citeseer, and Pubmed. We consistently observed across each dataset that with increasing depth, the gradient flow across layers decreases significantly along with the performance. In this paper, we hypothesize that by improving the gradient flow in deep vanilla-GCNs, along with effectively improving their trainability, we can achieve SOTA- level performance from vanillaGGCNs. We propose a new topology-aware initialization strategy based on the principles of isometry and dynamic architecture rewiring for vanilla- GCNNs to improvise the gradient flow and subsequently performance (Figure (a).b)).
Cora
Choseer
Pubmed
10.00
0.26
Volldsation Lozs
66.0
0.te
0ute
Goedlent Flow
Validation Lozs
%
Gredient
Validation Locs
02
0.25
Codient
drad Filx
Layer 2 Layer
0.22
0.00
0:22
Laver
1.0
22
0.01
0:23
Epoch
Epoch
Figure 3: Comparison of validation loss and gradient flow in vanilla- GCNN with 2 and 10 layers.
2.3
Topology-Aware Isometric Initialization
Recent work of 43 has revealed that initializing network parameters nearly isometric can train very deep CNNs without any normalization. We are inspired to properly initialize each GCN layer to make it an isometric mapping. To begin with, we first give the formal definition of isometry below: Definition 1. (43 A map f x + y between two inner-product spaces is called an isometry if
(f(x), f(x')) = (xx x²)
(5)
for all x, x' E X.
Existing isometric initialization techniques are not free lunch for GCNs. Qi et al. [43 showed that convolutional operator isometric if and only if their cross-channel weights are orthogonal each other. The straightforward implication is that delta kernel can be served as the isometric initialization. However, computing delta kernel in graph signal processing needs to involve complex numbers and cigen-decomposition of the adjacency matrix 44 which is infeasible for a common deep learning framework. To this end, we re-establish theoretical results for GCNs from Definition T
Consider one GCN layer (Eq. D.. our goal is to seek weight matrix such that pair-wise angles between node features are invariant after transforming by the layer. First of all, we denote the output feature of the i-th node as y, W X az where a, is the i-th column of (A T). The inner product of two node features j.j E [] can be computed as:
(u yリ) [aT s W) vee( [)]
[(aj & W) vec( X)]
(6)
Tr (((aaa) & (WTw) W
vee( X) vec vec(X)T),
(7)
where vec(-) denotes vectorization of matrix, Eq. 6 follows from the equality vec(ABC)
(CT & A) vec [45). On the other hand, x; Ic e, where e, is the i-th canonical basis, we can obtain a similar form of (mx :;
(z,, w,) Tr (I(ete)) & Ic] vec(X) )
(
To achieve isometry, we hope to solve a W such that Eq. closed-form solution does not exist in general. Instead, we seek a W to minimize the difference
g eequals to Eq. 7 However, a simple
between Eq. and Eq. 7
W' = argmin
Σ (JEIN
Ky. v,) - (II 2)i)²
(9)
We Xo
Σ Tt2 ([(a,a)) 3 (WTW) - -(eee)) s [o] veo(X) vec(x) (10)
= argmin We
[.E[N]

---

However, minimizing objective Eq. T0 will involve data matrix into the solution, which limits computational efficiency and generalization. Hence, we optimize looser upper bound of Eq. by minimizing the difference between (a,a) J @ ( W and (e,e,) @ Ic. The intuition is that once this difference reaches zero, Eq. Wiill will be minimized to zero as well.
W argmin
Σ
(a.a3) @ ( (WTw) (e.ee) @ Ic
(11)
WERC'xO x JJENN
At the first glance, Eq. I is non-convex and Kronecker product will produce a computational prohibitive matrix, which makes this problem intractable. However, it has not escaped our notice that the structure of a,a, is highly sparse. Hence, the entire norm minimization can be decomposed into wise minimization problems. We defer the detailed derivation into Appendix ??. As the consequence, the optimal solution to Eq. should satisfy:
2
Wk [C],
(12)
EijeNn( + (d, 1)
W wT =
Vk, E [C], +
(13)
where wy denotes the k-tt column of optimal weight matrix W Eq. 13 suggests that isometry requires weights for different channels to be orthogonal, which conforms with the general results of [3). But different from [43, results indicate that the magnitude of channel-wise weights should be constrained by a degree-related constant (Eq. 12), which binds the initial weights with topological information. To randomly initialize W in practice, one draw each column of W from
independent distributions (e.g., white Gaussian) with variance Σ² = N Ei' (d: + 1)(d; + +1] and to initialize weights with bounded values, we suggest employ the following uniform distribution:
3N2
3N2
W ~
(14)
c" (Ensemn(de+ 1)d, / (EEEEEE (d: (d 1)(d, + +1)
2.4
Gradient-Guided Dynamic Rewiring
Graph Convolutions can be considered as a type of Laplacian smoothing, and repeatedly ap- plying Laplacian smoothing many times in the case of multi-layer GCNs, leads the representa- tions of the nodes in GCN to converge to certain value and thus become indistinguishable, i.c. lose expressiveness and trainability 200 46). Despite numerous efforts from architectural, regular- ization, and normalization perspectives 23
25 28 29], there still exists a wide gap in fully understanding the trainability issue of deep GCNs which can aid in developing techniques which can prevent performance deterioration with increasing depth.
26
27
24
20
In this work, we look for the effect of increasing depth the error signal propagation during training and found that deep GCNs suffer from poor gradient flow and it worsens dramatically with increasing depth, thereby completely blocking the gradient propagation and potentially leading to catastrophic failure to update during training. More specifically, we performed gradient flow analysis during training of deep vanilla-GCNs (Figure 4 (a)) and found that with the progress in training, many deep GCN layers receive almost zero error signal during backpropagation (i.e. gradients) and unable to train. Motivated by this finding, we use computationally efficient Gradient Flow metric to identify layers that block healthy error signal back propagation during training and propose to dynamically rewire the vanilla- GCNs using skip- ccinecoonnttions (widely known improve gradient flow), which we call on- on-demand dynamic rewiring. Our dynamic rewiring technique improves gradient flow, mitigate sudden feature collapse and significantly helps in training deep vanilla-GCNe with high performance (Figure lbb) ac). Mathematically. our dynamic rewiring can be written as:
X = W X (1-))
(A + I)
(15)
x L (X) <
GF 1 IaxX! JaX! (1-I)
+X;
(16)
where, [::] is an indicator function, the subscript / denotes the training epoch, the superscript / denotes the layer index, GF denotes gradient flow, a denotes skip information ratio, and p denotes gradient flow drop threshold.
5

---

Precisely, we observe the Gradient Flow of each vanilla- GCN layer during training, and if the flow drop by p% (hyperparameter) of its initial value at the start of training. we assist the layer with a skip-connection. We use modified version of initial residual connection 47 24 which we define as the output feature matrix of first layer of vanilla-GCN (gives better performance than 47 24)), to supplement the layers that quickly loses energy. Once the layers which are more prone to lose expressiveness are identified and rewired using the skip-connections, the vanilla-GCN training can proceed as normal.
In comparison with previous work 23
38 20 which blindly inherits skip-connection techniques
from CNNs/RNNs, our work provides a principled approach to perform architectural rewiring of vanilla-GNNs. Static skips introduced in [23] [2 38 (0),, by default incorporate skips for training shallow GCNs with 2-3 layers (which do not require it), and tend to hurt the final performance. For example, in 3 can be observed that training 2-layered GCN with initial, jumping, or residual skips suffers- -2. %., -0.12%, -6.37% performance drop compared to a plain vanilla-GCN (81. 10%) on Cora. Our method only introduces skip-connections when is required by tracking the gradient flow of the layer, and thereby overcomes the issue of adding skips in shallow GCNs, and for layers that receive healthy gradient flow. Our extensive experiments on multiple datasets reveal that our approach of guided rewiring not only brings benefits on the efficiency front (memory overhead to store intermediate activations) but also comfortably outperforms all SOTA ad- ad-hoc sippconnection.
3 Experiment
In this section, we first provide experimental evidence to augment our signal propagation hypothesis and show that our newly proposed methods facilitate healthy gradient flow during the training of deep-vanilla GCNs. Next, we extensively evaluate our methods against state-of-the-ar graph neural network models and techniques to improve vanill-GGCNs on on a wide variety of open graph datasets.
Settngs
Corn
Pabmed
OGBN-A-Xiv
(Leurning rate. Weight Decay, Lidden dimesnion)
(0.005, 5e
4.64)
10,005, Se 4,64)
(0.01, 4, 4,6 (0.005, O. 256)
Table 1: Hyperparameter configuration for proposed method on representative datasets.
3.1 Dataset and Experimental Setup
We use three standard citation network datasets Cora, Citeseer, and Pubmed 48 in GNN domain for evaluating our proposed methods against state-of-the-art GNN models and techniques. We have used the basic vanilla-GCN implementation in Py PyTorch provided by the authors of (0 to incorporate our proposed techniques and show their effectiveness in making traditional GCN comparable/better with SOTA. For our evaluation on Cora, Citeseer, Pubmed, and OGBN-ArXiv, we have closely followed the data split settings and metrics reported by the recent benchmark [49]. See details in Appendix ?? For comparison with SOTA models, we have used JKNet [50], InceptionGCN [51], SGC (52), GAT B. GCNII [24), and DAGNN (53). We use Adam optimizer for our experiments and performed grid search to tune hyperparameters for our proposed methods and reported our settings in Table [ For all our experiments, we have trained our modified GCNs for 1500 epochs and 100 independent
repetitions following [49 and reported average performances with the standard deviations of the node classification accuracies. All experiments on large graph datasets, e.g., OGBN-ArXiv, are conducted on single 48G Quadro RTX 8000 GPU, while small graph experiments are completed using single 16G RTX 5000 GPU.
3.2 Gradient Flow and our proposed methods
Despite significant efforts to improve deep neural networks (CNNs/RNNs) training from the signal propagation perspective, in in-depth analysis of deep GCNs training with a focus on the gradient flow during back proppapppagttion is highly overlooked. We use Equation 4 to study gradient flow during the training of GCNs and Figure indicates that with an increase in depth, gradient flow in the network drop significantly hurting the trainability of GCNs. Figure indicates the relation between gradient flow and drop in validation loss (performance) for 2-layer and 10-layer GCNs for Cora, Citeseer, and Pubmed. It can be observed that across all datasets, 10-layer GCN has poor gradient flow compared to 2-layer GCN and we observed negligible drop in validation loss during training.

---

Vanilo GCN
GCN Our
SOV Gradient Rowring
Layer
Layer
Layer
Layer
Layer
Laver
Ep
Epoch
Epoch
Figure 4: Visualization of the gradient flow of layers during the training of 10-layers vanilla GCN, vanilla-GCN with our new topology-aware initialization and dynamic DE-based rewiring for 500 epochs on Cora, Our methods promote uniform gradient flow across all layers of vanilla-GCNs.
To better understand the behavior of each hidden layer in deep GCN training, we estimated the gradient flow per layer independently of a 10-layer GCN. To our surprise, we found that many layers receive zero error signals (gradients) under backpropagation, potentially leading to a catastrophic failure to update during training. Figure 4 a) illustrate layerwwise analysis of gradient flow in 10-layer vanilla-GCN on Cora. We observed that within few epochs of training, the gradient flow saturates, and then onwards, many layers of GCN receive zero error signal during the backpropagation and they fail to update leading to no drop in validation loss.
Layer Number
Dataset
Settings
2
3
4
8
9
10
11
12
Cora
GCN
81.1
81.9
80.4
79.9
77.5
77.1
69.5
28.2
27.4
30.1
25.4
GCN + Our Init
83.0
83.4
80.6
80.0
81.2
80.6
80.4
79.9
80.1
79.2
78.5
CiteSeer
GCN
71.4
67.6
64.6
63.7
63.9
24.1
20.8
22.3
23.2
22.9
21.6
GCN Our Init
71.7
78.2
68.3
62.8
61.9
PubMed
GCN
79.0
78.9
76.5
76.7
77.1
76.5
61.2
40.7
43.2
41.0
GCN Our Init
79.3
80.0
78.5
77.6
77.6
76.7
75.8
76.9
76.2
76.3
75.9
Table 2: Performance Comparison (test accuracy %) of of vanilla-GCNs (1) with and without newly proposed ropology-aware isometric initialization. Experiments are conducted on Cora, Citeseer, and PubMed using Mnilla-GCNs with layer 1 E (2, (2.,..... 12).
Initialization of neural networks is tightly coupled with the propagation of error signals 3 and effect their trainability. Our newly proposed topology-awer -aware isometric initialization and gradient- guided rewiring significantly improve gradient flow (Figure TTa) and (b)) as well as mitigate the issue of feature collapse of layers in deep vanilla-GCNs. In Figure 4b) and (c), the detailed layer-wise analysis of vanilla-GCN with our newly proposed methods clearly illustrate how our methods are able to uniformly restore healthy gradients across all layers leading improved trainability and significant performance gains.
Category
Settings
Cora
Citeseer
PubMed
2
32
2
16
32
32
VanillaGCCN
81.10
21.49
21.22
71,46
19.59
20.29
79.76
39.14
38.77
Skip
Resichul
74.73
20.05
19.57
66.83
20.77
20.90
75.27
38 84
38.74
Connection
Initial
79.00
78.61
78.74
70.15
68.41
68.36
77.92
77.52
78.18
Jumping
80.98
76.04
75.57
69.33
58.38
55.03
77.83
75.62
75.36
Dense
77.86
69.61
67.26
66.18
49.33
41.48
72.53
69.00
62.99
Normalization
BatchNorm
69.91
61.20
29.05
46.27
26.25
21.82
67.15
58.00
$5.98
PairNorm
74.43
55.75
17.67
63.26
27.45
20.67
75.67
71.30
61.54
NodeNorm
79.87
21.46
21.48
68.96
18.81
19.03
78.14
40.92
40.93
CombNorm
80.00
55.64
21.44
68.59
18.90
18.53
78.11
40.93
40.90
Random Dropping
DropNode
77.10
27.61
21.65
69.38
21.83
22,18
77.39
40.31
40.38
DropEige
79.16
27.87
70.26
22.92
40.50
LADIES
77.12
28.07
27.54
68.87
22.52
22.60
78.31
40.07
40.11
Identity Mapping
82.98
67.23
40:57
68.25
56.39
35.28
79.09
79.55
73.74
Gradient-Guided Rewiring (Ours)
82.79
$0.01
71.06
68.54
78.32
78.51
+60.16
+0.32
15.15
+:0.11
+0.11
+.0.31
+0.20
+90.19
+-0.27
Table 3: Performance Comparison of Gradient-guided Rewiring with respect to various proposed fancy techniques to improve the GCN training. Note that our results are generated using vanilla-Ger GCN []] Experiments are conducted Cora, Citeseer, and PubMed with 2/16/32 layers GCN.
7

---

3.3 Vanilla-GCNs and our proposed methods
In this section, we conduct a systematic study to understand the performance gain by improving gradient flow using our proposed methods: topology-aware isometric initialization and Gradient Guided Dynamic Rewiring, by incorporating them into the training process of deep vanilla-GCN Table 2 demonstrate the performance comparison of vanilla-GCNs [ with and without our new initialization method with an increase in depth. Our experiments on Cora, Citeseer, and PubMed using vanilla-GCNs with layers I E {2.3, ..., 12) illustrate how our new initialization has been successful in retaining the trainability of vanilla-GCNs with increasing depth along with improving performance at shallow depths. The highlighted (red) box represents the depths which vanilla-GCN GClNa lose trainability,, L.e validation loss shows no improvement during training.
Trainability issue of deep GCNs has been extensively studied from the perspective of over- smootheming 20 [1 and information bottleneck (22) and many approaches broadly categorized as architectural tweaks [23 24, 20 25]. and regularization & normalization [26] 27 28 29 has been proposed for mitigation. We defer their detailed description to Appendix ??. Table demonstrates the performance comparison of our gradient-guidee dynamic rewiring using skip-connections with re- techniques to improve deep GCNs training. It can be clearly observed
spect to various that on-demand dynamic rewiring method of introducing new skip-connections significantly outperforms all fancy normalization and regularization techniques as well as comfortably beats ad-hoc Axip-connections techniques.
Cora
PubMed
Method
2
64
Vanilla GCN 1
81.1
80.4
69.5
21.5
21.2
21.9
79.0
76.5
61.2
39.1
38.7
35.3
GAT [
81.9
80.3
31.3
30.5
27.1
27.9
78.4
77.4
29.1
26.3
28.7
25.0
JKNet 50
79.1
79.2
75.0
72.9
73.2
71.5
77.8
68.7
67.7
69.8
68.2
63.4
SGC
79.3
79.0
77.2
65.3
78.0
73.1
70.9
63.2
INCeptionGCN 51
79.2
77.6
76.5
81.7
81.7
80.0
78.5
77.7
77.9
74.9
74.1
74.3
GCNIT
82.2
82.6
84.2
84.6
78.2
78.8
79.3
79.8
79.7
Ours
83.1
82.8
82.4
82.3
82.1 1
80.4
80.2
79.6
79.8
79.5
79.9
79.7
(std: +:)
0.25
0.23
0.24
0.22
0.16
0.29
0.17
0.24
Table 4: Performance Comparison (test accuracy %) of our proposed method (topology- initial- ization and gradient-guide rewiring) with other previous SOTA frameworks on Cora & Pubmed.
3.4 Comparison with state-of-the-art methods
To further validate the effectiveness improving gradient flow in vanilla-GCNs, we perform compar- isons with previous state-of-the-art frameworks, including SG GAT(3 [KNet(50), APPNP (47), InceptionGCNI55] GPRGNN (54, and GCNII(4). We first observe that Gradient guided rewiring and Topology-ave aware isometric initialization brings orthogonal benefits and combining them helps vanillaGGCNs to achieve better performance. Table rreports the mean classification accuracy and the standard deviation on the test set of Cora and Pubmed of our methods using vanilla-GCNs with layer E {2, 4, 8, 16, 32, 64). One key benefit to note is that with the help of our methods, we can train vanilla-GCNs as deep as 64 layers. It can be observed that vanilla-GCM with our methods outperform all SOTA methods on Cora (layers 2 and 4) and Pubmed (layers 2, 4. 8, and 64), while holding the second position for all other layers. To evaluate on a large graph, we have chosen OGBN-AxRiv dataset, and (ableeS]rerresent the performance comparison of vanilla-GCNs with our method against SOTA baselines. It can be observed that with the help of our methods, vanilla- GCCNs can be efficiently trained deeper without any significant loss in performance. Very similar to Cora and Pubmed, our methods beats all SOTA methods while training 2-layer vanilla-GCNs and holds second position for all other layers. It is interesting to note that for OGBN-AxRin datasct, vanillaGGCNa with our proposed method consistently have performance improvement with an increase in depth possibly because of being able to capture long-term information effectively, which is in contrast to most of the SOTA methods whose performance suffers with increased in depth. Note that we are NOT trying to beat SOTA, but instead, our objective is to reveal the correct initialization and training scheme for vanilla-GCN and scale deep efficiently.
The last sanity check is whether our proposed methods can make deep SanillaGGCN effective across multiple different graph datasets. Specially, we evaluate it on seven other open-source graph datasets: (i) one Co-author datasets (55) (CS), (ii) two Amazon datasets (55) (Computers and Photo), (iii) three
8

---

Layer
GCN
SGC 52
DAGNN 25
GCNI 24
JKNe: 50
APPNP[47
GPRGNN 54
Ours
2
69.46-20.22
61.98=00.08
67.65=0.552
71.24:00.17
63.73+0.38
65.3140223
69.31=00.09
71.59=00.88
16
0.3
41.88:10.77
71882:0.28
72.61:0.29
6..5
66.95:10:24
70.30:10115
71.76:10.03
32
45.46-14.55
34.22:10.04
41.26.1.27
72.60-10.25
66.31.10.33
66.94110226
10.18:10.16
72.03-10.55
64
38. 7.663
36.17=2.11
70.22::.554
72.13-20.99
62.9743.81
65.54::1.74
70.59:2.60
72.28:00.22
Table 5: Performance Comparison (test accuracy %) of our proposed method (topology-aver initialization and Gradient-guide guided rewiring) with previous SOTA frameworks using OGBN-AxRiv.
WebKB datasets [56] (Texas, Wisconsin, Cornell), and (iv) the Actor dataset [56]. Table 6 reports the
performance comparison of deep vanilla-GCN with 32-layers with state-of-the-ass methods having the same depth. Our methods universally encourage significant trainability benefits to deep vanilla-GCNs across all datasets achieving state-of-the-an performance on Computers dataset while performing in top-2 for all remaining datasets.
Calegory
CS [55
Computers 55
Photo [5
Texas [56]
Winconsin 56
Comell [56]
Actors [56]
GCN 0
24.01=3.42
58.72:b4.97
$8.64=8.40
60.12:+4,22
$2.94:::3999
54.05=7.11
25,46 144
GAT
11.04=0.94
9.42400.4
1.02
11.54+0..2
14.01110.88
19.78-144 1.42
6.42:40.3
SGC
59
70.52=3.96
37,53=0,20
26.60=4.64
56.41:4.25
51.29+6.44
58.57=3.44
26.17=11115
GCNII 24
71.67=2.68
37.56:20.43
62.95=9944
6.519::6.56
70.31:14.75
74.16=6.48
34.28:t1.12
JKNet
50
81.82:13.32
6..99
78.42.16.88
61,08 6.223
52.76.15.69
4..90
28.80
APPNP
47
0.49
43.02:1 16
59.62.4.3.27
60.68:14.50
54.24:15.94
58.47=3.74
28.65 1.28
Ours
89.33 2.10
77.18:11.72
72.77
2.993
9.0077
58.51 1.66
30.95.1.1.0
Table 6: Transfer studies of our proposed method (topology-awar initialization and gradient-guided rewiring) with deep vanillaGGCNs (32-layers). Comparisons are conducted on seven open-source widely adopted datasets with other previous state-of-the-art frameworks.
3.5 Dirichlet Energy-based analysis of our proposed methods
In this section, we use Dirichlet Energy to illustrate how our proposed techniques help in mitigating the issue of losing expressiveness, enable deep GNNs to leverage the high-order neighbors. Node pair distance has been widely adopted to quantify the embedding similarities, and Dirichlet energy is simple and expressive metric to estimate the expressiveness of node embeddings learned by GCNs, in topology-awan fashion 46 57]. Following [66, we define Dirichlet Energy as:
Definition 2.
[46] Dirichlet energy E(x) of scalar function x E R on the graph G is defined as:
1 Σ
E(x) = x Lx
(17)
2
(1 (1+ d,)1/22 (1+ (1+d,) d,)
(1.)EE
For the vector field X =[x1 aN1 E RCNN where w; E RRC, Dirichlet energy is defined as:
E(X) -XX)-T(XXXX')
Σ (L.jEe
(18)
(1+d))
(1+ d 12
Cora Vanila-CCN
Choseer Vanila-GEN
Pubmed Vanila-OCN
Layer
Layer Layer
Loger Layer
Layer
Layer
-40
Epoch Cor proposed Methods
Spoch
Epoch
Cheseer proposed Methods
Pubmed Our proposed Methods
Layer
Layer
Layer
Leyer
Layer
Layer
Layer
Layer
Layer
Epach
Epoch
Epach
Figure 5: Visualization of Dirichlet Energy of layers during the training of 10-layers vanilla GCN (row 1) and with our proposed methods on Cora, Pubmed, and Citeseer. Plotted using the log scale for better visualization. Our methods prevent Dirichlet Energy to drop to zero during training and maintain the expressiveness of feature embeddings.

---

We track the Dirichlet energy of feature matrix w.r.t. the (augmented) normalized Laplacian at different layers of the vanilla-GCy during training and observed that during training of deep vanilla-GCN, the Dirichlet energy of some layers decreases exponentially and becomes close to zero within a few epochs of training. i.e lose expressiveness (Figure(3) row 1). Our newly proposed methods: topology-awan
isometric initialization and gradient-guided rewiring significantly improve gradient flow, as well as mitigate the issue of exponentially dropping Dirichlet energy across all the layers of deep GCNs, thereby restoring the expressiveness of node embeddings (Figure row 2).
Other Related Works
GNNs have established state-of oftthe-rrt performance in numerous real-world applications
13 11
18 While deep architectures improve the representational power not every useful GNN has to be deep. Many real-world graph are -ooall-world"(O0] where a node can reach any other node in a few hops, hence few layers would suffice to provide global coverage. However, when the graph data has no small-world property, or the related task requires long-range information, then deeper GNNs become very necessary. Many works [20] 21 revealed that when we start stacking spatial aggregations recursively in GNNs, the node representations will collapse to indistinguishable vectors and it will hamper the training of deep GNNs. More generally, this phenomenon happens for any message -aaagggg mechanism via stochastic matrices including attention [6]] Recently, there has been series of techniques developed to handle the over-smoothing issue, which can be broadly categorized under skip connection, graph normalization, random dropping. Skip-connections 23 24
5
4 14
15
16
12
17
of neural networks
58
59,
38 20) have been applied to GNNs to exploit node embeddings from the preceding layers, to relieve the over-smoothing issue. Graph
normalization techniques [28] 62 63 64 (65] re-scale node embeddings over an input graph to constrain pairwise node distance and thus alleviate over-smoothing Dropout methods [66] 26 27 67 can be regarded as data augmentations, which help relieve both the over-fitting and over-smoothing issues in training very deep GNNs.
5 Conclusion
This paper makes an important step towards understanding the substandard performance of deep vanilla-GCNs from the signal propagation perspective and hypothesizes that by facilitating healthy gradient flow, we can significantly improve their trainability, as well as achieve state-of-the-ard (SOTA) level performance or close using merely vanillaGGNNs. This paper derives a topology-aware isometric initialization scheme for vanilla-GCNs based on the principles of isometry. Additionally, this paper proposes to use Gradient Flow for the dynamic rewiring of vanilla- GCNNs with skip-connections Extensive experiments across multiple datasets illustrate that these methods improvise gradient flow in deep vanilla- GCNN and significantly boost their performance. An interesting direction for future work includes building theoretical relations between our proposed methods and gradient flow.
References
[1] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, abs/16099000 (bs//6609.0207.. 2017.
[2] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[3] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 171. 10903, 2017.
[4] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. L2-gen: Layer-wise and learned efficient training of graph convolutional networks. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2124-2132, 2020.
[5] Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018
10

---

[6] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 257-266, 2019.
[7] Wenqing Zheng, Edward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subhian. Cold brew: Distilling graph node representations with incomplete or missing neighborhoods. arXiv preprint arXiv:2 / 04840, 2021.
[8] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.102. 2018.
[9] Keyu Duan, Zirui Liu, Peihao Wang, Wenqing Zheng. Kaixiong Zhou, Tianlong Chen, Xia Hu, and Zhangyang Wang. A comprehensive study on large-scale graph training: Benchmarking and rethinking. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[10] Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint UrXiv:1803.0333 2018.
[11] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[12] Junyuan Shang, Cao Xiao, Tengfei Ma, Hongyan Li, and Jimeng Sun. Gamenet: Graph aug- mented memory networks for recommending medication combination. ArXiv, abs/1 abs/1809.00 809.01 01852, 2019.
[13] Lei Tang and Huan Liu. Relational learning via latent social dimensions. In KDD, 2009.
[14] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self supervupervii help graph convolutional networks? Proceedings of machine learning research, 11::10871- 2020.
[15] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In NIPS, 2017.
[16] Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33:i190 ii98, 2017.
[17] Long Zhao, Xi Peng, Yu Tian, Mubbasir Kapadia, and Dimitris N. Metaxas. Semantic graph convolutional networks for 3d human pose regression. 2019 JEEE/CVF Conference on Computer Vision and Patlern Recognition (CVPR), pages 3420-3430, 2019.
[18] Yixiao Zhang, Xiaosong Wang, Ziyue Xu, Qihang Yu, Alan Loddon Yuille, and Daguang Xu. When radiology report generation meets knowledge graph. AAAI, 2020.
[19] Zhiwen Fan, Lingjie Zhu, Honghua Li, Xiaohao Chen, Siyu Zhu, and Ping Tan. Floorplancad: large-scale cad drawing dataset for panoptic symbol spotting. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 10128-10137, 2021.
[20] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for supervise learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
[21] Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. ArXiv, abs/ 100.099000550, 2019.
[22] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. ArXiv, abs/2066.05205, 2021.
[23] Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Can gens go as deep as cnns? ArXiv, abs//104.03775 2019.
[24] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. ArXiv, abs/2007.021133, 2020.
(25) Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
[26) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
11

---

[27] Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general graph convolutional networks. ArXiv, abs/2008.09864, 2020.
[28]
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. ArXiv, 122219999.222,,, 2020.
[29] Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation in deep graph convolutional networks. Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021.
[30] Weilin Cong, Morteza Ramezani, and Mchrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936-9944 2021.
[31] Sitao Luan, Mingde Zhao, Xiao Wen Chang, and Doina Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. arXiv preprint arXiv:2008 08838, 2020.
[32] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, 2010.
[33] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. 2015 IEEE International Conference on Computer Vision (ICCV), pages 1026-1034. 2015.
[34] Jeffrey Pennington, Samuel S. Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In NIPS, 2017.
[35] Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein Deep infor- mation propagation. ArXiv, abs/1611 abs/1611.01122, 2017.
[36] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[37] Gao Huang, Zhuang Liu, and Kilian Q. Weinberger. Densely connected convolutional networks. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 2261-2269, 2017.
[38] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks. ArXiv, Abs/1806.03536, 2018
[39] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.0544 2015.
[40] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint 17105537 2017.
[41] Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs. IEEE transactions signal processing, 61(7):1644-1656, 2013.
[42] Ajay Kumar Jaiswal, Haoyu Ma, Tianlong Chen, Ying Ding, and Zhangyang Wang. Spending your winning lottery better after drawing it. arXiv preprint arXiv:2101.03255 2021.
[43] Haozhi Qi, Chong You, Xiaolong Wang, Yi Ma, and Jitendra Malik. Deep isometric learning for visual recognition. In International Conference on Machine Learning, pages 7824-7835.
PMLR, 2020.
[44] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-88) -288088888,,00 2018.
[45] Kathrin Schacke. On the kronecker product. Master's thesis, University of Wuterloo, 2004.
[46] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
[47] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
12

---

[48]
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification in network data articles. Al Magazine, 29:93-106, 09 2008.
[49] Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng. Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: A comprchensive benchmark study. arXiv preprint arXiv:2108.106 10521. 2021.
[50] 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, pages 5453-5462. PMLR, 2018.
[51] Anees Kazi, Shayan Shekarforoush, S Arvind Krishna, Hendrik Burwinkel, Gerome Vivar, Karsten Kortüm, Seyed-Ahmad Ahmadi, Shadi Albarqouni, and Nassir Navab. Inceptiongen: receptive field aware graph convolutional network for disease prediction. In International Conference on Information Processing in Medical Imaging, pages 73-85. Springer, 2019.
[52] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pages 6861-6871. PMLR, 2019.
[53] Liqi Yang, Linhan Luo, Lifeng Xin, Xiaofeng Zhang, and Xinni Zhang. Dagmn: Demand-aware graph neural networks for session-based recommendation. arXiv preprint arX1v:2105.14428, 2021.
[54] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
[55] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojehevski, and Stephan Günnemann.
Pitfalls of graph neural network evaluation. arXiv preprint 1rXiv:1811.05866 2018.
[56) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 200.i::0022.22887 2020.
[57] Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34:21834-21844 2021.
(58) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 18X.vv:8100000800 2018
[59] Peihao Wang. Yuchao Wang, Hua Lin, and Jianbo Shi. Sogen: Second-order graph convolutional networks. arXiv preprint 2 2022
[60] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
[61] Peihao Wang, Wenqing Zheng, Tianlong Chen, and Zhangyang Wang. Anti-oversmoothing in deep vision transformers via the fourier domain analysis: From theory to practice. arXiv preprint arXiv:2203.00 220.0096.. 2022.
[62] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015.
[63] Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. Advances in Neural Information Processing Systems, 33:4917-4928, 2020.
[64] Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3-19, 2018.
[65] Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens. arXiv preprint arXiv:2003.13663, 2020.
[66] Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdi- nov. Dropout: a simple way to prevent neural networks from overfitting. J. Much. Learn. Res., 15:1929-1955 2014.
[67] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. In NeurIPS, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "djHzBvkz6c5", "reviewer": "Reviewer_eHHR", "summary": "The authors study the gradient flow of deep GCNs and derive a topology-aware isometric initialization scheme for vanilla-GCNs. Then, they propose to use Dirichlet Energy for dynamic rewiring of vanilla-GCNs with skip-connections to increase the expressive power of GCN. \n", "questions": "1).  Line 76, “we leverage Dirichlet Energy (which measures the expressiveness of feature embedding)…” I cannot see why Dirichlet Energy measures the expressiveness of feature embedding? \n\n2). In equation (4), why is the gradient flow defined as the mean of the p-norm of the gradients for all the L layers.\n\n3). What is the standard deviation of the results in table 2.\n\n4). What is the “Dirichlet Energy guided rewiring” looks like? Write it in math.\n\nWriting:\n\n1). The position of Figure 1 need to be adjusted.\n\n2). Figure 3 is messy, I suggest only keeping one set of legend and moving it outside the plot.\n\n3). To simplify the computation, in equation (6), you can write $y_i = WX(A+I)e_i$, where $e_i$ is the column one-hot vector with 1 in I-th element and 0 for others.\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths: \n1. The writing is easy to follow.\n\n2. The experiments are comprehensive.\n\n\n## Weaknesses: \n\n1. The method and results have some novelty but not significant.\n\n2. Some plots are messy and some arguments are not well support by enough evidence.\n\n3. Some Missing literature on the gradient flow and trainability of GNNs. [1,2]\n\n[1] Luan S, Zhao M, Chang X W, et al. Training matters: Unlocking potentials of deeper graph convolutional neural networks[J]. arXiv preprint arXiv:2008.08838, 2020.\n\n[2] Cong W, Ramezani M, Mahdavi M. On provable benefits of depth in training graph convolutional networks[J]. Advances in Neural Information Processing Systems, 2021, 34: 9936-9949.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LUyxEMhScf", "reviewer": "Reviewer_7SM5", "summary": "The work focuses on improving the trainability of vanilla-GCN. Starting from the initial observation of the gradient flow issue, the authors propose two techniques, namely topology-aware isometric initialization and Dirichlet energy guided rewiring to improve the optimization. Empirically, on several benchmark datasets, authors show that the propose two techniques do improve the training of vanilla-GCN, leading to a competitive model quality (though not SOTA).", "questions": "Can the proposed two techniques improve SOTA GNNs not just GCNs?\n", "limitations": "Nothing particular.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is written in a very logical way and the proposed methods are well motivated. The empirical evaluation is systematic and convincing.\n\nHowever, it seems the trainability issue generally happens when the number of layers is large. But even when the proposed methods are used, increasing the number of layers generally does not improve the model quality at all. Hence, is it possible that the trainability issue comes from the fact that the datasets are too small and/or too noisy such that higher model capacity does not help? \n\nAnother question I have is that would the proposed two techniques be helpful to other more complicated SOTA GNNs with e.g. attention  & normalization? If so, the proposed techniques would be more helpful in practice.\n\nFinally, while adaptive rewiring based on Dirichlet energy is quite effective, it always uses the output feature matrix of first layer as the skip feature. Compared to the standard skip connection used in ResNet, this effectively makes the network relatively shallower, which can be seen as trading model complexity for trainability. Then, why not just use shallower networks instead then?", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7gp4ZLYAdo", "reviewer": "Reviewer_ePpt", "summary": "This paper tries to improve the performance of the deep GNN model by improving the gradient flow during training. Specifically, the authors propose two methods, topology-\naware isometric initialization and dynamic rewiring by Dirichlet Energy. Topology-\naware isometric initialization aims to provide a good initialization with isometric property, while dynamic rewiring is to dynamically add the skip connections based on the decrease of  Dirichlet energy of each GCN layer.\n", "questions": "Please refer  to the Strengths And Weaknesses.", "limitations": "None", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe idea of improving gradient flow is insightful. I agree that gradient flow is a key factor in improving the performance of Deep GNNs. \nIt's easy to read and understand. I enjoyed reading this paper. \n\nWeaknesses:\n1. I think the observations in this paper are insightful. The proposed solution generally works.  The main weakness lies in the theoretical analysis. In the isometric initialization part, the authors only give the construction of the initialization (Eq 14) without any further justification. Then, in the rewiring part, the authors directly apply the Dirichlet energy as a measure to control the generation of skip connections. It makes use of the property of Dirichlet energy but is too artificial.  Meanwhile, the relationship between Dirichlet energy and gradient flow is not well elaborated. \n\n2. I like the nice figures and rich empirical evaluations in this paper.  Here are my suggestions:\n\n- Since the gradient flow is defined on gradients rather than graphs, I’m curious whether the proposed isometric initialization and dynamic rewiring can improve the gradient flow on the MLP model or not. \n\n- As stated in the paper, the dynamic rewiring needs to update Dirichlet energy $Tr(XLX^{T})$ for each GCN layer during training. It looks like the calculation of  $Tr(XLX^{T})$ is expensive, especially for a large graph. I want to see the impact of this dynamic rewiring in terms of training time.\n\n - Is isometric initialization also work for other GNN backbones, such as GAT, and APPNP?\n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "1u2NuXg8iNe", "reviewer": "Reviewer_K9SU", "summary": "This work adds insight into why Graph Convolutional Networks (GCNs) have had trouble going deep. In particularly, it extends the intuition of \"over-smoothening\" and \"information bottlenecks\" that plague other neural nets (which were solved by gradient flow) and uses techniques to improve gradient flow for GCNs. In particular, it does better initialization (topology-aware isometric initialization) and rewiring (Dirichlet Energy Guided Dynamic Rewiring). By having a better distribution of initial weights and adding skip connections to propagate gradients into needed areas on where needed, the authors demonstrate very competitive (usually top-2 of 14) performance by enhancing a mere vanilla-GCN.", "questions": "Under what conditions is the sparsity assumption for the structure of a_{i}a_{j} no longer true?", "limitations": "n/a", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ This is a very well-motivated work. The discussion of gradient flow solutions for other neural networks very cleanly tees up the \"obviousness\" of gradient flow solutions for GCNs.\n+ The experiments to measure gradient flow in GCNs (eg Figure 2) are useful and interesting.\n+ Really enjoyed the simple insight applied by this paper to demonstrate big gains. Particularly impressed by the dynamic skip connections.\n+ The writing for this paper was very clear (e.g. description of how GCNs work in section 2.2, underlining certain phrases for emphasis, approachable tone of describing other methods as \"fancy state-of-the-art methds\")\n\nWeaknesses\n- It wasn't always clear whether the demonstrated issues with deep networks were primarily from gradient flow, per se, as opposed to generally just overfitting. Deeper networks are higher-capacity, but the motivating experiments did not disentangle that.\n- You reference \"Appendix 1\" on line 158, but this work does not have an appendix.\n\nSuggested Tweaks\n- Format-wise, the figures were a little scattered. Figure 1 is listed on page 2 but not described until page 4.\n- There are a few typos (e.g. \"bolltleneck\" on line 32, plural complex numbers* on line 138) or seemingly wrong words (eg on page 5 you miight have meant \"improvises\" instead of \"improves\" gradient flow, though I don't think the next word is correct when you say \"Our dynamic rewiring ... retain Dirichlet Energy\").\n- In Table 4, imo you should only bold the best entry in each column. If you really want to draw attention to the second best entry, perhaps you could underline them?", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept