Verifying Relational Explanations: A Probabilistic Approach

Abisha Thapa Magar, Anup Shakya, Somdeb Sarkhel, Deepak Venugopal

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:

  1. 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.
  2. 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.
  3. 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.
Symmetric graph approximations generated via Boolean Matrix Factorization
Injecting an explanation into the factor graph to measure uncertainty reduction

Datasets

The approach was evaluated on several standard synthetic and real-world node classification benchmarks for GNNs:

  • Synthetic Motifs: BAShapes, BACommunity, TreeGrids, and TreeCycles. These datasets append specific structural motifs (like houses or cycles) to base graphs, providing a clear structural ground truth.
  • Real-World Networks: Cora and Citeseer (citation networks), and WebKB (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., WebKB with 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 BAShapes and TreeCycle, 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 BAShapes to TreeGrid), the standard internal scores failed to achieve statistical significance, whereas the BP method remained reliable.
  • Real-World Datasets: On Cora and Citeseer, 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

Abstract

Explanations on relational data are hard to verify since the explanation structures are more complex (e.g. graphs). To verify interpretable explanations (e.g. explanations of predictions made in images, text, etc.), typically human subjects are used since it does not necessarily require a lot of expertise. However, to verify the quality of a relational explanation requires expertise and is hard to scale-up. GNNExplainer is arguably one of the most popular explanation methods for Graph Neural Networks. In this paper, we develop an approach where we assess the uncertainty in explanations generated by GNNExplainer. Specifically, we ask the explainer to generate explanations for several counterfactual examples. We generate these examples as symmetric approximations of the relational structure in the original data. From these explanations, we learn a factor graph model to quantify uncertainty in an explanation. Our results on several datasets show that our approach can help verify explanations from GNNExplainer by reliably estimating the uncertainty of a relation specified in the explanation.
BibTeX
@inproceedings{magar2023verifying,
  author = {Abisha Thapa Magar and Anup Shakya and Somdeb Sarkhel and Deepak Venugopal},
  title = {{Verifying Relational Explanations: A Probabilistic Approach}},
  booktitle = {IEEE Big Data},
  year = {2023},
  doi = {10.1109/bigdata59044.2023.10386213},
}
Figure