Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed a framework to do graph based explanations. Compared to the existing explainers, the proposed method is able to explain the predictive outcome for any downstream tasks, without re-training the explainer for every new tasks. The core idea is to decompose the explanation into node embedding explanation with subgraph, and downstream classifier explanation with node embeddings. Experiments show that the proposed method is effective at explaining multiple objectives, while also being much faster than alternatives. 

strengths_and_weaknesses: Overall the paper is well motivated. The runtime required by existing explainers like GNNExplainer is indeed a bottleneck in applying the model. This paper proposed a simple and timely solution to the explainer community, and from the experiments it turns out to be efficient and effective. I think the contribution regarding this specific problem is valid. 

The paper is overall well written and easy to follow. 

There are some concerns regarding the current draft, mainly about some clarifications and the rationales for the design choices. Please see my questions below. 

questions: Q1: since directly optimizing the MI might be difficult, can we just (naively) optimize RMSE or some other distance metrics? 

Q2: During training it seems the \Tau_{\theta} selects the subgraph and feed it into GNN and optimize MI end2end. However the edge selection requires a threshold, which is literally a step function that is non-differentiable. I wonder how this is handled in the paper? 

Q3: The subgraph selection is done via the selection of each edge independently. It seems a bit limited in the sense of expressiveness, as sometime maybe a subgraph jointly controls the certain dimension of the embedding. I’d like to learn the authors opinion on this.
limitations: Please check the questions in the above section.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper sets out to achieve two main objectives - a Graph Neural Network explainer TAGE that is task agnostic, and hence second, can be used in multi-task prediction. The task agnostic claim is because TAGE uses gradient methods for the downstream tasks along with an explainer for GNN embedding which is task agnostic. The gradient methods produce a condition vector during inference. But during training a method using multivariate Laplace distribution is used for generating the condition vector. The overall objective is to maximize the mutual information between the embedding produced from the original graph and the embedding produced from the subgraph given by explainers.

Overall, the approach sounds interesting and useful. But there might be some misgivings about the claims - whether the method is really task agnostic or whether the datasets chosen really have multi-task predictions.
strengths_and_weaknesses: Strengths:

1. The paper makes a lot of practical sense given how GNN models are trained. Explaining at the GNN embedding level, and using it along with a task specific explainer. The use of gradient based methods for the latter seems reasonable. If the cost of explaining multiple tasks is amortized and efficient, this work is practically useful.

2. The paper does a good job of setting out the objectives to the point that there is some redundancy in the earlier sections. Descriptions of the following are well written.

a. Maximizing mutual information (MI) between the embeddings as the objective,
b. how to make this MI objective tractable (JSE, NCE),
c. using condition vectors from downstream tasks during inference and from the Laplace distribution during training
d. evaluation for quality and universal explanation ability

3. The visualization and the observation of closeness of chosen edges in the explanation (for MoleculeNet) are very interesting.

Weaknesses:

1. The claim of the method being task agnostic seems a pit provocative though it's largely true.
2. The definition of multi-tasks in the examples are debatable. Are there really 121 tasks in PPI? Given the limitations in evaluating the quality of the explanations (from an end user perspective), it's hard to judge if the explanations of TAGE are qualitatively better for each of the tasks.
3. It would be better if the discussion was consistently on one of the datasets (MoleculeNet), while other datasets are described in the appendix.
questions: 1. Was there any ablation done on using the embedding explainer along with PG Explainer for the down stream task? Is the use of the Laplace distribution a problem there?
2. What other distributions can be used besides multivariate Laplace distribution?

limitations: The authors mention the limitation of all inductive approaches when the training and inference data are inconsistent.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposes a method to explain GNNs on node classification and graph classifications without knowing the downstream task in advance. It separates the GNN-based models on these tasks into two parts, i.e., a GNN embedding model and an MLP downstream model. The former takes the input graph and encodes it to node/graph embeddings. The latter takes the output from the former and makes predictions for the downstream tasks. Two explainers are developed regarding these two parts respectively, and the work focuses on the embedding explainer for the first part. The embedding model is pretrained unsupervised. The embedding explainer is trained to extract a subgraph that maximizes the mutual information between the whole graph embedding and the subgraph embedding, without knowing the downstream task. Overall, the proposed method can be more efficient when explaining multiple tasks at once.
strengths_and_weaknesses: Strengths:

1. The proposed explainer runs faster than existing explainers.
2. The paper is clearly written and easy to follow.

Weaknesses:

The major weakness to me is the motivation of the work. In what cases will we truly need a task-agnostic explanation? If our goal is to understand why a model makes such a prediction, then how could we hide the prediction in advance when learning an explainer?
What formula 1 says is essentially "find the important subgraph that gives me a similar encoded embedding as if I encoded the whole graph". Why would this be reasonable in practice when we are looking into each specific task? Don't we want to give explanations as specific as possible? Personally, I don't think we could assume there is a subgraph that is generally important for all tasks since these tasks are indeed different. (similar to No-Free-Lunch theorem). This is also part of the reason why we have the sparsity metric for evaluation to avoid being too general. Probably the authors could explain or discuss their motivation and where this method is useful more clearly.

I also have some concerns about the setting of the model. Why set the pipeline into two separated parts? As far as I know, the GNN encoder is often used in a pretrain-finetune fashion which has higher accuracy than fixing the encoder for downstream tasks, like the context prediction pretraining on MoleculeNet datasets in your experiments. Why do we want to explain a less accurate model given a more accurate setting is easily available. I understand efficiency is a concern, but may be sacrificing too much accuracy to achieve a task-agnostic explanation isn't worth doing?

The discussion of related work is not very thorough. Some recent works are missing, e.g., [1] and [2]. Some works like SubgraphX and Gem are cited but not discussed specifically.

[1] Wang, X., Wu, Y., Zhang, A., He, X., & Chua, T. S. (2021). Towards multi-grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 34, 18446-18458.

[2] Lin, W., Lan, H., Wang, H., & Li, B. (2022). Orphicx: A causality-inspired latent variable model for interpreting graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 13729-13738).

Minor:
Notation D mismatch in lines 90 and 145
 
questions: 1. In the paper authors use some pre-training task to initialize GNN. In the experiments (Figure 3), are all the baselines run on the pre-trained model? Or some will fine-tune on downstream tasks? What is the prediction accuracy after fine-tuning? I think this is important as we want to make sure comparing the explanation ability with the same model.

2. Could this approach work for other self-supervised pre-training tasks? Did the authors try any of them? As I think the approach should be a general framework to understand a pre-trained model.

3. As mentioned in "strength and weakness", I suggest the authors explain more clearly why and when this task-agnostic model might work, and when it may fail. I doubt there should be a explanation that could be suitable for different tasks. Probably the authors could emphasize their contribution more on how to explain a pre-trained model instead of saying its generalized to different tasks. Probably with a few label and fine-tuning would be more reasonable for such as task-agnostic model.
limitations: The authors list the limitation on broad usage setting (cannot do inductive and black-box explanation). But I expect more discussion on whether such a task-agnostic explanation could really be useful for different task, when will it fails (e.g., some task-specific feature could not be captured during pre-training)
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a novel graph explainer independent of specific downstream tasks. The proposed explainer consists of two parts: embedding explainer and downstream explainers. This task-agnostic attribute of the embedding explainer is implemented by a  self-supervised method via Mutual Information. The extensive quantitative experiments and visualizations demonstrate the merits of the proposed method.
strengths_and_weaknesses: Strengths:
1. The proposed task-agnostic graph explanator has some novelty in this field. The task agnostic explanation may bring new insight from different views compared with task-specific tasks. This character might be very interesting for some directions like drug discovery via graph learning. 
2. The implementation of self-supervised training for the embedding model is interesting. It is also an interesting attempt to apply MI objective.
3. The experiments show improved computational time cost compared to baselines.

Weaknesses:
1. The section on related works might need more words to help the readers understand your work. For example, it would be better to add some discussions for [1]. Moreover, the mask-based explanation models are a branch of graph explanation methods. The differences between the proposed and the existing ones may need to be clarified.
[1]. Siqi Miao, Miaoyuan Liu, Pan Li; Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism; ICML 2022.
2. The paper may lack some discussions about its limitations.  As line 293 said, the proposed method may have poorer performance compared with task-specific explainers. When it is better to use the proposed method rather than others?

questions: 1. When it is better to use the proposed method rather than others?
limitations: The work has pointed out some limitations. I encourage the authors to add more about its application condition.
review_title: null

Meta-review: metareview: This paper proposed an extension to existing graph explanation approaches, by introducing the task-agnostic concept that decouples the representation learning and task adaptation modules. All reviewers agree that the paper is well motivated and has practical values. During the rebuttal the authors have also addressed several concerns raised by the reviewers. Based on the agreement from all the reviewers we recommend the acceptance of this paper.

confidence: Certain
Decision: Accept