GOAt: Explaining Graph Neural Networks via Graph Output Attribution

W1: First, as discussed in Sections 1 and 5, most existing instance-level methods train a secondary model to identify the critical graph structures, resulting in black-boxed explanations and unnecessary cost. Second, explanations generated by the existing explainers may not be deterministic or consistent for the same input graph over different runs, because each run of secondary model learning may lead to different outcomes. Moreover, a number of approaches require gradient back-propagation, and suffer from the saturation problem (Shrikumar et al., 2017), where a saturated gradient refers to a function for which a bigger input will not lead to a relevant increase in output. So if the gradient is saturated (which means it is extremely close to zero), a bigger upstream gradient does not lead to a bigger current gradient when applying the chain rule. We revisit the research question of GNN explanation and point out that there is no need to train auxiliary models or use gradient information for GNN explanation. Rather, by directly analyzing the GNN input-output relationship itself, GOAt is a training-free method without requiring any auxiliary model. GOAt forwardly attributes graph outputs to input graph features (and edges), naturally producing consistent explanations across different runs, and avoids relying on gradients. Moreover, GOAt demonstrates stronger fidelity, discriminability and stability through experiments on 6 datasets over 3 types of GNNs.

W2: As we explained at the beginning of Section 3, we first expand the GNN output as a sum of scalar products involving input features (e.g. edges) and activation patterns. Then for each scalar product, we apply Equal Contribution concept. We have added a figure (Figure 1) illustrating our method in the updated manuscript (highlighted in red). As Figure 1 shows, we first expand the representation of GNN’s input-output relation into a sum of product terms. For example, the expansion form of an element in the output matrix can be $y_{13}=10A_{11}A_{12}A_{23}+8A_{11}A_{13}A_{33}+11A_{12}A_{21}A_{13}$. Then, for each product term, like $10A_{11}A_{12}A_{23}$, the elements in adjacency matrix $A$ are from {0,1}, indicating the absence or presence of edges between pairs of nodes. The absence of any edge among $A_{11}, A_{12}, A_{23}$ would make the whole term $10A_{11}A_{12}A_{23}$ equal to $0$. Therefore, we say that the three edges are equally important to this product term. Hence, all three edges evenly share the contribution to this term, where each edge contributes $10/3$. Finally, we investigate all the product terms, and obtain the contribution of each edge by summing up its contribution to all the product terms. For instance, the contribution of $A_{11}$ to output $y_{13}$ is $10/3+8/3=6$. The proof of Equal Contribution in a scalar product can be found in Appendix A.

W3: As discussed in Sections 1 and 5, GLGExplainer and GCFExplainer are global-level explainers, whereas this paper focuses on instance-level GNN explainability. Therefore, they did not appear in the experiments as baselines.

W4: We notice that the reviewer wrote in the summary that “Empirical results on three well-known datasets show the effectiveness of the proposed method”. In fact, we conducted experiments on 6 datasets, including 3 node classification datasets and 3 graph classification datasets. Major works in this domain test on 5~7 datasets, e.g., PGExplainer (NeurIPS'20) tested on 6 datasets, SubgraphX (NeurIPS'21) tested 5 datasets, RG-Explainer (NeurIPS'21) 6 datasets, RCExplainer (NeurIPS 2021) 7 datasets, DEGREE (ICLR 2022) 6 datasets, TAGE (NeurIPS 2022) 6 datasets. Furthermore, unlike most existing methods that were only tested on GCN, we additionally conducted experiments on more variants of GNNs (including GCN, GIN, GraphSAGE). We even re-ran all the baselines since they were not trained on GIN or GraphSAGE. We re-implemented some baselines, e.g., because author implementation of DEGREE suffers from memory leak, RCExplainer is not open-sourced, subgraphX is a costly search-based method, RCExplainer, RG-Explainer are RL methods requiring long training. These represent extensive and significant experimental efforts, comparable to or even more than the prior works. Moreover, during the rebuttal period, we ran additional experiments on BBBP, providing further evidence of our approach's efficacy (see Appendix L, highlighted in red). These additional results align with the discussion in Section 4, which shows that our method outperforms all baseline methods.

W5: Thanks for pointing out the typo. We have removed it from the updated manuscript.

We would appreciate it if the reviewer could re-assess the work. The gist here is that we show that GNN explanation really does not need to resort to gradient or another model. There is a surprisingly simple analytical way to attribute graph outputs to input features, which is also effective and beats SOTA methods.

W1: Thank you very much for the advice. We updated our manuscript by adding the empirical time analysis in Appendix K (highlighted in blue). We compared with the outstanding baselines, which are the perturbation-based method GNNExplainer (Ying et al., 2019), decomposition-based method DEGREE (Feng et al., 2022), and the search-based method SubgraphX (Yuan et al., 2021). Our approach is much faster than SubgraphX and GNNExplainer, and runs slightly faster than DEGREE while providing more faithful, discriminative and stable explanations as demonstrated in Section 4, which showcases the significance of our method.

W2: We updated our manuscript by adding the formulas that compute discriminability and stability in Section 4.2 and 4.3. (highlighted in blue).

Q1: When we evaluate the discriminability, we filtered out the wrongly predicted data samples. Therefore, only when GNN makes a correct prediction, the embedding would be included in the discriminability computation. We updated our manuscript by adding this clarification in Section 4.2. (highlighted in blue)

Q2: To clear up the confusion on the definition of coverage/stability, we have updated the manuscript with the formula to calculate stability in Section 4.3 (highlighted in blue). The reason our approach shows high coverage for BA-2Motifs but relatively low coverage for Mutagenicity and NCI1 is rooted in the nature of these datasets. BA-2Motifs is synthetic, where the GNN achieves a 100% prediction accuracy (Table 2). This makes outstanding subgraphs, like the "house" motif, clearer to the original GNN, making it easier for our explainer to achieve high coverage with just a few explanation subgraphs. On the other hand, Mutagenicity and NCI1 are real-world datasets where the original GNNs achieve around 80% accuracy. This poses a challenge for the GNN itself to identify important subgraphs. Moreover, these real-world datasets involve more types of subgraphs, making it difficult to achieve high coverage with only a few explanation subgraphs. Therefore, the results from all baselines, including our method, are reasonable given these challenges.

W1: Our primary goal is to introduce a training-free explanation algorithm that calculates the importance of graph components for each data instance in a forward analytical manner. While our main emphasis isn't on minimizing computation complexity, we've incorporated an empirical time cost analysis in Appendix K (highlighted in blue) to provide additional insights into the computational aspects of our approach. We compared with the outstanding baselines, which are the perturbation-based method GNNExplainer (Ying et al., 2019), decomposition-based method DEGREE (Feng et al., 2022), and the search-based method SubgraphX (Yuan et al., 2021). As an analytical method, our approach is much faster than SubgraphX and GNNExplainer, and runs slightly faster than DEGREE while providing more faithful, discriminative and stable explanations as demonstrated in Section 4, which showcases the significance of our method.

W2: In response to the reviewer's suggestion, we have added a figure (Figure 1) illustrating our method in the updated manuscript (highlighted in red). As illustrated in Figure 1, we first expand the representation of GNN’s input-output mapping to a sum of product terms. For example, the expansion form of an element in the output matrix can be $y_{13}=10A_{11}A_{12}A_{23}+8A_{11}A_{13}A_{33}+11A_{12}A_{21}A_{13}$. Then, an example of a product term is $10A_{11}A_{12}A_{23}$. The elements in the adjacency matrix $A$ can take values from {0,1}, indicating the absence or presence of edges between pairs of nodes. The absence of any edge among $A_{11}, A_{12}, A_{23}$ would make the whole term $10A_{11}A_{12}A_{23}$ equal to $0$. Therefore, we say that the three edges are equally important to this product term. Hence, all the three edges evenly share the contribution of this term, where each edge has a contribution of $10/3$. Finally, we investigate all the product terms, and obtain the contribution of each particular edge by summing up its contribution to all the product terms. For instance, the contribution of $A_{11}$ to $y_{13}$ is $10/3+8/3=6$.

W1: In Section 5, we already have discussed the methods mentioned by the reviewer, namely, Pope et al. (2019) and Schnake et al. (2021). Pope et al. (2019) propose several methods, namely, SA, CAM, Grad-CAM and Excitation-BP, where Excitation-BP is categorized as a decomposition method according to the survey paper [4]. On the other hand, Schnake et al. (2021) proposes a decomposition method GNN-LRP. These methods measure the importance of input features by decomposing the original model predictions into the importance scores of the corresponding input features. And what's important is that they all rely on gradient backpropagation to achieve this. As gradient-based methods, they face the saturation problem (Shrikumar et al., 2017), where a saturated gradient refers to a function for which a bigger input will not lead to a relevant increase in output. So if the gradient is saturated (which means it is extremely close to zero), a bigger upstream gradient does not lead to a bigger current gradient when applying the chain rule. Saturated gradients may potentially lead to less faithful explanations generated by these gradient-based methods.

The novelty of our approach is not that it is a decomposition method (there are a bunch of decomposition methods already). Rather, the novelty of GOAt lies in that we directly attribute graph outputs to input graph features in an analytical way based on the notion of “equal contribution” without using gradients at all, thus not suffering from the issues these gradient methods are suffering from. That is, the idea proposed by this work is to offer a way to directly attribute GNN output to each input graph feature including edges. This is the major difference and novelty which depart from how the gradient-based methods derive explanations.

[4] Yuan, Hao, et al. “Explainability in Graph Neural Networks: A Taxonomic Survey.” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, pp. 1–19.

W2: We did have compared our method with the leading decomposition method DEGREE (Feng et al., 2022) in our experiments already, which is a more recent decomposition method than Pope et al. (2019) and Schnake et al. (2021). Please check Section 4 and Appendix G for detailed insights. Through extensive experiments across 6 datasets and 3 variants of GNNs, our approach consistently demonstrates superior faithfulness, discriminability, and stability compared to the baseline methods.

W3: Thank you for recommending a recent related work. We will cite and discuss this work. This paper also points out some issues of existing work that the explanations generated by some typical existing explanation methods may not be deterministic even for the same input graph, since they require training an auxiliary or secondary model; the auxiliary model may generate inconsistent explanations even for the same input graph over different runs of the model training. A lack of consistency will compromise the faithfulness of the explanation as well. To address this issue, they introduce alignment objectives to improve existing methods that require auxiliary model training, where the embeddings of the explanation subgraph and the raw graph are aligned via anchor-based objective function, distributional objective function based on Gaussian mixture models, and mutual information-based objective functions. In contrast, we propose a completely training-free instance-level explainer that does not need to be optimized to any learning objective. Being a novel analytical framework without resorting to an auxiliary model or training at all, GOAt naturally generates consistent explanations across different runs. Furthermore, GOAt offers the additional advantage of producing stable explanations even across similar graph samples as has been demonstrated in our experiments, proving the significance of our approach. We have added discussion on this related work in Section 5 in the updated manuscript (highlighted in green).

We are committed to addressing reviewer concerns and improving the quality of this research. It is much appreciated if the reviewer could reassess the quality of this work. It is worth noting that we are not missing important related work and our analytical framework GOAt is fundamentally different from and performs better than gradient-based decomposition methods, as has been demonstrated in the paper.