Reply to Reviewer dedn
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.