PaperlayerView exact revision on arXiv

Source-linked AI summary

A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit

Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias

arXiv:2609.05113v1cs.LG

TL;DR

Counterfactual GNN explainers aim to identify minimal, realistic graph edits that change predictions, but existing methods trade off explanation size, coverage, and quality. This study compares six state-of-the-art methods across diverse graph and node classification settings using quantitative and qualitative metrics, finding that no explainer consistently leads across validity, efficiency, size, minimality, and motif proximity. The results motivate more general, efficient, qualitatively reliable explainers and standardized benchmarks.

  • Problem

    Existing counterfactual explainers differ in strengths and weaknesses, with limited general and efficient methods for high-quality explanations involving edge additions and deletions.

  • Method

    The study comparatively evaluates state-of-the-art post-hoc counterfactual GNN explainers across graph and node classification on real-world and synthetic datasets.

  • Results

    No single explainer consistently performs best across validity, efficiency, explanation size, minimality, and motif proximity.

  • Takeaways & Limitations

    The findings support developing more general, efficient, qualitatively reliable explainers and more standardized evaluation benchmarks.

  • Takeaways & Limitations

    The study does not consider heterogeneous or dynamic graphs and notes that node-classification explanations show reduced performance relative to graph classification.

Abstract

from arXiv · show

Counterfactual explanations for graph-structured data seek to determine minimal and realistic modifications required in an input graph to alter a model's prediction to a predefined output. Although counterfactual explainers that support modifying the graph by both adding and removing edges have recently emerged, there is still a lack of general and efficient methods, especially when considering the quality of the generated explanations. Moreover, the problem remains far from solved, as existing methods exhibit different strengths and weaknesses, often trading off between explanation size, coverage and quality. For this reason, it is important to identify where each method performs well and where it falls short, so as to guide future research in the field. Thus, our study compares six state-of-the-art (SOTA) models on a diverse set of real-world and synthetic datasets, covering both binary and multi-class graph and node classification tasks, and evaluates their performance using diverse quantitative and qualitative metrics.

1 Introduction

Counterfactual explanations extend GNN explainability from identifying influential graph components to specifying minimal changes that alter predictions. This study compares state-of-the-art methods across diverse tasks, datasets, and evaluation dimensions.

  • Motivation: GNNs process graph structure and node features for graph, node, and link prediction tasks.Examples include molecular toxicity, paper-topic, and missing-connection prediction.
  • Motivation: Early GNN explainers mainly identified influential subgraphs whose removal preserved or changed a specific prediction.These local factual methods focused on explaining an already-made decision rather than specifying how to alter it.
  • Counterfactual explainability: Counterfactual explainers seek minimal graph-structure or node-feature modifications that change a model’s prediction.They therefore indicate what should be changed, complementing factual explanations of why a prediction was made.
  • Counterfactual explainability: Recent methods support more flexible perturbations, including both edge additions and deletions, beyond earlier domain-specific approaches.These methods draw on ideas from adversarial attacks, diffusion models, and spectral style transfer.
  • Study scope: The study provides a comprehensive assessment of post-hoc, model-agnostic counterfactual explainers for graph and node classification.It evaluates real-world and synthetic datasets, binary and multiclass settings, and metrics covering performance, efficiency, and explanation quality.

2 Literature Classification

Graph counterfactual explainers have progressed from edge-removal methods toward approaches that support broader graph transformations, global explanations, and generative modeling. The literature remains heterogeneous in task scope, assumptions, and evaluation coverage.

  • Edge-removal methods: Most early counterfactual explainers generated subgraphs by removing edges, using optimization, decision-region learning, or heuristic mask-search strategies.Examples include CF-GNNExplainer, RCExplainer, MOO, CF2, and CFExplainer.
  • Edge additions: LEGIT and MEG incorporated edge addition through reinforcement learning, but specifying all possible states requires extensive domain knowledge.CLEAR instead uses a variational autoencoder with regularization intended to encourage minimal structural changes.
  • Global explainers: Global explainers target counterfactuals applicable to larger proportions of input graphs, but their transformation capabilities differ.GCFExplainer adds and removes edges using random walks, whereas GlobalGCE uses an autoencoder while focusing on subgraph explanations.
  • Generative approaches: RSGG-CE, ATEX-CF, and D4Explainer use generative-adversarial, adversarial-attack, and diffusion approaches to support broader counterfactual generation.RSGG-CE transforms graphs toward the opposite class, ATEX-CF targets node classification, and D4Explainer models explanation-graph distributions.
  • Evaluation gap: Recent state-of-the-art methods were often evaluated against edge-removal baselines, motivating a broader comparison across graph and node classification.The study extends an earlier graph-classification-focused evaluation to both prediction tasks.

3 Preliminaries

Counterfactual explanations modify graph inputs to change graph- or node-level predictions while remaining minimal and plausible. The paper motivates these edits through practical graph-completion scenarios and formalizes them using adjacency, feature, and classifier representations.

  • Motivation: Drug-interaction graphs illustrate why edge additions can provide counterfactual insights beyond removing existing edges.An added interaction between drugs A and C could indicate increased hypersensitivity risk and motivate further investigation.
  • Graph representation: A graph is represented by nodes V, edges E, binary adjacency matrix A, and feature matrix X.The adjacency matrix has dimensions N×N, while the feature matrix lies in R^N×d.
  • Graph classification: For graph classification, factual explainers preserve the original label on an explanatory subgraph, whereas counterfactual explainers seek a minimally modified graph with a different label.The classifier maps graphs to labels, and the counterfactual objective changes the graph-level prediction.
  • Counterfactual objective: Valid counterfactual generation is formulated as finding minimal graph edits that change the prediction while also requiring plausibility and robustness.The candidate space consists of graph perturbations whose predictions differ from the original class.
  • Node classification: For node classification, counterfactual explainers seek a minimally different, plausible subgraph relevant to a target node.The node classifier takes both the graph and node as input, and the explanation aims to alter that node’s prediction.

4 Evaluation

The evaluation compares counterfactual explainers across graph and node classification using diverse datasets and metrics. Results show consistent trade-offs among validity, fidelity, explanation size, motif proximity, minimality, and runtime, with no method dominating all criteria.

  • Experimental setup: The graph-classification study evaluates CF2, D4Explainer, RSGG-CE, GIST, GCFExplainer, and an exhaustive-search Random baseline across synthetic and real-world datasets.The datasets include binary and multiclass settings, while node-classification experiments compare D4Explainer, CF2, and CF-GNNExplainer.
  • Graph classification: Graph-classification results reveal a trade-off between validity, fidelity, and explanation size, so strong performance on one criterion does not ensure broadly practical explanations.GCFExplainer maintains perfect validity on real-world datasets but produces substantially larger explanations; GIST also produces explanations considered too large for human interpretation.
  • Overall interpretation: The study favors explanations that modify meaningful local neighborhoods while balancing coverage, small size, high fidelity, minimality, and realistic changes.Producing a counterfactual in every case is not preferred when the resulting edits are arbitrary, distant, or out of distribution.
  • Explanation quality: Most explainers fail to consistently modify the ground-truth motif, whereas CF2 achieves the highest Motif Proximity on most datasets.This limitation persists even on synthetic datasets where changing the embedded motif is required to alter the prediction.
  • Explanation quality: Minimality varies across datasets and methods: RSGG-CE performs best among SOTA explainers on several datasets, while CF2 and D4Explainer are strong on some real-world datasets.GCFExplainer and GIST tend to produce less minimal explanations, likely reflecting a trade-off with validity.
  • Efficiency: RSGG-CE has the lowest training times, GIST and RSGG-CE compete for lowest inference times, and D4Explainer has the highest training times.The results underline that runtime must be considered alongside explanation performance.
  • Node classification: In node classification, CF-GNNExplainer generally produces compact counterfactuals with high validity, while CF2 favors compact explanations but can sacrifice validity.No method consistently achieves the best minimality across all node-classification datasets; CF2 reaches near-perfect Motif Proximity on Tree-Cycles.

5 Open Challenges

The analysis identifies unresolved challenges in counterfactual explanation, including trade-offs among qualitative criteria, limited task coverage, inconsistent evaluation, and restricted graph-structure scope.

  • Research direction: The study identifies open research challenges intended to guide future development of counterfactual GNN explainers capable of both adding and removing edges.The analysis frames these challenges as part of a comprehensive assessment of a new generation of post-hoc explainers.
  • Method trade-offs: No universally best-performing explainer emerges because methods trade off compactness, validity, efficiency, coverage, and qualitative explanation quality.RSGG-CE produces compact, valid explanations efficiently but has moderate qualitative scores; D4Explainer performs strongly on real data but is computationally intensive; GCFExplainer achieves high coverage but poor qualitative scores.
  • Evaluation standards: Evaluation lacks standardized benchmarks, includes inconsistent baselines and metrics, and must weigh explanation quality and robustness beyond validity and fidelity.The study notes that existing comparisons often use popular rather than strongest baselines and metrics with substantially different scope.
  • Task coverage: Many studies emphasize graph classification while overlooking node classification and link prediction, with node-classification explanations showing reduced performance.The authors also report that some explainers do not support these tasks, and that detailed qualitative metrics remain necessary even when simpler metrics look favorable.
  • Graph-data scope: The survey excludes heterogeneous and dynamic graphs, leaving future explainers to accommodate a wider variety of graph data.These structures are described as an emerging area in graph representation learning with impactful GNN prediction models.

6 Conclusions

The comparative study finds that no counterfactual GNN explainer consistently leads across validity, efficiency, explanation size, minimality, and motif proximity. It therefore identifies continuing needs for general, efficient, qualitatively reliable explainers and standardized evaluation benchmarks.

  • No single explainer consistently performs best across validity, efficiency, explanation size, minimality, and motif proximity.
  • The findings highlight the need for more general, efficient, and qualitatively reliable counterfactual explainers.
  • The study also highlights the need for more standardized benchmarks for evaluating counterfactual explainers.

A Hyperparameter Selection

The evaluation reports training configurations and dataset-specific hyperparameters for all included methods. Unless otherwise reported, it follows each method's original implementation and recommended settings, while retraining all frameworks under the study's own data splits.

  • The appendix reports training configurations and dataset-specific hyperparameters for every method included in the evaluation.
  • Unless otherwise reported, the study follows each method's original implementation and recommended settings.
  • All frameworks were retrained because the study used different train, validation, and test splits from the original evaluations.

A.1 Graph Classification Hyperparameters

Graph-classification experiments use method-specific training configurations across synthetic and real-world datasets. The appendix specifies optimization, sampling, diffusion, regularization, and search settings for CF2, D4Explainer, GIST, RSGG-CE, and GCFExplainer.

  • CF2 uses 500 training epochs, with dataset-dependent sparsity penalties and learning rates across motif and real-world datasets.The settings include α=0.7, γ=0.9, threshold 0.5, λ=20 or 100, and η=0.02 or 0.05.
  • D4Explainer trains a diffusion model for 800 epochs using six diffusion layers, hidden size 64, instance normalization, and a ten-step noise schedule.Its learning rate is η=10^-3, decay γ=0.999, dropout is 0.001, and the CF loss weight is α_cf=0.5 with sparsity level 2.5.
  • GIST is trained for 50 epochs with batch size 16, hidden dimension 16, two attention heads, and regularization coefficient α=0.9.Optimization uses Adam with learning rate 10^-3 and weight decay 10^-5.
  • RSGG-CE is trained for 30 epochs using positive-and-negative edge sampling, 500 sampling iterations per step, and one GAN per target class.The generator and discriminator use SGD with η=10^-3 and batch size 4, while embedding dimensions vary by dataset.
  • GCFExplainer uses dataset-specific decision thresholds, teleport probabilities, neighborhood sample sizes, and per-class maximum steps.The appendix reports separate settings for motif, BBBP, Graph-SST5, and Twitter datasets.

A.2 Node Classification Hyperparameters

Node-classification experiments use method-specific optimization and diffusion settings. The appendix reports configurations for CF-GNNExplainer, CF2, and D4Explainer across the evaluated node-classification datasets.

  • CF-GNNExplainer uses learning rate 10^-2, β=0.5 for the size-loss weight, and 500 optimization epochs per node.
  • CF2 runs the per-node counterfactual search for 2,000 epochs with α=0.6, γ=0.5, and λ=500.The learning rate is 10^-2 for BA-Shapes, Cora, and PubMed, and 5 × 10^-2 for Tree-Cycles.
  • D4Explainer trains its diffusion model for 800 epochs with batch size 32, learning rate 10^-3, decay 0.999, dropout 0.001, and a ten-step noise schedule.The CF loss weight and sparsity penalty vary between Tree-Cycles and BA-Shapes.
Loading 2609.05113v1…