Real-world decision-making in public health and social science can greatly benefit from predictive models, yet translating predictions into effective interventions requires explaining the model behavior. While Graph Neural Networks (GNNs) are well-suited for modeling relational data, existing explanation methods largely operate at the node level and fall short of supporting actionable, network-level intervention design. Existing counterfactual GNN explainers, such as CF-GNNExplainer and CF2, rely on continuous mask optimization over features and edges, which implicitly assume feasible edge manipulation, may allocate effort to immutable or non-actionable attributes, and incur substantial computational overhead. Further, the method of arriving at the explanation itself is difficult to explain to a domain specialist who is not an AI expert. Can simple methods generate good explanations? To explore this, we reframe counterfactual explanation as an intervention design problem. At the local level, we generate counterfactuals via a greedy search that directly identifies minimal, actionable changes to node features and neighbor-level conditions. We derive conditions under which the greedy search provides guarantees, and empirically show that these conditions are approximately met. These counterfactuals are converted into interpretable rules suitable for real-world intervention. At the network level, we formulate intervention selection as a Disjunctive Normal Form (DNF) coverage problem under a budget constraint, which is nondecreasing and approximately submodular, enabling a greedy algorithm with theoretical guarantees. Experiments on synthetic graphs and real-world suicide risk networks demonstrate that our approach produces scalable, cost-effective intervention strategies with significantly improved efficiency over mask-based counterfactual methods.
Figures & tables
Figure 1. Two-phase framework: Phase 1 generates node-level counterfactual explanations via iterative greedy search over node features, edge modifications, and neighbor feature perturbations. Phase 2 aggregates local clauses into a global intervention policy using submodular optimization under a budget constraint. Two-phase pipeline diagram. Phase 1 takes a graph and a trained GNN and runs an iterative greedy search over node features, edge modifications, and neighbor feature perturbations to produce a per-node counterfactual clause. Phase 2 aggregates these clauses into a global DNF intervention policy by greedy submodular maximization of node coverage under a budget constraint.
Figure 2. Empirical validation of relaxed additivity and approximate submodularity assumptions. The distributions of additivity ratios (left) and modularity ratios (right) are tightly concentrated around 1, suggesting that the objective function closely satisfies near-additive and near-modularity properties, thereby supporting the theoretical guarantees. Two histograms. The left panel shows the distribution of additivity ratios and the right panel the distribution of modularity ratios, measured over 5000 randomly sampled pairs of disjoint intervention sets. Both distributions are sharply peaked near a value of one, indicating that the objective is close to additive and exhibits diminishing returns.
Dataset
#Graph
#Ave n
#Ave e
#Class
#Feat
Task
Explanation Benchmark Datasets
BA-Shapes
1
700
4100
4
–
node
Tree-Cycles
1
871
1950
2
–
node
Mutag 0
2301
31.74
32.54
2
14
graph
Intervention Datasets
Military
1
241
258
2
48
node
Table 1. Summary statistics of explanation and intervention datasets. The benchmark datasets (top) are used for evaluating explanation quality with ground-truth motifs, while the intervention datasets (bottom) are used for assessing counterfactual-based intervention design. Synthetic datasets are generated at multiple scales to control graph size and feature dimensionality. NF and NO denote the Neighbor-Feature and Neighbor-Only variants, respectively.
Models
BA-Shapes
Tree-Cycles
Mutag 0
Pr%
#exp
Time(s)
Pr%
#exp
Time(s)
Pr%
#exp
Time(s)
GNNExplainer
60.08
6.0
0.265
68.06
6.0
0.204
59.71
15.0
0.257
CF-GNNExplainer
67.19
5.79
0.232
87.40
3.44
0.186
66.09
7.72
0.221
CF 2
73.15
6.21
3.77
84.92
5.81
1.81
65.28
14.95
2.80
CF-Greedy (Ours)
78.87
1.20 (MIP)
0.037
87.50
1.40 (MIP)
0.033
92.59
1.19 (MIP)
0.079
Table 2. Evaluation of different explanation methods against ground-truth. “Pr%”, “#exp”, and “Time” denote Precision, explanation size, and average inference time per instance (in seconds). For our method, #exp is measured by the Minimum Information Perturbation (MIP) , defined as the smallest number of modifications required to flip the model’s prediction. The best and second-best results for Pr% and Time are highlighted in bold and underline .
Dataset
Method
CF
CF 2
Ours-Greedy
AUCC
Cov.(DNF)
Time
AUCC
Cov.(DNF)
Time
AUCC
Cov.(DNF)
Time
Rand.
Freq.
DNF
Rand.
Freq.
DNF
Rand.
Freq.
DNF
Real
Military
0.348
0.360
0.344
37.4%
129.090
0.605
0.680
0.912
97.6%
348.258
0.901
0.933
0.961
100.0%
8.533
Youth
/
/
/
/
/
0.273
0.294
0.664
75.96%
443.399
0.303
0.341
0.739
78.88%
10.448
Synthetic
Neighbor-Feature
N100-E150-D10
0.454
0.462
0.275
33.330%
44.105
0.416
0.649
0.811
97.780%
130.399
0.671
0.858
0.922
100.000%
2.473
Table 3. Comparison of different counterfactual explanation methods on real-world and synthetic datasets. AUCC denotes the area under the coverage curve (in %), while Cov. represents the final coverage (in %). Time reports the average runtime in seconds. The best, second-best, and worst results for DNF-based AUCC, Coverage, and Time are highlighted in bold , underline , and red , respectively.
Figure 3. Runtime scalability of CF-Greedy, CF, and CF 2 on synthetic graphs with 100 to 25,600 nodes. Line plot of runtime in seconds against the number of nodes, on logarithmic axes, for CF-Greedy, CF, and CF-squared on synthetic graphs ranging from 100 to 25,600 nodes. CF and CF-squared grow steeply and stop before the largest sizes, while CF-Greedy grows far more slowly and continues across the full range.
Counterfactual Clauses
Interpretation
1. race_7 → 1 (race: other → multiracial) +30 2. soldier_1 → 1 ∧ career_intent_1 → 1 (satisfaction: not satisfied → satisfied; career plan: other → stay until retirement) +13 3. xˉcareer_intent_3>0.50 (peer condition: > 50% of peers staying beyond obligation) +2 4. race_5 → 1 (race: other → White) +2 5. race_2 → 1 (race: other → Asian) +1 6. soldier_1 → 1 (satisfaction: not satisfied → satisfied) +1 7. race_3 → 1 (race: other → Black) +1 8. race_2 → 1 ∧ soldier_1 → 1 ∧xˉcareer_intent_1>0.33 (race: other → Asian; satisfaction: not satisfied → satisfied; > 33% peers retiring) +1
1. Racial identity as dominant correlate. Race is the single strongest predictor of the model’s risk classification: changing racial category alone flips 59% (30/51) of at-risk predictions (Clause 1), and clauses involving race (Clauses 1, 4–5, 7–8) together cover 69% (35/51). Multiple racial categories appear across clauses, revealing that suicide risk predictions are strongly stratified along racial lines. This is not an actionable target, but may highlight known disparities across races ( Brenner et al., 2023 ) . 2. Career commitment as a protective factor. Career intent—particularly long-term military commitment—combined with soldier satisfaction emerges as the second most influential factor, covering 14 additional individuals (Clauses 2, 6). These suggest that a clear sense of purpose and professional belonging are associated with lower predicted risk. 3. Peer environment effects. Several clauses involve neighbor-mean thresholds for peers’ career intent (Clauses 3, 8), indicating that the social composition of an individual’s peer network influences the model’s predictions beyond individual attributes.
Table 4. Unconstrained CF-GREEDY results on the Military dataset (all features mutable) – may not be applicable for intervention design. Left: selected clauses with coverage and cost. Right: human-readable interpretation of the key risk and protective factors identified.
Counterfactual Clauses
Proposed Interventions
1. career_intent_1 → 1 (career plan: other → stay until retirement) +22 2. soldier_1 → 1 (satisfaction: not satisfied → satisfied) +13 3. xˉauditc_1>0.33 (peer condition on peers’ alcohol-use score) +4 4. career_intent_6 → 1 (career plan: other → definitely leaving) +4 5. soldier_1 → 1 ∧ career_intent_1 → 1 (satisfaction: not satisfied → satisfied; career: other → stay until retirement) +4 6. career_intent_3 → 1 ∧ phq9_total → 0 (career: other → staying beyond obligation; depression: symptomatic → none) +2 7. soldier_3 → 1 ∧ career_intent_4 → 1 (satisfaction: satisfied → dissatisfied; career: other → undecided) +1 8. married → 1 ∧xˉcareer_intent_1>0.50 (unmarried → married; > 50% peers plan to retire) +1
Tier 1: Career development programs (Clauses 1–2, 4–5; covers 84%). Career intent is the most actionable protective factor. Promoting long-term military commitment—through career counseling, re-enlistment decision support, and skills-to-civilian mapping—combined with soldier-satisfaction building addresses the large majority of at-risk individuals. This suggests implementing mandatory career development workshops targeting at-risk personnel. Tier 2: Clinical & psychosocial support (Clauses 6, 8; extends coverage to 90%). Reducing depression severity (PHQ-9 → 0) and relationship stability support (marriage) provide additional coverage. Recommended: stepped-care depression treatment and relationship enrichment programs (e.g., PREP for Strong Bonds). Tier 3: Network-level peer interventions (Clauses 3, 7–8; covers 100%). The remaining individuals require interventions involving peer composition: embedding at-risk individuals among career-committed, stably married peers. Recommended: battle-buddy pairing with career-motivated soldiers, assignment to units with higher career commitment concentrations, and peer mentoring programs.
Table 5. Constrained CF-GREEDY results on the Military dataset (demographic features immutable). Left: selected clauses with coverage and cost. Right: human-readable intervention strategies derived from clauses.
In this study, we propose a novel pipeline for generic, model-agnostic, local-level counterfactual explainability in graph neural networks (GNNs). Although counterfactual explainers capable of both adding and removing edges have emerged in recent years, the need for generic and efficient solutions remains unmet, particularly concerning qualitative explanation generation. Our approach couples progress in factual explainability with missing edge prediction models rooted in link prediction research, in order to enhance the quality, robustness and intuitiveness of explanations. A multi-faceted experimental analysis conducted on real-world and synthetic graph classification benchmarks, both binary and multi-label, demonstrates the advancements in comparison to state-of-the-art baselines across diverse metrics.
Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH), Heraklion, Greece · Computer Science Department, University of Crete, Greece
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.
Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece
Explainable Artificial Intelligence aims to make black-box models more trustworthy by presenting, in a human-understandable manner, the elements that lead to the model's output. This involves both (i) identifying components and connections with genuine causal influence on outputs and (ii) translating such structures into an interpretable representation. For the former, we introduce CIExplainer, a novel perturbation-based method grounded in causal inference for explaining Graph Neural Networks (GNNs). CIExplainer identifies the subgraph with the highest causal effects on GNN predictions using the Potential Outcome Framework. We evaluate and compare CIExplainer on various GNN architectures (GCN, GraphSAGE, GAT, GIN) and datasets. To bridge subgraph explanations with human interpretability, we further propose G2TeXplainer, a method that transforms causal subgraphs into natural language explanations that capture both feature-level and relational information.
Francisco Caldas, Sahil Satish Kumar, Ruben Belo +1
NOVA LINCS, NOVA School of Science and Technology, Lisbon, Portugal