Graph Neural Networks (GNNs) owe their success to their ability to combine node features with structural topology through message passing. In a single layer, a node aggregates information from its immediate neighbors; over multiple layers, this information propagates across entire neighborhoods. However, this recursive mixing makes GNNs notorious black boxes. When a model flags a financial transaction as fraudulent or a molecule as toxic, it is difficult to isolate why. Did the prediction trigger because of the node's individual attributes, the features of its neighbors, or the specific geometry of their connections?
To deploy GNNs safely in high-stakes domains like healthcare, finance, and cybersecurity, researchers have developed frameworks to interpret their internal logic. These approaches generally fall into two categories: post-hoc explainers, which probe a trained model, and self-explainable models, which are interpretable by design.
Subgraph and Feature Attribution
The most intuitive way to explain a GNN prediction is to identify a compact substructure—a subset of nodes, edges, or node features—that is primarily responsible for the output.
A classic approach to this is Layer-wise Relevance Propagation (LRP), which backpropagates a model's output decision through its layers to assign importance scores to input elements. However, computing higher-order subgraph attributions traditionally suffers from exponential computational complexity. To resolve this, Ping Xiong developed sGNN-LRP, a framework that reframes the relevance propagation steps as a message-passing problem itself. Because the explanation process mirrors the linear-time structure of the GNN's forward pass, this method reduces the computational overhead from exponential to linear time, enabling rapid subgraph attribution.
While identifying arbitrary subgraphs is computationally efficient, the resulting explanations can sometimes be difficult for humans to interpret. To bridge this gap, Gao et al. proposed MotifExplainer. Instead of scoring isolated edges, this method extracts "motifs"—recurrent, statistically significant substructures like carbon rings in chemistry or dense cliques in social networks. By anchoring explanations to these higher-level concepts, the output aligns more closely with human domain expertise.
Other approaches look at explanations across multiple granularities. Xiang Wang introduced ReFine, a multi-grained explainability framework. It uses a pre-training phase to learn global, class-level structural patterns, and then fine-tunes these insights to provide precise, instance-specific local explanations.
Counterfactuals and Local Surrogates
Another paradigm shifts the question from "What did the model look at?" to "What would change the model's mind?" This is the essence of counterfactual explanations.
Lucic et al. developed CF-GNNExplainer, a framework that searches for the minimal perturbation—specifically, the smallest number of edge deletions—needed to flip a GNN's prediction. If removing a single connection changes a "high-risk loan" prediction to "low-risk," that specific connection is highly actionable and explanatory.
[Original Graph] ---> GNN Prediction: Class A
|
(Prune minimal edges via CF-GNNExplainer)
v
[Counterfactual Graph] ---> GNN Prediction: Class B
Rather than perturbing the graph directly, some methods approximate the GNN's behavior locally. Farzaneh Heidari proposed Interpretable Local Surrogates (ILS), a model-agnostic approach. ILS samples the graph neighborhood around a target node and fits a simple, inherently transparent linear model to those samples. This provides a local explanation without requiring access to the complex, non-linear internal weights of the underlying GNN.
Alternatively, explanations can be framed through causality. Lin et al. introduced Gem, an explainability tool based on Granger causality. Instead of optimizing an optimization objective for every single target instance, the authors trained a generative model to quickly predict the most causal subgraphs, speeding up explanation generation by orders of magnitude.
The Reliability Crisis in GNN Explanations
As the number of GNN explanation techniques has grown, researchers have begun to rigorously evaluate whether these explainers are actually faithful to the underlying models.
Agarwal et al. conducted a systematic theoretical and empirical analysis of popular GNN explainers in Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods. They established mathematical upper bounds on how much these tools violate core properties like stability and faithfulness. Surprisingly, their empirical findings revealed that state-of-the-art explanation methods occasionally fail to outperform simple random baselines, highlighting a critical need for rigorous validation.
To address this evaluation challenge, Sanchez-Lengeling et al. designed a quantitative benchmarking framework in Evaluating Attribution for Graph Neural Networks. By constructing synthetic graph datasets with mathematically verifiable ground-truth reasons for their labels, they created a reliable sandbox to measure exactly how well different attribution methods isolate true predictive features.
Furthermore, explanations themselves can be fragile. Mohammadi et al. evaluated the robustness of graph counterfactual explanations under adversarial influence, noting that minor data perturbations or hyperparameter shifts can lead to wildly inconsistent explanations. To combat this uncertainty, Zhang et al. introduced ConfExplainer, which integrates a confidence scoring module with the Graph Information Bottleneck principle. By outputting a reliability metric alongside the explanation, it helps users determine when an explanation can be trusted and when it is uncertain.