GraphSVX

GraphSVX uniquely computes Shapley values jointly over nodes and features, providing a unified importance score. Unlike methods that explain structure or features in isolation, it captures the interaction effect where a node's importance is conditional on its features. This yields a holistic explanation that identifies both the critical nodes in the graph and the specific feature dimensions driving the prediction.

Exact Shapley value computation is exponential in complexity. GraphSVX employs Monte Carlo sampling over the power set of nodes and features to approximate values efficiently. It uses a weighted least squares optimization to estimate Shapley values from a manageable number of model evaluations, making it practical for large graphs without sacrificing the theoretical guarantees of the Shapley framework.

GraphSVX operates as a post-hoc, model-agnostic explainer. It treats the GNN as a black box, requiring only the ability to query predictions on masked input graphs. This means it can explain any GNN architecture—GCN, GAT, GraphSAGE, or GIN—without access to internal weights or gradients. The same explainer works across different models, simplifying the interpretability stack.

The framework supports explanations at multiple resolutions:

• Node-level: Which nodes contributed most to a specific node's prediction?
• Feature-level: Which input features were most influential?
• Global-level: Aggregate explanations to understand overall model behavior across the dataset. This flexibility allows engineers to debug individual predictions or audit systemic biases.

GraphSVX allows features to be grouped into semantically meaningful coalitions before computing Shapley values. For example, demographic features can be treated as a single coalition to measure their collective impact. This grouping mechanism is essential for algorithmic fairness auditing, enabling practitioners to quantify the influence of protected attributes on GNN predictions in social network or credit graph applications.

GraphSVX inherits the strong axiomatic properties of Shapley values from cooperative game theory:

• Efficiency: Importance scores sum to the prediction difference from the baseline.
• Symmetry: Identical contributions receive identical scores.
• Dummy: Irrelevant features or nodes receive zero importance.
• Additivity: Explanations are consistent across ensemble models. These guarantees make explanations legally defensible for regulated industries.

The game-theoretic foundation of GraphSVX. Shapley values compute each node or feature's marginal contribution to a GNN prediction by averaging its impact across all possible coalitions. GraphSVX extends this by jointly considering node coalitions and feature coalitions to produce a unified importance score.

• Satisfies efficiency, symmetry, and additivity axioms
• Guarantees fair credit distribution among graph components
• Computationally approximated via Monte Carlo sampling in GraphSVX

The primary evaluation criterion for GraphSVX explanations. Faithfulness measures how accurately an explanation reflects the GNN's true reasoning by computing the drop in prediction score when the most important nodes or features are removed.

• Higher drop = more faithful explanation
• GraphSVX optimizes for fidelity by selecting coalitions that preserve prediction behavior
• Contrasts with stability metrics that measure explanation consistency under input perturbations

A model-agnostic baseline that GraphSVX improves upon. GNNExplainer identifies a compact subgraph and feature subset maximizing mutual information with the prediction. Unlike GraphSVX, it does not provide Shapley-based importance scores or handle joint node-feature coalitions.

• Uses continuous relaxation of discrete masks
• Produces a single explanatory subgraph
• GraphSVX adds uncertainty quantification via Shapley value variance

The experimental methodology used to validate GraphSVX explanations. By systematically removing or masking the top-k nodes and features identified by the explainer, researchers measure the prediction degradation curve.

• Positive perturbation: removing important components causes sharp accuracy drop
• Negative perturbation: removing unimportant components has minimal effect
• GraphSVX demonstrates steeper degradation than baselines, indicating higher explanation quality

The minimal structural changes that would flip a GNN's prediction. While GraphSVX provides additive feature attribution, counterfactual methods identify edge deletions or node removals that produce a different outcome.

• Complements GraphSVX by offering actionable recourse
• CF-GNNExplainer finds the smallest edge set to delete
• Combined with Shapley values, enables both why this prediction and what would change it explanations

A theoretical principle underlying explanation quality. The GIB compresses an input graph into a minimal subgraph that retains maximal mutual information about the label, discarding irrelevant structure.

• GraphSVX approximates this by selecting high-contribution coalitions
• Related methods like GSAT and GraphMask learn stochastic attention to identify bottlenecks
• Provides theoretical justification for why smaller, faithful explanations are superior