Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper has done an excellent work of finding the out-of-distribution between the subgraph and graph as the confounder. Further, this paper proposes a conditional variational graph auto-encoder in assessing the causal effects of subgraph on the prediction. They also introduce a surrogate variable to denote this out-of-distribution effect. Through adversarial training, the effects of the proposed model is correctly verified.  
main_review: This paper proposes a surrogate variable $G_{s}^*$ to denote the out-of-distribution effect and seems find interesting ways to evaluate the causal effects between the subgraph and full graph.

*Strengths*:

1. the out-of-distribution has not been explored before, as the paper claims.
2. the conditional variational graph autoencoder is well proposed and well trained. 
3. I will the experimental settings, especially about the 3 insights. These results have sufficiently verify the claims and advantages of the paper. 

*Weaknesses*
I did find clear weaknesses. 
summary_of_the_review: Based on the innovation, clear model description and solid experimental results, I recommend for accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a novel explainer-agnostic method to adjust the biases of feature importance scores of feature attribution for GNNs. The paper first describes the feature importance scores of the GNN feature attribution framework have biases due to the out-of-distribution (OOD) problem. The subgraph important scores are calculated by inputting a subgraph instead of data graphs, but subgraph patterns can fall into regions outside the distribution of training data graphs. To address this problem, the paper proposed a method to generate surrogate graphs within the data graph distribution by CVGAE to make a front-door adjustment for deconfounding these biases by distribution shift. Experiments using several state-of-the-art GNN explainers shows demonstrated the effectiveness of the proposed framework.

main_review: The paper presents an interesting new method with a clear focus on debiasing GNN-explainer subgraph importance scores by generating surrogate subgraphs to correct distribution shift problems. The paper is well written and easy to follow, and the core idea sounds very effective and the empirical study using three datasets provides useful demonstrations.

Overall I liked the idea of the paper and found it nice work. Here are a couple of small questions to make sure of the paper's contribution.

- The proposed method is GNN-explainer agnostic. This point is advantageous because we can make importance corrections to any GNN explainers we like. But at the same time, a natural question will be: Is there any chance that we miss important features because the method to generate subgraph patterns didn't consider this OOD problem even if the proposed method can make a correction by posthoc processing. So for example, is it possible to have situations we have no significant important subgraph patterns after OOD-bias correction? Or, either way, any subgraph patterns come from at least one of the data graphs, and so by recovering such data graph within the training distribution, we can approximately resolve the data distribution bias and there are technically no problems??

- The paper focuses on structural features. This will imply that the bias under consideration is primarily distribution shift due to taking subgraphs of data graphs, and we need to recover the original data graph in the training set from a given any subgraph patterns. 
But relatively small subgraph patterns can occur in multiple instances, and does this generative step actually generate such surrogate graph as intended? 
Say, let G_s be a subgraph pattern we want to calculate the importance score but falls in out of the training distribution. The surrogate graph G_s^* by CVGAE is basically intended to recover the original super graph of G_s in the training dataset, isn't it? It'll be very helpful to make sure this point in some way. 

- Just for your interest, and no need to include this in the paper: it might be interesting to consider whether the bias from subgraphs to the data graphs is the main problem. If the generative step can be explicit, we can even have a deterministic mapping from the possible subgraph patterns to the original graphs by graph mining algorithms. Explicit subgraph patterns are intensively investigated in the graph mining field in parallel to GNN-based approaches to the graph classification problem. For example, the book "Managing and Mining Graph Data (Ed: Charu C. Aggarwal & Haixun Wang) covers a list of relevant papers. So we can directly search explicit subgraph patterns in the data graphs and such approaches are intensively investigated around 10 years ago.  
  - by direct graph mining such as mining "discriminative patterns", "emerging patterns", "contrastive patterns", (many works such as Llinares-López+, Fast and memory-efficient significant pattern mining via permutation testing, KDD2015)
  - by LASSO (K. Tsuda, Entire regularization paths for graph data. ICML 2007: 919-926)
  - by feature-wise boosting (Saigo+, gBoost: a mathematical programming approach to graph classification and regression, Machine Learning, 2009)
  - by sparse coordinate descent (Takigawa+, Generalized sparse learning of linear models over the complete subgraph feature set. TPAMI 2017)
  - by decision tree / decision forest (Shirakawa+, Jointly learning relevant subgraph patterns and nonlinear models of their indicators. MLG2018@KDD)  
But using these methods, we often see disappointing conclusions that in general, "smaller subgraph patterns" are important because smaller subgraphs are more frequently occurring in the data and thus can be contributing in making predictions. 

summary_of_the_review: The paper is well written, easy to follow, and presents a very useful explainer-agostic method to correct the OOD bias of subgraph important scores by GNN explainers. Small questions are made to make sure
1. Even this explainer-agnostic method can correct the OOD biases, the original GNN explainers didn't take into account those biases. Does this cause any problem?
2. What the surrogate graphs are like? They are recovered original graphs containing the given subgraphs?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper sheds an exciting light on the problem of producing a meaningful evaluation of GNN explanation methods (at least a subset of them).
The idea is to introduce a deconfounder D to capture the effect of OOD explanations. The authors make an interesting example for a well-known synthetic dataset where the weight of the explanation in the ground truth is lower than a clear non-valid explanation when evaluated using the model to explain.
The introduction of the deconfounder D creates a spurious path between the graph variable and the explainer variable. To mitigate this effect, then, they introduce a front-door adjustment to the causal graph.
The front door adjustment requires a graph generator and authors use a novel Conditional-VGAE to generate graphs that will also cover the OOD case.
The paper finally presents some experiments showing the evaluation method in action.
main_review: As I have stated in summary, the paper has caught an interesting problem with current explanation evaluation methods. This aspect is a strength! Another strength is that they cast the problem into a causal framework making the reasoning behind the novel evaluation mechanism reasonably interpretable.

The main issue with the paper lies in its clarity. It is not challenging to follow the technical details but rather to understand what the authors want to do. For instance, the authors title Section 2.1 as "Problem Formulation" but I do not see any problem formulated in that section.
Also, the evaluation method requires using a generative model to generate enough samples to be able to apply Equation 1.

For the above reasons, I would like authors to clearly state:
1. Whenever a new model for explaining GNNs is developed, should one also generate graphs using CVGAE?
2. How can one tell the superiority of the novel evaluation method from your paper? Where is exactly that assessed and proved? I tried to grasp it from reading the article, but I've not been able to.
3. Can you please clearly state what is the impact of the generative model on your evaluation? The two baselines are very weak, in my opinion. One is random, OK we should always include random baselines. The other one, though, is not conditional, which makes only explicit that a conditional generator is better. But I would have been surprised to find out that this was not the case. So, the question is: what are other baselines that would truly show the impact of the generator? Would it be sufficient to use whatever conditional method to generate graphs?


====== Minor Concerns ======
1. with less discriminative information --> Define "less discriminative information"
2. G_s is defined in the caption of Figure 1 but not in the text and when you first use it, is difficult to follow the sentence.
3. what the full graph like --> what the full graph is like
4. It harms the removal-based evaluation of the explanatory subgraph --> I've read this sentence over and over again but I've not been able to understand what you actually meant
5. well-trained GNN predictor --> What "well-trained" means?
6. it is rooted from G_s --> it is rooted on (?) G_s.  (What does actually mean this sentence?)
7. Equation (2) the product should have i = 1 and not just i
8. auto-encoder is able to generate --> autoencoder we are able to generate
9. the formula  that comes after formally does not look correct (or I've not understood it)
10. Besides, we introduce ... generated graphs --> Cannot understand it
11. Equation equation 1 (in a couple of places)



Authors have addressed most of my concerns, except for the #1, which is still not 100% clear. After the rebuttal, I've decided to raise my score.
summary_of_the_review: In summary, I like the idea but I believe the paper does not make a good job of conveying the message to the readers.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors use a causal view to investigate the OOD effect on the explanation evaluation of GNNs. They find the confounder between the extracted subgraphs and the model prediction, which makes the evaluation less reliable. To solve this problem, the authors proposed a deconfounding evaluation method based on the front-door adjustment from causal discovery. To generate a reliable surrogate subgraph, they proposed a generative model, which contains three losses for training. The experimental results show the effectiveness of the proposed method (DSE).
main_review: Strengths:
In general, the motivation of this paper is very clear. The paper is easy to follow. View GNNs from a causal perspective is not a new idea. However, this paper uses causal theory to investigate the OOD problem in DNNs is new and interesting.

Weaknesses:

My major concerns are as follows,

1. In Section 3.1, the authors mention 'our work is the first to adopt the causal theory to \textbf{solve} the OOD problem ...'. However, I think this paper is a causal view on the OOD problem in DNNs instead of solving the OOD problem in DNNs. Especially, at the beginning of Section 4, the authors also highlight that they study the explanation evaluation and the generator, which are verified my opinion. 

2. In the adversarial training part, there are several hyper-parameters such as $\gamma$, $\omega$, $\tau$, $\lambda$, and $\beta$. However, the authors do not provide any sensitivity analysis about these hyper-parameters. On the other hand, since there are three losses in Eq.(4), the authors should do several Ablation studies to demonstrate the significance of each loss function. 

3. In Insight 3 of Section 4.2, the authors mention 'The DSE-based rankings are highly consistent with the references,'. However, it is not clear what is the references and where can we get these references? In specific, how to get the values of Prec column and values of Score column in Table 1.

4. Why the VAL performance of VGAE on MNIST$_{sup}$ is a negative value (-0.203)?

5. Since the work of Causal Screening (Screener) [1] is very close to this paper, the authors should discuss more differences between this paper and paper [1] instead of mentioning it slightly in the Related Work.

[1] Wang, Xiang, et al. "Causal Screening to Interpret Graph Neural Networks." (2020).

My minor concerns:

1. Some notations are not clear and there are some typos. 
a) In Eq. (1), what is the meaning of \textbf{do}?
b) Below Eq.(3), 'Equation equation 1' should be 'Equation 1'.
c) In Figure 3, what is 'AGG'?
summary_of_the_review: From my perspective, this paper is interesting in some aspects. The causal view on the OOD problem in DNNs is a new idea.
review_title: null

Meta-review: This paper recieves extensive discussions among SAC, two ACs and PCs. The decision was not made lightly. We hope that you will find the comments below  from two ACs useful for future publication. 
----------------------------------------------------------------
This paper is concerned with the feature attribution framework, which distributes the prediction made by a Graph Neural Network (GNN) to its input features, such as edges or nodes, and identifies an influential subgraph as the explanation. The currently prevailing feature removal strategy, which feeds only the considered subgraph into the target predictor and then measures the importance of the subgraph, will encounter the so-called Out-Of-Distribution (OOD) problem--the new subgraphs may not appear in the training dataset.

This paper proposes to use the causal inference framework to deal with this OOD problem. The proposal seems interesting: it considered the considered subgraph as the cause of the prediction and treats domain shift as a (hidden) common cause for both of them. It proposes to estimate a surrogate graph G_s^* to satisfy the front-door criterion and then estimate the causal effect of the subgraph on the prediction.

While the proposed method seems novel and interesting and the reported empirical results seem encouraging, I have some basic concerns about the proposal.
1. The authors didn't justify why the feature attribution evaluation problem can/should be considered as a causal effect identification problem. In feature attribution evaluation, one is essentially interested in evaluating the prediction given the subgraph. The distribution shift variable, D, contains information that is helpful for this purpose.  Why should one go with the causal effect identification formulation, in which D is made independent from the subgraph and then integrated out? I think this justification is essential.

2. It is not justified why the constructed variable, G_s^*, satisfies the front-door criterion. In Section 3.1, the authors claimed that "G_s^* should follow the data distribution and respect the inherent knowledge of graph properties, thus no link exists between D and G_s^*."  I failed to see why this implies that there is no link from D to G_s^* (or that D and G_s^* are conditionally independent given G_s)--note that D is part of the data distribution. Without this justification, I am not sure whether the application of front-door adjustment is sensible.

Overall, the paper contains interesting ideas and the results look encouraging. It would be highly appreciated if the authors managed to make this work convincing, by properly addressing the issues above.  I hope to see those components in an updated paper.
------------------------------------------------------

This work considers the task of debiasing GNN-explainer subgraph importance scores by generating surrogate subgraphs to correct distribution shift problems. Through a causal model, the authors argue that a model prediction based on the explanatory subgraphs suffers from a distribution shift (e.g., induced subgraph degree distributions are different than those of the full graph). Hence, the associations between the important induced subgraphs and the model prediction may be spurious. In particular, the casting of induced subgraph explanations as a front-door hidden variable should be definitively valuable to the community (but maybe a little too strong of a condition, seems unnecessary for the proposed goal).

Overall the reviewers believe the goal and observations are novel and valuable. Most of the reviewers' concerns were addressed in the rebuttal. As a pure data-driven domain adaptation work, I think the work is good. However, even after discussing with the authors, I am still concerned with the soundness of the causal theory behind the work.

A Conditional Variational Graph Auto-Encoder (CVGAE) are tasked to produce subgraphs that act as a front-door adjustment variable. The argument is that this front-door adjustment solves the challenges of the distribution shift. Front-door adjustment is generally performed over observed variables. If performed with a model, the model is likely mechanistic. CVGAE are extremely flexible models for a front-door adjustment. And while the generated subgraphs are constrained to reproduce a data-driven distribution of induced subgraphs (and that those themselves have constraints), that in itself is not enough to guarantee these generated graphs give a proper front-door adjustment. The work also describes "generate counterfactual edges" without a clear causal model for how these edges are generated or why they are counterfactual. The causal theory needs a lot of work.

The work is very promising and may become a cornerstone contribution to graph explanations. However, as it stands now, the causal theory needs to be more formal (the work offers no proofs of the various claims). I am excited to see the causal theory fully developed in the future.
Decision: Reject