Abstract
Explainability in Graph Neural Networks (GNNs) is crucial for high-stakes applications, yet verifying the reliability of relational explanations remains a significant challenge. This paper introduces a novel probabilistic framework that quantifies the uncertainty of GNN explanations. By generating symmetric counterfactual graphs through Boolean Matrix Factorization and learning a factor graph over the resulting explanations, the approach provides a statistically rigorous method to assess explanation quality. Experimental results on synthetic and real-world datasets show that this approach outperforms traditional importance scores, particularly in complex relational contexts.
Introduction
As Graph Neural Networks (GNNs) are increasingly deployed in domains like healthcare and social network analysis, the demand for Explainable AI (XAI) has grown. Tools such as GNNExplainer aim to identify influential subgraphs—specific sets of nodes and edges—that drive a model's prediction. However, verifying these relational explanations is difficult because graphs are abstract and complex, often requiring domain expertise that does not scale. Currently, there is no robust, automated way to determine if a GNN's explanation is truly "certain" or merely a result of noise.
Methodology
The proposed pipeline estimates uncertainty in explanations through a three-stage likelihood-based approach:
1. Generating Symmetric Counterfactuals
To understand explainer behavior, the authors generate "what-if" scenarios using Boolean Matrix Factorization (BMF). BMF creates low-rank approximations of the original graph, introducing symmetries that represent "likely" counterfactual versions of the data while maintaining core relational structures.
2. Learning a Factor Graph
The system runs GNNExplainer on these symmetric variants to collect Counterfactual Relational Explanations (CREs). These CREs are then used to model the distribution of explanations using a Factor Graph. In this Probabilistic Graphical Model (PGM), factor nodes represent logical relationships (conjunctions) between entities and the target prediction.
3. Uncertainty Quantification via Belief Propagation
The factor graph is calibrated using Belief Propagation (BP). To evaluate a specific explanation from the original graph, it is injected into the calibrated model as new evidence. The reduction in uncertainty—measured by the change in joint probability distributions—quantifies the true significance of that explanation.
Experimental Evaluation
The approach was evaluated on both synthetic and real-world datasets:
- Synthetic Motifs:
BAShapes,BACommunity,TreeGrids, andTreeCycles, where ground-truth motifs are known. - Real-world Networks:
Cora,Citeseer, andWebKBcitation and web networks, representing noisy, complex relational data.
Key Results
- Superior Reliability: The BP-based uncertainty measure consistently outperformed GNNExplainer’s internal Importance Scores (IS), particularly in the
BAShapesandTreeCyclebenchmarks. - Handling Complexity: The performance gap widened as graph structures became more intricate (e.g., in
TreeGrid), suggesting the probabilistic approach is better suited for complex data. - Statistical Significance: Using McNemar’s statistical test, the authors demonstrated that removing edges identified as "certain" by their method had a significantly greater impact on model predictions than removing edges based on standard scores.
Discussion and Future Work
A key insight of this work is using symmetry as a proxy for likelihood, allowing the model to learn a distribution over plausible alternative explanations rather than relying on raw importance scores. However, the method's effectiveness is tied to the underlying GNN's accuracy; on datasets like WebKB where the GCN performed poorly, the verification was less reliable. Additionally, the computational overhead of Belief Propagation is higher than simple gradient-based methods. Future research will explore integrating this verification with user feedback to allow human experts to interactively refine explanations based on uncertainty estimates.
Summary updated