DEEP GRAPH TREE NETWORKS
Authors: Nan Wu
Chaofan Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: graph tree networks
graph tree convolution networks
graph tree attention networks
GNNs

Abstract: We propose Graph Tree Networks (GTree), a self-interpretive deep graph neural network architecture which originates from the tree representation of the graphs. In the tree representation, each node forms its own tree where the node itself is the root node and all its neighbors up to hop-k are the subnodes. Under the tree representation, the message propagates upward from the leaf nodes to the root node naturally and straightforwardly to update the root node's hidden features. This message passing (or neighborhood aggregation) scheme is essentially different from that in the vanilla GCN, GAT and many of their derivatives, and is demonstrated experimentally a superior message passing scheme. Models adopting this scheme has the capability of going deep. Two scalable graph learning models are proposed within this GTree network architecture - Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN), with demonstrated state-of-the-art performances on several benchmark datasets. The deep capability is also demonstrated for both models.

Under review as a conference paper at ICLR 2022
DEEP GRAPH TREE NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
We propose Graph Tree Networks (GTreeNets), a self-interpretive deep graph neural network architecture which originates from the tree representation of graphs. In the tree representation, each node forms its own tree where the node itself is the root node and all its neighbors up to k-hop are the subnodes. Un- der the tree representation, messages propagate upward from the leaf nodes to the root node naturally to update the root node's hidden features. This message pass- ing scheme, which has better interpretability, is essentially different from that in the vanilla Graph Convolution Network (GCN), Graph Attention Network (GAT) and many of their derivatives. Two scalable graph learning models are proposed within this GTreeNet architecture Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN), with experimentally demonstrated state-of-the--e performance on several benchmark datasets and the capability of going deep.
INTRODUCTION
Graph Neural Networks (GNNs), class of neural networks for learning graph structured data, have been successfully applied in many areas to solve real world problems, such as link predictions in social networks (Fan et al. 2019), pattern recognition (Ju al., 2020; Shi & Rajkumar 2020), product recommendation and personalized search in E-commerce (Zhu et al. 2019)). fraud detection (Wang al. 2019a Dou et al. 2020), protein interface predictions (Fout et al. (017)) power es- timation and tier design in the semiconductor industry (Zhang et al. 2020 Lu et al. 22020), traffic
forecasting YYu et al. 2017). and natural language processing (Yao al. 2019: Vashishth et al., 2020 Wu et al. 2021). Among many different graph learning approaches, the class of spatial graph convolution based models, which adopts a message passing scheme to update node features, has gained particular attention due to its simplicity yet good performance. The most representative work among this class is the Graph Convolutional Network (GCN) (Kipf & Welling (017) which limits the ChebNet (Defferrard et al. 2016) up to the 1st order polynomial, and together with some further approximation leading to a direct neighbor aggregation. The success of the GCN model (Ying et al.) 2018 Hu et al. 2020b) has led to the rapid development in spatial convolution based models, such as the Graph Attention Network (GAT) (Velickovic et al. (2018), GraphSage (Hamilton et al. 2017). APPNP (Klicpera al. 2018), DAGNN (Liu al. 2020), and etc.
Today the vanilla GCN and GAT are the two most popular baseline models. One GCN or GAT layer aggregates only the direct neighbor nodes. Although they work well in many test cases, their performance degrades as stacking multiple propagation layers to achieve larger receptive fields. Xu al. )2018) and Li et (2018) attribute such degradation in performance to over-smoothing effect that nodes from different classes become indistinguishable, while Liu et al. (2020) attributes that to the intertwined propagation and transformation. A small neighborhood may not provide enough information especially when nodes are sparsely labeled (Klicpera et al. 2018: Liu et al., 2020). Many recent work has been devoted to extending the size of neighborhood utilized in graph learning- APPNP (Klicpera et al. 2018) and DAGNN (Liu et al. (2200) are two most recent deep graph models with state-of-the-art performance on several popular benchmark datasets. APPNP (Kliepera et al.) 2018) is developed based on personalized PageRank to preserve local information which requires fine tuning of teleport probability. DAGNN (Liu et al.) 2020) aggregates neighbors from different hops in parallel (in one layer) to utilize information from larger receptive field compared to GCN. Although DAGNN has achieved state-of-the-arr performance, it may only be applicable to adopt simple aggregation function the one used in GCN. It could be computationally challenging

---

Under review as a conference paper at ICLR 2022
GNN models (such GAT, and graph transformer (Dwivedi & Bresson 2020 Hu et al. 2020c)); because this aggregation scheme requires computation of the attention weight for each pair of node and its k-hop neighbor, which could be a too large number. In the aggregation of k-hop neighborhood. the number of attention weights is the total number of non-zero entries in the kth power of the graph adjacency matrix A. Although the adjacency matrix is usually sparse, its kth power could be non-sparse especially for undirected graphs. For example, in the Cora dataset (Wang al. 2019b A has ~22 million non-zero entries while A has only ~10k non-zero entries. Furthermore, aggregating multi-hoy neighborhood in one step neglects path information which is usually important for heterogeneous graphs with rich metapath information (Fu et al., 2020; Wang et al., 2019c).
to combine such multi-hop aggregation scheme with
We propose Graph Tree Networks (GTreeNets), a self-interpretive deep graph neural network ar- chitecture which originates from the tree representation of graphs. In the tree representation, each node forms own tree where the node itself is the root node and all its neighbors up to k-hop are the subnodes. Under the tree representation, message propagates upward from the leaf nodes to the root node naturally to update the root node's s hidden features. This message passing scheme, which has better interpretability, is essentially different from that in the vanilla Graph Convolution Net- work (GCN), Graph Attention Network (GAT) and many of their derivatives. Two scalable graph learning models are proposed within this GTrreNett architecture Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN), with experimentally demonstrated state-of- the-art performance on several benchmark datasets and the capability of going deep by stacking multiple propagation layers. Our models do not require finely-tuned hyperparameter in the propa- gation scheme.
This work is structured as follows. Section 2 illustrates the architecture of our Graph Tree Networks (GTreeNets) and two derivative graph learning models Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN), along with the analysis of model complexity. Section 3 presents the experimental results including three parts: Section shows the performance test of our GTCN and GTAN models as compared to several popular and state-of-the-a GNN models on five benchmark datasets. Section shows the performance test for our GTCN and GTAN models at different depths compared to the vanilla GCN and GAT models. Section 3.3 discusses the effect of adding transformation in propagation layers in our GTCN and GTAN models. We conclude our work in Section 4 and discuss insights for future work.
2 OUR APPROACH: GRAPH TREE NETWORKS
We first introduce notations used throughout this paper. We follow the general convention to use bold uppercase and lowercase to represent matrices and vectors, respectively. The topology of a graph G (V, E) with nodes V and edges E can be fully described by its adjacency matrix A and degree matrix D. V = N and [E] M are the number of nodes and edges, respectively. Nu denotes the set of direct neighbors (I-hop neighbors) of node u. X E Nx represents the feature map for all nodes, where each row æ, E TR. represents the feature vector of node u with dimension of D. Y E R N represents the class matrix for all nodes, where each row yo represents the class vector of node with C' classes.
2.1 TREE REPRESENTATION AND NETWORK STRUCTURE
Tree is a straightforward representation for the graph topology, where each node and its neighbor- hood form one tree with the node itself being the root node and its neighbors being the subnodes. Figure Tinutrrrlltsssss the tree representation for node with up to 3-hop neighbors in the sample graph. We use a directed graph just for illustration, the tree representation also works for undirected graphs.
In Figure h E Rf is the vector of node u's output hidden features at k-hop away from the root node 1. The final output of the root node is denoted as h4. Messages propagate upward from subnodes to the root node hop by hop in the tree. Nodes may occur multiple times at the same level in the tree (like node 5 occurring twice at 2-hop as shown in Figure IT. each of them is from different k-hop path that may pass different messages to the root node. We assume a node u at any k-hop preserves its initial information prior receiving information from its child nodes. With this
2

---

Under review as a conference paper at ICLR 2022
output: h
X1
farget node: 1
X
1 1-hop neighbors: 2, 3,4
h4
N
x
X2
2
X
5
2-hop neighbors: 2, 2,
A
h:
1t
X3
A5
X4
X2
X5
3-hop 3-hop neighbors: 3, 5, 4, 2,
Figure 1: Sample of tree representation for node I (showing up 3-hop neighborhood). The input features of node u denoted as Lu. and the hidden features of the node u the 1!th hop of the root node is denoted as h
assumption, node's features are updated by aggregating its child nodes and its own initial features in the tree representation.
This tree representation of graphs leads to a new graph learning architecture Graph Tree Networks (GTreeNets) shown in Appendix A.I. with the general message passing rule formulated Equa- tion 1
where k L- h fu (aggregate (o (xx),, (h++1, the tree depth (number of propagation layers). Tx is the vector of input features of node u. Zu = ((x,) ) is the transformation of input features of node us i.e. the initial hidden features for the propagation layer. h is the vector of hidden features of node u at k-hop, and h Zu. fa(-) is hop-wise (layer-wise) transformation function such as MLP.
1e4H,,e Yu E NN,)))
(1)
Combination of different aggregation function and transformation function in Equation 1 derives various graph learning models under the GTreeNet architecture. We propose two graph tree mod- els Section 2.2 and 2.3 Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN),
2.1.1
RELATION TO PROPAGATION SCHEME IN GCN-LIKE MODELS
The general message passing rule in GCN-like models such as GCN (Kipf & Welling 2017), GAT VVelickovic et al.] 2018), and GraphSage (Hamilton al., 2017) is
h = fn-1 (aggregate (h"" n21 (h Ve E N.)))
(2)
Comparing to Equation I it is notable that the message passing scheme in our proposed GTreeNet is essentially different from the one adopted by the GCN-like models. In GTreeNet, we update node's hidden features by aggregating its neighbor's 's hidden features and its own initial features. While in GCN-like models, a node's ' hidden features are updated by aggregating its neighbor's hidden features and its own hidden features from the last propagation layer. Our propagation scheme preserves the local information when stacking multiple propagation layers while the propagation scheme GCN- like models does not. Note that use denote the propagation layer number in Equation 2 to avoid ambiguities.
2.2 GRAPH TREE CONVOLUTION NETWORK
The propagation rule of our proposed Graph Tree Convolution Network is
h E Au
1++1 + Áuu
(3)
where À 1ー AD is the symmetric normalized adjacency matrix Ā (A + I) is the adjacency matrix with added self-loops. D is the degree matrix with self-loops where Da... E, Aua. 2, MLP(2x.).
We find that using À D-1 À yields similar performance.
3

---

Under review as a conference paper at ICLR 2022
As compared to the general propagation rule in GTreeNet shown in Equation T GTCN model uses an MLP as the transformation function o(-), an identity function as (-). and a weighted sum function the aggregation function with weights being the clements of the normalized adjacency matrix.
The mathematical description of our GTCN model is then formulated as
Z MLP (X)
H Z
H = Ai H + A2Z, k -= 2, ,....,
You softmax (HOW)
where RNXF is the initial hidden feature map obtained by applying an MLP to the input feature map X. H* E RRX the hidden feature map at the kth hop. A₁ and Ag are the non-diagonal and diagonal component of the normalized adjacency matrix, respectively. W E RxC is the trainable weight matrix.
Note that our model separates the transformation from propagation with no trainable parameters required in the propagation layers. By aggregating a node's neighbor information with its own initial information, we always preserve the local information of node. These characteristics make our model capable of going deep without comprising performance as demonstrated in Section
3.2
2.2.1 RELATION TO GCN AND APPNP
GCN. The propagation rule in GCN is
h ReLU (E Auch. Aucha-l) w
which uses weighted sum to aggregate the hidden features node u and its neighbors from the last propagation layer, and an MLP with ReLU activation function as f--1(-) transform the feature representation.
Except for the different information used in aggregation discussed in Section 2.1.1 another ma- jor difference between our GTCN model and the GCN model is that transformation function is applied after each propagation layer in GCN which causes intertwined propagation and transforma- tion, and introduces more trainable parameters. These differences make the GCN model subject to compromised performance when stacking multiple propagation layers.
APPNP. The propagation rule in APPNP is
h" = (1 a1 (E
h + Amnhh" h. + OzZu
which uses weighted sum to aggregate the hidden features node u and its neighbors from the last propagation layer, as well as its initial hidden feature. Note that the APPNP also adopts an identity function as fa-1(-), i.e. no transformation is applied after propagation.
APPNP uses the hidden features of node from the last propagation layer (hz-1) in aggregation to update its hidden feature while our GTCN model does not. addition, APPNP introduces a teleport probability adjust the influence from the neighborhood which requires fine tuning for different graphs.
Note that the APPNP model can be derived from our GTreeNet by adding self-loops in the graph. Therefore, node u is also a child node of itself when building the tree representation. In this case, the general propagation rule in the resulting tree representation becomes:
h fx (aggregate (o (æw) h {h k+1 Ve NN.))
2.2.2 RELATION TO CHILD-SUM TREE-LSTM
The Child-Sum Tree-LSTM Tai 2015) can also be derived from GTreeNet, which uses RNN aggregation function to aggregate a node's initial features and its neighbors with no further transformation.
4

---

Under review as a conference paper at ICLR 2022
2.3 GRAPH TREE ATTENTION NETWORK
The propagation rule of our proposed Graph Tree Attention Network is h
ELU EVEN. a b uu
where an and a are trainable attention weights calculated as a,v = softmax (c LeakyRRlLU (wo²) [zu h h2ttl) LeakyReLL (w= [zu zul) uf==
if
(9)
0,0
As compared to the general propagation rule in GTreeNet shown in Equation I uses an MLP as the transformation function d(.), an ELU function as f*).,, and an attention based weighted sum function as the aggregation function.
GTAN model
The mathematical description of our GTAN model then formulated as
Z MLP (X)
H Z
h ELU (EVENS ouott k+1 I + auuzu), k L 1, 2, .....
(10)
Yor = softmax WH)
where anp and A are calculated as Equation
2.3.1 RELATION TO GAT
The propagation rule GAT
h ELU (E SEN, oi, ho oz h
W
(11)
which uses attention based weighted sum to aggregate the hidden features of node u and its neigh- bors from the last propagation layer, and an MLP with ELU activation function fx)1(+) to trans- form the feature representation.
Except for the different information used in aggregation discussed in Section 2.1.1 another major difference between our GTAN model and the GAT model is that a transformation function with trainable parameters is applied after each propagation layer in GAT which introduces more trainable parameters. This might make the learning difficult and jeopardize the model performance.
2.4 MODEL COMPLEXITY
is straightforward see from Equation Hand 10 the time complexity of our GTCN and GTAN models is FLL which is in the same order as the vanilla GCN and GAT. Here |E] is the number of edges, F the dimension hidden features, and the model depth.
EXPERIMENTS
In this section, we conduct our experiments in three parts. The first one in Section 3.1 demon- strate the performance of our GTCN and GTAN models. We choose depth of 10 for both models to aggregate information from up to 10-hop neighbors the graph, and compare their performances against two current state-of-the We also include the most popular GCN and GAT models, as well as the Child-Sum Tree-LSTM as our baseline models. The second one in Section 3.2 is to demonstrate the deep capability of our mod- els by comparing our model performance with that the vanilla GCN and GAT different model comparison. The third one in Section 3.3
deep graph models: APPNP and DAGNN with the same depth.
depths. The Child-Sum Tree-LSTM is also included to discuss the effect of adding an MLP transformation function fa(-) with trainable parameters in GTCN and GTAN models. The codes reproduce experiments publicly available.
5

---

Under review as a conference paper at ICLR 2022
Table Statistics of datasets.
Cora
Citeseer
PuhMed
Coauthor-CS
ogbn-arxiv
Nodes
2708
3327
19717
18333
169343
Edges
10556
9228
88651
81894
1166243
Features/Node
1433
3703
500
6805
128
Classes
7
15
40
Label Rate
5.2%
3.6%
0.3%
1.6%
53.7%
Training
20/class
20/class
20/class
20/class
90941
Validation
500
500
500
450
29799
Test
1000
1000
1000
17583
48603
Datasets. We work on four popular benchmark datasets (Cora, Citeseer, PubMed and MS Coauthor- CS) from DGL library (Wang et al. 2019b) and one OGB dataset ogbn-arxiv (Hu et al. demonstrate the performance of our proposed models. The four datasets from the DGL library undirected graphs. Fixed data splits are provided for the Cora, Citeseer and PubMed datasets. For the Coauthor-CS dataset, split the data in the following way. We randomly selected 20 training samples per class and 30 validation samples per class, and all remaining samples are used as the test samples. We repeat the above process three times yiclding three splits for the Coauthor-CS dataset to avoid any bias. The ogbn-arxiv dataset is a homogeneous, unweighted, directed graph representing the citation between all Computer Science arXiv papers indexed by MAG. Each paper has 128- 228-dimensional features obtained by averaging the embeddings of words. The task is to predict the subject areas (40 total classes) of the paper.
2020a) to
The statistics of the benchmark datasets are summarized in Table 1 Note that the adjacency matrix for the Citeseer and PubMed datasets provided DGL. (Wang et al.) 2019h) includes several self- loops. We remove these self-loops to obtain the adjacency matrix in experiments.
3.1 PERFORMANCE OF GRAPH TREE CONVOLUTION AND ATTENTION NETWORKS
Baseline models. We compare our GTCN and GTAN models to five GNN models: the vanilla GCN (Kipf & Welling 2017). GAT /Velickovic et al.) 2018 Child-Sum Tree-I.TTM (Tai et al. 2015) and the current oftte-ofthhe-art APPNP (Klicpera et al. 2018)) and DAGNN (Liu ct al. 2020) models (we are also interested in comparing with the AdaGCN model (Sun et al. 2021 but the source code for the model has not been publicly available yet).
Model hyperparameters. For fair comparisons, all models as their original papers. All implementations use Adam optimizer with two hyperparameters: learning rate and weight decay.
up in almost the same settings
The detailed experiment setup is described Appendix A.2
Results of accurancy. We take 30 runs of each model each DGL dataset, and 10 runs of each model on the obgn-arxiv " The test results of classification accuracy are represented by mean + std. Test results the four DGL datasets are summarized in Table 2 The Macro-F1 scores of each model on the four DGL dataset are summarized in T Appendix A.3). Test results on the obgn-arxiv dataset are summarized in Table 3
Our GTCN model outperforms the current state-of-the-art baseline models APPNP and DAGNN on the Cora, Citeseer, and Coauthor-CS datasets. Our GTAN model achieves state-of-the-art perfor- mance on the Coauthor-CS dataset and the ogbn-arxiv dataset.
The ogbn-arxiv dataset much larger with much more complex neighborhood structures com- pared to the four DGL datasets. This may explain why our GTAN model outperforms GTCN model. GTAN has trainable pair-wise attention weights in each propagation layers, while GTCN does not have trainable weights in all propagation layers, i.e. GTCN employs fixed weights in the message
This set by OGB.

---

Under review as a conference paper at ICLR 2022
Table 2: Summary of average classification accuracy + one standard deviation (in percent) after filtering out the top and bottom 10% data on DGL datasets
Method
Cora
Citeseer
PubMed
Coauthor- CS (1)
Coauthor- CS (2)
Coauthor- CS (3)
GCN (hop 2)
81.5 + 0.2
71.6
79.0 + 0.3
90.7 + 0.2
90.2 + 0.2
89.7 + 0.2
GAT (hop = 2)
83.0 + 0.5
71.1 0.9
77.6
+ 0.4
90.4 0.3
90.3
89.5 + 0.4
Tree-LSTM
81.9 0.7
68.6 1.0
76.6
16.6 0.6
91.0 =1000.2 0.2
90.8 = 0.2
90.8 + 0.2
(hop = 2)
APPNP (hop=
83.6 + 0.5
0.5
79.6 + 0.2
91.8 + 0.4
91.8 + 0.3
91.4 + 0.3
10)
DAGNN (hop
84.0 + 0.5
72.6
79.6 0.4
90.4 + 0.3
90.3 0.4
89.6 + 0.6
10)
GTAN (hop-
83.4 + 1.0
7.44
79.4 + 0.2
92.2 + 0.3
92.4 0.2
92.0 + 0.3
10, ours)
GTCN (hop 84.5 = 0.6
72.9 0.5
79.2
92.7 0.1
92.5 0.1
92.4 + 0.2
10, ours)
Table Summary of average classification accuracy + one standard deviation (in percent) ogbn- arxiv dataset.
Method
ogbn-arxiv
GCN (hop = 3)
71.7 + 0.2
GAT (hop = 3)
71.8 + 0.1
Tree-LSTM (hop 3)
0.3
APPNP (hop = 5)
0.1
DAGNN (hop 16)
72.1
GTAN (hop 4, ours)
72.7 0.2
GTCN (hop = 5, ours)
72.3 + 0.2
aggregation. Therefore GTAN could capture more complex neighborhood structure than GTCN, and is more favored in such case.
Training time per epoch. The average training time per epoch on the DGL datasets are summarized in Table Obviously, our GTCN model is scalable to large graph and computational efficient even with deep layers. Attention based models require computation for attention weights between each pair of node and its neighbor nodes in each propagation layer, therefore are less efficient for dense graphs.
3.2 TEST OF MODEL DEPTH CAPABILITY
In this section, we demonstrate our models' capability of going deep by testing our models on the four DGL datasets with different numbers of propagation layers. We compare our GTCN model with the vanilla GCN, and our GTAN model with the vanilla GAT. We also include the Child-Sum Tree- LSTM model in the comparison as it is a derivative model within our GTreeNet architecture. All models are tested with depth of 2, 5 and 10, respectively. The classification accuracy is obtained with the same process as described Section 3.1
Model hyperparameters. For all models under test, we use 64 hidden units for every intermediate hidden layer. For the vanilla GCN, the dropout is 0.5, learning rate is 0.01 and weight decay is 5e-4 for all datasets and all model depths. For the vanilla GAT, we use one attention head for all experiments. At depth 2, the hyperparameters are the same as used in Section 3.1 At depth 5, the hyperparameters are mostly the same used at depth 2 except that set for the attention dropout for all datasets. At depth 10, the hyperparameters are fine-tuned with the layer dropout and the attention dropout of (0.2, 0) for all datasets. The learning rate and weight decay are 0.01 and
7

---

Under review as a conference paper at ICLR 2022
Table 4: Average training time per epoch (ms/epoch) on DGL datasets.
Method
Cora
Citeseer
PubMed
Coauthor-CS
GCN (hop 2)
3.5
3.3
3.6
7.4
GAT (hop = 2)
4.7
4.6
12.0
GCN (hop 10)
14.3
13.9
19.1
25.9
GAT (hop = 10)
17.6
17.8
21.8
32.7
APPNP (hop 10)
3.7
3.5
3.8
12.0
DAGNN (hop = 10)
4.7
4.6
5.1
13.2
GTAN (hop 10, ours)
17.7
18.1
19.4
34.4
GTCN (hop 10, ours)
3.7
3.6
8.1
18.6
0.84
0.82
0.66
0.76
Tee-LLTM
TreeLL5MM
GCN
0.74
GICN
GICN
0.60
GTAN
0.72
10
10
(a) Cora
(b) Citeseer
0.79
0.90
0.78
0.77
GCN
GCN
GITON
GTCN
0.84
GTAN
GTAN
10
10
(c) Pubmed
(d) Coauthor-CSS
Figure 2: Model performance in accuracy at different depths, tested four datasets: Cora (a),
Citeseer (b), Pubmed (c), and Coauthor-CS (d).
Se-3 respectively for all datasets. For the Child-Sum Tree-LSTM, the settings are consistent for all three depths and four datasets, with the input dropout and the dropout after the LSTM cell being (0.8, 0.6), learning rate being 0.01 and weight decay being 5e-4. For our GTCN model, the settings are the same as used in Section 3.1. For our GTAN model, the settings for depth 2 and 5 are mostly the same as descrihed Section except that the attention dropout set 0.6 for the Cora and Citeseer datasets.
Results. The test results of all five models at different depths are illustrated in Figure 2 More details are summarized in Table 8 and respectively in Appendix A.4 The results show that the performance Graph Tree Network based models (GTCN, GTAN and Child-Sum Tree-LSTM) does compromise in general when going deep, while the performance of the vanilla GCN and GAT models degrades significantly when going deep which is known as the "over-smoothing" issue. This comparison demonstrates the superiority of the message passing scheme in GTreeNet.
8

---

Under review as a conference paper at ICLR 2022
3.3 EFFECT OF ADDING TRANSFORMATION AFTER PROPAGATION
We find that adding an MLP network as f& in Equation ! will degrade the model performance. To demonstrate this experimentally. we construct a variant of our GTCN model by adding an MLP with the ReLU activation function after each propagation layer, and call it GTCN2 model. The propagation rule GTCN2 model now H ReL.U (A, performance of the GTCN and GTCN2 models on the Cora dataset at different depths (2, 5, and 10). Same tests are also performed on our GTAN model, and all results are summarized in Table
AzZ) W). We compare the
Adding an MLP network after each propagation layer introduces additional trainable parameters, which may cause worse fitting especially when training samples are limited. The results also show that the model performance degrades stacking more propagation layers after adding an MLP network after each propagation layer, which are consistent with the findings Liu et al. (020).
Table 5: Model performance in accuracy with and without nonlinear layers, tested on the Cora dataset.
Method (Cora)
Depth 2
Depth =
Depth 10
GTCN
83.3 + 0.3
84.4 0.6
84.5 = 0.5
GTCN2
80.7 = 0.5
80.6 0.6
80.0 = 0.8
GTAN
83.0 + 0.4
8.77
83.3 1.0
GTAN2
80.8 + 0.6
79.1
78.6 + 1.0
CONCLUSION
In this paper. we propose an innovative self-interpretive graph learning architecture: deep Graph Tree Network (GTreeNet), which is naturally derived from the tree representation of graphs. The message passing scheme in the GTreeNet has better interpretability than that in the vanilla GCN and GAT models. Two models within the GTreeNet architecture are proposed Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN), with demonstrated state-of-the-arr performance several benchmark datasets and the capability of going deep by stacking multiple propagation layers. The major advantage of the message passing scheme in the GTreeNet that models adopting this message passing scheme can go deep by stacking multiple propagation layers instead of calculating multi-hop information directly, where only information from the direct neigh- bors is used in each layer. This advantage may allow us extend our GTCN and GTAN models to heterogeneous graphs. Dealing with metapaths in heterogencous graphs is one of the biggest hurdles confronted by most of the current heterogeneous models like MAGNN (Pu al. (0200) and HAN (Wang et al. (019c), as the number of metapaths increases dramatically when aggregating multi- hop neighbors. The message passing scheme in our models helps avoid dealing with metapaths explicity as information on metapaths is self-contained by stacking multiple propagation layers. This opens future research opportunities. The general propagation rule we formulate the GTreeNet architec- ture may also open new research opportunities by exploring combination of different aggregation schemes and transformation functions.
REFERENCES
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-3852, 2016.
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network-based fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 315-324, 2020.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint 20 296699, 2020.

---

Under review as a conference paper at ICLR 2022
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-4244840 2019.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL htw.stttsp.... http::/ss////.ceeddeeeeoe ngs neur wewerripp.. cc/ haper/2017//11e//E
fbd w wwwb5-Pape..brpree..
Xinyu Fu, Jiani Zhang, Ziqiao Meng. and Irwin King. Magon: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, pp- 2331-2341 2020.
William L Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1035-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0066) 2020a.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0068) 2020b.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In 2020c.
Proceedings of The Web Conference 2020, pp.
Xiangyang Ju, Steven Farrell, Paolo Calafiura, Daniel Murnane, Lindsey Gray, Thomas Klijnsma, Kevin Pedro, Giuseppe Cerati, Jim Kowalkowski, Gabriel Perdue, et al. Graph neural networks for particle reconstruction in high energy physics detectors. arXiv preprint arXiv:2003. /1603, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings. OpenReview.net, 2017. URL httpst //openzeviews
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp- 338-348, 2020.
Yi-Chen Lu, Sai Surya Kiran Pentapati, Lingjun Zhu, Kambiz Samadi, and Sung Kyu Lim. Tp- gnn: graph neural network framework for tier partitioning in monolithic 3d ics. In 2020 57th ACM/EEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020.
Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection in a point cloud. In Proceedings of the IEEF/CVF conference on computer vision and paltern recognition, pp. 1711-1719, 2020.
Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Ada(gen): into deep models. In International Conference on Learning Representations, 2021. URL https:
Adaboosting graph convolutional networks
/ppenrevi ew. net.
www.:/etttor////. forum? d=QkRbd E
Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint 150.000553 2015.
10

---

Under review as a conference paper at ICLR 2022
Shikhar Vashishth, Naganand Yadati, and Partha Talukdar. Graph-based deep learning in natural language processing. In Proceedings of the 7th ACM IKDD CoDS and 25th COMAD, pp. 371- 372. 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htLLhttps///ppezeeeee htt.://w.eee/./otteeoe///o ott.:r/eww....tt.oooo..oooooooo.
Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang. Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi-supervised graph attentive network for financial fraud de- tection. 2019 IEEE International Conference on Data Mining (ICDM), pp. 598-607, IEEE, 2019a.
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centrie, perfoanterformant package for graph neural networks. arXiv preprint arxiv: wxXvv1900.00/15. 2019b.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous 2019c.
graph attention network. In The World Wide Web Conference, pp.
Lingfei Wu, Yu Chen, Heng Ji, and Yunyao Li. Deep learning on graphs for natural language pro- cessing. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Tutorials, pp. 11-14, 2021.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pp.
PMLR, 2018.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Pruceedings of the AAAI conference on artificial intelligence, volume 33, pp. 7370-7377, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv:1709.0487. 2017.
Yanqing Zhang. Haoxing Ren, and Brucek Khailany. Grannite: Graph neural network inference for transferable power estimation. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020.
Rong Zhu, Kun Zhao, Hongxia Yang. Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. Aligraph: comprehensive graph neural network platform. arXiv preprint arXiv: 080200 2019.
A APPENDIX
A.1 GTREENET ILLUSTRATION
Figure is an illustration of our Graph Tree Network (GTreeNet).
A.2 EXPERIMEMT SETUP
The maximum training epochs is set 1000 for all experiments.

---

Under review as a conference paper at ICLR 2022
Y/2
Y3
Y4
ys output prediction y
Inference
softmax
W (shared weight matrix across nodes)
2
3
hg
output feature map H
1
h
h
2
3
hop-1 feature map !!!
Propagation
h2
h2
2
3
hop-2 feature map H
h
h
h2
2
3
hop-3 feature map H
22
Z3
7
7.5
Transformation
hop-L feature map H² Z
MLP
X1
1
X2
X3
x
X5
5
input feature map X
Figure 3: Illustration of GTreeNet the sample graph in Figure 1
A.2.1
TEST ON DGL DATASETS
For the vanilla GCN, we use two layers with 64 hidden units and the dropout is 0.5 for all datasets. The learning rate and weight decay are 0.01 and 5e-4 respectively for all datasets.
For the vanilla GAT, we also use two layers with 64 hidden units, and other hyperparameters are fine-tuned to obtain the best performance. One attention head is used for both layers" The layer dropout and attention dropout are 0.8 and 0.8 respectively for the Cora and Citeseer datasets, 0.8 and 0.2 respectively for PubMed and Coauthor-CS datasets. The learning rate and weight decay 0.01 and 5e-4 respectively for all datasets.
For the 2-layer Child-Sum Tree-LSTM model, the input dropout and the dropout after the LSTM cell are 0.8 and 0.6 respectively. The learning rate and weight decay are 0.01 and 5e-4 respectively for all datasets.
For the APPNP, DAGNN, and GTCN and GTAN models, same as that used by the original paper of the APPNP model (Klicpera et al.) 2018). 64 hidden units used for these four deep models. For the APPNP, the dropout is 0.5 for the first ML. layer and the edge dropout is 0.5 for the propagation layer, the teleport probability a is 0.1 for the Cora, Citeseer and Pubmed datasets, and 0.2 for the Coauthor-CSS dataset[] For the DAGNN, the dropout is 0.8 and learning rate is 0.01 for all datasets. The weight decay is 2c-2 for the Citeseer dataset, and Se-3 for the Cora, PubMed and Coauthor-CS datasets. For our GTCN, we have two dropouts: one
maximum hop of 10, the
'hhe original paper (Velickovic et al. 2018 uses 8 heads the first layer, but we that head already achieves matching results. We have validated with greedy search that the value used in the original paper is approximately optimal.
12

---

Under review as a conference paper at ICLR 2022
Table 6: Summary of average Macro-Fl score + one standard deviation (in percent) after filtering out the top and bottom 10% data.
Method
Cora
Citeseer
PubMed
Coauthor- CS (1)
Coauthor- CS (2)
Coauthor- CS (3)
GCN (hop 2)
80.5 + 0.4
68.8 + 0.3
78.8 + 0.3
87.7 + 0.3
87.5 + 0.4
86.4 + 0.3
GAT (hop = 2)
81.6 + 0.5
67.0 0.7
77.1
0.3
87.8 + 0.4 0.4
87.8 0.4
86.9 + 0.4
Tree-LSTM
80.7 = 0.6
64.2
76.2
+ 0.6
88.8 0.2
88.5 = 0.2
88.1 + 0.2
(hop = 2)
APPNP (hop=
81.8 + 0.4
68.3
78.9 + 0.2
89.1 + 0.5
89.6 + 0.3
88.8 + 0.5
10)
DAGNN (hop
82.5 + 0.4
68.9 + 0.3
78.9 + 0.3
87.5 + 0.7
87.4 0.5
86.9 + 0.5
10)
GTAN (hop-
81.7 + 0.6
68.0 0.4
78.6 0.3
90.2 + 0.4
90.6 0.3
89.8 + 0.3
10, ours)
GTCN (hop 82.8 + 0.7
69.1 0.6
78.9 0.3
90.6 + 0.2
90.5 0.2
90.2 + 0.2
10, ours)
Table 7: Model performance in accuracy with different depths, tested on the Cora dataset
Method (Cora)
Depth 2
Depth = 5
Depth = 10
GCN GAT
81.5 + 0.2
78.1
72.3 = 1.4
83.0 0.5
8..
78.9 = 0.9
Tree-LSTM
81.9 0.7
8.7
80.4 0.7
GTAN (ours)
83.0 0.4
83.4 0.5
GTCN (ours)
83.3 = 0.3
8.
0.5
for the initial lny-l MLP, and the other is for the propagation layer. Corresponding dropout values are set to (0.6, 0.6) for the Cora dataset, (0.8, 0.6) for the Citeseer dataset, (0.8, 0.5) for the Pubmed dataset and (0.6, 0.2) for the Coautbor-CS dataset. The learning rate is 0.01 for the Cora, Citeseer and Coauthor-CC CS datasets, and 0.02 for the PubMed dataset. The weight decay is 5e-4 for the Cora, Citeseer and PubMed datasets, and 5e-3 for the Coauthor-CS dataset. For our GTAN, have the same two dropouts as for the GTCN, which are set to (0.6, 0) for the Cora, Citeseer and PubMed datasets, and (0.2, 0.2) for the Coauthor-CS dataset. The learning rate is set to 0.01 for all datasets. The weight decay is set to 5e-4 for the Cora, Citeseer and PubMed datasets, and 5e-3 for the Coauthor-CS dataset.
The early-stopping patience number is set to 100 for the DAGNN model (the same number is used in the original paper (Liu et al., 2020)), 300 for our GTAN model, and 200 for all other models.
A.2.2 TEST ON OGB DATASET
For the vanilla GCN, we use three layers with 256 hidden units and the dropout is 0.5. The learning rate and weight decay are 0.01 and 0, respectively.
For the vanilla GAT, we use three layers with 128 hidden units. One attention head is used for all layers. The input dropout and attention dropout are 0.2 and 0, respectively. The learning rate and weight decay are 0.01 and O, respectively.
For Child-Sum Tree-LSTM model, we use three layers with 256 hidden units. The input dropout and the dropout after the LSTT cell are 0.2 and 0, respectively. The learning rate and weight decay are 0.01 and 0, respectively.
For the APPNP model, use 5 layers with 256 hidden units. The input dropout and the dropout after each propagation layer are 0.2 and 0, respectively. The learning rate and weight decay are 0.01 and O, respectively.
13

---

Under review as a conference paper at ICLR 2022
Table 8: Model performance in accuracy with different depths, tested on the Citeseer dataset
Method (Citeseer)
Depth = 2
Depth = 5
Depth = 10
GCN GAT
71.6 + 0.3
64.8 + 1.0
58.8 + 1.9
71.1 0.9
68.1 + 0.9
66.6 1.0
Tree-LSTM
68.6 1.0
65.8 -
64.7
GTAN (ours)
0.6
71.4 0.6
GTCN (ours)
72.2 0.7
72.8 0.5
72.9 :. 0.5
Table 9: Model performance in accuracy with different depths, tested on the PubMed dataset
Method (PubMed)
Depth =
Depth 5
Depth 10
GCN GAT
79.0 : 0.3
76.7 0.6
75.3 0.9
7..6
76.9 0.5
7.71
Tree-LSTM
76.6 0.6
76.9 + 0.4
77.3
GTAN (ours)
79.1 + 0.4
79.3 0.4
19.4+002
GTCN (ours)
78.5 + 0.5
7..6
79.2 0.3
Table 10: Model performance in accuracy with different depths, tested the Coauthor-CS(3)
dataset
Method (Coauthor-CS)
Depth 2
Depth
Depth 10
GCN GAT
89.7 0.2
87.1 0.7
82.9 + 0.8
89.5 + 0.4
83.8
Tree-LSTM
91.0
90.8 0.2
GTAN (ours)
91.7
91.7 + 0.2
92.0
GTCN (ours)
92.1 + 0.2
92.0 + 0.2
0.24
14

---

Under review as a conference paper at ICLR 2022
For the DAGNN model, we use 16-hop with 256 hidden units. The dropout is 0.2. The learning rate and weight decay are 0.005 and O, respectively.
For our GTAN model, after each propagation layer are 0.2 and O, respectively. The learning rate and weight decay are 0.01 and 5e-5, respectively.
layers with 128 hidden units. The input dropout and the dropout
For our GTCN model, we use layers with 256 hidden units. The input dropout and the dropout after each propagation layer are 0.2 and 0.2, respectively. The learning rate and weight decay 0.01 and 5e-5, respectively.
A.3 TEST RESULTS ON MODEL PERFORMANCE IN MACRO-FI SCORE
The test results of model performance in Macro-FI score on the four DGL datasets are summarized in Table G
A.4 TEST RESULTS ON MODEL PERFORMANCES WITH DIFFERENT DEPTIIS
The test results model accuracy on the four DGL datasets with different number of propagation layers are summarized in Table 7 and T0 respectively.
15


Reviews:
[{"review_id": "tKPYtUL5Lbl", "reviewer": "Reviewer_2Sv9", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "I see no difference between the classical message passing scheme and the tree structure proposed in this paper.\nThe classical message passing scheme can also be described by a tree where each node's neighbors are its children.\n\nThe specific formula proposed by the paper is almost the same as APPNP [1]\n\n[1] Predict then Propagate: Graph Neural Networks meet Personalized PageRank. ICLR 2019", "summary_of_the_paper": "This paper proposes a message-passing formula derived from the tree representation of a graph.\nHowever, the proposed method has no innovation.", "summary_of_the_review": "This paper has no novelty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "jdB2eKADk13", "reviewer": "Reviewer_T8A2", "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": "### Strength\n\n- The idea of utilizing the tree representation is generally sound.\n\n\n### Weakness\n\n- From the second paragraph, the authors seem to make their tale by pointing out the complexity issue in the existing models (e.g. \"time complexity of O(k|E|)\", \"could be a too large number\" ). However, there is no interpretation on how their proposed model can address this issue. Particularly, the complexity of the proposed model is still in the same order as the vanilla GCN and GAT. And in the experiment, they only evaluate their proposed model in terms of effectiveness, which is hard to give a good end to the tale in the introduction.\n- The approach section is pretty chaotic. I am really hard to follow the key idea of their proposed model, and the model formulation is not tidy enough. E.g. Equation (5) and (6) could be more concise.\n- In the conclusion, the authors further propose the Heterogeneous Graph Tree Attention Network (HGTAN) with its formulas. But this proposed model hasn't been validated by any means, and should not be in the conclusion section. Instead, the conclusion section should focus more on the Graph Tree Network and the conclusion should connect to the experimental result, rather than some subjective statements, such as '\"We believe xxx\".\n- The writing is a critical issue for this paper. There are too many grammatical issues throughout this paper. And many statements lack their justification. E.g.Section 2, the first sentence, \"Generally graph learning based on direct neighbors only does not yield the best performance.\" needs a justification.\n- I don't think message passing through tree structure nodes would be a general scheme for all the nodes, since some nodes may not have any hierarchical structure. The analysis on which types of nodes could benefit more from the proposed tree-based message passing scheme should be added to further validate the generalization ability of the proposed model.\n- \"self-interpretive \" has not to be interpreted and justified in the paper.", "summary_of_the_paper": "The paper studies the task of network embedding. The authors propose a Graph Tree Networks (GTree), a deep graph neural network architecture that originates from the tree representation of the graphs. In particular, the proposed approach conduct message passing upward from the leaf nodes to the root node to update the root node’s hidden features. Experiment validates the effectiveness of the proposed model,", "summary_of_the_review": "- The writing of the paper should be significantly improved.\n- The motivation is not well stated in a good tale and the proposed model cannot address the issues stated in the motivation.\n- Many statements are too subjective and are not be well justified.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cBXa6UL-Km-", "reviewer": "Reviewer_RxA8", "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": "This paper provide two deep learning models to dealing with the tree representation of the graphs. \n\nStrength: 1. The message propagation is clear and explanable, which is dfifferent from conditional vanilla CCN， GAT and other dervatives.  2. The method is easy to follow and intuitive. 3. The performance reaches that of SOTA.\n\nWeakness:  1. The proposed method is intuitive and straightforward. So the contribution of the paper is unclear. ", "summary_of_the_paper": "In the paper, a self-interpretive graph learning architecture is presented based on the tree representation of graphs.The message passing scheme is natural and intuitive. Two models, Graph Tree Convolution and Graph Tree Attention Network, are given with SOTA performance. ", "summary_of_the_review": "This paper provides a simple and intuitive way to carry out graph learning based on the tree represnetaion of graph. And the performance of the presented models looks convincing. Source code is give for evluation. But I still have the following concerns:\n1. What are the major contributions of the paper? \n2. The time complexxity should include the transfering time from graph to tree structure? Especially for the large scele graph data? ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X0aJNb4AAR0", "reviewer": "Reviewer_3AAc", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strenght: \n1. The model architecture allows the network to encode path information crisply.\n2. The Graph tree network is more expressive than APPNP.\n\n\nWeakness\n1. I find the empirical evaluations are somewhat limiting.", "summary_of_the_paper": "The authors propose a novel neighborhood aggregation technique for GNNs based on the tree representation of the graph. Their proposed methods GTCN and GTAN pose comparable time complexity to that of GCN but empirically yield better results on various popular benchmarks. ", "summary_of_the_review": "Questions/ Clarification/ Suggestions:\n1.  I understand that the time complexity is comparable with GCN, however, I am still curious to know about training time (per epoch) for al the proposed models. \n2. Open Graph benchmark (https://ogb.stanford.edu/docs/leader_nodeprop/) provides a wide variety of tasks and associated datasets that are more interesting than these benchmarks. I would encourage the authors to apply their model to some of them.\n3. Why does the performance degrades significantly when a nonlinear layer after each propagation layer is added? The authors have never addressed that in the paper. I think pressing a bit more along that line might lead to a better interpretation of the message passing of the model.\n\nI would be happy to increase my score if some of the above-mentioned concerns are properly addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While I understand and have empathy with the authors' viewpoint of their work and novelty, this unfortunately has not reached reviewers' hearts in the way that they intended. There has been no strong support for acceptance, as the questions about the amount of novelty piled up. Some interactions between authors and reviewers happened. It is clear that the authors made an effort to show the differences with respect to other tree-related models and algorithms, as well as to highlight the strengths of the approach which was claimed to be too similar and simplistic. I believe the interactions helped with improving the first viewpoint of reviewers, however this improvement has not been enough, as reviewers did not significantly changed their stances. This is a short process and indeed it is not easy to change first impressions. If anything to add is that I hope that the impressions can be used to give a new presentation to the work that will enhance the work and its view by others.
Decision: Reject