PaperlayerView exact revision on arXiv

Source-linked AI summary

On Explainability of Graph Neural Networks via Subgraph Explorations

Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, Shuiwang Ji

arXiv:2102.05152v2cs.LGcs.AI

TL;DR

Existing GNN explainers focus on nodes and edges rather than directly explaining graph substructures. SubgraphX searches for important subgraphs using Monte Carlo tree search and Shapley values, and provides better explanations for a variety of GNN models at reasonable computational cost.

  • Problem

    Existing GNN explainers focus on nodes, edges, or features and do not directly provide input-specific subgraph explanations, although subgraphs are more human-intelligible.

    Source: §1 · p. 1, §3.1 · p. 3

  • Method

    SubgraphX uses Monte Carlo tree search to explore subgraphs, Shapley values to measure their importance and interactions, and efficient approximations for Shapley computations.

    Source: §1 · p. 1

  • Results

    SubgraphX provides better explanations for a variety of GNN models with reasonable computational cost.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Subgraphs are a more intuitive, human-intelligible unit for explaining GNN predictions.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

We consider the problem of explaining the predictions of graph neural networks (GNNs), which otherwise are considered as black boxes. Existing methods invariably focus on explaining the importance of graph nodes or edges but ignore the substructures of graphs, which are more intuitive and human-intelligible. In this work, we propose a novel method, known as SubgraphX, to explain GNNs by identifying important subgraphs. Given a trained GNN model and an input graph, our SubgraphX explains its predictions by efficiently exploring different subgraphs with Monte Carlo tree search. To make the tree search more effective, we propose to use Shapley values as a measure of subgraph importance, which can also capture the interactions among different subgraphs. To expedite computations, we propose efficient approximation schemes to compute Shapley values for graph data. Our work represents the first attempt to explain GNNs via identifying subgraphs explicitly and directly. Experimental results show that our SubgraphX achieves significantly improved explanations, while keeping computations at a reasonable level.

1. Introduction

SubgraphX explains GNN predictions by identifying important subgraphs, addressing the limits of existing explanations that focus on nodes, edges, or node features. Its approach combines Monte Carlo tree search with Shapley-value importance estimates, and experiments report better explanations at reasonable computational cost.

1. Introduction

  • GNN predictions are treated as black boxes, limiting understanding and trust and impeding their use in critical areas.Graph structure also makes image- and text-explanation methods unsuitable for direct application to GNNs.Source: §1 · p. 1
  • Existing GNN explanation methods, including GNNExplainer (Ying et al., 2019), PGExplainer (Luo et al., 2020), and PGM-Explainer (Vu & Thai, 2020), focus on nodes, edges, or node features.They consider subgraphs only indirectly through regularization, while the paper argues subgraph-level explanations are more intuitive and useful.Source: §1 · p. 1
  • SubgraphX uses Monte Carlo tree search to explore subgraphs and Shapley values to measure their importance by capturing interactions among graph structures.Its efficient Shapley-value approximations consider interactions only within the information aggregation range.Source: §1 · p. 1
  • SubgraphX provides better explanations across a variety of GNN models at reasonable computational cost.The paper evaluates effectiveness and efficiency through qualitative and quantitative experiments.Source: §1 · p. 2

2. Related Work

GNNs learn node and graph representations by aggregating neighboring-node features, while prior GNN explainers largely focus on nodes, edges, or features rather than input-dependent subgraphs.

2.1. Graph Neural Networks

  • GCNs illustrate GNN information aggregation: each layer transforms node features by combining normalized neighbor features with learnable weights and a nonlinear activation.The formulation adds self-loops before degree normalization.Source: §2.1 · p. 2

2.2. Explainability in Graph Neural Networks

  • GNN explainability is less studied than image and text explainability, and existing methods do not provide input-dependent subgraph explanations.The literature is categorized into gradients/features-based, decomposition, surrogate, generation-based, and perturbation-based methods (Yuan et al., 2020c).Source: §2.2 · p. 2
  • Gradient/feature methods (Baldassarre & Azizpour, 2019) are simple and efficient but do not incorporate graph-specific properties; decomposition methods attribute prediction terms to nodes or edges.Decomposition examples include LRP (Schwarzenberg et al., 2019), Excitation BP, and GNN-LRP (Schnake et al., 2020); surrogate methods approximate local relationships (Huang et al., 2020; Vu & Thai, 2020), while XGNN generates graph patterns for high-level explanations (Yuan et al., 2020b).Source: §2.2 · p. 2
  • Perturbation explainers identify influential inputs by monitoring prediction changes: GNNExplainer (Ying et al., 2019) optimizes soft masks, while PGExplainer (Luo et al., 2020) predicts important edges and GraphMask (Schlichtkrull et al., 2021a) predicts droppable edges.PGExplainer uses approximated discrete masks and focuses on input-space edges; GraphMask examines edges at every GNN layer.Source: §2.2 · p. 2

3. The Proposed SubgraphX

SubgraphX explains GNN predictions by directly identifying important, connected subgraphs instead of inferring subgraphs from node or edge importance. It uses Monte Carlo tree search (MCTS) and Shapley values to explore subgraphs and account for interactions among graph structures.

3.1. From Node and Edge to Subgraph Explanations

  • SubgraphX argues that directly identifying subgraphs is more intuitive than node- or edge-level explanations, producing connected, human-intelligible explanations that can capture structural interactions.Prior methods may yield disconnected subgraphs through post-processing, and node or edge importance does not directly establish subgraph importance.Source: §3 · p. 2, §3.1 · p. 3

3.2. Explaining GNNs with Subgraphs

  • SubgraphX seeks the most important connected subgraph for a prediction, with a size bound for concise explanations, because exhaustive enumeration is intractable on complex, large graphs.The formal task is introduced for graph classification and restricts candidate explanations to connected subgraphs.Source: §3.2 · p. 3

3.3. Subgraph Exploration via MCTS

  • MCTS represents node-pruning operations as tree edges, tracks visit counts and rewards to guide exploration, and returns the highest-scoring subgraph among explored leaves.Search initially favors less-visited actions and later favors actions yielding higher rewards.Source: §3.3 · p. 4

3.4. A Game-Theoretical Scoring Function

  • Shapley values score subgraphs by their marginal contribution across coalitions, capturing interactions among graph structures that direct GNN prediction scores can miss.The method treats the GNN prediction as game gain and graph structures as players, with the target subgraph treated as one player.Source: §3.4 · p. 4

3.5. Graph Inspired Efficient Computations

  • SubgraphX approximates subgraph Shapley values by considering only L-hop neighbors, Monte Carlo sampling coalitions, and zero-padding node features rather than removing nodes.The zero-padding strategy preserves graph structure because graphs are sensitive to structural changes; Nmin sets MCTS's stopping condition, and internal-node subgraphs can be selected by size.Source: §3.5 · p. 5

3.6. SubgraphX for Generic Graph Tasks

  • SubgraphX extends to node classification and link prediction by searching the relevant L-hop computation graph, and treats GNNs as black boxes using only inputs and outputs.The approach is applicable to multiple GNN families, including GCNs, GATs, GINs, and Line-Graph NNs.Source: §3.6 · pp. 5–6

4. Experimental Studies

Across graph and node classification tasks, SubgraphX produces human-interpretable subgraph explanations; quantitative studies report stronger fidelity at similar sparsity, and efficiency and pruning studies reveal trade-offs in computation time and fidelity.

4.1. Datasets and Experimental Settings

  • Experiments evaluate SubgraphX on five datasets spanning graph and node classification, compare GCN, GAT, and GIN models against explanation baselines, and constrain explanation node counts equally across methods.The datasets include synthetic, biological, and text data; baselines are MCTS GNN, GNNExplainer, and PGExplainer.Source: §4.1 · p. 6

4.2. Explanations for Graph Classification Models

  • On BA-2Motifs, SubgraphX identifies the house motif in a correct prediction and the missed five-node cycle motif behind an incorrect prediction, yielding succinct connected explanations.The dataset’s motifs serve as approximations of explanation ground truth; PGExplainer and GNNExplainer identify discrete edges.Source: §4.2 · p. 7, Figure 3 · p. 7
  • On MUTAG, SubgraphX precisely identifies mutagenicity-associated carbon rings, while MCTS GNN includes extra edges and PGExplainer and GNNExplainer produce discrete edges.The examples are correct mutagenic predictions, and the explanations are assessed against chemical domain knowledge because ground-truth explanations are unavailable.Source: §4.2 · p. 7, Figure 4 · p. 7
  • On Graph-SST2, SubgraphX and MCTS GNN identify positive phrases, and SubgraphX tends to include fewer non-neural words; only PGExplainer fails to explain an incorrect positive prediction.For the correct positive prediction, SubgraphX and MCTS GNN identify “makes old story new”; for the incorrect positive prediction, other methods identify “truly going to inspire” as important.Source: Figure 2 · p. 7, §4.2 · p. 8

4.3. Explanations for Node Classification Models

  • On BA-Shape node classification, SubgraphX targets the motifs that explain correctly classified nodes, while other methods cover only partial motifs and include extraneous structures.The explanations are evaluated for consistency with the motif-based node-labeling rules.Source: §4.3 · p. 8, Figure 6 · p. 8

4.4. Quantitative Studies

  • In five of six experiments, SubgraphX explanations are more faithful at similar Sparsity levels, as measured by Fidelity.Figure 5 plots Fidelity against Sparsity; higher Sparsity indicates smaller explanations, which can have lower Fidelity.Source: §4.4 · pp. 8–9, Figure 5 · p. 8

4.5. Efficiency Studies

  • SubgraphX is 11 times faster than MCTS† with similar Fidelity, while its explanations’ Fidelity is 300% higher than GNNExplainer’s and PGExplainer’s.MCTS† samples coalition sets from the full player set rather than the reduced set; SubgraphX remains slower than GNNExplainer and PGExplainer, and PGExplainer also requires model training on the full dataset.Source: §4.5 · p. 9, Table 2 · p. 9

4.6. Study of Pruning Actions

  • High2low pruning is five times faster than Low2high but yields inferior Fidelity scores.SubgraphX uses High2low for BA-Shape with GCNs and Low2high for other models; both strategies restrict pruning to the first 12 nodes ordered by degree.Source: §4.6 · p. 9, Table 3 · p. 9

5. Conclusions

SubgraphX explains GNN predictions by explicitly identifying important subgraphs, which the paper presents as more human-intelligible building blocks of complex graphs. It explores subgraphs with Monte Carlo tree search, uses Shapley values to measure importance and interactions, and approximates them by considering interactions within the information aggregation range.

5. Conclusions

  • SubgraphX explicitly identifies important subgraphs to explain GNN predictions, addressing the lack of subgraph-based explanations in existing methods.The paper argues that subgraphs are building blocks of complex graphs and are more human-intelligible.Source: §5 · p. 9
  • Monte Carlo tree search efficiently explores different subgraphs, while Shapley values measure their importance by accounting for interactions among graph structures.Source: §5 · p. 9
  • Shapley-value computations are expedited with approximation schemes that consider interactions only within the information aggregation range.Source: §5 · p. 9
  • Experiments show SubgraphX produces higher-quality, more human-intelligible explanations while keeping time complexity acceptable.Source: §5 · p. 9

Appendix · A. Datasets and Experimental Settings · A.1. Datasets and GNN Models

The appendix describes GNN architectures and testing performance for six datasets; the models were trained to obtain reasonable performance and their predictions were explained.

A.1. Datasets and GNN Models

  • For MUTAG, explanations are studied across the whole dataset, while the other four datasets are explained on their testing sets.The GNN variants are fitted to the datasets and used to explain the trained models.Source: §A.1 · p. 13
  • 1.00 testing accuracy for MUTAG GINs and 0.92 for MUTAG GCNs; explanations cover the whole dataset for both models.Both use three layers, max pooling, ReLU, 2000 training epochs, and a 0.005 learning rate; the GIN uses a two-layer MLP for each layer’s feature transformations.Source: §A.1 · p. 13
  • 0.863 testing accuracy for BBBP GCNs, with explanations studied on the testing set.The model has three GCN layers, max pooling, ReLU, 800 training epochs, and a 0.005 learning rate; the data split is 80% training, 10% validation, and 10% testing.Source: §A.1 · p. 13
  • 0.881 testing accuracy for Graph-SST2 GATs, with explanations studied on the testing set.The model has three GAT layers with 10 heads and 10-dimensional features, 768 input features, max pooling, ReLU, dropout 0.6, 800 training epochs, and a 0.005 learning rate; it uses the original SST2 split.Source: §A.1 · p. 13
  • 0.99 testing accuracy for BA-2Motifs GCNs, with explanations studied on the testing set.The model has three 20-dimensional GCN layers, L2-normalized node features, average pooling, ReLU, 800 training epochs, and a 0.005 learning rate; the data split is 80% training, 10% validation, and 10% testing.Source: §A.1 · p. 13
  • 0.957 testing accuracy for BA-Shape GCNs, with explanations studied on the testing set.The model has three 20-dimensional GCN layers, L2-normalized node features, ReLU, 800 training epochs, and a 0.005 learning rate; the data split is 80% training, 10% validation, and 10% testing.Source: §A.1 · p. 13

A.2. Experimental Settings · A.3. Evaluation Metrics

The evaluation metrics represent explanations as node masks, measure prediction change after occluding important nodes, and quantify how many nodes are selected. Good explanations aim for high Fidelity and high Sparsity.

A.3. Evaluation Metrics

  • SubgraphX and MCTS-based explanations yield node masks directly, while GNNExplainer and PGExplainer edge masks are converted by selecting nodes connected to important edges.Source: §A.3 · p. 13
  • Fidelity measures the average change in the original class’s predicted probability after important nodes are occluded with zero features.The method zeroes node features rather than removing nodes, which would significantly affect graph structure.Source: §A.3 · pp. 13–14
  • Sparsity measures the fraction of graph nodes selected as important, with higher Sparsity and higher Fidelity described as desirable.Source: §A.3 · p. 14

B. Explanations for Graph Classification Models

SubgraphX provides human-intelligible subgraph explanations for graph-classification predictions, and its Graph-SST2 example highlights a phrase tied to the negative sentiment.

B. Explanations for Graph Classification Models

  • On BBBP and MUTAG, SubgraphX provides more human-intelligible subgraph explanations, while PGExplainer and GNNExplainer focus on discrete edges.The visualizations are reported in Figures 7 and 8.Source: B. Explanations for Graph… · p. 14
  • On Graph-SST2, SubgraphX provides reasonable explanations for the sentiment-model predictions.The results are shown in Figure 8.Source: B. Explanations for Graph… · p. 14
  • For a correctly predicted negative sentence, SubgraphX identifies “missing is its spirit” as important, whereas other methods highlight words or phrases less related to the negative meaning.The passage describes “missing” as the keyword for the sentence’s semantic meaning.Source: B. Explanations for Graph… · p. 14

C. Explanations for Node Classification Models

For BA-Shape node classification, SubgraphX highlights whole motifs in correct predictions and partial motifs in incorrect predictions.

C. Explanations for Node Classification Models

  • On BA-Shape, SubgraphX highlights whole motifs for correct predictions but only partial motifs for incorrect predictions, whose information is insufficient for correct predictions.Figure 9 shows the BA-Shape explanations, with the target node displayed larger.Source: C. Explanations for Node… · p. 14, Figure 9 · p. 17

Related papers

Loading 2102.05152v2…