GRAPHS, ENTITIES, AND STEP MIXTURE
Authors: Kyuyong Shin
Wonyoung Shin
Jung-Woo Ha
Sunyoung Kwon
Venue:  (2020)
Keywords: Graph Neural Network
Random Walk
Attention

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.

Under review as a conference paper at ICLR 2020
GRAPHS, ENTITIES, AND STEP MIXTURE
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph neural networks have shown promising results representing and ana- lyzing diverse graph-structured data such as social, citation, and protein inter- action networks. Existing approaches commonly suffer from the oversmoothing issue, regardless of whether policies are edge-based or node-based for neighbor- hood aggregation. Most methods also focus 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 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-an comparable performances on four benchmark graph datasets comprising transductive and inductive learning tasks. Furthermore, we empiri- cally demonstrate the significance of considering global information. The source code will be publicly available the near future.
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. (017). 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 al. 2018 Xu et 2018 Gao & |] 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 implics that two connected nodes have similar properties and are more likely 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 informa- tion; They fully utilize node information and reduce the effects of relational (edge) information. A recent approach, graph attention networks (GAT), employs the attention mechanism that weights used for neighborhood aggregation differ according to the feature of nodes (Veličković al. 2018). This approach has yielded impressive performance and has shown promise in improving generaliza- tion for unseen graphs.
Regardless of neighborhood aggregation schemes, most methods, however, suffer from 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 data that are closely connected due to oversmoothing (Li et 2018), which indicates the "washing out" of remote nodes' features via averaging. Consequently, information becomes localized and access

---

Under review as a conference paper at ICLR 2020
global information is restricted (Xu al. 2018). leading to poor performance 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 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 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 ad- dition 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 perfor- mance 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 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.
BACKGROUNDS
2.1 RANDOM WALKS
Step-0
Step-1
Step-2
Step-ea
33.9
174
20
8.3
12.5
Figure 1: Random walk propagation procedure. From left right are step-0, step-1, step-2, and step- infinite. The values in each node indicate the distribution of a random walk. In the leftmost picture, only the starting node has 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.
Random walk, which is widely used method in graph theory, mathematically models how node information propagates throughout the graph. As shown Figure 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:
P AD
where A denotes the adjacency matrix of the graph, and D the diagonal matrix with 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 neighboring node adds up one.
2

---

Under review as a conference paper at ICLR 2020
Let u' be the distribution of the random walk at step t (u represents the starting distribution). The t step random walk distribution is equal to multiplying P, the transition matrix, times. In other words,
u' Pu" w' P P'u.
(2)
The entries of the transition matrix are positive numbers, and each column sums up one, indicating that P is a matrix form of the Markov chain with steady-state. One of the cigenvalues equal to 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 sequeecce-o-sequeeee modeling to solve long-term de- pendency problems that occur in machine translation (Bahdanau et al.) (015). The key idea of atten- tion is allowing the model to learn and focus on what is important by examining features of the hid- den layer. In the case of GNNs (Scarselli et al. 2008), GATs (Veličković et al. 2018) achieved state- of-the-art performance by using the attention mechanism. Because the attention mechanism consid- ers 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 model to fully utilize node information. The attention mechanism enables different importance values to be as- signed to nodes of the same neighborhood, 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 (V, E) be graph, where V and E denote the sets of nodes and edges, respectively. Nodes are represented as a feature matrix X E Raxs, where n and f respectively denote the number of nodes and the input dimension per node. A label matrix is Y IR"x with the number of classes and a learnable weight matrix is denoted by W. The adjacency matrix of graph G is represented
as A E R.**, The addition of self-loops to the adjacency matrix is A A + I,, and the column normalized matrix of Á is Å ÄD-I with A J,.
3.1
GRAPH STEP MIXTURE: BASE APPROACH
FC-layur
BC-Layer
X
Z
1"-stage
2tlstaage
3"'stage
Figure 2:
Schematic process of Graph Step Mixture. The procedure consists of three stages: (1st- stage) input passes the FC-layer, (2nd-stage) adjacency matrix multiplied then concatenated, (3rd- stage) the final output is produced.
Most graph neural networks suffer from the oversmoothing issue along with localized aggregation. 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 propaga- tion process but also tackles oversmoothing and localized aggregation issues through a mixture of random walk steps.
3

---

Under review as a conference paper at ICLR 2020
GSM has simple structure that is composed of three stages, shown in Figure 2 Input X passes through a fully connected layer with a nonlinear activation. The output is then multiplied by nor- malized adjacency matrix À each random walk step that is to 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:
(<ii À ((( k=
ZGSM = softmax
(3)
where || is the concatenation operation, is the maximum number of steps considered for aggre- gation, and A is the normalized adjacency matrix À multiplied l: times. As be seen from Equation weights are shared across nodes.
In our method, the adjaceney 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-EI-Haija et al. 2019), use a symmetric Laplacian adjacency matrix, which limits graph structures to given fixed graphs.
Step-1
Step-2
Step-3
(a) Traditional global aggregation scheme
(b) Our step-mixture scheme
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).
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 Fig- ure B While traditional graph convolution methods consider aggregated information within three steps by A(A(AXW()) (())))))))))))))) )2()) our method can take all previous aggregations into account by (A" A-XW X A&WW).
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 Hmult (see Equations and As described Equation we employ multi-head attention, where mmuti is the concatenation of m attention layers and is the coefficient of attention computed using concatenated features of nodes and its neighboring nodes.
ZGESM softmax || À H W1), k=
H || (Wa
By incorporating attention to our base model, we can avoid or ignore noisy parts the graph, providing guide for random walk (Lee et al. 2018). Utilizing attention also improve com- binatorial generalization for inductive learning, where training and testing graphs are completely different. In partieular, datasets with the same structure but different node information benefit

---

Under review as a conference paper at ICLR 2020
Table 1: Summary of datasets used in the experiments.
Nodes (Graphs)
Type
Datasets
Features
Edges
Classes
Label rate
Total
Training
Validation
Test
Cora
2,708
140
500
1,000
1,433
5,429
7
5.1%
T
Citeseer
3,327
120
500
1,000
3,703
4,732
6
3.6%
Pubmed
19,717
60
500
1,000
500
44,338
3
0.3%
PPI
56,944
44,906
6,514
5,524
50
8,187
121
(24)
(20)
(2)
(2)
Transductive learning datasets consist of one graph and use a subset of the graph for training. Inductive learning datasets consist many graphs and use a graphs training and unseen graphs for testing.
from our method because these datasets can only be distinguished by node information. Focusing on node features for aggregation
thus provide more reliable results in inductive learning.
The time complexity of our base model is O(s x x h), where 8 is the maximum number of steps considered for aggregation, / is the number of non-zero entries in the adjacency matrix, and h the hidden feature dimension. As suggested by Abu-EI-Haija et (201)), we can assume h << | under realistic assumptions. Our model complexity is, therefore, highly efficient with time complexity ((s x 1). 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 rep- resent documents and the edges correspond to citation links. The edge configuration is undirected, and the feature of each node consists of word representations of document. Detailed statistics of the datasets are described in Table
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 1% for Cora, 3.6% for Citeseer, and 0.3% for Pubmed can be learned. In addition experiments with public label rate settings, we conducted experiments using datasets where labels were randomly split into smaller set for training. To check whether model can propagate node information to the entire graph, we reduced the label rate Cora to 3% and 1%, Citeseer to 1% and 0.5%, Pubmed to 0.1 1.1% and followed the experimental settings of Li jet 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-proter 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 remains completely unobserved during training. Each node 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-ard 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
leamable graph convolution (LGCN) (Gao 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 (Adal. Net) (Liao al. 2019) and maximal entropy transition (PAN) (Ma al. 2019). We
5

---

Under review as a conference paper at ICLR 2020
Table 2: Experimental results on the public benchmark datasets. Evaluation metrics on transduc- tive and inductive learning datasets are classification accuracy (%) and Fl-score, respectively. Top-3 results for each column are highlighted in bold, and top-1 values are underlined.
Transductive
Inductive
Cora public (5.1%)
Citeseer public (3.6%)
Pubmed public (0.3%)
Method
LP (Xiaojin & Zoubin 2002
68.0
45.3
63.0
Deep Walk PPerozzi al. 2014
67.2
43.2
65.3
Cheby (Defferrard
2016
81.2
69.8
74.4
Planetord Yang el al. 2016
75.7
64.7
77.2
GCN Kipp & Welling 2017
81.5
70.3
79.0
GraphSAGE (Hamilton
2017
0.612
GAT /Veličkovic
2018
83.0
72.5
79.0
0.973
I.GNN (Gao et al. (2088)
83.3
73.0
79.5
0.772
JK-LSTM (Xu ct al. 2018
0.976
AGNN (Thekumparampil et
2018
83.1
71.7
79.9
Union (Li
2018)
80.5
65.7
78.3
"APPNP (Klicpraa (Klipera el... 2019
83.2
71.7
79.7
SGC [Wu al (0199)
81.0
71.9
78.9
MixHop (Abu-El-Hain ct al.
2019
81.9
71.4
80.8
GWNN (Xu ct al.
(019)
82.8
71.7
79.
AdaLNet Q
2019
80.4
68.7
78.1
PAN (Ma él al.
2019
82.0
71.2
79.2
GSM (our base model)
82.8
71.7
80.3
0.753
GESM (GSM+attention)
84.4
72.6
80.1
0.976
Best experimental results through our own implementation
further include models that utilize teleport term during propagation APPNP (Kliepera et al. 2019). conduct convolution via spectral filters such as ChebyNet (Defferrard et al. 2016). GCN (Kipf & Welling 2017), SGC (Wu et al., (019a), and GWNN (Xu et al.] 2019) and models that adopt attention between nodes, such as GAT (Veličković et al., 2018) and AGNN (Thekumparampil al., 2018).
For inductive learning tasks, compare model against four baseline models. This includes graphs that use sampling and aggregation (GraphSAGE-LSST (Hamilton et al.] (017). and jumping-knowledee (JK-LSTM) (Xu 2018), along with GAT and LGCN which used in the transductive setting.
4.3 EXPERIMENTAL SETUP
Regarding the hyperparameters of our transductive learning models, 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 E [64, 512} and the maximum number of steps used for aggregation E {10, 30) were adjusted for each dataset. We trained for a maximum of 300 epochs with L2 regularization À 0.003 and learning rate Ir 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 10 for GSM, and used for inductive learning (Veličković et al. (0188) We trained our models for maximum of 2,000 epochs with learning rate Ir 0.008. The evaluation metric the micro-F1 score, and report the averaged results of 10 runs.
5, 15 for GESM. L2 regularization and dropout were not
For all the models, the nonlinearity function of the first fully connected layer exponen- tial linear unit (ELU) (Clevert et al.] 2016). Our models were initialized using Glorot initializa- tion (Glorot & Bengio 2010) and were trained minimize the cross-entropy loss using the Adam

---

Under review as a conference paper at ICLR 2020
Table 3: 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.
Cora
Citeseer
Pubmed
Method
1%
3%
0.5%
1%
0.1%
LP (Xiaoiin Zoubin
2002
62.3
67.5
34.8
40.2
65.4
Cheby (Dellerrard el al. 2016
52.0
70.8
31.7
51.2
GCN Kipl & Welling
2017
62.3
76.5
43.6
55.3
65.9
Union [I al 2018)
69.9
78.5
46.3
59.1
70.7
"JK JK-GCNIP XUI
2018)
65.1
76.8
37.1
55.3
71.1
APPNP (Klippeaa al.
2019
67.6
80.8
40.5
59.9
70.7
SGC [Wü et al. 2019a)
77.2
41.0
71.7
AdaL.Net (Liao et al. 2019)
67.5
77.7
53.8
63.3
72.8
GSM (our base model)
68.2
81.6
45.6
62.6
73.0
GESM (GSM+attention)
70.5
81.2
53.2
62.7
73.8
Best experimental results through implementation
optimizer (Kingma & Ba 2013). 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 summarizes the comparative evaluation experiments for transductive and inductive learning tasks. In general, not only are there 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 equivalent to those of other methods. As can be identified from the table, our base model GSM, which is com- putationally 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, base model GSM, which employs edge-based aggregation method, does not invariably obtain the highest accuracy. However, our model with attention, GESM, significantly improves performance
GSM by learning the importance 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ć al. (2018). in which reducing the influence of structural information improved generalization.
neighborhood nodes,
Results on datasets with low label rates. To demonstrate that our methods can consider global infor- mation, we experimented on sparse datasets with low label rates of transductive learning datasets. As indicated Table 3 our models show remarkable performance even on the dataset with low label rates, In particular, and 3 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 methods adaptively selecting node information from local and global neighborhoods, and allowing peripheral nodes to receive information.
further observe the superiority of methods by inspecting Ta-
5.2 MODEL ANALYSIS
Oversmoothing and Accuracy. As shown in Figure 4a GCN (Kipf & Welling 2017). SGC (Wu al. 2019a), and GAT (Veličković et al. 2018) suffer from oversmoothing. GCN and GAT show

---

Under review as a conference paper at ICLR 2020
Accuracy
Train Accuracy
0.5
GCN
JK Net
Ket
# of stops
of steps
(a) Training accuracy comparison according to (b) Test accuracy of JK-Net GSM using number of propagation steps.
concatenated features after the step.
Figure 4: Effect of the step size on model performance Cora.
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 is for JK-Net to maintain performance. GSM, on the other hand, maintains steady performance, which confirms that GSM does not collapse even for large step sizes.
0.9
0.8
Test Accuracy
0.6
0.5
GSM
GESM
public (5.1%)
public (5.1%)
0.4
3%
1%
1%
0.3
# of steps
Figure Accuracy comparison for various label rates according to step size.
We also observe the effect on accuracy the number of steps increases under three labeling condi- tions for GSM and GESM. represented in Figure [ it is evident that considering remote nodes can contribute to the increase in accuracy. By taking into account more data within a larger neigh- borhood, 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, pre- sumably 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 large. The inference time of GESM is much faster than GAT' (Veličković et al. 2018) while providing higher accuracies and stable results (see
8

---

Under review as a conference paper at ICLR 2020
1.2
GCN
GAT
1.0
GESM
Time(s)
0.6
0.4
0.2
0.0
# of steps
Figure 6: Inference time of various models as the step size increases for Cora dataset.
Appendix A). Our methods are both fast and accurate due to the sophisticated design with a mixture of random walk steps.
Embedding Visualization. Figure visualizes the hidden features Cora from our models by using
CSM
CESM
Figure 7: t-SNE plot of the last hidden layer trained on the Cora dataset.
the t-SNE algorithm (Maaten & Hinton 2008). The figure illustrates the difference between edge- based and node-based aggregation. While the nodes are closely clustered in the result from GSM, they scattered in that of GESM. According to the results in Table 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).
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 fur- ther refine our base model, we have presented GESM, which explicitly leverages node information (see Appendix B). The results from extensive experiments show that models successfully achieve state-of-the-ar or competitive performance for both transductive and inductive learning tasks on four benchmark graph datasets. As future directions, will refine our method that utilizes node information to improve the computational efficiency regarding attention. In addition, we will extend GESM that can be applied real-world large scale graph data.
REFERENCES
Sami Abu-aa-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolution

---

Under review as a conference paper at ICLR 2020
architectures via sparsified neighborhood mixing. International Conference Machine Learning (ICML). 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. International Conference on Learning Representations (ICLR), 2015.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Re- lational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: N0M3v/8800.026.1 2018.
Djó Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). International Conference on Learning Representations (ICLR), 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Hongyang Gao and Shuiwang Ji. Graph representation learning via hard and channel-wise attention networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 741-749. ACM, 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424. ACM, 2018.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Random walk based fake account detection in online social networks. In 2017 47th Annual IEEE/FIP International Conference Dependable Systems and Networks (DSN), pp. 273-284, IEEE, 2017.
Kyung-Min Kim, Donghyun Kwak, Hanock Kwak, Young-Jin Park, Sangkwon Sim, Jae-Han Cho, Minkyu Kim, Jihun Kwon, Nako Sung, and Jung-Wor Ha. Tripartite heterogeneous graph prop- agation for large-scale social recommendation. arXiv preprint arXiv:1908.02555 2019.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. International
Conference on Learning Representations (ICLR), 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference Learning Representations (ICLR). 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günneeann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representa- tions (ICLR), 2019.
John Boaz Lee, Ryan A Rossi, Sungchul Kim, Nesreen K Ahmed, and Eunyee Koh. Attention models in graphs: A survey, arXiv preprint 1807 2018
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Secona AAAI Conference on Artificial Intelligence, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. International Conference on Learning Representations (ICLR), 2019.
10

---

Under review as a conference paper at ICLR 2020
Sitao Luan, Mingde Zhao, Xiao-Wer Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. Advances in neural information processing systems, 2019.
Zheng Ma, Ming Li, and Yuguang Wang. Pan: Path integral based convolution for deep graph neural networks. International Conference Machine Learning (ICML), 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9NNov)2559-2200, 2008
Ed Manley. Estimating urhan traffic patterns through probabilistic interconnectivity of road network junctions. PloS one, ((5))e0127095, 2015.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 701-710. ACM, 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint /8/.:/888.0. 2018.
Gilbert Strang. Introduction to linear algebra, volume 3.
Press Wellesley,
MA, 1993.
Kiran K Thekumparampil, Chong Wang. Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv:1803.03755 2018
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua
Bengio. Graph attention networks. International Conference Learning Representations
(ICLR), 2018
Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. In Seccry-Secondaan AAAI Conference Artificial Intelligence. 2018.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Wein- berger. Simplifying graph convolutional networks. International Conference Machine Learning (ICML), 2019a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A 2019b.
comprehensive survey on graph neural networks. arXiv preprint
Zhu Xiaojin and Ghahramani Zoubin. Learning from labeled and unlabeled data with label propa- gation. Tech. Rep.. Technical Report CMU-CALD-02-107 Carnegie Mellon University, 2002.
Bingbing Xu, Huawei Shen, Qi Cao. Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. International Conference on Learning Representations (ICLR), 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. International Conference on Machine Learning (ICML), 2018
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. International Conference on Machine Learning (ICML), 2016.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint 17Xiv:1709.04855, 2017.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):110--1198, 2017.

---

Under review as a conference paper at ICLR 2020
Table 4: Summary of datasets used in the additional experiments.
Classes
Features
Nodes
Edges
Label rate
Coauthor CS
15
6,805
18,333
100,227
1.6%
Coauthor Physics
8,415
34,493
282,455
0.2%
Amazon Computers
10
767
13,381
259,159
1.4%
Amazon Photo
745
7,487
126,530
2.1%
Table Average test set accuracy and standard deviation over 100 random train/validationntes. splits with 20 runs. Top-3 results for each column are highlighted in bold, and top-1 values are underlined.
Coauthor CS
Coauthor Physics Amazon Computers
Amazon Photo
MLP
88.3 + 0.7
88.9 + 1.1
44,9 + 5.8
69.6 = 3.8
LogReg
86.4 0.9
86.7 + 1.5
64.1 + 5.7
73.0 6.5
I.P (Xiaojin & Zoubin
2002
73.6 + 3.9
86.6 + 2.0
70.8 +
72.6 11.1
GCN (Kipl & Welling
2017
91.1 + 0.5
92.8 + 1.0
82.6 + 2.4
91.2 = 1.2
GraphSAGE (Hamilon el al
2017
91.3 + 2.8
93.0 1 0.8
82.4 1 1.8
91.4 = 1.3
GAT VVllčkkvii al.
2018
90.5 1 0.6
92.5 1 0.9
78.0 1: 19.0
85.7 20.3
GSM (our base model)
91.8 1 0.4
93.3 1 0.6
79.2 1: 2.0
89.3 = 1.9
GESM (GSM+atteetion)
92.0 1 0.5
93.7 1 0.6
79.3 1 1.7
90.0 2.0
A EXPERIMENTS ON OTHER DATASETS
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" in which nodes are authors, features represent the article keyword for each au- thor'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-worde of product views, and class lahels represent product categories. Detailed statistics of the datasets are described in Table 4 and followed the experimental setup of Shchur al. (2018).
We used the same values for each hyperparameter (unified size: GAT and GESM: 8) without tuning. The results in Table[5]prov that our proposed methods do not overfit to particular dataset. Moreover, in comparison to GAT, the performance of GESM is more accurate, and stable.
64, step size: 15, multi-head for
B ATTENTION VISUALIZATION
3800
3823
3200
600
210
(a) Basic attention.
(b) Our attention.
Figure 8: Visualization of attention distribution.
12

---

Under review as a conference paper at ICLR 2020
We visualized the distribution of attention vectors. TigureBaplots 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 conjecture that GESM slightly adjusts the weight values, contributing to improved performance.
13


Reviews:
[{"review_id": "SJlsm7i6YH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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.\n\nHowever, there are a few weak points which should explain my overall score:\n\n1. 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].\n\n2. The GESM model is not fully understandable since it is missing a formal description for computing $\\alpha$. It is only said that $\\alpha$ is computed using the concatenation of features from the central node and its neighbors. Can you elaborate how exactly you compute $\\alpha$, 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.\n\n3. The final prediction layer with weight matrix W_1 operates on all propagation layers, resulting in a parameter complexity of $O(s  h c)$, where $c$ is the number of classes. With $s=30$ and $h=512$, 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 $O(n  s^2  h^2  c)$ which does not nearly match your reported complexity.\nFurthermore, 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.\n\n4. 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.\n\n5. Since the used benchmark datasets are already reasonably explored, authors are advised to include evaluation on other datasets as well, e.g., from [6].\n\n6. The transition matrix $P$ is missing self-loops to match with the results of Figure 1. Since you already define $P$ analogously to $\\hat{\\tilde{A}}$, you should focus on one notation for consistency reasons.\n\n[1] Wu et al.: Simplifying Graph Convolutional Networks\n[2] Klicpera et al.: Predict then Propagate: Graph Neural Networks meet Personalized PageRank\n[3] Xu et al.: Representation Learning on Graphs with Jumping Knowledge Networks\n[4] Hamilton et al.: Inductive Representation Learning on Large Graphs\n[5] Kipf and Welling: Semi-Supervised Classification with Graph Convolutional Networks\n[6] Shchur et al.: Pitfalls of Graph Neural Network Evaluation\n\n----------------------------\nUpdate 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\".\n\nI have raised my score from \"5: Weak Reject\" to \"6: Weak Accept\".", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg4oGBstr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a graph neural network model that aims at improving the feature aggregation scheme to better handle distant nodes, therefore mitigating the “smoothing” problem of classic averaging.\n\nI find the paper clearly motivated and easy to follow, although some sentences could be streamlined and some repetitions could be removed. For instance last paragraph in page 3, this should be clear already and should be restated.\n\nOne thing that is not clear is how does the model cope with the increase in feature dimensionality due to the concatenation over different steps. Isn’t this leading to overfitting? Did the authors experiment with other schemes such as averaging or gating? If so it would be nice to see the results for each of the configurations as it is not clear to me what should be chosen a-priori.\n\nExperiments are nicely executed and the proposed approach is compared against a rich array of other models. Results are state-of-the-art and also the analysis of the model is interesting, i.e. it doesn’t diverge when increasing # steps at test time.\nHow does the attention vector look like? Does it tend to peak at a given k, or is it more uniformly distributed? \n\nHow does the model compare to having k GAT layers, each constrained to use neighboring nodes at step k as input for the attention computation? Did the authors experiment on this?\n\nOverall I like the work but find the novelty quite limited, more effort could have been put into motivating the soundness of the use of multiple random walks. Perhaps some theory could be developed to make the paper stronger.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1eQBPadqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new GNN model to address the common issue “oversmoothing”, namely, Graph Entities with Step Mixture via random walk (GESM). Basically, it integrates both mixture of various steps through random walk, and graph attention network, and demonstrates that it can overcome the SOTA on popular benchmarks.\n\nDetailed comments: \n\n* The oversmoothing problem has been mentioned many times in this paper, yet little has been demonstrated through experiments that the new model can solve the oversmoothing issue. It would be great to show the performance improvement while oversmoothing is mitigated.\n\n* The proposed idea is very similar to the following paper: “Revisiting Graph Neural Networks: All We Have is Low-Pass Filters”. Both use low-pass filtering (via transition matrix) to propagate the information on the graph. I suggest a detailed discussion with this work.\n\n* The major concern of this work is the weak novelty. It combines GAT with multiple random walk under the GNN framework. While this is working well on most GNN datasets, it is not very new by itself.\n\n* Some experimental results are comparable to existing methods, as shown in Table 2 and 3. Maybe the time complexity is the major contribution of this paper. A head-to-head running time comparison with SOTA in Table 4 will be helpful.\n\n* Fewer methods are compared in Table 3 than in Table 2. Can authors add more in Table 3 to give a better demonstration?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers are concerned about this paper while the other one is slightly positive. A reject is recommended.
Decision: Reject