Factorized Explainer for Graph Neural Networks

Rundong Huang, Farhad Shirani, Dongsheng Luo

Abstract

Graph Neural Networks (GNNs) have received increasing attention due to their ability to learn from graph-structured data. To open the black-box of these deep learning models, post-hoc instance-level explanation methods have been proposed to understand GNN predictions. These methods seek to discover substructures that explain the prediction behavior of a trained GNN. In this paper, we show analytically that for a large class of explanation tasks, conventional approaches, which are based on the principle of graph information bottleneck (GIB), admit trivial solutions that do not align with the notion of explainability. Instead, we argue that a modified GIB principle may be used to avoid the aforementioned trivial solutions. We further introduce a novel factorized explanation model with theoretical performance guarantees. The modified GIB is used to analyze the structural properties of the proposed factorized explainer. We conduct extensive experiments on both synthetic and real-world datasets to validate the effectiveness of our proposed factorized explainer.

Introduction

Graph Neural Networks (GNNs) have become indispensable tools for analyzing graph-structured data in domains ranging from bioinformatics to social networks. However, their complex, non-linear architectures often function as "black boxes," making it difficult to interpret why a specific prediction was made. Post-hoc explanation methods aim to address this by identifying "minimal and sufficient" subgraphs—the core structural motifs—that drive the GNN's output.

Recent state-of-the-art explainers typically rely on the Graph Information Bottleneck (GIB) principle. However, this approach faces two critical challenges. First, the standard GIB objective often admits "trivial solutions" where the explainer identifies disconnected edges that signal the predicted label without capturing the actual structural logic of the GNN. Second, most existing explainers are "local," focusing on small neighborhoods. This makes them ineffective when a prediction depends on multiple distant motifs or when the GNN's internal message-passing process is lossy.

Methodology: The K-FactExplainer Framework

To overcome these limitations, we propose K-FactExplainer, a framework built on a modified information-theoretic objective and a novel factorized architecture.

1. Modified GIB Objective

To prevent the "signaling" problem inherent in standard GIB, we replace the mutual information term with a cross-entropy term. This modification forces the explainer to align its output directly with the original GNN's logic, ensuring that the generated explanation is truly faithful to the model's decision-making process rather than just a statistical shortcut.

2. Factorized Architecture

K-FactExplainer employs a "committee" of $k$ Multi-Layer Perceptrons (MLPs) to capture complex, multi-motif structures.

  • Local Experts ($\Psi_1$ to $\Psi_k$): These MLPs provide local perspectives on the graph's edges, identifying potential explanatory components.
  • Global Manager ($\Psi_0$): A separate MLP analyzes the entire graph embedding to determine the relative importance (weighting) of each local expert for a given input.
The K-FactExplainer architecture: A global MLP weights the outputs of multiple local explainers to produce a final sampled explanation graph.

By integrating these factorized outputs, the model can effectively "patch together" explanations that span large or disconnected parts of a graph, mitigating the issues caused by lossy aggregation in standard GNNs.

Experimental Evaluation

We evaluated K-FactExplainer against several baselines, including GNNExplainer and PGExplainer, across a variety of node and graph classification tasks.

Datasets

The evaluation included synthetic benchmarks (BA-Shapes, BA-Community, Tree-Circles, Tree-Grid) and real-world datasets (MUTAG). We also introduced a more challenging benchmark, BA-4motifs, specifically designed to test scenarios where a single label is associated with multiple distinct structural patterns.

Results and Discussion

K-FactExplainer consistently outperformed existing methods in terms of faithfulness and motif coverage.

Comparison of explanation faithfulness (AUC-ROC) across synthetic and real-world datasets.

Key findings include:

  • Superior Faithfulness: On the BA-Shapes dataset, K-FactExplainer achieved a perfect 1.000 AUC-ROC, significantly higher than traditional GIB-based methods.
  • Multi-Motif Handling: On the complex BA-4motifs task, K-FactExplainer achieved a Motif Coverage Rate of 0.712, nearly doubling the performance of PGExplainer (0.433).
  • Efficiency: Despite the multi-MLP architecture, K-FactExplainer maintains low inference times, making it practical for real-world use.

Conclusion

K-FactExplainer addresses fundamental flaws in GNN explainability by replacing the standard GIB objective and introducing a factorized architecture. By leveraging a committee of local experts guided by a global manager, it accurately identifies complex structural motifs that monolithic explainers miss. Future work will explore automated methods for determining the optimal number of factors ($k$) and extending the framework to handle more irregular graph structures.

Summary updated

Abstract

Graph Neural Networks (GNNs) have received increasing attention due to their ability to learn from graph-structured data. To open the black-box of these deep learning models, post-hoc instance-level explanation methods have been proposed to understand GNN predictions. These methods seek to discover substructures that explain the prediction behavior of a trained GNN. In this paper, we show analytically that for a large class of explanation tasks, conventional approaches, which are based on the principle of graph information bottleneck (GIB), admit trivial solutions that do not align with the notion of explainability. Instead, we argue that a modified GIB principle may be used to avoid the aforementioned trivial solutions. We further introduce a novel factorized explanation model with theoretical performance guarantees. The modified GIB is used to analyze the structural properties of the proposed factorized explainer. We conduct extensive experiments on both synthetic and real-world datasets to validate the effectiveness of our proposed factorized explainer.
BibTeX
@inproceedings{huang2024factorized,
  author = {Rundong Huang and Farhad Shirani and Dongsheng Luo},
  title = {{Factorized Explainer for Graph Neural Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i11.29157},
}
Figure