SubgraphX

Unlike gradient-based or perturbation methods that evaluate nodes in isolation, SubgraphX employs MCTS to perform a guided search over the subgraph space. The algorithm builds a search tree where each node represents a subgraph, using the Shapley value as the reward signal to direct the search toward highly explanatory structures. This balances exploration of diverse subgraphs with exploitation of promising candidates, avoiding the local optima that plague greedy masking approaches.

SubgraphX uses the graph Shapley value to quantify a subgraph's contribution to the prediction. This game-theoretic metric computes the marginal contribution of the subgraph across all possible coalitions of nodes, ensuring the explanation satisfies efficiency, symmetry, dummy, and additivity axioms. The Shapley value provides a theoretically principled alternative to heuristic importance scores, guaranteeing that the identified subgraph is both necessary and sufficient for the original prediction.

SubgraphX enforces a connectivity constraint during the MCTS rollout, ensuring that the final explanation is a single connected component rather than a scattered set of disconnected nodes. This produces explanations that correspond to meaningful structural motifs—such as functional groups in molecular graphs or cohesive communities in social networks—rather than arbitrary node collections that are difficult for humans to interpret.

The method supports explanations at multiple levels of granularity by controlling the MCTS search depth and the pruning threshold. At coarse levels, SubgraphX identifies large functional modules; at fine levels, it pinpoints specific critical edges and nodes. This hierarchical capability allows practitioners to zoom in from a high-level structural rationale down to the precise atomic interactions that flipped the model's decision.

SubgraphX operates as a post-hoc, model-agnostic explainer requiring only black-box access to the trained GNN's prediction function. It makes no assumptions about the internal architecture—whether GCN, GAT, GIN, or GraphSAGE—and does not require gradients or intermediate activations. This makes it applicable to proprietary or API-wrapped models where internal access is restricted.

Computing exact Shapley values over all possible subgraph coalitions is combinatorially intractable. SubgraphX addresses this through Monte Carlo sampling within the MCTS framework, approximating the Shapley value by sampling coalitions from the search tree. This approximation converges efficiently while maintaining the axiomatic guarantees of the Shapley framework, making the method practical for graphs with hundreds or thousands of nodes.

The core search algorithm powering SubgraphX. MCTS efficiently explores the vast space of possible subgraphs by iteratively performing four steps:

• Selection: Traversing the tree from the root to a leaf node using a search policy (like UCB1) that balances exploration and exploitation.
• Expansion: Adding one or more child nodes to the tree to represent new subgraph candidates.
• Simulation: Evaluating the chosen subgraph's importance using a Shapley value-based scoring function.
• Backpropagation: Updating the statistics of all traversed nodes with the simulation result. This guided search avoids exhaustive enumeration, making subgraph discovery tractable.

SubgraphX uses the Shapley value from cooperative game theory to assign a fair importance score to a candidate subgraph. The subgraph is treated as a coalition of nodes/edges, and its marginal contribution to the GNN's prediction is computed across all possible permutations of graph components. This ensures the explanation satisfies key axioms:

• Efficiency: The sum of contributions equals the total prediction.
• Symmetry: Identical components receive equal scores.
• Dummy: Irrelevant components receive zero score.
• Additivity: Scores are additive across games. This provides a theoretically grounded, unbiased measure of subgraph importance.

The process of systematically removing nodes or edges deemed irrelevant by an explainability metric to create a sparser, more interpretable subgraph that preserves the original prediction. In the context of SubgraphX, the output is a pruned subgraph—the minimal connected structure that is most influential for the GNN's decision. Pruning serves as both an explanation and a fidelity check: if removing the identified subgraph causes a significant prediction drop, it confirms the explanation's faithfulness.

A quantitative evaluation score that measures how accurately an explanation subgraph reflects the true reasoning process of the GNN. For SubgraphX, faithfulness is typically assessed by the drop in prediction probability when the identified critical subgraph is removed from the input. A high drop indicates the explanation captured genuinely causal structures. This is contrasted with the Fidelity Metric, which measures how well the original model's prediction is reproduced when using only the explanatory subgraph as input.

A self-explainable GNN framework where a generator module extracts a concise, causal subgraph (the rationale) and a predictor module makes a decision based solely on that rationale. Unlike post-hoc methods like SubgraphX, rationalization is built into the training process. The generator is optimized to find the minimal subgraph that maximizes mutual information with the label, often using the Graph Information Bottleneck principle to discard irrelevant structural noise.

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 SubgraphX identifies the subgraph most responsible for the actual prediction, counterfactual explanations answer "what would need to change for a different result?" This is crucial for algorithmic recourse in high-stakes applications like loan approvals or drug discovery, where understanding how to flip a decision is as important as understanding the decision itself.