Source-linked AI summary
Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning
Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, Yongfeng Zhang
TL;DR
GNN explanations are difficult to learn and evaluate because models are non-transparent and ground-truth explanations are often unavailable. CF2 combines counterfactual and factual reasoning for explanation generation and evaluation, and experiments report superior explanations and useful metrics across synthetic and real-world datasets.
Problem
GNN predictions are difficult to explain, and evaluating explanations is challenging because many real-world graph datasets lack ground-truth explanations.
Method
CF2 optimizes explanations using both counterfactual and factual reasoning and evaluates necessity and sufficiency with Probability of Necessity and Probability of Sufficiency.
Results
Experiments on synthetic and real-world datasets verify CF2's superiority and the usefulness of its evaluation metrics.
Takeaways & Limitations
Considering necessity and sufficiency together provides a framework for generating and quantitatively evaluating GNN explanations.
Takeaways & Limitations
The Mutag0 dataset is restricted to compounds containing benzene-NO2, reflecting the dataset-specific influence of NH2 and the discriminative role of benzene-NO2.
Abstract
from arXiv · showhide
Structural data well exists in Web applications, such as social networks in social media, citation networks in academic websites, and threads data in online forums. Due to the complex topology, it is difficult to process and make use of the rich information within such data. Graph Neural Networks (GNNs) have shown great advantages on learning representations for structural data. However, the non-transparency of the deep learning models makes it non-trivial to explain and interpret the predictions made by GNNs. Meanwhile, it is also a big challenge to evaluate the GNN explanations, since in many cases, the ground-truth explanations are unavailable. In this paper, we take insights of Counterfactual and Factual (CF^2) reasoning from causal inference theory, to solve both the learning and evaluation problems in explainable GNNs. For generating explanations, we propose a model-agnostic framework by formulating an optimization problem based on both of the two casual perspectives. This distinguishes CF^2 from previous explainable GNNs that only consider one of them. Another contribution of the work is the evaluation of GNN explanations. For quantitatively evaluating the generated explanations without the requirement of ground-truth, we design metrics based on Counterfactual and Factual reasoning to evaluate the necessity and sufficiency of the explanations. Experiments show that no matter ground-truth explanations are available or not, CF^2 generates better explanations than previous state-of-the-art methods on real-world datasets. Moreover, the statistic analysis justifies the correlation between the performance on ground-truth evaluation and our proposed metrics. Source code is available at https://github.com/chrisjtan/gnn_cff.
1 INTRODUCTION
GNNs learn from graph structure and features but are difficult to interpret, while explanations are hard to evaluate without ground truth. CF2 addresses both issues by jointly modeling necessity and sufficiency and introducing quantitative evaluation metrics.
- GNNs aggregate graph features and structure effectively, but their non-transparent predictions require explanation to support understanding and model refinement.
- Factual reasoning can produce sufficient but redundant explanations, whereas counterfactual reasoning can produce necessary but incomplete explanations.Factual explanations may include extra edges; counterfactual explanations may capture only a small subset of the real explanation.
- CF2 formulates an optimization problem that combines counterfactual and factual objectives to extract explanations that are both necessary and sufficient.The counterfactual objective encourages necessary edges, while the factual objective preserves sufficient information.
- Ground-truth explanations are often unavailable for real-world graphs, making quantitative evaluation of GNN explanations difficult.
- CF2 introduces Probability of Necessity and Probability of Sufficiency to evaluate explanation necessity and sufficiency without requiring ground truth.The metrics align with counterfactual and factual reasoning, respectively.
- The work reports contributions spanning the CF2 framework, quantitative evaluation metrics, and experiments on 2 synthetic and 3 real-world datasets.
2 RELATED WORKS
Explainable GNN methods extend broader explainable-AI approaches to graph data, where topology matters alongside individual features. Existing work includes factual approaches based on information preservation and counterfactual approaches based on prediction changes.
- Explainable-AI methods include gradient/feature-based, perturbation/causal-based, and surrogate approaches, developed mainly for images and text.
- Graph explanations must account for topological structure in addition to individual features because graph structure is related to domain-specific functionality.
- Explainable GNN research includes gradient extensions, generative methods such as PGExplainer and XGNN, and counterfactual approaches such as CF-GNNExplainer.PGExplainer learns approximate discrete masks, while XGNN generates graphs to approximate original predictions.
3 PRELIMINARIES AND NOTATIONS
GNNs learn node representations by aggregating neighbor information across layers, then support graph and node classification through graph-level or local computational representations.
- Learning Representations: GNNs iteratively aggregate neighbor information to update each node’s representation across layers.The final node representation is produced after the model’s total number of layers.
- Learning Representations: Graph representations can be computed by averaging the node representations in a graph.
- Graph Classification: Graph classification learns a classifier that predicts each input graph’s class label from its adjacency and node-feature matrices.
- Node Classification: Node classification predicts each node’s class using its L-hop computational sub-graph and corresponding adjacency and feature matrices.
4 PROBLEM FORMULATION
CF2 formulates GNN explanations as simple, effective sub-graphs that combine factual sufficiency with counterfactual necessity. It measures explanation complexity and strength, then uses both in a constrained optimization objective.
- 4 PROBLEM FORMULATION: The explainable GNN problem seeks explanations that are sufficient, necessary, and simple rather than merely predictive.The paper states that these goals are represented by factual and counterfactual conditions plus Occam’s Razor-based complexity control.
- 4.1 Explainable Graph Neural Networks: CF2 represents an explanation with edge and feature masks applied to the graph’s adjacency and node-feature matrices.The resulting masked adjacency and features define the generated explanation sub-graph.
- 4.2 Counterfactual and Factual Conditions: Factual reasoning requires the explanation alone to preserve the original prediction, whereas counterfactual reasoning requires removing it to change the prediction.
- 4.2 Counterfactual and Factual Conditions: CF2 formulates factual and counterfactual conditions as objectives for extracting explanations.
- 4.3 Simple and Effective Explanations: CF2 uses complexity as a learning objective and strength as a learning constraint to seek simple, effective explanations.
- 4.3 Simple and Effective Explanations: Explanation complexity counts the edges and features used to construct an explanation, represented by the 1s in its binary masks.
- 4.3 Simple and Effective Explanations: Explanation strength measures effectiveness through factual and counterfactual components, with larger values preferred.
5 THE CF2 FRAMEWORK
The CF2 framework optimizes explanation complexity subject to sufficient explanation strength, then relaxes nondifferentiable components so the objective can be optimized.
- Framework: CF2 aims to generate low-complexity, high-strength explanations for any prediction made by a GNN.
- Optimization Framework: The constrained framework minimizes explanation complexity while requiring the explanation to be strong enough.
- Optimization Framework: The strength constraint preserves the predicted label when the explanation is retained and changes it when the explanation is removed.
- Optimization Relaxation: CF2 relaxes real-valued masks, the original 0-norm objective, and pairwise contrastive losses to make the optimization differentiable.
- Implementation: A mask value above 0.5 retains its associated edge or feature after optimization.The margin and threshold are both set to 0.5.
- Hyper-parameters: Increasing λ prioritizes explanation effectiveness over complexity, potentially producing larger sub-graphs and feature spaces.
6 EVALUATING GNN EXPLANATIONS
Because ground-truth explanations are often unavailable, CF2 evaluates explanations through factual sufficiency and counterfactual necessity. It summarizes both properties with PS, PN, and their harmonic mean F_NS.
- Evaluation Motivation: Ground-truth explanations are absent from many real-world graph and node classification datasets, making evaluation difficult.
- Probability of Sufficiency: Probability of Sufficiency (PS) is the percentage of explanations whose sub-graph alone preserves the prediction of the whole graph.
- Probability of Necessity: Probability of Necessity (PN) is the percentage of explanations whose removal changes the GNN prediction.
- Overall Evaluation: Higher PS and PN values indicate better explanation performance.
- Overall Evaluation: F_NS = 2·PN·PS/(PN+PS) combines sufficiency and necessity into an overall explanation score.
7 EXPERIMENTS
CF2 is evaluated on synthetic and real-world datasets using ground-truth and PN/PS-based metrics, with experiments examining its design choices and comparison baselines. Across these evaluations, CF2 balances factual and counterfactual reasoning and generally outperforms methods using either perspective alone.
- Experimental Setup: Experiments use two synthetic and three real-world datasets spanning node and graph classification, including datasets with and without ground-truth motifs.The datasets are BA-Shapes, Tree-Cycles, Mutag, NCI1, and CiteSeer.
- Experimental Setup: CF2 is compared with GNNExplainer, CF-GNNExplainer, and Gem under explanation-generation settings that differ in whether explanation size is predefined or optimized.GNNExplainer and Gem require a human-selected K, whereas CF-GNNExplainer and CF2 automatically determine explanation size through optimization.
- Quantitative Analysis: CF2 achieves overall better ground-truth performance than the baselines according to Accuracy and F1, with Gem the only exception on BA-Shapes Accuracy, where CF2 is lower by 0.62%.The comparison is based on explanations evaluated against ground-truth motifs; Gem's BA-Shapes result uses the ground-truth motif size as prior knowledge.
- Quantitative Analysis: Factual reasoning produces higher ground-truth coverage, whereas counterfactual reasoning produces more precise but less complete explanations; CF2 balances these tendencies and achieves higher overall F1.This pattern motivates combining both reasoning perspectives rather than relying on either one alone.
- Quantitative Analysis: On PN/PS-based evaluation, CF2 performs best in 100% of PN cases, 83% of PS cases, and 100% of FNS cases, with a 13.57% average FNS improvement over the best baseline.Counterfactual methods perform better on PN, while factual methods perform better on PS.
- Qualitative Analysis: Qualitative results show that CF2 discovers graph motifs better than factual-only and counterfactual-only methods, while intermediate α values outperform using only one reasoning type.The experiments compare explanations on BA-Shapes, Tree-Cycles, and Mutag and study α as the balance between reasoning objectives.
8 CONCLUSIONS AND FUTURE WORK
CF2 jointly models necessity and sufficiency for GNN explanations and uses PN/PS-based metrics to evaluate them quantitatively. Experiments support the method and metrics on synthetic and real-world datasets, while future work targets vision- and language-based explanations.
- CF2 generates GNN explanations by simultaneously considering the necessity and sufficiency of the explanations.
- PN and PS enable quantitative evaluation of the necessity and sufficiency of extracted GNN explanations.
- Experiments on synthetic and real-world datasets verify the proposed method and the usefulness of its evaluation metrics.
- The framework is proposed for future generalization beyond graph-based explanations to vision- and language-based explanations.
A MATHEMATICAL DEFINITIONS FOR NODE CLASSIFICATION
For node classification, the paper defines the explainable GNN problem using each node’s L-hop computational graph.
- The node-classification formulation uses the L-hop computational graph around a node and defines the explainable GNN problem within that sub-graph.
A.1 Problem Formulation (Node Classification)
For node classification, explanations are learned as edge and feature masks over a node’s computational graph. The framework defines factual and counterfactual conditions and balances explanation strength with complexity.
- A.1 Problem Formulation (Node Classification): The node-classification explanation consists of an edge mask and a feature mask applied to the computational graph’s adjacency and feature matrices.
- A.1 Problem Formulation (Node Classification): After optimization, the masked adjacency and feature matrices form the generated explanation for the target node’s prediction.
- A.1 Problem Formulation (Node Classification): The node-classification formulation defines factual and counterfactual conditions for evaluating explanation behavior.
- A.1 Problem Formulation (Node Classification): Explanation complexity, factual explanation strength, and counterfactual explanation strength are defined for the node-classification setting.
A.2 The CF2 Framework (Node Classification)
For node and graph classification, CF2 minimizes explanation complexity while requiring the generated explanation to remain sufficiently strong, using a relaxed optimization formulation.
- CF2 uses the same basic idea for node and graph classification: minimize explanation complexity while keeping the generated explanation sufficiently strong.
- The framework generates explanations by solving a relaxed optimization equation.