Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: To address the over-smoothness in neighborhood caused by soft-attention in GNN, this paper presents an idea of adaptive receptive fields (ARFs), which can choose contexts on different hops from the central node, so as to efficiently explore dependencies with longer distances.  The construction of ARFs follows a reinforcement learning (RL) framework. 

The adaptive selection of contextual neighbors is a promising solution, as not all the neighbors are equally important. It is an interesting idea to apply reinforcement learning to this problem. An RL agent first selects  a contact node in the direct neighbors, and then explores the neighbors of this contact node. 
 
Although the design of ARF with RL is a valuable practice,  the ARF construction process has several issues. It defines the state of a target node as a vector from f_s by taking the searched neighbors as input. How f_s is defined? The action is to select a neighbor of a target node u from its 1-hop or 2-hop neighbors. Even when the states transit from one to another, the action is always to select neighbors of u from its 1-hop or 2-hop neighbors, rather than going deep to explore the graph for more useful neighbors. After a fixed number of steps T, the added neighbors are still within the 2-nd order neighbors. Such an ARF construction process limits the region to explore in the graph. It cannot "explore dependencies with longer distances".

The presented approach shares a lot similarity with that in [1]. The constructor is analogous to the score network f_s, while the evaluator is analogous to the network f_h and f_c for accumulating the neighbor with recurrent attentions and for classification. However, [1] is not cited, and not used as a baseline to compare. 

In addition, the over-smoothing problem for GNN has been recently studied in several papers, authors are suggested to cite and compare with them as well, such as [2] [3].

Suggestions to the authors:
1) The design of ARF should be improved, with a reasonable setting of the state function and actions. 
2) Recent work should be aware. Discussion and experimental comparison with them should be included.  

[1] Akujuobi et al. Recurrent Attention Walk for Semi-supervised Classification. WSDM 2020

[2] Chen et al. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. AAAI 2020.

[3] Xie et al. When Do GNNs Work: Understanding and Improving Neighborhood Aggregation. IJCAI 2020


Thanks to authors for the clarification.  I have updated my score. 
However, a easy search with the title of the paper "Recurrent Attention Walk for Semi-supervised Classification" in Google can find the code in GitHub. 


review_title: my review

final_score: rating: 5: Marginally below acceptance threshold
review_content: #####Summary#####

This paper proposes to construct adaptive receptive fields for graph convolution using reinforcement learning. This strategy can address the smoothness of attention weights issue, and capture long-distance dependencies in graphs. Considering the following pros and cons comprehensively, I decide to give a recommendation of weak reject to this work.

#####Pros#####

(1) The studied problem is very crucial and valuable. Aggregating information from neighborhood can capture useful information as well as introduce noise sometimes. How to construct an adaptive receptive field of each node is a significant direction that deserves more investigation.

(2) This work points out the issue that the soft attention weights (such as in GAT) suffer from over-smoothness in large neighborhoods. Also, the impressive experimental result in Fig. 3 can verify this to some degree. This observation is insightful and might helpful for future exploration.

#####Cons#####

(1) The main shortcoming of this work is the high complexity of the method. This work utilizes the reinforcement learning to training the constructor, which is expected to be very complicated. Furthermore, there does not exist the experiments about running efficiency of the proposed method, which is very necessary to demonstrate the value of the proposed approach.

(2) Also, the dataset used in this paper is relatively small and some of them are shown to have data quality issue [1]. More experiments on larger datasets, such as OGB [1], should be considered.

[1] Hu et al. Open graph benchmark: Datasets for machine learning on graphs.

review_title: Recommendation to weak reject

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
The authors theoretically and empirically show that soft-attention mechanism uses in GCNs suffers from over-smoothness in large neighborhoods. For addressing this shortcoming, they propose a neighborhood sampling approach called adaptive receptive fields (ARFs) which discretely select nodes among the multi-hop neighborhood and allow to efficiently explore long-distance dependencies in graphs. The authors also propose GRARF (GCN with Reinforced ARF) which learns optimal policy of constructing ARFs with reinforcement learning. For a given node, an RL agent successively expands ARF via a two-stage process. Firstly, a contact node in an intermediately-constructed ARF is selected and then a context among the direct neighbors of the contact node is added to ARF. The reward is the performance of the trained GCN on constructed ARF. Overall, the results demonstrate the effectiveness of the approach on benchmark datasets. The authors also demonstrate that the method is quite effective at handling noise in the graph compared to GCN and GAT by evaluating them on the Cora dataset with synthetically added noise.  

Strengths: 
1. The proposed idea of using reinforcement learning for selecting influence neighborhood of a node in GCNs is novel. The results show the effectiveness of the method. 
2. The method is more robust to noise and is capable of capturing information from distant neighbors for learning efficient representation. 

Weaknesses: 
1. The scalability of the method for larger graphs is not very explicit from the given experiments.
2. Using RL might accompany multiple challenges involved with learning policy which might restrict the applicability of the approach. 


Questions:
1. In Figure 4(b)-(d), it is not clear which attention weight distribution corresponds to GCN and which corresponds to the GAT model. 
2. Please explain the reason behind the vast difference in the performance of the baseline models on cora, citeseer, and pubmed datasets. For instance, GAT reported around 83% on cora, however, here it has been given as 87.8. Also, on ppi dataset, the performance changes from 97.3 to 47.29. 

-----
Based on the issues pointed out by the other reviewers. I have decided to reduce my score for the paper. 

review_title: Official Blind Review #1

final_score: rating: 5: Marginally below acceptance threshold
review_content: 

**Summary:**

The paper proposes a method for avoiding the oversmoothing happening in standard GNN methods. It defines a receptive field of a node, as the set of nodes that send messages to that node and proposes a method to create adaptive receptive fields specific to each node. Instead of using all the nodes in a multi-hop neighbourhood, an reinforcement learning method is proposed to select only a subset of these nodes. The RL problem is formalised such that each state represents a set of already selected nodes, while actions represent the next selected node. The goal of the RL agent (constructor) is to form an adaptive neighbourhood for each node, and the reward is given by the loss of a GNN method (evaluator) that uses this neighbourhood. 

**Strengths:**


Adapting the receptive field of each node in a GNN is a good idea that could result in better modeling of the context, longer connections and also avoiding feature oversmoothing. 

The proposed RL method to create adaptive receptive fields is sound and experiments show that it is indeed useful.


The experiments with noisy data are interesting and show that ARF selects important nodes and also helps for long-range connections.



**Weaknesses**

The main weakness of the paper is that the proposed adaptive receptive field (ARF) is not properly motivated by the theory in section 2. It is a good idea to have an ARF as it has many advantages, but they are not properly explained in the theoretical section. ARF could achieve long-range connections while avoiding the standard node features oversmoothing problem (different than the presented attention smoothing), but this should be better motivated.


The smoothness of the weights should be more clearly defined. For example, are the weights $1 / n, 2 / n, 3 / n$ smooth? They respect Proposition 1 as they all approach 0 when $n \to \inf$, but they could be distinguished. Different from the usage in the paper, maybe the ratio $\alpha_{i,j} / \alpha_{i,k}, \forall j,k \in N(i)$ could be used.

It is not clear why small attention weights should be avoided. Weights that decrease with the number of nodes do not necessarily result in bad representations. All the attention weights could approach 0, but they could be sufficiently distinct and also result in proper node representations. 

The computational complexity of the constructor should be discussed. What is the total inference time of GRARF, taking into account the construction of the adaptive fields? What percent of the total time is spent by the constructor and evaluator?





**Additional comments and questions:**

Fair evaluation on cora, citeseer, pubmed datasets has been shown to be difficult [A]. The community seems to be moving forward to larger datasets like OGB [B] or [C].

It would be useful to make a connection and compare to other approaches that involve adaptive receptive fields, like Liu et al., 2019.  

The weight's smoothness should have a clearly presented definition, especially to avoid confusions to the smoothness of the node features, as pointed out by the authors in footnote 3.

How important is the reward shaping for good performance?

*Minor*:
In Eq.1 the first part represents the whole graph H, while the last term represents a single node:  h_i.
Eq. 5: u == i ?


[A] Shchur, Oleksandr, et al. "Pitfalls of graph neural network evaluation." arXiv preprint arXiv:1811.05868 (2018).
[B] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." arXiv preprint arXiv:2005.00687 (2020).
[C] Dwivedi, Vijay Prakash, et al. "Benchmarking graph neural networks." arXiv preprint arXiv:2003.00982 (2020).


**Conclusion:**

While the proposed method is sound and interesting and the paper has some good evaluations. The main problem of the paper is represented by the unclear theoretical part that is detrimental to the paper and should be fixed. In this form, I tend to give a *5: marginally below*  rating.

__________________________________________________________
**After rebuttal**

I thank the authors for their responses, but I will keep my original rating of the paper. I think this paper has potential and a new submission will have a better result.

Suggestion for improvements:

1. As the other reviewers pointed out, the proposed method is computationally expensive. Although this is a downside, it is not really a major one, as long as the authors have a proper analysis of the complexity and of the actual inference / training time. The authors pointed out that their contribution consists of proving that the adaptive receptive fields are useful, and I agree that an efficient method is not necessary for this, but the analysis should be made.

2. I think that additional ablation studies are needed. For example, the experiment in Figure 4 a) supports Proposition 1 but only on Cora that is homophilic and where the mean of the nodes is a good aggregation. The experiments with added noise are a good start. Maybe also compare GRARF with GAT with a simple strategy of selecting the edges (top k according to $e_{i,j}$, or all with $\alpha_{i,j} > 0.5$ ).

3. Improve the motivation from Section 2. 

review_title: Review - AnonReviewer4

Meta-review: Four knowledgeable referees lean towards rejection because of the missing detailed complexity analysis [R1,R2,R3], the choice of rather small datasets which hinders the rigorous evaluation of GNN models [R3,R4], missing state-of-the-art comparisons [R2] and ablations [R4]. The rebuttal addressed some of the concerns raised by the reviewers, in particular, clarifications request by R2, smoothness of the weights questions of R4, and the difference in performance of the baseline methods of R1. However, after discussion, the reviewers are still concerned with the missing ablations, comparisons, and complexity analysis. I agree with their assessment and therefore must reject. However, I agree with the reviewers that this is an interesting approach and encourage the authors to consider the reviewer's suggestions for future iterations of their work. 
Decision: Reject