Source-linked AI summary
CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks
Ana Lucic, Maartje ter Hoeve, Gabriele Tolomei, Maarten de Rijke, Fabrizio Silvestri
TL;DR
Understanding why machine-learning models make predictions is increasingly important, including for graph-based molecular property prediction. CF-GNNExplainer generates counterfactual explanations by perturbing graph structure, and produces accurate, minimal changes across tested datasets.
Problem
Understanding why machine-learning models make predictions is increasingly important, and molecular applications need minimal graph changes that can alter predicted properties.
Method
CF-GNNExplainer generates counterfactual examples by removing edges from a node's adjacency matrix until the GNN prediction changes.
Results
CF-GNNExplainer generates counterfactual examples for the majority of test nodes and achieves at least 94% accuracy where ground-truth explanations are known.
Takeaways & Limitations
The method produces explanations that are minimal in edges removed and sparsity while targeting edges crucial to the initial predictions.
Takeaways & Limitations
GNNExplainer cannot automatically find a minimal subgraph, so its counterfactual minimality cannot be evaluated directly.
Abstract
from arXiv · showhide
Given the increasing promise of graph neural networks (GNNs) in real-world applications, several methods have been developed for explaining their predictions. Existing methods for interpreting predictions from GNNs have primarily focused on generating subgraphs that are especially relevant for a particular prediction. However, such methods are not counterfactual (CF) in nature: given a prediction, we want to understand how the prediction can be changed in order to achieve an alternative outcome. In this work, we propose a method for generating CF explanations for GNNs: the minimal perturbation to the input (graph) data such that the prediction changes. Using only edge deletions, we find that our method, CF-GNNExplainer, can generate CF explanations for the majority of instances across three widely used datasets for GNN explanations, while removing less than 3 edges on average, with at least 94\% accuracy. This indicates that CF-GNNExplainer primarily removes edges that are crucial for the original predictions, resulting in minimal CF explanations.
1 INTRODUCTION
CF-GNNExplainer addresses the gap between conventional GNN explanations and counterfactual explanations by seeking minimal graph changes that alter predictions. It evaluates this approach across three public datasets and reports accurate, small perturbations.
- In drug discovery, changing molecular graph structure could help identify minimal modifications associated with a desired predicted property.
- Existing GNN explanation methods primarily identify prediction-relevant subgraphs rather than counterfactual changes that produce alternative outcomes.
- CF-GNNExplainer generates counterfactual explanations for GNNs by identifying minimal perturbations to graph data.
- The method is evaluated on three public datasets using fidelity, explanation size, sparsity, and accuracy.
- CF-GNNExplainer generates counterfactual examples with at least 94% accuracy while removing fewer than 3 edges on average.
- The paper formalizes the task, proposes CF-GNNExplainer, and introduces an experimental setup for holistic evaluation.
2 RELATED WORK
Related GNN explanation methods generally retrieve relevant subgraphs, whereas CF-GNNExplainer seeks minimal perturbations that change predictions without requiring the user to set explanation size. The paper distinguishes this local counterfactual task from other explanation and attack settings.
- Most existing GNN XAI methods generate subgraphs considered important for a particular prediction.
- Subgraph-generating methods require users to specify the number of features or edges to retain in advance.
- CF explanations find the minimal perturbation that changes a prediction, while subgraph methods identify relevant subgraphs that are not necessarily minimal.
- Prior GNN counterfactual work includes link prediction, whereas CF-GNNExplainer produces instance-level explanations for another task.
- Counterfactual examples and adversarial examples both use perturbations that change predictions, but their intents differ: explanation versus fooling the model.
- CF-GNNExplainer targets individual nodes and evaluates accuracy to distinguish informative counterfactuals from adversarial perturbations.
3 BACKGROUND
The paper represents node-classification inputs with graph structure and node features, focusing on the local neighborhood used by a GNN. CF-GNNExplainer adapts matrix sparsification to remove crucial adjacency entries and thereby edges.
- GNNs operate on nodes and edges to produce representations for downstream tasks, with this work focusing on node classification.
- A GNN is represented as f(A, X; W), where A is the adjacency matrix, X the feature matrix, and W the learned weights.
- With ℓ layers, a node representation includes neighbors up to ℓ hops away, defining the relevant subgraph neighborhood.
- CF-GNNExplainer uses a learned binary sparsification matrix to zero out entries in the adjacency matrix and remove edges.
- The targeted edges are those considered important or crucial for the original prediction.
4 PROBLEM FORMULATION
The paper formulates a graph counterfactual as an altered adjacency structure that changes a node’s prediction while preserving its features. The optimal explanation minimizes a distance-based loss subject to producing a different output.
- A general counterfactual example changes an instance so that the classifier’s prediction differs from the original.
- An optimal counterfactual minimizes the distance between the original instance and its perturbed version.
- For graph data, CF-GNNExplainer perturbs the subgraph adjacency matrix by removing edges while retaining the node feature vector.
- The objective combines prediction loss, which encourages a changed output, with distance loss, which encourages proximity to the original node.
- The optimal counterfactual is the perturbed node that minimizes the combined loss.
5 METHOD: CF-GNNExplainer
CF-GNNExplainer generates counterfactual graph explanations by sparsifying a node’s adjacency matrix until the fixed GNN changes its prediction, while seeking minimal edge deletions.
- Counterfactual generation: CF-GNNExplainer generates a counterfactual node graph by perturbing its adjacency matrix while keeping the original GNN model fixed.The method can operate on any GNN model f and produces a modified adjacency matrix with the original node features.
- Adjacency Matrix Perturbation: The method learns a binary perturbation matrix P that sparsifies the original adjacency matrix and seeks f(Av, x) ≠ f(P ⊙ Av, x).A zero entry in P deletes the corresponding edge, while ones retain edges for the forward pass.
- Counterfactual Generating Model: CF-GNNExplainer perturbs only Av, preserving self-loops so each node update includes its own previous representation.The degree matrix is recomputed from the perturbed adjacency matrix, then the identity matrix is added to account for self-loops.
- Loss Function Optimization: The optimization uses a loss that penalizes unchanged predictions and measures perturbation distance by the number of removed edges.For undirected graphs, the edge-removal distance is divided by 2 to account for symmetric adjacency matrices.
- CF-GNNExplainer: Starting from an all-ones perturbation matrix, the algorithm iteratively updates its real-valued parameters, tests candidate counterfactuals, and retains the most minimal valid example.A candidate is valid when the original GNN predicts a different output for the sparsified graph; the retained result is the optimal CF example.
- Complexity: CF-GNNExplainer has time complexity O(KN^2), where N is the neighborhood size and K is the number of iterations.In practice, explanations are typically generated for only a subset of the dataset.
6 EXPERIMENTAL SETUP
The experiments evaluate CF-GNNExplainer and baselines on synthetic graph datasets using four metrics, with hyperparameters selected through search. The setup targets ground-truth-based assessment of counterfactual explanations for node classification.
- 6.1 Datasets and Models: The evaluation uses the tree-cycles, tree-grids, and ba-shapes datasets, which provide ground-truth explanations for node classification predictions.Each dataset combines a base graph, attached motifs, and randomly added edges; nodes are classified by motif membership.
- 6.1 Datasets and Models: A 3-layer GCN with hidden size 20 is trained for each task using the experimental setup of Ying et al. (2019), achieving at least 87% test accuracy.The ba-shapes dataset is substantially denser than the two tree-based datasets.
- 6.2 Baselines: The study compares CF-GNNExplainer with random, 1hop, rm-1hop, and GNNExplainer baselines.GNNExplainer is evaluated for S ∈ {1, 2, 3, 4, 5, GT}, while the other baselines use specified perturbation strategies.
- 6.3 Metrics: The evaluation measures fidelity, explanation size, sparsity, and accuracy for counterfactual explanations.Low fidelity, small explanation size, high sparsity, and motif-exclusive removals are desirable under the stated metric definitions.
- 6.4 Hyperparameter Search: Hyperparameter search varies iterations K, trade-off β, learning rate α, momentum m, and optimizer, selecting the setting that produces the most CF examples.The tested optimizers are Adam, SGD, and AdaDelta, with specified grids for the numerical hyperparameters.
7 RESULTS
Across the three datasets, CF-GNNExplainer generally produces accurate counterfactual examples with smaller explanations and stronger sparsity than the baselines. It generates counterfactuals for most test nodes while removing few edges, outperforming GNNExplainer on fidelity and accuracy.
- Overall results: CF-GNNExplainer outperforms the baselines in explanation size, sparsity, and accuracy in almost all settings.When a baseline wins one metric, it performs poorly on other metrics or datasets.
- Explanation size: CF-GNNExplainer has the smallest explanation sizes across all three datasets.The contrast is especially pronounced against random and 1hop on ba-shapes, whose denser neighborhoods permit many unnecessary edge removals.
- Sparsity: CF-GNNExplainer outperforms random, rm-1hop, and 1hop on sparsity for all three datasets.Its advantage aligns with the small explanation sizes observed across datasets.
- Accuracy: CF-GNNExplainer reaches at least 94% accuracy across all datasets, with the highest accuracy on tree-cycles and tree-grid.rm-1hop has the highest accuracy on ba-shapes but cannot generate CF examples for motif nodes in the other two datasets.
- Comparison with GNNExplainer: CF-GNNExplainer outperforms GNNExplainer on fidelity and accuracy for all tested values of S across all three datasets.Explanation size and sparsity cannot be compared fairly because GNNExplainer requires S as user input.
- Summary: CF-GNNExplainer generates counterfactual examples for the majority of test nodes while removing a small number of edges.For nodes with known ground truth, it achieves at least 94% accuracy.
8 SOCIETAL IMPACT
Counterfactual explanations should be interpreted within their deployment context because their suggested changes are candidate changes rather than guarantees of recourse. Their practical actionability depends on the application setting.
- Practical limitations: CF explanations are not guarantees of recourse, so suggested changes should be treated as candidate changes rather than absolute solutions.Whether a change is pragmatically actionable depends on the context in which the ML system is deployed.
- Evaluation: The authors recommend human-centered user studies to evaluate the practical utility of XAI methods.They suggest collaboration between XAI and human-computer interaction researchers.
9 CONCLUSION
CF-GNNExplainer generates minimal and accurate counterfactual explanations for GNNs across three datasets, but currently supports only edge deletions for node classification.
- Conclusion: CF-GNNExplainer generates minimal counterfactual explanations for any GNN by removing crucial edges from individual node neighborhoods.Minimality concerns both the number of edges removed and the proportion of the neighborhood perturbed.
- Conclusion: Results hold across all three evaluated datasets, where CF-GNNExplainer reliably produces minimal, accurate counterfactual explanations.
- Conclusion: CF-GNNExplainer is currently limited to edge deletions in node classification tasks.Planned extensions include node-feature perturbations and graph-classification tasks.
A Results Table Including Standard Deviations
The table reports standard deviations for Explanation Size and Sparsity, while statistical comparisons show broad significance with a specific tree-grid exception.
- Table interpretation: Standard deviations are reported for Explanation Size and Sparsity because both metrics average values across the dataset.They are not reported for Fidelity or Accuracy because those metrics are proportions.
- Statistical comparisons: All differences between CF-GNNExplainer and baselines are statistically significant at α = 0.01, except two tree-grid comparisons against rm-1hop.The exceptions concern Explanation Size and Sparsity.
- Statistical comparisons: CF-GNNExplainer significantly outperforms rm-1hop on tree-grid Fidelity and Accuracy at α = 0.01.
- Evaluation scope: GNNExplainer cannot be evaluated on Explanation Size or Sparsity because users must specify explanation size in advance.Comparison with GNNExplainer is therefore limited to Fidelity and Accuracy.