Factorized Explainer for Graph Neural Networks

Rundong Huang, Farhad Shirani, Dongsheng Luo

Introduction

Graph Neural Networks (GNNs) have become the standard for modeling non-Euclidean data, yet their "black-box" nature remains a significant hurdle for deployment in high-stakes domains like medicine or autonomous driving. While several post-hoc explanation methods exist, they often fall into a mathematical trap known as "trivial solutions"—providing technically optimal but human-unusable explanations. This paper introduces K-FactExplainer, a novel framework designed to overcome these limitations by using a coordinated team of local explainers to identify complex, multi-part motifs within graphs.

The Problem: Trivial Solutions and the Locality Trap

Existing GNN explainers typically rely on the Graph Information Bottleneck (GIB) principle to find a "minimal and sufficient" subgraph that explains a prediction. However, the authors identify two critical flaws in this standard approach:

  1. The Signaling Issue: The original GIB objective allows for "trivial solutions" where an explainer can "cheat" by outputting a subgraph that merely signals the predicted label without being a meaningful structural component of the original graph.
  2. The Locality Trap: Most state-of-the-art explainers (e.g., PGExplainer) are inherently local, focusing on small node neighborhoods. In real-world scenarios, a graph's label may be determined by multiple motifs spread across the structure. Local explainers struggle to capture these disparate patterns simultaneously, leading to incomplete explanations.

The K-FactExplainer Framework

To address these issues, K-FactExplainer introduces a two-pronged solution involving a modified objective function and a factorized architecture.

Modified GIB Objective

The authors replace the standard mutual information term with a cross-entropy loss. This forces the explainer to find subgraphs that the GNN actually utilizes for its prediction, effectively closing the "signaling" loophole.

Factorized Architecture

Instead of a single global explainer, the model employs a "manager-specialist" hierarchy:

  • Local Experts ($\Psi_1 \dots \Psi_k$): A set of $k$ multi-layer perceptrons (MLPs) that act as specialists, identifying potential explanatory edges based on local node embeddings.
  • Global Selector ($\Psi_0$): A manager MLP that analyzes the entire graph embedding to determine the appropriate weight (trust level) for each local expert for a given input.
  • The "Patchwork" Effect: The final explanation is a weighted combination of these experts, allowing the model to "patch together" multiple motifs that may be geographically distant within the graph structure.
The K-FactExplainer architecture uses a Global Selector (Psi_0) to coordinate multiple Local Experts (Psi_1 to Psi_k) to generate a sampled explanatory graph.

Experimental Evaluation

The researchers evaluated K-FactExplainer on six widely-used GNN explainability benchmarks, including node classification (BA-Shapes, BA-Community, Tree-Circles, Tree-Grid) and graph classification (BA-2motifs, MUTAG). These datasets are ideal for evaluation because they contain "ground truth" motifs—specific shapes like "houses" or chemical groups like $NO_2$—that the explainer should ideally identify.

Key Results

K-FactExplainer consistently outperformed existing methods across all datasets in terms of AUC-ROC, which measures how accurately identified edges match ground truth motifs.

Comparison of K-FactExplainer against baseline methods across six benchmarks, showing superior AUC-ROC performance, particularly on complex multi-motif datasets.

Key findings from the results include:

  • Perfect Accuracy: On the BA-Shapes dataset, K-FactExplainer achieved a perfect 1.000 AUC.
  • Multi-Motif Mastery: On datasets where multiple patterns determine the label (BA-2motifs and MUTAG), K-FactExplainer showed significant gains over the previous leader, PGExplainer (e.g., 0.821 vs 0.566 on BA-2motifs).
  • Scalability: Performance generally improved as the number of experts ($k$) increased, confirming that the factorized approach successfully captures complex structural information that local explainers miss.

Conclusion and Future Work

K-FactExplainer demonstrates that the standard mathematical framework for GNN explanation is fundamentally prone to shortcuts. By modifying the GIB objective and introducing a factorized architecture, the authors provide a more robust way to recover the structural motifs GNNs use for decision-making. Future work may explore applying this factorized approach to dynamic, time-varying graphs or more complex tasks like link prediction.

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