Shapley Values on Graphs

The sum of all node or edge Shapley values equals the difference between the GNN's prediction for the original graph and its expected prediction over all possible graphs (the baseline). This property guarantees a complete decomposition of the prediction, leaving no attribution unaccounted for.

• Full Accountability: The total prediction deviation is perfectly partitioned among all graph components.
• Budget Constraint: The sum of importances acts as a zero-sum budget, forcing the method to distribute credit precisely.

Two nodes or edges that make the exact same marginal contribution to the prediction when added to any possible coalition of other graph components must receive identical Shapley values. This ensures procedural fairness.

• No Structural Bias: Importance is based purely on functional contribution, not on arbitrary node indices or labels.
• Isomorphic Guarantee: Structurally identical components within a subgraph are guaranteed equal importance scores.

A node or edge that contributes absolutely nothing to the prediction—its addition never changes the output regardless of the coalition—receives a Shapley value of exactly zero. This property naturally filters out irrelevant components.

• Sparsity Induction: Non-contributing elements are automatically assigned zero importance, simplifying the explanation.
• Noise Rejection: Isolated nodes or edges disconnected from the predictive signal are mathematically ignored.

If the GNN's prediction function is a linear combination of two separate functions, the Shapley value for a node is the sum of its Shapley values computed on each function independently. This ensures mathematical consistency across model ensembles.

• Ensemble Compatibility: The importance of a node in a bagged or boosted ensemble of GNNs is simply the average of its importance in each model.
• Feature Decomposition: Allows for the independent attribution of importance to different output classes or logits.

The Shapley value is fundamentally defined as a weighted average of marginal contributions. A node's importance is calculated by observing how much it changes the prediction when added to every possible subset of other nodes, then averaging these changes with a specific combinatorial weighting.

• Coalitional Fairness: This averaging over all possible orderings is the mathematical core that distinguishes Shapley from simple gradient-based methods.
• Context-Aware: A node's contribution is evaluated in the context of all possible interactions, capturing complex non-linear synergies.

Computing exact Shapley values on graphs is #P-hard due to the exponential number of possible node coalitions (2^N). Practical implementations rely on sampling approximations like Monte Carlo permutation sampling.

• Approximation Error: The trade-off between computational budget and explanation accuracy is a central design constraint.
• Graph-Specific Optimizations: Techniques like GraphSVX and localized subgraph sampling reduce the coalition space by exploiting graph locality, assuming distant nodes have negligible interaction.

An explainability method that uses Monte Carlo Tree Search (MCTS) to efficiently explore and identify the most critical subgraph structures for GNN predictions. It evaluates subgraph importance using Shapley values as the scoring function within the MCTS rollout phase. This approach captures higher-order interactions between nodes that single-node attribution methods miss.

A principle for learning explainable GNNs by compressing the input graph into a minimal subgraph that retains maximal mutual information about the label. It formalizes the trade-off between compression (discarding irrelevant structure) and prediction (preserving label-relevant information). This connects to Shapley values through the shared goal of identifying minimal sufficient explanations.

A quantitative evaluation score that measures how accurately an explanation subgraph reflects the true reasoning process of the GNN. It is typically assessed by the drop in prediction performance when the explanation is removed or masked. For Shapley-based explanations, faithfulness validates that nodes with high Shapley values are genuinely causal contributors rather than spurious correlates.

The minimal structural perturbations to a graph—such as removing specific edges or nodes—that would alter a GNN's prediction to a different outcome. While Shapley values assign positive contribution scores, counterfactual explanations identify the necessary conditions for a prediction. Together they provide both sufficiency and necessity perspectives on model decisions.