Source-linked AI summary
GNNExplainer: Generating Explanations for Graph Neural Networks
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, Jure Leskovec
TL;DR
GNN predictions combine graph structure and node features but remain difficult to explain. GNNExplainer learns compact structural and feature explanations through mutual-information optimization, and experiments show improved explanation accuracy across synthetic and real-world graphs.
Problem
GNNs lack transparent, human-intelligible explanations despite their use of graph structure and node features in complex predictions.
Method
GNNExplainer identifies a compact explanatory subgraph and node-feature subset by maximizing mutual information with the GNN prediction.
Results
17.1% average improvement over alternative approaches shows stronger explanation accuracy across the evaluated settings.
Takeaways & Limitations
The method provides concise explanations for individual predictions and consistent explanations for sets of instances across graph-based tasks.
Takeaways & Limitations
The optimization lacks a valid convexity assumption and therefore relies on regularized minimization reaching a high-quality local minimum.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs.GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. However, incorporating both graph structure and feature information leads to complex models, and explaining predictions made by GNNs remains unsolved. Here we propose GNNExplainer, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task. Given an instance, GNNExplainer identifies a compact subgraph structure and a small subset of node features that have a crucial role in GNN's prediction. Further, GNNExplainer can generate consistent and concise explanations for an entire class of instances. We formulate GNNExplainer as an optimization task that maximizes the mutual information between a GNN's prediction and distribution of possible subgraph structures. Experiments on synthetic and real-world graphs show that our approach can identify important graph structures as well as node features, and outperforms baselines by 17.1% on average. GNNExplainer provides a variety of benefits, from the ability to visualize semantically relevant structures to interpretability, to giving insights into errors of faulty GNNs.
1 Introduction
GNNs model graph structure and node features effectively but remain difficult to explain, limiting transparency in important applications. GNNExplainer addresses this gap with compact, model-agnostic explanations that identify influential subgraphs and node features, including consistent explanations across instances.
- Motivation: GNNs combine relational graph information with node features, but their predictions lack human-intelligible explanations.This limits transparency despite their effectiveness on graph-based machine-learning tasks.
- Approach: GNNExplainer returns a small influential subgraph and subset of node features for predictions from any GNN and graph-based task.It supports node classification, link prediction, graph classification, and both single- and multi-instance explanations.
- Approach: GNNExplainer formulates explanation as mutual-information maximization while learning graph and feature masks to select important information.The graph mask selects an important subgraph, while the feature mask removes unimportant node features.
- Results: Synthetic and real-world experiments identify planted motifs and domain-specific structures, including NO2 groups, molecular rings, and Reddit star structures.The method produces consistent and concise explanations across graph-based machine-learning tasks.
2 Related work
Prior interpretability methods use surrogate models, feature-level analyses, or attention, but they do not adequately represent graph relations. GNN explanations therefore need to account jointly for relational structure and node features.
- Existing approaches: Interpretability methods for non-graph neural networks mainly use proxy models or identify important computational aspects such as features and contributions.These approaches include locally faithful approximations, feature gradients, backpropagated contributions, and counterfactual reasoning.
- Graph-specific gap: Graph explanations are difficult because predictions may depend on combinations of nodes and edge paths, including alternative paths that form cycles.Relational structure can determine whether an edge matters in context.
- Design requirement: The paper frames the missing capability as explanations that leverage rich relational information alongside node features.This requirement follows from the role of graph structure in graph machine learning.
- GNN-specific gap: Attention-based GNN methods can assign edge importance shared across node predictions, conflicting with cases where an edge matters for one node but not another.They may also be limited to particular architectures or omit joint consideration of graph structure and node features.
3 Formulating explanations for graph neural networks
GNNs generate predictions through message passing, neighborhood aggregation, and representation updates over a computation graph. GNNExplainer uses this computation graph to identify the structural pathways and feature dimensions most relevant to a prediction.
- 3 Formulating explanations for graph neural networks: A graph G contains edges E, nodes V, and d-dimensional node features X, while a trained GNN Φ predicts node labels after optimization on training nodes.The formal setup focuses on node classification while noting other tasks are addressed later.
- 3.1 Background on graph neural networks: Each GNN layer computes neural messages between node pairs using their previous-layer representations and their relation.The message function is denoted MSG.
- 3.1 Background on graph neural networks: The model aggregates messages from each node’s neighborhood and transforms the aggregate with an update operation to obtain the next representation.Neighborhood definitions depend on the particular GNN variant.
- 3.1 Background on graph neural networks: After L computation layers, node vi’s final embedding is zi = hL_i, and GNNExplainer applies to models expressible through MSG, AGG, and UPDATE computations.This formulation defines the class of GNNs supported by the approach.
- 3.2 GNNEXPLAINER: Problem formulation: The computation graph Gc(v) fully determines the information used to predict at node v, including its structural adjacency and associated features.The model represents prediction behavior as a conditional distribution PΦ(Y | Gc, Xc).
- 3.2 GNNEXPLAINER: Problem formulation: The prediction is determined by Φ, computation-graph structure Gc(v), and node features Xc(v), so explanations can focus on these inputs.GNNExplainer represents an explanation using a subgraph GS and associated features.
- 3.2 GNNEXPLAINER: Problem formulation: The feature mask selects a small subset of node-feature dimensions associated with the explanatory subgraph while masking unimportant features.This jointly captures structural and feature information relevant to the prediction.
4 GNNEXPLAINER
GNNExplainer identifies influential subgraphs and node features by optimizing mutual information with GNN predictions, using masks, sparsity constraints, and regularization. The framework extends across prediction tasks and supports single-instance and class-level explanations.
- Single-instance explanations: GNNExplainer identifies a prediction-relevant subgraph and associated node features by maximizing mutual information with the GNN’s prediction.For node v, the explanation limits the computation graph and features to those most influential for the predicted label.
- Single-instance explanations: The explanation subgraph minimizes prediction uncertainty and is constrained to at most K_M nodes, favoring a compact set of informative edges.With a fixed trained GNN, maximizing mutual information is equivalent to minimizing conditional entropy; the size constraint denoises the computation graph.
- Optimization: The optimization is non-convex because neural networks violate the convexity assumption, yet regularized minimization often reaches local minima yielding high-quality explanations.A mean-field variational approximation and discreteness regularizer are used to make estimation tractable and obtain good local minima empirically.
- Objective variants: The objective can be changed from conditional entropy to cross entropy to explain why a model predicts a class or how to obtain a desired class label.The predicted class is used for “why” queries, while the ground-truth class can answer “how to make” queries.
- Joint structural and feature information: GNNExplainer jointly learns structural and feature masks, selecting at most K_F feature dimensions while using regularization to encourage discrete explanations.A binary selector F masks node features, and entropy regularization promotes discrete structural and feature masks.
- Model extensions: GNNExplainer applies without changing its optimization algorithm to node classification, link prediction, and graph classification, while graph-level explanations may be disconnected.For link prediction it learns masks for both endpoints; for graph classification, aggregation can prevent the explanation from being a connected subgraph.
5 Experiments
Experiments evaluate GNNEXPLAINER on synthetic node-classification and real-world graph-classification datasets, measuring whether it identifies explanatory structures and features. It outperforms alternative approaches and produces domain-relevant explanations across these settings.
- Datasets: The evaluation covers four synthetic node-classification datasets and two graph-classification datasets, MUTAG and REDDIT-BINARY.Synthetic datasets include BA-SHAPES, BA-COMMUNITY, TREE-CYCLES, and TREE-GRID.
- Feature explanations: GNNEXPLAINER identifies relevant node features in MUTAG and BA-COMMUNITY, whereas baseline methods fail or assign importance to irrelevant dimensions.The method highlights C, O, H, and N atoms in MUTAG and the feature relevant to a node’s structural role in BA-COMMUNITY.
- Quantitative results: 17.1% average improvement over alternative approaches, with up to 43.0% higher accuracy on TREE-GRID.The method scores highly on edges belonging to ground-truth explanations, supporting its explanation-accuracy results.
- Qualitative explanations: GNNEXPLAINER correctly identifies house, cycle, and tree motifs that explain node labels in topology-based synthetic tasks.These motifs are identified by GNNEXPLAINER but not by the baseline methods in the cited qualitative analysis.
- Real-world graph explanations: For MUTAG, GNNEXPLAINER identifies the carbon ring and NH2 and NO2 chemical groups associated with mutagenicity.For REDDIT-BINARY, it highlights high-degree expert nodes in question-answer graphs and tree-like discussion patterns.
- Additional evaluation: The experiments also include multi-instance explanations using graph prototypes, with further details provided in the Appendix.
6 Conclusion
The conclusion presents GNNEXPLAINER as a model-agnostic method for explaining GNN predictions without modifying or retraining the underlying model. It uses graph structure and node features to identify important pathways and support interpretation and debugging.
- Contribution: GNNEXPLAINER explains predictions from any GNN on any graph-based machine-learning task without modifying or retraining the underlying architecture.
- Mechanism: The method leverages recursive neighborhood aggregation to identify important graph pathways and relevant node-feature information passed along them.
- Applications: GNNEXPLAINER provides an interface for interpreting GNN predictions, debugging models, and identifying systematic patterns of mistakes.
A Multi-instance explanations
Multi-instance GNNExplainer aligns explanations within a class to reveal shared structural patterns and compare individual explanations with a class prototype.
- It extends single-instance explanations into global class explanations by relating node-specific important structures to a prototypical class structure.
- A reference node is selected as the class prototype by choosing the embedding closest to the class mean or matching prior structural knowledge.
- Relaxed alignment matches each class member’s computation subgraph to the reference using adjacency and feature similarity.
- The prototype is the median of aligned adjacency matrices, enabling inspection of shared class patterns and comparison with an individual explanation.
B Experiments on multi-instance explanations and prototypes
Multi-instance explanations emphasize correlations across related instances, especially shared characteristics among members of the same class.
- Class-level explanations can highlight shared functional groups, such as NO2 in mutagenic compounds.
C Further implementation details
The experiments train GNNs and explanation methods with Adam using fixed learning-rate, epoch, and data-split settings.
- Adam trains both GNNs and explanation methods, with GNNs trained for 1000 epochs at learning rate 0.001.GNN accuracy reaches at least 85% on graph-classification datasets and 95% on node-classification datasets.
- GNNEXPLAINER uses the same optimizer and learning rate but trains for 100–300 epochs on a local computation graph.
- All datasets use an 80/10/10% train/validation/test split.