Abstract
Graph Neural Networks (GNNs) leverage the structural properties of the graph to inform the architecture of the neural network, thus achieving improved accuracy in graph learning tasks. However, like many neural network models, GNNs face a significant challenge with interpretability. To mitigate this issue, recent works have developed post-hoc instance-level explanation methods that focus on identifying minimal and sufficient subgraphs which strongly influence GNN predictions. Approaches that build on the graph information bottleneck principle (GIB) to quantify minimality and sufficiency have received particular attention, and have been used in several state-of-the-art explanation mechanisms. This work identifies several fundamental issues in such quantifications, particularly a signaling issue in the sufficiency, and a redundancy issue in the minimality quantifications. These may lead to explanations that do not accurately reflect the rationale behind GNN decisions. To overcome these challenges, we propose a new objective function and explainer architecture, dubbed the SculptEdgeX. The SculptEdgeX framework assesses the sufficiency of an input subgraph by generating an in-distribution supergraph and evaluating its prediction accuracy when processed by the GNN. This involves an initial densification process that adds edges to the input graph, followed by a selective edge removal step — called edge sculpting — to produce an in-distribution supergraph. To ensure the in-distribution property, we pre-train a calibrator network that parametrizes the underlying distribution of a given graph, hence enabling us to compare the distribution parameters with those of the original input distribution. We validate our method through extensive experiments on both synthetic and real-world datasets, demonstrating the effectiveness of SculptEdgeX in producing informative explanations.
Introduction
Graph Neural Networks (GNNs) are powerful but notoriously "black-box" models. To trust them in sensitive areas like healthcare or finance, we need to know why they made a specific prediction. Most current methods try to find a minimal and sufficient subgraph—the smallest piece of the graph that leads to the same prediction.
Many state-of-the-art explainers rely on the Graph Information Bottleneck (GIB) principle. However, this paper identifies two major pitfalls in GIB:
- The Signaling Issue: An explainer might "cheat" by choosing a subgraph whose shape or size "signals" the label to the GNN, even if that subgraph isn't the actual reason for the prediction.
- The Redundancy Issue: GIB often fails to filter out "low-entropy" components—parts of the graph that appear in every instance (like a common molecular backbone) but don't actually contribute to the specific classification.
The SculptEdgeX Framework
To overcome these challenges, the authors propose SculptEdgeX, a novel framework that improves GNN explainability by fixing fundamental flaws in the GIB principle. By "sculpting" in-distribution supergraphs, the method provides more faithful explanations that avoid signaling shortcuts and redundant information. The framework operates in three main stages:
- Stage 1: The Calibrator Network: Before explaining anything, a calibrator is pre-trained using contrastive learning (InfoNCE). This network learns to distinguish "in-distribution" graphs from "out-of-distribution" (OOD) perturbations.
- Stage 2: Densification: To test if an explanation is truly sufficient, the system creates a "dense" version of the input graph by adding edges between 2-hop neighbors.
- Stage 3: Edge Sculpting: This is the core innovation. The system uses a differentiable mask to remove edges from the dense graph while keeping the explanation subgraph untouched. The goal is to "sculpt" a supergraph that is both in-distribution (verified by the calibrator) and leads to the same GNN prediction.
By ensuring the GNN is evaluated on in-distribution graphs, SculptEdgeX avoids the "distribution shift" problem that often leads to nonsensical explanations.
Experimental Evaluation
The authors evaluated SculptEdgeX on six widely recognized benchmarks, including synthetic datasets like BA-2Motifs and BA-HouseGrid, and real-world molecular datasets such as Mutag, Al-Carbonyl, Fl-Carbonyl, and Benzene.
Key Results
SculptEdgeX consistently outperformed baseline methods in terms of AUC-ROC for explanation faithfulness:
- Substantial Gains: On the Al-Carbonyl dataset, SculptEdgeX improved AUC-ROC by 29.4% and 20.8% over the best-performing baselines when using GNNExplainer and PGExplainer backbones, respectively.
- Visual Proof: t-SNE visualizations showed that the "sculpted" graphs were virtually indistinguishable from the original data distribution, whereas raw explanatory subgraphs were clearly OOD.
Conclusion
A major insight of this work is that GNNs behave unpredictably when fed isolated subgraphs because those subgraphs look nothing like the training data. By building a supergraph that "looks real," SculptEdgeX provides a much more honest assessment of the explanation's sufficiency. While the framework involves a more complex optimization process than simple masking, its ability to break signaling shortcuts and handle distribution shifts makes it a significant step forward in GNN interpretability.
Summary updated