Bidirectional Counterfactual Explanations for Graph Neural Networks

This direction is merged into another direction: model interpretability (GNN interpretability). Its last version stays readable and citable here.

Version 1 of 122 papers32 conceptsfrozen 2026-10-04

Graph Neural Networks (GNNs) are often treated as black boxes, providing high-accuracy predictions for molecules, social networks, and code structures without explaining their reasoning. Traditional interpretability methods focus on "factual" explanations—identifying which existing edges or nodes were most influential to a prediction. However, a newer research direction focuses on counterfactual explanations: identifying the minimal set of changes (perturbations) that would flip the model's prediction.

Instead of asking "What part of this graph is important?", counterfactual reasoning asks "What is the smallest change I could make to change the outcome?" This approach provides actionable recourse, telling a researcher not just that a molecule is toxic, but exactly how to modify it to make it safe.

The Limitation of Subgraph Pruning

Early work in GNN interpretability, such as CF-GNNExplainer by Ana Lučić and Fabrizio Silvestri, primarily focused on edge deletion. These methods identify a "minimal sufficient" subgraph by pruning connections until the prediction changes.

However, as noted by Samidha Verma and Sayan Ranu in Empowering Counterfactual Reasoning over Graph Neural Networks through Inductivity, deletion-only methods are fundamentally limited. If a GNN’s decision is based on the absence of a specific structural motif—like a chemical ring that hasn't been closed—a deletion-only explainer can never discover that adding a single bond would flip the prediction. To truly understand the decision boundary, an explainer must be able to both add and remove edges.

Bidirectional Structural Perturbations

To address this, researchers have moved toward bidirectional structural modifications. Bardh Prenkaj and Giovanni Stilo introduced RSGG-CE, which uses a generative framework to produce "residual maps." Rather than synthesizing a new graph, the model learns a map of specific additions and removals. This allows the framework to treat structural duality—the insertion and deletion of components—as a unified task, making it far more effective for complex datasets where motifs must be completed rather than just simplified.

Similarly, ATEX-CF by Yu Zhang and Arijit Khan bridges the gap between adversarial attacks and interpretability. By using "attack-informed" edge additions, they identify influential features that are currently absent from the graph, providing a higher-fidelity view of the model's logic.

Joint Optimization of Features and Structure

Graphs are not just sets of connections; they are also defined by the attributes of their nodes. A prediction might flip because a bond was removed, or because a specific atom's properties changed.

COMBINEX, developed by Fabrizio Silvestri and Gabriele Tolomei, treats this as a joint optimization problem. By simultaneously applying differentiable perturbations to both the adjacency matrix (structure) and the feature matrix (attributes), the model finds the most efficient path to a prediction flip. This unified approach prevents the explainer from being "blind" to feature-level changes that might be more realistic or minimal than structural ones.

Ensuring Realistic and In-Distribution Explanations

A common pitfall in counterfactual generation is creating "ghost graphs"—mathematically valid perturbations that are physically or logically impossible in the real world.

To solve this, Jialin Chen and Rex Ying proposed D4Explainer. This framework uses discrete denoising diffusion to ensure that generated counterfactuals stay "in-distribution." By learning the underlying distribution of the training data, the diffusion process guides the perturbations toward realistic configurations. This ensures that if a model is being explained for drug discovery, the suggested counterfactual is a molecule that could actually exist.

Beyond Static Graphs

The frontier of this research extends counterfactuals into dynamic and specialized domains:

  • Dynamic Graphs: In temporal networks where edges appear and disappear over time, CoDy by Zhan Qu uses Monte Carlo Tree Search (MCTS) to find the minimal set of past events that, if changed, would alter a future prediction.
  • Argumentation Frameworks: Xiang Yin and Nico Potyka developed CE-QArg to provide recourse in quantitative bipolar argumentation. This allows users to see how changing the strength of an initial argument or adding a new counter-argument could flip a system's final decision.
  • Software Security: CFExplainer by Zhaoyang Chu and Yao Wan applies these concepts to code vulnerability detection, identifying the minimal code refactoring needed to move a program from a "vulnerable" state to a "secure" one.

By moving from simple subtraction to bidirectional, multi-modal, and distribution-aware perturbations, this field is turning GNN explanations from passive descriptions into active tools for discovery and recourse.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bidirectional_counterfactual_explanation_cef89b16,
  title = {Bidirectional Counterfactual Explanations for Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bidirectional-counterfactual-explanations-for-graph-neural-networks/rdr_cef89b16859b4ead9c03f83368d02ac7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_bidirectional_counterfactual_explanation_cef89b16_v1,
  title = {Bidirectional Counterfactual Explanations for Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bidirectional-counterfactual-explanations-for-graph-neural-networks/rdr_cef89b16859b4ead9c03f83368d02ac7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}