Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
Utilizing 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. 
Moreover, 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?

review_title: Incremental contribution

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Here I list my concerns and questions about this work:

1. 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.

2. 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. 

3. 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?

4. 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.
review_title: Official Review#3

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summarization

The 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


Strong points

1)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.
 
2)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).


Weak points: The main weakness could be innovation and experiments

Innovation: 

The proposed methods are quite heuristic, and I assume there could be many other improvements:

1)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.

2)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.

Experiments

1)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).

2)As your definitions, \lambda is a trade-off hyperparameter, but I miss the setting and ablation study of this important hyperparameter. 

3)Why not try AD+RWRREG? From the results, this combination seems could be better (like GCN, Diffpool in Table.2).

Questions:

My questions have been included in Weak points part

Additional Feedback

1)Time complexity of constructing Random Walk with Restart (RWR) Matrix.
review_title: This work is quite constructive, but low innovation

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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).



Pros:

1. 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.

2. The experimental results seem promising. The model implementation details in the appendix are extensive, which facilitates good reproducibility.

3. This paper is written well and has good clarity.



Cons:

1. 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.

2. This paper argues that existing GCNs are only leveraging the graph structure in the form of the 2-hop or 3-hop neighborhood of
each 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.

3. 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. 

4. 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.



Refs:

[1] [KDD 2019] [Cluster-GCN] An efficient algorithm for training deep and large graph convolutional networks
[2] [arXiv 2020] [ie-HGCN] Interpretable and Efficient Heterogeneous Graph Convolutional Network
[3] [ICCV 2019] [DeepGCNs] Making GCNs Go as Deep as CNNs 
[4] [arXiv 2019] [HAHE] Hierarchical Attentive Heterogeneous Information Network Embedding
[5] [ICLR 2019] [GIN] How Powerful Are Graph Neural Networks
review_title: 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.

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