Are Graph Convolutional Networks Fully Exploiting the Graph Structure?
Authors: Davide Buffelli
Fabio Vandin
Venue:  (2021)
Keywords: Graph Representation Learning
Graph Neural Networks
Random Walks

Abstract: Graph Convolutional Networks (GCNs) represent the state-of-the-art for many graph related tasks. At every layer, GCNs rely on the graph structure to define an aggregation strategy where each node updates its representation by combining information from its neighbours. A known limitation of GCNs is their inability to infer long-range dependencies. In fact, as the number of layers increases, information gets smoothed and node embeddings become indistinguishable, negatively affecting performance. In this paper we formalize four levels of injection of graph structural information, and use them to analyze the importance of long-range dependencies. We then propose a novel regularization technique based on random walks with restart, called RWRReg, which encourages the network to encode long-range information into node embeddings. RWRReg does not require additional operations at inference time, is model-agnostic, and is further supported by our theoretical analysis connecting it to the Weisfeiler-Leman algorithm. Our experimental analysis, on both transductive and inductive tasks, shows that the lack of long-range structural information greatly affects the performance of state-of-the-art models, and that the long-range information exploited by RWRReg leads to an average accuracy improvement of more than $5\%$ on all considered tasks.

Under review as a conference paper at ICLR 2021
ARE GRAPH CONVOLUTIONAL NETWORKS FULLY EXPLOITING THE GRAPH STRUCTURE?
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Convolutional Networks (GCNs) represent the state-of-the-art for many graph related tasks. At every layer, GCNs rely on the graph structure to define an aggregation strategy where each node updates its representation by combining information from its neighbours. A known limitation of GCNs is their inability infer long-range dependencies. In fact, as the number of layers increases, infor- mation gets smoothed and node embeddings become indistinguishable, negatively affecting performance. this paper we formalize four levels of injection of graph structural information, and use them analyze the importance of long-range de- pendencies. We then propose a novel regularization technique based on random walks with restart, called RWRReg. which encourages the network to encode long-range information into node embeddings. RWRReg does not require addi- tional operations inference time, is model-agnostic, and further supported by our theoretical analysis connecting it to the Weisfeiler-Lemaa algorithm. Our ex- perimental analysis, on both transductive and inductive tasks, shows that the lack of long-range structural information greatly affects the performance of state-of- the-art models, and that the long-range information exploited by RWRReg leads to average accuracy improvement of more than 5% on all considered tasks.
INTRODUCTION
Graphs are a ubiquitous data representation many real world phenomena, with applications rang- ing from social networks, to chemistry, biology, and recommendation systems (Zhou et al.) [2018). Graph Neural Networks (GNNs) are the generalization deep learning for graph structured data, and have received a huge amount of attention from the research community.
One class GNN models, the Graph Convolutional Network (GCN), has demonstrated to be ex- tremely effective and is the current state-of-the soffthe-art art for tasks such graph classification, node clas- sification, and link prediction. GCNs adopt a message passing mechanism where at each layer every node in the graph receives message (e.g. feature vector) from its 1-hop neighbours. The massages are then aggregated with permutation invariant function (e.g. by mean or sum) and are used to up- date the node's 's representation vector with learnable, possibly non-linear, transformation. The final node embedding vectors are used to make predictions, and the whole process is trained end-to-end. Empirically, the best results are obtained when the message passing procedure is repeated 2 times, as a higher number of layers leads to ovor-smog (Li et al. 2018 Xu et al. 2018b). Thus, GCNs are only leveraging the graph structure in the form of the 2-hop or 3-hop neighbourhood of each node. A direct consequence of this phenomenon is that GCNs are not capable of extracting and exploiting long-range dependencies between nodes.
Random walks with restart (Page et al. 1998) have proven to be very effective at quantifying how closely related two nodes are (Tong et al. 2006),, regardless of their distance in the graph. In fact random walks with restart can capture the global structure of graph, and have been used for many tasks including ranking, link prediction, and community detection (Jin et al. 2019). On the other hand, random walks with restart do not consider node features, which are instead heavily exploited by GCNs. Combining GCNs and random walks with restart could then provide a powerful method to fully exploit the information contained in graph.

---

Under review as a conference paper at ICLR 2021
In this work we not interested in defining state-of-the-an results, proposing novel GNN models. We focus on studying the impact of long-range dependencies, and identifying a first strategy, which can easily be applied to any existing model, incorporate this information.
Our Contribution. In more detail, assess whether the injection of information the graph structure that can not be captured by 2 or 3-hop neighbourhoods has a significant impact on the performance of several state-of-ther Firstly, we propose and formalize four different levels of structural information injection. Secondly, propose novel and practical regularization strategy, Random Walk with Restart Regularization (RWRReg), to inject structural information using random walks with restart, allowing GCNs to leverage rongerange dependencies. RWRReg does not require additional operations at inference time, maintains the sermutationiivvariane of GCN models, and leads to an average 5% increase in accuracy on both node classification, and graph classification. Thirdly, we prove a theoretical result linking random walks with restart and the Weisfeiler-L Leman algorithm, providing theoretical foundation for their use in GCNs. Fourthly, we test how the injection of structural information can impact the performance of 6 different GCN models on node classífication, graph classification, and on the task triangle counting. Results show that current state-of-the-are models lack the ability to extract long- raage information, and this is severely affecting their performance.
GCN models. In this regard, contributions are fourfold.
INJECTING LONG-RANGE INFORMATION IN GCNS
To test if GCNs missing on important information that is encoded in the structure of graph, we inject additional structural information into existing GCN models, and test how the performance of these models changes in several graph related tasks. Intuitively, based model's performance when injected with different levels of structural information, we can understand how much infor- mation is captured by GCNs, and if this additional knowledge can improve performance on the considered tasks. In the rest of this section we present the notation used throughout the paper, the four levels of structural information injection that consider, and analytical result proving the effectiveness of using information from random walks with restart.
2.1 PRELIMINARIES
We use uppercase bold letters for matrices (M), and lowercase bold letters for vectors (v). We plain letters with subscript indices to refer to a specific element of matrix (Mi,). ) or of vector (v)). We refer to the vector containing the i-th row of a matrix with the subscript "i, 1 (M..), while we refer to the i-th column with the subscript ":, 1" (M.)).
For graph 9 (V, E), where V f1..., .., n) is the set of nodes and V V is the set of edges, the input is given by tuple (X, A). X is an n x d matrix where the i-th row contains the d-dimensional feature vector of the i-th node, and is the a X n adjacency matrix. For the sake of clarity we restrict our presentation to undirected graphs, but similar concepts can be applied to directed graphs.
2.2 STRUCTURAL INFORMATION INJECTION
We consider four different levels of structural information injection, briefly described below. We remark that not the injection strategies presented in this section are made for practical use, as the scope of these strategics is to help understand the importance of missing structural information. In particular, in Section we study the impact of the different types of structural information injection, and hence quantify the information that is not exploited by current GCN models. We then discuss scalability and practicality aspects in Section 5
Adjacency Matrix. We concatenate each node's s adjacency matrix row to its feature vector. This explicitly empowers the GCN model with the connectivity of each node, and allows for higher level structural reasoning when considering a neighbourhood (the model will have access to the connectivity of the whole neighbourhood when aggregating messages from neighbouring nodes).
2

---

Under review as a conference paper at ICLR 2021
Random Walk with Restart (RWR) Matrix. We perform random walks with restart (RWR) (Page et al., 1998) from each node v, thus obtaining a n-dimensional vector (for each node) that gives score of how much v is "related" to each other node in the graph. We concatenate this vector of RWR features to each node's feature vector. The choice of RWR is motivated by their capability capture the relevance between two nodes in graph TTng et al., 2006), and by the possibility to modulate the exploration of long-range dependencies by changing the restart probability. Intuitively, RWR starting at node is very likely to visit a node (e.g. there are multiple paths that connect the two), then there will be high score in the RWR vector for v at position This gives the GCN model higher level information about the structure of the graph that goes beyond the 1-
hop neighbourhood of each node, and, again, it allows for high level reasoning on neighbourhood connectivity.
RWR Regularization. We define a novel regularization term that pushes nodes with mutually high RWR scores to have embeddings that are close to each other (independently of how far they are in the graph). This regularization term encourages the message passing procedure defined by GCNs, that acts neighbouring nodes, to produce embeddings where pairs of nodes with high RWR score have similar representations. Therefore, the model is encouraged to extract global information, from local communications. The final embeddings range information provided by RWR. Let S be the n x n matrix with the RWR scores. We define the RWRReg (Random Walk with Restart Regularization) loss as follows:
then combination of local information and long-
LewRReg
Σ .EEV
H Hj.11
where H is a matrix of size n x containing d-dimensional node embeddings that are in between graph convolution layers (see Appendix A for the exact point in which H is considered for each model). With this approach, the loss function used to train the model becomes: L. = Loiiinna + ARRRReg where Corigiaat is the original loss function for each model, and À is a balancing term.
RWR Matrix RWR Regularization. We combine the previous types of structural knowl- edge injection. The intuition is that it should be easier to enforce the RWRReg by having the ad- ditional long-range information provided by the RWR features. We expect this type of information injection to have the highest impact on performance of the models on downstream tasks.
2.3 RELATIONSHIP BETWEEN THE 1-WEISFEILER- LEMAN ALGORITHM AND RWRS
In this section we provide analytical evidence that the information from RWR significantly em- powers GCNs. In particular, we prove an interesting connection between the 1-Weisfeiler-Leme (1-WL) algorithm and RWR.
The 1-WL algorithm for graph isomorphism testing uses an iterative coloring, or relabeling, scheme, in which all nodes are initially assigned the same label (e.g., the value 1). It then iteratively refines the color of each node by aggregating the multiset of colors in its neighborhood. The final feature representation of graph is the histogram of resulting node colors. (For a more detailed description of the 1-WL algorithm we refer the reader to Shervashidze et al. (2011))) It is known that there are non-isomorphic graphs that are not distinguishable by the 1-WL algorithm, and that n iterations are enough to distinguish two graphs of n vertices which are distinguishable by the 1-WL algorithm. There is a well known connection (Kipf & Welling 2017 Xu al.] 2018a) between 1-WL and differentiable approximation of the algorithm. In aggregation-based GCNs, which can be seen iterations by the 1-WI. algorithm, can be distin- particular, graphs that can be distinguished à guished by certain GCNs in l message passing iterations (Morris et al. 2019))
Here, we prove that graphs that are distinguishable by 1-WL in iterations have different feature representations extracted by RWR of length k. Given graph G = (V, E), we define its k-step RWR representation as the set of vectors Ie = [rv,ar.... ................................ To.u,, v E V, where each entry Te,u describes the probability that RWR of length i starting in ends in u E V.
Proposition 1. Let G1 = (V1, E1) and G2 (V2, E2) be two non -on-isomorphic graphs for which the 1- WL algorithu terminates with the correct answer after l iterations and starting from the labelling of all 1 Then the k-step RWR representations of G1 and G2 are different.
3

---

Under review as a conference paper at ICLR 2021
The proof can be found in Appendix Given that & iterations of the 1-WL algorithm require GCNs of depth & to be performed, but in practice GCNs are limited to depth 2 or 3, the result above shows that RWR can empower GCNs with relevant information that is discarded in practice.
Recent work (Micali & Zhu 2016) has shown that anonymous random walks (i.c., random walks where the global identities of nodes not known) of fixed length starting at node a sufficient to reconstruct the local neighborhood within a fixed distance of a node u (Micali & Zhu 2016). Subsequently, anonymous random walks have been introduced in the context of learning graph rep- resentations (Ivanov & Burnaev 2018). Such results are complementary to ours, since they assume access the distribution of entire walks of given length, while our RWR representation only stores information on the probability of ending in a given node, In addition, such works do not provide a connection between RWR and 1-...
CHOICE OF MODELS
In order test the effect of the different levels of structural information injection and to obtain results that are indicative of the whole class of GCN models, our experimental study covers most of the spatial graph convolution techniques. We conceptually identify four different categories from which we select representative models.
Simple Aggregation Models. Such models fall into the message passing framework (Gilmer et al, 2017) and utilize a "simple" aggregation strategy, where each node receives messages (e.g. feature vectors) from its neighbours, and uses the received messages to update its embedding vector. As representative choose GCN (Kipf & Welling 2017), one of the fundamental and widely used GNNs models. We also consider GraphSage (Hamilton et al.) 2017). as represents a different aggregation strategy where set of neighborhood aggregation functions are learned, and a sampling approach is used for defining fixed size neighbourhoods.
Attention Models. Several models have used an attention mechanism a GNN scenario (eee et al. 2018a by Veličković et al. 2018 Zhang et al. 2018). While they fall into the message passing framework, we consider them separately as they employ a more sophisticated aggregation scheme. As a representative we focus on GAT (Veličković et al. 2018). the first to present attention mechanism over nodes for the aggregation phase, and currently one of the best performing models on several datasets. Furthermore, it can be used in an inductive scenario.
Pooling Techniques. Pooling on graphs is very challenging task, since it has to take into account that each node might have different sized neighbourhood. Among the methods that have been proposed for differentiable pooling on graphs (Cangea et al.) 2018 Ying et al., 2018b Diehl et al.) 2019 Gao & Jil 2019 Lee et al.] 2019). we choose Dofl (Ying al., (018b) for its strong empirical results. Furthermore, it can learn to dynamically adjust the number of clusters (the number a hyperparameter, but the network can learn to use fewer clusters if necessary).
Beyond WL. Morris et al. (2019) prove that message-passing GNNs cannot be more powerful than the 1-WL algorithm, and propose k-GNNs, which rely on a subgraph message-passing mechanism and are proven to be powerful as the k- &-WL algorithm. Another approach that goes beyond the WL algorithm was proposed by Murphy et al. (2019). Both models are computationally intractable in their initial theoretical formulation, so approximations
needed. As representative choose t-GNNs, to test if subgraph messaag-passsng is affected by additional structural information.
4 EVALUATION OF THE INJECTION OF STRUCTURAL INFORMATION
We now present our framework for evaluating the effects of the injection of structural information into GNNs, and the results of experiments. We consider one transductive task (node classifica- tion) and two inductive tasks (graph classification, and triangle counting), and we further study the impact of the restart probability of RWR on the results.
We use each architecture for the task that better suits its design: GCN, GraphSage, and GAT for node classification, and DiftPool and k-GNN for graph classification. We add adapted version of
4

---

Under review as a conference paper at ICLR 2021
Table 1: Node classification accuracy results of different models with added Adjaceney matrix fea-
tures (AD), RWR features (RWR), RWR Regularization (RWRReg), and RWR features + RWR
Regularization (RWR-RWRReg).
Model
Structural
Dataset Pubmed
Information
Cora
Citeseer
none
0.799 = 0.029
0.776 + 0.022
0.663 + 0.095
AD
0.806 = 0.035
0.779 = 0.070
0.653 + 0.104
GCN
RWR
0,817 = 0.025
0.782 = 0.042
0.665 + 0.098
RWRReg
0.861 + 0.025
0.799 + 0.034
0.686 + 0.096
RWR+RWRReg
0.842 + 0.026
0.811 0.037
0.690 - 0.102
none
0.806 = 0.017
0.807 0.016
0.681 + 0.021
AD
0.803 = 0.014
0.803
0.688 + 0.020
GraphSage
RWR
0.816 = 0.014
0.017
0.693 + 0.019
RWRReg
0.841 + 0.016
0.017
0.721 + 0.021
RWR+RWRReg
0.837 + 0.015
+.010
0.728 + 0.020
none
0.815 + 0.021
0.804
0.664 + 0.008
AD
0.823 + 0.019
0.796
0.672 0.017
GAT
RWR
0.833 = 0.020
0.009
0.686 + 0.009
RWRReg
0.824 = 0.022
0.811 0.013
0.702 + 0.013
RWR+RWRReg
0.848 + 0.019
0.828 + 0.010
0.701 + 0.011
GCN for graph classification, as a common strategy for this task is to deploy a node-level GNN, and then apply readout function combine node embeddings into global graph embedding vector.
With regards to datasets, for node classification we considered the three most used benchmarking datasets in literature: Cora, Citeseer, and Pubmed (Sen al. 2008). Analogously, for graph classifi- cation we chose three frequently used datasets: ENZYMES, PROTEINS, and D&D (Kersting et al.) 2016 Dataset statistics can be found in Appendix
For all the considered models we take the hyperparameters from the implementations released by the authors. The only parameter tuned using the validation set the balancing term when RWRReg is applied. We found that the RWRReg loss tends to be larger than the Cross Entropy loss for prediction, and the best values for À lie in the range [10-9. 10- For all the RWR-based techniques used a restart probability of 0.15 (The effects of different restart probabilities are explored below.) Detailed information on our implementations can be found in Appendix A
Node Classification. For each dataset follow the approach that has been widely adopted in literature: we take 20 labeled nodes per class as training set, 500 nodes as validation set, and 1000 nodes for testing. Most authors have used the train/validation/test split defined by Yang al.) (0116) Since we want to test the general effect of the injection of structural information, we differ from this approach and we not sample 20 nodes per class for training, 500 random nodes for validation, and 1000 random nodes for testing. We then report mean and standard deviation for the accuracy on the test set over these 100 runs.
roly rely on a single split. We perform 100 runs, where at each run randomly
Results are summarized Table where we observe that the simple addition of RWR features to the feature vector of each node is sufficient to give performance gain (up to 2%). The RWRReg term then significantly increments the gain (up to 7.5%), showing that even for the task of node classification structural information and long-range information are important, confirming that only looking at neighbours and close nodes not enough.
Graph Classification. Following the approach from Ying et al. (0118) and Morris et al. (2019) we use 10-fold cross validation, and report mean and standard deviation of the accuracy on graph classification. Results summarized in Table 2 The performance gains given by the injection of structural information are even more apparent than for the node classification task. Intuitively, the
We use 0.15 as is common default value used in many papers and software libraries. Source code provided Supplementary Material and will be made publicly available upon acceptance.
5

---

Under review as a conference paper at ICLR 2021
Table 2: Graph classification accuracy results of different models with added Adjacency matrix
features (AD), RWR features (RWR), RWR Regularization (RWRReg), and RWR features + RWR Regularization (RWR+RWRReg)
Model
Structural
Dataset D&D
Information
ENZYMES
PROTEINS
none
0.570 + 0.052
0.755 0.028
0.740 0.035
AD
0.591 0.076
0.779
0.022
0.775 0.042
GCN
RWR
0.584 = 0.055
0.775 0.023
0.784 = 0.034
RWRReg
0.621 0.041
0.786 0.024
0.785 0.036
RWR+RWRReg
0.616 + 0.065
0.790 + 0.023
0.795 + 0.032
none
0.661 0.031
0.793 = 0.022
0.813 = 0.017
AD
0.711 = 0.027
0.837 0.020
0.821 0.039
DifiPool
RWR
0.687 + 0.025
0.824 = 0.028
0.783 = 0.043
RWRReg
0.733 = 0.032
0.822 0.025
0.820 0.038
RWR+RWRReg
0.721 + 0.039
0.840 + 0.024
0.834 - 0.038
none
0.515 + 0.111
0.756 0.021
0.763 0.043
AD
0.572 + 0.063
0.778 0.020
0.751 + 0.034
k-GNN
RWR
0.573 = 0.077
0.794 + 0.022
0.781 0.028
RWRReg
0.582 + 0.075
0.787 0.022
0.780 0.028
RWR+RWRReg
0.571 = 0.080
0.786 = 0.021
0.785 + 0.026
structure of the nodes in a graph is fundamental for distinguishing different graphs. Most notably, the addition of the adjacency features sufficient give large performance boost (up 11 1)).
Surprisingly, models like DiffPool and k-GNN show an important difference in accuracy (up to 10%) when there is injection of structural information, meaning that even the most advanced meth- ods suffer from the inability to properly exploit all the structural information encoded in graph.
Impact of RWR Restart Prob- ability. We tested how perfor- mance change with different restart probabilities. Intuitively, higher restart probabilities might put too much focus close nodes, while lower probabilities may focus too much nodes that are "central" in the graph structure, with fewer dif- ferences in the RWR features be- tween nodes. Figure [ (a) sum- marises how the accuracy node classification changes with differ- restart probabilities. Results for graph classification are shown in Figure (b). In accordance our intuition, higher restart probabili- ties focus on close nodes (and less on distant nodes), and produce lower accuracies. Furthermore, we notice how injecting RWR infor- mation is never detrimental to the performance of the model without any injection.
GCN
GGN
GCN-D
0.81
G23--D
3.2-
GONAWW
G2344W
GCNRRWRRe
221
3.2
10
Random Ville Restart Probebiity
Fandem Walk Resber Protenity Ok)
(a)
(b)
Figure I: Accuracy on Cora (a), and on D&D (b), of GCN without and with the injection of structural information, and for different restart probabilities RWR.
Counting Triangles. The TRIANGLES dataset Knyazev et al. (2019) is composed of randomly generated graphs, where the task is to count the number triangles contained in each graph. This is a hard task for GNNs as the aggregation of neighbouring node's 's features with permutation invariant functions does not allow the model to explicitly access to structural information. The TRIANGLES dataset has a test set with 10'000 graphs, of which half are similar in size to the ones in the training and validation sets (4-25 nodes), and half are bigger (up to 100 nodes). This permits an evaluation of the generalization capabilities graphs of unseen sizes.

---

Under review as a conference paper at ICLR 2021
For this regression task we three layer GCN, and we minimize the Mean Squared Error (MSE) loss (more details can be found in Appendix A). Table MSE results on the test dataset as whole and the two splits separately. We see that the addition of RWR features and of RWRReg provides significant benefits (up to 19 % improvements), specially when the model has to generalize to graphs of unseen sizes, while the addition of adjacency features leads to overfitting.
5 PRACTICAL RWR REGULARIZATION
As shown in Section 4 the addition of RWR features as node features coupled with RWRReg provides a significant im- provement of the accuracy on all con- sidered tasks. However, these benefits come at a high cost: adding RWR fea- tures increases the input size of n elements (which is prohibitive for large graphs), and RWRReg requires the com- putation of an additional loss term (and the storage of the RWR matrix) dur- ing training. Furthermore, all the con- sidered models have a weight matrix at each layer that depends on the feature dimension, which means we are also increasing the number of parameters at the first layer by n (1) (where d()) is the dimension of the feature vector for each node after the first GCN layer). In this sec- tion we propose practical way take advantage of the injection of structural information without increasing the number of parameters, and controlling the memory consumption during training.
Table 3: Mean Squared Error (MSE) of GCN with differ- ent levels of structural information injection on the TRI- ANGLES test set.
Model
TRIANGLES Test Set
Global
Small
Large
GCN
2.290
1.311
3.608
GCN-AD GCN-RWR
4.746
1.162
5.971
2.044
1.101
2.988
GCN-RWRReg
2.187
1.282
3.014
GCN-RWR+RWRRe
2.029
1.166
2.893
The results in Section 4 show that the sole addition of the RWRReg term increases the performance of the considered models by more than 5%. Furthermore, RWRReg does not increase the size of the input or the number of parameters (as it does not add any feature the node's 's feature vectors), does not require additional operations at inference time, and maintains the permutation invariance of GCN models. Therefore, RWRReg alone is a very practical tool that significantly improves the quality of GCN models. However, when dealing with very large graphs, keeping in memory the RWR matrix to compute RWRReg during training might be too expensive. We then explore how the sparsification of this matrix affects the resulting model. In particular, we apply a top-K strategy: for each node, we only keep the K highest RWR weights. Figure 2 shows how different values of K' impact performance We can see that the addition of the RWRReg term is always beneficial. Furthermore, by taking the top-2. we can reduce the number of entries in the RWR matrix of z elements, while still obtaining an average 3.2% % increment on the accuracy of the model. This strategy then allows the selection of the value of K that best suits the available memory, while still obtaining high performing model (better than GCN without structural information injection).
node classification (which usually is the task with the largest graphs).
GCH
CCN
0.60
GCN AGR
GCN--4 AD
GDK-40 A/
SCh 1MV1
0.71
(CK-AD AD
CCh- NWl
2.82
G.V Aa---a
GCT, AWRRee
OCN- HR/A0-0)
Aruuecy O1
2.81
0.80
2.00
0.62
0.95
3.78
0.65
0.79
105
402
902
1/05
5.71
J000000 3250
9950
19/17
0.51
350
1500
2520
3521
(a)
(b)
(c)
Figure2 2: Performance of GCN-RWRReg on node classification when trained using Top-K K sparsifi- cation of the RWR matrix.
7

---

Under review as a conference paper at ICLR 2021
6 RELATED WORK
The field of GNNs has become extremely vast, for a thorough review we refer the reader to the latest survey on the subject (Wu et al., 2019). To the best of our knowledge there are no studies that test if additional structural information can significantly impact GCNs, and there has been very few interest in long-range dependencies between nodes. However, there are some works that are conceptually related to our approach.
Klicpera al. 2019b) use RWR to create a new (weighted) adjacency matrix where message pass- ing is performed. While this can enable long-range communication, it is impractical for inductive scenarios, as the RWR matrix needs to be calculated for each new graph. In contrast, our RWRReg method only uses the RWR matrix in the training phase, and does not require any additional opera- tion at inference time. Other works have used random walks with GCNs in different ways. [i et al. (2018) random walks in co-training scenario to add new nodes for the GCN's training set. Ying et al. (2018a) and Zhang et al. (2019) use random walks to define aggregation neighbourhoods that are not confined to fixed distance. HAbuEEl-Haija et al. (2018) and AAbu-El-Hajja et al. (2019) use powers of the adjacency matrix, which can be considered as random walk statistics, to define neighbourhoods of different scales. [hhangg & Ma (2018) use random walks define the positive pointwise mutual information (PPMI) matrix and then use it in place of the adjacency matrix in the GCN formulation. Klicpera et al. (2019a) use a diffusion strategy based on RWR instead of aggregating information from neighbours. This last work has recently been extended by [Bojchevski jet al. (2020) to scale to large graphs using RWRs to sample neighbourhoods. We remark how all the aforementioned papers focus creating smart or extended neighbourhoods which are then used for node aggregation, while we show that node aggregation (or pessage-passing. without additional information (e.g., RWR features RWR-based regularization) is not capable of fully exploiting structural graph information.
Pei ct al. 2020) propose strategy to insert long-range dependencies information in GCNs by per- forming aggregation between neighbours in a latent space obtained with some classical node em- bedding techniques, but it is limited to transductive tasks. Our method can be easily applied to any existing GCN architecture, and works also on inductive tasks. |aao et al.] (2019). and [Jing & Lin (2018) use regularization techniques to enforce that the embeddings of neighbouring nodes should be close to each other. The first uses Conditional Random Fields, while the second uses a regular- ization term based on the graph Laplacian. Both approaches only focus on I-hop neighbours and do not take long-range dependencies into account.
With regards to the study of the capabilities and weaknesses of GNNs, Li et al. (2018) and Xu
et al. (2018b) study the over-smoothing problem that appears in Deep-GCN architectures, while Xu al. (2018a) and Morris et al. (2019) characterize the relation to the Weisfeiler-
algorithm.
Other works have expressed the similarity with distributed computing (Sato et al. 2019 Loukas 2020), and the alignment with particular algorithmic structures (Xu et al. 2020). These important contributions have advanced our understanding of the capabilities of GNNs, but they do not quantify the impact of additional structural information.
Our approach relies on the computation of the RWR matrix for training the model. When dealing with large graphs there is a vast literature on fast approximations of RWR scores (Andersen et al.
2006 Tong et al. 2006 Bahmani al. 2010 Lofgren 2015 Wei al. 2018 Wang et al. 2019).
CONCLUSIONS
In this work we showed that state-of-the-ar GCN models ignore relevant information regarding node and graph similarity that is revealed by long distance relations among nodes. We describe four ways to inject such information in several models, and empirically show that the performance of all models significantly improve when such information is used. We then propose a novel regulariza- tion technique based on RWR, which leads to an average improvement of 5% on all models. Our experimental results are supported by novel connection between RWR and the 1-Weisfeiler- algorithm, which proves that RWR encode long-range relations that are not captured by considering only neighbours at distance at most 2 or 3, it is common practice in GCNs. Based on results, there are several interesting directions for future research, including the design of GCN architectures that directly capture long distance relations.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-El-Haija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN: Multi-scale graph convolution for semi-supervised node classification. In UAI, 2018.
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing, In International Conference on Machine Learning (ICML), 2019.
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 06), 2006. doi: 10.1109/focs 2006..44 /tLhttp::////
dol. wttp://p..oooo......oo.... http://...11111910 1109/ 2006.00 44
Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast incremental and personalized pager- ank. Proceedings of the VLDB Endowment, 4(3):173-1844 Dec 2010. ISSN 2150-8097. doi: 10. 14778/1929861.19988888 URL http::/dx doi wwt/
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin J. Blais, Benedek Rozemberczki, M. Lukasik, and Stephan Gunnemann. Scaling graph neural networks with ap- proximate pagerank. Proceedings of the 26th ACM SIGKDD International Conference Knowl- edge Discovery Data Mining, 2020.
Catalina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò. Towards sparse hierarchical graph classifiers. NIPS Workshop on Relational Representation Learning, 2018.
Djork-Aré Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (ELUss. ICLR, 2016.
Frederik Diehl, Thomas Brunner, Michael Truong Le, and Alois Knoll. Towards graph pooling by edge contraction. JCML Workshop Learning and Reasoning with Graph-Structured Data, 2019.
Hongchang Gao, Jian Pei, and Heng Huang. Conditional random field enhanced graph convolutional neural networks. Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining KDD '19, 2019. doi: 10.1145/32925003333088 URL http:
7/dx. doi wttg//...... /2044//222222 3330888
Hongyang Gao and Shuiwang Ji. Graph U-nets, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley. Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. Proceedings of the 34th International Conference Machine Learning Volume 70, ICML'17, pp. 1263-1272. JMLR.org, 2017. URL. http:
//dl www.aacm.oom www.:acm.orggccc ptrggcitatiio... wtt.cmmmmmmm33m3ee-- 30..-333333311113311223
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large
graphs. In NIPS, 2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML, 2015.
Sergey Ivanov and Evgeny Burnaev. arXiv:1805.11922 2018.
Anonymous walk embeddings.
arXiv preprint
Bo Jiang and Doudou Lin. Graph laplacian regularized graph convolutional networks for semi- supervised learning. ArXiv, Abs/1800.099833 2018.
Woojeong Jin, J. Jung, and U. Kang. Supervised and extended restart in random walks for ranking and link prediction in networks. PLoS ONE, 14, 2019.
M. G. Kendall. The treatment of ties in ranking problems. Biometrika, 33(3))239-251, 1945. ISSN 00063444.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016.

---

Under review as a conference paper at ICLR 2021
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günneeann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019a.
Johannes Klicpera, Stefan WeiBenberger, and Stephan Günnemann, Diffusion improves graph learn- ing. In Conference on Neural Information Processing Systems (NeurIPS), 2019b.
Boris Knyazev, Graham Taylor, and Mohamed Amer. Understanding attention in graph neural net- works. In International Conference on Learning Representations (ICLR) Workshop on Represen- tation Learning on Graphs and Manifolds, 2019.
John Boaz Lee, Ryan A. Rossi, Sungchul Kim, Nesreen K. Ahmed, and Eunyee Koh. Attention models in graphs: A survey. ArXiv, abs/1807.000 009944 2a.
John Boaz Lee, Ryan A. Rossi, and Xiangnan Kong. Graph classification using structural attention. In KDD, 2018b.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In ICML, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018
Peter Lofgren. Efficient algorithms for personalized pagerank. ArXiv, abs/15512.0463,, 2015.
Andreas Loukas. What graph neural networks cannot learn: depth width. In International Con- ference on Learning Representations, 2020.
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200:108-122, 2016.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. Relational pooling for graph representations. ICML, 2019.
L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. In Proceedings of the 7th International World Wide Web Conference, pp. 161-172, Brisbane, Australia, 1998.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geo- metric graph convolutional networks. International Conference on Learning Representations, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In NeurIPS, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93, Sep 2008, ISSN 0738-4602. doi: 10.1 111.///mma...2933.2222 2155
URL http: dxwp doi org 1609/ v2913.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(Sep):2539- 2561,2011
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 1:1929-1958. 2014.
10

---

Under review as a conference paper at ICLR 2021
Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. Fast random walk with restart and its applica- tions. Sixth International Conference on Data Mining (ICDM 06), pp. 613-622 2006.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. ICLR, 2018.
Sibo Wang, Renchi Yang, Runhui Wang, Xiaokui Xiao, Zhewei Wei, Wenqing Lin, Yin Yang, and Nan Tang. Efficient algorithms for approximate single-source personalized pagerank queries. ACM Transactions on Database Systems, 44(4):1-37, Oct 2019. ISSN 0362-5915. doi: 10.1 145/ 3360902. URL http: www. org 10. 11411/366133330
Zhewei Wei, Xiaodong He, Xiaokui Xiao, Sibo Wang, Shuo Shang, and Ji-Rong Wen. TopPPR: Top-k personalized pagerank queries with precision guarantees on large graphs. Proceedings of the 2018 International Conference on Management of Data SIGMOD '18, 2018. doi: 10.1145/ 3183713.3196920. UtLhttp::/ http//xx.cioooooooooo/////oooo.t www.orgg.1.. 10t..1111133331111 3196920
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. ArXiv, abs/1901.000 09119.,0099,, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? ArXiv, abs/18 11188880000266 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018b.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference Learning Representa- fions, 2020.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Proceed- ings of the 24th ACM ACM SIGKDD International Conference on Knowledge Discovery & Data Mining KDD 18, 2018 8a. doi: 10.1 (0.11145//2118819221999999 URI. /tttp://dxx doi. http://xx.c...ro...11111111
321 98198127 9. 32 1 9999
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In NeurIPS, 2018b.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V. Chawla. Heteroge- neous graph neural network. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining KDD 19, 2019. doi: 10.1145/392200.333309. URL 3330961
http://dxx /xx doi orw//0lg100... htt.:.o.........1111.3313531
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In UAI, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. ArXiv, abs/18 1ss/1812.08444, 2018.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph based semi- supervised classification. Proceedings of the 2018 World Wide Web Conference on World Wide Web WWW 18, 2018. doi: 10.1 11.1 011144/3178876.33 3161116.6. 3178876 3186116
graph-based
URL http::/ddx http:/xxxxoo.ooooooo/ www.kdoo.oooooo cooii.org/1000 1145/
A MODEL IMPLEMENTATION DETAILS
We present here detailed description of the implementations of the models we use in our exper- imental section. Whenever possible, we started from the official implementation of the authors of each model. Table 4 contains links to the implementations used as starting point for the code for our experiments. Our code available as supplementary material and will be made publicly available after acceptance.
11

---

Under review as a conference paper at ICLR 2021
Table 4: Starting model implementations.
Model
Implementation
GCN (for node classification)
github.com/tkijp/yyyenn
GCN (for graph classification)
githb..com/baaaa/ggrpp....
GCN (for triangle counting)
GraphSage
GAT
github. hullubbcoom/Deego//yyyyiiii
DiffPool
gitbub.com/Kex Ymgg/dtipooo
k-GNN
github.com/chrsmrrs/k-ggg
Training Details. With regards the training procedure we have that models are trained with early stopping on the validation set (stopping the training if the validation loss doesn't 't decrease for a certain amount of epochs), and unless explicitly specified, we use Cross Entropy as loss function for all the classification tasks.
For the task of graph classification we zero-pad the feature vectors of each node to make them all the same length when we inject structural information into the node feature vectors.
For the task of triangle counting we follow Knyazev et al. (219)) and use the one-hot representation of node degrees as node feature vectors to impose some structural information in the network.
Computing Infrastructure. The experiments were run on a GPU cluster with 7 Nvidia 1080Ti, and on CPU cluster (when the memory consumption was too big fit in the GPUs) equipped with 8 cpus 12-Core Intel Xeon Gold 5118 @2.30GHz, with 1.5Tb of RAM.
In the rest of this Section we go through each model used in our experiments, specifying architecture, hyperparameters, and the position of the node embeddings used for RWRReg.
A.1 GCN (node classification)
We use two layer architecture. The first layer outputs a 16-dimensional embedding vector for each node, and passes through ReLu activation, before applying dropout (Srivastava (Sivaut(Sivvattav et (2014), with probability 0.5. The second layer outputs a e-dimensional embedding vector for each node, where e is the number output classes and these vectors are passed through Softmax to get the output probabilities for each class. An additional L2-loss is added with balancing term of 0.0005. The model is trained using the Adam optimizer Kingma & (2015) with a learning rate of 0.01.
We apply the RWRReg on the 16-dimensional node embeddings after the first layer.
A.2 GCN (graph classification)
We first have two GCN layers, each one generating a 128-dimensional embedding vector for each node. Then we apply max-pooling on the features of the nodes and pass the pooled 128-dimensional vector to a two-layer feed-forward neural network with 256 neurons at the first layer and at the last one, where is the number of output classes. A ReLu activation is applied in between the two feed-forward layers, and Softnax is applied after the last layer. Dropout Srivastava et al. (2014) is applied in between the last GCN layer and the beed-fowward layer, and in between the feedforward layers (after ReLu), in both cases with probability of 0.1. The model is trained using the Adam optimizer Kingma & Ba (2055) with a learning rate of 0.0005.
We apply the RWRReg on the 128-dimensional node embeddings after the last GCN layer.
A.3 GCN (counting triangles)
We first have three GCN layers, each one generating a 64-dimensional embedding vector for each node. Then we apply max-pooling the features of the nodes and pass the pooled 64-dimensional vector to a layer feed-forward neural network with one neuron. Dropout Srivastava et al. (2014) is applied in between the last GCN layer and the feed-forward layer with probability of 0.1. The
12

---

Under review as a conference paper at ICLR 2021
model is trained by minimizing the mean squared error (MSE) and is optimized using the Adam optimizer Kingma & Ba (2015) with a learning rate of 0.005.
We apply the RWRReg on the 64-dimensional node embeddings after the last GCN layer.
A.4 GRAPHSAGE
We use two layer architecture. For Cora we sample 5 nodes per-neighbourhood at the first layer and 5 at the second, while on the other datasets we sample 10 nodes per-neighbourhood at the first layer and 25 the second. Both layers are composed of mean-aggregators (i.e., we take the mean of the feature vectors of the nodes in the sampled neighbourhood) that output a 128-dimensional embedding vector per node, After the second layer these embeddings are multiplied by a learnable matrix with size 128 x c, where cis the number of output classes, giving thus a c-dimensional vector per-node. These vectors are passed through Softmax to get the output probabilities for each class. The model is optimized using Stochastic Gradient Descent with a learning rate of 0.7.
We apply the RWRReg on the 128-dimensional node embeddings after the second aggregation layer.
A.5 GAT
We use two layer architecture. The first layer uses an 8-headed attention mechanism that outputs an 8-dimensional embedding vector per-node. LeakyReLu is set with slope a 0.2. Dropout Srivastava et al.] (2014) (with probability of 0.6) is applied after both layers. The second layer outputs c-dimensional vector for each node, where e the number of classes, and before passing each vector through Softmax to obtain the output predictions, the vectors are passed through an Elu activation Clevert et al. (2016). An additional L2-loss is added with a balancing term of 0.0005. The model is optimized using Adam Kingma & Ba 2015) with a learning rate of 0.005.
We apply the RWRReg on the 8-dimensional node embeddings after the first attention layer. A particular note needs be made for the training of GATs: we found that naively implementing the RWRReg term on the node embeddings in between two layers brings to an exploding loss as the RWRReg term grows exponentially at each epoch. We believe this happens because the attention mechanism in GATs allows the network to infer that certain close nodes, even 1-hop neighbours, might not be important to a specific node and so they shouldn't be embedded close to each other. This clearly goes in contrast with the RWRReg loss, since I-hop neighbours always have a high score. We solved this issue by using the attention weights to scale the RWR coefficients at each epoch (we make sure that gradients are not calculated for this operation as we only use them for scaling). This way the RWRReg penalizations are in accordance with the attention mechanism, and are still encoding long-range dependencies.
A.6 DIFFPOOL
We use a 1-pooling architecture. The initial node feature matrix is passed through two (one to obtain the assignment matrix and one for node embeddings) 3-layer GCN, where each layer outputs a 20-dimensional vector per-node. Pooling is then applied, where the number of clusters is set as 10% of the number of nodes in the graph, and then another 3-layer GCN is applied to the pooled node features. Batch normalization [oofe Szegedy (2015) is added in between every GCN layer. The final graph embedding is passed through a 2-layer MLP with final Softmax activation. An additional L2-loss is added with a balancing term of 10 10-7 together with two pooling-specific losses. The first enforces the intuition that nodes that are close to each other should be pooled together and is defined as: LLP = (1)(0) S(!) 5:0) [[ where
|| is the Frobenius norm, and (()) is the assignment matrix at layer 1. The second one encourages the cluster assignment to be close to a one- hot vector, and is defined as: Lg 1 Σn H (S..). where H is the entropy function. However, in the implementation available online, the authors do not make use of these additional losses. We follow the latter implementation. The model is optimized using Adam Kingma & Ba 2015) with learning rate of 0.001.
We apply the RwRReg on the 20-dimensional node embeddings after the first 3-layer GCN (before pooling). We tried applying it also after pooling on the coarsened graph, but the fact that this graph could change during training yields to poor results.
13

---

Under review as a conference paper at ICLR 2021
A.7 G-G
We use the hierarchical 1-2-3-GNN architecture (which is the one showing the highest empirical results). First a I-GNN is applied to obtain node embeddings, then these embeddings are used as initial values for the 2 GNN (1-2-GNN). The embeddings of the 2-GNN are then used initial values for the 3-GNN (1-2-3-GNN). The I-GNN applies graph convolutions, while 2-GNN and the 3-GNN apply 2 graph convolutions. Each convolution outputs a 64-dimensional vector and is followed by an Elu activation Clevert et al. (2016). For each k; node features are then globally averaged and the final vectors concatenated and passed through three layer MLP. The first layer outputs a 64-dimensional vector, while the second outputs a 32-dimensional vector, and the third outputs a c-dimensional vector, where e is the number of output classes. To obtain the final output probabilities for each class, log(Softmax) is applied, and the negative log likelihood is used as loss function. After the first and the second MLP layers an Elu activation Clevert al.) (2016) is applied, furthermore, after the first MLP layer dropout [Srivastaaa et al. (2014) is applied with probability 0.5. The model is optimized using Adam Kingma Ba (2015) with a learning rate of 0.01, and a decaying learning rate schedule based on validation results (with minimum value of 10-5).
We apply the RWRReg on the 64-dimensional node embeddings after the 1-GNN. We were not able to apply it also after the 2-GNN and the 3-GNN, as would cause out-of out-of-memory issues with our computing resources.
B PROOF OF PROPOSITION ]
Given a graph G = (V, E), we define its k-step RWR representation as the set of vectors r. [ee.u...... T..u.. V E V, where each entry Tu,u describes the probability that a RWR of length starting in e ends in u.
Proposition 2. Let === I-WL. algorithm terminates with the correct answer after l iterations and starting from the labelling of all I's. Then the k-step RWR representations G1 and G2 are different.
= (V1, FA) and G2 (V2, F2) be two non-isomorphic graphs for which the
Proof. Consider the WL algorithm with initial labeling given by all I's. It's easy to see that i) after k iterations the label of a node y corresponds to the information regarding the degree distribution of the neighborhood of distance < & from e and ii) in iteration i < k, the degrees of nodes at distance i from v are included in the label of v. In fact, after the first iteration, two nodes have the same colour if they have the same degree, as the colour of each node is given by the multiset of the colours of its neighbours (and we start with initial labeling given by all I's). After the second colour refinement iteration two nodes have the same colour if they had the same colour after the first iteration (i.e. have the same degree), and the multisets containing the colours (degrees) of their neighbours are the same. In general, after the Æ-th iteration, two nodes have the same colour if they had the same colour in iteration the same for the two nodes. Hence, two nodes that have different colours after certain iteration, will have different colours in all the successive iterations. Furthermore, the colour after the k-th iteration depends on the colour at the previous iteration (which "encodes" the distribution of degree of neighbours up to distance k k- included), and the multiset of the degrees of neghbours at distance k.
1. and the multiset containing the degrees of the neighbours at distance is
Given two non-isomorphic graphs G1 and G2, if the WL algorithm terminates with the correct answer starting from the all I's labelling in A iterations, it means that there is no matching between vertices in V1 and vertices in V22 such that matched vertices have the same degree distribution for neighborhoods at distance exactly k. Equivalently, any matching M that minimizes the number of matched vertices with different degree distribution has at least one such pair. Now consider one such matching M, and let v E V1 and w E 122 be vertices matched in M with different degree distributions for neighborhoods at distance exactly k. Since u and w have different degree distributions at distance k. the number of choices for paths of length & starting from v and w must be different (since the number of choices for the 1o-th edge the path is different). Therefore, there must be at least node u e Vi and a node 2 E Vz2 that are matched by M but for which the number of paths of length from to is different from the number of paths of length l from w to Since Te. is proportional
14

---

Under review as a conference paper at ICLR 2021
Table 5: Node classification dataset statistics.
Dataset
Nodes
Edges
Classes
Features
Label Rate
Cora
2708
5429
1433
0.052
Pubmed
19717
44338
3
500
0.003
Citeseer
3327
4732
3703
0.036
Table 6: Graph classification and triangle counting dataset statisties.
Dataset
Graphs
Classes
Avg. Nodes
Avg. # Edges
ENZYMES
600
6
32.63
62.14
D&D
1178
2
284.32
715.66
PROTEINS
1113
2
39.1
72.82
TRIANGLES
45000
10
20.85
32.74
to the number of paths of length & from to u, have that Te,u o Tw,z, that is rv o Tw- Thus, the ktep RWR representation of G and G2 are different.
C DATASETS
We briefly present here some additional details about the datasets used for our experimental sec- tion. Table [ summarizes the datasets for node classification, while Table 6 presents informa- tion about the datasets for graph classification and triangle counting. The node classification datasets are available at lattps://lings. soe. ucse www.sscc.ed//aeeooooo data, while the graph classifi- cation and the triangle counting at morriss/raphker laaerrnnneaatttttteeet datassets
www es tu wwrtmund. de staff/
D FAST IMPLEMENTATION OF THE RANDOM WALK WITH RESTART REGULARIZATION
Let H be the matrix containing the node embeddings, and be the matrix with the RWR statistics. We are interested in the following quantity
LRwRReg Σ ES H
H
To calculate it in a fast way (specially when using GPUs) we use the following procedure. Let us first define the following matrices:
Si
+ Sj for i + j for i = j
$ X symmetric matrix with St,5
S
D x diagonal matrix with D Σ Sis
A = D -
Where are allowed to make S symmetric because || H |H H...l Vi,j. We then have
LRWRRes
S.y H. HAGl -
Where Tr(:) is the trace of the matrix. Note that H. is the i-th column of H, transposed, so its size is 1 n.
15

---

Under review as a conference paper at ICLR 2021
E EMPIRICAL ANALYSIS OF THE RANDOM WALK WITH RESTART MATRIX
We now analyse the RWR matrix to justify the use of RWR for the encoding of long range dependen- cies, and other important structural information. We consider the three node classification datasets (see Section 4 of the paper), as this is the task with the largest input graphs, and hence where this kind of information seems more relevant.
We first consider the distribution of the RWR weights differ- ent distances from given node. In particular, for each node, we take the sum of the weights as- signed to the I-hop neighbours, the 2-hop neighbours, and on. We then take the average, over all nodes, of the sum of the RWR weights at each hop. We discard nodes that belong to connected components with di- ameter S 4, and we only plot the values for the distances that have an average sum of weights higher than 0.001. Plots are shown in Figure 3 We notice that the RWR matrix contains information that goes beyond the immediate neighbourhood of node. In fact, we see that approximately 90% of the weights are contained within the 6-hop neighbourhood, with a significant portion that is not contained in the 2-hop neighbourhood usually accessed by GCN-like models.
Cheeet
2014
Sos
(a)
(b)
(c)
Figure 3: Average distribution of the RWR weights at different distances for the node classification datasets. Distance zero indi- cates the weight that a node assigns to itself.
Next we analyse if RWR capture some non-trivial relationships between nodes. In particular, we investigate if there are nodes that are far from the starting node, but receive a higher weight than some closer nodes. To quantify this property we use the Kendall Tau- measure (Kendall (1445). In more detail, for each node u we consider the sequence rwc() where the i-th element is the weight that the RWR from node has assigned node i: [[] Su,i. We then define the sequence drw(()) such that drw [j] dist(r, Ssort www.srtttttgggtss..... weights (j, roo())), where dist(x, y) is the shortest path distance between node r and node ) is the node with the j- Pubmed Citeseer
Table 7: Average and standard deviation, over all nodes, of Kendall Tau-b values measuring the non-trivial relationships between nodes captured by the RWR weights.
Dataset
Average Kendall Tau-b
Cora
0.729 = 0.082
y. and L (j, (*)
0.631 + 0.057
th highest RWR weight in (w) Intuitively, if the RWR matrix isn't capable of capturing non-trivial relationship would have that drw(t) is a sorted list (with repetitions). By comparing drw(v) with its sorted version with the Kendall Tau-b rank, we obtain a value between 1 and -1 where means that the two sequences are identical, and -1 means that one is the reverse of the other. Table 7 presents the results, averaged over all nodes, on the node classification datasets. These results show that while there is a strong relation between the information provided by RWR and the distance between nodes, there is information in the RWR that is not captured by shortest path distances.
0.722 + 0.171
As an example of the non-trivial relationships encoded by RWR, Figure 4 presents a drw(v) se- quence taken from node in Cora. This sequence obtains a Kendall Tau-b value of 0.591. We can observe that the nodes at distance I are the nodes with the highest weights, however, for distances greater than 1, already have some non-trivial relationships. In fact, we observe some nodes at distance 3 that receive a larger weight than nodes at distance 2. There are many other interesting non-trivial relationships, for example we notice that some nodes at distance and some at distance 11, obtain a higher weight than some nodes at distance 5.
3 consider RWR, with restart probability of 0.15, as done for the experimental evaluation of our pro- posed technique.
WWe use the Tau-h version because the elements in the sequences we analyze are all distinct.
16

---

Under review as a conference paper at ICLR 2021
(1000)
G
8.
10,
6.
8.
7
3.
24.
10,
10,
9
0,
10,
10,
13,
6,
Figure 4: (r sequence for the 1000-th node in Cora.
17


Reviews:
[{"review_id": "hD6fQlYHu_m", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the long-range dependency and proposes four levels of injection of longer-range graph structure information based on random walks with restart (RWR). Experimental results show that the proposed models perform well on the tasks of node classification, graph classification, and counting triangles.\nUtilizing long-range dependency is not new in graph neural networks. I do not think the authors give enough reviews about important related tasks; their related work section focuses more on RWR. Considering the motivation and the solved issues of graph neural networks, more relevant literature in GNN domains should be added, such as MixHop (Abu-El-Haija et al., 2019), Snowball (Luan et al., 2019), APPNP (Klicpera et al., 2019 ), GDC (Klicpera et al., 2019). Compared with those works, the RWR regularization seems incremental. Adding the RWR features is just a new feature and adding the RWR regularization term actually can be translated into a kind of message passing schema. \nMoreover, some details of the method are not very clear. For example, how do we calculate $S_{I,j}$? When we add the regularization, do we use all node pairs or just the node pairs within some distance? If using all node pairs, is the computational complexity too high?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gah7TKW8Nlr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summarization\n\nThe authors formalize four levels of injection of graph structural information, and use them to analyze the importance of long-range dependencies. Among these four different structural information injections, the authors design various graph analysis tasks to evaluate the superiority of the proposed methods, and the experimental results could be reasonable and easy to follow\n\n\nStrong points\n\n1)This paper is good writing and easy to understood. The proposed Random Walk with Restart (RWR) Matrix and RWR Regularization are quite reasonable to boost the model performance of graph neural networks (GNNs), and easy to follow.\n \n2)From the experimental results, the proposed methods have been proven efficient in various graph analysis tasks (node classification, graph classification and triangle counting) for different GNNs (GCN, GraphSage and GAT).\n\n\nWeak points: The main weakness could be innovation and experiments\n\nInnovation: \n\nThe proposed methods are quite heuristic, and I assume there could be many other improvements:\n\n1)In section 2.2, the combination of Random Walk with Restart (RWR) Matrix and GCN is too heuristic, why not try other feature fusion methods rather than straightforward concatenation.\n\n2)The developed RWR Regularization can be regarded as a formulation of Laplace Regularization, and only thing you do is replacing the Laplace matrix with the RWR matrix. Actually, there are also other graph construction methods (like consine similarity matrix etc) to replace the RWR matrix in RWR Regularization, you need to introduce additional experiments to prove the advantages of RWR matrix.\n\nExperiments\n\n1)The experimental results in Table. 1 are not so convinced. I agree with the point that your work don’t focus on defining new state-of-the-art results, but you still need to provide the node classification comparisons with the same train/validation/test split defined by Yang et al. (2016).\n\n2)As your definitions, \\lambda is a trade-off hyperparameter, but I miss the setting and ablation study of this important hyperparameter. \n\n3)Why not try AD+RWRREG? From the results, this combination seems could be better (like GCN, Diffpool in Table.2).\n\nQuestions:\n\nMy questions have been included in Weak points part\n\nAdditional Feedback\n\n1)Time complexity of constructing Random Walk with Restart (RWR) Matrix.", "extra_scores": {}, "extra_text": {}}, {"review_id": "fI4H68KM-gw", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies GCNs when long-range dependencies have been added to the model as a regularizer. The regularizer proposed in this work is based on a random walk with restart (RWR) approach as RWR encourages the model to consider long-range dependencies. This paper shows that infusing the long-range dependencies using RWR regularizer improves the performance of some models for node classification and graph classification.\n\nHere I list my concerns and questions about this work:\n\n1. Baselines: As listed in the related work section, there are other works exploiting the long-range dependencies in the graph but this work only compares to the vanilla version of some models and shows adding the RWR regularizer improved their performance. However, it's already pointed out in the literature that long-range dependencies help the improvement. I expect this paper to compare with more strong baselines that also consider long-range dependencies so one can decide which approach better suits one application and gets better results.\n\n2. Results in Table 1: Results reported for GCN and GAT are not consistent with the original papers. As an example, the GAT paper reports the accuracy of 72.5 ± 0.7% for node classification on the Citeseer dataset but this paper reports 66.4 ± 0.8 for GAT. \n\n3. Results in Figure 1: The results reported in this table need more explanation. If smaller restart probability yields better accuracy, why not testing smaller than 5% for Cora in (a)? Why one of the figures has a start point of 5% on the x-axis and the other has 10%? I expected this figure to have low scores for low probabilities and then get better to some extent and then decrease after some point again. Can the authors elaborate more on why the performance is always decreasing as we increase the restart probability?\n\n4. Section 5 on practical RWR regularization: This section studies a strategy for keeping the top-K RWR weights and sets the rest to 0 but the proposed strategy still needs to compute all RWR weights. Also, the results in Figure 2 show that larger values of K always yield better results. I was expecting that after some value of K the performance plateaus but the charts are always increasing and this shows that it's not a good idea to only keep the top-K weights.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BHk0dn0p3vS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use k-step RWR to capture long-range structural information as a part of node features, so as to overcome the limitation of GCN that it cannot infer long-range dependencies. However, the methodology is incremental and cannot easily be applied to real-world large-scale networks. In summary, the originality and significance are limited (please see detailed comments in the following).\n\n\n\nPros:\n\n1. On the premise that GIN [5] has proved the connection between GNNs and WL test, similarly, this work proves the connection between k-step RWR and WL test.\n\n2. The experimental results seem promising. The model implementation details in the appendix are extensive, which facilitates good reproducibility.\n\n3. This paper is written well and has good clarity.\n\n\n\nCons:\n\n1. Considering the RWR feature matrix has a size of n x n, concatenating it to each node's feature vector will make the node features have a very high dimension (at least larger than n), which will introduce many parameters in the first layer of GCN. Besides, the time complexity and space complexity will also increase so that the model cannot easily be applied to real-world large-scale complex networks. Although Top-K sparsification of the RWR matrix is proposed in Section 5, the performance is sacrificed more or less. Besides, we should note that RWR itself has at least square time complexity, which requires lots of computation.\n\n2. This paper argues that existing GCNs are only leveraging the graph structure in the form of the 2-hop or 3-hop neighborhood of\neach node, and are not capable of extracting and exploiting long-range dependencies between nodes. However, there exist some works that can train GCN with deeper layers. For example, Cluster-GCN [1] can train GCNs with 5 layers, ie-HGCN [2] trains GCNs on HINs (heterogeneous information network) with 6-8 layers. Moreover, DeepGCNs [3] can successfully train very deep GCNs with as many as 112 layers.\n\n3. This paper proposes to use k-step RWR to capture long-range structural information, and then concatenate the information to node features. The similar idea was adopted in existing work HAHE [4] as well, which also injects high-order (long-range) structural information as node features. What is more, the k-step RWR cannot be optimized by gradient descending, in an end-2-end fashion. \n\n4. The length k of RWR is a crucial hyper-parameter, which plays a similar role to the number of layers of GCNs. However, I didn't find its setting in the experiments. Besides, it should be studied in the experiments to demonstrate its effectiveness of capturing long-range (larger than 2,3 hops) structural information.\n\n\n\nRefs:\n\n[1] [KDD 2019] [Cluster-GCN] An efficient algorithm for training deep and large graph convolutional networks\n[2] [arXiv 2020] [ie-HGCN] Interpretable and Efficient Heterogeneous Graph Convolutional Network\n[3] [ICCV 2019] [DeepGCNs] Making GCNs Go as Deep as CNNs \n[4] [arXiv 2019] [HAHE] Hierarchical Attentive Heterogeneous Information Network Embedding\n[5] [ICLR 2019] [GIN] How Powerful Are Graph Neural Networks", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: R4 of this submission was slightly positive on this submission while all other reviewers expressed quite significant concerns in their reviews. R4 also agreed that the originality and experimental results as presented in this submission are not sufficient during discussion, although he/she pointed out the incorporation of long-range structural information is novel. Given the above recommendations and discussions, a reject is recommended.


Decision: Reject