Counterfactual Transition Graphs: Evaluating Cross-Class Transition Quality

Syed Muhammad Hamza Zaidi; Szymon Bobek; Grzegorz J. Nalepa; Myra Spiliopoulou

cs.LGAug 24, 2026

Counterfactual Transition Graphs: Evaluating Cross-Class Transition Quality

Authors: Syed Muhammad Hamza Zaidi, Szymon Bobek, Grzegorz J. Nalepa, Myra Spiliopoulou

Organizations: Otto-von-Guericke University Magdeburg, Magdeburg, Germany · Jagiellonian University, Krakow, Poland · Center for Applied Intelligence Systems Research, School of ITE, Halmstad University, Halmstad 30118, Sweden

Abstract

Counterfactual (CF) explanations for time-series classifiers are usually evaluated one example at a time: what minimal edit flips this single window's prediction? We argue that the more informative question for diagnostic interpretability is structural: how does the classifier connect its own classes to each other? We propose a counterfactual transition graph (CGT) in which each node is a class and each edge weight is the CF reliability of the transition from one prototype to another under a proximity aware retrieval sweep. On a six-class hand-movement task, we induce a CGT that reveals a non-trivial topology, which is not predicted by the binary confusion matrix: it shows that counterfactual reachability does not align with classifier accuracy and even runs counter to it (Spearman $ρ=-0.37$ over the 15 pairs), i.e. the boundaries the classifier separates most confidently are among those an in-distribution edit can least often cross. Our framework is method agnostic, i.e. any CF-explainers can be used. Presently, we use it to juxtapose replacement-based CFs with gradient-based CFs; gradient-based methods reach almost any class by stepping off the data manifold, while replacement-based methods stay on it and fail on precisely the rigid boundaries.

Figures & tables

Figure 1: Transitions of a hand’s joints from the class Fingertip-Touch ( $T_{2}$ ) to the class Clothes-Peg ( $T_{1}$ ): each block shows four representative joints (original: blue, counterfactual: orange) and the class probabilities before and after the edit. The replacement-based generators ( gacp , gacp_context ) do not flip the prediction, while gacp_context produces physiologically implausible oscillations; the gradient-based generators ( nepo , residual ) flip the label with a small but off-manifold edit.

Figure 2: Workflow of the TGNN classifier, summarised from [ 22 ] : the temporal sequence of anatomical hands per gesture (subfig 1) are encoded spatially with graph convolutions, each step separately (subfig 2); biLSTM is used for temporal encoding (subfig 3); the MLP-head does downstream classification

Pair	Acc	$w$	Plaus.	GACP	GACP-Ctx	NEPO	Residual
$T_{1},T_{2}$	0.985	0.08	10.9	0.00	0.02	0.80	0.53
$T_{1},T_{3}$	0.988	0.08	15.9	0.05	0.01	0.33	0.80
$T_{1},T_{4}$	0.989	0.11	23.5	0.04	0.01	0.87	0.93
$T_{2},T_{3}$	0.987	0.12	8.5	0.04	0.02	1.00	0.80
$T_{4},T_{5}$	0.972	0.26	7.2	0.20	0.21	0.93	0.47
$T_{1},T_{6}$	0.933	0.26	7.0	0.17	0.22	0.73	1.00

Table 1: Quantities on the edges of the transition graph, one row per class pair, sorted by increasing CP-proximity

w

. “Acc” is accuracy (1-classifier difficulty); “Plaus.” is the mean plausibility (lower is more realistic); the last four columns give per-generator validity.

Figure 3: The counterfactual transition graph computed separately for each generator. Nodes are classes; each edge weight (colour and thickness) is the mean validity of that boundary. The replacement generators (GACP, GACP-Context; top) leave every $T_{1}$ (Clothes-Peg) boundary thin and dark and recover a sparse, structured topology, whereas the gradient generators (NEPO, Residual; bottom) flood almost every boundary, reaching all classes by leaving the data manifold. Pooling the four panels gives the edge weights $w$ analysed in Table 1 .

Figure 4: Classifier difficulty (grey) vs. CF rigidity (orange) per class pair after min-max rescaling of each quantity independently. For both quantities, values closer to zero are better - easier separation, resp. easier class flipping. The long top connectors ( $T_{1},T_{2}$ ; $T_{1},T_{3}$ ; $T_{1},T_{4}$ ) are boundaries the classifier separates almost perfectly yet a realistic edit almost never crosses; $T_{1},T_{5}$ inverts this.

Counterfactual Explanations

Counterfactual explanations show how changing an input could alter a model’s prediction, supporting model understanding, auditing, and actionable recourse.

See all 117 papers

A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit
Sep 4, 2026Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1Counterfactual Explanations Graph Counterfactual Explanations
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece
FCx: An algorithm for finding Feasible Counterfactual Explanations
Sep 16, 2026Kleopatra Markou, Vana Kalogeraki, Dimitrios GunopulosCounterfactual Explanations
National and Kapodistrian University of Athens, Department of Informatics and Telecommunications, Greece · Athens University of Economics and Business, Department of Informatics, Greece
What-If Explanations Over Time: Counterfactuals for Time Series Classification
Mar 29, 2026Udo Schlegel, Thomas SeidlGraph Counterfactual Explanations Counterfactual Explanations
LMU Munich, Germany · Munich Center for Machine Learning (MCML), Germany

Sep 4, 2026J/K move · Enter open · S save

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

Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece

Counterfactual Explanations Graph Counterfactual Explanations GNN Explainability Explainability Evaluation

Open paper AskPDF arXiv

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.

Abstract

Counterfactual Explanations

Explore similar work

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

FCx: An algorithm for finding Feasible Counterfactual Explanations

What-If Explanations Over Time: Counterfactuals for Time Series Classification