PaperlayerView exact revision on arXiv

Source-linked AI summary

Explainability in Graph Neural Networks: A Taxonomic Survey

Hao Yuan, Haiyang Yu, Shurui Gui, Shuiwang Ji

arXiv:2012.15445v3cs.LGcs.AI

TL;DR

Deep models, including GNNs, lack unified explainability treatments and standardized evaluation resources despite their growing use. This survey supplies a taxonomy, systematic method analysis, datasets, metrics, an open-source library, and comparative experiments, concluding with a unified methodological treatment and standardized testbed for GNN explainability.

  • Problem

    GNN explainability lacks a unified treatment of methods and a standard benchmark or testbed for evaluation, despite growing graph-model research.

  • Method

    The survey taxonomizes and analyzes GNN explanation methods, summarizes datasets and metrics, builds three text-derived graph datasets, and provides implementations and experiments.

  • Results

    The work provides a unified methodological treatment of GNN explainability and a standardized testbed for evaluations.

  • Takeaways & Limitations

    The taxonomy and comparative analysis offer researchers high-level insights for choosing research directions and baselines.

  • Takeaways & Limitations

    Instance-level explanations require more human supervision, while model-level patterns may not be human-intelligible or exist in real-world data.

Abstract

from arXiv · show

Deep learning methods are achieving ever-increasing performance on many artificial intelligence tasks. A major limitation of deep models is that they are not amenable to interpretability. This limitation can be circumvented by developing post hoc techniques to explain the predictions, giving rise to the area of explainability. Recently, explainability of deep models on images and texts has achieved significant progress. In the area of graph data, graph neural networks (GNNs) and their explainability are experiencing rapid developments. However, there is neither a unified treatment of GNN explainability methods, nor a standard benchmark and testbed for evaluations. In this survey, we provide a unified and taxonomic view of current GNN explainability methods. Our unified and taxonomic treatments of this subject shed lights on the commonalities and differences of existing methods and set the stage for further methodological developments. To facilitate evaluations, we generate a set of benchmark graph datasets specifically for GNN explainability. We summarize current datasets and metrics for evaluating GNN explainability. Altogether, this work provides a unified methodological treatment of GNN explainability and a standardized testbed for evaluations.

1 INTRODUCTION

Deep models achieve strong performance but remain difficult to interpret, limiting trust in critical applications. This survey addresses the emerging need for systematic GNN explainability through a taxonomy, evaluation resources, datasets, implementations, and comparative experiments.

  • Deep models are often treated as black boxes because their underlying prediction mechanisms lack interpretability, limiting trust in applications involving fairness, privacy, and safety.
  • GNN explainability is increasingly important because graph data underpin tasks involving social networks, molecules, financial data, and other real-world structures.
  • The survey systematically reviews existing deep graph-model explanation techniques and proposes a taxonomy with key ideas and comparative analysis for each category.
  • It summarizes datasets and evaluation metrics, discusses their limitations, and recommends several metrics for GNN explanation tasks.
  • The authors build three publicly available human-understandable graph datasets from text and provide an open-source library containing methods, datasets, and metrics.
  • Experiments compare explanation techniques and provide insights for researchers about research directions and baseline selection.

2 THE CHALLENGES

Explaining GNNs is challenging because graphs encode discrete, non-grid-like topology and structurally meaningful subgraphs that are harder for people to understand than image or text inputs. These difficulties motivate standard datasets and evaluation metrics.

  • Graphs lack grid-like locality and have variable neighborhoods, while adjacency matrices encode topology with discrete values that hinder direct transfer of image explanation methods.
  • Graph explanations must capture structural information because graph labels and functionalities can depend on motifs or other substructures rather than individual nodes.
  • Complex graph domains such as molecules, social networks, and citation networks require domain knowledge, making their explanations difficult for humans to understand.
  • The proposed taxonomy organizes GNN explanation approaches into instance-level and model-level branches, with instance-level methods grouped by explanatory mechanism.

3 AN OVERVIEW OF THE TAXONOMY

The taxonomy distinguishes explanations tied to individual input graphs from explanations describing general model behavior. These views differ in interpretability and supervision requirements and can be combined to understand GNNs more fully.

  • Instance-level methods: Instance-level methods provide input-dependent explanations by identifying important features for each input graph.
  • Instance-level methods: Instance-level approaches are divided into gradients/features-based, perturbation-based, decomposition, and surrogate methods according to how importance scores are obtained.
  • Model-level methods: Model-level methods explain GNNs independently of specific inputs by providing high-level insights into general model behavior.
  • Comparison: Instance-level explanations are easier to understand because they use real inputs, whereas model-level graph patterns may not exist in the real world and require less human supervision.
  • Comparison: Combining instance-level and model-level explanations is presented as necessary for a fuller understanding of deep graph models.

4 INSTANCE-LEVEL EXPLANATIONS

Instance-level explanations identify important parts of a specific input graph using gradients, features, or related mechanisms. These methods differ in assumptions and applicability, with several approaches constrained by heuristic model or architecture requirements.

  • Instance-level explanation methods produce input-specific explanations, and this section examines each category’s motivations, methodologies, advantages, and limitations.
  • Gradients/features-based methods: Gradients/features-based methods approximate input importance using gradients or hidden feature-map values.
  • Gradients/features-based methods: SA uses squared gradients as importance scores for graph nodes, edges, or node features, but gradients measure sensitivity and can fail under saturation.
  • Gradients/features-based methods: Guided BP clips negative gradients to zero and uses only positive gradients for importance, while retaining SA’s limitations.
  • Gradients/features-based methods: CAM maps final-layer node features to input nodes using weighted feature-map sums, requiring global average pooling and a fully connected final classifier.
  • Gradients/features-based methods: CAM is limited by special GNN-structure requirements, heuristic assumptions about final embeddings, and direct applicability only to graph classification.
  • Gradients/features-based methods: Grad-CAM removes CAM’s global-average-pooling constraint by using averaged gradients of final node embeddings as feature-map weights.

4.2 Perturbation-Based Methods

Perturbation-based methods generate masks over nodes, edges, or node features, combine them with the input graph, and retain information that preserves the original prediction. They differ in mask type, generation strategy, and optimization procedure.

  • Unified pipeline: Perturbation methods generate node, edge, or node-feature masks and combine them with the input graph before evaluating prediction similarity.The general pipeline uses the trained GNN to assess whether the masked graph produces a prediction similar to the original.
  • Mask types: Soft masks enable back-propagation but may introduce evidence, whereas discrete masks avoid new values but require non-differentiable sampling solutions.Approximated discrete masks use reparameterization to retain differentiability while alleviating the introduced-evidence problem.
  • Representative methods: GNNExplainer optimizes soft edge and node-feature masks by maximizing mutual information between original and masked-graph predictions.The masks are initialized randomly, treated as trainable variables, and combined with the graph by element-wise multiplication.
  • Representative methods: PGExplainer learns approximated discrete edge masks with a parameterized predictor that scores edges from concatenated endpoint embeddings.The masks are sampled using the reparameterization trick and trained through a mutual-information objective.
  • Representative methods: GraphMask learns layer-specific edge importance, while Causal Screening and SubgraphX use greedy causal selection and Monte Carlo Tree Search, respectively.SubgraphX produces human-intelligible subgraphs but incurs higher computational cost; Causal Screening may also become trapped in local optima.
  • Representative methods: ZORRO greedily selects nodes or node features using fidelity scores, avoiding training and introduced evidence but risking local-optimal, instance-specific explanations.Its fidelity score measures how closely predictions match after selected inputs are fixed and the others are replaced with random noise.

4.3 Surrogate Methods

Surrogate methods explain individual GNN predictions by approximating local behavior with simple interpretable models. Their main differences concern how local data are sampled and which surrogate model is fitted.

  • General pipeline: Surrogate methods sample neighboring data and fit an interpretable model whose explanations are treated as explanations of the original GNN prediction.The approach assumes that relationships in the input’s neighboring region can be approximated locally.
  • Methods: GraphLime uses N-hop neighbors and their predictions as a local dataset, then fits an HSIC Lasso surrogate for node-feature importance.A reasonable N is the number of layers in the trained GNN.
  • Methods: RelEx samples connected subgraphs from a target node’s computational graph and feeds them to the trained GNN to obtain local predictions.Neighboring nodes are selected randomly in a breadth-first manner.
  • Methods: PGM-Explainer perturbs node features, selects dependent variables with the Grow-Shrink algorithm, and fits an interpretable Bayesian network.Its local dataset contains node variables rather than different neighboring graph samples, so it explains nodes but ignores graph edges.

4.4 Decomposition Methods

Decomposition methods explain GNN predictions by distributing prediction scores back to the input space layer by layer. Their central methodological difference is the score decomposition rule.

  • General pipeline: Decomposition methods treat the prediction as an initial target score and back-propagate its components to input features as importance scores.The methods directly study model parameters to reveal relationships between input features and output predictions.
  • Methods: LRP decomposes output prediction scores into node importance scores using rules based on hidden features and weights.The surveyed variants use the ϵ-stabilized rule or the z+-rule, while incorporating the adjacency matrix into the post-hoc explanation phase to preserve conservation.
  • Methods: Excitation BP decomposes target probabilities into conditional-probability terms under a law-of-total-probability formulation.Its computation is highly similar to the z+-rule in LRP.
  • Methods: GNN-LRP assigns importance to graph walks by approximating T-order Taylor terms, where T equals the number of trained GNN layers.Graph walks correspond to message flows during neighborhood aggregation, and the method records layer-to-layer distribution paths as walks.
  • Limitations: GNN-LRP has theoretical grounding but may produce inaccurate approximations and requires high computational complexity because it tracks individual walks.Its back-propagation procedure approximates the high-order derivatives rather than computing them directly.

5 MODEL-LEVEL EXPLANATIONS

Model-level explanations seek general graph patterns associated with GNN behavior rather than explanations for individual instances. XGNN addresses the challenge of discrete graph topology by generating graphs that maximize a target prediction.

  • Model-level explanations: Model-level methods study input graph patterns that produce a particular GNN behavior, such as maximizing a target prediction.Compared with instance-level methods, they aim to provide general insights and high-level understanding.
  • Motivation: Explaining GNNs at the model level is challenging because image-style input optimization cannot directly handle discrete graph topology.The paper describes model-level explanation as important but less studied, identifying XGNN as the only existing method known to the authors.
  • XGNN: XGNN trains a graph generator with reinforcement learning to add edges that produce graphs maximizing a target graph prediction.The generated graphs are intended to contain discriminative graph patterns and serve as global explanations.
  • XGNN: XGNN incorporates graph validity rules and graph-size limits to encourage explanations that are human-intelligible and succinct.For chemical data, an example rule limits an atom’s degree to its maximum chemical valency.

6 A COMPREHENSIVE COMPARATIVE ANALYSIS

The survey compares GNN explanation techniques across explanation type, learning, task, target, black-box access, computational flow, and graph-specific design. These dimensions expose trade-offs in interpretability, generalizability, model access, and topology awareness.

  • Type: Explanation techniques are classified by whether they provide instance-level or model-level explanations.Instance-level explanations depend on individual inputs, whereas model-level explanations describe broader model behavior.
  • Learning: Learning-based explainers may capture input–prediction relationships better, but added black boxes can reduce trustworthiness.Feature/gradient-based and decomposition methods do not use learning procedures.
  • Task: The survey evaluates method generalizability across node classification and graph classification tasks.These are the two tasks considered in the comparative analysis.
  • Target: Methods target node, edge, node-feature, or graph-walk importance, with graph structures receiving particular emphasis.For graph models, edges, walks, and subgraphs can be more informative than individual nodes.
  • Black-box: Black-box explainers use only trained GNN inputs and outputs, improving applicability when models are encapsulated or highly complex.Other techniques require access to model parameters or hidden representations.
  • Design and Flow: Graph-specific design matters because methods extended from images cannot account for topology and graph structure.The survey also distinguishes backward from forward computational flows when explaining trained GNNs.

7 EVALUATIONS

The evaluation framework combines human-understandable and synthetic graph datasets with fidelity, sparsity, and related metrics. It also identifies limitations of synthetic data and questions the fairness of some alternative metrics.

  • Datasets: Good evaluation datasets should be understandable to humans and contain human-verifiable rationales linking examples to labels.Synthetic motifs provide approximate explanation ground truths, but their simple graph–label relationships limit comprehensive evaluation.
  • Synthetic data: The survey includes BA-Shapes, a node-classification dataset combining a 300-node base graph with a house-like five-node motif.Node labels depend on whether nodes belong to the base graph or motif locations.
  • Sentiment graph data: Text sentiment graphs represent words as nodes and word relationships as directed edges, with edge labels ignored by most GNNs.Graph-SST2, Graph-SST5, and Graph-Twitter use BERT-derived 768-dimensional word embeddings as initial node features.
  • Molecular data: Molecular datasets require domain knowledge because atoms, chemical bonds, and functional groups determine interpretable graph properties.MUTAG, BBBP, and Tox21 are examples of molecular explanation datasets.
  • Metrics: Fidelity+ measures prediction change after removing important features, whereas Fidelity− measures prediction preservation when unimportant features are removed.Fidelity+ probability focuses on predicted-probability changes and is more sensitive than its accuracy counterpart.
  • Metric limitations: Contrastivity and Consistency are not recommended because their assumptions may be unfair across classes or competitive models.Different models can capture different relationships despite similar performance, especially on large and complex datasets.

8 EXPERIMENTAL STUDIES

Experiments compare GNN explanation methods across graph classification and node classification datasets using Fidelity, Accuracy, and Stability. SubgraphX is consistently strongest on Fidelity, while method performance varies with task, dataset type, and graph-specific design.

  • 8.1 Method Comparisons with Fidelity: The benchmark compares explanation methods on six datasets spanning graph and node classification, real-world and synthetic data.The datasets are Graph-SST2, Graph-SST5, Graph-Twitter, BBBP, BA-2Motifs, and BA-Shapes.
  • 8.1 Method Comparisons with Fidelity: SubgraphX consistently achieves the best Fidelity+ and Fidelity− results, indicating strong performance from subgraph-level explanations.Fidelity+ measures prediction-probability drop after removing important features; lower Fidelity− means fewer important features were removed.
  • 8.1 Method Comparisons with Fidelity: GNN-GI and GNN-LRP generally outperform GNNExplainer and PGExplainer on Fidelity, while the latter methods perform better on the BA-Shapes node-classification task.DeepLift and Grad-CAM are unstable across datasets, consistent with their migration from image-domain methods without graph-specific designs.
  • 8.2 Study of Fidelity: Fidelity scores generally exceed the random baseline, but DeepLift underperforms random on BA-Shapes and BA-Motifs.All methods outperform random on both Fidelity metrics for the proposed sentiment graph datasets, supporting their suitability for evaluation.
  • 8.3 Method Comparisons with Accuracy: Accuracy results favor GNN-LRP on BA-Shapes and GNNExplainer on BA-Community, whereas DeepLift performs worst on both datasets.SubgraphX is excluded because its subgraph explanations cannot be converted to soft edge masks, and synthetic ground truths are only approximations.
  • 8.4 Method Comparisons with Stability: Stability comparisons show that DeepLift can have the best Stability despite significantly worse Accuracy, indicating inconsistent explanatory quality.Stability measures the change in Accuracy after prediction-preserving perturbations of the input graph.
  • 8.5 Dataset Visualizations: Visualizations are easier for non-experts to understand on Graph-SST2 than on BBBP because words and sentiment phrases have clearer meanings than molecular patterns.The examples include the negative phrase “has nothing fresh” in Graph-SST2 and CN patterns in BBBP.

9 AN OPEN-SOURCE LIBRARY

The authors develop a publicly available open-source library for unified, reproducible study of GNN explainability. It supports reproducing existing methods, developing algorithms, and evaluating explanations.

  • Library purpose: The library is part of the DIG graph deep-learning library and is publicly available for GNN explainability research.It is designed as a turnkey library for graph deep-learning research.
  • Unified implementations: It includes implementations of GNNExplainer, PGExplainer, DeepLIFT, GNN-LRP, Grad-CAM, SubgraphX, and XGNN.These methods are implemented within a common library environment to support comparisons.
  • Unified implementations: A unified PyTorch 1.6.0 and PyTorch Geometric 1.6.1 environment enables easier and fairer comparisons across methods.The library also includes sentiment graph datasets and commonly used datasets such as MUTAG and BBBP.

10 CONCLUSION

The paper addresses the limited and fragmented study of GNN explainability through a systematic survey and unified taxonomy. It also analyzes methods, datasets, metrics, and introduces human-understandable graph datasets for evaluation.

  • Motivation: GNN explainability remains less explored than GNN modeling, with existing methods lacking a comprehensive study and analysis.The paper frames these methods as approaches for investigating the mechanisms of graph-model black boxes.
  • Contributions: The survey proposes a taxonomy, explains methods’ ideas and trade-offs, and analyzes datasets and metrics used for GNN explanation evaluation.Its treatment covers methodology, insights, advantages, drawbacks, and comparative analysis.
  • Contributions: Three graph datasets converted from text are designed to be human-understandable and directly usable for GNN explanation tasks.These datasets complement the survey’s evaluation framework.
Loading 2012.15445v3…