TL;DR
Verifying the subgraphs generated by Graph Neural Network (GNN) explainers is notoriously difficult because they are abstract and scale poorly with human evaluation. This paper introduces a novel probabilistic approach that evaluates explanations against symmetric, counterfactual graph variants using factor graphs. By measuring how much an explanation reduces uncertainty across these variants, the method provides a statistically more reliable verification metric than the explainer's internal confidence scores.
What Problem Does This Paper Address?
Explainable AI (XAI) has made great strides with tools like LIME and SHAP, which explain predictions using human-interpretable features like pixel patches or words. If an image classifier highlights a dog's ears to explain a "dog" prediction, any human can easily judge if that explanation makes sense.
Graph Neural Networks (GNNs), however, are a different beast. Popular tools like GNNExplainer output a subgraph to explain a node classification. These relational explanations are highly abstract and complex. Verifying them usually requires deep domain expertise (e.g., molecular chemistry or citation networks) and cannot easily scale. While GNNExplainer provides its own internal importance scores, these are often uncalibrated and unreliable. This paper tackles the challenge of verifying relational explanations without relying on scarce human experts.
Methods
The authors propose a likelihood-based framework built on top of GNNExplainer that quantifies explanation uncertainty through three main steps:
- Symmetric Counterfactual Generation: Instead of randomly altering the input graph to see how the explanation changes, the authors leverage the fact that real-world graphs inherently contain structural symmetries. They use Boolean Matrix Factorization (BMF) to create low-rank, symmetric approximations of the original graph's adjacency matrix. These approximations serve as realistic counterfactual graphs.
- Factor Graph Modeling: The authors run GNNExplainer on all these symmetric counterfactual variants to collect a set of explanations. They then model the distribution of these explanations using a Factor Graph (a type of Probabilistic Graphical Model). The factors in this graph represent logical relationships (conjunctions) between the nodes and the target prediction.
- Uncertainty Estimation via Belief Propagation: The factor graph is calibrated using Belief Propagation (BP) to find the prior joint probability distribution of the relations. To verify a specific explanation from the original graph, they inject it into the calibrated factor graph as a new factor, weighted by GNNExplainer's confidence score. By measuring the reduction in uncertainty (the difference in joint probabilities before and after injection), they determine how reliable the relation truly is.
Datasets
The approach was evaluated on several standard synthetic and real-world node classification benchmarks for GNNs:
- Synthetic Motifs:
BAShapes,BACommunity,TreeGrids, andTreeCycles. These datasets append specific structural motifs (like houses or cycles) to base graphs, providing a clear structural ground truth. - Real-World Networks:
CoraandCiteseer(citation networks), andWebKB(webpage connectivity dataset).
Key Insights and Ideas
- Symmetry as a Prior: Randomly perturbing graphs often creates unrealistic structures that confuse GNNs. By using BMF to enforce low-rank symmetric approximations, the counterfactuals remain grounded in the structural patterns of the original data.
- Contextual Importance Over Raw Scores: GNNExplainer's internal importance scores (IS) can be deceptive. The paper demonstrates that an explanation is only truly valuable if it significantly reduces uncertainty relative to other plausible relationships in the graph's neighborhood.
- The "Garbage In, Garbage Out" Effect for XAI: On datasets where the underlying GNN performed poorly (e.g.,
WebKBwith 50-60% accuracy), the proposed verification method performed similarly to the baseline. This reveals an important insight: if the model itself hasn't learned reliable patterns, its explanations are fundamentally harder—if not impossible—to verify.
Key Results
To evaluate the quality of the uncertainty estimates, the authors used McNemar's statistical test. They systematically removed the edges deemed most certain by both their method (BP) and GNNExplainer's internal scores (IS), retrained the GCN, and measured the drop in prediction accuracy. A larger drop (higher McNemar's Statistic) indicates that the removed edges were genuinely vital to the model's logic.
- Synthetic Datasets: For
BAShapesandTreeCycle, the proposed BP method achieved significantly higher McNemar's Statistic (MS) values across almost all node classes compared to standard internal scores. - Complexity Scaling: As graph structures grew more complex (moving from
BAShapestoTreeGrid), the standard internal scores failed to achieve statistical significance, whereas the BP method remained reliable. - Real-World Datasets: On
CoraandCiteseer, the BP method consistently outperformed or matched the baseline. Notably, as more edges were removed (increasing $G$), the significance of GNNExplainer's internal scores plummeted, while the proposed method maintained strong statistical significance.
Limitations and Future Work
The primary limitation of this approach is its dependency on the accuracy of the underlying GNN. If the GNN is poorly trained, the learned factor graph reflects that noise, rendering the uncertainty estimation less effective. Additionally, computing Boolean Matrix Factorization iteratively can become computationally expensive for massive graphs.
For future work, the authors suggest integrating human-in-the-loop feedback to dynamically refine the factor graph's weights, combining the scalability of their probabilistic framework with occasional expert validation.
Summary updated