Abstract
Graph Neural Networks (GNNs) have become essential for processing relational data, yet their "black box" nature limits their deployment in sensitive domains. We present GraphSVX, a post-hoc, model-agnostic explanation method that provides theoretically grounded interpretations of GNN predictions. By extending Shapley values from cooperative game theory to the graph domain, GraphSVX decomposes predictions into "fair" contributions from both node features and graph structure. Our evaluation demonstrates that GraphSVX achieves state-of-the-art accuracy on synthetic benchmarks and exhibits superior robustness to noise compared to existing explainers.
Introduction
As GNNs are increasingly deployed in high-stakes areas like healthcare and law enforcement, the need for interpretability has transitioned from a luxury to a requirement. While models like GNNExplainer and PGExplainer have made strides, they often lack theoretical grounding, treat features and structure in isolation, or produce scores that are difficult to interpret. GraphSVX addresses these gaps by leveraging the Shapley value—the gold standard for fair credit assignment—to provide a unified and mathematically rigorous explanation framework.
The Unified Framework and GraphSVX
The authors propose a unified framework that encapsulates most existing GNN explainers into a three-stage pipeline: Mask (generating perturbations), Gen (constructing a new graph), and Expl (generating the final explanation).
GraphSVX fits into this framework by employing a surrogate model approach to approximate Shapley values efficiently:
- Perturbation (Mask): It generates "coalitions" by randomly masking node features and neighboring nodes. A "SmarterSeparate" generator prioritizes high-impact coalitions to maintain efficiency.
- Surrogate Model (Gen/Expl): It trains a Weighted Linear Regression (WLR) model on these perturbations. The weights are derived from a specific kernel ensuring that the resulting coefficients approximate the Shapley values of the features and neighbors.
- Capturing Indirect Effects: To account for GNN message passing, GraphSVX uses path-preserving logic (e.g., Dijkstra’s algorithm) to ensure that the influence of distant nodes is captured correctly within the coalitions.
Experimental Evaluation
GraphSVX was evaluated against synthetic benchmarks (BA-Shapes, Tree-Cycles) and real-world datasets (MUTAG, Cora, PubMed).
Key Results
- Accuracy: GraphSVX achieved near-perfect accuracy on synthetic datasets with known ground-truth motifs, reaching scores of 0.99 on BA-Shapes and 0.97 on Tree-Cycles.
- Robustness: In noise-injection tests on citation networks, GraphSVX successfully ignored "noisy" (irrelevant) features and nodes, whereas baseline explainers often incorrectly identified them as important.
- Fairness: By satisfying core game-theoretic axioms like Efficiency and Dummy, GraphSVX ensures that contributions sum to the total prediction and that useless features receive zero credit.
Conclusion
GraphSVX represents a significant step toward transparent GNNs by providing a theoretically sound method for "fair" credit attribution. While the computational cost of local explanations remains a challenge for massive-scale graphs, its ability to unify feature and structural importance while maintaining robustness makes it a powerful tool for trustworthy AI in relational data domains.
Summary updated