Year: 2021

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. Under 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 passing 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-art performance on several benchmark datasets and the capability of going deep.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNNs), a class of neural networks for learning on 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 et al., 2020; Shi & Rajkumar, 2020), product recommendation and personalized search in E-commerce (Zhu et al., 2019), fraud detection (Wang et al., 2019a; Dou et al., 2020), protein interface predictions (Fout et al., 2017), power estimation and tier design in the semiconductor industry (Zhang et al., 2020; Lu et al., 2020), traffic forecasting (Yu et al., 2017), and natural language processing (Yao et 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, 2017) 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 et al., 2018), DAGNN (Liu et 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 et al. (2018) and Li et al. (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., 2020) are two most recent deep graph models with state-of-the-art performance on several popular benchmark datasets. APPNP (Klicpera et al., 2018) is developed based on personalized PageRank to preserve local information which requires fine tuning of a teleport probability. DAGNN (Liu et al., 2020) aggregates neighbors from different hops in parallel (in one layer) to utilize information from a larger receptive field as compared to GCN. Although DAGNN has achieved state-of-the-art performance, it may only be applicable to adopt simple aggregation function as the one used in GCN. It could be computationally challenging
to combine such multi-hop aggregation scheme with attention-based GNN models (such as 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 a 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 et al., 2019b) A5 has ∼2.2 million non-zero entries while A has only ∼10k non-zero entries. Furthermore, aggregating multi-hop 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).
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. Under the tree representation, message propagates upward from the leaf nodes to the root node naturally to update the root node’s hidden features. This message passing 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-ofthe-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 propagation 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 3.1 shows the performance test of our GTCN and GTAN models as compared to several popular and state-of-the-art GNN models on five benchmark datasets. Section 3.2 shows the performance test for our GTCN and GTAN models at different depths as 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.

heading: 2 OUR APPROACH: GRAPH TREE NETWORKS
text: 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 (1-hop neighbors) of node u. X ∈ RN×D represents the feature map for all nodes, where each row xu ∈ RD represents the feature vector of node u with dimension of D. Y ∈ RN×C represents the class matrix for all nodes, where each row yu represents the class vector of node u with C classes.

heading: 2.1 TREE REPRESENTATION AND NETWORK STRUCTURE
text: Tree is a straightforward representation for the graph topology, where each node and its neighborhood form one tree with the node itself being the root node and its neighbors being the subnodes. Figure 1 illustrates the tree representation for node 1 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 1, hku ∈ 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 1 is denoted as h01. 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 1), each of them is from a 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 to receiving information from its child nodes. With this
assumption, a 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) as shown in Appendix A.1, with the general message passing rule formulated as Equation 1:
hku = fk ( aggregate ( ϕ (xu) , { hk+1v ,∀v ∈ Nu })) (1)
where k = L−1, . . . , 0. L is the tree depth (number of propagation layers). xu is the vector of input features of node u. zu = ϕ(xu) is the transformation of input features of node u, i.e. the initial hidden features for the propagation layer. hku is the vector of hidden features of node u at k-hop, and hLu = zu. fk(·) is a hop-wise (layer-wise) transformation function such as MLP. 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 models in Section 2.2 and 2.3: Graph Tree Convolution Network (GTCN) and Graph Tree Attention Network (GTAN).

heading: 2.1.1 RELATION TO PROPAGATION SCHEME IN GCN-LIKE MODELS
text: The general message passing rule in GCN-like models such as GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018), and GraphSage (Hamilton et al., 2017) is
hnu = fn−1 ( aggregate ( hn−1u , { hn−1v ,∀v ∈ Nu })) (2)
Comparing to Equation 1, 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 a node’s hidden features by aggregating its neighbor’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 in GCNlike models does not. Note that we use n to denote the propagation layer number in Equation 2 to avoid ambiguities.

heading: 2.2 GRAPH TREE CONVOLUTION NETWORK
text: The propagation rule of our proposed Graph Tree Convolution Network is hku = ∑
v∈Nu Âuvh
k+1 v + Âuuzu (3)
where Â = D̃− 1 2 ÃD̃− 1 2 is the symmetric normalized adjacency matrix1. Ã = (A+ I) is the adjacency matrix with added self-loops. D̃ is the degree matrix with self-loops where D̃uu =∑ v Ãuv . zu = MLP(xu). 1We find that using Â = D̃−1Ã yields similar performance.
As compared to the general propagation rule in GTreeNet shown in Equation 1, our GTCN model uses an MLP as the transformation function ϕ(·), an identity function as fk(·), and a weighted sum function as the aggregation function with weights being the elements of the normalized adjacency matrix.
The mathematical description of our GTCN model is then formulated as
Z = MLP (X)
HL = Z
Hk = A1H k+1 +A2Z, k = L− 1, L− 2, . . . , 0 Yout = softmax ( H0W ) (4) where Z ∈ RN×F is the initial hidden feature map obtained by applying an MLP to the input feature map X . Hk ∈ RN×F is the hidden feature map at the kth hop. A1 and A2 are the non-diagonal and diagonal component of the normalized adjacency matrix, respectively. W ∈ RF×C 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 a node. These two characteristics make our model capable of going deep without comprising performance as demonstrated in Section 3.2.

heading: 2.2.1 RELATION TO GCN AND APPNP
text: GCN. The propagation rule in GCN is hnu = ReLU ((∑
v∈Nu Âuvh
n−1 v + Âuuh n−1 u
) W n−1 ) (5)
which uses weighted sum to aggregate the hidden features of node u and its neighbors from the last propagation layer, and an MLP with ReLU activation function as fn−1(·) to transform the feature representation.
Except for the different information used in aggregation as discussed in Section 2.1.1, another major difference between our GTCN model and the GCN model is that a transformation function is applied after each propagation layer in GCN which causes intertwined propagation and transformation, 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 hnu = (1− α) (∑
v∈Nu Âuvh
n−1 v + Âuuh n−1 u ) + αzu (6)
which uses weighted sum to aggregate the hidden features of 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 fn−1(·), i.e. no transformation is applied after propagation. APPNP uses the hidden features of node u from the last propagation layer (hn−1u ) in aggregation to update its hidden feature while our GTCN model does not. In addition, APPNP introduces a teleport probability α to 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:
hku = fk ( aggregate ( ϕ (xu) ,h k+1 u , { hk+1v ,∀v ∈ Nu })) (7)

heading: 2.2.2 RELATION TO CHILD-SUM TREE-LSTM
text: The Child-Sum Tree-LSTM (Tai et al., 2015) can also be derived from our GTreeNet, which uses RNN aggregation function to aggregate a node’s initial features and its neighbors with no further transformation.

heading: 2.3 GRAPH TREE ATTENTION NETWORK
text: The propagation rule of our proposed Graph Tree Attention Network is hku = ELU (∑
v∈Nu αku,vh k+1 v + α k u,uzu
) (8)
where αku,v and α k u,u are trainable attention weights calculated as αku,v = softmax ( eku,v ) eku,v = { LeakyReLU ( wT [ zu ∥ hk+1v ]) if u ̸= v
LeakyReLU ( wT [zu ∥ zu] ) if u = v
(9)
As compared to the general propagation rule in GTreeNet shown in Equation 1, our GTAN model uses an MLP as the transformation function ϕ(·), an ELU function as fk(·), and an attention based weighted sum function as the aggregation function.
The mathematical description of our GTAN model is then formulated as
Z = MLP (X)
HL = Z hku = ELU (∑
v∈Nu αku,vh k+1 v + α k u,uzu
) , k = L− 1, L− 2, . . . , 0
Yout = softmax ( H0W0
) (10)
where αku,v and α k u,u are calculated as in Equation 9.

heading: 2.3.1 RELATION TO GAT
text: The propagation rule in GAT is hnu = ELU ((∑
v∈Nu αnu,vh n−1 v + α n u,uh n−1 u
) W n−1 ) (11)
which uses attention based weighted sum to aggregate the hidden features of node u and its neighbors from the last propagation layer, and an MLP with ELU activation function as fn−1(·) to transform the feature representation.
Except for the different information used in aggregation as 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.

heading: 2.4 MODEL COMPLEXITY
text: It is straightforward to see from Equation 4 and 10 that the time complexity of our GTCN and GTAN models is O(L|E|F ) which is in the same order as the vanilla GCN and GAT. Here |E| is the number of edges, F is the dimension of hidden features, and L is the model depth.

heading: 3 EXPERIMENTS
text: In this section, we conduct our experiments in three parts. The first one in Section 3.1 is to demonstrate the performance of our GTCN and GTAN models. We choose a depth of 10 for both models to aggregate information from up to 10-hop neighbors in the graph, and compare their performances against two current state-of-the-art deep graph models: APPNP and DAGNN with the same depth. 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 models by comparing our model performance with that of the vanilla GCN and GAT at different model depths. The Child-Sum Tree-LSTM is also included as a comparison. The third one in Section 3.3 is to discuss the effect of adding an MLP transformation function fk(·) with trainable parameters in our GTCN and GTAN models. The codes to reproduce our experiments are publicly available.
Datasets. We work on four popular benchmark datasets (Cora, Citeseer, PubMed and MS CoauthorCS) from DGL library (Wang et al., 2019b) and one OGB dataset ogbn-arxiv (Hu et al., 2020a) to demonstrate the performance of our proposed models. The four datasets from the DGL library are undirected graphs. Fixed data splits are provided for the Cora, Citeseer and PubMed datasets. For the Coauthor-CS dataset, we 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 yielding 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-dimensional features obtained by averaging the embeddings of words. The task is to predict the subject areas (40 total classes) of the paper.
The statistics of the benchmark datasets are summarized in Table 1. Note that the adjacency matrix for the Citeseer and PubMed datasets provided in DGL (Wang et al., 2019b) includes several selfloops. We remove these self-loops to obtain the adjacency matrix in our experiments.

heading: 3.1 PERFORMANCE OF GRAPH TREE CONVOLUTION AND ATTENTION NETWORKS
text: 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-LSTM (Tai et al., 2015) and the current state-of-the-art APPNP (Klicpera et al., 2018) and DAGNN (Liu et 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 are set up in almost the same settings as in their original papers. All implementations use Adam optimizer with two hyperparameters: learning rate and weight decay.
The detailed experiment setup is described in Appendix A.2.
Results of accurancy. We take 30 runs of each model on each DGL dataset, and 10 runs of each model on the obgn-arxiv dataset2. The test results of classification accuracy are represented by mean ± std. Test results on the four DGL datasets are summarized in Table 2. The Macro-F1 scores of each model on the four DGL dataset are summarized in Table 6 (See 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 performance on the Coauthor-CS dataset and the ogbn-arxiv dataset.
The ogbn-arxiv dataset is much larger with much more complex neighborhood structures as compared 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
2This is set by OGB.

heading: Method ogbn-arxiv
text: 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 4. 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 a node and its neighbor nodes in each propagation layer, therefore are less efficient for dense graphs.

heading: 3.2 TEST OF MODEL DEPTH CAPABILITY
text: 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 TreeLSTM model in the comparison as it is a derivative model within our GTreeNet architecture. All models are tested with a depth of 2, 5 and 10, respectively. The classification accuracy is obtained with the same process as described in 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 as used at depth 2 except that we set 0 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

heading: Method Cora Citeseer PubMed Coauthor-CS
text: 5e-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 described in Section 3.1, except that the attention dropout is set to 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 7, 8, 9, and 10 respectively in Appendix A.4. The results show that the performance of Graph Tree Network based models (GTCN, GTAN and Child-Sum Tree-LSTM) does not 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 our GTreeNet.

heading: 3.3 EFFECT OF ADDING TRANSFORMATION AFTER PROPAGATION
text: We find that adding an MLP network as fk in Equation 1 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 a GTCN2 model. The propagation rule in GTCN2 model is now Hk = ReLU (( A1H k+1 +A2Z ) W ) . We compare the 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 5.
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 as stacking more propagation layers after adding an MLP network after each propagation layer, which are consistent with the findings by Liu et al. (2020).

heading: Method (Cora) Depth = 2 Depth = 5 Depth = 10

heading: 4 CONCLUSION
text: 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-art performance on 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 is 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 neighbors is used in each layer. This advantage may allow us to extend our GTCN and GTAN models to heterogeneous graphs. Dealing with metapaths in heterogeneous graphs is one of the biggest hurdles confronted by most of the current heterogeneous models like MAGNN (Fu et al., 2020) and HAN (Wang et al., 2019c), 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 in the GTreeNet architecture may also open new research opportunities by exploring combination of different aggregation schemes and transformation functions.

heading: A APPENDIX

heading: A.1 GTREENET ILLUSTRATION
text: Figure 3 is an illustration of our Graph Tree Network (GTreeNet).

heading: A.2 EXPERIMEMT SETUP
text: The maximum training epochs is set to 1000 for all experiments.

heading: A.2.1 TEST ON DGL DATASETS
text: 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 layers3. 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 the PubMed and Coauthor-CS datasets. The learning rate and weight decay are 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 our GTCN and GTAN models, we use a maximum hop of 10, the same as that used by the original paper of the APPNP model (Klicpera et al., 2018). 64 hidden units are used for these four deep models. For the APPNP, the dropout is 0.5 for the first MLP layer and the edge dropout is 0.5 for the propagation layer, the teleport probability α is 0.1 for the Cora, Citeseer and Pubmed datasets, and 0.2 for the Coauthor-CS dataset.4 For the DAGNN, the dropout is 0.8 and learning rate is 0.01 for all datasets. The weight decay is 2e-2 for the Citeseer dataset, and 5e-3 for the Cora, PubMed and Coauthor-CS datasets. For our GTCN, we have two dropouts: one
3The original paper (Velickovic et al., 2018) uses 8 heads for the first layer, but we find that 1 head already achieves matching results.
4We have validated with greedy search that the α value used in the original paper is approximately optimal.

heading: Method (Cora) Depth = 2 Depth = 5 Depth = 10
text: is for the initial one-layer 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 Coauthor-CS dataset. The learning rate is 0.01 for the Cora, Citeseer and Coauthor-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, we 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.

heading: A.2.2 TEST ON OGB DATASET
text: 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 0, respectively.
For Child-Sum Tree-LSTM model, we use three layers with 256 hidden units. The input dropout and the dropout after the LSTM cell are 0.2 and 0, respectively. The learning rate and weight decay are 0.01 and 0, respectively.
For the APPNP model, we 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 0, respectively.

heading: Method (Coauthor-CS) Depth = 2 Depth = 5 Depth = 10

heading: Method (PubMed) Depth = 2 Depth = 5 Depth = 10

heading: Method (Citeseer) Depth = 2 Depth = 5 Depth = 10
text: 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 0, respectively.
For our GTAN model, we use 4 layers with 128 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 5e-5, respectively.
For our GTCN model, we use 5 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 are 0.01 and 5e-5, respectively.

heading: A.3 TEST RESULTS ON MODEL PERFORMANCE IN MACRO-F1 SCORE
text: The test results of model performance in Macro-F1 score on the four DGL datasets are summarized in Table 6.

heading: A.4 TEST RESULTS ON MODEL PERFORMANCES WITH DIFFERENT DEPTHS
text: The test results of model accuracy on the four DGL datasets with different number of propagation layers are summarized in Table 7, 8, 9, and 10, respectively.

Review summaries:
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,