originality: graph neural networks did not have a method for explainable predictions significance: GNNs are widely used and explanations are important. Work shows existing NN explanation frameworks don't work well with graphs quality: The authors propose a novel method to explain the predictions of Graph Neural Networks - both for explaining single node predictions or predictions of a class of nodes. This is achieved by isolating multiple possible subgraphs relevant to the classification, whose edges are selected via mutual information maximization and variational inference. Use of masks allows for explanations to jointly include node features. Convincing empirical results (except for how the hand-picked thresholding affects the results). significance: The paper is solid and make good arguments for the decisions made in the method. some issues: 1. The proposal distribution for VI assumes independent edges in the subgraph, which is not ideal if one thinks that some explanations must jointly depend on multiple edges: say, either edges (a,b) and (b,c) or edges (a,d) and (d,c). 2. A threshold is used to remove low-weight edges, and identify the explanation subgraph G_S. It is unclear how the different explanation methods are affected by the choice of this arbitrary threshold. Moreover, there isn't justification for the chosen number of edges and nodes selected to justify the classification. (minor: Automatically discovering subgraph sizes would be a nice feature to have). 3. minor: The work does not provide an assessment of how well the mean field approximates the original objective. Minor typos: "is fixed, trained GNN" => " is fixed, a trained GNN"

The authors propose a model-agnostic approach for explaining GNNs prediction. The problem they are addressing is novel, and they use a simple but effective approach to address that. The paper is well written and most of the details are clear. Their approach is novel in finding important subgraphs for the prediction. They evaluate their method across mulitple synthetic and real world dataset. A more detailed explaination on synthetic dataset and how they generate the labels would make the experiments more reproducable. quantitative analysis on the real world datasets in addition to the synthetic datasets would be beneficial.

The paper focuses on graph neural networks (GNN) that has recently gained significant attention as vital components for machine learning systems over graph structured data. Specifically, the authors build a method to analyze the predictions made by GNN and output explanations in the form of contextual subgraph and subset of features of nodes in this subgraph. The goal is to understand what parts of the graph (structure and features) were given importance by GNN model while computing predictions for node and edge. The authors achieve this by optimizing an information theoretic objective that considers the mutual information between the predictions and the relevant graph components. The authors provide methods for both single and multi-instance setting. Empirical evidence show that GNNExplainer outperforms couple of baselines on various datasets in terms of explanation accuracy and identifying the correct subgraphs/subset of features. - Overall, the paper is well written and provides good exposition of the technical details of the approach. - Since past few years, there has been significant increase in machine learning over graphs while little effort has been spent on validating and/or interpreting the resulting models. This paper certainly sets a right step in this direction and is a very timely contribution - The idea of using structural properties such as subgraph and important features aligns well with what one expects the GNN models to focus on, while making predictions. Having said that, I have several concerns both for methodology but more importantly, for experiments that prevents me from giving high score to the paper: - It is not clear what is the strong motivation behind using mutual information? One can see that the mutual information is useful in connecting predictions to substructures however, is this guaranteed to be always useful? For instance, if two nodes are connected to each other within a dense graph but have different labels, how does this approach able to figure out good sub-component for one node different from the other node which leads to different labels? - On page 4, the authors mention K_M nodes and also K_M edges. is this a typo? If not how K_M node and K_M edges are related here? - Different constraints are a bit concerning in this approach: - The constraint of K_M edges seem to be very restrictive. It appears from experiments it is a hyper-parameter. So, when one set it to a small number, isn’t the explainer forced to give very naive explanations? e.g. mostly as subset of 1-ho neighbors? - Further, a lot of GNN models have been developed with a promise that one can capture information from far away nodes through message passing atleast in few hop (>1) neighborhood. But the restriction in the paper to have connected subgraph as explanation is counterintuitive to that. - What is the purpose of subgraph constraint A_S? And why is it explicitly required? Isn’t it naturally enforced based on definition? - Further, how do you ensure that these restrictions in-fact, are not contaminating the explanation i.e. the explanation obtained for the prediction are mainly the result of this restrictive approach and not the artifact of the model? - While the authors mention in a section that this approach is model-agnostic and can be applied to any model post-facto, it is still important to see how (if anything) would be required to change when intricacies of some other model are involved? Does it mean that for any other model, exact same objective will still be able to lead to accurate explanations? Or will you need to change the objective (input to the objective ,e.g. what to condition the predictions on), based on the model? - If a GNN model uses simple attention mechanism on features (to distinguish from GAT), will GNN Explainer still perform able to capture important features effectively? Experiments: —————- - How much role did regularization play in the overall performance? You have multiple components in the. loss function, can you provide an ablation on what happens if you only optimize for structure vs feature vs both (plus regularization ,etc)? - For the quantitative analysis on synthetic data, how do you come up with the ground truth explanation? Is it curated manually? - Overall, the experiments are very limited and does not fully expose the use of this approach: - Specifically, the authors mention multiple times that such a tool can be used to analyse false predictions made by model. It is very important for this paper to provide empirical (quantitative or qualitative) to this with some examples may be where the model does bad prediction and the explanation is able to capture it. - Further, while the authors compare with few weak baselines (this is not a negative, it is understandable that no strong baseline exist) on multiple datasets, a more insightful experiment would be to compare different GNN models on same dataset and demonstrate how the GNNExplainer captures different characteristics for different models. - While there are some experiments shown for subgraph based explanation, experiments on node features are very limited. More experiments are needed to convincingly show that GNNExplainer are able to actually focus on most important features. - How does the method perform with changing restrictions on subgraph size, feature dimensions etc.? One can assume the trade-off between larger vs useful explanation but it is important to see this tradeoff by experiments to understand the effectiveness of GNNExplainer in capturing the optimal subcomponents/ sub features that leads to predictions.

This paper proposes to provide a model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model by providing an explanation in the form of a small subgraph of the input graph together with a small subset of the most influential node features. The authors validate their proposed approach through several experiments This paper reads well and the results appear sound. I personally find the methodology and the provided techniques to overcome the challenges in each step very interesting. Furthermore, the provided experiments support their intuition and arguments. As for the drawbacks of this paper, I find the relationship to the prior works partly unclear. Furthermore, the related work study is missing some of the most recent works on explaining the learning methods on graphs [1,2,3]. Moreover, It would be nice if the authors could also provide some ideas for future research directions, such as the prospects of using their approach for improving node classification and link prediction tasks. [1] Dai, Hanjun, et al. "Adversarial attack on graph structured data.". [2] Zügner, Daniel, Amir Akbarnejad, and Stephan Günnemann. "Adversarial attacks on neural networks for graph data.". [3] Pezeshkpour, Pouya, Yifan Tian, and Sameer Singh. "Investigating Robustness and Interpretability of Link Prediction via Adversarial Modifications.".