Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an RL-enhanced GNN explainer, RG-Explainer which could construct a connected explanatory subgraph by sequentially adding nodes from the boundary of the current generated graph, and can be used for inductive setting. Experiments on both synthetic and real datasets are carried out to compare the proposed algorithm with existing  GNN explainers. 
main_review: The reviewer finds this manuscript well-written and the performance of the algorithm impressive. The reviewer believes such a framework could be useful for understanding and explain the performance of GNNs.

One major question is regarding the complex convergence of the algorithm. Due to the introduction of the RL framework, which leads to high training complexity, and the policy gradient may not necessarily converge. However, no analysis or experiments were provided regarding this issue. More discussion with respect to the convergence of the framework is needed.
limitations_and_societal_impact: Yes, but the discussion of societal impact is not in the main text but in the supplementary document.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studied the explanation for GNNs. The authors formulated the task of generating an exploratory sub-graph as a combinatorial optimization problem, and proposed a framework, RG-Explainer, to solve the problem via reinforcement learning. 

The RG-Explainer framework consists of three parts: a seed locator for starting node selection, a graph generator for generating the explanatory sub-graph, and a learned stopping criteria to avoid generating very large explanatory graphs. 

The authors conducted experiments on node classification and graph classification tasks.  The qualitative results showed that the proposed method could provide plausible explanations. The quantitative results showed that the proposed method has better accuracy, and outperforms the baseline in both inductive and transductive settings.

main_review: Originality: The proposed framework is novel in terms of GNN explanatory. The authors introduced RL-based learning schema for the explanatory sub-graph generation.  

Quality: The proposed framework is reasonable. My main concerns are about the experiment results. 
1)	It seems that the authors did not implement the baselines based on the officially released code (e.g., https://github.com/flyingdoog/PGExplainer for [16]), but the reproduction challenge ([11]), which reports much lower results compared to the original paper.  A proper justification will be appreciated. 
2)	More ablation studies are necessary to clarify the contribution of different components (e.g., the different components in Eq. (7), and the pre-training part).
3)	Whether this RL-based framework requires longer training / inference time?The efficiency analysis, as discussed in existing works [16, 34], would be good to be included. 

Clarity: Overall, this paper is written clearly, except that Figure 1 is a bit confusing. In particular, 
1)	Does the locator receive the reward from the environment? 
2)	In the graph generator, should the reward arrows within the episode be removed, as the reward is assigned episodically? 
3)	What is the meaning of the “right” ticks? 

Significance: The significance is moderate. Although RL has been extensively studied in solving combinatorial optimization problems (e.g., the routing problems), this paper provides a new direction for RL application.



limitations_and_societal_impact: Limitations have been discussed before, and there's no obvious negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an RL-based GNN explainer to address the neglected interactions among nodes and edges in the generated subgraph for model interpretation in the existing works. Specifically, the subgraph generation process is modeled as a Markov decision process (MDP) where the state is the currently selected node, action space is composed by the candidate neighboring nodes, and reward signal is the combinatorial loss to encourage the RL learner to generate a compact and succinct subgraph. In this way, the subgraph generation process strictly follows the structure of the original graph and therefore considers the interactions among nodes and edges.
main_review: Strengths:

1. In general, this paper is well-written and easy to follow.
2. The proposed model is technically sound. Specifically, the definition of MDP seems reasonable, the reward signal is properly designed and well-motivated and the sparse reward signal problem is addressed properly with Monte-Carlo estimation. In addition, stopping criteria are designed to avoid large subgraphs with a maximum number of generation steps; and the starting point selection with the learning-based approach is designed to address graph classification scenarios efficiently.
3. The qualitative evaluation and quantitative results show the superior outcome comparing with state-of-the-art approaches.

Weaknesses:
1. Policy gradient and Monte-Carlo estimation may suffer from high variances and could be unstable, which may not be able to generate explanation consistently. Monte-Carlo estimation could also be inefficient. More analysis on rollout reward evolution with respect to the training timestamps may help.
2. Line 200 "In this way, we can solve the sparse reward problem and also distribute reward signals at all steps." The sparse reward is a very challenging problem. I understand that Monte-Carlo estimation could help since it gives a reward to each step. However, Monte-Carlo estimation suffers from high variance, which could slow down the convergence. To my knowledge, this is far from "solve " sparse rewards. A term like "alleviate" could be more appropriate. I would also expect more discussion of why Valina Policy Gradient and Monte-Carlo estimation are adopted here, why they can tackle the sparse reward, and why not using other RL algorithms that could be more stable and may generate more consistent explanations, like DQN or A2C.
3.More justification of leveraging the self-attention mechanism to generate stop signal is needed as it seems a bit arbitrary to directly incorporate the \tilde{H}_t(STOP) into action space. In addition, the author mentioned that a maximum number of generation steps is still needed to avoid generating large subgraphs. It is unclear whether the self-attention mechanism is effective. Ablation studies with respect to the sizes of the generated graph without maximum generation steps would be helpful.

-------------------------------- Post rebuttal --------------------------------

The authors' response has addressed my concerns. The score is raised.


limitations_and_societal_impact: No
review_title: null

Meta-review: The paper addresses the issue of explainability in GNNs using RL for finding explanatory subgraphs. The authors provided an extensive rebuttal including new experimental results requested by the reviewers. The AC believes the authors' responses address in a satisfactory manner the reviewers' comments and recommends acceptance.
Decision: Accept (Poster)