Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper introduces a robustness explanations method on graph neural networks (RCExplainer) against random noise. To achieve their goals, they first model the common decision logic of a GNN and then extract robust counterfactual explanations by neural networks that explore the decision logic carried by the linear decision boundaries of the decision regions. 
Their conducted experiments have verified the effectiveness of the proposed framework.
main_review: There are several major concerns in this work.

1. Authors may put more effort to improve the presentation/writing of the paper.


2. The task is a little bit weird for me. 
 Can random noise affect/change the GNN's prediction (e.g., node's label)? 
If yes,  it would be better to investigate whether there are some correlations between GNNs and explainer.
It's not easy to understand how to conduct a robust GNN Explainer on non-robust GNNs. If the perturbations can change the GNN's prediction, it has a high chance to change the subgraph generated by the proposed method.

Although this work doesn't work on adversarial attacks on GNNs model, they are suggested to perturb the graph data via some GNNs attacking methods to solid their methods, instead of random noise. 

How to add the random noise? Is it for the entire graph data or individual node? 
For the explanation on a target node,  if added noise is far away from the local neighbors of the target node, it's meaningless to study their robustness and it's also hard to change the explanation results.

3. Modeling decision regions for robust explainer is not well motivated. 
Are there any other solutions? What are the detailed advantages of modeling decision boundaries for train GNN Explainers in their proposed methods?

4. It would be better to analyze the computation time for training, although the proposed method doesn't require too much time for inference.
The inference time of their methods basically depends on their designed neural networks. As they only compute a score on the embedding of two nodes, it works very efficiently.  

5. CF-GNNExplainer ->"CF-GNNExplainer [20] is only included in the results of node classification, because the source code of CF-GNNExplainer is not available "
The code has already been released three months ago. You can check at GitHub.
limitations_and_societal_impact: N.A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of generating explanations for graph classifications. In particular, the paper focuses on the robustness of the explanation. A new explanation generation method is proposed where the key is a new learning objective of the generation model. The objective considers the prototype of each class to eliminate the impact of noise. Extensive experiments on benchmark datasets validate the effectiveness and efficiency of the proposed method.
main_review: Strong points:
1. This paper studies an important problem about the explanation of graph classification.
2. This paper highlights the robustness of explanations and proposes a new method to enhance the robustness.
3. Extensive experiments are conducted.

Weak points:
1. The paper is not well written with many unclear points. For instance, 
- Definition 1 is unclear due to the vague descriptions such as "significantly" and "slight changes".
- Is the counterfactual same as the concept in causal theory? If so, the requirement of counterfactual (the first requirement of the explanation) should be revised. In causal theory, the change of outcome variable (prediction) is not necessary for a counterfactual.

2. "For experiments, our explanation network f consists of 2 fully connected layers with a ReLU activation and the hidden dimension of 64." It would be better to explain the intuition of the network design and explore the structure of the explanation network.

3. "CF-GNNExplainer [20] is only included in the results of node classification, because the source code of CF-GNNExplainer is not available and [20] reports performance on only node classification tasks."
This is a ridiculous excuse for not reporting the performance of an important baseline! (This makes me decrease the rating)

4. The authors argue the importance of aligning well between the generated explanation and human intuition. How does the proposed method achieve this target?
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper deals with the problem of generating counterfactual explanations for GNNs. The proposed approach is based on directly optimizing the counterfactual explanations in an end-to-end learning scheme. The proposed framework is validated on both synthetic and real data. 

main_review: Originality: The problem of generating counterfactual explanations form GNNs is very interesting, and worth investigating. The proposed methodology is definitely relevant and valid. Contrary to the existing work, the proposed approach 1) explicitly models the common decision logic of GNNs on similar input graphs and 2) tends to promote that removing the set of edges identified by an explanation from the input
graph changes the prediction significantly. 

Quality: The paper is technically sound. The framework is well validated with experimental results on both real and synthetic data. The discussion on the performance of the method on the mutagenicity dataset (in terms of AUC) is interesting. I would expect that a similar discussion on how the graph model/topology affect the performance of the algorithm to be very informative. 

Clarity: The paper is generally well written. However, adding a block diagram of the architecture in the main text is needed (Fig. 3 of the appendix). Moreover, some qualitative results on the explanations (similar to table 4 of the appendix) and the difference from the existing works would help the reader to position the paper and appreciate the contribution. 

Some additional minor comments:

- line 143: the sentence "Because the feature….” Is not grammatically correct. 
- Specify what are the GNNs that are used in the experiments.  

Significance: The obtain results are interesting and will probably be used by the research community. 





limitations_and_societal_impact: The authors elaborate on the limitations and societal impact in the conclusion section. The points that they raise are valid. I would add as a limitation of the existing work the lack of ability to deal with weighted edges.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a GNN explanation model to generate counterfactural and noise-robust explanations. The explanations are produced by a neural network as a set of edges where before and after removing them will result in a large deviation in the final prediction. To train such as neural network, instead of directly maximizing the deviation (in terms of confidence score) before and after removing the edges, the paper leverages common decision boundaries summarized from the linear decision boundaries of the GNN over the training graphs so that removing the edges cause many violations of the common decision boundaries. This way, the explanation is more robust to noise and does not overfit to individual instances. Experiments demonstrate the fidelity and robustness of the proposed method.
main_review: Quality: Overall, I feel the paper makes a solid contribution for explaining GNNs. The motivation of generating conunterfactual explanations robust to noise is convincing, and the proposed solution is technically sound. By summarizing common decision boundaries from the linear decision boundaries of the GNN, the proposed method find edges removing which cause the maximum violations of these decision boundaries. It makes sense to me to use common decision boundaries instead of prediction scores to measure the "importance" of an edge, because it is more robust to noise and generates explanations based on consistency with the whole training data instead of individuals. The experiments on fidelity and robustness validate that the method generates high-quality and robust-to-noise explanations for GNNs. One concern is that many approximations are made to transform those NP-hard optimization problems to greedy/continuous problems. This results in no gurantees in the solutions. I would like the authors to explain more about the effects (on solution quality and efficiency) of such approximations.

Originality and Significance: Since I am not an expert in GNN explanability, I can hardly evaluate the originality and significance of the method, such as how counterfactual explanations are generated for models other than GNNs, and whether the proposed method makes a simple modification to existing methods for explaining general neural networks. I will listen to other reviewers' comments on this part.

Clarity: The writing of this paper can be improved. For example, "common decision boundary" appears first in the abstract, however its concrete explanation does not appear until section 4.1. I would suggest avoid such technical terms in abstract, and explain (define) "common decision boundary/logic" explicitly in the introduction. Also, the sentence "Our explanations are naturally robust to noise because they are produced from the common decision boundaries of a GNN that govern the predictions of many similar input graphs" is not straightforward to me. I spent a hard time trying to understand why the proposed method is robust to noise, until I understand common decision boundary in the very late part of the paper.

I give a score 6 with a low confidence due to my limited knowledge in this area. I am willing to adjust my score if other reviewers help endorse its originality and significance.
limitations_and_societal_impact: Yes. The authors comment on the potential privacy concerns of the generated explanations.
review_title: null

Meta-review: Overall the reviewers agree that this work contributes a valid, useful method for robust counterfactual explanations on GNNs (itself of significant importance) that is well evaluated and explained. Note the reviewers have pointed out several places where the write up could be improved, and the authors are advised to address these in the final version of the work.
Decision: Accept (Poster)