DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
Authors: Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang
Venue:  (2020)
Keywords: graph neural network
over-smoothing
over-fitting
dropedge
graph convolutional networks

Abstract: Over-fitting and over-smoothing are two main obstacles of developing deep Graph Convolutional Networks (GCNs) for node classification. In particular, over-fitting weakens the generalization ability on small dataset, while over-smoothing impedes model training by isolating output representations from the input features with the increase in network depth. This paper proposes DropEdge, a novel and flexible technique to alleviate both issues. At its core, DropEdge randomly removes a certain number of edges from the input graph at each training epoch, acting like a data augmenter and also a message passing reducer. Furthermore, we theoretically demonstrate that DropEdge either reduces the convergence speed of over-smoothing or relieves the information loss caused by it. More importantly, our DropEdge is a general skill that can be equipped with many other backbone models (e.g. GCN, ResGCN, GraphSAGE, and JKNet) for enhanced performance. Extensive experiments on several benchmarks verify that DropEdge consistently improves the performance on a variety of both shallow and deep GCNs. The effect of DropEdge on preventing over-smoothing is empirically visualized and validated as well. Codes are released on~https://github.com/DropEdge/DropEdge.

Published as a conference paper at ICLR 2020
DROPEDGE: TOWARDS DEEP GRAPH CONVOLU- TIONAL NETWORKS ON NODE CLASSIFICATION
Yu Rong', Wenbing Huang?; Tingyang Xu', Junzhou Huang
1 Tencent Al Lab
2 Beijing National Research Center for Information Science and Technology (BNRist), State Key Lab on Intelligent Technology and Systems, Department of Computer Science and Technology. Tsinghua University yu w.r.rooootmaaill com, hwenbing com cingyangxu@tencent com, jzhtangeuta.edu
ABSTRACT
Over-fitting and over-smoothing are two main obstacles of developing deep Graph Convolutional Networks (GCNs) for node classification. In particular, over-fitting weakens the generalization ability on small dataset, while over-smoothing impedes model training by isolating output representations from the input features with the increase in network depth. This paper proposes DropEdge, novel and flexible technique to alleviate both issues. At its core, DropEdge randomly removes a certain number of edges from the input graph at each training epoch, acting like a data augmenter and also message passing reducer. Furthermore, we theoretically demonstrate that DropEdge either reduces the convergence speed of over-smoothing or relieves the information loss caused by it. More importantly, our DropEdge is general skill that be equipped with many other backbone models (e.g. GCN, ResGCN, GraphSAGE, and JKNet) for enhanced performance. Extensive experiments several benchmarks verify that DropEdge consistently improves the performance on variety of both shallow and deep GCNs. The effect of DropEdge preventing over-smoothing is empirically visualized and validated well.
Codes are released on /estps://githnn com www.//roppddge//rooon.....
INTRODUCTION
Graph Convolutional Networks (GCNs), which exploit message passing or equivalently certain neigh- borhood aggregation function to extract high-level features from node as well as its neighborhoods. have boosted the state-of-the- oftthe-arss for variety of tasks on graphs, such as node classification (Bhagat et al. [011]] Zhang et al.) (2018), social recommendation (Freeman) (0000 Perozzi et al. (2044), and Kleinberg 2007) to name some. other words, GCNs have been becoming one of the most crucial tools for graph representation learning. Yet, when we revisit typical GCNs on node classification (Kipf & Welling 2017). they are usually shallow (e.g. the number the layers is 2 Inspired from the success of deep CNNs image classification, several attempts have been proposed to explore how to build deep GCNs towards node classification (Kipf' & Welling 2017] Li et al. 2018 Sa Xu al., 20188 Li et al., 2019); nevertheless,
link prediction (Liben-Nowar
of them delivers sufficiently expressive architecture. The motivation of this paper is to analyze the very factors that impede deeper GCNs perform promisingly, and develop method to address them.
We begin by investigating two factors: over-fitting and over-smoothing Over-fitting comes from the case when we utilize over-parametric model to fit distribution with limited training data, where the model we learn fits the training data very well but generalizes poorly to the testing data. does exist if we apply deep GCN on small graphs (see 4-layer GCN on Cora in Figure [ Over-smoothing, towards the other extreme, makes training a very deep GCN difficult. As first introduced by Li al.) (2018a) and further explained in Wu et al. (2019): Xu et al.) (20T8a): Klicpera al. 2011), graph convolutions essentially push representations of adjacent nodes mixed with each
"Wenbing Huang is the corresponding author.
'hhen counting the numher of layers (or network depth) of GCN, this paper does not involve the input layer.

---

Published as a conference paper at ICLR 2020
Training Loss
Validation Loss
1.75
GUN-8
BCN---DepEddg GCN- 4
GCN s
GUN-S-DiopEdge GCN-4
GUN- G-N---Di
1.25
GCN D-Drppldee
0.75
0.25
0.25
0
50
100
150
200
250
300
350
400
0
50
100
150
200
250
300
350
400
Epochs
Epochs
Figure 1: Performance of Multi-layer GCNs on Cora. We implement 4-layer GCN w and w/o DropEdge (in orange), 8-layer GCN w and w/o DropEdge (in blue GCN-4 gets stuck in the over-fitting issue attaining low training error but high validation error; the training of GCN-8 fails to converge satisfactorily due to over-smoothing. By applying DropEdge, both GCN-4 and GCN-8 work well for both training and validation.
other, such that, if extremely we go with an infinite number of layers, all nodes' representations will converge to a stationary point, making them unrelated to the input features and leading to vanishing gradients. We call this phenomenon as over-smoothing of node features. To illustrate its influence, we have conducted an example experiment with 8-layer GCN in Figure in which the training of such a deep GCN is observed to converge poorly.
Both of the above two issues can be alleviated, using the proposed method, DropEdge. The term "DropEdge" refers to randomly dropping out certain rate of edges of the input graph for each training time. There are several benefits in applying DropEdge for the GCN training (see the experimental improvements by DropEdge in Figure D]. First, DropEdge can be considered technique. By DropEdge, we are actually generating different random deformed copies of the original graph; as such, augment the randomness and the diversity of the input data, thus better capable of preventing aver-fitting. Second, DropEdge can also be treated as a message passing reducer. In GCNs, the message passing between adjacent nodes is conducted along edge paths. Removing certain edges is making node connections more sparse, and hence avoiding over-smoothing to some extent when GCN goes very deep. Indeed, we will draw theoretically in this paper, DropEdge either reduces the convergence speed of over-smoothing or relieves the information loss caused by it.
data augmentation
We are also aware that the dense connections employed by JKNet (Xu al. 2018a) are another kind of tools that can potentially prevent over-smoothing. In its formulation, JKNet densely connects each hidden layer to the top one, hence the feature mappings in lower layers that are hardly affected by over-smootinn weo-sinthhin are still maintained. Interestingly and promisingly, we find that the performance of JKNet can be promoted further if it utilized along with our DropEdge. Actually, our DropEdge- flexible and general technique able to enhance the performance of various popular backbone networks on several benchmarks, including GCN (Kipf & Welling 2017), ResGCN (Li et al. 2019)). JKNet (Xu et al. (2018)), and GraphSAGE (Hamilton et al. 2017) We provide detailed evaluations in the experiments.
RELATED WORK
Inspired by the huge success CNNs in computer vision, a large number of methods come redefining the notion of convolution graphs under the umbrella of GCNs. The first prominent research on GCNs is presented in Bruna et al. (2013), which develops graph convolution based on spectral graph theory. Later, Kipf & Welling 2017 Defferrard et al. (2016); Henaff et al. (2015): Li eet al. 2018b); Levie et al. (2017) apply improvements, extensions, and approximations on spectral- based GCNs. To address the scalability issue of spectral-based GCNs on large graphs, spatial-based
GCNs
GCNs have been rapidly developed (Hamilton et al. 2017 Monti et al. 2017 Niepert et al. 2016
"To check the efficacy of DropEdge more clearly, here have removed bias in all GCN layers, while for the experiments in $ (5] the bias are kept.
2

---

Published as a conference paper at ICLR 2020
Gao et al. 2018). These methods directly perform convolution in the graph domain by aggregating the information from neighbor nodes. Recently, several sampling-bast massed based methods have been proposed for fast graph representation learning, including the node-wise sampling methods (Hamilton et al. 2017), the layer-wise approach (Chen et al., 2018) and its layer-dependent variant (Huang et al. 2018). Specifically, GAT (Velickovic al. (018) has discussed applying dropout edge attentions. While it actually is a post-conducted version of DropEdge before attention computation, the relation to over-smoothing is never explored in Velickovic et al. (2018). In our paper, however, we have formally presented the formulation of DropEdge and provided rigorous theoretical justification of its benefit in alleviating over- wver-smothhing. We also carried out extensive experiments by imposing DropEdge on several popular backbones. One additional point is that we further conduct adjacency normalization after dropping edges, which, even simple, is able to make much easier to converge during training and reduce gradient vanish as the number of layers grows.
Deep GCNs Despite the fruitful progress, most previous works only focus shallow GCNs while the deeper extension is seldom discussed. The attempt for building deep GCNs is dated back to the GCN paper (Kipf & Welling 2017), where the residual mechanism is applied: unexpectedly, as shown in their experiments, residual GCNs still perform worse when the depth is 3 and beyond. The authors in Li et al.] (2018)) first point out the main difficulty in constructing deep networks lying in over-smoothing, but unfortunately, they never propose any method to address it. The follow-up study (Klicpera et al. 2019) solves over-smoothing by using personalized PageRank that additionally involves the rooted node into the message passing loop; however. the accuracy is still observed to decrease when the depth increases from 2. JKNet (Xu et al., (018a) employs dense connections for multi-hop message passing which is compatible with DropEdge for formulating deep GCNs. Oono & Suzuki (2019) theoretically prove that the node features of deep GCNs will converge to subspace and incur information loss. It generalizes the conclusion in [i ct al. (2018a) by further considering the ReLu function and convolution filters. Our interpretations on why DropEdge can impede over-smoothing is based on the concepts proposed by Oono & Suzuki (2019). A recent method (Li et al. 2019) has incorporated residual layers, dense connections and dilated convolutions into GCNs to facilitate the development of deep architectures. Nevertheless, this model is targeted on graph-level classification (i.e. point cloud segmentation), where the data points are graphs and naturally disconnected from each other. In our task for node classification, the samples are nodes and they all couple with each other, thus the over-smoothing issue is more demanded to be addressed. By leveraging DropEdge, we are able to relieve over-smoothing, and derive more enhanced deep GCNs on node classification.
NOTATIONS AND PRELIMINARIES
Notations. Let G = (V. represent the input graph of size N with nodes v, E V and edges (vi, vy) E E. The node features are denoted X {ar,.... ;.....aaa aNx E R and the adjacency matrix is defined as A E RNN which associates each edge (v,, U2) with its element A,j- The node degrees are given by d = [di.... , dy) } where dj computes the sum of edge weights connected to node We define D as the degree matrix whose diagonal elements are obtained from d.
GCN is originally developed by Kipf & Welling (017)) The feed forward propagation in GCN is recursively conducted as
H(+1) a (AHH
(1)
where (1+1) = (hl (1+1) h (1+1) feature for node i; À =
are the hidden vectors of the 1-th layer with h,) as the hidden D)D 1/2 1-122 is the re-normalization of the adjacency matrix, and D is the corresponding degree matrix of A I; (-) is nonlinear function, Lee. the ReLu function; and ((() E IBCxx is the filter matrix in the [-th layer with C refers to the size of 1-th hidden layer. We denote one-layer GCN computed by Equation T as Graph Convolutional Layer (GCL) in what follows.
3

---

Published as a conference paper at ICLR 2020
4 OUR METHOD: DROPEDGE
This section first introduces the methodology of the DropEdge technique as well as its layer-wise variant where the adjacency matrix for each GCN layer is perturbed individually. We also explain how the proposed DropEdge can prevent over-fitting and over-smoothing in generic GCNs. Particularly for smor-smo,,,ing, we provide its mathematical definition and theoretical derivations on showing the benefits of DropEdge.
4.1 METHODOLOGY
At each training epoch, the DropEdge technique drops certain rate of edges of the input graph by random. Formally, randomly enforces Vp non-zero elements of the adjacency matrix A to be zeros, where V is the total number of edges and is the dropping rate. If we denote the resulting adjacency matrix as Adop. then its relation with A becomes
Adrop
A',
where A' is sparse matrix expanded by random subset of size Vp from original edges &. Following the idea of Kipf & Welling (217)) we also perform the re-normalization trick on Adrop- leading to Arro- We replace A with Arop in Equation for propagation and training. When validation and testing, Dro is not utilized.
Preventing over-fitting, DropEdge produces varying perturbations of the graph connections. As a result, generates different random deformations the input data and can be regarded as data augmentation skill for graphs. To explain why this is valid, provide an intuitive understanding here. The key in GCNs is to aggregate neighbors' information for each node, which can be understood weighted sum of the neighbor features (the weights are associated with the edges). From the perspective of neighbor aggregation, DropEdge enables a random subset aggregation instead of the full aggregation during GNN training. Statistically, DropEdge only changes the expectation of the neighbor aggregation up to a multiplier p. if we drop edges with probability p. This multiplier will be actually removed after weights normalization, which is often the case in practice. Therefore, DropE- dge does not change the expectation of neighbor aggregation and is an unbiased data augmentation technique for GNN training, similar to typical image augmentation skills (e.g. rotation, cropping and flapping) that are capable of hindering ever-fitting in training CNNs. We will provide experimental validations 5.1
Layer- Wise DropEdge. The above formulation of DropEdge is one-shot with all layers sharing the same perturbed adjacency matrix. Indeed, we can perform DropEdge for each individual layer. Specifically, we obtain A by independently computing Equation 2 for each I-th layer. Different layer could have different adjacency matrix A drop' Such layer-wise version brings in more randomness and deformations of the original data, and we will experimentally compare its performance with the original DropEdge 5.2
Over- wvrrshmothing is another obstacle of training deep GCNs. and we will detail how DropEdge can address it to some extent in the next section. For simplicity, the following derivations assume all GCLs share the same perturbed adjacency matrix, and we will leave the discussion on layer-wise DropEdge for future exploration.
4.2 TOWARDS PREVENTING EVER-SMOOTHEE
By its original definition in Li et al. 20188), the over-smoothing phenomenon implies that the node features will converge to a fixed point as the network depth increases. This unwanted convergence restricts the output of deep GCNs to be only relevant the graph topology but independent to the input node features, which as a matter of course incurs detriment the expressive power of GCNs. Oono & Suzuki (2019) has generalized the idea in Li et al. (2018a) by taking both the -ineericyy (i.e. the ReLu function) and the convolution filters into account; they explain over- smoothing as convergence subspace rather than convergence to a fixed point. This paper will use the concept of subspace by Oono & Suzuki 2019) for more generality.
We first provide several relevant definitions that facilitate our later presentations.
4

---

Published as a conference paper at ICLR 2020
Definition 1 (subspace). Ler M (ECIC RRCICCRMxx) be M-dimensional subspace in R NxC, where E IP NxNx is orthogonal, i.c. E IM, and M S N.
Definition (e-smoothing), We call the e-smoothing of node features happens for GCN, if all its hidden vectors H beyond certain layer have a distance larger than (e >> 0) with respect to a subspace M that is independent to the input features, namely,
()(H()) < <,,
where d-(() computes the distance between the input matrix and the subspace MD
Definition 3 (the e-smoothing layer), Given the subspace M and e, call the minimal value of the layers that satisfy Equation 3 as the e-smoothing layer, that is, 1" (M,c) mine(d < <c).
Since conducting analysis exactly based on the e-smoothing layer is difficult, we instead define the relaxed e-smoothing layer which is proved to be upper bound of l"
Definition 4 (the relaxed e-smoothing layer). Given the subspace M and c, we call i(M,c)
(X))) as the relaxed smoothing layer, where, [-] computes the ceil of the input, is the log ax
supremum of the filters' singular values over all layers, and X is the second largest eigenvalue of A. Besides, we have
According to the conclusions by the authors in Oono & Suzuki (2019), a sufficiently deep GCN will certainly suffer from the e-smoothing issue for any small value of under some mild conditions (the details are included in the supplementary material). Note that they only prove the existence of e-smoothing in deep GCN without developing any method to address it.
Here, we will demonstrate that adopting DropEdge alleviates the e-smoothing issue in two aspects: 1. By reducing node connections, DropEdge is proved to slow down the convergence of over-smoothing; in other words, the value of the relaxed e-smoothing layer will only increase if using DropEdge. 2. The gap between the dimensions of the original space and the converging subspace, i.e. N M measures the amount of information loss; larger gap means more severe information loss. As shown by our derivations, DropEdge is able increase the dimension of the converging subspace, thus capable of reducing information loss.
We summarize our conclusions as follows.
Theorem 1. We denote the original graph as G and the one after dropping certain edges out as G'. Given a small value of e, we assume G and G' will encounter the e-smoothing issue with regard to subspaces M and M', respectively. Then, either of the following inequalities holds after sufficient edges removed.
The relaxed smoothing layer only increases: i(M,c) S i(Misc);
The information loss is decreased: N - dim( N - dim()
The proof of Theorem T based on the derivations in Oono & Suzuki (2019) as well as the concept of mixing time that has been studied in the random walk theory (Lovász al.] 1993). We provide the full details in the supplementary material. Theorem tells that DropEdge either reduces the convergence speed of over-smoothing or relieves the information loss caused by In this way, DropEdge enables us to train deep GCNs more effectively.
4.3 DISCUSSIONS
This sections contrasts the difference between DropEdge and other related concepts including Dropout, DropNode, and Graph Sparsification.
DropEdge vs. Dropout The Dropout trick (Hinton et al., 2012) is trying to perturb the feature matrix by randomly setting feature dimensions to be zeros, which may reduce the effect of over-fitting but of no help to preventing over-smoothing since it does not make any change the adjacency
"The definition of (-v(-) ) is provided in the supplementary material. All detailed definitions and proofs provided in the appendix.
5

---

Published as a conference paper at ICLR 2020
matrix. As reference, DropEdge can be regarded generation of Dropout from dropping feature dimensions to dropping edges, which mitigates both over- ver-fitting and over-smoothing fact, the impacts of Dropout and DropEdge complementary each other, and their compatibility will be shown in the experiments.
DropEdge vs. DropNode Another related vein belongs to the kind of node sampling based methods, including GraphSAGE (Hamilton et al., 2017), FastGCN (Chen et al.) 2018), and AS- GCN (Huang al., 2018). We name this category of approaches as Drop.Node. For original motivation, DropNode samples sub-graphs for mini-batch training, and it can also be treated as specific form of dropping edges since the edges connected to the dropping nodes are also removed. However, the effect of DropNode on dropping edges is node-oriented and indirect. By contrast, DropEdge is edge-oriented, and it is possible to preserve all node features for the training (if they can be fitted into the memory once), exhibiting more flexibility. Further, to maintain desired performance, the sampling strategies in current DropNode methods are usually inefficient, for example, GraphSAGE suffering from the aooonenialll-ggooiinn layer size, and AS AS-GCN requiring the sampling to be conducted recursively layer by layer. Our DropEdge, however, neither increases the layer size as the depth grows nor demands the recursive progress because the sampling of all edges are parallel.
(Eppstein al. 1997> is an old re- search topic in the graph domain. Its optimization goal is removing unnecessary edges for graph compressing while keeping almost all information of the input graph. This clearly district to the purpose of DropEdge where optimization objective is needed. Specifically, DropEdge will remove the edges of the input graph by random at each training time, whereas Sraaph-Sparsifiattie resorts to tedious optimization method to determine which edges to be deleted, and once those edges are discarded the output graph keeps unchanged.
DropEdge vs. Graph-Sparsification
5 EXPERIMENTS
Joining the previous works' practice, we focus on four benchmark datasets varying in graph size and feature type: (1) classifying the research topic of papers in three citation datasets: Cora, Citeseer and Pubmed (Sen et al.] 2008); (2) predicting which community different posts belong to in the Reddit social network (Hamilton et al. 2017). Note that the tasks in Cora, Citeseer and Pubmed are transductive underlying all node features are accessible during training, while the task in Reddit is inductive meaning the testing nodes are unseen for training. We apply the full-supervised training fashion used in Huang et al. (2018) and Chen et al. (2018) on all datasets in our experiments. The statics of all datasets are listed in the supplemental materials.
Datasets
5.1 CAN DROPEDGE GENERALLY IMPROVE THE PERFORMANCE OF DEEP GCNs?
In this section, we are interested in if applying DropFigee can promote the performance of current. popular GCNs (cspecially their deep architectures) on node classification.
Implementations We consider five backbones: GCN (Kipf & Welling 2017). ResGCN (He et al. 2016, Li et al., 2019), JKNNtt Xu et al. 2018a), IncepGCN and GraphS (Hamilton et al. 2017 with varying depth from 2 to 64 Since different structure exhibits different training dynamics on different dataset, to enable more robust comparisons, we perform random each model, and report the case giving the best accuracy on validation set of each benchmark. The searching space of dlyper-parametee material. Regarding the same architecture w or w/o DropEdge, we apply the same set of hyper- parameters except the drop rate for fair evaluation.
search for
and more details are provided in Table 4 in the supplementary
Overall Results Table D summaries the results on all datasets. We only report the performance of the model with 2/8/32 layers here due to the space limit, and provide the accuracy under other different depths in the supplementary material. It's observed that DropEdge consistently improves the
'The formulation is given in the appendix. 'For Reddit, the maximum depth 32 considering the memory bottlencck.

---

Published as a conference paper at ICLR 2020
Table 1: Testing accuracy (%) comparisons on different backbones w and w/o DropEdge.
2 layers
layers
32 layers
Dataset
Backbone
Orignal 86.10
DropEdge 86.50
Orignal
DropEdge
Orignal
DropEdge
GCN
78.70
85.80
71.60
74.60
ResGCN
85,40
86.90
85.10
86.80
Cora
JKNett
86. 70
87
87.10
87.60
IncepGCN
86.70
88.20
87.40
87.70
GraphSAGE
87.80
88.10
84.30
87.10
31.90
32.20
GCN
75.90
78.70
74.60
77.20
59.20
61,40
ResGCN
77.80
78.80
74.40
77.90
Citeseer
JKNet
79.20
80.20
71.70
80.00
IncepGCN
79.60
80.50
72.60
80.30
GraphSAGE
78.40
80.00
74.10
77.10
37.00
53.60
GCN
90.20
91.20
90.10
90.90
84.60
86.20
ResGCN
89.60
90.50
90.20
91.10
Pubmed
JKNet
90.60
91.20
89.20
91.30
IncepGCN
90.20
91.50
OOM
90.50
GraphSAGE
90.10
90.70
90.20
91.70
41.30
47.90
GCN
96.11
96.13
96.17
96,48
45.55
50.51
ResGCN
96.37
96.46
93.93
94.27
Reddit
JKNet
96,82
97.02
OOM
OOM
IncepGCN
96.43
96.87
OOM
OOM
GraphSAGE
96.22
96.28
96.38
96.42
96.43
96.47
testing accuracy for all cases. The improvement is more clearly depicted in Figure where we have computed the average absolute improvement over all backbones by DropEdge on each dataset under different numbers of layers. On Citeseer, for example, DropEdge yields further improvement for deeper architecture; it gains 0.9% average improvement for the model with 2 layers while achieving remarkable 13.5% increase for the model with 64 layers. addition, the validation losses of all 4-layer models on Cora are shown in Figure 2b The curves along the training epoch are dramatically pulled down after applying DropEdge. which also explains the effect of DropEdge on alleviating over-fitting. Another valuable observation in Table that the 32-layer IncepGCN without DropEdge incurs the Out-Of-Memory (OOM) issue while the model with DropEdge survives, showing the advantage of DropEdge to save memory consuming by making the adjacency matrix sparse.
Comparison with SOTAs We select the best performance for each backbone with DropEdge, and contrast them with existing State the Arts (SOTA), including GCN, FasIGCN, AS-GCN and GraphSAGE in Table 2 for the SOTA methods, have these findings: (1) Clearly, , our DropEdge obtains significant enhancement against SOTAs; particularly Reddit, the best accuracy by method is 97.02%, and it is better than the previous best by AS-GCN (96.27%) which is regarded as a remarkable boost considering the challenge on this benchmark. (2) For
reuse the results reported in Huang et al. (201)).
models with DropEdge, the best accuracy is obtained under the depth beyond 2, which again verifies the impact of DropEdge on formulating deep networks. (3) As mentioned in 4.33 FastGCN, AS-GCN and GraphSAGE are considered the DropNode extensions of GCNs. The DropEdge based approaches outperform the DropNode based variants as shown in Table 2 which somehow confirms the effectiveness of DropEdge. Actually, employing DropEdge upon the DropNode methods further delivers promising enhancement, which can be checked by revisiting the increase by DropEdge for GraphSAGE Table
5.2 How DOES DROPEDGE HELP?
This section continues more in-depth analysis DropEdge and attempts to figure out why it works. Due to the space limit, we only provide the results on Cora, and defer the evaluations on other datasets to the supplementary material.
Note that this section mainly focuses on analyzing DropEdge and its variants, without the concern with pushing fatte-of-the-alt results. So, do not perform delicate hyper-parameter selection. We employ GCN as the backbone in this section. Here, GCN-n denotes GCN depth n. The hidden dimension, learning rate and weight decay are fixed to 256, 0.005 and 0.0005, receptively. The
7

---

Published as a conference paper at ICLR 2020
Cora
16%
1.2
14%
layees
4 layers
1.1
OCN4
12%
32 layers
layers
61 lapers
16 lapers
Validation Lass
1.0
10%
0.9
Degpldge
8%
0.9
RNNe- (Drgglidg
6%
0.7
4%
0.5
0.5
044
25
50
100
125
150
175
200
Cora
Citeseer
Pubmed
Reddit
Epoch
(a) The average absolute improvement by DropEdge.
(b) The validation loss different
backbones w and w/o DropEdge.
Figure 2
Table 2: Accuracy (%) comparisons with SOTAs. The number in parenthesis denotes the network depth for the models with DropEdge.
Transductive Citescer
Inductive Reddit
Cora
Pubmed
GCN
86.64
79.34
90.22
95.68
FastGCN
85.00
77.60
88.00
93.70
ASGCN
87.44
79.66
90.60
96.27
GraphSAGE
82.20
71.40
87.10
94.32
GCN+DropEdge
87.60(4)
79.20(4)
91.30(()
96.71(4)
ResGCN+DrooEEdge
87.00(4)
79.40(16)
91.10(32)
96.48(16)
JKNeetDDopEEdge
88.00(16)
80.20(8)
91.60(64)
97.02(8)
IncepGCN+Droopdgge
88.20(8)
80.50(8)
91.60(4)
96,87(8)
GraphSAGGE+roppddge
88.10(4)
80.00(2)
91.70(8)
96.54(4)
random seed is fixed. We train all models with 200 epochs. Unless otherwise mentioned, we do not utilize the "witthlopp" and "withbn" operation (see their definitions in Table 4 in the appendix).
5.2.1 ON PREVENTING OVER- SMOOTHING
As discussed in $ 4.2 the over-smoothing issue exists when the top-layer outputs of GCN converge subspace and become unrelated to the input features with the increase in depth. Since we are unable to derive the converging subspace explicitly, we measure the degree of over-smoothing by instead computing the difference between the output of the current layer and that of the previous one. We adopt the Euclidean distance for the difference computation. Lower distance means more serious over-smoothing. Experiments are conducted on GCN-8.
Figure (a) shows the distances of different intermediate layers (from to 6) under different edge dropping rates (0 and 0.8). Clearly, over-smoothing becomes more serious in GCN as the layer grows, which is consistent with our conjecture. Conversely, the model with DropEdge (p 0.8) reveals higher distance and slower convergent speed than that without DropEdge (p = 0), implying the importance of DropEdge alleviating over-smoothing. We also interested in how the over- smoothing will act after training. For this purpose, we display the results after 150-epoch training in Figure 3 (b). For GCN without DropEdge, the difference between outputs of the 5-th and 6-th layers is equal to O, indicating that the hidden features have converged to a certain stationary point. On the contrary, GCN with DropEdge performs promisingly, as the distance does vanish to zero when
(a) Before Training
(b) After Training
Training Loss
10
Distance
10
10
1.8
GCNip-0) GCNip-0.8 8)
1.4
GCNip-00 GCNip-0.3 0.8)
10
GCNip 0)
GCNIp 0.31
Layer
Layer
Epoch
Figure 3: Analysis on over-smoothing. Smaller distance means more serious over-smoothing.
8

---

Published as a conference paper at ICLR 2020
Cora
Cora
1.4
1.6
GCN-4 (No Erge Dropout)
GCN-4 (No DropEdge, No Dropout)
Thain & Validation Loss
1.4
DDN--D Validation
GDn--edg Train
Validation Loos
1.2
GCN-4 EDropEdge, Dropout)
GCN-4 (DropEdge, No Dropout)
1.2
GUN 4-mpbele (LikTrm
GCN-4DmpEAge Validatioo
2.0
1.0
0.8
0.6-
0.4
0.2
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Epoch
Epoch
(a) Dropout vs DropEdge on Cora.
(b) Comparison between DropEdge and layer-wise
(LW) DropEdge.
Figure 4
the number of layers grows; it probably has successfully learned meaningful node representations after training, which could also be validated by the training loss in Figure (c).
5.2.2 ON COMPATIBILITY WITH DROPOUT
4.3 has discussed the difference between DropEdge and Dropout. Hence, we conduct an ablation study on GCN-4, and the validation losses are demonstrated in Figure 4a It reads that while both Dropout and DropEdge are able to facilitate the training of GCN, the improvement by DropEdge more significant, and if we adopt them concurrently, the loss decreased further, indicating the compatibility of DropEdge with Dropout.
5.2.3 ON LAYER- WISE DROPEDGE
[4.] has descried the Layer- Wise (LW) extension of DropEdge. Here, provide the experimental evaluation on assessing its effect. As observed from Figure 4b the LW DropEdge achieves lower training loss than the original version, whereas the validation value between two models is comparable. implies that LW DropEdge can facilitate the training further than original DropEdge. However, we prefer use DropEdge other than the LW variant as only avoid the risk of over-fitting but also reduces computational complexity since LW DropEdge demands to sample each layer and spends more time.
CONCLUSION
We have presented DropEdge, a novel and efficient technique to facilitate the development of deep Graph Convolutional Networks (GCNs). By dropping out certain rate of edges by random, DropEdge includes more diversity into the input data to prevent ever-fitting and reduces message passing in graph convolution alleviate over-smoothing. Considerable experiments on Cora, Citeseer, Pubmed and Reddit have verified that DropEdge can generally and consistently promote the performance of current popular GCNs, such as GCN, ResGCN, JKNet, IncepGCN, and GraphSAGE. is expected that our research will open up new venue on more in-depth exploration of deep GCNs for broader potential applications.
ACKNOWLEDGEMENT
This research was funded by National Science and Technology Major Project of the Ministry of Science and Technology of China (No. 2018AAA0102900), Finally, Yu Rong wants to thank, in particular, the invaluable love and support from Yunman Huang over the years. Will you marry me?
REFERENCES
Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classification social networks, In Social network data analytics, pp. 115-148. Springer, 2011.

---

Published as a conference paper at ICLR 2020
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In Proceedings of International Conference on Learning Represen- tations, 2013.
Jie Chen, Tengfei Ma, and Cao Xiao, Fastgen: Fast learning with graph convolutional networks importance sampling. In Proceedings of the 6th International Conference on Leurning Represenla- lions, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pp. 3844-38525 2016.
David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig. Sparsification- technique for speeding up dynamic graph algorithms. Journal of the ACM (JACM), 44(5):669-666, 1997.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 6530 6539,
2017.
Linton C Freeman. Visualizing social networks. Journal of social structure, 1(1):4 2000.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks, In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424. ACM, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems, pp. 1025-1033 1035, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint 150.0055060533333 2015.
Geoffrey E Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R Salakhutdinov. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.05800 2012.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700-4708, 2017.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances Neural Information Processing Systems, pp. 4558 4567, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph
neural networks meet personalized pagerank. In Proceedings of the 7th International Conference Learming Representations, 2019.
Ron Levie, Federico Monti, Xavier Bresson, and Michael Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 67(1):97-109, 2017.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In International Conference on Computer Vision, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirly-Second AAAI Conference Artificial Intelligence, 2018a.
10

---

Published as a conference paper at ICLR 2020
Ruoyu Li, Sheng Wang. Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018b.
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019-1011, 2007.
László Lovász et Random walks on graphs: A survey. Combinatorics, Paul erdos is eighty, 2(1): 1-46, 1993.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cmns. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 5115-5124, 2017.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Kenta Oono and Taiji Suzuki. On asymptotic behaviors of graph enns from dynamical systems perspective. arXiv preprint arXiv:1903 10947, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vetioo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93, 2008.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818 182286,, 2016.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Minjie Wang. Lingfn Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang, Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning graphs. ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. URL https: /oss://arxivve http://awxxxv...//....eoe/
org. al9p:////////99....../ 01315
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.005900 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, 201 8a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint 1xXiv:8806.0338 2018b.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
11

---

Published as a conference paper at ICLR 2020
A APPENDIX: PROOF OF THEOREM
To prove Theorem 1, we need to borrow the following definitions and corollaries from Oono & Suzuki (2019). First, denote the maximum singular value of W by 8 and set sup,EN, 8t- initialized so that 1. Second, denote the distance that
We assume that Wi of all layers induced as the Frobenius norm from X to M by (X) == infy X YIIF. Then, we recall
Corollary 3 and Proposition I in Oono & Suzuki (2019) Corollary below.
Corollary 1. Let X S.... AN be the eigenvalues of Á, sorted ascending order. Suppose the multiplicity of the largest eigenvalue AN is M(S N), i.e. AN-M < AN--++1 Ax and the second largest eigenvalue defined as
N-M max
PAl < LAN|.
(4)
n=l
Let E to the eigenspuce associated with - .. AN. Then we have An = 1, and
dM(H S s(dd
(5)
where M (ECIC E RMICJ. Besides, s1\ 1, implying that the output the 1-th layer of GCN on G exponentially approaches M.
We also need to adopt some concepts from Lovász al. (1993) in proving Theorem 1. Consider the graph G as an electrical network, where each edge represents unit resistance. Then the effective resistance, Rst from node to node is defined as the total resistance between node s and t. According to Corollary 3.3 and Theorem 4.1 (i) in Lovász al, (1993), can build the connection between À and Rst for each connected component via commute time as the following inequality.
1
2
(6)
Rug
d,
de
Prior to proving Theorem first derive the lemma below.
Lemma 2. The 6-smoothing happens whenever the layer number satisfies
log (x)
121=
log(sA)
where [.] computes the ceil of the input. It means > l.
Proof. We start our proof from Inequality [ leading to
dM(H ()) s (H
st (
< st
When reaches c-smoothing, the following inequality should be satisfied as
d (H (1) < (' <E,
3 llo sA < log dx)
(8)
Since S sA < 1, then log s\ < 0. Therefore, the Inequality g becomes
log TM(X]
1>
(9)
log S\
Clearly, we have i > 1" since 1* is defined as the minimal layer that satisfies e-smoothing. The proof concluded.
Now, we prove Theorem 1
12

---

Published as a conference paper at ICLR 2020
Proof. Our proof relies basically on the connection between À and R. in Equation 6 Corollary 4.3 in Lovász et al. (193) that removing any edge from G can only increase any Rst- then according to (6), the lower bound of À only increases if the removing edge is not connected to either 8 or t (i.e. the degree d, and de keep unchanged). Since there must exist a node pair satisfying Rit oc after sufficient edges (except self-loops)
We recall
removed from connected component of G. we have the infinite case À = 1 given in Equation 6 that both 1/d, and 1/d, are consistently bounded by finite number,i.e. 1. It implies À does increase before it reaches X = 1. As i is positively related (see the right side of Equation
where (og(s>) <0), we have proved the first part of Theorem 1, i.e., E( < l(M', e) after removing sufficient edges.
When there happens Ru: = xc, the connected component is disconnected into two parts, which leads to the increment of the dimension of M by I and proves the second part of Theorem 1. i.e., the information loss decreased: N dim(M) N dim(M').
13

---

Published as a conference paper at ICLR 2020
B APPENDIX: MORE DETAILS IN EXPERIMENTS
B.1
DATASETS STATISTICS
Datasets
The statistics of all datasets summarized in Table
Table 3: Dataset Statistics
Datasets
Nodes
Edges
Classes
Features
Traing/Validation/Testigg
Type
Cora 2,708
5,429
7
1,433
1,208/500/1,
Transductive
Citescer
3,327
4,732
6
3,703
1,812/500/1,
Transductive
Pubmed
19,717
44.338
3
500
18,217/500/1,00
Transductive
Reddit
232,965
11,606.919
41
602
152.410023.69//553344
Inductive
B.2 MODELS AND BACKBONES
Backbones Other than the multi-layer GCN, we replace the CNN layer with graph convolution layer to implement three popular backbones recasted from image classification. They are residual network (ResGCN)(He et al. 2016; Li et al., 2219)) inception network (InepGCCN((Szeeely et al. 2016) and dense network (JKNet) (Huang et al. 2017 Xu et al. 20T8b). Figure shows detailed architectures of four backbones. Furthermore, we employ one input GCL and one output GCL on these four backbones. Therefore, the layers in ResGCN, JKNet and InceptGCN are at least layers. All backbones are implemented in Pytorch (Paszke et al. 2017). For GraphSAGE, we utilize the Pytorch version implemented by DGL Wang et al. 2019).
Outqut
Output
Aggresttoon
Aggesspionn
GCL
GCL
GCL
GCL
OCL
GCL
GCL
CCL
GCL
GCL
OCL
Input
Input.
Imput
Input
(e) GCN
[c)]KNeet
(d) InayGON
Figure 5: The illustration of four backbones. GCL indicates graph convolutional layer.
Self Feature Modeling We also implement a variant of graph convolution layer with self feature modeling (Fout 2017
H (1+1) (ÀH w H w
(10)
where w(O)) self E RCxCi-1
Hyper-parameter Optimization We adopt the Adam optimizer for model training. To ensure the re-productivity of the results, the seeds of the random numbers of all experiments are set to the same. fix the number training epoch to 400 for datasets. All experiments are conducted on NVIDIA Tesla P40 GPU with 24GB memory.
Given a model with n E (2, 16, 16,32, 64) layers, the hidden dimension is and we conduct random search strategy to optimize the other dlyper-paamee for each backbone in $ $5.. The de- cryptions of
are summarized in Table Table the types the normalized adjacency matrix that selectable in the "normalization" aggregation type like GCN, MAX, MEAN, or LSTM is hyper-paramedd For GraphSAGE, the
as well.
For each model, try 200 different hlper-paramen combinations via random search and select the best test accuracy as the result. Table 6 summaries the paramereesss of each backbone with the best accuracy different datasets and their best accuracy reported in Table 2
14

---

Published as a conference paper at ICLR 2020
B.3
THE VALIDATION LOss ON DIFFERENT BACKBONES AND W/O DROPEDGE.
Figure 6 depicts the additional results of validation loss on different backbones w and w/o DropEdge.
Cora
Citeseer
Citeseor
CCNie
OCNid
Teappticn
Validation Loss
Validatioo Less
Validetion Loss
0.9
ReditNN Drsplidae
CCNie Drg oge
1.8
RerDCh l'boppidgee
OCh legg
0.
HKNe -i Dvep
1.4
IKNd Doge
144
HCNi de S-rbo
0.7
0.5
1.2
0.5
04
25
30
50
75
100
125
150
175
200
25
50
100
125
Epoch
Epoch
Epoch
Figure The validation loss on different backbones w and wo DropEdge. GCN-n denotes PlainGCN of depth similar denotation follows for other backbones.
B.4 THE ABLATION STUDY ON CITESEER
Figure 7a shows the ablation study of Dropout vs. DropEdge and Figure 4b depicts a comparison between the proposed DropEdge and the layer-wise DropEdge Citeseer.
Citeseer
Citeseer
2.0
1.5
1.8
GCN-4 (No DropEdge. Dropout)
GCN- (No Drop No Dropout)
Train Validution Loss
1.5
GCN DmdgeeeeTTeeeeTeee
Bdgge
Validation Loss
GCN-4 EdropEdge, No Dropout)
1.4
GCN-4- Didppedge Validatioo
1.6
GCN-4 Edge, Dropout)
1.2
0.4
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Epech
Epoch
(a) Ablation study of Dropout DropEdge on Citeseer.
(b) Performance comparison of layer-wise DropE-
dge.
Figure
Table 4: Hlper-parameter Description
Description
learning rate
weight-decay sampling sampling-percent dropout
L2 regulation weight
edge preserving percent (1
dropout rate
normalization
propagation models (Kipf Welling 2017
withloop
using self feature modeling
withbn
using batch normalization
15

---

Published as a conference paper at ICLR 2020
Table 5: The normalization / propagation models
Description
Notation
A
First-order GCN
FisstOrderGCN
T+ A+D"1/ AD
Augmented Normalized Adjacency
AugNormAdj
(D+ [D+1)=1/(A++ (AD 1
Augmented Normalized Adjaccacy with Self-loop
BingGeNorrAAj
Augmented Random Walk
AupRWalk
(D+I)"(A+))
Table 6: The hyper-parameters of best accuracy for each backbone all datasets.
Dataset
Backhone
nlayers
Acc.
Hyper-parameters
GCN
0.876
Ir:0.010, veeght-decay:5e-3, sampling-pereee percent:077. dropout:0.8, nor-
malization.FirstOrderrGCC
ResGCN
4
0.87
lr:0.001, weight-dcccyyyy.lee-..
sampling-percennt.. prrprreentt....ddooo........ dropout:0.55 nor-
malizatioonFFrsstrderrCCCC
Cora
JKNet
16
0.88
1r:0.088, worghh-ddcay.-f-44,
samp://-4-..apppgggeeee.-2..222 p dropout:0.8,
malizatioon:AugNNrmAAd.
IncepGCN
8
0.882
Ir:0.010, weight-decay:le-33
dropout:0.5,
normalization AugNormAA
GraphSage
4
0.881
Ir:0:000, weight-decay::ee
1oappling-pereeet0.444 dropout:0.5, ag-
gregator:mean
GCN
4
0.792
Ir:0.009, weight-decay:le-3, cumpling-percenttO..e dropout:0.8,
BimnliizationBBngeeNoonnn withloop, withbn
ResGCN
16
0.794
Ir:0.001, weight- decay:5e-3, sampling petping..ereee....... dropout: nor- withloop
BanizaaionnBingGeeommm
Citeseer
JKNet
0.802
Ir:0.004, weight-decay:5e-- sampling-perrent:0066 dropout:0..3. nor-
malization:Aug AormAAdd withloop
IncepGCNN
8
0.805
lr:0:002, wwwrghht-eecy::----- sampling- dropout:0.5, nor-
malization.BingGeeomm... withloop
GraphSage
0r:0001, wwwght-decay...eeee.. le-4. campling-percentten dropout:0.5, ag-
gregator:mean
GCN
4
0.913
lr:0.010, weight-decay:lee3, sampling-pereenttle dropout:0.5, nor- withloop, withbn
ResGCN
32
0.911
lr:0.033, weight--eccay:---- sampling--errentt... dropout:0..... nor-
MulizationnAAuNormmAAA. withloop. withbn
Pubmed
JKNet
64
0.916
lr:0:005, wewght decay:le-4 sampling-peree Pereent::.... dropout:0.8, nor-
malizatiion.AugNooAAAOA. withloop. withbn
IncepGCN
0.916
Ir:0.002, wewght- decay: sampling-pereente pereent:0.55 dropout:0.8, nor-
Bingae NormAdj. withloop, withbn
GraphSage
8
0.917
lr:0.007, weight-decay:l pttp://daaaaa.....aaaaaaaneerree sampling-percentt..s dropout:0.3, ag-
gregator:mean
GCN
0.9671
lr:00005, weight-decay: samplinng-eereentt.... dropout:O.5,
malizationnAAgRRall. withloop
ResGCN
16
0.9648
Ir:0.009, wrrgght-decayless. sampling-perrcen:00222 dropout:0.55 nor-
malization:
withbn
Reddit
JKNet
8
0.9702
Ir:0.010, decay:5e-5, campling-pereenttO.. dropout:0.5, nor-
malization: Mallization:BinGeeMeee NermAAdi withloop, withbn
IncepGCN
8
0.9687
Ir:0.008, deight-decay: le-4, sampling-percent:// dropout:0.3, nor-
malization: FirstOrdorGCN, withbn lr:0.005, ceight-decay:5-55 campling-percenttn dropout:0.3, ag-
GraphSAGE
4
0.9654
gregator.mean
16

---

Published as a conference paper at ICLR 2020
DropEdge
53.20
84.80
87.90 7.900
88.20
31.90
45.60
75.30
80.00
79.90
25.10
79.00
90.20
91.60
90.00
62.30
Origgal
2.00
31 .00
21 $1.20
76.70
79.00
16.90
79.70
87.90
90.60
0OM
40.70
79
86.
85
44.
Drop DropEdge
74.60
86.80
87.60
87.70
32.20
61.40
77.90
80.00
80.30
53.60
86.20
91.10
91.30
90.50
47.90
50.51
94.27
00M
0OM
96.47
32
Table 7: Accuracy (%) comparisons different backbones with and without DropEdge
Orignal
71.60
85. 1..10
87.10
87.40
31.90 .0
59,20
74.40
71.70
72.60
37.00
84.60
90 10
89 20
00M
41.30
45.55
93.93
00M
0OM
96.43
DropEdge
84.30
86 90
88.00
87.70
84.50
76.80
79.40
80.10
80.20
74.50
90.30
91.00
91.50
91.30
87.80
90.54
96.48
96.78
OOM
96. 18
16
Orignal
82.10
85 530
86.20
87.10
84.10
65.20
78.20
78.80
88.00
72.90
88.10
89.60
89.90
90.80
83.50
67.11
96.34
OOM
OOM
96.15
DropEdge
85. .08
87 7.80
88.20
87.10
77.20
78.80 80
80.20
80.50
77.10
90.90
90.50
91.20
91.50
91.70
96.48
96.46
97.02
96.8 96.87
96.42
Orignal
78.70
85,40
86.70
86.70
84.30
74.60
77.80
79.20
79.60
74.10
90.10
89.60
90.60
90.20
90.20
96.17
96.37
96.82
96.43
96.38
87 7.00
87.7 87.70
87 77
88. 10
79.20
80.20
79.90
79.20
91.30
90.70
91.30
91.60
91.20
96.71
96.33
96.75
96.77
96.54
Drop
87.
78
Orignal
83.50
86,00
86.90
85.60
87.10
76.70
78.90
79.10
79.50
77.30
88.70
90.70
90.50
89.90
89.40
96.62
96.13
96.54
96.48
96.45
DropEdge
86.50
88. 10
80.00
91.20
90.70
96.13
96.28
78.70
2
Orignal 86.10
87.80
75,90
78.40
90,20
96.11
96.22
Backbone
IncepGCN GraphSAGE
IncepGCN
GraphSAGE
IncepGCN
GraphSAGE
IncepGON
GraphSAGE
ResGON
ResGCN
ResGCN
ResGCN
JKNet
JKNet
JKNet
JKNet
GCN
GCN
GCN
GCN
Dataset
Cora
Citeseer
Pubmed
Reddit
17


Reviews:
[{"review_id": "ryl-3sBhcH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a simple but effective strategy that aims to alleviate not only overfitting, but also feature degradation (oversmoothing) in deep graph convolutional networks (GCNs).  Inspired by dropout in traditional MLPs and convnets, the authors clearly motivate their contribution in terms of alleviating both overfitting and oversmoothing, which are problems established both in previous literature as well as validated empirically by the authors. Ultimately, the authors provide solid empirical evidence that, while a bit heuristic, their method is effective at alleviating at least partially the issues of overfitting and oversmoothing.\n\nI vote weak-accept in light of convincing empirical results, some theoretical exploration of the method's properties, but limited novelty.\n\nPros:\nSimple, intuitive method\nDraws from existing literature relating to dropout-like methods\nLittle computational overhead\nSolid experimental justification\nSome theoretical support for the method\nCons:\nMethod is somewhat heuristic\nMitigates, rather than solves, the issue of oversmoothing\nLimited novelty (straightforward extension of dropout to graphs edges)\nUnclear why dropping edges is \"valid\" augmentation\n\nFollowup-questions/areas for improving score:\n\nIt would be nice to have a principled way of choosing the dropout proportion; 0.8 is chosen somewhat arbitrarily by the authors (presumably because it generally performed well). There is at least a nice interpretation of choosing 0.5 for the dropout proportion in regular dropout (maximum regularization).\n\nAs brought up in the comments, edges to drop out to the graph's properties is an interesting direction to explore. While the authors state that they would like to keep the method simple and general, the method is ultimately devised as an adaptation of dropout to graphs, so exploiting graph-specific properties seems reasonable and a potential avenue to further improving performance. \n\np2: \"First, DropEdge can be considered as a data augmentation technique\" Why are these augmentations valid; why should the output of the network be invariant to these augmentations? I would like to see some justification for why the proposed random modification of the graph structure is valid; intuitively, it seems like it might make the learning problem impossible in some cases.\n\nDeeper analysis of the (more interesting, I think) layer-independent regime would be nice. (As a side-note, the name \"layer-independent\" for this regime is a bit confusing, as the edges dropped out *do* depend on the layer here, whereas in the \"layer dependent\" regime, edges dropped out do *not* depend on the layer).\n\nComments:\nFigure 1 could probably be re-organized to better highlight the comparison between GCNs with and without DropEdge; consolidating the content into 2 figures instead of 4 might be more easily parsable. Adding figure-specific captions and defining the x axis would also be nice.\n\nUse \"reduce\" in place of \"retard\"\np2 \" With contending the scalability\" improve phrasing\np2 \"By recent,\" -> \"Recently,\"\np2 \"difficulty on\" -> \"difficulty in\"\np2 \" deep networks lying\" -> \"deep networks lies\"\np3 \"which is a generation of the conclusion\" improve phrasing\np3 \" disconnected between\" -> \"disconnected from\"\np4 \"adjacent matrix\" -> \"adjacency matrix\"\np4 \"severer \" -> \"more severe\"\np5 \"but has no help\" -> \"but is no help\"\np5 \"no touch to the adjacency matrix\" -> improve phrasing\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rJlykwUUcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied the problem of \"deep\" GCNs where the goal is to develop training methods that can make GCN becomes deeper while maintaining good test accuracy.  The authors proposed a new method called \"DropEdge\", where they randomly drop out the edges of the input graphs and demonstrate in experiments that this technique can indeed boost up the testing accuracy of deep GCN compared to other baselines. \n\nThis paper is clearly well-written and the authors conducted a comprehensive study on deep GCNs. I also like the discussion in sec 4.3 where the authors explicitly clarify what are the difference between DropEdge, Dropout and DropNode, as the other two are the methods that will pop up during reading this paper. The extensive experiment results also show that for deeper GCNs, DropEdge always win over other baselines (see Tab 1) despite most of them are marginal except the backbone being GraphSAGE on Citeseer. Can you explain why this is the case? Why other backbones seem to have similar performance  even with DropEdge (i.e. most of the accuracy increase are less than 3 %). \n\nQuestion:\n1.  When looking at Tab 1, it looks like most of the time, 2-layers networks are already the best (or close to the best) and are clearly better than 32 layers. Therefore, this makes me wonder: why do we need deeper networks at all if the shallow networks can already achieve a good (almost best) performance and it is also much similar and efficient in training? Can you please clarify why do we care to train a deeper network at all under this scenario? Are there any reasons that we would like to use deeper network as opposed to shallower networks?\n\n2. It is less clear to me regarding this sentence: \"DropEdge either retards the convergence speed of over-smoothing or relieves the information loss caused by it\" \n\nOverall, I think this paper presents an interesting study on making deeper GCNs comparable to shallow network performance, but since the the boosted performance doesn't really outperform most of the 2-layer networks,  I would like to hear the justification of why we need the deeper networks for this node classification task. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eC_r5atS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a simple and interesting strategy, DropEdge, to alleviate the over-fitting and over-smoothing in GCN. The logic is simple and clear and the paper is well-written. \n\nMajor concerns:\n1. After randomly enforce a certain rate of edges to be zero, how to preserve properties in the original complex network, such as degree power-law distribution, communities? If it was not necessary to preserve the properties, then what information should be preserved from the original graph.\n2. Randomly drop edges may result in disconnected components, how to handle disconnected components?\n3. Why do the authors use dimension difference as the measure to quantitatively evaluate information loss in Thm 1. More dimension reduction does not mean more information loss.\n4. As a follow-up concern for C1, graph sparsification makes more sense than DropEdge because it has clear information reserve targets while there is no target for the randomness in DropEdge.\n5. In Table 1 and Fig 2, why the improvements for more layers are bigger than those of the fewer layers?\n6. In Fig 2, why the trend of Reddit dataset is so different from others (the more layers the more improvements by applying DropEdge)? \n7. In Table 2, why there are the DropEdge versions for some methods while not for some other methods (e.g., FastGCN, ASGCN)? Why there is no result of GAT?\n\nMinor:\n1. Sec 3, \"notation\", \"\\mathbf{x}_n\" -> \"\\mathbf{x}_N\"\n2. Eq (1), \"\\mathbf{h}_n^{(l+1)}\" -> \"\\mathbf{x}_N^{(l+1)}\"\n3. What's C_l in the explaination under Eq(1)?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a very simple but thoroughly evaluated and investigated idea for improving generalization in GCNs. Though the reviews are mixed, and in the post-rebuttal discussion the two negative reviewers stuck to their ratings, the area chair feels that there are no strong grounds for rejection in the negative reviews. Accept.
Decision: Accept (Poster)