AdaGCN: Adaboosting Graph Convolutional Networks into Deep Models
Authors: Ke Sun
Zhanxing Zhu
Zhouchen Lin
Venue: ICLR 2021 Poster (2021)
Keywords: Graph Neural Networks
AdaBoost

Abstract: The design of deep graph models still remains to be investigated and the crucial part is how to explore and exploit the knowledge from different hops of neighbors in an efficient way. In this paper, we propose a novel RNN-like deep graph neural network architecture by incorporating AdaBoost into the computation of network; and the proposed graph convolutional network called AdaGCN~(Adaboosting Graph Convolutional Network) has the ability to efficiently extract knowledge from high-order neighbors of current nodes and then integrates knowledge from different hops of neighbors into the network in an Adaboost way. Different from other graph neural networks that directly stack many graph convolution layers, AdaGCN shares the same base neural network architecture among all ``layers'' and is recursively optimized, which is similar to an RNN. Besides, We also theoretically established the connection between AdaGCN and existing graph convolutional methods, presenting the benefits of our proposal. Finally, extensive experiments demonstrate the consistent state-of-the-art prediction performance on graphs across different label rates and the computational advantage of our approach AdaGCN~\footnote{Code is available at \url{https://github.com/datake/AdaGCN}.}.

Published as a conference paper at ICLR 2021
ADAGCN: ADABOOSTING GRAPH CONVOLUTIONAL NETWORKS INTO DEEP MODELS
Ke Sun
Zhejjang Lab
Key Lab. of Machine Perception (MoE), School of EECS, Peking University ajksunke@pku. edu.ccduu...o cn
Zhanxing Zhu
Beijing Institute Big Data Research, Beijing, China zhanxing. zhuêpku en
Zhouchen Lin"
Key Lab. of Machine Perception (MoE), School of EECS, Peking University Pazhou Lab, Guangzhou, China z mlinepku. edu. cn
ABSTRACT
The design of deep graph models still remains to be investigated and the crucial part is how to explore and exploit the knowledge from different hops of neighbors an efficient way. In this paper, we propose novel RNN-like deep graph neu- ral network architecture by incorporating AdaBoost into the computation of net- work; and the proposed graph convolutional network called AdaGCN (Adaboost- ing Graph Convolutional Network) has the ability to efficiently extract knowledge from high-order neighbors of current nodes and then integrates knowledge from different hops of neighbors into the network in an Adaboost way. Different from other graph neural networks that directly stack many graph convolution layers, AdaGCN shares the same base neural network architecture among all "layers" and recursively optimized, which is similar to an RNN, Besides, We also theo- retically established the connection between AdaGCN and existing graph convo- lutional methods, presenting the benefits of our proposal. Finally, extensive ex- periments demonstrate the consistent state-of-the-art prediction performance on graphs across different label rates and the computational advantage of our ap- proach AdaGCN
INTRODUCTION
Recently, research related to learning graph structural data has gained considerable attention in
machine learning community. Graph neural networks (Gori et al.] [2005] Hamilton al.. 2017] Veličković et al. 2018), particularly graph convolutional networks (Kipf & Welling, 2017 Deffer- rard et al.) [2166] Bruna et al. 2014) have demonstrated their remarkable ability on node classifi- cation (Kipf & Welling 2017), link prediction (Zhu et al. 2016) and clustering tasks (Fortunato) 2010). Despite their enormous success, almost all of these models have shallow model architectures with only two three layers. The shallow design of GCN appears counterintuitive deep versions of these models, in principle, have access to more information, but perform worse. Oversmooth- ing (Li al. 2018) has been proposed explain why deep GCN fails, showing that by repeatedly applying Laplacian smoothing, GCN may mix the node features from different clusters and makes them indistinguishable. This also indicates that by stacking too many graph convolutional layers, the embedding of each node in GCN is inclined to converge to certain value (Li et al. 2018). mak- ing it harder for classification. These shallow model architectures restricted by oversmoothing issue
"Corresponding author.
"ooe is available at http:////ggttbbb..ooaaaaaaa/////

---

Published as a conference paper at ICLR 2021
limit their ability to extract the knowledge from high-order neighbors, i.e., features from remote hops of neighbors for current nodes. Therefore, it is crucial to design deep graph models such that high-order information can be aggregated in effective way for better predictions.
There are some works (Xu et al. 2018b; Liao et al. 2019, Kliepera et al. 2018 Li et al. 2019 Liu et al., (2200) that tried to address this issue partially, and the discussion
refer to Appendix A. By contrast, we argue that a key direction of constructing deep graph models lies in the efficient exploration and effective combination of information from different orders of neighbors. Due to the apparent sequential relationship between different orders of neighbors, it is a natural choice to incorporate boosting algorithm into the design of deep graph models. As an important realization of boosting theory, AdaBoost (Freund et al. (999) is extremely easy to implement and keeps competi- tive in terms of both practical performance and computational cost (Hastie et al.] 2009). Moreover, boosting theory has been used to analyze the success of ResNets in computer vision (Huang et al.) 2018) and AdaGAN (Tolstikhin et al.) (017) has already successfully incorporated boosting algo- rithm into the training of GAN (Goodfellow et al. 2014).
In this work, we focus on incorporating AdaBoost into the design of deep graph convolutional networks in non-trivial way. Firstly, in pursuit of the introduction of AdaBoost framework, we refine the type of graph convolutions and thus obtain a novel RNN-like GCN architecture called AdaGCN. Our approach efficiently extract knowledge from different orders of neighbors and then combine these information in an AdaBoost manner with iterative updating of the node weights. Also, compare AdaGCN with existing methods from the perspective of both architectural difference and feature representation power to show the benefits of our method. Finally, we conduct extensive experiments demonstrate the consistent state-of-the-art performance of our approach across different label rates and computational advantage over other alternatives.
2
OUR APPROACH: ADAGCN
2.1 ESTABLISHMENT OF ADAGCN
Consider undirected graph G E) with N nodes e; E V. edges (1), E E. A E NNN is the adjacency matrix with corresponding degree matrix Dū = Σ, Asy. In the vanilla GCN model (Kipf & Welling, 2017) for semi-supervised node classification, the graph embedding of nodes with two convolutional layers is formulated as:
(1) where Z E R is the final embedding matrix (output logits) of nodes before softmax and K the number of classes. X NCC denotes the feature matrix where C is the input dimension. Á か + Ä & where Ā = + and / is the degree matrix of Á. In addition, W(() RC the input-to-hidden weight matrix for hidden layer with Il feature maps and (1)) H is the hidden-to-output weight matrix.
Z Å ReLU(AXWOO) (W)
Our key motivation of constructing deep graph models is to efficiently explore information of high- order neighbors and then combine these messages from different orders of neighbors in an AdaBoost way. Nevertheless, if we naively extract information from high-order neighbors based on GCN, are faced with stacking / layers' parameter matrix W(0, i 0, ...,, costly in computation. Besides, Multi-Scale Deep Graph Convolutional Networks (Luan et al., 2019) also theoretically demonstrated that the output can only contain the stationary information of graph structure and loses all the local information in nodes for being smoothed if we simply deepen GCN. Intuitively, the desirable representation of node features does not necessarily need too many nonlinear transformation J applied on them. This is simply due to the fact that the feature of each node normally one-dimensional sparse vector rather than multi-dimensional data structures, e.g., images, that intuitively need deep convolution network to extract high-level representation for vision tasks. This insight has been empirically demonstrated in many recent works (Wu et al. 2019] Klicpera et al.] 2018 Xu et al.] 2018a), showing that a two-layer fully-connected neural networks is better choice in the implementation. Similarly, our AdaGCN also follows this direction by choosing an appropriate f in each layer rather than directly deepen GCN layers.
which is definitely
Thus, we propose to remove ReLU to avoid the expensive joint optimization of multiple parameter matrices. Similarly, Simplified Graph Convolution (SGC) (Wu et al. 2019) also adopted this prac-
2

---

Published as a conference paper at ICLR 2021
2
Z
zer
2z w²
g w
2 w
8 w
f
f
A?
((
A
fg
x
A1-1X
f0
Å
Å
A
1=2
1=3
1=
1=L
Figure The RNN-like architecture AdaGCN with each base classifier f0 sharing the same neural network architecture Sa. w and 0, denote node weights and parameters computed after the 1-th base classifier, respectively.
tice, arguing that nonlincarity between GCN layers is not crucial and the majority of the benefits arises from local weighting of neighboring features. Then the simplified graph convolution is:
A' (O)) w(- Å'XW,
where we collapse ( (1) (((1)) W and A' denotes Å to the 1-th power. In particular, one crucial impact of ReLU in GCN is to accelerate the convergence of matrix multiplication since the ReLU contraction mapping intuitively. Thus, the removal of ReLU operation could also alleviate the oversmoothing issue, i.e. slowering the convergence of node embedding to indistin- guishable ones (Li et al., 2018). Additionally, without ReLU this simplified graph convolution also able to avoid the aforementioned joint optimization over multiple parameter matrices, result- ing computational benefits. Nevertheless, we find that this type of stacked linear transformation from graph convolution has insufficient power in representing information of high-order neighbors, which is revealed in our experiment described Appendix|A. AA. Therefore, we propose to utilize an appropriate nonlinear function fa. e.g., two-layer cully-connected neural network, to replace the linear transformation W in Eq. 2 and enhance the representation ability of each base classifier in AdaGCN as follows:
= ='''')),
(3)
where ( represents the final embedding matrix (output logits before Softmax) after the 1-th base classifier in AdaGCN, This formulation also implies that the (-th base classifier in AdaGCN is ex- tracting knowledge from features of current nodes and their (-th hop of neighbors. Due the fact that the function of I-th base classifier in AdaGCN is similar to that of the 1-th layer in other tra- ditional GCN-based methods that directly stack many graph convolutional layers, we regard the whole part of 1-th base classifier the 1-th layers in AdaGCN. As for the realization of Multi-class AdaBoost, we apply SAMME (Stagewise Additive Modeling using a Multi-class Exponential loss function) algorithm (Hastic et al., 2009), natural and clean multi-class extension of the two-class AdaBoost adaptively combining weak classifiers.
As illustrated in Figure we apply base classifier f! to extract knowledge from current node feature and 1-th hop of neighbors by minimizing current weighted loss. Then we directly compute the weighted error rate err(!) and corresponding weight (1) of current base classifier r! as follows:
err
Σ i=1
TT C4 # 1( (o:))
W
1=1
1 - (1r(1)
( log
log K 1),
err(
where wi denotes the weight of i-th node and e; represents the category of current i-th node. To attain positive !)), only need err(")) 1/ K, i.e., the accuracy of each weak classifier
3

---

Published as a conference paper at ICLR 2021
should be better than random guess (Hastie al., 2009). This can be met easily to guarantee the weights to be updated in the right direction. Then we adjust nodes' weights by increasing weights on incorrectly classified ones:
Wi - We exp (
(a+ 10 (z:)) (o=))))))))))))))))))))))))))( ;i=
(5)
After re- re-normalizing the weights, we then compute A = A (A'X) to sequentially extract knowledge from /+1-th hop of neighbors in the following base classifier S (((+1) One crucial point of AdaGCN that different from traditional AdaBoost, we only define one fe. e.g. a two-layer fully connected neural network, which in practice is recursively optimized in each base classifier just similar to a recurrent neural network. This also indicates that the parameters from last base classifier leveraged as the initialization of next base classifier, which coincides with intuition that + 1-th hop of neighbors are directly connected from I-th hop of neighbors. The efficacy of this kind of layer-wise training has been similarly verified in (Belilovsky et al.) 2018) recently. Further, we combine the predictions from different orders of neighbors in an Adaboost way to obtain the final prediction X);
C(A,X) arg max Σ
a 18 (''
(6)
Finally, we obtain the concise form of AdaGCN in the following:
1'x = Á. (X-
z 100 (A'X)
Z AdaBoost )
Note that So is non-linear, rather than linear in SGC etu 2019), guarantee the representation power. As shown in Figure [ the architecture of AdaGCN is variant of RNN with synchronous sequence input and output. Although the same classifier architecture is adopted for rameters are different, which is different from vanilla RNN. We provide detailed description of the algorithm in Section 3
{()) their pa-
2.2 COMPARISON WITH EXISTING METHODS
Architectural Difference. As illustrated in Figure ! and 2 there an apparent differ-
ence among the architectures of GCN (Kipi Welling 2017). SGC (Wu et al. 2019).
GCN
Jumping Knowledge (JK) (Xu et al. 2018b)
SGC
and AdaGCN, Compared with these existing graph convolutional approaches that sequen- tially convey intermediate result ( to com- pute final prediction, our AdaGCN transmits weights of nodes w², aggregated features of different hops of neighbors A' x. More im- portantly, in AdaGCN the embedding ( is independent of the flow of computation the network and the sparse adjacent matrix Á also not directly involved in the computation of individual network because we compute
JK
Figure 2: Comparison of the graph model architec- tures. fa in JK network denotes aggregation layer with aggregation function such as concatena- tion or max pooling.
1(++1) X in advance and then feed it instead of Á into the classifier ((+1) thus yiclding signifi- cant computation reduction, which will be discussed further Section
Connection with PPNP and APPNP. We also established a strong connection between AdaGCN and previous state-of-ther of-the-rrt Personalized Propagation of Neural Predictions (PPNP) and Approxi- mate PPNP (APPNP) (Klicpera et al. 2018) method that leverages personalized pagerank to recon- struct graph convolutions in order to use information from a large and adjustable neighborhood. The analysis can be summarized in the following Proposition T Proof can refer to Appendix A.3
4

---

Published as a conference paper at ICLR 2021
Proposition 1. Suppose that is the teleport Let matrix sequence { be from the outpur of each layer I in AdaGCN, then PPNP is equivalent to the Exponential Moving Average (EMA) with exponentially decreasing factor Y { in sharing parameters version, and its approximate version APPNP can be viewed as the approximated form of EMA with a limited number of terms.
Proposition ! iillustrates that AdaGCN can be viewed as an adaptive form of APPNP, formulated as:
100 (A'X)
Z
(8)
Specifically, the first discrepancy between AdaGCN and APPNP lies in the adaptive coefficient (1) in AdaGCN determined by the error of 1-th base classifier f/²) rather than fixed exponentially decreased weights in APPNP. In addition, AdaGCN employs classifier f/² with different parameters to learn the embedding of different orders of neighbors, while APPNP shares these parameters in its form. We verified this benefit of our approach our experiments shown Section 4.2
Comparison with MixHop MixHop (Abu-EI-Haija et al. 2019) applied the similar way of graph convolution by repeatedly mixing feature representations of neighbors at various distance. Propo- sition proves that both AdaGCN and MixHop are able to represent feature differences among neighbors while previous GCNs- based methods cannot. Proof can refer to Appendix A.4 Recap the definition of general layer-wise Neighborhood Mixing (Abu-El-Haija et al. 2019) as follows:
Definition 1. General layer-wise Neighborhood Mixing: A graph convolution network has the abil- ity to represent the layer-wise neighborhood mixing if for any bo, by ..., bL, there exists an injective mapping f with setting of its parameters, such that the output of this graph convolution network can express the following formula:
L Σ bio (A'x) 1-
(9)
Proposition AdaGCNs defined by our proposed approach (Eq. equation are capable of repre- senting general layer-wise neighborhood mixing, i.e., can meet the Definition
Albeit the similarity, AdaGCN distinguishes from MixHop in many aspects. Firstly, MixHop con- catenates all outputs from each order of neighbors while we combines these predictions in an Ad- aboost way, which has theoretical generalization guarantee based on boosting theory [Hastie et al. (2009). Oono& & Suzuki 2020) have recently derived the optimization and generalization guarantees of multi-scale GNNs, serving as the theoretical backbone of AdaGCN, Meantime, MixHop allows full linear mixing of different orders of neighboring features, while AdaGCN utilizes different non- linear transformation (!)) among all layers, enjoying stronger expressive power.
3 ALGORITHM
In practice, we employ SAMMERR (Hastie et al.) 2009). the soft version of SAMME, in AdaGCN.
SAMME.R (R for Real) algorithm (Hastie al. 2009) leverages real-valued confidence- pre- dictions, i.e., weighted probability estimates, rather than predicted hard labels in SAMME, in the prediction combination, which has demonstrated better generalization and faster convergence than SAMME. We elaborate the final version of AdaGCN in Algorithm I We provide the analysis on the choice of model depth Appendix A.7 and then we elaborate the computational advantage of AdaGCN in the following.
Analysis of Computational Advantage. Due the similarity of graph convolution in Mix- Hop El-ujaa- et al.) 2019), AdaGCN also requires no additional memory computational complexity compared with previous GCN models. Meanwhile, our approach enjoys huge com- putational advantage compared with GCN-based models, e.g., PPNP and APPNP, stemming from excluding the additional computation involved in sparse tensors, such as the sparse tensor multipli- cation between A and other dense tensors, in the forward and backward propagation of the neural network. Specifically, there only L times sparse tensor operations for AdaGCN model with L layers, i.e., Å' X Á. (Á'-1X) X) for each layer 1. This operation in each layer yields dense tensor
5

---

Published as a conference paper at ICLR 2021
Algorithm 1 AdaGCN based on SAMMERR Algorithm
Input:
Features Matrix X, normalized adjacent matrix A, two-layer fully connected network fo, number layers L and number of classes K.
Output: Final combined prediction X)),
Initialize the node weights w; 1/n, i 1,2, ... n on training set, neighbors feature matrix ( X and classifier f/ ((-1)
2: for (= 0 do
3: Fit the graph convolutional classifier f/d on neighbor feature matrix X based on f (((-1) by
minimizing current weighted loss.
4: Obtain the weighted probability estimates (x)) for l/:: Pk (X = Softmax (fg
(1)
( (c k| xI == L....,
5: Compute the individual prediction A1 (x) for the current graph convolutional classifier f/"
1 (1) (X (K looghh ① (X(1)
K log p (x(0)
where k == 1,.... K. Adjust the node weights w, for each node 2; with label y training set:
6:
K
- w. exp
V, log (0) (a:) i = ,,...,?
K
Re-normalize all weights w;.
8: Update |+1 l+hp neighbor feature matrix {1+11)
x1++1) AX
9: end for
10: Combine all predictions h n/2 ($+11) for = 0,... L.
C(A.X) arg max
kk (X
(1
1=0
11: return Final combined prediction X).
B¹ = X'X for the i-th layer, which is then fed into the computation in two-layer fully-connected network, i.e., f8 (B') = ReLU(E' W()) Due to the fact that dense tensor B' has been com- puted in advance, there is other computation related to sparse tensors in the multiple forward and backward propagation procedures while training the neural network. By contrast, this multiple com- putation involved in sparse tensors in the GCN-based models, c.g., GCN: A ReLU W ) highly expensive. AdaGCN avoids these additional sparse tensor operations in the neural network and then attains huge computational efficiency. We demonstrate this viewpoint in the Section 4.3
EXPERIMENTS
Experimental Setup. We select five commonly used graphs: CiteSeer, Cora-MI. (Bojchevski & Günnemann, 2018 McCallum et al., 2000), PubMed (Sen et al. 2008). MS-Academic (Shchur ct aaall|201 2018) and Reddit. Dateset statistics are summarized in Table I. Recent graph neural networks suffer from overfitting to single splitting of training, validation and test datasets (Klicpera et al.) 2018). To address this problem, inspired by (Klicpera et al. a01)8) we test all approaches on multiple random splits and initialization conduct rigorous study. Detailed dataset splittings are provided in Appendix A.6
Dateset
Nodes
Edges
Classes
Features
Label Rate
CiteSeer
3,327
4,732
3,703
3.6%
Cora
2,708
5,429
7
1,433
5.2%
PubMed
19,717
44,338
3
500
0.3%
MS Academic
18,333
81.894
15
6,805
1.6%
Reddit
232,965
11,606,919
602
65.9%
Table 1: Dateset statistics

---

Published as a conference paper at ICLR 2021
Cora-ML
Citeseer
Pubmed
10
70
TV
Test Accuracy(%o
Test Accuracy
Test Accuracy
50
GCN
GUN
(CY(ResiOaa)
(CN(Red
GCN(Residaa)
SGC
SGC
SGC
AdsGGN
ABsGON
AdaGON
1 12
Layers
Layers
Layers
Figure 3:
Comparison of accuracy of different models as the layer increases. We regard the I-th base classifier as the 1-th layer in AdaGCN as both of them are leveraged to exploit the information from 1-th order of neighbors for current nodes.
Basic Setting of Baselines and AdaGCN. We compare AdaGCN with GCN Kipt & Welling
2017) and Simple Graph Convolution (SGC) (Wu al. 2019) in Figure 3 Table 2 we employ
the same baselines as (Klicpera et al.
2018): V.GCN (vanilla GCN) (Kipf & Welling 2017) and
GCN with our early stopping, N-GCN (network of GCN) Alu--ElHaija et al. 8a), GAT (Graph
Attention Networks) (Veličković et al.
2018), BT.FP (bootstrapped feature propagation) (Buchnik)
& Cohen 2018) and JK (jumping knowledge networks with concatenation) (Xu et al. (008b). In
the computation part, we additionally compare AdaGCN with FastGCN (Chen al., 2018) and GraphSAGE (Hamilton et al., 2017). We refer to the result of baselines from (Kliepera et 20188) and the implementation of AdaGCN is adapted from APPNP. For AdaGCN, after the line search on pareeeerrs,e,sss, we set h = 5000 hidden units for the first four datasets except academic with h 3000, and 15, 12, 20 and 5 layers respectively due to the different graph structures. In addition, we set dropout rate to 0 for Citeseer and Cora-MI. datasets and 0.2 for the other datasets and x 10-3 Lg regularization on the first linear layer. We weight decay as 1 10-3 for Citescer while 1 x 10 10-4 for others. More detailed model parameters and analysis about our early stopping mechanism can be referred from Appendix A.6
4.1 DESIGN OF DEEP GRAPH MODELS TO CIRCUMVENT OVERSMOOTHING EFFECT
It is well-known that GCN suffers from oversmoothing (Li al. 2018) with the stacking of more graph convolutions. However, combination of knowledge from each layer to design deep graph
Model
Citeseer
Cora-ML
Pubmed
MS Academic
V.GCN
73.51=0.48
82.30--0.34
77.65=0.40
91.65=0..99
GCN
75.40=0.30
83.41+0.39
78.68=0.38
92.10
N-GCN
74.25+0.40
82.25+0.30
77.43+0.42
92.86+0.11
GAT
75.39-0.27
84.3740.24
77.76=0.44
91.22:10.07
JK
73.03=0.47
82.69-H0.35
77.88=0.38
91.71=0.10
BT.FP
73.55+0.57
80.84++0.97
72.94+1.00
91.61+0.24
PENP
75.83=0.27
85.29-40.25
0OM
OOM
APPNP
75.73+0.30
85.09+0.25
79.73=0.31
93.27=00088
PPNP (ours)
75.53-10.32
84.3910.22
0OM
OOM
APPNP (ours)
75.41+0.355
24.28+0.28
79.41+0.34
92.98-00.07
AdaGCN
85.97
79.95
93.17
P value
1.8x10
2.2x10 16
1.110
2.1x10
Table 2: Average accuracy under 100 runs with uncertainties showing the 95 % confidence level calculated by bootstrapping. OOM denotes "out of memory". "(ours)" denotes the results based on implementation. which slight lower than numbers above from original literature (Klicpera ett al. 2018). P values of paired test between APPNP (ours) and AdaGCN are provided in the last row.
7

---

Published as a conference paper at ICLR 2021
Citeseer
Cora-MI.
Pubmed
MS Academic
Label Rates
1.0% / 2.0%
2.0% / 4.0%
0.1% 0.2%
0.6% 1.2%
V.GCN
67.6441477..8444
76,441./81.74088
70.1+1.4774.411666
0..-+0.49111-0.2
GCN
70.3:10.9/72.71.11
80.010.7782.:1009
7171211/7..21100
PPNP
72.5::..977..7.0077
80.110.7783.011.6
OOM
OOM
APPNP
72.2411..74.2+1.11
80.1+0.7/8..20.6
74.0-1.5/7.2+1.2 77.1-0.5/79.3--..3
91.7:0..292.6600.2 92.1:0.192..0011
AdaGCN
7422:003775550.33
837:00./85.3H0.2
Table 3: Average accuracy across different label rates with 20 splittings of datasets under 100 runs.
models is reasonable method to circumvent oversmoothing issue. In our experiment, we aim to explore the prediction performance of GCN, GCN with residual connection (Kipf Welling 2017).
SGC and our AdaGCN with growing number of layers.
From Figure 3] it can be easily observed that oversmoothing leads the rapid decreasing of accu- racy for GCN (blue line) as the layer increases. In contrast, the speed of smoothing (green line) of SGC is much slower than GCN due to the lack of ReLU analyzed in Section 2.T Similarly, GCN with residual connection (yellow line) partially mitigates the oversmoothing effect of original GCN but fails to take advantage of information from different orders of neighbors to improve the predic- tion performance constantly. Remarkably, AdaGCN (red line) is able to consistently enhance the performance with the increasing of layers across the three datasets. This implies that AdaGCN can efficiently incorporate knowledge from different orders of neighbors and circumvent oversmoothing of original GCN in the process of constructing deep graph models. In addition, the fluctuation of performance for AdaGCN is much lower than GCN especially when the number of layer large.
4.2 PREDICTION PERFORMANCE
We conduct rigorous study of AdaGCN four datasets under multiple splittings of dataset. The results from Table 2 suggest the state-of-the-ar performance of our approach and the improvement compared with APPNP validates the benefit of adaptive form for our AdaGCN. More rigorously, p values under paired test demonstrate the significance of improvement for our method.
In the realistic setting, graphs usually have different labeled nodes and thus necessary in- vestigate the robust performance of methods on different number of labeled nodes. Here we utilize label rates to measure the different numbers of labeled nodes and then sample corresponding labeled nodes per class graphs respectively. Table presents the consistent state-of-the-arr performance of AdaGCN under different label rates. An interesting manifestation from Table 3 that AdaGCN yields more improvement on fewer label rates compared with APPNP, showing more efficiency graphs with few labeled nodes. Inspired by the Layer Effect on graphs (Sun et al., 2019), we argue that the increase of layers in AdaGCN label signals especially on graphs with limited labeled nodes.
result in more benefits on the efficient propagation of
More rigorously, additionally conduct the comparison on a larger dataset, i.e., Reddit. We choose the best layer 4 due to the fact that AdaGCN with larger number of layers tends to suffer from overfitting on this relatively sim- ple dataset (with high label rate 65.9%). Ta- ble 4 suggests that AdaGCN can still outper- form other typical baselines, including V.GCN, PPNP and APPNP. More experimental details can be referred from Appendix A.6
Reddit V.GCN 94.46+0.06 PPNP
FI-Score
Per-epoch training time
6627.46ms
OOM
OOM
APPNP 95.04+00.07
29489.8 8 Ims
AdaGCN 95.3910.13
32.29ms
Table 4: Average Fl-scores and per-epoch train- ing time of typical methods on Reddit dataset un- der 5 runs.
4.3 COMPUTATIONAL EFFICIENCY
Without the additional computational cost involved in sparse tensors in the propagation of the neu- ral network, AdaGCN presents huge computational efficiency. From the left part of Figure 4 exhibits that AdaGCN has the fastest speed of per-epoch training time in comparison with other methods except the comparative performance with FastGCN in Pubmed. In addition, there a somewhat inconsistency in computation of FastGCN, with fastest speed in Pubmed but slower than
8

---

Published as a conference paper at ICLR 2021
Time
Time on Pubmed
GEN
GCC
50C
214
Time per spuch (ms)
A6GGNN
2-28.7
Time epoch
k-23.8
lc-0.1
Cleeerr
CareMt
Pabasil
Mo Acadenie
Layers
Figure 4: Left: Per-epoch training time of AdaGCN other methods under 5 runs four datasets. Right: Per-epoch training time of AdaGCN compared with GCN and SGC with the increasing of layers and the digit after "k =" denotes the slope fitted linear regression.
GCN on Cora-ML and MS-Academic datasets. Furthermore, with multiple power iterations in- volved in sparse tensors, APPNP unfortunately has relatively expensive computation cost. It should be noted that this computational advantage of AdaGCN is more significant when it comes to large datasets, e.g., Reddit. Table 4 demonstrates AdaGCN has the potential to perform much faster on larger datasets.
Besides, we explore the computational cost of ReLU and sparse adjacency tensor with respect to the number of layers in the right part Figure We focus on comparing AdaGCN with SGC and GCN as other GCN-based methods, such as GraphSAGE and APPNP, behave similarly with GCN. Partic- ularly, we can easily observe that both SGC (green line) and GCN (red line) show linear increasing tendency and GCN yields larger slope arises from ReLU and more parameters. For SGC, stack- ing more layers directly undesirable regarding the computation. Thus, a limited number of SGC layers is preferable with more advanced optimization techniques Wu et al. (2019). It also shows that the computational cost involved sparse matrices neural networks plays dominant role in all the cost especially when the layer is large enough. In contrast, AdaGCN (pink line) displays an almost constant trend as the layer increases simply because excludes the extra computation involved in sparse tensors Å, such as ... À ReLU(AXW (()) .,, in the process of training neural networks. AdaGCN maintains the updating of parameters in the f(") with fixed architecture in each layer while the layer-wise optimization, therefore displaying a nearly constant computation cost within each epoch although more epochs are normally needed in the entire layer-wise train- ing. We leave the analysis of exact time and memory complexity of AdaGCN as future works, but boosting-based algorithms including AdaGCN is memory-efficient (Oono Suzuki 2020).
DISCUSSIONS AND CONCLUSION
One potential concern is that AdaBoost (Hastie al. 2009 Freund et al. 1999) is established on i..d. hypothesis while graphs have inherent data dependent property. Fortunately, the statistical convergence and consistency of boosting (Lugosi & Vayatis 2001 Mannor et al. 2003) still be preserved when the samples are weakly dependent (Lozano et al. (0033). More discussion can refer to Appendix A.5 In this paper, we propose novel RNN-like deep graph neural network architecture called AdaGCNs. With the delicate architecture design, our approach AdaGCN can effectively explore and exploit knowledge from different orders of neighbors in an Adaboost way. Our work paves way towards better combining different-oris neighbors to design deep graph models rather than only stacking on specific type of graph convolution.
ACKNOWLEDGMENTT
Z. Lin is supported by NSF China (grant 61625301 and 61731018), Major Scientific Research Project of Zhejiang Lab (grant no.s 2019KB0ACOI and 2019KB0AB02), Beijing Academy of Arti- ficial Intelligence, and Qualcomm.

---

Published as a conference paper at ICLR 2021
REFERENCES
Sami Abu-El-uu-leeeee El-u-Ea-aaja,, Amol Kapoor, Bryan Perozzi, and Joonscok Lee. N-gen: Multi-scale graph con- volution for semi-supervised node classification, International Workshop on Mining and Learning with Graphs (MLG), 2018a. 8a.
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolution architectures via sparsified neighborhood mixing. International Conference on Machine Learning
(ICML), 2019.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. International Conference on Machine Learning (ICML), 2018.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsu- pervised inductive learning via ranking. International Conference on Learning Representations (ICLR), 2018.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. International Conference Learning Representations (ICLR), 2014.
Eliav Buchnik and Edith Cohen. Bootstrapped graph diffusions: Exposing the power of nonlinear- ity. In Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, pp. 8-10. ACM, 2018.
Peter Bühlmann and Bin Yu. Boosting with the 12 loss: regression and classification. Journal of the American Statistical Association, 98(462):324 339, 2003.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. International Conference Learning Representations (ICLR), 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 (NeurIPS), pp. 3844-3852, 2016.
Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5);75-174, 2010.
Yoav Freund, Robert Schapire, and Naoki Abe. short introduction boosting. Journal-Japanese Society For Artificial Intelligence, 14(771-780):1612, 1999.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems (NeurIPS), pp. 2672-2688 2014.
Marco Gori, Gabriele Monfardini, and Franco Scarselli, new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pp. 734. IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs In Advances in Neural Information Processing Systems (NeurIPS), pp. 1024-1034, 2017.
Trevor Hastie, Saharon Rosset, Ji Zhu, and Hui Zou. Multi-class adaboost. Statistics and Its Inter- face, 2(3):349 360, 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Furong Huang, Jordan Ash, John Langford, and Robert Schapire. Learning deep resnet blocks sequentially using boosting theory. International Conference on Machine Learming (ICML), 2018.
Wenxin Jiang et al. Process consistency for adaboost. The Annals of Statistics, 32(1): 2004.
10

---

Published as a conference paper at ICLR 2021
Ming Jin, Heng Chang, Wenwu Zhu, and Somayeh Sojoudi. Power up! robust graph convolutional network against evasion attacks based on graph powering. arXiv preprint arXiv:1905. 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Rep- resentations (ICLR), 2018.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Can gens go as deep as cnns? ICCV, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning, Association for the Advancement of Artificial Intelligence (AAAI), 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. International Conference on Learning Representations (ICLR), 2019.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 338 348, 2020.
Aurelie C Lozano, Sanjeev R Kulkarni, and Robert E Schapire. Convergence and consistency of regularized boosting with weakly dependent observations. IEEE Transactions Information Theory, 60(1)6551-660, 2013.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Gábor Lugosi and Nicolas Vayatis. On the bayes-risk consistency of boosting methods. 2001.
Shie Mannor, Ron Meir, and Tong Zhang. Greedy algorithms for
conver- gence rates, and adaptivity. Journal of Machine Learning Research, 4(0ct):713-742, 2003.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Advances Neural formation Processing Systems (NeurIPS), 2020.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. From graph low-rank global attention to 2-fwl approximation. ICML Workshop Graph Representation Learning and Beyond, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Ran Collective classification in network data. Al magazine, 29(3):93, 2008.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Relational Representation Learning Workshop 2011,2018), NeurlPS, 2018.
Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Multi-stage self-supervised learning for graph convolu- tional networks. Association for the Advancement of Artificial Intelligence (AAAI), 2019.
Ilya O Tolstikhin, Sylvain Gelly, Olivier Bousquet, Carl-Johann SabrnnGabriel, and Bernhard Schölkopf. Adagan: Boosting generative models. In Advances in Neural Information Processing Systems (NeurIPS), pp. 5424 5433, 2017.

---

Published as a conference paper at ICLR 2021
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. Interaational Conference on Learning Representations (ICLR), 2018.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. International Conference on Machine Learning (ICML), 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie
Jegelka. Representation learning on graphs with jumping knowledge networks. International Conference Machine Learning (ICML), 2018b.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations (ICLR), 2019.
Tong Zhang, Bin Yu, et Boosting with early stopping: Convergence and consistency. The Annals of Statistics, 33(4) 2005.
Jun Zhu, Jiaming Song, and Bei Chen. Max-margin nonparametric latent feature models for link prediction. arXiv preprint 170.07160,,074288 2016.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 RELATED WORKS ON DEEP GRAPH MODELS
A straightforward solution (Kipf & Welling 2017] Xu et al. 2018b) inspired by ResNets (He et al. (2016) was by adding residual connections, but this practice unsatisfactory both in prediction performance and putational efficiency towards building deep graph models, as shown in our experiments Section [4.1 and 4.3 More recently, JK (Jumping Knowledge Networks (Xu et al (0188)) introduced jumping connections into final aggregation mechanism in order to extract knowledge from different layers of graph convolutions. However, this straightforward change of GCN architecture exhibited inconsistent empirical performance for different ag- gregation operators, which cannot demonstrate the successful construction of deep layers. In addition, Graph powering-han -hanng method (Jin et al. 2019) implicitly leveraged more spatial information by extending classical spectral graph theory to robust graph theory, but they concentrated on defending adversarial attacks rather than model depth. LanczosNet (Liao et al. 2019) utilized Lanczos algorithm to construct low rank approximations of the graph Laplacian and then exploit multi-scale information. Moreover, APPNP (Approximate Per- sonalized Propagation of Neural Predictions, (Klicpera et al. 2018)) leveraged the relationship between GCN and personalized PageRank to derive an improved global propagation scheme. Beyond these, DeepGCNs (Li et al. (019) directly adapted residual, dense connection and dilated convolutions to GCN architecture, but it mainly focused the task of point cloud semantic segmentation and has not demonstrated its effectiveness in typical graph tasks. Similar to our work, Deep Adaptive Graph Neural Network (DAGNN) (Liu al.] 2020 also focused on incorporating information from large receptive fields through the entanglement tation transformation and propagation, while our work efficiently ensembles knowledge from large receptive fields in an Adaboost manner. Other related works based on global attention models (Puny et al. 2020) and sample- based methods (Zeng et al. 2019) also helpful construct deep graph models.
represen-
A.2 INSUFFICIENT REPRESENTATION POWER OF ADASGC
As illustrated in Figure 5 with the increasing of layers, AdaSGC with only linear transformation has insufficient representation power both in extracting knowledge from high-order neighbors and combining information from different orders of neighbors while AdaGCN exhibits consistent improvement of performance as the layer
increases.
Cora-ML
Citeseer
Pubmed
80
Test Accuracy (%)
Test Accuriey ccurrwyy (%
Test Accur 1 (%)
66
88
Ads8CC AdaGCN
ABSGC
Al&SCC AdsGCN
AdsCCN
Lavers
Lavers
Lavers
Figure 5: AdaSGC vs AdaGCN.
A.3 PROOF OF PROPOSITION 1
Firstly, we further elaborate the Proposition as follows, then we provide the proof.
Suppose that 7 is the teleport factor. Consider the output Zrene 7(I (1 - -)))))))())) in PPNP and Zappnp from its approxminated version APPNP. Let matrix sequence ( be from the output of each layer / in AdaGCN, then PPNP equivalent to the Exponential Moving Average (EMA) with exponentially decreasing factor 7, first-order infinite impulse response filter, on (2 in sharing parameters version, i.c., f!)) = fo- In addition, APPNP, which reformulate in Eq. 10 can he viewed the approximated form of EMA with
13

---

Published as a conference paper at ICLR 2021
limited number of terms.
ZARNN
(r Σ (1- +1 (1-0)) Lmu
(10)
Proof. According to Neumann Theorem, Zrane can be expanded as Neumann series:
Zpane 7 (1 fo(X)
7 (1-7)'''00X))
1=0
where fcature emhedding matrix sequence { for each order of neighhors share the same parameters fo- we relax this sharing nature to the adaptive form with respect to the layer and put A' into fo. then the output Z can be approximately formulated as:
7PpNP RS
-1 (a'x))
t=0
This relaxed version from PPNP is the Exponential Moving Average form of matrix sequence ( with exponential decreasing factor 7. Moreover, if we approximate the EMA by truncating it after items, then the weight omitted by stopping after items is (1 -) Thus, the approximated EMA exactly APPNP form:
L-1 AAPNN (7 (1- Ā' A0) 1=0
A.4 PROOF PROPOSITION 2
Proof. We consider a two layers fully-connected neural network as f in Eq. then the output of AdaGCN can he formulated as:
2 (A''
t=0
Particularly, we set (r())
and (())) sign(b:) II where sign(b:) is the signed incidence scalar
w.t.t by Then the output of AdaGCN can be presented as:
h sign(bi)a Dsign(bi))
o(''x)
b (b sign(br)
1=0
Σ bror (A'x)
1=0
The proof that -Csee methods are capable of representing general layer-wise neighborhood mixing has been demonstrated MixHop (Abu-El-Haipp al. 2019) Proposition 2 proved.
A.5 EXPLANATION ABOUT CONSISTENCY OF BOOSTING ON DEPENDENT DATA
Definition 2. (3-mixing sequences.) Let af o(W) oW,, Wi-1..., W3) be the a-field generated by
strictly stationary sequence of random variables W (W,, W W,). The 8-mixing coefficient defined by:
Bw (n) = =sup Esup {1r (Alot) P(A)| A ofin.
Then sequence W called 3-mixing lim Sw (n) a positive constant ra such that Bw (n) O(n
Further, algebraically 8-mixing there
Definition 3. (Consistency) classification rule is consistent for certain distribution E(L(h,))
(h, (X) = Y) - as - ao where is a constant. is strongly Bayes-risk consistent if lim L(ht)) = a almost surely.
Under these detinitions, the convergence and consistence of regularized boosting method on stationary 8- mixing sequences can he proved under mild assumptions. More details can be referred from (Lozano et al. 2013)
14

---

Published as a conference paper at ICLR 2021
A.6 EXPERIMENTAL DETAILS
Early Stopping on AdaGCN. We apply the same early stopping mechanism across all the methods as (Kliepera) ct al. 2018) for fair comparison. Furthermore, boosting theory also has the capacity to perfectly incorporate early stopping and it has been shown that for several boosting algorithms including AdaBoost, this regulariza-
tion via early stopping can provide guarantees of consistency (Zhang et al. 2005 Jiang et al. 2004 Bühlmann
Yo, 2003
Dataset Splitting, We choose a training set fixed nodes per class, an early stopping set 500 nodes and test set of remained nodes. Each experiment is run with 5 random initialization on each data split, leading to a total of 100 runs per experiment. On a standard setting, we randomly select 20 nodes per class. For the two different label rates on each graph, select 6, 11 nodes per class on citeseer, 8, 16 nodes per class on Cora-ML, 7, 14 nodes per class on Pubmed and 8, 15 nodes per class MS-Academic dataset.
approaches. we use same learning rate of 0.01, 0.5 dropout rate, 5 x 10 L2 regularization weight, and 16 hidden units. For FastGCN, we adopt the officially released code to conduct our experiments. PPNP and APPNP are adapted with best setting: K 10 power iteration steps for APPNP, teleport probability = 0.1 Cora-ML, Citeseer and layers with h 64 hidden units and apply L2 regularization with À = 5 10-3 on the weights the first layer and use dropout with dropout rate 0.5 on both layers and the adjacency matrix. The early stopping criterion uses a patience of p = 100 and an (unreachably high) maximum of n 10000 epochs.The implementation of AdaGCN is adapted from PPNP and APPNP. Corresponding patience 300 and n 500 in the early stopping of AdaGCN. Moreover, SGC re-implemented a straightforward way without incorporating advanced optimization for better illustration and comparison. Other baselines are adopted the same parameters described in PPNP and APPNP.
Model parameters. For
in the original paper:
Pubmed, 7 0.2 on Ms-Academic. In addition, we
Settings on Reddit datasct. By repeatedly tuning the parameters of these typical methods on Reddit, we finally choose weight decay rate as 10 hidden layer size 100 and epoch 20000 for AdaGCN, For APPNP, we opt weight decay rate 10-9, dropout rate 0 and epoch 500. V.GCN applies the same parameters in (Kipf Welling 2017) and we choose epoch as 500. All approaches have not deployed early stopping due to the expensive computational cost on the large Reddit dataset, which also a fair comparison.
A.7 CHOICE OF THE NUMBER OF LAYERS
Different from the "forcible" behaviors in CNNs that directly stack many convolution layers, in our AdaGCN there is a theoretical guidance on the choice of model depth L, i.c. the number of base classifiers or layers, derived from boosting theory. Specifically, according to the boosting theory, the increasing of L can expo- nentially decreases the empirical loss, however, from the perspective of VC-dimension, yield overfitting of AdaGCN. should be noted that the deeper graph convolution layers AdaGCN are not always better. which indeed heavily depends on the the complexity of data. In practice. L can be determined via vross-validation. Specifically, we start a VC-dimension- bbaed analysis to illustrate that too large L can yield overfitting of AdaGCN. For layers of AdaGCN, its hypothesis is
overly large L
L Σ Ea
FL
arg max
:a
1 ER,IE(1,
(11)
Then the VC-dimension of Fi can be bounded follows in terms of the VC-dimension d of the family of base hypothesis:
VCdim (Fr.) 2(d + 1)(L + lo,
(12)
where e is constant and the upper bounds grows as L increases. Combined with VC-dimension generalization bounds, these results imply that larger values of L can lead to overfitting of AdaBoost. This situation also happens in AdaGCN, which inspires us that there is no need to stack too many layers AdaGCN in order avoid overfitting. practice, L typically determined via cross- validation.
15


Reviews:
[{"review_id": "zvBJALHzCXw", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "By integrating Adaboosting and a fully connected layer, this paper provides a new graph neural network structure. The objective of this paper is to design a deeper graph models in an efficient way for better performance. The computational efficiency and performance of the proposed algorithm are evaluated using the task of node property prediction on several public datasets. This is a new variant of GNN, but the quality this paper is lower than the expectation regarding to the clarity and organisation. \n\nPros: \n1.\tThe algorithm integrated Adaboosting for graph data. Thus, AdaGCN could utilise different levels of node features for final prediction. \n2.\tThe method is optimised in a layer-wise way rather than the traditional GCN optimisation, which is similar to the optimisation of recurrent neural networks. \n3.\tAuthors compared the structure of AdaGCN with that of other GNN variants. \n4.\tFor the experiments, the proposed algorithm is more computationally efficient, and achieves better performance on the task of node property prediction.  The performance of AdaGCN is slightly more robust than previous methods. The performance drop is not observed within 10 layers for AdaGCN as shown in Fig 3. \n\nCons: \n1.\tSpeaking of the state of art performance, GraphSAGE with LSTM also achieves a 95.4% F1 score on the Reddit dataset for node classification tasks. Thus, the authors may need to compare the training time and performance with more recent algorithms, like ClusterGCN and GraphSAGE. \n2.\tThe paper is not well written. Many typos are discovered. For example, extra space is added in the first sentence after equation 3. Meanwhile, the punctuation around equations is not consistent. For the full sentence following an equation, one would place a full stop after the equation. However, there is no full stop after equations 5, 6, 7, and 8. Abbreviations, such as \"JK\", \"APPNP\", and \"PPNP\", are used before introduction. \n3.\tSome notations are confusing and misleading. $K$ refers to the number of node categories, and $k$ refers to a category of a node. Meanwhile, $w_i$ and $W^{l}$ have completely irrelevant definitions. \n4.\tTo evaluate the efficiency of different GCN approaches, the authors listed the per-epoch training time of methods. The implementation of GCN with different frameworks would result in the large variance of training time. It is better that the authors could include the time and memory complexity of each algorithm. \n5.\tFig 4, after 10 layers, it is not clear whether the linear trend would continue. This result is a bit misleading.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "mCzESxYkOse", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\nThis paper incorporates AdaBoost into the deep graph neural network architecture, which has the ability to efficiently extract knowledge from high-order neighbors and then integrates knowledge from different hops of neighbors into the network in an Adaboost way. It solves the problem of oversmoothing. Extensive experiments show the effectiveness of the proposed method. \n\n##########################################################################\n\nPro:\n+ The paper is clear and well organized.\n+ The introduction of AdaBoost into the deep GNN is novel and interesting.\n+ The comparison with several existing methods is well analyzed in terms of both model architectures and computational advantages. \n+ Extensive experiments are conducted to demonstrate the consistent state-of-the-art performance of the proposed method.\n\n##########################################################################\n\nCons:\n- Although the same classifier architecture is adopted for $f^{(l)}_\\theta$, their parameters are different, which is different from RNN. It is better to avoid this confusion.\n\n- It would be better to include some discussion of the global attention methods (e.g., [Puny et al., 2020] ) and sampling-based methods (e.g., [Zeng et al., 2020]).\n\nReferences: \nPuny et al. From Graph Low-Rank Global Attention to 2-FWL Approximation. ICML Workshop Graph Representation Learning and Beyond, 2020.\n\nZeng et al. Graph sampling-based inductive learning method. ICLR ’20, 2020.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "kKffE7JkQ9a", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall, the proposed AdaGCN model could incorporate the different hops of neighbors into the network in an Adaboost way without improving the computational cost. That has been confirmed by the theoretical comparison with other baselines and the experimental results.\n\nPros:\n[1] It proposed a novel deep graph neural network by incorporating AdaBoost into the computation of network.\n[2] It compared to the existing related work to illustrate the benefits of the proposed AdaGCN.\n[3] The experiments demonstrate its effectiveness of efficiency of AdaGCN on encoding the high-order graph structure information.\n\nCons:\n[1] The simplified graph convolution might be vulnerable to the noisy nodes. That is, when there exists one noisy node with abnormal attributes, this simplified graph convolution might be significantly degraded. Thus, the higher-order convolution in the proposed method might become worse.\n[2] In table 2, it is confusing why the implemented methods (e.g., PPNP (ours), APPNP (ours)) have lower performance than the results reported in the literature (Klicpera et al., 2018).\n[3] In Section 4.3, it shows that Fast-GCN has fastest speed in Pubmed, but slower than GCN on Cora-ML and MS-Academic datasets. That might need more explanation since intuitively the goal of Fast-GCN is to improve the efficiency of GCN.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PmccgXMlmUr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nIn this paper, the authors study graph convolutional networks, where they propose to use AdaBoost for Deep GCNs. This method makes it possible to use information from multi-hop neighbours. Computationally, the proposed method is efficient, which is illustrated through various experiments. The paper is well written with good clarity, while the proposed method is novel and significant to the research community. \n\nReasons for recommending acceptance\n- To that of reviewer's knowledge, the proposed scheme is novel. The method address the issue of using information for higher-order neighbours, without increasing the computational complexity. \n- comprehensive experiments across multiple datasets, evaluating AdaGCN in terms of computational efficiency, accuracy, dependency on the number of layers. \n\nQuestions\n- While comparing MixHop against AdaGCN, the authors mention that AdaGCN does have generalization guarantees from Boosting theory. This statement is loose, and a formal justification may be needed. \n- In Figure 4 (Right), where the epoch time is measured against the number of layers, AdaGCN is shown to have nearly constant time w.r.t. layers. Some more explanation would be useful in understanding this. \n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of the reviewers are very positive about this work, and R3 is slightly concerned about the datasets, writing, and notations etc. The authors responded to these concerns in detail and have agreed to take care of these comments. Thus an accept is recommended based on the understanding that the authors will fulfil their commitments.
Decision: Accept (Poster)