Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: With the increasing use of complex black-box Graph Neural Networks (GNNs) in high-stakes applications, it is critical to developing explanation algorithms to understand their decisions. To this end, several methods have been proposed to generate instance-level explanations for GNN predictors. However, most works focus on generating predictions for individual node- or graph-class predictions and fail to generate model-level explanations that aim to understand the global behavior of the model. In this work, the authors propose, GNNInterpreter, a probabilistic generative model-level explanation method for GNNs that learns an explanation graph distribution that identifies the discriminative features of a graph for a given class prediction. Experimental results show that GNNInterpreter generates faithful explanations for synthetic and real-world datasets.
strength_and_weaknesses: **Strengths**

1. The paper presents a new method for generating model-level explanations for graphs with different types of node and edge features.
2. The proposed algorithm is computationally efficient and takes 10x less time than currently used graph explainer algorithms.

**Weaknesses and Open Questions**
1. The paper argues that an important goal of a GNN model explainer is to confine the distribution of the explanation graphs to the domain-specific boundary and leverages the abstract knowledge learned by the GNN itself to prevent the explanation from deviating from the true data distribution. However, the distribution from this representation may not be essentially similar to the true data distribution.
2. GNNInterpreter assumes white-box access to the model and training dataset, where it approximates the domain knowledge using the average embedding of all graphs $\psi_{c}$ from the target class in the training set. This drastically limits the approach to smaller models and datasets.
3. The description of GNNInterpreter is incomplete in the main tex. For instance, Equation 8 only provides the generic loss for training $\omega_{ij}$, $\eta_{ij}$, and $\xi_{ij}$ parameters and does not talk about the critical $\ell_{p}$-loss and other constraints.
4. The paper does not talk about the *Redundant Evidence* pitfall mentioned in Faber et al. [1] Do they report the results by taking the maximum score across all possible explanations for a given class?
5. It would be great to comment on other baseline explainers for graph classifiers like [2-3] or a random baseline.

**References**
1. Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is wrong: On evaluating gnn explanation methods. In KDD, 2021.
2. Veyrin-Forrer, L., Kamal, A., Duffner, S., Plantevit, M., & Robardet, C. On GNN explanability with activation patterns, 2021.
3. Duval, Alexandre, and Fragkiskos D. Malliaros. GraphSVX: Shapley value explanations for graph neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springee, 2021.

clarity,_quality,_novelty_and_reproducibility: **Clarity**

The paper is clearly written and provides a detailed motivation for the need for model-level explanations.

**Novelty**
 
The paper tackles generating model-level explanations for GNN predictor models which haven't been explored much.

**Reproducibility**

No code implementation details have been shared.
summary_of_the_review: Look at the strengths and weaknesses for complete details.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a model-level explanation method for GNNs. The core idea is, given a class, to maximize a graph that has the highest softmax-activation for that class. In order to obtain graphs that are meaningful, a regularization term is added forcing similarity of the graph embedding with the average embeddings for the same class. Because many components of a graph are discrete (e.g., the presence or absence of an edge), they apply the Gumbel-Softmax trick to reparameterize the gradients, under the assumption that all edges can be independently sampled. They compare the method with a baseline method, XGNN, or a series of standard benchmarks.
strength_and_weaknesses: First, the method which is proposed is basically activation maximization applied to a graph, with a simple "localization" term (see, e.g., [1]) to force the embeddings to lie close to the embeddings of the real graphs. I would suggest to discuss explicitly the relation of the method with known methods from the CV literature. In my experience, in the CV literature this kind of localization regularization is uncommon because it tends to "collapse" the answer on the reference point (the average of the embeddings). It would be interesting for the authors to evaluate whether this is also happening here (i.e., what happens if I simply take the $\hat{\phi}$ term from (2) and visualize it after proper thresholding?).

The core innovation of the work is using the GS trick to reparameterize the gradients. Also here, this is quite common today in the GNN literature (e.g., DGM for latent graph imputation, PGExplainer for explanation, adaptive graph sparsification, ...). There are also many recent proposals to generate discrete structures that do not require to assume independence of all edges, which is really strong [2]. I believe it would be better to discuss these applications on the paper, as they are clearly related (especially PGExplainer and similar works).

Third, the authors mention several time that "the generated explanation is both faithful and valid regarding the domain-specific knowledge", but this cannot guaranteed since this is only enforced through a weak regularization (indirectly via the embeddings). Unless this is tested more extensively, I believe these sentences are not valid.

[1] https://www.sciencedirect.com/science/article/pii/S1051200417302385
[2] https://arxiv.org/abs/2106.01798
clarity,_quality,_novelty_and_reproducibility: The paper is well written and easy to follow. The idea is clear from first reading. There are many important elements of the method (including several regularization terms) that are relegated to the appendix. In my opinion it would be better to move these to the main text, since they are essential for reproducing the results.
summary_of_the_review: Overall, I believe the results are interesting from the point of view of xAI on graphs. However, the method is a simple adaptation of techniques from the CV world. The experiments lack some important points to showcase the validity of the methods. Because of this, I think this is at most a borderline paper in terms of the ICLR audience, that could benefit from the points raised above, especially concerning a more proper evaluation of the state-of-the-art and more experimental details.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes GNNInterpreter to detect a model-level explanation for GNN. GNNInterpreter learns a probabilistic generative graph distribution to detect the model-level explanation without introducing another model. Experiments are evaluated on both synthetic and real-world datasets. 
strength_and_weaknesses: **Strengths:**
1. It is novel that this paper learns a probabilistic generative graph distribution to generate an explanation graph with different types of node features and edge features.
2. The experimental results are analyzed in detail, and the proposed method is tested on several datasets. 

**Weaknesses:**
1. Some of the latest related works on the instance-level explanation of GNN are not thoroughly discussed, such as causal explanation GEM [1] and OrphicX [2], reinforcement learning explanation RG-Explainer [3] and perturbation-based explanation SubgraphX [4].
2. The experiments in this paper to evaluate explanation only focus on graph classification, while other GNNs tasks are also crucial in explainability research, such as node classification and link prediction.
3. In Section 4.2, the authors present two assumptions to learn a probabilistic generative graph distribution, but an explanation of the reasonableness of the assumptions is missing.
4. In Section 4.3, the reparameterization trick is efficient for the sampling function to be differentiable. However, it is not new to use this idea which has been used by previous work such as PGExplainer [5].
5. It is said that "instance-level methods are very time-consuming," but the authors do not compare the proposed method with these instance-level models to illustrate this claim. It is suggested to add relevant comparative experiments to support this claim.
6. In addition, it does not analyze the time complexity and shows why GNNInterpreter saves more time than XGNN, which is critical for showing the effectiveness of the proposed method.
7. In Section 5.2, the experiments only choose GCN or NNConv as GNN models, which are not comprehensive to illustrate model-agnostic on other GNN models such as GAT and GraphSage.
8. In Section 5.2, the experiments in the verification study show the reasonableness of speculation to House-X class. However, it does not adequately explain the reasons for the difference between the explanations and ground truth in House-X and Complete-4.

[1] Generative Causal Explanations for Graph Neural Networks. ICML, 2021.   
[2] OrphicX: A Causality-Inspired Latent Variable Model for Interpreting Graph Neural Networks. CVPR, 2022.   
[3] Reinforcement Learning Enhanced Explainer for Graph Neural Networks. NeurIPS, 2021.   
[4] On Explainability of Graph Neural Networks via Subgraph Explorations. ICML, 2021.   
[5] Parameterized Explainer for Graph Neural Network. NeurIPS, 2020.   


clarity,_quality,_novelty_and_reproducibility: This paper is clearly written, while some repetitive sentences need to be avoided. The authors proposed a novel method, probabilistic generative model-level explanation, for GNN considering features of nodes and edges. Experiments are evaluated on both synthetic and real-world datasets. However, there is no code in the supplementary materials.
summary_of_the_review: This paper is easy to read and proposes a new approach to explain GNN models with a probabilistic generative graph. The author should explain the problem, followed by laying out their arguments more clearly. More experiments enforcing the arguments empirically are needed. Overall, the current version of this paper is not ready to be published in ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a probabilistic generative model-level explanation method for GNN named GNNInterpreter. By relaxing the adjacency matrix, the node features, and the edge features to continuous variables, it generates a graph capturing the critical characteristics that the GNN models discriminate the classes.

Compared to its counterpart XGNN, GNNInterpreter is capable of generating graphs with continuous node features as well as edge features. It also requires no domain expertise or knowledge.
strength_and_weaknesses: Strength:
1. Great ambition in attempting to interpret GNN models on different types of graphs.
2. By using an objective function instead of adopting the reinforcement learning setting, the efficiency is greatly improved.
3. The relaxation on the adjacency matrix and the features is clearly described.

Weakness:
1. Need to clarify that this method focuses on graph classification task, similar to XGNN.
2. None of the experiments is carried out on a graph with both node features and edge features.
3. Due to the space limitation, the algorithms and most of the figures are in the appendix, making the main body of the paper a little bit dry.
4. In "The lack of self-explainability becomes a serious obstacle for applying GNNs to real-world problems, especially those when making wrong decisions may incur an unaffordable cost" the "those" should be removed. 

Suggestion:
1. Try to move Algorithm 1 back into the main body of the paper. It's essential for understanding the whole structure of GNNInterpreter.
2. Instead of continuous relaxation, maybe optimization methods on the discrete settings could be considered as alternatives, such as subgradient.

clarity,_quality,_novelty_and_reproducibility: Novelty:
Although generating a graph to explain the GNN model is not a brand new idea, this approach is still novel and it provides a significant advance to the field.

Quality:
The proposed method is well supported both theoretically and empirically, especially when combined with the appendix. The assumptions, though not very strong, might need justification.

Clarity:
The method is clearly described and discussed.

Reproducibility:
The experimental details are provided in the appendix. The code has not been provided yet at the time of the review.
summary_of_the_review: The interpreter for GNN presented in the paper outperforms XGNN, which is the SOTA GNN model-level explainer. Most of the paper is well-written and the proposed method is well-supported. Some minor weaknesses need to be fixed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a model-based explanation method for the class of GNNs following a message-passing scheme. There was a thorough and lively discussion phase during which the authors provided enough improvements and clarifications to satisfy all reviewers. This is a clear accept. 
justification_for_why_not_higher_score: There were still some weak points identified by the reviewers. Especially one reviewer only gave a score marginally above the acceptance threshold. Hence, a poster presentation seems appropriate. 

However, this paper could also be a candidate for a spotlight presentation. 
justification_for_why_not_lower_score: All reviewers gave scores above the acceptance threshold.
Decision: Accept: poster