Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks

We gratefully thank the anonymous reviewer for their appreciation of our contribution of exact Shapley interactions for GNNs, and the time invested and thoughtful comments to help us convey the contribution of our manuscript! We address the weaknesses and questions in the following:

Weaknesses

• W1 (linear readout): Yes, we discuss this limitation in Section 5 and 6. In this case, it will arguably be infeasible to compute MIs, since they are not restricted by the graph structure within the GNN, as shown in Figure 6. However, our empirical results indicate that SIs are quite similar to GNNs with non-linear readouts. In our view, it is thus not advisable to use the paradigm of GraphSHAP-IQ, i.e. exact computation of MIs and deriving SIs from them, but rather rely on approximation methods of SIs directly. Overall, we strongly believe that our theoretical results and the introduction of MIs to understand interactions in GNNs will enable the development of approximation methods specifically tailored to GNNs, since our results still hold on intermediate layers of the GNN, e.g. before non-linear readout. In this context, we have already extended GraphSHAP-IQ with such a graph-inspired approximation variant. However, our main contribution in this paper is the exact computation and theoretical results on sparse MIs.
• W2 (visualization): Thank you for raising this important point! We fully agree that higher-order visualizations are more challenging to interpret. The SIs yield a flexible trade-off between complexity (of visualization) and faithfulness (to the game). For standard two-way interactions, we rely on a modified network plot, which is standard for graphs [1]. Moreover, with the SI-Graph (Definition 3.1 and e.g. Figure 1), we propose an intuitive visualization technique that extends this concept to any-order interactions. Yet, exploring other visualization and human-centered post-processing of SIs remains an important direction for future research.
• W3 (notations): Thank you for this valuable suggestion! In the revised version, we added a notation table in the appendix.

Questions

• Q1 (top-k): Yes, in this particular example, the approximated TOP-2 and TOP-6 interactions fully coincide with the ground-truth TOP-2 and TOP-6 set (independent of order). In practice, the choice of $k$ is however very critical and a good choice for $k$ is unknown. To illustrate this, we conducted a small study on this instance by measuring the ratio of approximated TOP-k interactions with the set of TOP-k ground-truth interactions (independent of their order) of varying $k$, which we collect in the following table for the discussed example (row 1), averaged over 100 graphs from MTG with 20-40 nodes for SV (row 2), 2-SII (row 3), 3-SII (row 4). The results show that TOP-k approximated interactions generally do not agree with TOP-k ground-truth interactions, which gets substantially worse for higher orders. |k|1|2|3|4|5|6|7|8|9|10| |-|-|-|-|-|-|-|-|-|-|-| |Example Figure 1/4|0|1|0.67|0.75|0.8|1|0.86|0.88|0.8|0.81| |SV|0.69|0.77|0.78|0.82|0.82|0.82|0.82|0.83|0.85|0.86| |2-SII|0.62|0.76|0.82|0.84|0.81|0.80|0.80|0.81|0.82|0.83| |3-SII|0.45|0.51|0.49|0.50|0.48|0.48|0.47|0.48|0.49|0.49|

• Q2 (runtime): Thank you for highlighting the computational aspects! To clarify this aspect, we extended our experiments with an analysis of the computational complexity (see general statement above and Appendix G.2). Following your suggestion, we exchanged the middle plot of Figure 4 with the runtime analysis for GraphSHAP-IQ and the baselines. We display average MSE against runtime in log-seconds for each method, which clearly shows how baseline methods behave in terms of computational cost and performance. Notably, the runtime of GraphSHAP-IQ is similar to the baseline methods for order 1 (SV). In contrast to the baselines, the runtime is unaffected by increasing explanation orders, while still providing exact explanations.

• Q3 (CNNs): Thank you for this brilliant remark! Yes, our theoretical results apply to CNNs, provided that there is a linear pooling and linear readout after the convolutions. However, for CNNs these assumptions are less common than for GNNs. Yet, our theoretical results apply to any model with spatially restricted features, e.g. topological deep learning [2], as long as these features are only linearly transformed for prediction. We added this remark to future work.

[1] Inglis, Alan, Andrew Parnell, and Catherine B. Hurley. "Visualizing variable importance and variable interaction effects in machine learning models." Journal of Computational and Graphical Statistics 31.3 (2022): 766-778

[2] Papillon, Mathilde, et al. "Architectures of Topological Deep Learning: A Survey of Message-Passing Topological Neural Networks." (2023)

Dear Reviewer cY3Q,

I largely concur with the Authors' analysis of your review; it is a negative-leaning review that gives almost nothing concretely actionable (beyond amending and concretising relations to related work) that the Authors can do to improve their standing.

If you were an Author, you probably would not appreciate receiving reviews like this.

I kindly ask you to concretely specify which actions you'd like the Authors to do in order for you to consider increasing your score. For example:

• What needs to be changed about the logical structure?
• What are the key grammatical issues you have noticed?
• What is unconvincing about the motivation of the paper?
• Which experiments should the Authors attempt to run?

If you do not provide such actions in time for the Authors to respond to them, I would likely discard your review from consideration.

Best, AC

Dear reviewer, we are very disappointed by what you have presented as a "review" and feel that the enormous amount of work we have put into our paper has not been valued. Your feedback is completely generic, lacking in substance and providing little to no actionable points for improving the manuscript. Frankly, we don't see how we can respond to your comments in any meaningful way.

To answer your question: At the core of our theoretical results is Assumption 3.4 on the GNN architecture. With the performances in Table 1 we want to show that GNNs under this assumption still achieve performances comparable to other literature.

We gratefully thank the anonymous reviewer for their time and critical view of our work! We hope to clarify the raised weaknesses and questions in the following:

Novelty:

Thank you for raising this important point! For further clarification, we added a detailed discussion of related work, including GraphSVX, in the appendix (see general statement above). In fact GraphSVX (Duval & Malliaros, 2021) consider node prediction and discard (dummy) nodes outside of the receptive fields of the node embeddings. Instead, GraphSHAP-IQ considers graph prediction, and discards (dummy) interactions, that are not fully contained in any of the receptive fields. Notably, GraphSVX's reasoning does not apply to graph classification (there are no dummy nodes on graph level!), and none of our theoretical results can be established with their arguments. In fact, for graph classification, GraphSVX considers all nodes, and therefore proposes a model-agnostic sampling-based approximation for the SV (KernelSHAP baseline). GraphSVX for graph prediction is therefore not structure-aware, as mentioned in our introduction (line 078-079) and in their paper:

We simply look at $f(X, A) \in R$ instead of $f_v(X, A)$, derive explanations for all nodes or all features (not both) by considering features across the whole dataset instead of features of v, like our global extension.

In detail, GraphSVX for node classification relies on the SV and the dummy axiom. It is argued that the node embedding of a node $v$ is not affected by a node $q$ outside the $\ell$-hop neighborhood of $v$, and thus by the dummy axiom the SV of node $q$ must be zero. Their reasoning also follows formally from our Lemma 3.5, since the SV of node $q$ is constructed from the MIs of sets $S$ that contain $i$, which are never fully contained in the $\ell$-hop neighborhood and are thus zero. However, as also observed by Duval & Malliaros (2021), the argument via SV and dummy axiom does not hold on graph level, since there are no dummy nodes in graph classification (all nodes affect the prediction on graph level)! In contrast, we proposed to investigate the purified interactions (MIs), where we established (Proposition 3.6) that indeed on graph level dummy interactions actually exist (provided linear global pooling and readout). In contrast, for graph classification GraphSVX approximates the SV directly for a game with all nodes $N$ requiring $\vert \mathcal P(N) \vert = 2^n$ calls for exact computation, whereas GraphSHAP-IQ computes exact MIs for all sets in $\mathcal I = \bigcup_{i \in N} \mathcal P(\mathcal N^{(\ell)}_i)$, which requires substantially less model calls $\vert I \vert \ll 2^n$. This result is the core of our main contribution (Theorem 3.7), which allows for the efficient computation of MIs. Consequently we are able to derive exact SVs and SIs from the exact MIs, whereas GraphSVX (for graph classification) is a model-agnostic approximation.

Experiments:

Your suggestion is a great motivation for the development of new algorithms in future work, which we briefly mentioned in line 524-526! Unfortunately, our results are not applicable to any of the baseline methods. In short, model-agnostic approximations rely on game evaluations (masked predictions $\nu_g(T)$ that are not sparse), whereas GraphSHAP-IQ and our theoretical results rely on (sparse) MIs ($m_g(S)$). More concretely, GraphSHAP-IQ does not disregard any nodes, instead, it disregards dummy interactions (MIs for set of nodes) to compute all non-trivial MIs ($m_g(S)$, Proposition 3.6). From the exact non-trivial MIs (defined for the whole powerset $\mathcal P(N)$), we were able to derive the exact SVs (defined for single nodes, $\Phi_1(i)$ ) and SI (defined for sets up to size $k$, $\Phi_k(S)$). In contrast, all baseline methods directly compute SVs or SIs by Monte Carlo approximation using randomly sampled game values (masked predictions $\nu_g(T)$). Unfortunately, a zero value of the MI $m_g(S)$ does not translate to a zero-valued masked prediction $\nu_g(S)$, and thus does not allow to restrict the sampling space for the baselines. Yet, as mentioned in future work (line 524-526), we believe that our findings of dummy interactions (Proposition 3.6) could still be used to inspire novel graph-informed approximation techniques. In this context, we have already extended GraphSHAP-IQ with such a graph-inspired approximation variant, which we used for the extreme cases, where the exact computation is infeasible, cf. empirical evaluation in Experiment 4.2. However, our main contribution in this paper is the exact computation and theoretical results on dummy interactions.

We gratefully thank the anonymous reviewer for appreciating the novelty and theoretical results of our work. We would like to engage with you with the following point-by-point response to your questions and concerns, and hope to make you more convinced about our contribution.

• W1: Thank you for this valuable suggestion. In our work, instead of measuring the actual computational time, we relied on the number of model calls as the main driver for computational complexity. This is standard in related work of the model-agnostic baseline methods, which scale linearly with number of model calls. To verify this behavior, we added a runtime analysis (see general statement for details).
• W2: We fully agree that exact computation depends on the receptive fields and graph density (sparsity of edges), but we disagree that larger graphs are a problem! As we show theoretically (Theorem 3.7) and empirically (Experiment 4.1) the complexity does depend at most linearly on the size of the graph. This is in stark contrast to the model-agnostic computation, which scales exponentially with the number of nodes. While GNNs each convolutional layer increases the initial budget, the size of the graph is not a limiting factor in general, e.g. in Figure 3, left, we observe that for 2-Layer GNNs a budget of $10k$ suffices to compute exact SIs for graphs up to size 55, which would otherwise require $2^{55} \approx 10^{16}$ model calls. For the 3-Layer GNN, we require in this case between $10^7-10^8$ model calls with GraphSHAP-IQ for all instances, independent of size. To verify that the complexity scales only linearly with size, we additionally computed the $R^2$ of all fitted logarithmic curves (solid lines) in Figure 3 and other benchmark datasets in Figure 7-9, and added them to the labels. The logarithmic fit in the exponentially scaled plot (i.e. linear fit) exhibits a moderate ($R^2\approx 0.5$) to strong ($R^2>0.9$) $R^2$ fit, which validates that the complexity of the computation grows linearly with the size of the graph. Note that this behavior is across all instances, independent of a specific graph structure. Yet, as mentioned in the paper, in extreme cases exact computation might still be restricted, where the approximation of GraphSHAP-IQ should be used, which allows for a flexible budget range.
• W3: Yes, we discuss this limitation in Section 5 and 6. In this case, it will arguably be infeasible to compute MIs, since they are not restricted by the graph structure within the GNN, as shown in Figure 6. However, our empirical results indicate that SIs are quite similar to GNNs with non-linear readouts. In our view, it is thus not advisable to use the paradigm of GraphSHAP-IQ, i.e. exact computation of MIs and deriving SIs from them, but rather rely on approximation methods of SIs directly. Overall, we strongly believe that our theoretical results and the introduction of MIs to understand interactions in GNNs will enable the development of approximation methods specifically tailored to GNNs, since our results still hold on intermediate layers of the GNN, e.g. before non-linear readout. In this context, we have already extended GraphSHAP-IQ with such a graph-inspired approximation variant. However, our main contribution in this paper is the exact computation and theoretical results on sparse MIs.
• Q1: Yes, of course! All our results directly transfer to node prediction, which relates to the simplistic setting of a single node game $\nu_i$ from Definition 3.2. Note that this is the trivial setting, where Assumption 3.4 (linear pooling and readout) is not even required! We can directly compute all MIs and corresponding SVs or SIs using Theorem 3.3. However, in this simplistic setting, arguments from GraphSVX (Duval & Malliaros, 2021) could be applied, which remove nodes that do not affect the node embedding using the dummy axiom. At the core of our contribution are graph predictions, and specifically the usage of MIs to derive efficient computation on the graph level. As noted by Duval & Malliaros (2021) their reasoning via SVs does not transfer to graph prediction, because there are no dummy features on the graph level. However, as established in our work (Proposition 3.6), there are indeed dummy interactions (MIs), which allow to efficiently compute MIs on graph level and then derive SVs and SIs from later on.
• Q2: Thank you for this question! We discuss this in the paragraph "Node Masking" and now clarify this in lines 284-286. Our theoretical results hold for any masking technique, provided that it can be applied to any subset of nodes. We decided to rely on BSHAP as a generally applicable, well-established and theoretically well-understood choice, and it remains important future work to explore other choices that are more suitable to specific use cases.

After discussion with the area chair zvPV and follow-up response of reviewer dedn, we $\color{blue}\text{added}$ the following:

• We restructured the related work section in the main paper, and moved the comprehensive overview to Appendix C. Moreover, we added a detailed comparison with other approaches, such as GraphSVX or TreeSHAP in Appendix C.1. (requested by reviewer dedn, cY3Q and area chair zvPV)
• For each model-agnostic baseline for approximation of SIs, we added an interaction-informed variant. Accordingly, we adapted Section 3.3, and added a new section with details in Appendix D.3. Moreover, we extended the empirical analysis in Section 4.2. (requested by reviewer dedn)