Title: GRAPHS, ENTITIES, AND STEP MIXTURE

Abstract: Graph neural networks have shown promising results on representing and analyzing diverse graph-structured data such as social, citation, and protein interaction networks. Existing approaches commonly suffer from the oversmoothing issue, regardless of whether policies are edge-based or node-based for neighborhood aggregation. Most methods also focus on transductive scenarios for fixed graphs, leading to poor generalization performance for unseen graphs. To address these issues, we propose a new graph neural network model that considers both edge-based neighborhood relationships and node-based entity features, i.e. Graph Entities with Step Mixture via random walk (GESM). GESM employs a mixture of various steps through random walk to alleviate the oversmoothing problem and attention to use node information explicitly. These two mechanisms allow for a weighted neighborhood aggregation which considers the properties of entities and relations. With intensive experiments, we show that the proposed GESM achieves state-of-the-art or comparable performances on four benchmark graph datasets comprising transductive and inductive learning tasks. Furthermore, we empirically demonstrate the significance of considering global information. The source code will be publicly available in the near future.

1. INTRODUCTION:

Graphs are universal data representations that exist in a wide variety of real-world problems, such as analyzing social networks (Perozzi et al., 2014; Jia et al., 2017) , forecasting traffic flow (Manley, 2015; Yu et al., 2017) , and recommending products based on personal preferences (Page et al., 1999; Kim et al., 2019) . Owing to breakthroughs in deep learning, recent graph neural networks (GNNs) (Scarselli et al., 2008) have achieved considerable success on diverse graph problems by collectively aggregating information from graph structures (Wang et al., 2018; Xu et al., 2018; Gao & Ji, 2019) . As a result, much research in recent years has focused on how to aggregate the feature representations of neighbor nodes so that the dependence of graphs is effectively utilized.

The majority of studies have predominantly depended on edges to aggregate the neighboring nodes' features. These edge-based methods are premised on the concept of relational inductive bias within graphs (Battaglia et al., 2018) , which implies that two connected nodes have similar properties and are more likely to share the same label (Kipf & Welling, 2017) . While this approach leverages graphs' unique property of capturing relations, it appears less capable of generalizing to new or unseen graphs (Wu et al., 2019b) .

To improve the neighborhood aggregation scheme, some studies have incorporated node information; They fully utilize node information and reduce the effects of relational (edge) information. A recent approach, graph attention networks (GAT), employs the attention mechanism so that weights used for neighborhood aggregation differ according to the feature of nodes (Veličković et al., 2018) . This approach has yielded impressive performance and has shown promise in improving generalization for unseen graphs.

Regardless of neighborhood aggregation schemes, most methods, however, suffer from a common problem where neighborhood information is considered to a limited degree (Klicpera et al., 2019) . For example, graph convolutional networks (GCNs) (Kipf & Welling, 2017) only operate on data that are closely connected due to oversmoothing (Li et al., 2018) , which indicates the "washing out" of remote nodes' features via averaging. Consequently, information becomes localized and access to global information is restricted (Xu et al., 2018) , leading to poor performance on datasets in which only a small portion is labeled (Li et al., 2018) .

In order to address the aforementioned issues, we propose a novel method, Graph Entities with Step Mixture via random walk (GESM), which considers information from all nodes in the graph and can be generalized to new graphs by incorporating random walk and attention. Random walk enables our model to be applicable to previously unseen graph structures, and a mixture of random walks alleviates the oversmoothing problem, allowing global information to be included during training. Hence, our method can be effective, particularly for nodes in the periphery or a sparsely labeled dataset. The attention mechanism also advances our model by considering node information for aggregation. This enhances the generalizability of models to diverse graph structures.

To validate our approach, we conducted experiments on four standard benchmark datasets: Cora, Citeseer, and Pubmed, which are citation networks for transductive learning, and protein-protein interaction (PPI) for inductive learning, in which test graphs remain unseen during training. In addition to these experiments, we verified whether our model uses information of remote nodes by reducing the percentage of labeled data. The experimental results demonstrate the superior performance of GESM on inductive learning as well as transductive learning for datasets. Moreover, our model achieved enhanced accuracy for datasets with reduced label rates, indicating the contribution of global information.

The key contributions of our approach are as follows:

• We present graphs with step mixture via random walk, which can adaptively consider local and global information, and demonstrate its effectiveness through experiments on public benchmark datasets with few labels.

• We propose Graph Entities with:

Step Mixture via random walk (GESM), an advanced model which incorporates attention, and experimentally show that it is applicable to both transductive and inductive learning tasks, for both nodes and edges are utilized for the neighborhood aggregation scheme. • We empirically demonstrate the importance of propagation steps by analyzing its effect on performance in terms of inference time and accuracy.

2. BACKGROUNDS:

2.1 RANDOM WALKS 100

Step-0 0 0 0 0 0 0 0

33.3:

Step-1 Random walk, which is a widely used method in graph theory, mathematically models how node information propagates throughout the graph. As shown in Figure 1 , random walk refers to randomly moving to neighbor nodes from the starting node in a graph. For a given graph, the transition matrix P , which describes the probabilities of transition, can be formulated as follows:

33:

P = AD -1 (1)

where A denotes the adjacency matrix of the graph, and D the diagonal matrix with a degree of nodes. The probability of moving from one node to any of its neighbors is equal, and the sum of the probabilities of moving to a neighboring node adds up to one.

Let u t be the distribution of the random walk at step t (u 0 represents the starting distribution). The t step random walk distribution is equal to multiplying P , the transition matrix, t times. In other words,

EQUATION

)

The entries of the transition matrix are all positive numbers, and each column sums up to one, indicating that P is a matrix form of the Markov chain with steady-state. One of the eigenvalues is equal to 1, and its eigenvector is a steady-state (Strang, 1993) . Therefore, even if the transition matrix is infinitely multiplied, convergence is guaranteed.

2.2. ATTENTION:

The attention mechanism was introduced in sequence-to-sequence modeling to solve long-term dependency problems that occur in machine translation (Bahdanau et al., 2015) . The key idea of attention is allowing the model to learn and focus on what is important by examining features of the hidden layer. In the case of GNNs (Scarselli et al., 2008) , GATs (Veličković et al., 2018) achieved stateof-the-art performance by using the attention mechanism. Because the attention mechanism considers the importance of each neighboring node, node features are given more emphasis than structural information (edges) during the propagation process. Consequently, using attention is advantageous for training and testing graphs with different node features but the same structures (edges).

Given the many benefits of attention, we incorporate the attention mechanism to our model to fully utilize node information. The attention mechanism enables different importance values to be assigned to nodes of the same neighborhood, so combining attention with mixture-step random walk allows our model to adaptively highlight features with salient information in a global scope.

3. OUR PROPOSED METHODS:

Let G = (V, E) be a graph, where V and E denote the sets of nodes and edges, respectively. Nodes are represented as a feature matrix X ∈ R n×f , where n and f respectively denote the number of nodes and the input dimension per node. A label matrix is Y ∈ R n×c with the number of classes c, and a learnable weight matrix is denoted by W . The adjacency matrix of graph G is represented as A ∈ R n×n . The addition of self-loops to the adjacency matrix is A = A + I n , and the column normalized matrix of A is Â = AD -1 with Â0 = I n . Most graph neural networks suffer from the oversmoothing issue along with localized aggregation.

3.1. GRAPH STEP MIXTURE: BASE APPROACH:

Although JK-Net (Xu et al., 2018) tried to handle oversmoothing by utilizing GCN blocks with mulitple propagation, it could not completely resolve the issue as shown in Figure 4b . We therefore propose Graph Step Mixture (GSM), which not only separates the node embedding and propagation process but also tackles oversmoothing and localized aggregation issues through a mixture of random walk steps.

GSM has a simple structure that is composed of three stages, as shown in Figure 2 . Input X passes through a fully connected layer with a nonlinear activation. The output is then multiplied by a normalized adjacency matrix Â for each random walk step that is to be considered. The results for each step are concatenated and fed into another fully connected layer, giving the final output. The entire propagation process of GSM can be formulated as:

EQUATION

where is the concatenation operation, s is the maximum number of steps considered for aggregation, and Âk is the normalized adjacency matrix Â multiplied k times. As can be seen from Equation 3, weights are shared across nodes.

In our method, the adjacency matrix Â is an asymmetric matrix, which is generated by random walks and flexible to arbitrary graphs. On the other hand, prior methods such as JK-Net (Xu et al., 2018) and MixHop (Abu-El-Haija et al., 2019) , use a symmetric Laplacian adjacency matrix, which limits graph structures to given fixed graphs.

(a) Traditional global aggregation scheme

Step-1

Step-2

Step-3 (b) Our step-mixture scheme For the concatenation operation, localized sub-graphs are concatenated with global graphs, which allows the neural network to adaptively select global and local information through learning (see Figure 3 ). While traditional graph convolution methods consider aggregated information within three steps by A(A(AXW (0) )W (1) )W (2) , our method can take all previous aggregations into account by

(A 0 XW | A 1 XW | A 2 XW | A 3 XW ).

3.2. GRAPH ENTITY STEP MIXTURE: GSM ENHANCED WITH ATTENTION:

To develop our base model which depends on edge information, we additionally adopt the attention mechanism so that node information is emphasized for aggregation, i.e., Graph Entity Step Mixture (GESM). We simply modify the nonlinear transformation of the first fully connected layer in GSM by replacing it with the attention mechanism denoted by H multi (see Equations 3 and 4). As described in Equation 4, we employ multi-head attention, where H multi is the concatenation of m attention layers and α is the coefficient of attention computed using concatenated features of nodes and its neighboring nodes.

EQUATION

By incorporating attention to our base model, we can avoid or ignore noisy parts of the graph, providing a guide for random walk (Lee et al., 2018) . Utilizing attention can also improve combinatorial generalization for inductive learning, where training and testing graphs are completely different. In particular, datasets with the same structure but different node information can benefit from our method because these datasets can only be distinguished by node information. Focusing on node features for aggregation can thus provide more reliable results in inductive learning.

The time complexity of our base model is O(s × l × h), where s is the maximum number of steps considered for aggregation, l is the number of non-zero entries in the adjacency matrix, and h is the hidden feature dimension. As suggested by Abu-El-Haija et al. ( 2019), we can assume h << l under realistic assumptions. Our model complexity is, therefore, highly efficient with time complexity O(s × l), which is on par with vanilla GCN (Kipf & Welling, 2017).

4. EXPERIMENTS:



4.1. DATASETS:

Transductive learning. We utilize three benchmark datasets for node classification: Cora, Citeseer, and Pubmed (Sen et al., 2008) . These three datasets are citation networks, in which the nodes represent documents and the edges correspond to citation links. The edge configuration is undirected, and the feature of each node consists of word representations of a document. Detailed statistics of the datasets are described in Table 1 .

For experiments on datasets with the public label rate, we follow the transductive experimental setup of Yang et al. (2016) . Although all of the nodes' feature vectors are accessible, only 20 node labels per class are used for training. Accordingly, 5.1% for Cora, 3.6% for Citeseer, and 0.3% for Pubmed can be learned. In addition to experiments with public label rate settings, we conducted experiments using datasets where labels were randomly split into a smaller set for training. To check whether our model can propagate node information to the entire graph, we reduced the label rate of Cora to 3% and 1%, Citeseer to 1% and 0.5%, Pubmed to 0.1%, and followed the experimental settings of Li et al. (2018) for these datasets with low label rates. For all experiments, we report the results using 1,000 test nodes and use 500 validation nodes.

Inductive learning. We use the protein-protein interaction PPI dataset (Zitnik & Leskovec, 2017) ,which is preprocessed by Veličković et al. (2018) . As detailed in Table 1 , the PPI dataset consists of 24 different graphs, where 20 graphs are used for training, 2 for validation, and 2 for testing. The test set remains completely unobserved during training. Each node is multi-labeled with 121 labels and 50 features regarding gene sets and immunological signatures.

4.2. COMPARISON MODELS:

For transductive learning, we compare our model with numbers of state-of-the-art models according to the results reported in the corresponding papers. Our model is compared with baseline models specified in (Veličković et al., 2018) such as label propagation (LP) (Xiaojin & Zoubin, 2002) , graph embeddings via random walk (DeepWalk) (Perozzi et al., 2014) , and Planetoid (Yang et al., 2016) . We also compare our model with models that use self-supervised learning (Union) (Li et al., 2018) , learnable graph convolution (LGCN) (Gao et al., 2018) , GCN based multi-hop neighborhood mixing (JK-GCN and MixHop) (Xu et al., 2018; Abu-El-Haija et al., 2019) , multi-scale graph convolutional networks (AdaLNet) (Liao et al., 2019) and maximal entropy transition (PAN) (Ma et al., 2019) . We further include models that utilize teleport term during propagation APPNP (Klicpera et al., 2019) , conduct convolution via spectral filters such as ChebyNet (Defferrard et al., 2016) , GCN (Kipf & Welling, 2017) , SGC (Wu et al., 2019a) , and GWNN (Xu et al., 2019) and models that adopt attention between nodes, such as GAT (Veličković et al., 2018) and AGNN (Thekumparampil et al., 2018) .

For inductive learning tasks, we compare our model against four baseline models. This includes graphs that use sampling and aggregation (GraphSAGE-LSTM) (Hamilton et al., 2017) , and jumping-knowledge (JK-LSTM) (Xu et al., 2018) , along with GAT and LGCN which are used in the transductive setting.

4.3. EXPERIMENTAL SETUP:

Regarding the hyperparameters of our transductive learning models, we used different settings for datasets with the public split and random split. We set the dropout probability such that 0.3 of the data were kept for the public split and 0.6 were kept for the random split. We set the number of multi-head m = 8 for GESM. The size of the hidden layer h ∈ {64, 512} and the maximum number of steps used for aggregation s ∈ {10, 30} were adjusted for each dataset. We trained for a maximum of 300 epochs with L2 regularization λ = 0.003 and learning rate lr = 0.001. We report the average classification accuracy of 20 runs.

For inductive learning, the size of all hidden layers was the same with h = 256 for both GSM, which consisted of two fully connected layers at the beginning and GESM. We set the number of steps s = 10 for GSM, and s = 5, m = 15 for GESM. L2 regularization and dropout were not used for inductive learning (Veličković et al., 2018) . We trained our models for a maximum of 2,000 epochs with learning rate lr = 0.008. The evaluation metric was the micro-F1 score, and we report the averaged results of 10 runs.

For all the models, the nonlinearity function of the first fully connected layer was an exponential linear unit (ELU) (Clevert et al., 2016) . Our models were initialized using Glorot initialization (Glorot & Bengio, 2010) and were trained to minimize the cross-entropy loss using the Adam (Li et al., 2018) 69.9 78.5 46.3 59.1 70.7 * JK-GCN (Xu et al., 2018) 65 optimizer (Kingma & Ba, 2015) . We employed an early stopping strategy based on the loss and accuracy of the validation sets, with a patience of 100 epochs.

5. RESULTS:



5.1. NODE CLASSIFICATION:

Results on benchmark datasets. Table 2 summarizes the comparative evaluation experiments for transductive and inductive learning tasks. In general, not only are there a small number of methods that can perform on both transductive and inductive learning tasks, but the performance of such methods is not consistently high. Our methods, however, are ranked in the top-3 for every task, indicating that our method can be applied to any task with large predictive power.

For transductive learning tasks, the experimental results of our methods are higher than or equivalent to those of other methods. As can be identified from the table, our base model GSM, which is computationally efficient and simple, outperforms many existing baseline models. These results indicate the significance of considering both global and local information and using random walks. It can also be observed that GESM yielded more impressive results than GSM, suggesting the importance of considering node information in the aggregation process.

For the inductive learning task, our base model GSM, which employs an edge-based aggregation method, does not invariably obtain the highest accuracy. However, our model with attention, GESM, significantly improves performance of GSM by learning the importance of neighborhood nodes, and surpasses the results of GAT, despite the fact that GAT consists of more attention layers. These results for unseen graphs are in good agreement with results shown by Veličković et al. (2018) , in which reducing the influence of structural information improved generalization.

Results on datasets with low label rates. To demonstrate that our methods can consider global information, we experimented on sparse datasets with low label rates of transductive learning datasets. As indicated in Table 3 , our models show remarkable performance even on the dataset with low label rates. In particular, we can further observe the superiority of our methods by inspecting Table 2 and 3, in which our methods trained on only 3% of the Cora dataset outperformed some other methods trained on 5.1% of the data. Because both GSM and GESM showed enhanced accuracy, it could be speculated that using a mixture of random walks played a key role in the experiments; the improved results can be explained by our methods adaptively selecting node information from local and global neighborhoods, and allowing peripheral nodes to receive information.

5.2. MODEL ANALYSIS:

Oversmoothing and Accuracy. As shown in Figure 4a , GCN (Kipf & Welling, 2017) , SGC (Wu et al., 2019a) , and GAT (Veličković et al., 2018) suffer from oversmoothing. GCN and GAT show severe degradation in accuracy after the 8th step; The accuracy of SGC does not drop as much as GCN and GAT but nevertheless gradually decreases as the step size increases. The proposed GSM, unlike the others, maintains its performance without any degradation, because no rank loss (Luan et al., 2019) occurs and oversmoothing is overcome by step mixture.

Interestingly, JK-Net (Xu et al., 2018 ) also keeps the training accuracy regardless of the step size by using GGN blocks with multiple steps according to Figure 4a . We further compared the test accuracy of GSM with JK-Net, a similar approach to our model, in regards to the step size. To investigate the adaptability to larger steps of GSM and JK-Net, we concatenated features after the 10th step. As shown in Figure 4b , GSM outperforms JK-Net, even though both methods use concatenation to alleviate the oversmoothing issue. These results are in line with the fact that JK-Net obtains global information similar to GCN or GAT. Consequently, the larger the step, the more difficult it is for JK-Net to maintain performance. GSM, on the other hand, maintains a steady performance, which confirms that GSM does not collapse even for large step sizes. Test Accuracy GSM public (5.1%) 3% 1% GESM public (5.1%) 3% 1%

Figure 5 : Accuracy comparison for various label rates according to step size.

We also observe the effect on accuracy as the number of steps increases under three labeling conditions for GSM and GESM. As represented in Figure 5 , it is evident that considering remote nodes can contribute to the increase in accuracy. By taking into account more data within a larger neighborhood, our model can make reliable decisions, resulting in improved performance. Inspection of the figure also indicates that the accuracy converges faster for datasets with higher label rates, presumably because a small number of walk steps can be used to explore the entire graph. Moreover, the addition of attention benefits performance in terms of higher accuracy and faster convergence.

Inference time. As shown in Figure 6 , the computational complexity of all models increases linearly as the step size increases. We can observe that the inference time of GSM is faster than GCN (Kipf & Welling, 2017) especially when the number of steps is large. The inference time of GESM is much faster than GAT (Veličković et al., 2018) while providing higher accuracies and stable results (see Appendix A). Our methods are both fast and accurate due to the sophisticated design with a mixture of random walk steps.

Embedding Visualization. Figure 7 visualizes the hidden features of Cora from our models by using 2 , more closely clustered GSM does not generally produce better results than loosely clustered GESM, which supports findings that the attention mechanism aids models to ignore or avoid noisy information in graphs (Lee et al., 2018) .

6. CONCLUSION:

In this paper, we have proposed simple but effective two types of models to utilize global information and improve generalization for unseen graphs. GSM, the base model, is computationally efficient and effectively aggregate global and local information by employing multiple random walks. To further refine our base model, we have presented GESM, which explicitly leverages node information (see Appendix B). The results from extensive experiments show that our models successfully achieve state-of-the-art or competitive performance for both transductive and inductive learning tasks on four benchmark graph datasets. As future directions, we will refine our method that utilizes node information to improve the computational efficiency regarding attention. In addition, we will extend GESM so that it can be applied to real-world large scale graph data. 4 and we followed the experimental setup of Shchur et al. (2018) .

We used the same values for each hyperparameter (unified size: 64, step size: 15, multi-head for GAT and GESM: 8) without tuning. The results in Table 5 prove that our proposed methods do not overfit to a particular dataset. Moreover, in comparison to GAT, the performance of GESM is more accurate, and more stable. We visualized the distribution of attention vectors. Figure 8a plots the distribution of neighbors with equal importance and Figure 8b displays the distribution of attention weighted neighbors that we trained with GESM. Although both figures look similar to some degree, we can conjecture that GESM slightly adjusts the weight values, contributing to improved performance.

:

https://kddcup2016.azurewebsites.net/

Figures and Tables:

Figure 1: Random walk propagation procedure. From left to right are step-0, step-1, step-2, and stepinfinite. The values in each node indicate the distribution of a random walk. In the leftmost picture, only the starting node has a value of 100, and all other nodes are initialized to zero. As the number of steps increases, values spread throughout the graph and converge to some extent.

Figure 2: Schematic process of Graph Step Mixture. The procedure consists of three stages: (1ststage) input passes the FC-layer, (2nd-stage) adjacency matrix is multiplied then concatenated, (3rdstage) the final output is produced.

Figure 3: Conceptual scheme of neighborhood aggregation for three steps in conventional graph neural networks (a) and GSM which uses mixture of random walks (b).

Training accuracy comparison according to number of propagation steps.

Test accuracy of JK-Net and GSM using concatenated features after the 10th step.

Figure 4: Effect of the step size on model performance on Cora.

Figure 6: Inference time of various models as the step size increases for Cora dataset.

Figure 7: t-SNE plot of the last hidden layer trained on the Cora dataset.

Basic attention. (b) Our attention.

Figure 8: Visualization of attention distribution.

Summary of datasets used in the experiments. Transductive learning datasets consist of one graph and use a subset of the graph for training. † Inductive learning datasets consist of many graphs and use a few graphs for training and unseen graphs for testing.

Table content: <table><tr><td colspan="2">Type Datasets</td><td/><td colspan="2">Nodes (Graphs)</td><td/><td colspan="4">Features Edges Classes Label rate</td></tr><tr><td/><td/><td colspan="3">Total Training Validation</td><td>Test</td><td/><td/><td/></tr><tr><td/><td>Cora</td><td>2,708</td><td>140</td><td colspan="2">500 1,000</td><td>1,433</td><td>5,429</td><td>7</td><td>5.1%</td></tr><tr><td>T  *</td><td>Citeseer</td><td>3,327</td><td>120</td><td colspan="2">500 1,000</td><td>3,703</td><td>4,732</td><td>6</td><td>3.6%</td></tr><tr><td/><td colspan="2">Pubmed 19,717</td><td>60</td><td colspan="2">500 1,000</td><td colspan="2">500 44,338</td><td>3</td><td>0.3%</td></tr><tr><td>I  †</td><td>PPI</td><td>56,944</td><td>44,906</td><td colspan="2">6,514 5,524</td><td>50</td><td>8,187</td><td>121</td><td>-</td></tr><tr><td/><td/><td>(24)</td><td>(20)</td><td>(2)</td><td>(2)</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Experimental results on the public benchmark datasets. Evaluation metrics on transductive and inductive learning datasets are classification accuracy (%) and F1-score, respectively. Top-3 results for each column are highlighted in bold, and top-1 values are underlined.

Table content: <table><tr><td/><td/><td>Transductive</td><td/><td>Inductive</td></tr><tr><td>Method</td><td colspan="3">Cora public (5.1%) public (3.6%) public (0.3%) Citeseer Pubmed</td><td>PPI</td></tr><tr><td>LP (Xiaojin &amp; Zoubin, 2002)</td><td>68.0</td><td>45.3</td><td>63.0</td><td>-</td></tr><tr><td>Deep Walk (Perozzi et al., 2014)</td><td>67.2</td><td>43.2</td><td>65.3</td><td>-</td></tr><tr><td>Cheby (Defferrard et al., 2016)</td><td>81.2</td><td>69.8</td><td>74.4</td><td>-</td></tr><tr><td>Planetoid (Yang et al., 2016)</td><td>75.7</td><td>64.7</td><td>77.2</td><td>-</td></tr><tr><td>GCN (Kipf &amp; Welling, 2017)</td><td>81.5</td><td>70.3</td><td>79.0</td><td>-</td></tr><tr><td>GraphSAGE (Hamilton et al., 2017)</td><td>-</td><td>-</td><td>-</td><td>0.612</td></tr><tr><td>GAT (Veličković et al., 2018)</td><td>83.0</td><td>72.5</td><td>79.0</td><td>0.973</td></tr><tr><td>LGCN (Gao et al., 2018)</td><td>83.3</td><td>73.0</td><td>79.5</td><td>0.772</td></tr><tr><td>JK-LSTM (Xu et al., 2018)</td><td>-</td><td>-</td><td>-</td><td>0.976</td></tr><tr><td>AGNN (Thekumparampil et al., 2018)</td><td>83.1</td><td>71.7</td><td>79.9</td><td>-</td></tr><tr><td>Union (Li et al., 2018)</td><td>80.5</td><td>65.7</td><td>78.3</td><td>-</td></tr><tr><td>*  APPNP (Klicpera et al., 2019)</td><td>83.2</td><td>71.7</td><td>79.7</td><td>-</td></tr><tr><td>SGC (Wu et al., 2019a)</td><td>81.0</td><td>71.9</td><td>78.9</td><td>-</td></tr><tr><td>MixHop (Abu-El-Haija et al., 2019)</td><td>81.9</td><td>71.4</td><td>80.8</td><td>-</td></tr><tr><td>GWNN (Xu et al., 2019)</td><td>82.8</td><td>71.7</td><td>79.1</td><td>-</td></tr><tr><td>AdaLNet (Liao et al., 2019)</td><td>80.4</td><td>68.7</td><td>78.1</td><td>-</td></tr><tr><td>PAN (Ma et al., 2019)</td><td>82.0</td><td>71.2</td><td>79.2</td><td>-</td></tr><tr><td>GSM (our base model)</td><td>82.8</td><td>71.7</td><td>80.3</td><td>0.753</td></tr><tr><td>GESM (GSM+attention)</td><td>84.4</td><td>72.6</td><td>80.1</td><td>0.976</td></tr><tr><td/><td/><td/><td/><td/></tr></table>

Node classification results on datasets with low label rates. Top-3 results for each column are highlighted in bold and top-1 values are underlined.

Table content: <table><tr><td/><td>Cora</td><td/><td colspan="2">Citeseer</td><td>Pubmed</td></tr><tr><td>Method</td><td>1%</td><td>3%</td><td>0.5%</td><td>1%</td><td>0.1%</td></tr><tr><td>LP (Xiaojin &amp; Zoubin, 2002)</td><td>62.3</td><td>67.5</td><td>34.8</td><td>40.2</td><td>65.4</td></tr><tr><td>Cheby (Defferrard et al., 2016)</td><td>52.0</td><td>70.8</td><td>31.7</td><td>42.8</td><td>51.2</td></tr><tr><td>GCN (Kipf &amp; Welling, 2017)</td><td>62.3</td><td>76.5</td><td>43.6</td><td>55.3</td><td>65.9</td></tr><tr><td>Union</td><td/><td/><td/><td/><td/></tr></table>

Summary of datasets used in the additional experiments.

Table content: <table><tr><td/><td>Classes</td><td>Features</td><td>Nodes</td><td>Edges</td><td>Label rate</td></tr><tr><td>Coauthor CS</td><td>15</td><td>6,805</td><td>18,333</td><td>100,227</td><td>1.6%</td></tr><tr><td>Coauthor Physics</td><td>5</td><td>8,415</td><td>34,493</td><td>282,455</td><td>0.2%</td></tr><tr><td>Amazon Computers</td><td>10</td><td>767</td><td>13,381</td><td>259,159</td><td>1.4%</td></tr><tr><td>Amazon Photo</td><td>8</td><td>745</td><td>7,487</td><td>126,530</td><td>2.1%</td></tr></table>

Average test set accuracy and standard deviation over 100 random train/validation/test splits with 20 runs. Top-3 results for each column are highlighted in bold, and top-1 values are underlined.For an in-depth verification of overfitting, we extended our experiments to four types of new node classification datasets. Coauthor CS and Coauthor Physics are co-authorship graphs from the KDD Cup 2016 challenge 1 , in which nodes are authors, features represent the article keyword for each author's paper, and class labels indicate each author's most active research areas. Amazon Computers and Amazon Photo are co-purchase graphs of Amazon, where nodes represent the items, and edges indicate that items have been purchased together. The node features are bag-of-words of product reviews, and class labels represent product categories. Detailed statistics of the datasets are described in Table

Table content: <table><tr><td/><td colspan="4">Coauthor CS Coauthor Physics Amazon Computers Amazon Photo</td></tr><tr><td>MLP</td><td>88.3 ± 0.7</td><td>88.9 ± 1.1</td><td>44.9 ± 5.8</td><td>69.6 ± 3.8</td></tr><tr><td>LogReg</td><td>86.4 ± 0.9</td><td>86.7 ± 1.5</td><td>64.1 ± 5.7</td><td>73.0 ± 6.5</td></tr><tr><td>LP (Xiaojin &amp; Zoubin, 2002)</td><td>73.6 ± 3.9</td><td>86.6 ± 2.0</td><td>70.8 ± 8.1</td><td>72.6 ± 11.1</td></tr><tr><td>GCN (Kipf &amp; Welling, 2017)</td><td>91.1 ± 0.5</td><td>92.8 ± 1.0</td><td>82.6 ± 2.4</td><td>91.2 ± 1.2</td></tr><tr><td colspan="2">GraphSAGE (Hamilton et al., 2017) 91.3 ± 2.8</td><td>93.0 ± 0.8</td><td>82.4 ± 1.8</td><td>91.4 ± 1.3</td></tr><tr><td>GAT (Veličković et al., 2018)</td><td>90.5 ± 0.6</td><td>92.5 ± 0.9</td><td>78.0 ± 19.0</td><td>85.7 ± 20.3</td></tr><tr><td>GSM (our base model)</td><td>91.8 ± 0.4</td><td>93.3 ± 0.6</td><td>79.2 ± 2.0</td><td>89.3 ± 1.9</td></tr><tr><td>GESM (GSM+attention)</td><td>92.0 ± 0.5</td><td>93.7 ± 0.6</td><td>79.3 ± 1.7</td><td>90.0 ± 2.0</td></tr><tr><td colspan="3">A EXPERIMENTS ON OTHER DATASETS</td><td/><td/></tr></table>

Peer review (iclr2020):
This paper presents two models, namely GSM and GESM, to tackle the problem of transductive and inductive node classification. GSM is operating on asymmetric transition matrices and works by stacking propagation layers of different locality, where the final prediction is based on all propagation steps (JK concatenation style). GESM builds upon GSM and introduces a multi-headed attention layer applied on the initial feature matrix to guide the propagation layers. The models are evaluated on four common benchmark datasets and achieve state-of-the-art performance, especially when the training label rate is reduced. Overall, the paper is well-written and its presentation is mostly clear and comprehensible (see below). The quantitative evaluation looks good to me, especially since an ablation study shows the contributions of all of the proposed features. However, there are a few weak points which should explain my overall score: 1. The proposed GSM model is not new and only re-uses building blocks from the related work. [1] shows that removing non-linearities is an effective procedure for node classification. [2] investigates the massively stacking of propagations. The procedure of feature concatenation from different locality has been studied in [3]. Applying asymmetric normalization is a standard aggregation scheme for GNNs, e.g., in [4]. 2. The GESM model is not fully understandable since it is missing a formal description for computing . It is only said that is computed using the concatenation of features from the central node and its neighbors. Can you elaborate how exactly you compute , especially since the concatenation of neighboring features results in a non-permutation invariant architecture? In addition, in contrast to the reported results in Tables 3 and 4, Figure 4 indicates that the benefits of GESM are negligible. 3. The final prediction layer with weight matrix W_1 operates on all propagation layers, resulting in a parameter complexity of , where is the number of classes. With and , this results in 15.360 c parameters (!!!), whereas GCN [5] only uses 16 c parameters. Hence, I do not think it is fair to promote your model as efficient as vanilla GCN. In addition, the final matrix multiplication results in a computational complexity of which does not nearly match your reported complexity. Furthermore, I do wonder why your model is not heavily overfitting with such an amount of parameters. For example, this is the reason [3] does evaluate its model on a larger training split instead of a smaller one. 4. As your work is quite similar to [1, 2], it would be beneficial to also include the respective results of those methods in Tables 2 and 3. In addition, their differences and similarities should be discussed in detail. 5. Since the used benchmark datasets are already reasonably explored, authors are advised to include evaluation on other datasets as well, e.g., from [6]. 6. The transition matrix is missing self-loops to match with the results of Figure 1. Since you already define analogously to , you should focus on one notation for consistency reasons. [1] Wu et al.: Simplifying Graph Convolutional Networks [2] Klicpera et al.: Predict then Propagate: Graph Neural Networks meet Personalized PageRank [3] Xu et al.: Representation Learning on Graphs with Jumping Knowledge Networks [4] Hamilton et al.: Inductive Representation Learning on Large Graphs [5] Kipf and Welling: Semi-Supervised Classification with Graph Convolutional Networks [6] Shchur et al.: Pitfalls of Graph Neural Network Evaluation ---------------------------- Update after the rebuttal: The authors have addressed several issues and improved their manuscript. I greatly appreciate the effort and the new experimental results. However, the main weak point that the novelty of the approach is limited remains valid of course. Therefore, I am still more inclined to rejecting the paper. I have raised my score from *1: Reject* to *3: Weak Reject*. I have raised my score from *5: Weak Reject* to *6: Weak Accept*.