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

GNN explanations remain focused on nodes and edges, leaving intuitive graph substructures insufficiently addressed. SubgraphX searches connected subgraphs with Monte Carlo tree search and evaluates them using interaction-aware Shapley values, with experiments showing improved explanations at reasonable computational cost.

  • Problem

    Existing GNN explanation methods focus on node or edge importance and overlook graph substructures that are more intuitive and human-intelligible.

  • Method

    SubgraphX uses Monte Carlo tree search to explore connected subgraphs and Shapley values, approximated within the information aggregation range, to measure subgraph importance and interactions.

  • Results

    SubgraphX provides significantly improved explanations while keeping computations at a reasonable level.

  • Takeaways & Limitations

    SubgraphX explicitly identifies subgraphs as explanations for individual GNN predictions, making graph-model explanations more directly aligned with human-intelligible structures.

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

GNNs perform well across graph tasks but remain black boxes whose predictions lack explanations. SubgraphX addresses this gap by directly identifying important subgraphs with efficient search and interaction-aware importance scores, achieving better explanations at reasonable computational cost.

  • GNNs support graph classification, node classification, link prediction, and graph generation, but their predictions remain difficult to explain.
  • Graph explainability is less explored than image and text explainability because graphs contain structural information that is not grid-like.
  • Existing GNN explanation methods focus on nodes, edges, or node features rather than directly identifying substructures.
  • SubgraphX uses Monte Carlo tree search to efficiently explore subgraphs and Shapley values to measure their importance while capturing interactions among graph structures.The method also proposes efficient Shapley-value approximation schemes for graph data.
  • SubgraphX provides better explanations for a variety of GNN models while maintaining a reasonable computational cost.

2. Related Work

GNN explanation research builds on information aggregation and several node-, edge-, and feature-level methods. These approaches include gradient, decomposition, and perturbation techniques, but do not directly provide reliable input-dependent subgraph explanations.

  • GNNs generally generate node representations by aggregating and combining features from neighboring nodes.For GCNs, this aggregation uses normalized adjacency information, learnable transformations, and nonlinear activation.
  • Existing approaches do not directly provide input-dependent subgraph explanations, and combining important nodes or edges does not guarantee connected or interaction-aware subgraphs.
  • Gradient- and feature-based methods estimate node, edge, or node-feature importance but cannot incorporate graph-specific properties.
  • Decomposition methods explain predictions by assigning layer-wise backpropagated terms to graph nodes or edges.
  • Perturbation-based methods identify influential features by monitoring prediction changes after modifying inputs; GNNExplainer uses soft masks for edges and node features.

3. The Proposed SubgraphX

SubgraphX explains GNN predictions by directly searching for important connected subgraphs, using Monte Carlo tree search and Shapley values to evaluate their contributions and interactions. It supports black-box GNNs across graph, node, and link prediction settings while using efficient graph-aware computations.

  • 3.1. From Node and Edge to Subgraph Explanations: SubgraphX directly identifies connected subgraphs as input-dependent explanations, addressing the limitations of node- and edge-level methods.The method argues that connected subgraphs are more human-intelligible and avoids relying on disconnected collections of important nodes or edges.
  • 3.2. Explaining GNNs with Subgraphs: The explanation is selected by maximizing a subgraph score under an upper bound on subgraph size, avoiding brute-force enumeration of all connected subgraphs.The scoring function can in principle be replaced, although SubgraphX uses Shapley values with MCTS.
  • 3. The Proposed SubgraphX: Monte Carlo tree search explores candidate subgraphs by pruning nodes from a root graph and selecting paths toward leaves constrained by a size bound.Each search-tree node represents a connected subgraph, while edges represent node-pruning actions; selected paths are evaluated and updated iteratively.
  • 3.4. A Game-Theoretical Scoring Function: Shapley values serve as the scoring function, assigning subgraph importance from GNN prediction gains while capturing interactions among graph structures.The method treats the target subgraph as one player and computes its marginalized contribution across coalitions.
  • 3.5. Graph Inspired Efficient Computations: Graph-aware Shapley approximation restricts interactions to nodes within the GNN’s L-hop neighborhood and estimates values through sampled coalitions.For each sampled coalition, zero-padding perturbs node features outside the coalition or target subgraph rather than removing nodes from the input graph.
  • 3.6. SubgraphX for Generic Graph Tasks: SubgraphX generalizes to node classification and link prediction by using the relevant L-hop computation graph as the search root and preserving target nodes during perturbation.The explanation stage treats GNNs as black boxes and requires only model inputs and outputs, allowing use with multiple GNN families.

4. Experimental Studies

Experiments across graph and node classification tasks show that SubgraphX identifies concise, connected, and human-intelligible subgraph explanations across datasets and GNN models. Quantitative studies report stronger Fidelity with reasonable computational cost, including an 11× speedup over a non-approximated Shapley baseline.

  • Datasets and Experimental Settings: Experiments cover five datasets spanning synthetic, biological, and text data, with graph and node classification using GCN, GAT, and GIN models.SubgraphX is compared with MCTS GNN, GNNExplainer, and PGExplainer under a shared limit on explanation size.
  • Graph Classification Explanations: On BA-2Motifs, SubgraphX precisely identifies the house-like motif for correct predictions and the five-node cycle as the important structure behind an incorrect prediction.Its explanations are connected subgraphs, whereas PGExplainer and GNNExplainer identify discrete edges.
  • Graph Classification Explanations: On MUTAG, SubgraphX precisely identifies carbon rings in two mutagenic predictions, while MCTS GNN includes additional edges and the other baselines contain discrete edges.The evaluation uses chemical knowledge that carbon rings and NO2 groups tend to be mutagenic.
  • Graph Classification Explanations: On Graph-SST2, SubgraphX finds semantically positive phrases for correct and incorrect predictions and tends to include fewer neural words than competing methods.For the incorrect positive prediction, all methods except PGExplainer identify the positive phrase “truly going to inspire” as important.
  • Node Classification Explanations: On BA-Shape, SubgraphX precisely targets the motifs supporting correctly classified target nodes, whereas other methods cover only partial motifs.The dataset’s motifs provide rules for labeling different nodes, enabling consistency checks for the explanations.
  • Quantitative and Efficiency Studies: 11 times faster than MCTS† with similar Fidelity scores, while SubgraphX’s Fidelity scores are 300% higher than GNNExplainer and PGExplainer despite being slower.The study compares Fidelity at similar Sparsity levels and attributes the speedup to the proposed approximation schemes.

5. Conclusions

SubgraphX explains GNN predictions by explicitly identifying important subgraphs, combining Monte Carlo tree search with Shapley-value importance estimates and efficient approximations. Experiments report higher-quality, more human-intelligible explanations with acceptable time complexity.

  • SubgraphX identifies important subgraphs explicitly to explain GNN predictions.
  • Monte Carlo tree search efficiently explores candidate subgraphs for explanation.
  • Shapley values measure subgraph importance while accounting for interactions among graph structures.
  • Approximation schemes compute Shapley values using interactions within the information aggregation range.
  • Experiments show higher-quality and more human-intelligible explanations with acceptable time complexity.

A.1. Datasets and GNN Models

The evaluation uses multiple GNN variants trained on graph datasets to obtain reasonable predictive performance before explanation analysis. The reported MUTAG GCN model has three GCN layers and 0.92 testing accuracy.

  • Different GNN variants are trained on the datasets and then explained.The models are trained to obtain reasonable performance.
  • The MUTAG GCN model uses three GCN layers with 7-dimensional input features and 128-dimensional outputs per layer.It uses max-pooling, ReLU activation, 2,000 training epochs, and a 0.005 learning rate.
  • 0.92 testing accuracy is reported for the MUTAG GCN model.

A.3. Evaluation Metrics

The evaluation measures explanation quality by removing important information and observing prediction changes, while also measuring how many nodes explanations select. Good explanations should be sparse yet cause substantial prediction drops.

  • Fidelity measures the average change in predicted-class probability after important input features are removed.Important nodes are occluded with zero features to avoid substantially changing graph structure.
  • Sparsity measures the fraction of graph nodes selected in an explanation.The explanation mask identifies important nodes with binary values.
  • Good explanations select fewer nodes while producing significant prediction drops.

B. Explanations for Graph Classification Models

Visualizations compare SubgraphX with edge-focused explanation methods on BBBP, MUTAG, and Graph-SST2. SubgraphX produces human-intelligible subgraphs and identifies a semantically relevant phrase in a correctly classified example.

  • SubgraphX provides more human-intelligible subgraph explanations than PGExplainer and GNNExplainer on BBBP and MUTAG.The comparison methods focus on discrete edges.
  • On Graph-SST2, SubgraphX identifies “missing is its spirit” as important for a correctly predicted negative sentence.The passage characterizes “missing” as the keyword for the sentence’s negative meaning.
  • Other methods highlight “violates” and “none of this,” which are described as less related to the negative meaning.

C. Explanations for Node Classification Models

SubgraphX explanations for BA-Shape node classification focus on whole motifs for correct predictions and partial motifs for incorrect predictions. The section also reports explanation visualizations for BBBP, MUTAG, and Grpah-SST2.

  • BA-Shape: SubgraphX focuses on whole motifs for correct BA-Shape node predictions.The target node is shown at larger size in the BA-Shape visualization.
  • BA-Shape: SubgraphX captures partial motifs for incorrect BA-Shape node predictions.The passage states that partial motifs are insufficient for correct predictions.
  • Molecular datasets: The section presents explanation results for the BBBP and MUTAG datasets.The figure caption identifies Carbon, Oxygen, Nitrogen, and Chlorine with different colors.
  • Grpah-SST2: The section also presents explanation results for the Grpah-SST2 dataset.
Loading 2102.05152v2…