Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks
Authors: Maximilian Muschalik
Fabian Fumagalli
Paolo Frazzetto
Janine Strotherm
Luca Hermes
Alessandro Sperduti
Eyke Hüllermeier
Barbara Hammer
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks (GNNs)
Shapley Interactions
Game Theory
Explainable AI
Feature Interactions
Primary area: interpretability and explainable AI
TL;DR: We propose a model-specific method to compute exact Shapley value attributions and interactions for graph neural networks akin to TreeSHAP for trees.

Abstract: Albeit the ubiquitous use of Graph Neural Networks (GNNs) in machine learning (ML) prediction tasks involving graph-structured data, their interpretability remains challenging. In explainable artificial intelligence (XAI), the Shapley Value (SV) is the predominant method to quantify contributions of individual features to a ML model’s output. Addressing the limitations of SVs in complex prediction models, Shapley Interactions (SIs) extend the SV to groups of features. In this work, we explain single graph predictions of GNNs with SIs that quantify node contributions and interactions among multiple nodes. By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction. As a result, the exponential complexity of SIs depends only on the receptive fields, i.e. the message-passing ranges determined by the connectivity of the graph and the number of convolutional layers. Based on our theoretical results, we introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly. GraphSHAP-IQ is applicable to popular message passing techniques in conjunction with a linear global pooling and output layer. We showcase that GraphSHAP-IQ substantially reduces the exponential complexity of computing exact SIs on multiple benchmark datasets. Beyond exact computation, we evaluate GraphSHAP-IQ’s approximation of SIs on popular GNN architectures and compare with existing baselines. Lastly, we visualize SIs of real-world water distribution networks and molecule structures using a SI-Graph.

Published as a conference paper at ICLR 2025
EXACT COMPUTATION OF ANY-ORDER SHAPLEY IN- TERACTIONS FOR GRAPH NEURAL NETWORKS
Maximilian Muschalik 1.,3, Fabian Fumagalli Paolo Frazzetto Janine Strotherm?,
Luca Hermes?, Alessandro Sperduti 3.445, Eyke Hüllermeier', BBarbara Hammer
LMU Munich, MCML Bielefeld University, CITEC University of Padova
4 University of Trento
Augmented Intelligence Center, FBK
Equal Contribution
B Corresponding Author: maximi 1 www.aami....m.mmaaaa..... de
ABSTRACT
Albeit the ubiquitous use Graph Neural Networks (GNNs) in machine learning (MI.) prediction tasks involving graph-structured data, their interpretability re- mains challenging. In explainable artificial intelligence (XAI), the Shapley Value (SV) is the predominant method to quantify contributions of individual features to a ML model's output. Addressing the limitations of SVs in complex prediction models, Shapley Interactions (SIs) extend the SV to groups of features. In this work, we explain single graph predictions of GNNs with SIs that quantify node contributions and interactions among multiple nodes. By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction. As result, the exponential complexity of SIs depends only on the receptive fields, i.c. the message-ppssing ranges determined by the connectivity of the graph and the number of convolutional layers. Based on our theoretical results, we introduce GraphSHAP-IQ. an efficient approach to compute any-order SIs exactly. GraphSHAP-IQ is applicable to popular message- passing techniques in conjunction with linear global pooling and output layer. We showcase that GraphSHAP-IQ substantially reduces the exponential complex- ity of computing exact SIs on multiple benchmark datasets. Beyond exact com- putation, we evaluate GraphSHAP-IQ's approximation of SIs on popular GNN architectures and compare with existing baselines. Lastly. we visualize SIs of real-world water distribution networks and molecule structures using a SI-Graph.
INTRODUCTION
Graph-structured data appears in many domains and real-world applications (Newman, 2018), such as molecular chemistry (Gilmer et al., 2017), water distribution networks (WDNs) (Ashraf et al., 2023), sociology (Borgatti et al., 2009), physics Manchez-Gonzablee et al., 2020), or human re- sources (Frazzetto et al., 2023). To leverage such structure in machine learning (ML) models, Graph Neural Networks (GNNs) emerged as the leading family of architectures that specifically exploit the graph topology (Scarselli al., 2009). A major drawback of GNNs is the opacity of their predic- tive mechanism, which they share with most deep-learning based architectures (Amara et al., 2022). Reliable explanations for their predictions are crucial when model decisions have significant conse- quences (Zhang et al., 2024) or lead to new discoveries (McCloskey et al., 2019).
In explainable artificial intelligence (XAI), the Shapley Value (SV) (Shapley, 1953) is a prominent concept to assign contributions to entities of black box ML models (Lundberg & Lee, 2017: Covert et al., 2021; Chen et al., 2023). Entities typically represent features, data points (Ghorbani & Zou, 2019) graph structures (Yuan et al., 2021; Ye et al., 2023). Although SVs yield an axiomatic attribution scheme, they do not give any insights into joint contributions of entities, known as inter- actions. Yet, interactions are crucial to understanding decisions of complex black box ML models (Wright et al., 2016; Sundararajan et al., 2020; Kumar et al., 2021). Shapley Interactions (SIs) (Gra- bisch & Roubens, 1999; Bordt & von Luxburg, 2023) extend the SV to include joint contributions of multiple entities. SIs satisfy similar axioms while providing interactions up to a maximum num- ber of entities, referred as the explanation order. In this context, SVs are the least complex SIs,

---

Published as a conference paper at ICLR 2025
high pox
Ione pos
high
SI order
lick
kon neg.
High ong.
Exact SVs
Exact 2-SIIs
Exact MIs
molecule graph showing exact SIs for a molecule with 30 atoms from MTG. A GNN correctly identifies it mutagenic. The SIs, in line with ground- truth knowledge, highlight the NO₂ groups. Computing exact SIs requires 230 10 model calls. GraphSHAP-IQ needs 7 6933.
Figure SI-Graphs overlayed
whereas Möbius Interactions (MIs) (or Möbius transform) (Harsanyi. 1963; Rota, 1964) are the most complex SIs by assigning contributions to every group of entities. Thus, SIs convey an adjustable explanation with accuracy- compleiyy trade-off for interpretability (Bordt & von Luxburg, 2023). SVs, SIs and MIs are limited by exponential complexity, c.g. with 20 features already 2n x 10t model calls per explained instance required. Consequently, practitioners rely model-agnostic approximation methods (Lundberg & Lee, 2017: Fumagalli et al., 2023) or model-specific methods (Lundberg et al., 2020; Muschalik al., 2024b) that exploit knowledge about the model's structure to reduce complexity. As a remedy for GNNs, the SV was applied as a heuristic on subgraphs (Ying al., 2019; Ye et al., 2023), or approximated (Duval & Malliaros, 2021: Bui al., 2024).
In this work, we address limitations of the SV for GNN explainability by computing the SIs visu- alized as the SI-Graph in Figure 1. Our method yields exact SIs by including GNN-specifi knowl- edge and exploiting properties of the SIs. In contrast to existing methods (Yuan et al., 2021; Ye al., 2023), we evaluate the GNN on node level without the need cluster nodes into subgraphs. Instead of model-agnostic approximation (Duval & Malliaros, 2021; ; Bui al., 2024), structure-awarc computation for graph prediction tasks, and prove that MIs of node embeddings in- deed transfer to graph prediction for linear readouts. In summary, approach is model -seccfic computation of SIs for GNNs, akin to TreeSHAP (Lundberg et al., 2020) for tree-based models.
provide
Contribution. Our main contributions include:
(1) We introduce SIs among nodes and the SI-Graph for graph predictions of GNNs that ad- dress limitations of the SV and exploit graph and GNN structure with our theoretical results.
(2) We present GraphSHAP Interaction Quantification (GraphSHAP-IQQ, efficient method to compute exact any-order SIs in GNNs. For restricted settings requiring approximation, extend GraphSHAP-IQ and propose several interactioninformee baseline methods.
(3) We show substantially reduced complexity when applying GraphSHAP-IC on real-world benchmark datasets, and analyze SI-Graphs WDN and molecule structures.
(4) We find that interactions in deep readout GNNs are not restricted to the receptive fields.
Related Work. SIs, enriching the SV (Shapley, 1953) with higher-order interactions, were intro- duced in game theory (Grabisch & Roubens, 1999), and modified for local interpretability in ML (Lundberg et al.. 2020; Bordt & von Luxburg, 2023). The exponential complexity of the SV and SIs requires approximation by model-agnostic Monte Carlo sampling (Chen al., 2023; Fumagalli et al., 2023) or by exploiting the data structure (Chen et al., 2019). Exact computation is only feasi- ble with knowledge about the structure of the model and model-specific methods, such as TreeSHAP (Lundberg et al., 2020; Muschalik et al., 2024b), which is applicable to tree ensembles. Here, present model-specific method applicable to GNNs and graph prediction tasks, which computes exact SIs by exploiting the graph and GNN structure.
For local explanations of GNNs and graph prediction tasks, a variety perturbation- based methods (Ying et al., 2019; Luo et al., 2020: Yuan et al., 2021) have been proposed, which output isolated
2

---

Published as a conference paper at ICLR 2025
subgraphs. whereas Pope al. (2019) introduce node attributions. In this work, tions via node maskings and output attributions for all nodes, and all subset of nodes up to the given explanation order, which additively decomposes the graph prediction of the GNN. In context of GNN interpretabilityy the SV was applied in GraphSSXX (Duval & Malliaros, 2021) on single nodes with structure-aware approximation for node predictions. For graph prediction tasks, however, GraphSVX proposes a model-agnostic approximation. SubgraphX (Yuan et al., 2021) and SAME (Ye et al., 2023) use the SV assess the quality of isolated subgraphs. Recently, model- agnostic approximation of pairwise SIs have shown to improve isolated subgraph detections (Bui al., 2024). In contrast to existing work, we propose structure aware method that efficiently computes exact SVs for single nodes and exact any-order SIs for subset of nodes for graph pre- diction tasks of GNNs. Our explanation is based on all possible interactions (MIs) and additively decomposes the prediction. For more detailed discussion of related work, we refer to Appendix C.
perturba-
2 BACKGROUND
In Section 2.1, we introduce SIs that provide an adjustable accuracy-complexity trade-off for ex- planations (Bordt von Luxburg, 2023). In this context, SVs are the simplest and MIs the most complex SIs. In Section 2.2, we introduce GNNs, whose structure we exploit in Section 3 to effi- ciently compute any-order SIs. A summary of notations can be found in Appendix A.
2.1 EXPLANATION COMPLEXITY: FROM SHAPLEY VALUES TO MÖBIUS INTERACTIONS
Concepts from cooperative game theory, such as the SV (Shapley, 1953), are prominent in XAI to interpret predictions of black box ML model via feature attributions (Strumbelj & Kononenko, 2014; Lundberg & Lee, 2017). Formally, a cooperative game P(N) R is defined, where individual features N = {1.....]] n act as players and achieve a payout for every group of players in the power set P(N). To obtain feature attributions for the prediction of a single instance, typically refers to the model's prediction given only subset of feature values. Since classical ML models cannot handle missing feature values, different methods have been proposed, such as model retraining (Strumbelj et al., 2009), conditional expectations (I (Lundberg & Lee, 2017; Aas et al., 2021; Frye et al., 2021), marginal expectations (Janzing et al., 2020) and baseline imputations (Lundberg & Lee, 2017: Sundararajan et al., 2020). In high-dimensional feature spaces, retraining models or approximating feature distributions is infeasible, imputing absent features with a baseline, known as Baseline Shapley (BShap) (Sundararajan & Najmi, 2020), is the prevalent method (Lundberg & Lee, 2017; Sundararajan et al., 2017: Jethani et al., 2022). We now first introduce the MIs as backbone of additive contribution measures. Later in Section 3, we exploit sparsity of MIs for GNNs to compute the SV and any-order SIs.
Möbius Interactions (MIs) m P(N) R.. are fundamental concept of cooperative game theory and provide the basis for different summary measures. The MI is
m(S) Σ (-1)111-17) and they recover v(T) Σ m()) for all S, N. (1) TCS
SCT
From the MIs, every game value can be additively recovered, and MIs are the unique measure with this property (Harsanyi, 1963; Rota, 1964). The MI of subset S C N can thus be interpreted as the pure additive contribution that is exclusively achieved by a coalition of all players in S, and cannot be attributed to any subgroup of S. The MIs are further basis of the vector space of games (Grabisch, 2016), and therefore every measure of contribution, such as the SV or the SIs, can be directly recovered from the MIs, cf. Appendix E.3.
Shapley Values (SVs) for players E N of a cooperative game v are the weighted average
S. (i) = Σ
(T) with (T( = x(T =(T) [
TENY
over marginal contributions (T). It was shown (Shapley, 1953) that the SV is the unique attribu- tion method that satisfies desirable axioms: linearity (the SV of linear combinations of games, e.g., model ensembles, coincides with the linear combinations the individual SVs), dummy (features that do not change the model's prediction receive zero SV), symmetry (if model does not change
3

---

Published as a conference paper at ICLR 2025
its prediction when switching two features, then both receive the same SV), and lastly efficiency (the sum of all SVs equals the difference between the model's prediction v(N) and the featureless prediction v())). We may normalize v, such that v(0) O, which does not affect the SVs. The SV assigns attributions to individual features, which distribute the MIs that contain feature i, cf. Ap- pendix E.3. However, the SV does not provide any insights about feature interactions, i.e. the joint contribution of multiple features to the prediction. Yet, in practice, understanding complex mod- els requires investigating interactions (Slack al., 2020; Sundararajan al., 2020; Kumar et al., 2021). While the SVs are limited in their expressivity, the MIs are difficult to interpret due to the exponential number of components. The SIs provide a framework to bridge both concepts.
Shapley Interactions (SIs) explore model predictions beyond individual feature attributions, and provide additive contribution for all subsets up to explanation order = =I...., n. More formally, the SIs & (N) - IR assign interactions to subsets of N up to size k, summarized in PaNN). The SIs decompose the model's prediction with (NN) = Esc SSN, s (S)) The least complex SIs are the SVs, which are obtained with A: = 1. For l = n, the SIs are the MIs with 2n components, which provide the most faithful explanation of the game but entail the highest complexity. SIs are constructed based on extensions of the marginal contributions (T)), known as discrete derivatives (Grabisch & Roubens, 1999). For two players j E N, the discrete derivative (T) for subset T S N \ ij is defined as (T) == (T Uij) - (T) - (T) A,(T), i.e., the joint contribution of adding both players together minus their individual contributions in the presence of T'. This recursion is extended to any subset S C N and T C N \ S. A positive value of the discrete derivative (T) indicates synergistic effects, a negative value indicates redundancy, and a value close to zero indicates no joint information of all players in S given T. The Shapley Interaction Index (SII) (Grabisch& & Roubens, 1999) provides an axiomatic extension of the SV and summarizes the discrete derivatives in the presence of all possible subsets T Tas
pi (S)
-E TENYS (n (n |S| + 11"+111)(1)))) (21
1
AT(
with As(T) = (-11)11144) L).
LCS
Given an explanation order k. the k-Shapley Values (k-SIIs) (Lundberg et al., 2020; Bordt & von Luxburg, 2023) construct SIs recursively based on the S11, such that the interactions of SII and k-SII for the highest order coincide. Alternatively, the Shapley Taylor Interaction Index (STI)) (Sundararajan & Najmi, 2020) and the Faithful Shapley Interaction Index (FSII) (Tsai et al., 2023) have been proposed, cf. Appendix F.2. In summary, SIs provide a flexible framework of increasingly complex and faithful contributions ranging from the SV (k- 1) the MIs (k n). Given the MIs, it is possible to reconstruct SIs of arbitrary order, cf. Appendix E.3. In Section 3, we will exploit the sparse structure of MIs of GNNs efficiently compute any-order SIs.
2.2 GRAPH NEURAL NETWORKS
GNNs are neural networks specifically designed to process graph input (Scarselli et al., 2009). A graph g (V, E, X) consists of sets of nodes V = (v1, .., Un edges E C V V and do- E Raxdo, where x; are the node features of node i/ E V. A message passing GNN leverages the structural information of the graph g to iteratively aggregate node feature information of a given node E V within its neighborhood ((v) == {u E V Euv E E}. More precisely, in each iteration t E {I,..., E). the de di-dimensional k-th hidden node
dimensional node features X = [x1..., x,]"
features H [h
(A))
ha E Bgn are computed node-wise wise by
h = X;
h (k) = (1) (((f)))))
|0 E (o))))))
where {{-}} indicates a multiset and (kk) and (kk) are arbitrary (aggregation) functions acting on the corresponding spaces. Moreover, e is implemented as a permutation inniaiaiiionnnniiannt function, ensuring independence of both the order and number of neighboring nodes, and allows for an embedding of multisets vectors. The node embedding function is thus f((X) = h!("), For graph prediction tasks, the representations of the last nodes (9) must be aggregated in a fixed-size graph embedding cermuutaiooninvarian
for the downstream task. More formally, this is achieved with an additional pooling function V and parametrized output layer a Rd + Rdd where duu corresponds to the output dimension. The output of GNN for graph-level inference is defined as
fg(X) == a (V(((((X) 02 E V)))).
For graph classification, class probabilities are obtained from fxX through softmax activation.
4

---

Published as a conference paper at ICLR 2025
3 ANY-ORDER SHAPLEY INTERACTIONS FOR GRAPH NEURAL NETWORKS
In the following, we are interested in explaining the prediction of GNN fg for graph g with respect to nodes. We aim to decompose a model's ' prediction into SIs 4 visualized by a SI-Graph.
Definition 3.1 (SI-Graph), The SI-Graph is an undirected hypergraph gh == (N. PN((N. 2x) with node altributes (x for i N and hyperedge attributes (x(S) for 2 S S S k.
The simplest SI-Graph displays the SVs (k 1) as node attributes, whereas the most complex SI-Graph displays the MIs (k: = n2) as node and hyperedge attributes, illustrated in Figure 1. The complexity of the SI-Graph is adjustable by the explanation order which determines the maximum hyperedge order. The sum of all contributions in the SI-Graph yields the model's prediction (for regression) or the model's s logits for the predicted class (for classification). This choice is natural for an additive contribution measure due to additivity in the logit-space. To compute SIs, we introduce the GNN-induced graph game Mg with a node masking strategy in Section 3.1. The graph game is defined on all nodes and describes the output given subset of nodes, where the remaining are masked. Computing SIs on the graph game defines a perturbation -based and decomposition- GNN explanation (Yuan al., 2023), which is an extension of node attributions (Agarwal et al., 2023). In Section 3.2, we show that GNNs with linear global pooling and output layer satisfy an invariance property for the node game associated with the node embeddings (Theorem 3.3). This invariance implies sparse MIs for the graph game (Proposition 3.6), which determines the complexity of MIs by the corresponding receptive fields (Theorem 3.7), which substantially reduces the complexity of SIs in our experiments. In Section 3.3, we introduce GraphSHAP-IQ, an efficient algorithm to exactly compute and estimate SIs on GNNs. All proofs are deferred Appendix B.
3.1 A COOPERATIVE GAME FOR SHAPLEY INTERACTIONS ON GRAPH NEURAL NETWORKS
Given a GNN fg, we propose the graph game for which we compute axiomatic and fair SIs. Definition 3.2 (GNN-induced Graph and Node Game). For graph g = (V, E, X) and GNN fg.
we let N = {i: vi E V} be the node indices and define the graph game Vg : P(NN + as
2/ :=) = S0.5(((0)) with ( = (x
x (n) E Ra and x
x; ifiET,
b if
with E N and baseline b E TRuo In graph regression fg.g Sg and for graph classification f is the component of the predicted class ò of fa- We further introduce the (multi-dimensions) node game vs : P(N) - Rd as v;(T) = ((((T)) for E N and each node Us E V.
The graph game outputs the prediction of the GNN for subset of nodes T C by masking all node features of nodes Y; with i E N T using a suitable baseline b, illustrated in Figure 2, left. Computing such SVs is known as BShap (Sundararajan Najmi, 2020) and a prominent approach for feature attributions (Lundberg & Lee, 2017: Covert et al., 2021; Chen et al., 2023). As baseline b, we propose the average of each node feature over the whole graph. By definition, the prediction of the GNN is given by M9 (NV f, (X), and due to the efficiency axiom, the sum of contributions in the SI-Graph yields the model's 's prediction, and thus a decomposition. based GNN explanation (Yuan et al., 2023). The graph and the node game are directly linked by Equation (3)
(T) fg.s f (x) 0g (P(( a v)) = a oy ((( (ENN)) (4)
where 0g outputs the component of for the predicted class ý. The number of convolutional layers f determines the receptive field, i.e. the message-passing range defined by its ε-hop neighborhood
M = DENNNNN do (1,5) S O} with dy (i. := length of shortest path from Uy to in g.
Consequently, the node game 14 is unaffected by maskings outside its P-hop neighborhood.
Theorem 3.3 (Node Game Invariance). For a graph g and an L-Layer GNN for let v, be the GNN- induced node game with i E N. Then, vs satisfies the invariance vs (T(T)) v& (((0) for C N.
5

---

Published as a conference paper at ICLR 2025
Node Masking: Computing SIs the graph game is a perturbation- et al., 2023), where also other masking strategies were proposed (Agarwal et al., 2023); for exam- ple, node masks (Ying al., 2019; Yuan al., 2021), edge masks (Luo et al., 2020; Schlichtkrull al., 2021) or node feature masks (Agarwal et al., 2023). Our method is not limited to specific masking strategy as long as defines an invariant game (Theorem 3.3). We implement our method with the well-established and theoretically under- stood BShap (Sundararajan & Najmi, 2020). Al- ternatively, the -'ddddued subgraph could be used, but GNNs are fit to specific graph topologies, such as molecules, and perform poorly on isolated sub- graphs (Alsentzer et al., 2020). Note that, differ- ent masking strategies may emphasize different as- pects of GNNs, which is important future work. Due to the invariance, we show that MIs and SIs of the graph game are sparse. To obtain our theo- retical results, we require structural assumption. Assumption 3.4 (GNN Architecture). We require the global pooling v and the outpul layer o be linear functions, e.g. V is a mean or sum pooling operation and is a dense layer.
moseptive field node 3
mode embeddings
explanation (Yuan
V
K
global pooding
cutpot
[[issar, m.y,
lineer, ngg. layer
memoedrd mobia muslasi motio
Assumaption 3.4
Illustration of the graph game V/-- Masked nodes (grey) are imputed by base- line b. and embeddings are determined by the receptive field (left). Subsequently, a lin- ear pooling (V)) and output layer (o) yield the GNN-induced graph game output.
Figure 2:
Linearity Assumption: In our experiments, show that popular GNN architectures yield com- petitive performances under Assumption 3.4 on multiple benchmark datasets. In fact, such an as- sumption should not be seen as hindrance, it is the norm in GNN benchmark evaluations (Errica et al., 2020). Furthermore, simple global pooling functions, such as sum or mean, are adopted in many GNN architectures (Xu al., 2019; Wu al., 2022), while more sophisticated pooling layers do not always translate into empirical benefits (Mesquita et al., 2020; Grattarola et al.. 2021). Like- wise, a linear output layer is a common design choice, and the advantage of deeper output layers must be validated for each task (You et al., 2020).
3.2 COMPUTING EXACT SHAPLEY AND MÖBIUS INTERACTIONS FOR THE GRAPH GAME
Given a GNN-induced graph game Vg from Definition 3.2 with Assumption 3.4, i.e. and are linear, then the MIs of each node game are restricted to the é-hop neighborhood. Intuitively, mask- ings outside the receptive field do not affect the node embedding. Consequently, we show that the MIs of the graph game are restricted by all existing E-hop neighborhoods. More formally, due to the invariance of the node games (Theorem 3.3), the MIs for subsets that are not fully contained in the (-hop neighborhood !n! are zero.
Lemma 3.5 (Trivial Node Game Interactions). Let m4 P(N) + Id be the MIs of the GNN- induced node game v. for i N under Assumption 3.4. Then, ms(S) = 0 for all g A4(0)
Lemma 3.5 yields that the node game interactions outside of the ε-hop neighborhood do not have to be computed. Due Assumption 3.4, the interactions of the GNN-induced graph game are equally zero for subsets that are not fully contained in any ε-hop neighborhood.
Proposition 3.6 (Trivial Graph Game Interactions). Let my PPNN + R. be the MIs of the GNN- induced graph game Vg under Assumption 3.4 and let == ULEN P(N(0)) be the set of non-trivial interactions. Then, my(S)= = for all S C N with S & I.
I is the set of non-trivial MIs, whose size depends on the receptive field of the GNN. The size of I also directly determines the required model calls to compute SIs.
Theorem 3.7 (Complexity). For graph and an E-Layer GNN fg. computing MIs and SIs on the GNN-induced graph game Vy requires [I] model calls. The complexity is thus bounded by
I S Σ 20 S n 2n S n
3anux
IEN
6

---

Published as a conference paper at ICLR 2025
where Rmax maxieN W is the size of the largest t-hop neighborhood and dmax is the maxi- mum degree of the graph instance.
(E)
In other words, Theorem 3.7 shows that the complexity of MIs (originally 2") for GNNs depends at most linearly on the size of the graph n. Moreover, the complexity depends exponentially on the connectivity dmax of the graph instance and the number of convolutional layers & of the GNN. Note that this is very rough theoretical bound. In experiments, we empirically demonstrate that in practice for many instances exact SIs can be computed, even for large graphs (n > 100). Besides this upper bound, we empirically show that the graph density, which is the ratio of edges compared to the number of edges in a fully connected graph, is an efficient proxy for the complexity.
3.3 GRAPUSHAP-IQ. AN EFFICIENT ALGORITIIM FOR SHIPLEY INTERACTIONS
Building on Theorem 3.7, we propose GraphSHAP-IQ, an ef- ficient algorithm to compute SIs for GNNs. At the core is the exact computation of SIs, outlined in Algorithm 1, which we then extend for approximation in restricted settings. Moreover, we propose ineeraction-nffrmmee baseline methods that directly exclude valued SIs, which, however, still require all model calls for exact computation. To compute exact SIs, GraphSHAP- IQ identifies the set of non-zero MIs I based on the given graph instance (line 1). The GNN is then evaluated for all maskings contained in (line 2). Given these GNN predictions, the MIs for all interactions in I are computed (line 3). Based on the com- puted MIs. the SIs are computed using the conversion formulas (line 4). Lastly, GraphSHAP-IQ outputs the exact MIs and SIs. In restricted settings, computing act SIs could still remain infeasible. We thus propose an approximation variant GraphSHAP-IQ by introducing hyperparameter X, which limits the highest order of computed MIs in line 1. Hence, GraphSHAP-IQ outputs exact SIs, if À = nmax, thereby requiring the optimal budget. For a detailed description of GraphSHAP-IQ and the interaction informed variants, we refer to Appendix D.
Algorithm 1 GraphSHAP-IQ
Require: Graph (V, E, X), L-Lyyer GNN fg. SI order k.
1: + UIEN P()
2: V/3 + (Tg(X
3: mg [MI S)ssEz
4: 4g < MITOSII I (mg. k)
5: return MIs mg. SIs $
-errattio--nfommee
EXPERIMENTS
In this section, empirically evaluate GraphSHAP-IQ for GNN explainability, and showcase sub- stantial reduction in complexity for exact SIs (Section 4.1), benefits of approximation (Section 4.2), and explore the SI-Graph for WDNs and molecule structures (Section 4.3). Following Amara al. (2022), we trained a Graph Convolutional Network (GCN) (Kipf & Welling, 2017), Graph Isomor- phism Network (GIN) (Xu et al., 2019), and Graph Attention Network (GAT) (Velickovic et al., 2018) on eight real-world chemical datasets for graph classification and a WDN for graph regres- sion, cf. Table All models adhere to Assumption 3.4 and report comparable test accuracies (Errica et al., 2020; You et al., 2020). All experiments are based on shapi q (Muschalik et al., 2024a) and details can be found in Appendix F or at https: / githuu.........///g//........ com/ FFmg 11 L/GraphSHAPPPPP IQ.
Table 1: Summary of datasets and model accuracy.
Dotnset Description
Model Accwracy by Layer (S))
Dataset
Graphs
das
Nodes (ang)
Density (ang)
GCN 2
3
GAT
3
GIN
2
3
Speed-Up
(Sáncher-1 enggeling 3020)
Benzone (ZhbZ)
12000
81.2
10*
10a
(Sáncher- Langding et ol., 2020)
HuaondCCatoony (PLC)
8671
21.4
21.6
82.4
83.9
63.9
82.4
82.2
82.4
86.6
87.2
67.1
10*
10P
(Kazins et 2005)
Munagenicity (M7(7)
6337
2
30.3
18.3
77.8
80.7
50.3
72.6
73L6
74.8
77.8
77.4
77.5
10a
10"
10P
(Sánchez Lengeling 2020)
AlkaneCibbnyyl (ALC)
21.4
21.5
98.7
97.8
97.3
96.9
97.3
10
10"
102
PROTEINS (PR7)
(Borgwardt 2005)
39.1
42.4
75.2
71.1
74.0
75.3
60.5
79.8
79.3
74.8
67.7
(Rorgwantt 2005)
ENZYMES (AN2)
600
32.6
32.0
34.2
37.5
36.8
32.5
35.0
35.8
36.7
35.0
39.2
10F
10'
10a
CON2 (CX2)
(Sutherland at., 2003)
467
2
41.2
10.6
87.2
86.1
87.2
81.9
87.2
85.1
84.0
85.1
85.
10"
10"
10"
(Sutherland 2003)
BZR (8728)
90.1
104

---

Published as a conference paper at ICLR 2025
Milaggntc ty
Muttggeintty (24 Lyeer GMN
Nurder of Bec 283
108m J0M9
Namber of uning
3m
275
Im
225
3004
1004
320
124-
Layer 10.90)
10k
Layer 30.01
17.
32"
2 Layen 12.85
Layer
3t
2 Layers (2.50)
Layers 12:40)
24
15.00
120
Seaeling
123
Braciin
100
12.
10
20
35 Number Nodes
33 Go
25
Aurber Cruph hodes In!
Number Nocia
Figure 3: graphs of BZR (left) and MTG (middle, right) visualized by number of convolutional layers (left, middle) and graph density GNN (right). While madel-agnostic baselines scale exponentially (dashed lines), GrahpSHAP-IQ scales approximately linearly with graph sizes (R² of log-curves in braces).
Complexity of GraphSHAP-IQ in model calls (in log 10) by number of nodes for all
4.1 COMPLEXITY ANALYSIS OF GRAPHSHAP-IQ FOR EXACT SHAPLEY INTERACTIONS
In this experiment, we empirically validate the benefit of exploiting graph and GNN structures to compute exact SIs with GraphSHAP-IQ. The complexity is measured by the number of evaluations of the GNN-induced graph game, i.c. the number of model calls of the GNN, which the limiting factor of SIs, cf. runtime analysis in Appendix G.2. For every graph in the benchmark datasets, described in Table 1, we compute the complexity of GraphSHAP-IQ. where the first upper bound from Theorem 3.7 is used if maxieN [ > 23, i.e. the complexity exceeds 223 Rs 8.3 x 10 Figure displays the log-scale complexity (y-axis) by the number of nodes (x-axis) for BZR (left) and MTG (middle, right) for varying number of convolutional layers & (left, middle) and by graph density for a 2-Layer GNN (right). The model-agnostic baseline is represented by a dashed line. For results on all datasets, see Appendix G.1. Figure 3 shows that the computation of SIs is substantially reduced by GraphSHAP-IQ. Even for large graphs with more than 100 nodes, where the baseline requires over 30000 model calls, many instances can be exactly computed for 1-Layer and 2-Layer GNNs with fewer than 10S evaluations. In fact, the complexity grows linearly with graph size across the dataset, as shown by high R scores of fitted logarithmic curves. Figure 3 (right) shows that the graph density is an efficient proxy of complexity, with higher values for instances near the baseline.
4.2 INTERACTION-INFORE
APPROXIMATION OF SHAPLEY INTERACTIONS
For densely connected graphs and GNNs with many layers, exact computation of SIs might still be infeasible. We, thus, evaluate the approximation of SIs with GraphSHAP-IQ. current state-of-the-ar model-agnostic baselines (implemented in shapiq), and our proposed anteraction-iforreed vari- ants. For the SV (order 1), we apply KernelSHAP (Lundberg & Lee, 2017), Unbiased KernelSHAP (Covert & Lee, 2021), k-additive SHAP (Pelegrina al., 2023), Permutation Sampling (Castro al., 2009), SVARM (Kolpaczki et al., 2024a), and L-Shapley (Chen et al., 2019). We estimate k-SII (order 2 and 3) with KemelSHAAP-IQ (Fumagalli et al., 2024), Inconsistent KermelSHAP-IQ (Fu- magalli et al., 2024), Permulation Sampling (Tsai et al., 2023), SHAP-IQ (Fumagalli et al., 2023), and SVARM-IQ (Kolpaczki et al., 2024b). For each baseline, we use the interaction inforioooddd vari- ant, cf. Appendix D.3. We select graphs containing 20 n 40 nodes for the MTG, PRT, and BZR benchmark datasets. For each graph instance, we compute ground-truth SIs via GraphSHAP- IQ and evaluate all methods using the same number of model calls, which is the main driver of runtime, cf. Appendix G.2. Figure 4 (left) displays the average MSE (lower is better) for varying the model calls. GraphSHAP-IQ outperforms the baselines settings with majority of lower- order MIs. Figure 4 (middle) compares average runtime and MSE for varying explanation orders at GraphSHAP-IQ's ground-truth budget. Notably, GraphSHAP-IQ is among the fastest methods, and remains unaffected by increasing explanation order. Moreover, for all baselines (except permutation sampling), the interaction-iffommn variants substantially improve the approximation quality and runtime. Consequently, noisy estimates of SIs are substantially improved (Figure 4, right).
4.3 REAL-WORLD APPLICATIONS OF SHAPLEY INTERACTIONS AND THE SI-GRAPH
We now apply GraphSHAP-IQ in real-world applications and include further results in Appendix G. Monitoring water quality in WDNs requires insights into dynamic system governed by local
8

---

Published as a conference paper at ICLR 2025
2-511
Revenhweg Recethwoeeg PeAARTTIO Samphey SAA
Mutagenidty with layer
Order 190
Gnetawe leam
Eicaet 8-lll (ours)
100
Bos
13+1
10
00224
1000 2000 3000 0003 2005 5300 7006 5000
Auneage Runt me Seconds (ogi
Internction
Figure Approximation of SIs with GraphSHAP-IQ (green) and model-agnostic baselines for MTG (left). At budgets, where GraphSHAP-IQ reaches exact SIs, the baselines achieve varying es- timation qualities and computational costs (middle) which leads different estimated explanations, especially without interaction-inforeed baselines (right).
SV:
STII: (order
(b) Pyridine Molecule
SV (c) Benzene Molecule
MI
(a) WDN Explanations
Figure 5: Exact SIs values for three example graph structures. SVs illustrate the trajectory of chlori- nation levels a WDN (a). STHI (order 2) values showcase that a Pyridine molecule is not classified as benzene (b), and the largest positive MI for a benzene molecule is the benzene ring (c).
partial differential equations. Here, we investigate the spread of chlorine graph-level regression of a WDN, where GNN predicts the fraction of nodes chlorinated after some time. Based on the Hanoi WDS (Vrachimis et al., 2018), we create temporal WaterQuality (WAQ) dataset containing 1 000 graphs consisting of 30 time steps. We train and explain simple GNN, which processes node and edge features like chlorination level at each node and water flow between nodes. Figures and 11 show that 2-SIIs spread over the WDS aligned with the water flow. Therein, mostly first- order interactions influence the vire-ng chlorination levels.
Benzene rings in molecules are structures consisting of six carbon (C) atoms connected in ring with alternating single and double bonds. We expect a well-trained GNN to identify benzene rings incorporate higher-order MIs (order 6). Figure shows two molecules and their SI-Graphs computed by GraphSHAP-IQ. The Pyridine molecule in Figure 5 (b) is correctly predicted to be non-benzene as the hexagonal configuration features a nitrogen (N) instead of a carbon, which is confirmed by the SVs highlighting the nitrogen. STIIs of order 2 reveal that the MI of nitrogen is zero and interactions with neighboring carbons are non-zero, presumably due to higher-order Mls, since STH distributes all higher-order MIs to the pairwise STHSs In addition, STIIs among the five carbon atoms impede the prediction towards the benzene class. Interestingly, opposite carbons coincide with the highest negative interaction. The MIs for benzene molecule with 21 atoms in Figure (c) reveal that the largest positive MI coincides with the 6-way MI the benzene ring. Mutagenicity of molecules is influenced by compounds like nitrogen dioxide (NO,) (Kazius al., 2005). Figure shows SIs for a MTG molecule, which GNN identifies as mutagenic. 2-SIIs and MIs both show that not the nitrogen atom but the interactions of the NO₂ bonds contributed the most.

---

Published as a conference paper at ICLR 2025
linear readout (top 100 MIs)
deep readout (top 100 MIs)
deep readout (top 100 MIs; recolored)
linear readout [all 2-S11a)
deep readout (all 2-S1Is)
Figure 6: MIs and 2-SII scores for 2-layer GCN trained on MTG with a linear readout and a deep readout. Deep readout produces interactions outside the receptive field which recolored in grey.
5 COMPARISON OF LINEAR AND DEEP READOUTS
Theorem 3.4 imposes the use of linear readout, which a limitation of our method, though it re- mains commonly used in practice (You et al., 2020). In this section, we compare SIs for GNNs with both linear and non-linear readouts. We train a 2-layer GCN architecture with both linear and non- linear (2-layer perceptron) readouts MTG, where both models achieve comparable performance. Figure shows that non-linear readouts produce substantially different MIs that are not restricted to the receptive fields. Lower-order explanations models (NO2 group signalling mutagenicity). We conclude that linear readout restricts the inter- actions of the GNN to the graph structure and its receptive fields. In contrast, non-linear readouts enable interactions that extend beyond the receptive fields of the GNN. Many SV-based XAI meth- ods for GNNs (Yuan et al., 2021: Zhang et al., 2022: Ye al., 2023; Bui et al., 2024) implicitly rely on the assumption that interactions outside the receptive fields are negligible, which should be evaluated carefully for non-linear readouts.
similar, indicating the correct reasoning of both
LIMITATIONS AND FUTURE WORK
We presented GraphSHAP-IQ. efficient method to compute SIs that applies to all popular mes- sage passing techniques in conjunction with a linear global pooling and output layer. Assump- tion 3.4 is common choice for GNNs (Errica al., 2020; Xu et al., 2019; Wu et al., 2022) and does not necessarily yield lower performance (Mesquita et al., 2020; You et al., 2020; Grattarola al., 2021), which is confirmed by our experiments. However, exploring non-linear choices that preserve trivial MIs is important for future research. Masking node features with fixed baseline, known as BShap, preserves the topology of the graph structure and a well-established approach (Sundararajan et al., 2020). Nevertheless, alternatives such as induced subgraphs, edge-removal, or learnable masks, could emphasize other properties of the GNN. Lastly, approximation SIs with GraphSHAP-IQ and interaction-informe novel methods tailored to Proposition 3.6 are promising future work. Our results may further be applied to other models with spatially restricted features, such convolutional neural networks.
baselines substantially improved the estimation, where
7 CONCLUSION
We introduced the GNN-induced graph game, a cooperative game for GNNs on graph prediction tasks that outputs the model's prediction given a set of nodes. The remaining nodes are masked using baseline for node features, corresponding to the well-established BShap (Sundararajan al., 2020). We showed that under linearity assumptions on global pooling and output layers, the complexity of computing exact SVs, SIs, and MIs on any GNN is determined solely by the receptive fields. Based on our theoretical results, we presented GraphSHAP-IQ and interaction- informed variants of existing baselines, to efficiently compute any-order SIs for GNNs. We show that GraphSHAP-IQ and interaction-infore on multiple real-world benchmark datasets and propose to visualize SIs as the SI-Gra SI-Graph. By com- puting the SI-Graph, we discover trajectories of chlorine in WDNs and important molecule sub- structures, such benzene rings NO, groups
baselines substantially reduces the complexity of SIs
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
This paper presents work aiming advance the field of ML and specifically the field of XAL There are many potential societal consequences of our work. Our research holds significant potential for positive societal impact, particularly in areas like the natural sciences (e.g.. chemistry and biology) and network analytics. Our work can positively impact ML adoption and potentially reveal biases unwanted behavior in MI. systems.
However, we recognize that the increased explainability provided by XAI also carries ethical risks. There is the potential for "explainabillty-basee white-washing" where organizations, firms, in- stitutions might misuse XAI to justify questionable actions or outcomes. With responsible use, XAI can amplify the positive impacts of ML, ensuring its benefits are realized while minimizing harm.
REPRODUCIBILITY STATEMENT
The python code for GraphSHAP-IQ is available at https://gi cwm /FFm/1gll // GraphSHAP- IQ, and can be used on any graph game, a class specifically tailored to the shapic package (Muschalik et al., 2024a). We include formal proofs of all claims made in the paper in Appendix B. We further describe the experimental setup and details regarding reproducibility in Appendix F. Our experimental results, setups and plots can be reproduced by running the corre- sponding scripts. The datasets and their sources are described in Table 3.
ACKNOWLEDGMENTS
We gratefully thank the anonymous reviewers for their valuable feedback for improving this work! We thank André Artelt for the EPyT-Flow toolbox support. Fabian Fumagalli and Maximilian Muschalik gratefully acknowledge funding by the Deutsche Forschungggemmiischaaff (DFG, Ger- man Research Foundation): TRR 318/1 2021 438445824. Janine Strotherm gratefully acknowl- edges funding from the European Research Council (ERC) under the ERC Synergy Grant Water- Futures (Grant agreement No. 951424). Luca Hermes and Paolo Frazzetto gratefully acknowledge funding by "SAIL.: SustA Lifecycle of Intelligent Socio-Tecr Technical Systems," funded by the Ministry of Culture and Science of the State of North Rhine- Westp-hastppalia under grant 1009AA Additionally, Paolo Frazzetto gratefully acknowledges funding by Amajor SB S.p.A. Alessandro Sperduti gratefully acknowledges the support of the PNRR project FAIR Future AI Research (PE00000013), Concession Decree No. 1555 of October 11, 2022, CUP C63C22000770006.
REFERENCES
Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features are dependent: More accurate approximations to Shapley values. Artificial Intelligence, 103502, 2021.
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik, Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Selahattin Akkas and Ariful Azad. Gnnshap: Scalable and accurate GNN explanation using shapley values. In Proceedings of the ACM on Web Conference 2024, WWW 2024, Singapore, May 13-17, 2024, pp. 827-838. ACM, 2024.
Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik. Subgraph neural net- works. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 (NeurIPS 2020), 2020.
Kenza Amara, Zhitao Ying, Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan, Ulrik Brandes, Se- bastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. In Learning Graphs Conference, LoG 2022, 9-12 De- cember 2022, Virtual Event, volume 198 of Proceedings of Machine Learning Research, pp. 44. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2025
André Artelt, Marios S. Kyriakou, Stelios G. Vrachimis, Demetrios G. Eliades, Barbara Hammer, and Marios M. Polycarpou. Epyt-flow epanet python toolkit - flow. https: https://github. com/ WaterFutures Bet--PPyTPPooo 2024.
Inaam Ashraf, Luca Hermes, André Artelt, and Barbara Hammer. Spatial Graph Convolution Neural Networks for Water Distribution Systems. In Proceedings of the 21th International Symposium on Intelligent Data Analysis (IIA), Lecture Notes in Computer Science, pp. 29-41. Springer, 2023.
Sebastian Bordt and Ulike von Luxburg. From Shapley Values to Generalized Additive Models and back. In International Conference Artificial Intelligence and Statistics (AISTATS 2023), volume 206 of Proceedings of Machine Learning Research, pp. 709-745. PMLR, 2023.
Stephen P Borgatti, Ajay Mehra, Daniel J Brass, and Giuseppe Labianca. Network analysis in the social sciences, science, 323(5916):892-895, 2009.
Karsten M. Borgwardt, Cheng Soon Ong. Stefan Schönauer, S. N. Vishwanathan, Alexander J. Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. In Proceedings Thirteenth International Conference on Intellieent Systems for Molecular Biology 2005, Detroit, MI, USA, 25-29 June 2005, pp. 47-56, 2005.
Ngoc Bui, Hieu Trung Nguyen, Viet Anh Nguyen, and Rex Ying. Explaining graph neural net- works via structure- aware interaction index. Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
Giuseppe Casalicchio, Christoph Molnar, and Bernd Bischl. Visualizing the Feature Importance for Black Box Models, volume 1 11051 of Lecture Notes in Computer Science, pp. 655-670. Springer International Publishing, Cham, 2019. ISBN 978-3-030- 1080---00-00.
Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 3665): 2009.
Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. Algorithms to estimate Shapley value feature attributions. Nature Machine Intelligence, 566):590-601, 2023.
Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Ian Covert and Su-In Lee. Improving KemelSHAP:: Practical Shapley Value Estimation Using Lin- ear Regression. In The 24th International Conference Artificial Intelligence and Statisties, (AISTATS 2021), volume 130 of Proceedings of Machine Learning Reseurch, pp. 3457-3465.
PMLR, 2021.
Ian Covert, Scott M. Lundherg, and Su-In Lee. Understanding Global Feature Contributions With Additive Importance Measures. In Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020 (NeurIPS 2020), 2020.
Ian Covert, Scott M. Lundberg, and Su-In Lee. Explaining by removing: unified framework for model explanation. J. Mach. Learn. Res., -00099,, 2021.
Alexandre Duval and Fragkiskos D. Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Machine Learning and Knowledge Discovery in Databases. Research Track- European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part II volume 12976 of Lecture Notes in Computer Science, pp. 302-318. Springer, 2021.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Represen- lutions, ICLR 2020, Addis Abuba, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py PoTch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
12

---

Published as a conference paper at ICLR 2025
Paolo Frazzetto, Muhammad Uzair-Ul- UU-aag and Alessandro Sperduti. Enhancing human resources through data science: a case in recruiting. In Proceedings of the 2nd Italian Conference on Big Data and Data Science (ITADATA 2023), Naples, Italy, September 11-13, 2023, volume 3606 of CEUR Workshop Proceedings. SEURRWS.oOR 2023.
Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and Ilya Feige. Shapley explainability on the data manifold. In International Conference on Learning Representationx, 2021.
Katsushige Fujimoto, Ivan Kojadinovic, and Jean-Luc Marichal. Axiomatic characterizations of probabilistic and cardinal-probabilisti interaction indices. Games and Economic Behavior, 55 (1):72-99, 2006.
Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Eva Hammer. SHAP-IQ: Unified approximation of any-order shapley interactions. In Thirly-seventh Conference on Nearul Information Processing Systems (NeurIPS 2023), 2023.
Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Ham- mer. Kernelshap-iq: Weighted least-square optimization for shapley interactions, 2024.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learn- ing. In Proceedings of the 36th International Conference on Machine Learning, (ICML 2019), volume 97 Proceedings of Machine Learning Research, pp. 2242-2251, PMLR, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017.
Michel Grabisch. Set Functions, Games and Capacities in Decision Making, volume 46. Springer International Publishing Switzerland, 2016. ISBN 978-3-319-30690-2.
Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 28(4)5547-565, 1999.
Daniele Grattarola, Daniele 7ambon, Filippo Maria Bianchi, and Cesare Alippi. Understanding pooling graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 35:2708-21 271888 2021.
John C Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194-2200 1963.
Munir Hiabu, Joseph T. Meyer, and Marvin N. Wright. Unifying local and global model explana- tions by functional decomposition of low dimensional structures. In International Conference on Artificial Intelligence and Statistics (AISTATS 2023), volume 206 of Proceedings of Machine Learning Research, pp. 7040-7060. PMLR, 2023.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local inter- pretable model explanations for graph neural networks. IEEE Trans. Knowl. Data Eng., 35(7): 1968-6972,,8 2023.
Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantification in ex- plainable AI: A causal problem. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), volume 108 of Proceedings Machine Learning Research, pp- 2907-2916. PMLR, 2020.
Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. Fast- SHAP: Real-Time Shapley Value Estimation. In The Tenth International Conference on Learning Representations (ICLR 2022). OpenReview.net, 2022.
Justin Singh Kang. Yigit Efe Erginbas, Landon Butler, Ramtin Pedarsani, and Kannan Ram- chandran. Learning to understand: Identifying interactions via the mobius transform. CoRR, abs/2402.02631, 2024.
13

---

Published as a conference paper at ICLR 2025
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of Medicinal Chemistry, 48(1):312 320, 2005. ISSN 0022- 2623.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net- works. In International Conference on Learning Representations (ICLR), 2017.
Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hüllermeier. Approximating the Shapley Value without Marginal Contributions. In Thirty-Eightt AAAI Conference Artificial Intelligence, (AAAI 2024), pp. 12246-13553 AAAI Press, 2024a.
Patrick Kolpaczki, Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, and Eyke Hillermeier. SVARM-IQ: Efficient approximation of any-order Shapley interactions through stratification. In Proceedings The 27th International Conference on Artificial Intelligence and Statistics, (AISTAT'S 2024), volume 238 of Proceedings of Machine Learning Research, pp. 3520- 3528. PMLR, 2024b.
Indra Kumar, Carlos Scheidegger, Suresh Venkatasubramanian, and Sorelle A. Friedler. Shapley Residuals: Quantifying the limits of the Shapley value for explanations. In Advances in Neu- ral Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021 NeurIPS 2021, pp. 26598-26608, 2021.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 4765-4774, 2017.
Scott M. Lundberg, Gabriel G. Erion, Hugh Chen, Alex J. DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable Al for trees. Nature Machine Intelligence, 2(1):56-67, 2020.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Advances in Neural Information Processing Systems, volume 33, pp. 19620-19631. Curran Associates, Inc., 2020.
Jean-Luc Marichal and Marc Roubens. The chaining interaction index among players in cooperative games. Advances in Decision Analysis, pp. 69-85, 1999.
Kevin McCloskey, Ankur Taly, Federico Monti, Michael P Brenner, and Lucy J Colwell. Using attribution to decode binding mechanism in neural network models for chemistry. Proceedings of the National Academy of Sciences, 116(24):1 122-11629, 2019.
Diego P. Mesquita, Amauri H. Souza Jr., and Samuel Kaski. Rethinking pooling in graph neu- ral networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020. December 6-12, 2020, virtual, 2020.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Maximilian Muschalik, Hubert Baniecki, Fabian Fumagalli, Patrick Kolpaczki, Barbara Hammer, and Eyke Hüllermeier. shapiq: Shapley interactions for machine learning. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024a.
Maximilian Muschalik. Fabian Fumagalli, Barbara Hammer, and Eyke Hüllermeier. Beyond tree- shap: Efficient computation of any-order shapley interactions for tree ensembles. In Thirty- Eighth AAAI Conference on Artificial Intelligence, (AAAI 2024), pp. 14388-14396. AAAI Press, 2024b.
Roger B. Myerson. Graphs and cooperation in games. Math. Oper. Res., 2(3):225-229, 1977.
Mark Newman. Networks. Oxford University Press, 2018. ISBN 97801 98805090.
14

---

Published as a conference paper at ICLR 2025
Guilherme Dean Pelegrina, Leonardo Tomazeli Duarte, and Michel Grabisch. A k-additive choquet integral-based based approach to approximate the SHAP values for local interpretability in machine learning. Artificial Intelligence, 325:104014, 2023.
Alan Perotti, Paolo Bajardi, Francesco Bonchi, and André Panisson. GRAPHSHAP: motif-based explanations for black-box graph classifiers. CoRR, abs/2202.088115 2022.
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann.
Explainability methods for graph convolutional neural networks. In IEEE Conference Com- puter Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp- 10772-10781. Computer Vision Foundation IEEE, 2019.
Gian-Carlo Rota. On the foundations combinatorial theory: I. theory of möbius functions. In Classic Papers in Combinatorics, pp. 332-360. Springer, 1964.
Alvaro Gonzalzz, Jonathan Godwin, Tobias Pfaff, Rex Ying. Jure Leskovec, and Peter W. Battaglia. Learning to simulate complex physics with graph networks. In Proceedings of the 37th International Conference on Machine Learning, ICML. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 8459 8468. PMLR, 2020.
Benjamín Sánchez-Lengeling, Jennifer N. Wei, Brian K. Lee, Emily Reif, Peter Wang, Wesley Wei Qian, Kevin McCloskey, Lucy J. Colwell, and Alexander B. Wiltschko. Evaluating attribution for graph neural networks. Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61-80, 2009.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for NLP with differentiable edge masking. International Conference on Learning Representations, 2021.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus- Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Trans. Pattern Anal. Mach. Intell., 44(11):7581-756 2022.
L. S. Shapley. A Value for n-Person Games. In Contributions the Theory of Games (AM-28), Volume II, pp. 307-318. Princeton University Press, 1953.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling LIME and SHAP: adversarial attacks on post hoc explanation methods. AAAI/ACM Conference on AI, Ethics, and Society (AIES 2020), pp. 180-186. ACM, 2020.
Erik Strumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and Information Systems, 41(3):647-663 2014.
Erik Strumbelj. Igor Kononenko, and Marko Robnik-Sikonja. Explaining instance classifications with interactions of subsets of feature values. Data Knowl. Eng., 68(10):886 804, 2009.
Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In Pro- ceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 9278. PMLR, 2020.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic Attribution for Deep Networks. In Proceedings of the 34th International Conference Machine Learning (ICML 2017), volume 70 of Proceedings of Machine Learning Research, pp. 3319-3328. PMLR, 2017.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The Shapley Taylor Interaction Index. In Proceedings of the 37th International Conference on Machine Learning, (ICML 2020), volume 1 19 of Proceedings of Machine Learning Research, pp. 9259-9268. PMLR, 2020.
15

---

Published as a conference paper at ICLR 2025
Jeffrey J. Sutherland, Lee A. O'Brien, and Donald F. Weaver. Deliin--itttngg with genetic algorithm: A method for developing classification aruuctue-acttvvity relationships. J. Chem. Inf. Comput. Sci., 2003. 2003.
1366):19061191,
Che-Ping Tsai, Chin-Kuan Yeh, and Pradeep Ravikumar. Faith-Shap: The Faithful Shapley Interac- tion Index. Journal of Machine Learning Research, 24(94): 2023.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations
(ICLR), 2018.
Stelios G Vrachimis, Marios S. Kyriakou, Demetrios G. Eliades, and Marios M. Polycarpou. LeakDB: A Benchmark Dataset for Leakage Diagnosis in Water Distribution Networks. In Pro- ceedings of the 1st International Joint Conference on Water Distribution Systems Analysis & Computing and Control for the Water Industry (WDSA/CCWI), 2018.
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Marvin N. Wright, Andreas Ziegler, and Inke R. König. Do little interactions get lost in dark random forests? BMC Bioinform.. 17:145, 2016.
Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao. Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Singapore, Singapore, 2022.
Ping Xiong, Thomas Schnake, Michael Gastegger, Grégoire Montavon, Klaus-Robert Müller, and Shinichi Nakajima. Relevant walk search for explaining graph neural networks. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 38301-380 13301-38324. PMLR, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations (ICLR), 2019.
Ziyuan Ye, Rihan Huang, Qilin Wu, and Quanying Liu. SAME: uncovering GNN black box with sruuturr-awar shapley-based multipiece explanations. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Process- ing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 9240-9251, 2019.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In Ad- vances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Peng Yu, Albert Bifet, Jesse Read, and Chao Xu. Linear tree shap. In Advances in Neural Informa- tion Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, (NeurIPS 2022), 2022.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12241-12255 PMLR, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Trans. Pattern Anal. Mach. Intell., 45(5):5782-5799, 2023.
Artjom Zern Klaus Broelemann, and Gjergji Kasneci. Interventional SHAP values and interaction values for piecewise linear regression trees. In Thirty-Sevent AAAI Conference on Artificial Intelligence, (AAAI 2023), pp. 11173- AAAI Press, 2023.
16

---

Published as a conference paper at ICLR 2025
He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. Trustworthy graph neural networks: Aspects, methods, and trends. Proceedings of the IEEE, 2024.
Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. Gstarx: Explaining graph neural networks with structure-aware cooperative games. In Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022.
17

---

Published as a conference paper at ICLR 2025
ORGANISATION OF THE SUPPLEMENT MATERIAL
A Notation
19
Proofs
20
B.1 Proof of Theorem 3.3
20
B.2 Proof of Lemma 3,5
20
B.3 Proof of Proposition 3.6...
21
B.4 Proof of Theorem 3.7
Detailed Comparison of GraphSHAP-IQ and Related Work
23
C.I Detailed Differences between GraphSHAP-IQ and Related Methods
23
C.2 Linking GraphSHAP-IQ and L-Shapley
24
D Additional Algorithmic Details for GraphSHAP-IQ
26
D.I Exact Computation
26
D.2 Approximation with GraphSHAP-IQ
26
D.3
Interaction-Informec Baseline Methods
27
E
Further Background on Shapley Interactions
29
E.1
Related Work on Shapley Interactions
E.2
Efficient Shapley Interaction Indices
29
E.3
Conversion Formulas for Möbius Interactions Shapley Interactions
30
F
Experimental Setup and Reproducibility
31
F.1
Datasets
F.1.1
Chemical Datasets
31
F.1.2
Water Distribution Network
F.2
GNN Architectures
32
F3
Training
32
Additional Experimental Results
33
G.I
Complexity Analysis
33
G.2 Runtime Analysis
35
G.3 Explaining Water Quality Water Distribution Networks (WDNs)
................................
36
G.4
Approximation Quality of GraphSHAP-IQ
36
G.4.1 Setup Description ................................
36
G.4.2 Description of SV Baselines
36
G.4.3 Description of 2-SII Baselines
37
G.5 Explanation Graphs for Molecule Structures
37
18

---

Published as a conference paper at ICLR 2025
A NOTATION
We use lower-case letters to represent the cardinalities of the subsets, e.g. 8 == ==|- A summary of notations is given in Table 2.
Table 2: Notation Table
Notation
Description
Notations
(V
Graph instance to explain, with nodes V. odges E, and node features X
V
Set nodes g edges y
F
do
Number of node features
Xi Rd
vector of tt
X e Ro06
Node feature matrix for all nodes
Baseline features used for masking
- CV)
Set of graph node indices
Number of nodes
graph instance
SEN
Index of node vi in
Node indiees of the neightborhood of node
GNN Notations
((X)
GNN prediction for gruph g and node features X prediction class graph and
(s(X)
Number of graph convolutional layers Intermeiiate graph convolutional layers Number features node embedding layer
I.....t
de
1!4) 8dh
Nede embedding
node va layer
H
[b
embedding
graph instance layer
(Linear) permutation invariant global pooling function (Linear) rendout layer of the GNN
1 N
Node indiees of the E-hop neighborhood of node Size of the largest é- hop neighhorhood of the graph instance Maximum node degree
m 1NT01
graph instance
Masking Notations
TEN
Set node indices, typically used for masked predictions, where N 7 masked
[x, C
lb #
Masked vode festures
o, where
N T masked baseline
XPI [ x! with T N
Masked node feature matti of where nodes in N \ T are masked with b
Masked prediction of GNN using masked node features X(T)
((X with
Masked node emhedding for node evaluated masked mode features X
Game Theory Notations
P(V)
Power of N. Lcc all possible sets of node indices used to define the game Power
PL(M)
up
which
explanation computed
(,))) = (T
Graph game evalusted at T C. N. i.c. GNN prediction of class with masked node features (?7)
M = f((P0) for N
Gruph node game evaluated T C N. L.e. GNN embedding f. of mode with musked node fentures X
SEN
Set of bode indices, used refer to interaction, the sets for which attributions are computed
my(S)
set.S S MI for a set E N of the graph node game
graph game Py
(S)
7 UseN ()
Set of non-trivial MIs, i.c (8) 0, if &
(SS)
Final explanation of onder evaluated set most
19

---

Published as a conference paper at ICLR 2025
B PROOFS
B.1 PROOF OF THEOREM 3.3
Proof. By definition of vi, we need to show that f(((")) = fx(((TnA( holds. We prove by
induction over f. Denote f! the corresponding node embedding function for the E-layer GNN For a GNN with 1, immediately clear from Equation (2) that
1 (x(T) - (x, ( (x) ( uj E ( - 110h
}D))
Next, assume x1-1)) = )!را (x(rru!!))) holds for any GNN, and T & N. Then for GNN with layers, have
(x = (
(x(T)) (x()) 1s E (1)
1 (x (Tr
(x (xTrNN )) by E Nx! H))
( (x Alllp! ((( by N, (1))
= (x((x()))))
where we have used that ((((1) c An and v S AA for j NuO together with the
invariance (induction hypothesis) of f (((-1) and 8l f((-1)
B.2 PROOF OF LEMMA 3.5
Proof. Let E N and S & N, Our goal is to show that m²(S) = 0. For every subset T C N, can define disjoint sets
T TTww and T. == (N (,))), such that T TT' LTT
with 7 CN and T, C N(())) For S = S, LIST the assumption S E A, implies that S is not empty, i.e. 8 = 1TT O. Furthermore, due to the node game invariance, cf. Theorem 3.3, we have 24 (T) = (T,+) for every T S N. In the following, lower-case letters represent the corresponding cardinalities of the subsets, e.g. et = |T For the MI of interest S, the sum, by definition of MIs, ranges over P(S). Thus, since ST E P(S), we have for every T C S and every T;- S S. that the union T UT; E P(S). On the other hand, every T E P(S) can be uniquely decomposed into T = T UT. Hence, instead of summing over all 1' E P(S), we may also sum over all subsets T = T U TV with T S S and T, S S. The MI for S is then
(s(S) Σ (-1) (T)
TCS
Σ
Σ
(-1)--0t+1) is (T₃ UTF)
resst TTSTT
Σ Σ (-1)a-01++) (T:t)
PrEstTEES
Σ (-1)--9 us (T+)
Σ (-1)%
Ticst
TT
Σ (-1)=-1 14 (IT))
Σ
(-1)%
t
=0=
Σ (-1)+- vn (I (1 1)aT = 0,
T+sst
where we used the node game invariance in the third equation, the binomial theorem (a + 6)m Enzo (1)a=-k(* in the second last equation, and s in the last equation.
20

---

Published as a conference paper at ICLR 2025
B.3 PROOF OF PROPOSITION 3.6
Proof. The proof will be based on two important properties of the Mls.
Lemma B.1. The MI of a constant game C TR is
c. ifS D.
m²(S)
0, otherwise.
Proof.
The MI for constant game is computed for = @ as m00) = v/(0 = c and for == | >
c. (1)) Σ (
m(S) = (-1)"=v((T) =c -e
--
ICS
TCS
1=0
where we have used the binomial theorem (a = (*) n-
The second property is the linearity of the MI in terms of linear combination of games.
Lemma B.2 (Linearity (Fujimoto et al., 2006)). For a linear combination of two games v = c in D2 for constant R, the MI of is given
my = c my, (S) - Mu2 (S).
for all S N.
Proof. This result follows from Theorem 4.9 and Lemma 4.1 in Fujimoto et al. (2006). However, it may also be verified directly
(S) = ((-)==
(c-1)" +z) c. ma, (T) + my2 (T).
TES
TCS
Next, let S E USEN (()(()). Our goal is to show that (S( = 0. By Lemma 3.5, we have that
mi (S) = 0 E Rd for all i E N and node games V4 P(N) + Rd., We can thus define a new game Vy P(N) + 1e as vy (T') = 1/ (((,)(T) i N))) for T C N. Due Assumption 3.4, w is linear (a linear combination of inputs), and by Lemma B. constant shifts do not affect the Mls. We therefore assume that (f(0).... {0}}) = for any number of zero vectors 0. By the linearity of the MI (Lemma B.2), we have then
my (S) (((
N))) 0.
Lastly, Vn represents the logits of the predicted class in the GNN, i.c. (T) o (T)). The output layer a transforms the games defined as the components the (multi-dimensiona)) output of by an vector of size douts where dg returns the component used in the graph game V/g. Again, by Lemma I. constant shifts do not affect the MIs, and we let (0) = O, to obtain
my by (S)) (0) 0,
and likewise for graph regression, which concludes the proof.
B.4 PROOF OF THEOREM 3.7
By Proposition 3.6, the set of non-trivial MIs is given by To compute exact MIs it is therefore necessary to compute all MIs contained in I. Clearly, to compute the MI my(S) for any S C N, it is by definition the MI necessary to evaluate v,(S), Hence, the complexity of computing exact MIs cannot be lower than [Z]. Given now all graph game evaluations v, (T") with T E I, we proceed to show that no additional evaluation is required. In fact, to compute the MI my (S) for E I, we require all game evaluations v(T) with T C S. By definition of I (Proposition 3.6), there exists a node index E N, such that S E P(N(()). Since S C x it follows immediately that all T C S satisfy T E :P(V!(), and hence T I, which have already computed. This finishes
21

---

Published as a conference paper at ICLR 2025
the proof that exact computation requires [Z] graph game evaluations and hence GNN model calls. Additionally, the number of elements in trivially bounded by the number of subsets N, i.. 2n and further
I
UP IEN
Σ P(
Σ 2
S 12. 2
where each ε-hop neighborhood was bounded by Amax = number of nodes in the f-hop neighborhood by bounding the number of nodes in each hop with the maximum degree dmax as
maxieN ((()))
Lastly, we bound the
(E) max
S 1 +
dmax + d
max
dmax 1
max
where we have used the formula for geometric progression. With this bound obtain the final bound
T S max n dmmx I
which concludes the proof.
22

---

Published as a conference paper at ICLR 2025
C DETAILED COMPARISON OF GRAPHSHAP-IQ AND RELATED WORK
The following contains a detailed summary of the related and relevant work. We further discuss distinctions of GraphSHAP-IQ with specific methods from related work in Appendix C.I. Moreover, we establish a connection between GraphSHAP-IQ and L-Shapley in Appendix C.2
The SV (Shapley, 1953) was applied in XAI for local (Lundberg & Lee, 2017: Covert et al., 2021) and global (Casalicchio et al., 2019; Covert et al.. 2020) model interpretability. or data valuation (Ghorbani & Zou, 2019). The Myerson value (Myerson, 1977) variant of the SV for games restricted to graph components. Extensions of the SV to interactions for ML were proposed by Lundherg et al. (2020); Sundararajan al. (2020); Tsai et al. (2023); Bordt & von Luxburg (2023) Due to the exponential complexity, model-specific methods for tree-based models for SVs (Lund- berg et al., 2020; Yu et al., 2022), any-order SIs (Zern et al., 2023; Muschalik et al., 2024b) and MIs (Hiabu al., 2023) were proposed. Model-agnostie approximation methods cover the SV (Lund- berg & Lee, 2017: Chen et al., 2019; Kolpaczki et al., 2024a). SIs (Fumagalli et al., 2023; Kolpaczki et al., 2024b; Fumagalli et al., 2024), and MIs (Kang et al., 2024).
Instance-wise explanations on GNNs were proposed via perturbations (Ying et al., 2019; Luo et al., 2020; Yuan et al., 2021; Schlichtkrull et al., 2021), gradients (Pope al., 2019; Sánchez-Lengeling et al., 2020; Schnake et al., 2022; Xiong et al., 2023) or surrogate models (Vu & Thai, 2020; Huang al., 2023). GNN explanations are given in terms of nodes (Pope al., 2019; Huang et al., 2023) and subgraphs ( (Ying et al., 2019: Luo et al., 2020; Yuan et al., 2021). Other use paths (Schnake et al., attributions, maskings for nodes (Ying et al., 2019; Yuan et al., 2021) or edges (Luo et al., 2020; Schlichtkrull et al., 2021) were introduced. The SV was applied in perturbation- -aaed methods to assess the qual- ity of subgraphs (Yuan et al., 2021; Zhang et al., 2022: Ye et al., 2023), approximate SVs (Duval & Malliaros, 2021; Akkas & Azad, 2024) or for pre-defined motifs (Perotti et al., 2022). Recently, pairwise SIs were approximated to discover subgraph explanations (Bui et al., 2024).
2022: Huang et al., 2023) and edges (Schlichtkrull et al., 2021). For perturbation-basl
In contrast to existing work, we compute exact SVs on node level. Moreover, we exploit graph and GNN structure to compute SIs that uncover complex interactions, formally prove that for linear readouts interaction structures of node embeddings are preserved for graph predictions.
C.I DETAILED DIFFERENCES BETWEEN GRAPHSHAP-IQ AND RELATED METHODS
In this section, we compare GraphSHAP-IQ with TreeSHAP (Lundberg et al., 2020), THA-II (Muschalik et al., 2024b), GraphSVX (Duval & Malliaros, 2021), SubgraphX (Yuan et al., 2021), GStarX (Zhang et al., 2022) SAME (Ye et al., 2023), and recent work by Bui et al. (2024).
TreeSHAP (Lundherg al., 2020) TreeSHAP is a model-specific computation method to plain predictions of decision trees and ensembles of decision trees. TreeSHAP defines a cooperative game based on perturbations via the conditional distribution learned by the tree (path-dependent TreeSHAP) or via interventions using a background dataset (interventional TreeSHAP). Given these game definitions, TreeSHAP efficiently computes exact SVs polynomial time by exploiting the tree structure. Recently, extensions of TreeSHAP for interventional perturbations (Zern et al., 2023), and with TreeSHAP-IQ for path-dependent perturbations (Muschalik et al., 2024b) were proposed to efficiently compute exact any-ordet SIs in polynomial time. Similar GraphSHAP-IQ. Tree- SHAP and Tre-SHAP-IQ are model-specific variants for efficient and exact computation of SVs and SIs. However, TreeSHAP and TreeSHAP-IQ are only applicable to tree-based models, whereas GraphSHAP-IQ is only applicable to GNNs and other model classes with spatially-restrich fea- tures. While both methods model-specific variants to efficiently compute SIs, these methods are applied on fundamentally different model classes and exhibit completely different computation schemes.
Myerson- -yerson-TTaylor Interactions (Bui et al., 2024) This work highlights the opportunities and sig- nificance of SIs for GNN interpretability. Bui et al. (2024) propose an optimal partition of the graph instance as an explanation. This partition is found by approximating second-order STHI via Monte Carlo on connected components of the graph, without being structure-awant aware of GNNs. Note that in our benchmark datasets, there are no isolated components in the graphs, and therefore this does not yield any reduction in complexity. In contrast, GraphSHAP-IQ is able to compute exact STII (and Myerson-STT STII) for any order.
23

---

Published as a conference paper at ICLR 2025
GraphSVX (Duval & Malliaros, 2021). GraphSVX proposes to compute Shapley values with- out interactions on GNNs. This method does not use any GNN-specific structural assumption for graph classification, since GraphSVX considers SVs (not interactions). For graph classification, GraphSVX is an application of KernelSHAP to GNNs. However, for node classification, a result for SVs based on the dummy axiom was established, which also follows from Lemma 3.5. Note that this result for SVs is not applicable for graph prediction, since the dummy axiom does not hold on the graph level, cf. Section 5.5., global/graph classification (Duval & Malliaros, 2021). For our main result (Theorem 3.6), considering the purified interactions (MIs) instead of SVs is crucial.
SubgraphX (Yuan et al., 2021). SubgraphX identifies isolated subgraphs as explanation. This is done by proposing the SV as a heuristical scoring function for subgraph exploration. Given subgraph candidate, reduced game is defined, where the whole subgraph represents a single player. Based on the computed SV, the quality of the subgraph is determined. In contrast, GraphSHAP-IQ does not require to group nodes and does not identify isolated components using a scoring function. Instead, GraphSHAP-IC computes exact SVs node level, and SIs on all possible subgraphs up to order k, which yields an additive decomposition using all these components, which is faithful to the graph game.
GStarX (Zhang et al., 2022). GStarX identifies isolated subgraphs as an explanation. It is re- lated to SubgraphX (Yuan al., 2021) and proposes an alternative scoring function to the SVs. In contrast, GraphSHAP-IQ does not identify isolated components using scoring function. In- stead, GraphSHAP-IQ decomposes the GNN into all possible components (subgraphs) up to order k. Hence, GraphSHAP-IQ explains the GNN prediction across all maskings faithfully according to the SIs.
SAME (Ye et al., 2023). SAME proposes hierarchical MCTS algorithm heuristic way find explanations as subgraphs. SAME considers k-hop neighborhoods for computation of the SV, which however is not accurate for graph prediction, similar to GraphSVX (Duval & Malliaros, 2021).
C.2 LINKING GRAPHSHHAPII AND L-SHIAPLEY
In this section, we present link of GraphSHAP-IQ to L-Shapley (Chen et al., 2019) and prove a novel result, which states that L-Shapley with sufficiently large parameter computes exact SVs on games that admit the invariance property (Theorem 3.3), e.g. the GNN-induced node game. L- Shapley a model-agnostic method to approximate SVs that utilizes the underlying graph structure of features. L-Shapley proposes to compute the marginal contributions A,(T)) i) of subsets T that contain i E N in its X-hop neighborhood
(W t-1 (T))))).
-V (i) = W
Σ NET
(5)
The weights thereby match the weights of the SV restricted to its k-hop neighborhood. While L- Shapley is restricted to the SV, it strongly differs conceptionally from GraphSHAP-IQ in multiple ways. First, GraphSHAP-IQ allows to compute interactions up to order À in the f-hop neighbor- hood, whereas L-Shapley (implicitly) computes interactions up to order in the X-hop neighbor- hood. Second, L-Shapley considers only single neighborhood of the player E N, whereas GraphSHAP-IQ includes all interactions that contain player i in any é-hop neighborhoods. Con- sequently, GraphSHAP-IQ covers all interactions up to order of the GNN-induced graph game, whereas L-Shapley only covers interactions up to order À that are fully contained in the X-hop neigh- borhood of the node game of player i. Third, L-Shapley is model-agnostic method, which is based on a heuristical view of the game structure, whereas GraphSHAP-IQ exploits the GNN structure and additivity of all node games summarized in the graph game. Consequently, GraphSHAP-IQ com- putes exact SV with À = l, whereas L-Shapley computes exact SVs with À = n, i.c. only with all 2n model calls. Lastly, GraphSHAP-IQ maintains efficiency and computes the MIs, which allow to construct onyer SIs yielding an accuracy interpretability trade-off based on practitioner's 's needs.
Theorem C.1. For graph g and a single GNN- induced node game vi varor's i N associated with the node embedding (!) GraphSHAP-IQ applied on the node game with X (V!(0) and explanation
24

---

Published as a conference paper at ICLR 2025
order k 1 returns the L-Shapley computation with X = L. That is, in this specific case the L-Shapley computation is equal to the GraphSHAP-IQ computation and yields the exact SVs.
Proof. Let 24 be single node game of node u, V. X 1N,01 then by Corollary D.1 GraphSHAP-IQ computes exact MIs contained in NV which by Lemma 3.5 are all non-trivial interactions of the node game up order À = l. Consequently, GraphSHAP-IQ computes exact SVs of the node game. On the other hand, we will show that the L-Shapley computation in Equation (5) also yields these exact SVs in this case. We first observe that due the node game invariance in Theorem 3.3, we have for
T : TTN SN and TT == (N (N) E
with 7' = 1 UT; that
A. (i).
Before we compute the SV we need to state the following identity.
Lemma C.2 (Lemma 1 in Chen et al. (2019)). For any integer and pair of non-negative integers 2 t, we have
13
1 +
n- i+t
5
(s+ 1))
Proof.
The proof is given in the proof in Lemma 1 in Appendix by Chen et al. (2019).
Hence, we can compute the SV as
S.sy Σ
1
(T)
("-1)
TEN
Σ
1
(T
TeN n (n-1)
(t-1)
Σ (n-1)
(T (i)
TEN n
(--1
Σ
A (i)
Σ
( n-1
T T*C
n.
(
(N!10)
Σ
A /O
Σ
t
(
T. CV se
T-=0
---
+ n (A9
Σ
A \i)
(LV,(0)
1 1)(
1
-1-
Σ
A \o)
W
(W 4-1
TtCM
where we have used Lemma C.2 in the second last equation. This result of the SVs clearly coincides with Equation (5), which concludes the proof.
Theorem C.I shows that L-Shapley computes exact SVs, if the game corresponds to node game in GNN. However, L-Shapley does not compute exact SVs for the graph game, as interactions involved in the computation of the SV may also appear in other neighborhoods. In fact, L-Shapley applied the graph game only converges for &o = which corresponds to 2" model evaluations. In our experiments, we also show empirically that L-Shapley performs poorly on GNN-induced graph games.
25

---

Published as a conference paper at ICLR 2025
D ADDITIONAL ALGORITHMIC DETAILS FOR GRAPHSHAP-IQ
In this section, we provide further details of the GraphSHAP-IQ algorithm, including the full algo- rithm that is capapable of approximation.
D.1 EXACT COMPUTATION
Algorithm outlines the exact computation for GraphSHAP-IQ and we provide further details and pseudocode in this section. Algorithm describes the computation of the MIs from line 3 in Algo- rithm 1. Given the MIs, GraphSHAP-IQ outputs the converted SIs, according to the conversion for- mulas discussed called in line 4 in Algorithm 1. Here, the method GE GETCONVERS oxWe GUT outputs the distribu- tion weight for each specific index given an MI S, SI S and the index, according to the conversion formulas discussed in Appendix E.3.
Appendix E.3. Algorithm describes the pseudocode of the conversion method
Algorithm 2 Möbius Interaction (MI)
Require: Game values V/ and MI of interest C N.
1: my [S] < 0
2: for T' E P(S) do
3: my]SS] 4- mg[S] (-1)151-12)) 1g [T[
4: end for
5: return MI mg-
Algorithm 3 MItoSI
Require: (Approximated) MIs rig. SI order h: and index
1: for $ E INDEX(M,)) do
2: for S E P(Š) with [S| < do
3:
[S] < 0, not initialized yet. index)
4: ws < wwW.CCNERRIIIIEE.......
5:
$x[S] + 2 [S] + ws my(S) [$]
6: end for
7:
end for
8: return SIs 4k.
D.2 APPROXIMATION WITH GRAPHSHAP-IQ
For graphs with high connectivity and GNNs with many convolutional layers, computing exact SIs via Theorem 3.7 may still be infeasible. We thus propose GraphSHAP-IQ. flexible approach to compute either exact SIs or approximation. Outlined in Algorithm 4. GraphSHAP-IQ depends on a single parameter À= I,..., n that controls the size computed MIs. Given GraphSHAP-IQ deploys a deterministic approximation method that computes exhaustively all non-trivial MIs of the GNN-induced graph game Vn up to order L-Shapley (Chen et al., 2019).
Appendix C.2, we discuss a link between SVs and
Exact SIs: If X Z (2) i.e. À is larger or equal to the largest neighhorhood size, then the set of remaining neighborhoods RR (line 2) is empty. GraphSHAP-IQ then computes all non-trivial MIs and returns exact SIs. In fact, according to Proposition 3.6, Ix (line 1) contains all non-trivial MIs and GraphSHAP-IQ evaluates the graph game V all of these subsets (line 3). The MIs (S) are then computed for all S E IA = (line 4), and converted to SIs (line 13), cf. Appendix E.3.
Approximation: If A < n then IA (line 1) does not contain all non-trivial MIs and the set of remaining neighborhoods R^ (line 2) is not empty. Consequently, the recovery property of the MIs, ef. Equation (I), does not hold for T E Rx. and in particular not for the model predic- tion Ny (N) = fX).. Thus, for neighborhoods recovery value using the MIs (line 7) and assigns the gap to mT (line 8). Note that previous sorting (line 5) is required to ensure that previously assigned neighborhood MIs are included. UI- timately, the largest neighborhood S R. (line 10) receives the gap (line 11) of the prediction
E RR GraphSHAP-IQ computes the curret
26

---

Published as a conference paper at ICLR 2025
(²)(N)= f(X) and the sum of all MIs to maintain efficiency (line 12). The rationale of maintaining the recovery property is that while GraphSHAP-IQ introduces a bias on the approximated MIs, equally distributes missing interaction mass onto lower-order SIs. GraphSHAP-IQ further satisfies the following corollary.
Corollary D.I. GraphSHHAP-IQ computes exact SIs, if X
(E) Amax
1.
Proof. By Proposition 3.6 it is clear that GraphSHAP-IQ computes exact MIs and consequently exact SIs for 2 max (1A, (())), )), since GraphSHAP-IQ computes all MIs in I up order X. 1, GraphSHAP-IQ computes all MIs up to order max (IN, However, for neighborhoods of size maxie is then collected in Rx. W.l.o.g let R be the set to the corresponding missing MI. Due to the recovery property the MIs, this last missing interaction is exactly the gap computed in line 7, since
For À 2 maxieN
(IV) (MXX
(IA D) there only single MI remaining, which
mg Rt)
E1-1y~ = +
Σ (-))"
TCR
TCR
Since this holds for all missing interactions in R, and further I = Ix U Rr, it concludes the proof as also the efficiency gap (line 12) zero due to
Σ
(T)
my (T) = Σ
mg (T)) =
(T'))
Σ
mg(T) = (N) = (X)..
TA
TEI
TEN
Algorithm 4 GraphSHAP-IQ
Require: Graph g = (V, E, X), Layer GNN fg. MI order X, SI order k.
I: IA I'TEI,ITS
2: R^ + I W HI
3: Vg I
4: mg < [MI(Vg- S)SSEI
5: R^ + (RRI(RR)
6: for S E R2 do
7: [S] + Eres mgg [T]
8: 1S] + 1yl [S]
9: end for
5" + SELECTMA. R
11: T T f (X)
Σ mg T 12: 1 + 1
13: 4R +MIIO MIITOSI (mg, k)
14: return MIs mg. SIs d
D.3 INTERACTION ENTERACTION-INFORMED BASELINE METHODS
For given graph instance and GNN, Theorem 3.7 states that MIs sparse, i.e. all MIs of subsets that are not in I are zero. Unfortunately, model-agnostic baseline methods, such as Permu- tation Sampling (Tsai et al.. 2023). SHAP-IQ (Fumagalli et al., 2023), SVARM-IQ (Kolpaczki al., 2024b), KerneISHAP-IQ (Fumagalli et al., 2024) or Inconsistent KemneISHAP-IQ (Pelegrina et al., 2023; Fumagalli et al., 2024), use Monte Carlo sampling on the game evaluations, i.e. the masked predictions from the graph game Vg. Therefore, results on MIs cannot be directly applied to improve the baseline methods. However, all variants of SIs can be represented by MIs, and has been shown that the SI of subset S C N is given the weighted sum of MIs exclusively of subsets 7 C N that contain S, i.. C T (Bordt & von Luxburg, 2023). Due to the structure of non non-trivia trivial MIs I from Theorem 3.6. the following holds: For two sets S,T N with S T, if E I, then also S I. Conversely, & I, then also T & S. In other words, for the SI of a subset S C N with S $ I, its MI is zero, as well as all MIs of subsets T that contain S. Hence, the SI for subset S & I is
27

---

Published as a conference paper at ICLR 2025
zero as well, since it can be computed weighted sum exclusively of MIs of subsets that contain S. In conclusion, SIs of subsets that are not contained in can be discarded from approximation and set to zero. For baseline methods that estimate each SI separately using Monte Carlo, such as Permutation Sampling, SHAP-IQ and SVARM-IQ, we exclude these SIs from approximation and set their values zero. For regression-based methods, such KernelSHAP-IQ and Inconsistent KemmeISHAP-IQ. these interactions are excluded from the regression problem, and manually set to zero.
Notably, since all individual nodes are contained in Z, i.e. all nodes affect the graph prediction, the approximation of the SV unaffected by this adjustment. Consequently, do not adjust L-Shapley (Chen et al., 2019), as it is only applicable for SVs.
28

---

Published as a conference paper at ICLR 2025
E FURTHER BACKGROUND ON SHAPLEY INTERACTIONS
In this section we provide further background on SIs. We first provide more related work in Ap- pendix E.1. In Appendix E.2, we introduce SIs that satisfy the efficiency axiom. In Appendix E.3, we discuss conversion formulas of MIs to various SIs.
E.1 RELATED WORK ON SHAPLEY INTERACTIONS
The SV (Shapley, 1953) is concept from game theory (Grabisch, 2016) and applied in XAI for local (Lundberg & Lee, 2017; Covert et al., 2021; Chen al., 2023) and global (Casalicchio al., 2019; Covert et al., 2020) model interpretability, or data valuation (Ghorbani & Zou, 2019). The Myerson value (Myerson, 1977) a variant of the SV for games restricted on components of graphs. Extensions of the SV to interactions were proposed in game theory (Grabisch & Roubens, 1999; Marichal & Roubens, 1999) and MI. (Lundberg et al., 2020; Sundararajan al., 2020; Tsai al., 2023; Bordt & von Luxburg, 2023), where ML-based extensions preserve efficiency, c.g. the of interactions equals the model's prediction. The MIs (Rota, 1964; Harsanyi, 1963; Fujimoto et al., 2006) define fundamental concept in game theory, and the edge case of ML-based SIs. Due to the exponential complexity of SIs, efficient methods for tree-based models for SVs (Lundberg al., 2020; Yu al., 2022), any-order SIs (Zern al., 2023; Muschalik et al., 2024b) and MIs (Hiabu et al., 2023) were proposed. In model-agnostic settings, approximation methods have been proposed (Tsai al., 2023; Fumagalli al., 2023; Kolpaczki et al., 2024b; Fumagalli et al., 2024) as extensions of SV-based methods (Castro et al., 2009; Covert & Lee, 2021; Kolpaczki et al., 2024b; Lundberg Lee, 2017: Pelegrina al., 2023), and by exploiting graph-structured inputs (Chen et al., 2019). Recently, MIs were computed in synthetic settings (Kang et al., 2024).
E.2 EFFICIENT SHAPLEY INTERACTION INDICES
In the following, we describe extensions of the SV to SIs, which yield efficient interaction indices. That is, given an explanation order the SIs & are defined on all interactions up to order & and yield an additive decomposition of the model's prediction, i.e
v(N) = Σ (s(S).
SEN
k-Shapley Values (k-SII) The k-SIIs values of order 1 are defined as the SVs ΦV Furthermore, the pairwise k-SIIs are given as
P2(1t) - (ij)
and
p2(() = (
(1)
2
1
Σ
S (tj).
(ii))
JENYS
The general case is described by Bordt & von Luxburg (2023) and involves the Bernoulli numbers. For any explanation order l...., n, the k-SIIs are recursively defined as
(S)
if S = k
(S) = ② 11-1(S) + B
8=++8= SscNis (S if [ <
with 1 < |S| < < Do 0 and Bernoulli numbers B, (Bordt & von Luxburg, 2023). For 1, S-III is the SV, and for = n the MI (Bordt & von Luxburg, 2023). An explicit definition of S-IIII is given in Appendix A.I in Bordt & von Luxburg (2023)
K-19
** = Σ Σ
BRO (S R..
T=O RCN.IR|=F
Besides SII and S-III, there exist other interaction indices that extend the SV to higher orders and yield the MIs for kt These essentially differ by their distribution of MI lower-order interac- tions. Similar to k-III, these interaction indices can be described by the MIs. Hence, they can be computed once the MIs known.
29

---

Published as a conference paper at ICLR 2025
Shapley Taylor Interaction Index (STII) The STII (Sundararajan et al., 2020) is an interaction index that gives stronger emphasis to the highest order computed interactions, which capture all higher-order MIs. It is defined
STIL (S) =- a{S) for ||
< k and
P STII (S) Σ
(T( for |S] = k. TEN'S (iTi)
The STII for lower order, i.e. [S| < k, is simply the MI. For the maximum order, i.e. ||| k, the STHI is computed the higher-order MI with |S| > k solely on the top-order interactions of the STHL It was shown (Sundararajan al., 2020) that the STII is the only interaction index preserving the Shapley axioms that additionally satisfies the interaction distribution axion besides the classical axioms.
average over discrete derivatives. Therefore, the STII distributes
Faithful Shapley Interaction Index (FSII) The FSII (Tsai al., 2023) is an interaction index that yields stronger emphasis on the faithfulness of the interaction index. It is defined as the best approximation interactions up to order k in terms weighted least square objective
4 FSI
arg min
m(t)
((T)
E $s(())
4 CR
TEN, k<|Ti<n
SCT.ITISR
such that v(N)=
Σ
(S) and v(0) = (0)
SCN, 18|ck
where p(t) x 1-1 and n2 = KS S N [S| S kH is the number of interactions up to (2).t((ntt)
size k. It was shown that the FSII is the only interaction index preserving the Shapley axioms that additionally satisfies the faithfulness property, i.c. is represented as the solution to a single weighted
least square problem (Tsai al., 2023).
E.3 CONVERSION FORMULAS FOR MÖRIUS INTERACTIONS SHAPLEY INTERACTIONS
The MIs are a basis of the vector space of cooperative games and thus all SIs can be expressed in terms of the MIs. The SV well the SII can be directly computed by the conversion formulas
5v (i) = Σ
m(S)
and
SI (S)
Σ
m())
|ST
SEN:ES
SCN:825
The conversion formula for the MI to k-SII given Theorem 6 in Bordt von Luxburg (2023). The conversion for STH is given in the proof of Theorem 8 in Appendix H (Bordt & Luxburg, 2023). The conversion formula from to the FSII is given in Theorem 19 in Tsai et al. (2023).
30

---

Published as a conference paper at ICLR 2025
F EXPERIMENTAL SETUP AND REPRODUCIBILITY
All the experiments have been conducted using the PyTorch Geometric library (Fey Lenssen, 2019), running a computing machine equipped with Intel(R) Xeon(R) CPU, one Nvidia RTX A5000 and 60GB of RAM. Overall, the total compute time of this project, including preliminary experiments, training of GNNs, computation of baselines and SIs, required no more than 100 hours, which could be reduced by simple parallelization.
F.1 DATASETS
All considered methods were empirically validated eight common real-world chemical datasets for graph classification and one real-world water distribution network for graph regression. We avoid synthetic datasets commonly used in the graph XAI community due to their limitations (Amara et al., 2022). The licenses for the datasets are summarized in Table
Table 3: Dataset License Overview
Dataset
Source
License
BNZ
(Sánchez-Lengehle et al., 2020)
CCO 1.0 Universal
FLC
(Sinchez-Lengeling et al., 2020)
CCO 1.0 Universal
MTG
(Kazius et al., 2005)
CCO 1.0 Universal
ALC
(Sänchez-l.cngeling et al., 2020)
CCO 1.0 Universal
PRT
(Borgwardt et al., 2005; Morris et al., 2020)
"Free use", cf. Section 2 of Morris et al. (2020)
ENZ
(Borgwardt et al., 2005; Morris et al., 2020)
"Free use", cf. Section 2 of Morris et al. (2020)
CX2
(Sutherland al., 2003; Morris et ul., 2020)
"Free use". cf. Section 2 of Morris al. (2020)
BZR
(Sutherland al., 2003; Morris al., 2020)
"Free use". cf. Section 2 of Morris
(2020)
WAQ
(Vrachimis et al., 2018)
EUROPEAN UNION PUBLIC LICENCE 1.2 EUPL
F.1.1
CHEMICAL DATASETS
This data reflects biological and chemical problems, where particular substructures predict the properties of molecules. The Benzene (BNZ) (Sánchez-Leengliing et al., 2020) dataset consists of 12 000 moleculars, with each graph labeled as containing not benzene ring. In this context, the underlying explanations for the predictions are the specific atoms (nodes) that make up the benzene rings. The Fluoride Carbonyl (FLC) (Sanchez-Lengeling
al., 2020) dataset comprises 671 molecular graphs, each labeled positive or negative. A positive sample denotes a molecule with a fluoride ion (F-) and a carbonyl functional group (C = O). The underlying explanations for the labels are the specific combinations of fluoride atoms and carbonyl functional groups present within a given molecule. Similarly, the Alkane Carbonyl (ALC) (Sánchez-LLengllng
al., 2020) dataset consists of 1 125 molecular graphs, labeled positive if it features an unbranched alkane chain and functional carbonyl group (C= O), which serves as an underlying explanation. The Mutagenicity (MTG) (Kazius et al., 2005) dataset comprises 768 graph molecules, categorized into two classes based on their mutagenic properties, specifically their effect on the Graa--eeativee bacterium S. Typhimurium. Following Agarwal et al. (2023), the original dataset of 337 graphs reduced to 768, retaining only those molecules whose labels directly correlate with the presence or absence of specific toxicophores (motifs in the graphs), including NH2, NO2, aliphatic halide, nitroso, and azo-type groups, as defined by (Kazius et al., 2005). The latter four datasets have been retrieved from the implementation of (Agarwal al., 2023). PROTEINS (PRT) (Borgwardt al.. 2005) and ENZYMES (ENZ) (Borgwardt et al.. 2005) involve graphs whose nodes represent secondary structure elements and edges indicate neighborhood in the amino-acid sequence, entailing 113 and 600 graphs respectively. BZR (BZR) and COX2 (CX2) (Sutherland et al., 2003) are correlation networks of biological activities of compounds with their structural attributes, of 405 and 467 graphs. These latter datasets are fetched from the benchmark collection of (Morris et al., 2020). They all have binary labels except for ENZ, which has 6 classes. Finally, we did not exploit the additional continuous node features available for ENZ.
1.1 WATER DISTRIBUTION NETWORK
We apply GraphSHAP-IQ to a dynamical system governed by local partial differential equations (PDEs). Specifically, the spread of chlorine in water distribution systems (WDS), where GNN pre-
31

---

Published as a conference paper at ICLR 2025
Table 4: Model accuracy for shallow and deep GNNs (1-6 layers).
Dasuet Descrjsion
Aeconacy (iger1
Datant
Graplo
Nodes
omg)
Benity Garg
GUN
GAT
GIN
0S0ncher wangsiing 1070)
12000
20.6
22.6
15.2
85.
SALE
VALE
SALE
85.1
15.7
54.5
87.8
19.3
S45
9415
92.1
923
72.1
Elleggand 2009)
000
32.6
323
305
43.
ALD
3L.
52.5
25D1
25.
253
R33
45.9
36.7
35.0
250
310
300
dicts the fraction of nodes chlorinated after some time, framing this task as a graph-level regression. We chose this task because chemicals in WDS spread predominantly with water flow (advection). Therefore, the task should be mainly explained by the flow pattern of the network, which yields an intuitive expectation of the explanations.
We generate a temporal dataset WaterQuality (WAQ) using the EPyT-Flor toolbox (Artelt et al., 2024). The dataset consists of 1000 temporal graphs with 30 time steps each. Spatially, the graphs represent the Hanoi WDS (Vrachimis et al., 2018), popular 32-node benchmark WDS.
F.2 GNN ARCHITECTURES
Our approach universally applics to any message passing GNN and can be employed on graph datasets without requiring ground truth explanations. Since different GNN architectures exhibit unique learning patterns and performance characteristics, their explanations will also vary. To demonstrate the effectiveness of our approach, we followed the remarks and setting of Amara et al. (2022), by comparing the explanations of three popular GNN models: GCN (Kipf & Welling, 2017), GIN (Xu et al., 2019), and GAT (Velickovic et al., 2018). The overall model architecture is fol- lows: the graph input is unprocessed, we stack the GNN layers for E {1, 2, 3), concatenate all the embeddings (You et al., 2020). apply global sum- sum-pooling (Xu et al., 2019), and finally, a dense lin- ear layer returns the output predictions. Furthermore, each GNN layer is followed by sequence of modules: bat batchhnor chrnooraaaaaaa
zat on, dropout, and LeakyReLO activation function (You al., 2020). We validated the models for different amounts of hidden units h E {8, 16, 32, 64, 128), and we defined the multilayer perceptron of GIN with 32 hidden units, while all the remaining design choices for the GNN layers follow their default settings (e.g., aggregation function, number of at- tention heads, ...). For a selection of datasets, we also compared performances for deeper GNNs, cf. Table 4. The performances of the deeper models compared to more shallow GNNs mixed. All architectures lead to quite similar performances. Both shallow (less than 4 GNN layers) and deeper models (more than 3 GNN layers) lead best performing architectures.
Regarding WAQ, since we now have important edge features (water flows), we cannot use vanilla GCN, GIN, or GAT before. Instead, we designed a simple GNN that can process edge features, using 3 message-passing layers with mean-aggregation, ReLU activations, global average-pooling as the readout layer, and finally, a linear layer provides the regression outputs.
F.3 TRAINING
The adopted loss is the (binary) Cross- Pross-Entropy for classification and the L₁ for the regression. The chemical datasets have been split train/validationtess sets with a ratio 90/10/10 10 in a strati- fied fashion, ensuring that the splits have balanced amount of classes. The models are randomly initialized and trained for 500 epochs with harry_stoppl
with patience of 100 on the valida- tion set and batch size of 64. The models have been trained with Adam optimizer with starting learning rate of 0.01, using a halving scheduler with the patience of 50 epochs up to le and we weight.decay factor of 44
The test accuracies for the best-validated model configuration reported in Table 1, are comparable existing benchmarks (Errica et al., 2020; You al., 2020), confirming that our approach is valid for complex and powerful GNN architectures, as long as Assumption 3.4 holds. Moreover, deeper GNNs do not necessarily yield better performances, cf. Table 4.
32

---

Published as a conference paper at ICLR 2025
G ADDITIONAL EXPERIMENTAL RESULTS
This section includes additional empirical results and further details on the experimental setup. Ap- pendix G.I contains additional complexity results for benchmark datasets. Appendix G.3 shows a timeline for the WDN example use case. Appendix G.4 shows the approximation quality of GraphSHAP-IQ compared collection of sate--of-the-aee baseline methods. Appendix G.5 show- cases example SIs on molecule structures from different datasets.
G.1 COMPLEXITY ANALYSIS
In this experiment we provide further results on Section 4.1. We evaluate the complexity on GNNs with varying number of convolutional layers multiple benchmark datasets, described in Ta- ble The complexity is measured by number evaluations the GNN-induced graph game, i.e. number of model calls of the GNN, which is the limiting factor of SIs (Fumagalli al., 2023; Kol- paczki et al., 2024b; Muschalik et al., 2024b). Due to Theorem 3.7, the complexity of GraphSHAP- IQ does only depend on the message passing ranges and particular independent of the message passing technique. We therefore omit the explicit architecture in this experiment and focus only on the number of convolutional layers l. For every graph in the benchmark datasets, we evaluate the complexity of GraphSHAP-IQ,, where the model-agnostic method requires 2", where n is the num- ber of nodes in the graph. the size of the largest neighborhood exceeds 22, i.e. GraphSHAP-IQ requires at least 2 R 8.3 x 10 model calls, then the complexity is approximated by the upper bound presented Theorem 3.7. Figure 7, Figure 8, and Figure display the complexity (in log 10) by the size of the graphs for all instances (upper) and the median, Q1, and Q3 per graph size (n) for all benchmark datasets. The model-agnostic computation represented by the dashed line. The results show that the ground-truth computation of SIs is substantially reduced by GraphSHAP-IQ for many instances in the benchmark datasets.
FluorideCarbenty
MutacericRty
101
100m
Layer (0.95)
100m
Layer (2.99)
humber Modot Calla Kng Cug 101
100
Layara (1:335
Layera (0.2) (0.25)
1m
Tavelira
Lavera
humber Model Call
3m
Baseirra
Layers (0.2
1m
30k
10k
J0k
Layer 10
Layers (0.56
3k-
Layers 78.49)
100
300
Layers (0.52)
Boscin::
10 12
1B 20
6 20 28 20 24
15
50 10s 120 15s
Number of Graph Roodee (7)
Naumeer Graph Mottie (n)
Number Gragh Rodes (1)
Senzene
FluortdeCabbnyy
Mutacenicky
100m
Layer (0.96)
944 Layeru
humber Hodel Cala 500
10am
Layers 00.335
Layer 98.981
100
Layers (0.95)
bumber of Cals
1m
Deatiins
Layaru
3m
Beeeiirar
Layera (0.25)
1.09
304
30k
Layer 10
Layers 30.56
3k
Layers (8.49)
300
200
Layers (0.52) Basctine
6 10 14 16 18..8.0 Number Grach Rodee
6 8 10 14 20
75 50 105 120 135
Namber Graph Rotden
humber Grach Rodee (1)
Figure 7: Complexity of GraphSHAP-IQ against model-agnostic baseline (dashed) in model calls (in log 10) (y-axis) by number of nodes (x-axis) for all instances (upper) and median, Q1, Q3 (lower) for BNZ (left), FLC (middle), and MTG (right).
33

---

Published as a conference paper at ICLR 2025
AkkanCarbony
PROTEINS
ENZYMES
100m
Layer (0.98)
Numbar of Modie CatAA 30
300m
Nurvar Wuze Call- Mig 100
200
Lavers 10
Layerr 413
Baselline
Layers 9E;
3m
1n
1024
100k
1.06
Mude
304
1 Layer 721 2 Layers [0.73
30c
Layer 10.781
3k-
3 Layars [b,12]
1k
Layeers (0,09)
Layers (5.72)
Layars (4) Senetine
Layer (0.09)
Baseliee
30 13 38 18 20 24
15
35
45
00
75 Do 305 320 135
24 36
40 or 72 Bf as 120
Number Groph
Graph
AlkaneCarbenyy
PROTEINS
FNZYMES
100
Layer (0.35)
100m
Tammbe of Cits din 101
100m
Layara 50.51
Naamber of Cata Oin
Laysrs 912)
Laaerrs 92)
Easctine
2034
100k
1006
Layer 73)
Layer 18 701
Layers
Lapets 10 721
14
18
Layers
14
Layers 690
4 Layers Saseline
Layers 30, 660
Basetine
10 14 28 24
30 45 60
75 90 105 320 135
36 40
84 96
Figure 8: Complexity of GraphSHAP-IQ against model-agnostic baseline (dashed) in model calls (in log 10) (y-axis) by number of nodes (x-axis) for all instances (upper) and median, QI, Q3 (lower) for ALC (left), PRT (middle), and ENZ (right).
COK2
BZA
300m
Number Model Catl On lcg 301
100m
10m
200k
200k
Layer 98)
Layer 95)
2 Layers 10 591
Layer
30
Layers 10 521
3k
Layers (0
Layers 44)
Layas (0.77)
Seacii:
boadin:
10
48
St
$5
20
23
30
40
59
Graph
COK2
EZA
300m
(Ramber tootea Call Ievtoe 121
100mm
10m
100K
100k
Layer (2.2
Layer 99;
Layers (0.85)
28
Layars 10
18.
Layerr
Layees
Layers
Saceline
Saceline
30
96
Figure 9: Complexity of GraphSHAP-IQ against model-agnostic baseline (dashed) in model calls (in log 10) (y-axis) by number of nodes (X-axis) for all instances (upper) and median, Q1, Q3 (lower) for CX2 (left) and BZR (right).
34

---

Published as a conference paper at ICLR 2025
G.2 RUNTIME ANALYSIS
In this section, we conduct a small runtime analysis to confirm that the main driver of computa- tional complexity for GraphSHAP-IQ is indeed the number of model calls. This is standard in the approximation literature of SIs (Tsai et al., 2023) and confirmed for all baseline methods (Fumagalli al., 2024). We select 100 graph instances from MTG with 20 to 40 nodes, where GraphSHAP-IQ requires less than 10000 model calls for exact computation for a 2-Layer GCN. We then compute exact SIs for order (SV). 2 (2-SII), and 3 (3-SII) with GraphSHAP-IQ. For each graph instance, we run all baseline methods using the same budget that GraphSHAP-IQ required for exact com- putation. Figure 10 shows the number of model calls and runtime (upper row), as well as number of graph nodes and runtime (lower row) for order 1 (left), 2 (middle), and 3 (right). As expected, GraphSHAP-IQ's runtime scales linearly with number of model calls, and is basically unaffected by the size of the graph. Moreover, given the same number of model calls, GraphSHAP-IQ" runtime is similar to efficient baselines (SHAP-IQ and Permutation Sampling). Notably, increasing the ex- planation order barely affects the runtime of GraphSHAP-IQ, whereas it substantially increases the runtime of competitive baselines (KernelSHAP-IQ, SVARM-IQ, SHAP-IQ).
Furdine Analgii for Doole watie 3
Kurtin Cople wateen Order
JuKEIn Analyao for Exp anabie order
2000
Hardine Aoalgii bet code C d
Kurtin you OOE
30 23.30 20 24 21 30 12
20.22:0 20 2433 30 25.20
2022 30 21 28 24 15
Figure 10: Runtime comparison of GraphSHAP-IQ and baseline methods for SVs (left), 2-SII (mid- dle), and 3-SII (right). All methods were given the number of model calls, which were required for exact computation with GraphSHAP-IQ. The runtime (y-axis) against number of model calls (x- axis) plot (upper row) shows that the runtime of GraphSHAP-IQ scales linearly (A²² > 0.97) with increasing number of model calls. In contrast, the runtime (y-axis) against number of graph nodes (x-axis) plot (lower row) shows that the runtime is independent from the size of the graph. Lastly, increasing the explanation order substantially increases the runtime of most baseline methods, but barely affects GraphSHAP-IQ.
35

---

Published as a conference paper at ICLR 2025
G.3 EXPLAINING WATER QUALITY IN WATER DISTRIBUTION NETWORKS (WDNs)
We investigate the validity of our approach in explaining a critical real-world scenario: adding chlorine water distribution system (WDS) is a common disinfection practice used to inactivate microorganisms that can cause waterborne diseases. Chlorine is an effective disinfectant due to its ability to oxidize and denature microbial cells. However, can be toxic to aquatic organisms, particularly at high concentrations, and can impart an unpleasant taste or odor to the water, affecting consumer acceptance. In practice, chlorine is added a water reservoir and flows unevenly through the network. Therefore, it is essential to model these flows and concentrations, which is not trivial since it a dynamical system governed by local PDEs. We frame this problem as graph regression task, where the goal is to predict the relative chlorine concentration for each node at each time step. In Figure 1 1, we report the Hanoi WDN (Vrachimis et al., 2018) and simulate a chlorine injection at node reservoir 31 for t O. We observe how the 2-SII highlight the progressive importance of the nodes from the reservoir throughout the network.
Time Step 1
Time Step 2
Time Step 5
Time Step 10
Figure 11: Spread of chlorination through a WDN over time as explained by 2-SII.
G.4 APPROXIMATION QUALITY OF GRAPHSHAP-IQ
Additionally to the experiments conducted in Section 4.2, this section contains further evaluations on three datasets and detailed description of the SV baselines (Appendix G.4.2) and the 2-SII baselines (Appendix G.4.3). Figures 12 to 14 show the approximation quality of different GNN architectures for the MTG, PRT, and BZR benchmark datasets. Appendix G.4.1 outlines the approx- imation experiments in detail.
G.4.1 SETUP DESCRIPTION
To compare GraphSHAP-IQ's approximation result with existing model-agnostic baselines, we compute SIs for three benchmark datasets (MTG, PRT, and BZR). For each dataset, we randomly select 10 graphs containing 30 < < 40 nodes each. Based on Section 4.1, we further limit the selection to graphs which can be exactly computed via GraphSHAP-IQ with at most 100 (for MTG and PRT) and 2 32 768 (for BZR) model evaluations. First, compute SIs with GraphSHAP-IQ for each MI interaction order À starting with = until À 2 max x (IN, fc.f. Corollary D.1). Note that for different graphs even for the same datasets the maximum À value may differ. For each X, we observe the required model evaluations by GraphSHAP-IQ. Second, compute SIs with the bascline methods provided the same approximation budget as required by GraphSHAP-IQ for each A. Therein, we directly compare how the baselines (which may be run with any arbitrary approximation budget) compare with GraphSHAP-IQ. For each estimation budget (number of model evaluation), we estimate the SIs via two independent iterations for each baseline and average the evaluation metrics (each dot in Figures 12 to 15 are averaged evaluation metrics over two runs). As evaluation metric we choose the squan---uared-rroo (MSE, lower is better). For each graph, we compute the MSE between the ground truth SIs, as computed by exact GraphSHAP-IQ. and the estimated values.
G.4.2 DESCRIPTION OF SV BASELINES
As SV baselines we apply current state-of- ofate-of-the-art sampling based methods that operate on different representations of the SV and/or aggregation technique. In general, all of the following baseline
36

---

Published as a conference paper at ICLR 2025
methods (with L-Shapley the only exception) sampling coalitions of players, evaluate the model on these coalitions, observe the output of the model, and finally aggregate the observed out- puts into the SV. All SV baselines are implemented according to the shapiq (Fumagalli et al., 2023) open-source software package in Python.
KernelSHAP proposed in (Lundberg & Lee, 2017) is prominent SV approximation method and is applied akin to its original conception in addition to the sampling tricks discussed in (Covert & Lee, 2021; Fumagalli et al., 2023).
k-Additive KernelSHAP (Pelegrina et al., 2023) is an extension to KernlSHHA,, which also utilizes higher-order SIs in the computation procedure of the SV. Therein, it shows better approximation qualities than KemelSHAP. For our experiments, we set the higher-order interactions to 2.
Unbiased KernelSHAP (Covert Lee, 2021) extends KernelSHAP and offers a provably unbi- ased alternative. It was recently shown that Unbiased KemelSHAP is linked to the K-SII SHAP-IQ estimator (Fumagalli al., 2023).
Permutation Sampling for SV (Castro et al., 2009) is standard estimation method that iterates over random permuations of the player to determine the coalitions be used for the model evaluations. Because a permutation always needs to be traversed in its entirety, the number of model calls may be lower than GraphSHAP-IQ's s or the rest of the baselines.
SVARM (Kolpaczki et al., 2024a) is another sampling- based baseline operating on stratified rep- resentation of the SVs. Akin to KernelSHAP it can be queried on an arbitrary number of coalitions.
L-Shapley (Chen et al., 2019) is a deterministic method for computing the Shapley values for structured data. Unlike the rest of the SV approximation methods, L-Shapley cannot be evalu- ated on an arbitrary set of coalitions or number of model evaluations. L-Shapley functions similarly to GraphSHAP-IQ in that deterministically evaluates coalitions based on neighborhoods in the graphs. To circumvent this, we let L-Shapley akin to GraphSHAP-IQ. After L-Shapley exceeds GraphSHAP-IQ's number model evaluation we stop the iteration and use the last estimates (the estimates where Shapley always exceeds GraphSHAP-IQ in terms of model evaluations).
G.4.3 DESCRIPTION OF 2-SII BASELINES
Similar to Appendix G.4.2, we apply current state-of-theaar sampling based methods for 2-SII and in general k-SII All of the following baseline methods are sampling-bass based. We implement the experiments based on the shapig (Fumagalli et al., 2023) open-source Python software package.
KernelSHAP-IQ (Fumagalli et al., 2024) directly extends the SV KernelSHAP approximation paradigm SII and, hence, to k-III. KemnelSHAP-IQ leads high quality estimates.
Inconsistent KernelSHAP-IQ (Fumagalli et al., 2024) is a different version of KemelSHAP-IQ, which is linked to the k-Additive KemelSSHA (Pelegrina et al., 2023). While often leading to better estimations in lower number of model evaluations, Inconsistent KernelSHAP-IQ does not converge to the ground-truth values like KernelSHAP-IQ.
SHAP-IQ (Fumagalli et al., 2023) is sampling-basee based mean estimator for computing SIIs among other interaction indices like STII. It is theoretically linked to Unbiased KerneiSHAP (Fumagalli et al., 2023) and, thus, transfers its SV procedure to SII.
Permutation Sampling for SIī(Tsai et al., 2023) directly transfers the permutation sampling proce- dure from its SV counterpart (Castro et al., 2009) to estimate SIL. Similar to the SV algorithm. the SII variant requires a full pass through a permutation which may lead to less model evaluations with this baseline.
SVARM-IQ (Kolpaczki et al., 2024b) extends SVARM's (Kolpaczki et al., 2024a) stratified rep- resentation from the SV to the SII. Often SVARM-IQ outperforms state-of-the tfr approximation methods.
G.5 EXPLANATION GRAPHS FOR MOLECULE STRUCTURES
This section contains further exemplary SI-graphs for molecule structures of the MTG and BNZ datasets. Figure 16 shows two molecules from the MTG dataset, where of those molecules is
37

---

Published as a conference paper at ICLR 2025
Baselines
KarnelSHAP-10
Inc. KHAP-SHAP-1Q
Permutation Sampling
SHAP-1Q
SVARM-I0
2 f4 PROTBNS with
2:51 PROTEINS with 2
2:51 PROTERNS RIS whth
30-
327
2 30-1
10
10-1
10"12
Gra Q
6600
2:511 PROSTENS with byyerGCN
2:91 for PROTENS with 2 ayer GAT
2. for PROTENS with 2lyyer GIN
30"1
30-
20-1
20-4
30-
30"1
30'
38-12
30"
#ooph-90e-ng wg Interlattion
Figure 12: Comparison of GraphSSHAPIIQ's approximation quality with model-agnostic baselines on 10 graphs with 30 < n S 40 nodes from the PRT dataset for 2-layers GCN (left), GAT (middle) and GIN (right). The top row presents the MSE for each estimation (dots) and averaged over À (line) with the standard error of the mean (confidence band). The bottom row shows the same information including the MIs box plots for each A.
the same as in Figure 1. Further, Figure 17 shows additional SI-Graphs for molecules of the BNZ dataset. Lastly, Figure 18 shows how the SI- SI-Graphs differ for different GNN architectures.
38

---

Published as a conference paper at ICLR 2025
Baselliee
KameISHAP-10
Inc. Kema/SHAP-IQ
Permutaiion Samaling
SHAP-IQ
SVARM-HQ
gulaginiclty 2-yyer
Musagenicky
Mulaperic
2014
101
23-
100
30%
10
201
200
10-
10-
10-
Drad Ap
5002
2003
9:0 Hedel Evsustiona
10-11
2006
0:300 Model Dveluation
2:51 for Nutagenicity with 2 baee GCN
2 S1 for Nutagenicity With 2 layer GAT
S1 for MuDagenictty with 2 aver GIN
10-1
20-1
18
y
10
20-
10-4
10-
10--
20-1
0a0gishede 92 wrieaaie Denee
Figure 13: Comparison of GraphSHAP-IQ'' approximation quality with model-agnostic baselines on 10 graphs with 30 < n I 40 nodes from the MTG dataset for a 2-layers GCN (left), GAT (middle) and GIN (right). The top row presents the MSE for each estimation (dots) and averaged over x (line) with the standard error of the mean (confidence band). The bottom row shows the same information including the MIs as box plots for each X.
Baselines
2
for KernelSHAP-10
Inc. KHAR--HAR--Q
Permutation Samalina
SHAP-IQ
SVARM-I0
21 B2R
S1
355
232
327
107
22
10
10-5
10
10-1
5340
JOCCO
33063
20303
5050
1200E
2000
5303
33030
2000
Deckutires
2-511 for 877 with 7-ayee GCN
2-51 for RZZ Wish 2-ayer GAT
2:58 for B7B with 2-ayer GN
10-
10-1
10-0
8
10-1
20-4
9
0
10-4
10-
10-0
10-1
01 intrrcction Orderr
CHardOHAnID www.scter Crtt
Figure 14: Comparison of GraphSHAP-IQ's approximation quality with madel-agnostic baselines on 10 graphs with 30 < n < 40 nodes from the BZR dataset for 2-layers GCN (left), GAT (middle) and GIN (right). The top row presents the MSE for each estimation (dots) and averaged over À (line) with the standard error of the mean (confidence band). The bottom row shows the same information including the MIs as box plots for each X.
39

---

Published as a conference paper at ICLR 2025
Baselines
KemelSHAP
KernelSHAP
Permutation Sampling
KemneSSKP
SVARM
5V PROTT 2-leyeGGKK
for PROTEIN with GAT
SV IR-TTCII 24ayer CIN
10-4
10-
1044
9
30-
10-1
10
30000
6000
6633
5V for PROTEINS With 2- ayer CDN
SV for PROTEINS with 2-aywr EAT
5V for PROTE IS with Jeya GN
20-1
30-4
31-3
30-
2-001
30-
20-1
10
GroP5//AA4 intruction Crear
Figure 15: Comparison of GraphSHAP-IQ's approximation quality with model-agnostic baselines on 10 graphs with 30 < n S 40 nodes from the PRT dataset for 2-layers GCN (left), GAT (middle) and GIN (right). The top row presents the MSE for each estimation (dots) and averaged over À (line) with the standard error of the mean (confidence band). The bottom row shows the same information including the MIs box plots for each X.
40

---

Published as a conference paper at ICLR 2025
SV-Graph:
2-SII-Graph:
3-SII-Graph:
MI-Graph:
Figure 16: Additional SI-Graphs for molecule structures of the MTG dataset; molecule 7/ with 30 atoms (left) and molecule 189 with 14 atoms (right). The model a 2-layer GCN.
41

---

Published as a conference paper at ICLR 2025
SV-Graph:
STII-Graph: (order 2)
2-SII-Graph:
6-SII-Graph:
Figure 17: Additional SI-Graphs for molecule structures of the BNZ dataset; molecule Pyridine with atoms (left) and molecule 57 with 21 atoms (right). The model a 3-layer GAT.
42

---

Published as a conference paper at ICLR 2025
3-Layer GCN
3-Layer GIN
3-Layer GAT
2-SII:
MI:
Figure 18: Comparison of the SI-Graphs for the pyridine molecule for the three model architectures fitted on BNZ. All models accurately predict the molecule to be non- con-benzene.
43


Reviews:
[{"review_id": "w0QBJfhNnJ", "reviewer": "Reviewer_zYPu", "summary": "The paper introduces GraphSHAP-IQ, an approach to compute any-order Shapley Interactions exactly. The authors focus on explanations for fro graph classification task. First thing, they introduced GNN-induced Graph and Node Game, they show the invariance of the node game with respect of masking outside its $\\ell$ neighbourhood, where $\\ell$ is the number of layers of the GNN. \nExploiting this they also show that for GNN the complexity of MIs depends only linearly in the saize of the graph and exponentialy in the connectivity of the graph. Finally experiments on real world dataset are reported.", "questions": "- The paper addresses the problem for graph classification. Could this approach be extended to node classification? \n- Could we use a different baseline choise intead of the mean.  Such as a random baseline and a learned baseline ?\n\nTypo: \n- Line 421 \"ground truth \" shold be \"Ground truth\".", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-  The mehtod introduced in the paper is novel. \n-  The method is sound  and  the authors provide robust theoretical results. \n- The authors validate their approach with experiments on diverse datasets, including real-world datasets.", "weaknesses": "- Adding information on the algorithm's running time across different datasets and compare it with the running time of the baselines would provide more information about the applicability of the method. \n- The method's efficiency heavily depends on graph sparsity and the size of receptive fields. For very dense or large graphs, the complexity may still be prohibitive.\n- The algorithm assumes linear global pooling and output layers, which limits its direct application to non-linear readouts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CDCDJpjaLh", "reviewer": "Reviewer_dedn", "summary": "This paper identifies an invariance property in node games on graphs and demonstrates that the exponential complexity of Shapley Interactions depends only on the receptive fields of graph neural networks. Leveraging this insight, the authors propose GraphSHAP-IQ, a method for efficiently computing any-order Shapley Interactions for graph neural networks. They also introduce an approximate version of GraphSHAP-IQ, which restricts computation to the highest order of Möbius Interactions. Finally, the authors propose a visualization technique for Shapley Interactions using SI-Graph and validate their approach through experiments on various real-world applications.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed GraphSHAP-IQ method demonstrates high efficiency.\n- The authors provide theoretical guarantees for GraphSHAP-IQ's computational complexity.\n- Extensive experiments on real-world applications are conducted, with results clearly illustrated. Notably, the introduction of the WAQ dataset adds valuable tools for evaluating explanation methods on graphs.\n- The paper is well-written and easy to follow.", "weaknesses": "- **Novelty**: The primary contribution of this paper lies in reducing the computational complexity of Shapley Interactions through node game invariance, limiting the calculation of Shapley Interactions within the receptive field of the graph neural network. However, this approach is not entirely novel, as it was previously proposed in other works. For example, Section 5.4 of [1] states:\n\n  > Indeed, for a GNN model with $k$ layers, only $k$-hop neighbors of $v$ can influence the prediction for $v$, and thus receive a non-zero Shapley value. All others are allocated a null importance according to the dummy axiom and can therefore be discarded.\n\n  Extending this approach from model-agnostic to structure-aware approximation may offer limited novelty on its own.\n\n- **Experiments**: In Figure 4, the authors claim that GraphSHAP-IQ achieves better approximation quality than other methods, by comparing their MSE **at the same number of model evaluations**. However, as noted in the previous point, GraphSHAP-IQ’s performance advantage could be attributed simply to disregarding nodes outside the GNN’s receptive field, thereby requiring fewer model evaluations. Thus, the assertion that GraphSHAP-IQ provides superior approximation quality is unconvincing. A more balanced evaluation would involve applying the same efficiency optimization across all methods and comparing results to see if GraphSHAP-IQ still outperforms.\n\n- **Minor Issues**: The vertical spacing between paragraphs appears missing. Additionally, some capitalized terms (e.g., SV, SI, MI) and the term “BShap” contain hyperlinks that link incorrectly to the first page of the paper. \n\n[1] Duval, A., & Malliaros, F. D. (2021). GraphSVX: Shapley Value Explanations for Graph Neural Networks. In *Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings, Part II 21* (pp. 302-318). Springer International Publishing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o07LmFyeHp", "reviewer": "Reviewer_cY3Q", "summary": "The paper studies the interpretability of graph neural networks (GNNs) via Shapley Interactions (SIs). Specifically, it explores quantifying node contributions by computing exact SIs. The paper proposes an any-order SIs computation method named GraphSHAP-IQ, which can significantly reduce the complexity of exact SIs computation. Finally, it conducts extensive experiments to validate the effectiveness of GraphSHAP-IQ and complexity reduction.", "questions": "What is the purpose of showing the performance of GNN vanilla in Table 1?", "limitations": "", "rating": 3, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "- The figures on the paper are well-constructed and clearly convey the intended information.", "weaknesses": "- The writing in the paper needs significant improvement, as it currently makes it difficult for readers to follow the arguments and content. The issues with the writing can be summarized as follows: (1) The overall logic and flow of the paper are unclear, which hinders comprehension. (2)Several grammatical errors detract from the clarity and professionalism of the manuscript.\n\n- The motivation for the study is not clearly articulated and does not come across as compelling. This appears to be a result of suboptimal writing throughout the paper.\n\n- The review of related work appears to be somewhat disorganized, and it would be beneficial to provide a more detailed comparison with similar methods, such as TreeSHAP.\n\n- The experiments provided do not convincingly demonstrate the effectiveness of the method in reducing complexity. Additional or more targeted experiments may be needed to better support this claim.\n\nI recommend thoroughly revising the paper, enhancing the logical structure, and addressing the grammatical issues. This will greatly improve the readability and overall quality of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WxSQoZWVtR", "reviewer": "Reviewer_HTEk", "summary": "This paper proposes a method for efficient calculation of exact and approximate any-order Shapley Interactions by leveraging GNN structure and node receptive fields to filter out trivial interactions, eliminating unnecessary computations and significantly accelerating processing. For highly connected graphs or very deep GNNs, the paper introduces an approximation technique to ensure computational feasibility. Experiments demonstrate substantial acceleration and low error for the approximation method.", "questions": "1. In Fig.4 right, it seems that we can just plot the top-k most important 2-node group to remove the unimportant ones and get a clearer visualization. And the top relevant groups seem to be the same, i.e, N-O? It would be interesting to compare the top-k most important groups of the exact SHAP and approximated SHAP.\n2. Accuracy and computation expense needs trade-off when using SHAP. How much faster/slower is the proposed method than other approximation methods of SHAP? A figure with computation expense as x-axis, MSE as y-axis and each method as a point would be useful for users to decide when to use which method.\n3. Is the proposed method extendable to other models? E.g., for CNN, where each input pixel also has receptive fields.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe figures are well plotted, particularly Fig. 2.\n2.\tThis paper takes an innovative approach by leveraging the structural characteristics of GNNs to accelerate the computation of any-order Shapley Interactions, while ensuring exact results.\n3.\tThe experiments cover a diverse range of datasets and GNN architectures, providing comprehensive qualitative and quantitative results that demonstrate the method’s efficiency and low approximation error.", "weaknesses": "1. The restriction to a linear readout function may limit the method’s broader applicability.\n2.\tHigher-order interactions could make the interpretations for the visualization more challenging for users.\n3.\tThe extensive use of varied notations can be difficult to follow without a notation table.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)