Generating Intervention Hypotheses using Explainable Explanations on Graphs: G2I, a Two-Stage Greedy Framework

# Generating Intervention Hypotheses using Explainable Explanations on Graphs: G2I, a Two-Stage Greedy Framework
Source: [https://arxiv.org/html/2608.23835](https://arxiv.org/html/2608.23835)
Mulin TianAffiliation:University of Southern California,Los Angeles,California,USAemail:[mulintia@usc\.edu](mailto:[email protected])Ajitesh SrivastavaAffiliation:Northeastern University,Charlotte,North Carolina,USAemail:[aji\.srivastava@northeastern\.edu](mailto:[email protected])

© none

###### Abstract\.

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\.

###### Keywords:

Graph Neural Networks, Explainability, Intervention Generation\.

## 1\.Introduction

In social and health sciences, interventions are performed to improve individual outcomes\. These include identifying who could benefit from what kind of intervention\. For instance, to reduce the risk of suicide, the intervention may be designed to target those who could be at a higher risk based on certain historical, personal, or social attributes\([Christakis and Fowler, 2009](https://arxiv.org/html/2608.23835#bib.bib15);[Jackson, 2008](https://arxiv.org/html/2608.23835#bib.bib16)\)\. Yet, identifying which individuals are at risk, and critically, why they are at risk, remains a significant challenge\. Graph Neural Networks \(GNNs\)\([Wu et al\., 2021](https://arxiv.org/html/2608.23835#bib.bib36)\)have emerged as powerful tools for modeling social networks, as they can effectively encode both node\-level attributes and the relational structure between individuals\. This capability makes GNNs particularly suitable for predicting processes, where an individual’s outcomes are shaped not only by personal characteristics but also by their social connections\. However, beyond good accuracy, an explanation is needed to understand the model behavior\.

Explanations as hypotheses: Several prior works, including GNNExplainer\([Ying et al\., 2019](https://arxiv.org/html/2608.23835#bib.bib7)\), CF\-GNNExplainer\([Lucic et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib14)\), CF2\-GNNExplainer\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\), PGExplainer\([Luo et al\., 2020](https://arxiv.org/html/2608.23835#bib.bib27)\), SubgraphX\([Yuan et al\., 2021](https://arxiv.org/html/2608.23835#bib.bib28)\), and RCExplainer\([Bajaj et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib29)\), explain node\-level predictions by identifying the node features and edges that are most influential to a target node\. In particular, they can provide counterfactual explanations\([Wachter et al\., 2018](https://arxiv.org/html/2608.23835#bib.bib26);[Verma et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib30)\)– what minimal change in data can lead to a change in classification\. These counterfactual explanations can be seen as ‘intervention hypotheses’, i\.e\., if we are able to change certain attributes, it will change outcomes\. Recent work in Economics has suggested the idea of using machine learning counterfactual explanations as a tool for hypothesis generation\.\([Ludwig and Mullainathan, 2024](https://arxiv.org/html/2608.23835#bib.bib6)\)\. However, realizing this in real\-world relational data for interventions is challenging due to the following reasons\. \(1\) Existing approaches provide node\-level explanations and it is not clear how to convert it into population\-level intervention\. \(2\) Existing methods may not directly support explanations that lead to actionable and cost\-effective prevention strategies\. For example, an explanation for a node may suggest deleting an edge, which may not be possible or ethical in real networks, and does not provide population\-level insights\. \(3\) Most importantly,the explanation methods themselves are difficult to explainto a non\-ML expert\. We argue that in cross disciplinary collaborations, the method for generating explanation of a “black\-box” model should not itself be a black\-box and instead should be easy to explain to a non\-ML expert\.

To address these limitations, we propose to use forms of greedy algorithms at two levels \(G2I – Graph to Intervention\)\. At the “local”\-level, we perturb both structural and feature components of a network, greedily building a subset of features \(for individual and their neighborhood\) to maximize the shift in outcomes for node classification\. At “global”\-level, we construct an intervention\-design problem\. Given the local counterfactual explanations, how to design an intervention targeting a subset of features \(individual and neighborhood\-level\) to maximize improved outcomes\. Our G2I framework consistently outperforms prior explanation methods, including CF\([Lucic et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib14)\)and CF2\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\), in both the first\-stage explanation evaluation and the second\-stage intervention generation tasks\. Moreover, G2I achieves up to two\-orders of magnitude speedup compared to these methods\. We summarize the novelty and benefits of our method compared to prior works below\.

Explainability with Actionability:Our framework provides counterfactual explanations that explicitly characterize how changes to node attributes and social connections would alter a node’s predicted risk, moving beyond static importance scores toward explanations that reflect causal and contrastive reasoning\. By restricting feasible perturbations to features and neighborhoods that align with real\-world intervention constraints, we enable practitioners to understand and design and test interventions\.

Generalizable:Due to the greedy approach, our method does not require dataset\-specific hyperparameter tuning and maintains stable performance across different datasets and structural settings\.

Scalability:Compared to traditional mask\-based optimization methods, our approach scales to significantly larger graphs under the same hardware constraints, as it only requires storing the original graph and a pre\-trained GNN model, while prior methods require substantial memory overhead by maintaining mask variables of comparable size\. This advantage is critical for population\-level intervention design on large\-scale social networks\.

## 2\.Background and Related Work

GNN Explanation Methods\.GNNExplainer\([Ying et al\., 2019](https://arxiv.org/html/2608.23835#bib.bib7)\)learns a soft mask over edges and node features to identify a subgraph that is sufficient to preserve the original GNN prediction\. However, it does not model necessity, as it does not test whether removing the identified components would change the outcome\. Consequently, the explanations are descriptive but not counterfactual or actionable\. CF\-GNNExplainer\([Lucic et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib14)\)generates counterfactual explanations by identifying minimal edge deletions that flip a node’s prediction, explicitly capturing necessity\. However, it does not enforce sufficiency, since the remaining subgraph is not required to reproduce the original prediction\. The method is further limited to structural perturbations and ignores feature–structure interactions\.CF2\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\)explicitly incorporates both sufficiency and necessity by jointly optimizing factual and counterfactual objectives\. It ensures that the selected subgraph is sufficient to maintain the prediction while also being necessary such that its removal changes the outcome\. This joint formulation yields explanations that are more balanced and complete than methods focusing on only one criterion\.

Despite these advances, all three methods rely on mask\-based optimization procedures, which introduce an additional step of black\-box training\. The explanation is produced as the outcome of optimizing continuous mask variables under task\-specific loss functions, rather than through transparent, interpretable reasoning steps\. Consequently, the explanation process itself remains unclear and difficult to justify to practitioners outside Computer Science, which may limit its usability in real\-world decision\-making settings\.

Social Interventions\.Peer\-based interventions leverage social connections to enable individuals within a community to influence and support one another, and have been widely used to promote positive outcomes such as HIV prevention, substance use reduction\([Valente et al\., 2007](https://arxiv.org/html/2608.23835#bib.bib34)\), and mental health support\([Davidson et al\., 2006](https://arxiv.org/html/2608.23835#bib.bib35)\)\. These strategies rely on trust and shared lived experiences to facilitate meaningful behavioral change\. This approach is crucial in underserved communities due to the mistrust in formal institutions like healthcare systems, social services and law enforcement\. This skepticism often stems from negative past interactions within these systems\.\([Fest, 2013](https://arxiv.org/html/2608.23835#bib.bib2);[Dworsky and Courtney, 2009](https://arxiv.org/html/2608.23835#bib.bib1)\)\. As a result, individuals are more likely to seek support from peers rather than from traditional providers\. To support these peer\-driven methods, predictive models must go beyond classification to offer clear, interpretable insights\. Providing better understanding towhysomeone is at risk is vital in providing timely, actionable community\-rooted interventions\.

Real\-world interventions designed to address population\-level challenges are widely used, such as controlling the spread of infectious diseases\([Pastor\-Satorras et al\., 2015](https://arxiv.org/html/2608.23835#bib.bib17)\)or mitigating misinformation diffusion\([Vosoughi et al\., 2018](https://arxiv.org/html/2608.23835#bib.bib18)\)in social systems\. These problems are inherently collective, as human behavior and decision\-making are strongly influenced by interactions with others in a social network\([Christakis and Fowler, 2009](https://arxiv.org/html/2608.23835#bib.bib15);[Jackson, 2008](https://arxiv.org/html/2608.23835#bib.bib16)\)\. Therefore, when designing interventions at the population level, it is necessary to explicitly account for the underlying network structure rather than treating individuals as independent\.

In practice, intervention strategies are often based on simple heuristic rules of the form “if X, then Y,” such as targeting individuals with certain risk factors for specific treatments or policies\. However, such approaches are limited by human bias\([Tversky and Kahneman, 1974](https://arxiv.org/html/2608.23835#bib.bib37)\)and partial knowledge, as they rely on what practitioners can infer from available data or prior experience\([Ludwig and Mullainathan, 2024](https://arxiv.org/html/2608.23835#bib.bib6)\)\. At the same time, real\-world populations are highly heterogeneous\([Athey and Imbens, 2016](https://arxiv.org/html/2608.23835#bib.bib19)\), and the factors driving outcomes vary across individuals and their social contexts\. As a result, effective intervention strategies need to be personalized and context\-dependent, rather than relying on a single uniform rule applied to all individuals\.

Explanations as Hypothesis Generators\.Recent work notes the role of machine learning as a tool for hypothesis generation rather than just prediction\([Ludwig and Mullainathan, 2024](https://arxiv.org/html/2608.23835#bib.bib6);[Mullainathan and Spiess, 2017](https://arxiv.org/html/2608.23835#bib.bib33)\)\. In particular, they argue that data\-driven models can uncover patterns that may guide the design of interventions, especially in complex social systems where traditional theory\-driven approaches are limited\([Lazer et al\., 2009](https://arxiv.org/html/2608.23835#bib.bib38);[Lazer et al\., 2020](https://arxiv.org/html/2608.23835#bib.bib39)\)\.

However, generating actionable hypotheses from model outputs remains challenging\. In practice, hypothesis generation is often informal and relies heavily on human interpretation, making it difficult to systematically identify interventions that are both effective and scalable\. Moreover, the space of possible interventions is combinatorial, especially in networked settings, where both individual attributes and social interactions jointly influence outcomes\. Building on these observations, a natural direction is to formalize hypothesis generation as an optimization problem\. Given a limited intervention budget, one would seek to construct intervention strategies that maximize population\-level impact while satisfying practical requirements such as interpretability, actionability, and computational efficiency\. However, existing work has not provided a unified framework that simultaneously addresses these aspects in graph\-based intervention design\.

![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.](https://arxiv.org/html/2608.23835v1/framework.png)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\.
## 3\.Method and Approximation Guarantees

The proposed framework for intervention design on graph\-structured data consists of three primary components: \(1\) a graph\-based predictive model, \(2\) a node\-level counterfactual search to identify node\-specific interventions, and \(3\) a group\-level optimization phase to select a robust set of intervention policies\.

### 3\.1\.Predictive Backbone

We employ a Graph Convolutional Network\([Kipf and Welling, 2017](https://arxiv.org/html/2608.23835#bib.bib11)\)\(GCN\) as the predictive model for node\-level risk estimation\. To address high\-dimensional input features, we apply a fixed Principal Component Analysis \(PCA\)\([Jolliffe and Cadima, 2016](https://arxiv.org/html/2608.23835#bib.bib24)\)projection prior to graph convolution, reducing feature dimensionality while preserving interpretability\. The PCA projection matrix is pre\-computed and remains non\-trainable, ensuring a deterministic mapping between the original feature space and the reduced embedding space for consistent counterfactual analysis\.

The GCN layers propagate information through standard neighborhood aggregation with symmetric normalization\. Our framework is model\-agnostic and can be readily extended to other GNN architectures such as GraphSAGE\([Hamilton et al\., 2018](https://arxiv.org/html/2608.23835#bib.bib13)\)or GAT\([Veličković et al\., 2018](https://arxiv.org/html/2608.23835#bib.bib12)\)\.

Algorithm 1Node\-level Counterfactual Clause Generation1:Graph

GG, target node

vv, GNN model

ff, maximum number of interventions

KK, edge intervention modeedge\_mode

2:Node\-level counterfactual clause

cvc\_\{v\}
3:Initialize

cv←∅c\_\{v\}\\leftarrow\\emptyset, current graph

Gmod←GG\_\{\\text\{mod\}\}\\leftarrow G
4:while

\|cv\|<K\|c\_\{v\}\|<Kand

f⁡\(v,Gmod\)\>0\.5f\(v,G\_\{\\text\{mod\}\}\)\>0\.5do

5:Identify candidate interventions

IIbased onedge\_mode

6:Select

i∗←arg⁡maxi∈I⁡\(f⁡\(v,Gmod\)−f⁡\(v,Gmod⊕\{i\}\)\)i^\{\*\}\\leftarrow\\arg\\max\_\{i\\in I\}\\Big\(f\(v,G\_\{\\text\{mod\}\}\)\-f\\big\(v,G\_\{\\text\{mod\}\}\\oplus\\\{i\\\}\\big\)\\Big\)
7:ifmarginal improvement

\>0\>0then

8:

cv←cv∪\{i∗\}c\_\{v\}\\leftarrow c\_\{v\}\\cup\\\{i^\{\*\}\\\}
9:

Gmod←Gmod⊕\{i∗\}G\_\{\\text\{mod\}\}\\leftarrow G\_\{\\text\{mod\}\}\\oplus\\\{i^\{\*\}\\\}
10:else

11:break

12:Convert neighbor\-specific interventions in

cvc\_\{v\}into threshold\-based neighbor conditions

13:return

cvc\_\{v\}

### 3\.2\.Node\-level Counterfactuals

#### 3\.2\.1\.Neighborhood Feature Inclusion

Unlike traditional counterfactual methods that focus solely on the features of the target node, our approach explicitly incorporates the graph topology into the intervention space\. The scope of allowable interventions is controlled by anedge\_modeparameter, which defines how structural and neighborhood information is utilized:

Feature Only \(none\)\.Interventions are restricted to perturbations of the intrinsic features of the target nodevv\.

Edge Modification \(edges\)\.To ensure real\-world feasibility, our algorithm avoids treating structural modifications as literal relationship assignments \(e\.g\., forcing a friendship\)\. Instead, potential edge additions or removals are dynamically evaluated and converted into actionable neighborhood\-level feature distribution constraints\. Specifically, whenever an edge edit significantly shifts the target node’s 1\-hop neighborhood feature distribution, it is abstracted into a continuous threshold rule \(e\.g\., requiring the mean of a supportive featurejjamong peers to exceedθ\\theta\)\. By translating deterministic edge edits into generalized feature\-density constraints, the resulting interventions represent realistic public health programs and establish a rigorous, measurable cost model\.

Neighbor Feature Perturbation \(edge\_features\)\.The algorithm allows modifications to the features of the immediate neighbors ofvv, enabling the modeling of peer effects on the predicted risk ofvv\. Similar to the Edge Modification approach, the rule derived from such changes focuses on changes in mean of that feature in the node’s neighborhood\.

#### 3\.2\.2\.Generating Local Clauses

We employ an iterative greedy search procedure \(Algorithm[1](https://arxiv.org/html/2608.23835#alg1)\) to construct local counterfactual explanations\. At each iteration, the algorithm selects the intervention—either a feature perturbation, an edge modification, or a neighbor feature change—that maximizes the reduction in the predicted probability for the target node\.

Crucially, once a set of topological or neighborhood\-level interventions is identified, these changes are transformed into*Neighbor Conditions*to ensure that the resulting explanation remains both interpretable and generalizable\. Specifically, when an intervention alters the neighborhood of nodevv\(e\.g\., through edge additions/removals or neighbor feature perturbations\), we compute the induced change in the mean feature distribution of the one\-hop neighborhood\. This change is expressed as a threshold\-based condition:

\(1\)N⁡\(featurej\)∈\[op,threshold\],N\(\\text\{feature\}\_\{j\}\)\\in\[\\text\{op\},\\text\{threshold\}\],whereN⁡\(⋅\)N\(\\cdot\)denotes the mean over the one\-hop neighborhood, andop∈\{≥,≤\}\\text\{op\}\\in\\\{\\geq,\\leq\\\}specifies the direction of the constraint\. For example, adding a peer with high mindfulness to the neighborhood ofvvis abstracted as the mean value of a mindfulness feature within the neighborhood exceeds a predefined threshold\.

### 3\.3\.Approximation 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.](https://arxiv.org/html/2608.23835v1/figures/approx_guarantees.png)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\.The node\-level counterfactual search \(Algorithm[1](https://arxiv.org/html/2608.23835#alg1)\) relies on a greedy strategy that selects, at each step, the single intervention yielding the largest reduction in predicted risk\. A natural question arises:*does greedy optimization provide any quality guarantee on the resulting intervention set?*

The answer is yes, if the objective functionff, which measures the cumulative risk reduction achieved by a set of interventions, satisfies certain properties\. For instance:

- •Submodular\(f⁡\(A∪\{x\}\)−f⁡\(A\)≥f⁡\(B∪\{x\}\)−f⁡\(B\)f\(A\\cup\\\{x\\\}\)\-f\(A\)\\geq f\(B\\cup\\\{x\\\}\)\-f\(B\)forA⊆BA\\subseteq B\): Interventions exhibit*diminishing marginal returns*– the benefit of each additional intervention decreases as more interventions have already been applied\. Under this condition, classical results guarantee that greedy achieves a\(1−1/e\)\(1\-1/e\)\-approximation for cardinality\-constrained maximization\([Nemhauser et al\., 1978](https://arxiv.org/html/2608.23835#bib.bib21)\), and a12\\frac\{1\}\{2\}\-approximation under knapsack constraints\([Sviridenko, 2004](https://arxiv.org/html/2608.23835#bib.bib22)\)\. Guarantees exist, even ifffis approximately submodular\([Das and Kempe, 2018](https://arxiv.org/html/2608.23835#bib.bib5);[Krause and Golovin, 2014](https://arxiv.org/html/2608.23835#bib.bib32)\)\.
- •Approximately additive\(f⁡\(A∪B\)≈f⁡\(A\)\+f⁡\(B\)f\(A\\cup B\)\\approx f\(A\)\+f\(B\)\): Interventions act roughly independently\. We formalize this via a relaxed additivity and prove that this also provides reasonable guarantees in Theorem[3\.1](https://arxiv.org/html/2608.23835#S3.Thmtheorem1)\.

###### Theorem 3\.1\.

Letffbe a set function satisfying relaxed additivity with slack parameterα∈\[0,1\)\\alpha\\in\[0,1\):

\(1−α\)​\(f⁡\(A\)\+f⁡\(v\)\)≤f⁡\(A∪v\)≤\(1\+α\)​\(f⁡\(A\)\+f⁡\(v\)\)\(1\-\\alpha\)\(f\(A\)\+f\(v\)\)\\leq f\(A\\cup v\)\\leq\(1\+\\alpha\)\(f\(A\)\+f\(v\)\)for all setsAAandv∉Av\\notin A, such that

\(i\)f⁡\(∅\)=0f\(\\emptyset\)=0

\(ii\)f⁡\(A\),f⁡\(v\),f⁡\(A∪v\)≥0f\(A\),f\(v\),f\(A\\cup v\)\\geq 0

\(iii\)f⁡\(A∪v\)≥f⁡\(A\)f\(A\\cup v\)\\geq f\(A\)\.

Then, the cumulative scorefkf\_\{k\}obtained afterkkgreedy steps of Algorithm[1](https://arxiv.org/html/2608.23835#alg1)satisfies:

fk≥γk​fk∗whereγk≥1−α2​\(1\+α\)k−1−\(1\+α\)\.f\_\{k\}\\geq\\gamma\_\{k\}f\_\{k\}^\{\*\}\\quad\\text\{where\}\\quad\\gamma\_\{k\}\\geq\\frac\{1\-\\alpha\}\{2\(1\+\\alpha\)^\{k\-1\}\-\(1\+\\alpha\)\}\.

###### Proof Sketch\.

Letfk=f⁡\(Sk\)f\_\{k\}=f\(S\_\{k\}\)be the score afterkkgreedy steps, andfk∗f\_\{k\}^\{\*\}the optimal value\. Supposefk≥γk​fk∗f\_\{k\}\\geq\\gamma\_\{k\}f\_\{k\}^\{\*\}\. From the relaxed additivity assumption, we have:

fk\+1≥\(1−α\)​\(fk\+vk\+1∗\)andfk∗≤\(1\+α\)​\(fk\+vk\+1∗\)\.f\_\{k\+1\}\\geq\(1\-\\alpha\)\(f\_\{k\}\+v\_\{k\+1\}^\{\*\}\)\\quad\\text\{and\}\\quad f\_\{k\}^\{\*\}\\leq\(1\+\\alpha\)\(f\_\{k\}\+v\_\{k\+1\}^\{\*\}\)\.Using the lower bound forfk\+1f\_\{k\+1\}, we can write:

fk∗≤\(1\+α\)​\(fk\+11−α\)\.f\_\{k\}^\{\*\}\\leq\(1\+\\alpha\)\\left\(\\frac\{f\_\{k\+1\}\}\{1\-\\alpha\}\\right\)\.
Substitutefk≥γk​fk∗f\_\{k\}\\geq\\gamma\_\{k\}f\_\{k\}^\{\*\}into the inequality:

fk∗≤fk​\(1\+αγk−1\)\+1\+α1−α​fk\+1\.f\_\{k\}^\{\*\}\\leq f\_\{k\}\\left\(\\frac\{1\+\\alpha\}\{\\gamma\_\{k\}\}\-1\\right\)\+\\frac\{1\+\\alpha\}\{1\-\\alpha\}f\_\{k\+1\}\.
Assuming monotonicity \(fk\+1≥fkf\_\{k\+1\}\\geq f\_\{k\}\) and usingf∗\>fk\+1f^\{\*\}\>f\_\{k\+1\}, we derive a recurrence relation for the approximation factorγk\\gamma\_\{k\}:

1γk\+1≤\(1\+α\)​\(1γk\+α1−α\)\.\\frac\{1\}\{\\gamma\_\{k\+1\}\}\\leq\(1\+\\alpha\)\\left\(\\frac\{1\}\{\\gamma\_\{k\}\}\+\\frac\{\\alpha\}\{1\-\\alpha\}\\right\)\.
Definetk=1γk\+1\+α1−αt\_\{k\}=\\frac\{1\}\{\\gamma\_\{k\}\}\+\\frac\{1\+\\alpha\}\{1\-\\alpha\}\. Then above inequality can be rewritten as

tk\+1≤\(1\+α\)​tk⇒tk≤t1​\(1\+α\)k−1\.t\_\{k\+1\}\\leq\(1\+\\alpha\)t\_\{k\}\\Rightarrow t\_\{k\}\\leq t\_\{1\}\(1\+\\alpha\)^\{k\-1\}\.
Ifγ1=1\\gamma\_\{1\}=1, then:

1γ1=1⇒t1=1\+1\+α1−α=21−α\.\\frac\{1\}\{\\gamma\_\{1\}\}=1\\Rightarrow t\_\{1\}=1\+\\frac\{1\+\\alpha\}\{1\-\\alpha\}=\\frac\{2\}\{1\-\\alpha\}\.
Thus:

tk≤2​\(1\+α\)k−11−α⇒1γk≤2​\(1\+α\)k−1−\(1\+α\)1−α\.t\_\{k\}\\leq\\frac\{2\(1\+\\alpha\)^\{k\-1\}\}\{1\-\\alpha\}\\Rightarrow\\frac\{1\}\{\\gamma\_\{k\}\}\\leq\\frac\{2\(1\+\\alpha\)^\{k\-1\}\-\(1\+\\alpha\)\}\{1\-\\alpha\}\.
⟹γk≥1−α2​\(1\+α\)k−1−\(1\+α\),\\implies\\gamma\_\{k\}\\geq\\frac\{1\-\\alpha\}\{2\(1\+\\alpha\)^\{k\-1\}\-\(1\+\\alpha\)\},
which is the desired approximation bound\. ∎

While the approximation decays rapidly withkk, we show that a smallkkis sufficient to flip the classification\. Since our objective functionffis implicitly defined by a trained GNN, we conduct an empirical analysis to determine if approximate submodularity and/or additivity apply\.

##### Empirical Validation\.

Following the methodology of\([Horel and Singer, 2016](https://arxiv.org/html/2608.23835#bib.bib20)\), we randomly sample pairs of disjoint intervention setsAAandBBacross target nodes and measure two diagnostic ratios:

- •Additivity Ratio:radd=f⁡\(A∪B\)/\(f⁡\(A\)\+f⁡\(B\)\)r\_\{\\text\{add\}\}=f\(A\\cup B\)\\,/\\,\(f\(A\)\+f\(B\)\)\. A value of near 1 indicates approximate additivity\.
- •Modularity Ratio:rmod=∑x∈B\[f⁡\(A∪\{x\}\)−f⁡\(A\)\]/\[f⁡\(A∪B\)−f⁡\(A\)\]r\_\{\\text\{mod\}\}=\\sum\_\{x\\in B\}\[f\(A\\cup\\\{x\\\}\)\-f\(A\)\]\\,/\\,\[f\(A\\cup B\)\-f\(A\)\]\. A value ofrmod≤1r\_\{\\text\{mod\}\}\\leq 1confirms diminishing returns \(submodularity\);rmod≈1r\_\{\\text\{mod\}\}\\approx 1indicates near\-perfect modularity\. A value lower than11indicates approximate submodularity as defined in\([Das and Kempe, 2018](https://arxiv.org/html/2608.23835#bib.bib5)\)\.

[Figure2](https://arxiv.org/html/2608.23835#acmlabel2)reports the distributions of both ratios over 5000 random trials\.\(i\) Approximate additivity\.The additivity ratios \([Figure2](https://arxiv.org/html/2608.23835#acmlabel2), left\) are tightly concentrated around 1, with the vast majority falling within\[0\.9,1\.1\]\[0\.9,1\.1\]\. This implies that the slack parameterα\\alphain Theorem[3\.1](https://arxiv.org/html/2608.23835#S3.Thmtheorem1)is very small in practice\. Substituting a conservative estimate ofα≈0\.1\\alpha\\approx 0\.1into the bound of Theorem[3\.1](https://arxiv.org/html/2608.23835#S3.Thmtheorem1), even afterk=5k=5greedy steps, the approximation ratio satisfiesγ5≥0\.49\\gamma\_\{5\}\\geq 0\.49, indicating that the greedy solution retains at least 69% of the optimal cumulative risk reduction\.\(ii\) Submodularity \(and near\-modularity\)\.The modularity ratios \([Figure2](https://arxiv.org/html/2608.23835#acmlabel2), right\) are also concentrated around 1, with almost all instances ofrmod\>0\.5r\_\{\\text\{mod\}\}\>0\.5\. This results in\(1−e−0\.5\)\(1\-e^\{\-0\.5\}\)\-approximation guarantee\([Das and Kempe, 2018](https://arxiv.org/html/2608.23835#bib.bib5);[Krause and Golovin, 2014](https://arxiv.org/html/2608.23835#bib.bib32)\)\.

Algorithm 2Greedy Global Intervention Selection1:Local counterfactual candidates

𝒞\\mathcal\{C\}, budget

BB, coverage function

FF
2:Global intervention strategy

SS
3:

S←∅S\\leftarrow\\emptyset
4:

total\_cost←0\\textit\{total\\\_cost\}\\leftarrow 0
5:

cmax←arg⁡maxc∈𝒞⁡F⁡\(\{c\}\)c\_\{\\max\}\\leftarrow\\arg\\max\_\{c\\in\\mathcal\{C\}\}F\(\\\{c\\\}\)
6:while

𝒞∖S≠∅\\mathcal\{C\}\\setminus S\\neq\\emptysetdo

7:

c∗←arg⁡maxc∈𝒞∖S⁡F⁡\(S∪\{c\}\)−F⁡\(S\)\|c\|c^\{\*\}\\leftarrow\\arg\\max\_\{c\\in\\mathcal\{C\}\\setminus S\}\\frac\{F\(S\\cup\\\{c\\\}\)\-F\(S\)\}\{\|c\|\}
8:if

total\_cost\+\|c∗\|≤B\\textit\{total\\\_cost\}\+\|c^\{\*\}\|\\leq Bthen

9:

S←S∪\{c∗\}S\\leftarrow S\\cup\\\{c^\{\*\}\\\}
10:

total\_cost←total\_cost\+\|c∗\|\\textit\{total\\\_cost\}\\leftarrow\\textit\{total\\\_cost\}\+\|c^\{\*\}\|
11:else

12:Remove

c∗c^\{\*\}from further consideration

13:

𝒞←𝒞∖\{c∗\}\\mathcal\{C\}\\leftarrow\\mathcal\{C\}\\setminus\\\{c^\{\*\}\\\}
14:

S←arg⁡maxS′∈\{S,\{cmax\}\}⁡F⁡\(S′\)S\\leftarrow\\arg\\max\_\{S^\{\\prime\}\\in\\\{S,\\\{c\_\{\\max\}\\\}\\\}\}F\(S^\{\\prime\}\)
15:return

SS

### 3\.4\.Graph\-level Intervention

After generating node\-level counterfactuals, we wish to identify a small set of counterfactuals that can be used as a potential intervention over the population\. We construct a global intervention strategy by selecting a subset of local counterfactual clauses to form a Disjunctive Normal Form \(DNF\) policy that maximizes the number of high\-risk nodes being covered\.

#### 3\.4\.1\.Problem Formulation

LetP⊆VP\\subseteq Vdenote the set of nodes predicted as positive by the base model\. For each nodev∈Pv\\in P, we generate a local counterfactual clause, resulting in a candidate set𝒞=\{c1,…,c\|P\|\}\\mathcal\{C\}=\\\{c\_\{1\},\\dots,c\_\{\|P\|\}\\\}\. Our objective is to select a subsetS⊆𝒞S\\subseteq\\mathcal\{C\}that maximizes a global coverage functionF⁡\(S\)F\(S\):

\(2\)maxS⊆𝒞\|\{v∈P:∃c∈S,Covered\(v,c\)\}\|\.\\max\_\{S\\subseteq\\mathcal\{C\}\}\\left\|\\\{v\\in P:\\exists c\\in S,\\ \\mathrm\{Covered\}\(v,c\)\\\}\\right\|\.
subject to a total cost \(or complexity\) constraint:

\(3\)∑c∈S\|c\|≤B,\\sum\_\{c\\in S\}\|c\|\\leq B,where\|c\|\|c\|denotes the number of individual interventions contained in clausecc, andBBis a predefined budget\.

#### 3\.4\.2\.Coverage and Compatibility

A clauseccis said to*cover*a nodevvif applyingcctovvis sufficient to flip the predicted label ofvv\. In practice, we adopt two ways of covering a nodeCovered​\(v,c\)\\text\{Covered\}\(v,c\):

1. \(1\)Model\-based Flip\.For a node feature rule, we consider a node covered if applying the change to its feature will result in the trained model to flip the label,
2. \(2\)Rule Compatibility\.Additionally, nodevvis still considered covered if it satisfies its own minimal counterfactual requirementscvc\_\{v\}throughcc\. Specifically, this requires thatcccontains the same self\-feature interventions ascvc\_\{v\}, and that the neighborhood conditions imposed byccare*stricter than or equal to*those required bycvc\_\{v\}\. For example, a clause requiringN⁡\(X\)≥0\.8N\(X\)\\geq 0\.8is compatible with a node whose local requirement isN⁡\(X\)≥0\.5N\(X\)\\geq 0\.5\.

#### 3\.4\.3\.Monotonicity and Submodularity

The global coverage functionF⁡\(S\)F\(S\), satisfies two key properties:

- •Monotonicity:For anyA⊆B⊆𝒞A\\subseteq B\\subseteq\\mathcal\{C\}, we haveF⁡\(A\)≤F⁡\(B\)F\(A\)\\leq F\(B\)\. Adding additional intervention clauses never decreases the total number of covered nodes\.
- •Submodularity:The functionF⁡\(S\)F\(S\)exhibits diminishing marginal returns\. For anyA⊆B⊆𝒞A\\subseteq B\\subseteq\\mathcal\{C\}and any clausec∈𝒞∖Bc\\in\\mathcal\{C\}\\setminus B, \(4\)F⁡\(A∪\{c\}\)−F⁡\(A\)≥F⁡\(B∪\{c\}\)−F⁡\(B\)\.F\(A\\cup\\\{c\\\}\)\-F\(A\)\\geq F\(B\\cup\\\{c\\\}\)\-F\(B\)\.This is because the impact of an intervention, may overlap with impact of already applied interventions diminishing its coverage\.

#### 3\.4\.4\.Greedy Strategy and Approximation Guarantee

Maximizing a monotone submodular function under a knapsack constraint is NP\-hard\. However, it has been shown that a simple greedy algorithm \(Algorithm[2](https://arxiv.org/html/2608.23835#alg2)\) can achieve a 0\.405\-approximation\([Tang et al\., 2021](https://arxiv.org/html/2608.23835#bib.bib4)\)\. It iteratively chooses the clausec∗c^\{\*\}with the highest marginal coverage gain per unit cost:

\(5\)c∗=arg⁡maxc∈𝒞∖S⁡F⁡\(S∪\{c\}\)−F⁡\(S\)\|c\|\.c^\{\*\}=\\arg\\max\_\{c\\in\\mathcal\{C\}\\setminus S\}\\frac\{F\(S\\cup\\\{c\\\}\)\-F\(S\)\}\{\|c\|\}\.It then augments the result by finding if there is a single clause that could achieve a better coverage while being within the constraint\.

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\.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 theMinimum 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 inboldandunderline\.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 inbold,underline, andred, respectively\.

## 4\.Experiments

### 4\.1\.Datasets

We use both real\-world and synthetic datasets to evaluate the explanation and intervention components of our framework\. Together, these datasets enable a comprehensive assessment of explanation accuracy and counterfactual\-based intervention generation across relational and non\-relational settings\. The benchmark datasets provide ground\-truth motifs for quantitative explanation evaluation, while the intervention datasets examine intervention strategies under realistic and controlled synthetic settings\. Summary statistics are reported in[Table1](https://arxiv.org/html/2608.23835#S3.T1)\.

#### 4\.1\.1\.Datasets for Explanation Evaluation

We evaluate our explanation method on three datasets with available ground\-truth motifs: BA\-Shapes, Tree\-Cycles, and Mutag0\. BA\-Shapes and Tree\-Cycles\([Ying et al\., 2019](https://arxiv.org/html/2608.23835#bib.bib7)\)are synthetic node classification benchmarks with human\-designed structural motifs \(house and cycle patterns, respectively\)\. Mutag0is a curated sub\-dataset of Mutag\([Debnath et al\., 1991](https://arxiv.org/html/2608.23835#bib.bib23);[Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\), constructed to isolate benzene–NO2as the sole discriminative motif for graph classification\. These datasets allow quantitative evaluation of explanation accuracy against known ground\-truth structures\.

#### 4\.1\.2\.Datasets for Intervention Evaluation

We evaluate intervention strategies on two real\-world suicide risk networks and a family of synthetic graphs spanning varying sizes and densities\.

Military\.A real\-world peer network constructed from ego\-network interviews with active\-duty military personnel, comprising 241 nodes and 258 edges\. The dataset captures social support and advice\-seeking relationships alongside 27 individual\-level attributes spanning demographics, mental health assessments \(depression, PTSD, disability\), substance use, deployment history, and unit cohesion, yielding 48 features after one\-hot encoding of categorical variables\. Demographic attributes \(e\.g\., race, gender, age\) are designated as immutable to constrain counterfactual generation\. A suicidal ideation score is computed by summing direct suicidal intention responses\. While the SBQ\-R manual\([Osman et al\., 2001](https://arxiv.org/html/2608.23835#bib.bib8)\)suggests a cutoff of 7 or higher for high suicide risk, we adopt a much more conservative definition to support early identification and intervention: individuals are labeled*at\-risk*if either the summed suicidal\-intention score or the direct suicidal\-ideation item is 2 or greater, and*not at\-risk*otherwise\.

Youth\.A real\-world homeless youth dataset sourced from the YouthNet\-SPY study, consisting of 131 individuals with 39 features and no explicit graph structure, enabling evaluation of counterfactual interventions in a non\-relational setting\. Features span three domains: self\-reported attributes \(demographics, employment, substance use history\), neighborhood\-aggregate social network proportions \(e\.g\., peer drug use exposure, sexual health discussion\), and standardized psychological assessment scores \(depression, loneliness\)\. Suicide risk is derived from self\-reported ideation and planning in the past 12 months: individuals reporting either suicidal ideation or a suicide plan are labeled*at\-risk*, and others*not at\-risk*\.

Synthetic\.We construct a family of synthetic graph datasets using a hybrid generation mechanism that combines stochastic block model \(SBM\)\([Karrer and Newman, 2011](https://arxiv.org/html/2608.23835#bib.bib25)\)structure with homophily\-based edge formation\. Each node is assignedmmbinary attributes drawn uniformly at random, and a normalized weight vector determines the influence of each attribute on weighted\-distance\-based edge formation, inducing controlled homophily effects\. Risk labels are assigned through a controlled scoring mechanism\. In the*Neighbor\-Only*variant, a node’s risk depends solely on neighborhood composition, defined as the proportion of neighbors possessing a designated risk\-inducing attribute\. In the*Neighbor\-Feature*variant, risk follows a diathesis–stress formulation\([Monroe and Simons, 1991](https://arxiv.org/html/2608.23835#bib.bib31)\), where a node becomes high\-risk only when intrinsic vulnerability \(determined by specific attribute values\) interacts with exposure to high\-risk neighbors\. Nodes are labeled*at\-risk*if they fall within the top 17% of the risk score distribution\.

### 4\.2\.Experimental Setup

Models\.Our explanation method and intervention mechanism both rely on an underlying predictive model with reliable classification performance\. Across all experiments, we use a unified three\-layer Graph Convolutional Network \(GCN\)\([Kipf and Welling, 2017](https://arxiv.org/html/2608.23835#bib.bib11)\)as the predictive backbone, trained to perform binary node\-level risk classification \(at\-riskvs\.not at\-risk\) over all nodes in the graph\. We adopt an 80/20 stratified train–test split and optimize the models\. The trained backbone achieves average test accuracies of95\.85%\\mathbf\{95\.85\\%\},98\.99%\\mathbf\{98\.99\\%\}, and96\.40%\\mathbf\{96\.40\\%\}on the Military, Youth, and synthetic datasets, providing a reliable basis for the subsequent counterfactual explanations and intervention generation\.

Evaluation Metrics\.We use the following metrics to evaluate the node\-level explanations\.

- •Pr% \(Precision\)\.Precision is the proportion of predicted important edges that belong to the ground\-truth important subgraph\.
- •\#exp \(Explanation Size\)\.\#exp measures the size of the counterfactual explanation\. For baseline methods, it is the number of perturbed edges \(or features\)\. For our method, \#exp is defined as the*Minimum Information Perturbation \(MIP\)*, i\.e\., the minimum number of modifications needed to flip the prediction\.
- •Time\(s\)\.Time reports the average inference time per instance \(in seconds\) required to generate a counterfactual explanation\.

We use the following metrics for graph\-level intervention\.

- •AUCC\(Area Under the Coverage Curve\)\. AUCC measures intervention efficiency by computing the area under the coverage curve, which shows the number of flipped at\-risk nodes under different intervention budgets\. Higher AUCC indicates broader coverage with fewer interventions\.
- •Coverage\.Coverage is defined as the number of at\-risk nodes whose predicted labels are successfully flipped by a given intervention strategy under a fixed budget\.
- •Time\(s\)\.Time reports the time required to generate counterfactual explanations and intervention strategies \(in seconds\)\.

Hyperparameters and Implementation Details\.Experiments were conducted using a hybrid CPU\-GPU setup\. Model training and inference were performed on NVIDIA RTX 2080S GPUs, while explanation generation — including perturbation and greedy orchestration — was executed on a 64\-core AMD EPYC 7513 CPU with 248 GB memory\. To ensure a fair comparison, all competing methods were evaluated under the same GPU and CPU settings\. For CF, the regularization coefficientβ\\betawas selected from\{0\.01,0\.1,1\}\\\{0\.01,0\.1,1\\\}\. ForC​F2CF^\{2\}, the edge and node mask thresholds were tuned within the range\[0\.2,0\.8\]\[0\.2,0\.8\]\. The intervention budget was chosen from\{5,10,15,20\}\\\{5,10,15,20\\\}\. The code is publicly available111[https://github\.com/scc\-usc/G2I](https://github.com/scc-usc/G2I)\.

To evaluate the effectiveness of our proposed DNF\-based intervention strategy, we compare it against two commonly used baselines:\(1\) Random, which selects intervention candidates uniformly at random; and\(2\) Frequency, which prioritizes candidates based on their occurrence frequency in the generated counterfactual rules\. Each experiment was repeated 10 times with different random seeds, and we report the mean±\\pmstandard deviation\. For clarity, only the mean values are shown in the tables\.

![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.](https://arxiv.org/html/2608.23835v1/figures/scalability.png)Figure 3\.Runtime scalability of CF\-Greedy, CF, and CF2on 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\.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\.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\.
### 4\.3\.Results

We evaluate the explanation and intervention stages separately\.

#### 4\.3\.1\.Results for Explanation Evaluation

We follow the setup ofC​F2CF^\{2\}\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\)but use*Precision*as the primary metric\. Since our objective is to identify the minimal perturbation that flips a prediction, we focus on detecting truly critical components rather than maximizing coverage\. Precision directly measures how many identified edges correspond to ground\-truth important ones\.

SOTA Performance on Explanation\.In[Table2](https://arxiv.org/html/2608.23835#S3.T2), we observe that our greedy method achieves a consistent improvement over state\-of\-the\-art mask\-training explanation methods across all datasets\. Notably, the second\-best performing methods are also counterfactual\-based approaches, whose loss functions explicitly incorporate counterfactual objectives\. This observation further supports the importance of counterfactual reasoning in identifying truly decisive graph components across both node\- and graph\-level classification tasks\.

Minimum Explanation Size\.Unlike prior methods, which either fix explanation size \(KKin GNNExplainer\) or learn unconstrained soft masks \(CF\-GNNExplainer andC​F2CF^\{2\}\), our objective directly targets the minimal perturbation necessary to change the prediction\. Our minimal\-perturbation principle provides a distinct perspective on explanation generation\. Although ground\-truth explanations exist in our three benchmarks, real\-world settings typically lack explicit importance labels and predefined explanation sizes\. In practice, our method yields the smallest explanation size \(\#exp\) across all datasets, leading to more concise and interpretable explanations with reduced computational overhead\.

Shortest Runtime\.All methods were evaluated under the same hardware and experimental setup\. Our framework achieves more than a one\-order\-of\-magnitude speedup over existing methods, and in some cases approaches two orders of magnitude\. Such efficiency is particularly critical in time\-sensitive public decision\-making settings, where rapid and reliable explanations are essential\.

#### 4\.3\.2\.Results for Intervention Evaluation

For intervention generation, we compare three counterfactual explanation methods—CF\([Lucic et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib14)\),C​F2CF^\{2\}\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\), and our proposed CF\-Greedy—under three group\-level intervention strategies in[Table3](https://arxiv.org/html/2608.23835#S3.T3):*Random*,*Frequency\-based*, and*DNF\-based*\. We evaluate intervention quality using AUCC, where higher values indicate more efficient coverage under a fixed budget, and also report Coverage and Time\. For clarity, only DNF\-based Coverage is shown in the main table\.

Superior Coverage and AUCC\.As shown in Table[3](https://arxiv.org/html/2608.23835#S3.T3), explanations generated by CF\-Greedy consistently achieve substantially higher overall performance \(measured by AUCC\) compared to CF andC​F2CF^\{2\}\. Notably, even when combined with the*Random*and*Frequency\-based*intervention strategies, CF\-Greedy maintains strong performance advantages\.

In terms of final Coverage, CF\-Greedy outperforms CF andC​F2CF^\{2\}across nearly all datasets\. The only exception is on the Neighbor\-Only setting for N250\-E300\-D6, where performance is slightly lower thanC​F2CF^\{2\}\. Beyond this case, CF\-Greedy consistently achieves superior coverage, with many datasets reaching 100% coverage under the fixed budget—an outcome that CF andC​F2CF^\{2\}rarely attain\.

Superior Performance on Intervention\.Comparing the three intervention construction strategies across explanation methods reveals a clear structural pattern\. ForC​F2CF^\{2\}and CF\-Greedy, which generate joint feature–edge counterfactuals and thus enable heterogeneous intervention clauses, the DNF\-based strategy consistently achieves the best performance\. When candidate clauses contain diverse components, the DNF objective exploits combinatorial interactions and submodular\-like gains for better budget allocation\.

In contrast, for CF, which produces edge\-only explanations, the Frequency\-based strategy often performs competitively or even better\. Under single\-edge interventions, clauses are relatively homogeneous and highly overlapping, so selecting frequent edges already captures the dominant coverage structure, leaving limited room for combinatorial optimization\. As a result, the advantage of DNF diminishes when intervention expressiveness is restricted\. Importantly, real\-world intervention scenarios typically involve joint modifications of both individual attributes and relational structure\. In such heterogeneous settings, the DNF framework is naturally better aligned with practical intervention design\.

Sensitivity of Mask\-Based Methods\.We tuned CF andC​F2CF^\{2\}separately for each dataset, adjusting the regularization coefficientβ\\beta\(CF\) and mask thresholds \(CF2\) controlling explanation sparsity and size\. Optimal settings vary across datasets, indicating sensitivity to data characteristics\. In contrast, our greedy method requires no dataset\-specific tuning and outperforms the optimized baselines\.

Robustness to Network Scale\.Network density is characterized by the edge\-to\-node ratio \(E/N\), reflecting average node connectivity\. Real\-world networks are typically sparse, with relatively small average degree compared to network size\([Newman, 2010](https://arxiv.org/html/2608.23835#bib.bib10)\)\. Our synthetic graphs span low to moderately dense settings \(E/N from 1 to 5\), covering structures observed in social and organizational networks\.

Under different density settings, we observe distinct behaviors across explanation methods\. For CF, which relies on edge perturbations, performance improves as edge density increases, since denser graphs provide more opportunities for single\-edge interventions\. In contrast,C​F2CF^\{2\}shows the opposite trend, with performance decreasing as density grows\. CF\-Greedy remains stable across both sparse and dense settings\. Although performance slightly declines in very dense graphs, the impact is marginal compared to CF andC​F2CF^\{2\}, indicating stronger robustness to structural complexity\.

Shortest End\-to\-End Runtime\.We measure end\-to\-end runtime from explanation generation to intervention construction\. CF\-Greedy consistently achieves the shortest runtime across all datasets, outperforming CF andC​F2CF^\{2\}\. Although runtime grows with graph density, CF\-Greedy maintains a clear efficiency advantage\.

#### 4\.3\.3\.Scalability

We evaluate the scalability of our framework under different counterfactual explanation methods as the graph size increases from 100 to over 25,600 nodes\.[Figure3](https://arxiv.org/html/2608.23835#acmlabel3)reports the runtime of each strategy as a function of the number of nodes\. We observe that optimization\-based methods \(CF\([Lucic et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib14)\)and CF2\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\)\) become significantly slower as the graph size increases, due to repeated model evaluations during explanation generation\. In contrast, the greedy strategy demonstrates significantly better scaling behavior, remaining efficient even as the graph size grows\.

Beyond runtime, we also examine the practical feasibility of these strategies under fixed computational resources\. We find that exhaustive and optimization\-based methods \(CF\([Lucic et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib14)\)and CF2\([Tan et al\., 2022](https://arxiv.org/html/2608.23835#bib.bib9)\)\) become infeasible beyond approximately 6,400 nodes, requiring more than 248GB of memory to execute\. Under the same memory constraints, the greedy\-based strategy within our framework scales to graphs with over 20,000 nodes\.

## 5\.Discussion

### 5\.1\.Real\-World Intervention Design

A key advantage of our counterfactual framework is that the generated DNF clauses can be directly translated into human\-readable hypotheses\. We demonstrate this on the Military dataset by running CF\-GREEDY under two settings: \(1\) an*unconstrained*setting where all features are mutable, yielding explanatory insights about risk factors; and \(2\) a*constrained*setting where demographic attributes \(race, gender, sexuality, age, siblings, ACEs\) are immutable, yielding actionable intervention strategies\. Both settings achieve 100% coverage of all 51 at\-risk individuals\.

Understanding Risk Factors\.The unconstrained results \([Table4](https://arxiv.org/html/2608.23835#S4.T4)\) reveal the features most predictive of the model’s risk classification\. Race emerges as the single dominant factor, with a single racial category change flipping 59% of at\-risk predictions\. While race itself cannot and should not be an intervention target, this finding flags potential disparities in risk distribution that warrant further study — for instance, whether certain racial groups face systematically higher exposure to stressors or reduced access to protective resources\. Career intent and soldier identity emerge as secondary but strong protective factors even in the unconstrained setting, suggesting these are genuine, robust correlates of lower risk rather than artifacts of demographic confounding\.

Designing Actionable Interventions\.The constrained results \([Table5](https://arxiv.org/html/2608.23835#S4.T5)\) demonstrate that, even when demographic features are locked, our framework identifies actionable interventions achieving full coverage at a modest cost increase \(12 vs\. 11\)\. The interventions naturally organize into a tiered structure: high\-impact career programs alone cover 84% of individuals, clinical interventions extend coverage to 90%, and network\-level strategies reach the remaining 10%\. We note that some clauses point in opposite directions for different individuals \(e\.g\., increased soldier satisfaction lowers predicted risk for some, while decreased satisfaction does for others\), reflecting heterogeneous counterfactual pathways across subgroups rather than a single population\-wide effect\. This tiered organization provides a practical deployment blueprint: programs can be prioritized by population\-level impact, with career counseling as the universal first\-line intervention and peer\-network restructuring as a targeted complement\.

Please note that none of the revealed hypotheses may be causal\. The framework is meant to assist social scientists in understanding model behavior and in designing studies to test hypotheses or designing interventions\.

## 6\.Conclusion

We presented a theoretically grounded framework for graph explanation and intervention design based on discrete counterfactual reasoning, motivated by the goal of suicide prevention and simple explanation methods\. By directly optimizing for the minimal perturbation that flips a prediction, our method reframes explanation generation as a principled discrete optimization problem rather than continuous mask approximation\. For intervention design, we formulate clause selection as a DNF\-based coverage objective, enabling efficient greedy approximation under budget constraints\. Empirically, CF\-Greedy achieves superior precision, minimal explanation size, strong robustness to network density, and substantial runtime improvements, highlighting the advantages of discrete combinatorial optimization over mask\-based training approaches\. By generating interpretable counterfactual explanations and translating them into actionable intervention strategies, our framework supports scalable and transparent deployment in real\-world public health decision\-making\.

Future work includes formalizing tighter approximation guarantees for structured intervention costs and deploying selected promising interventions into the target population\.

###### Acknowledgements\.

This work was supported by the Army Research Office grant W911NF\-23\-1\-0354\.

## References

- Athey and Imbens \(2016\)S\. Athey and G\. ImbensRecursive partitioning for heterogeneous causal effects\.Proceedings of the National Academy of Sciences113\(27\),pp\. 7353–7360\.External Links:ISSN 1091\-6490,[Link](http://dx.doi.org/10.1073/pnas.1510489113),[Document](https://dx.doi.org/10.1073/pnas.1510489113)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p5.1)\.
- Bajajet al\.\(2022\)M\. Bajaj, L\. Chu, Z\. Y\. Xue, J\. Pei, L\. Wang, P\. C\. Lam, and Y\. ZhangRobust counterfactual explanations on graph neural networks\.External Links:2107\.04086,[Link](https://arxiv.org/abs/2107.04086)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1)\.
- Brenneret al\.\(2023\)L\. A\. Brenner, J\. E\. Forster, C\. G\. Walsh, K\. A\. Stearns\-Yoder, M\. J\. Larson, T\. A\. Hostetter, C\. A\. Hoffmire, J\. L\. Gradus, and R\. S\. AdamsTrends in suicide rates by race and ethnicity among members of the united states army\.PloS one18\(1\),pp\. e0280217\.Cited by:[Table 4](https://arxiv.org/html/2608.23835#S4.T4.2.2.2.1.1.1.1)\.
- Christakis and Fowler \(2009\)N\. A\. Christakis and J\. H\. FowlerConnected: the surprising power of our social networks and how they shape our lives\.Little, Brown,New York\.Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p1.1),[§2](https://arxiv.org/html/2608.23835#S2.p4.1)\.
- Das and Kempe \(2018\)A\. Das and D\. KempeApproximate submodularity and its applications: subset selection, sparse approximation and dictionary selection\.Journal of Machine Learning Research19\(3\),pp\. 1–34\.Cited by:[1st item](https://arxiv.org/html/2608.23835#S3.I1.i1.p1.1),[2nd item](https://arxiv.org/html/2608.23835#S3.I2.i2.p1.1),[§3\.3](https://arxiv.org/html/2608.23835#S3.SS3.SSS0.Px1.p3.1)\.
- Davidsonet al\.\(2006\)L\. Davidson, M\. Chinman, D\. Sells, and M\. RowePeer support among adults with serious mental illness: a report from the field\.Schizophrenia Bulletin32\(3\),pp\. 443–450\.External Links:[Document](https://dx.doi.org/10.1093/schbul/sbj043)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p3.1)\.
- Debnathet al\.\(1991\)A\. K\. Debnath, R\. L\. Lopez de Compadre, G\. Debnath, A\. J\. Shusterman, and C\. HanschStructure\-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds\. correlation with molecular orbital energies and hydrophobicity\.Journal of Medicinal Chemistry34,pp\. 786–797\.External Links:[Document](https://dx.doi.org/10.1021/jm00106a046),[Link](https://pubmed.ncbi.nlm.nih.gov/1995902/)Cited by:[§4\.1\.1](https://arxiv.org/html/2608.23835#S4.SS1.SSS1.p1.1)\.
- Dworsky and Courtney \(2009\)A\. Dworsky and M\. E\. CourtneyHomelessness and the transition from foster care to adulthood\.Child Welfare88\(4\),pp\. 23–56\.Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p3.1)\.
- Fest \(2013\)J\. FestStreet culture: an epistemology of street\-dependent youth\.JT Fest\.Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p3.1)\.
- Hamiltonet al\.\(2018\)W\. L\. Hamilton, R\. Ying, and J\. LeskovecInductive representation learning on large graphs\.External Links:1706\.02216,[Link](https://arxiv.org/abs/1706.02216)Cited by:[§3\.1](https://arxiv.org/html/2608.23835#S3.SS1.p2.1)\.
- Horel and Singer \(2016\)T\. Horel and Y\. SingerMaximization of approximately submodular functions\.InAdvances in Neural Information Processing Systems,Vol\.29,pp\. 3045–3053\.Cited by:[§3\.3](https://arxiv.org/html/2608.23835#S3.SS3.SSS0.Px1.p1.1)\.
- Jackson \(2008\)M\. O\. JacksonSocial and economic networks\.External Links:[Link](https://web.stanford.edu/~jacksonm/netbook.pdf)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p1.1),[§2](https://arxiv.org/html/2608.23835#S2.p4.1)\.
- Jolliffe and Cadima \(2016\)I\. T\. Jolliffe and J\. CadimaPrincipal component analysis: a review and recent developments\.Philosophical Transactions of the Royal Society A374\(2065\),pp\. 20150202\.External Links:[Document](https://dx.doi.org/10.1098/rsta.2015.0202)Cited by:[§3\.1](https://arxiv.org/html/2608.23835#S3.SS1.p1.1)\.
- Karrer and Newman \(2011\)B\. Karrer and M\. E\. J\. NewmanStochastic blockmodels and community structure in networks\.Physical Review E83\(1\),pp\. 016107\.External Links:ISSN 1550\-2376,[Link](http://dx.doi.org/10.1103/PhysRevE.83.016107),[Document](https://dx.doi.org/10.1103/physreve.83.016107)Cited by:[§4\.1\.2](https://arxiv.org/html/2608.23835#S4.SS1.SSS2.p4.1)\.
- Kipf and Welling \(2017\)T\. N\. Kipf and M\. WellingSemi\-supervised classification with graph convolutional networks\.External Links:1609\.02907,[Link](https://arxiv.org/abs/1609.02907)Cited by:[§3\.1](https://arxiv.org/html/2608.23835#S3.SS1.p1.1),[§4\.2](https://arxiv.org/html/2608.23835#S4.SS2.p1.1)\.
- Krause and Golovin \(2014\)A\. Krause and D\. GolovinSubmodular function maximization\.InTractability: Practical Approaches to Hard Problems,L\. Bordeaux, Y\. Hamadi, and P\. Kohli \(Eds\.\),pp\. 71–104\.Cited by:[1st item](https://arxiv.org/html/2608.23835#S3.I1.i1.p1.1),[§3\.3](https://arxiv.org/html/2608.23835#S3.SS3.SSS0.Px1.p3.1)\.
- Lazeret al\.\(2020\)D\. M\. J\. Lazer, A\. Pentland, D\. J\. Watts, S\. Aral, S\. Athey, N\. Contractor, D\. Freelon, S\. Gonzalez\-Bailon, G\. King, H\. Margetts, A\. Nelson, M\. J\. Salganik, M\. Strohmaier, A\. Vespignani, and C\. WagnerComputational social science: obstacles and opportunities\.Science369\(6507\),pp\. 1060–1062\.External Links:[Document](https://dx.doi.org/10.1126/science.aaz8170)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p6.1)\.
- Lazeret al\.\(2009\)D\. Lazer, A\. Pentland, L\. Adamic, S\. Aral, A\. Barabási, D\. Brewer, N\. Christakis, N\. Contractor, J\. Fowler, M\. Gutmann, T\. Jebara, G\. King, M\. Macy, D\. Roy, and M\. Van AlstyneComputational social science\.Science323\(5915\),pp\. 721–723\.External Links:[Document](https://dx.doi.org/10.1126/science.1167742)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p6.1)\.
- Lucicet al\.\(2022\)A\. Lucic, M\. ter Hoeve, G\. Tolomei, M\. de Rijke, and F\. SilvestriCF\-gnnexplainer: counterfactual explanations for graph neural networks\.InProceedings of the 25th International Conference on Artificial Intelligence and Statistics \(AISTATS\),Vol\.151,pp\. 4499–4511\.Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1),[§1](https://arxiv.org/html/2608.23835#S1.p3.1),[§2](https://arxiv.org/html/2608.23835#S2.p1.1),[§4\.3\.2](https://arxiv.org/html/2608.23835#S4.SS3.SSS2.p1.1),[§4\.3\.3](https://arxiv.org/html/2608.23835#S4.SS3.SSS3.p1.1),[§4\.3\.3](https://arxiv.org/html/2608.23835#S4.SS3.SSS3.p2.1)\.
- Ludwig and Mullainathan \(2024\)J\. Ludwig and S\. MullainathanMachine learning as a tool for hypothesis generation\.The Quarterly Journal of Economics139\(2\),pp\. 751–827\.Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1),[§2](https://arxiv.org/html/2608.23835#S2.p5.1),[§2](https://arxiv.org/html/2608.23835#S2.p6.1)\.
- Luoet al\.\(2020\)D\. Luo, W\. Cheng, D\. Xu, W\. Yu, B\. Zong, H\. Chen, and X\. ZhangParameterized explainer for graph neural network\.CoRRabs/2011\.04573\.External Links:[Link](https://arxiv.org/abs/2011.04573),2011\.04573Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1)\.
- Monroe and Simons \(1991\)S\. M\. Monroe and A\. D\. SimonsDiathesis\-stress theories in the context of life stress research: implications for the depressive disorders\.Psychological Bulletin110\(3\),pp\. 406–425\.External Links:[Document](https://dx.doi.org/10.1037/0033-2909.110.3.406)Cited by:[§4\.1\.2](https://arxiv.org/html/2608.23835#S4.SS1.SSS2.p4.1)\.
- Mullainathan and Spiess \(2017\)S\. Mullainathan and J\. SpiessMachine learning: an applied econometric approach\.Journal of Economic Perspectives31\(2\),pp\. 87–106\.External Links:[Document](https://dx.doi.org/10.1257/jep.31.2.87)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p6.1)\.
- Nemhauseret al\.\(1978\)G\. L\. Nemhauser, L\. A\. Wolsey, and M\. L\. FisherAn analysis of approximations for maximizing submodular set functions—i\.Mathematical Programming14,pp\. 265–294\.External Links:[Document](https://dx.doi.org/10.1007/BF01588971),[Link](https://link.springer.com/article/10.1007%2FBF01588971)Cited by:[1st item](https://arxiv.org/html/2608.23835#S3.I1.i1.p1.1)\.
- Newman \(2010\)M\. NewmanNetworks: an introduction\.Oxford University Press\.Cited by:[§4\.3\.2](https://arxiv.org/html/2608.23835#S4.SS3.SSS2.p7.1)\.
- Osmanet al\.\(2001\)A\. Osman, C\. L\. Bagge, P\. M\. Gutierrez, L\. C\. Konick, B\. A\. Kopper, and F\. X\. BarriosThe suicidal behaviors questionnaire\-revised \(sbq\-r\): validation with clinical and nonclinical samples\.Assessment8\(4\),pp\. 443–454\.External Links:[Document](https://dx.doi.org/10.1177/107319110100800409)Cited by:[§4\.1\.2](https://arxiv.org/html/2608.23835#S4.SS1.SSS2.p2.1)\.
- Pastor\-Satorraset al\.\(2015\)R\. Pastor\-Satorras, C\. Castellano, P\. Van Mieghem, and A\. VespignaniEpidemic processes in complex networks\.Reviews of Modern Physics87\(3\),pp\. 925–979\.External Links:ISSN 1539\-0756,[Link](http://dx.doi.org/10.1103/RevModPhys.87.925),[Document](https://dx.doi.org/10.1103/revmodphys.87.925)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p4.1)\.
- Sviridenko \(2004\)M\. SviridenkoA note on maximizing a submodular set function subject to a knapsack constraint\.Operations Research Letters32,pp\. 41–43\.External Links:[Document](https://dx.doi.org/10.1016/s0167-6377%2803%2900062-2)Cited by:[1st item](https://arxiv.org/html/2608.23835#S3.I1.i1.p1.1)\.
- Tanet al\.\(2022\)J\. Tan, S\. Geng, Z\. Fu, Y\. Ge, S\. Xu, Y\. Li, and Y\. ZhangLearning and evaluating graph neural network explanations based on counterfactual and factual reasoning\.InProceedings of the ACM Web Conference 2022,WWW ’22,pp\. 1018–1027\.External Links:[Link](http://dx.doi.org/10.1145/3485447.3511948),[Document](https://dx.doi.org/10.1145/3485447.3511948)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1),[§1](https://arxiv.org/html/2608.23835#S1.p3.1),[§2](https://arxiv.org/html/2608.23835#S2.p1.1.2),[§4\.1\.1](https://arxiv.org/html/2608.23835#S4.SS1.SSS1.p1.1),[§4\.3\.1](https://arxiv.org/html/2608.23835#S4.SS3.SSS1.p1.1),[§4\.3\.2](https://arxiv.org/html/2608.23835#S4.SS3.SSS2.p1.1),[§4\.3\.3](https://arxiv.org/html/2608.23835#S4.SS3.SSS3.p1.1),[§4\.3\.3](https://arxiv.org/html/2608.23835#S4.SS3.SSS3.p2.1)\.
- Tanget al\.\(2021\)J\. Tang, X\. Tang, A\. Lim, K\. Han, C\. Li, and J\. YuanRevisiting modified greedy algorithm for monotone submodular maximization with a knapsack constraint\.Proceedings of the ACM on Measurement and Analysis of Computing Systems5\(1\),pp\. 1–22\.Cited by:[§3\.4\.4](https://arxiv.org/html/2608.23835#S3.SS4.SSS4.p1.1)\.
- Tversky and Kahneman \(1974\)A\. Tversky and D\. KahnemanJudgment under uncertainty: heuristics and biases\.Science185\(4157\),pp\. 1124–1131\.External Links:[Document](https://dx.doi.org/10.1126/science.185.4157.1124)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p5.1)\.
- Valenteet al\.\(2007\)T\. W\. Valente, A\. Ritt\-Olson, A\. Stacy, J\. B\. Unger, J\. Okamoto, and S\. SussmanPeer acceleration: effects of a social network tailored substance abuse prevention program among high\-risk adolescents\.Addiction102\(11\),pp\. 1804–1815\.External Links:[Document](https://dx.doi.org/10.1111/j.1360-0443.2007.01992.x)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p3.1)\.
- Veličkovićet al\.\(2018\)P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. BengioGraph attention networks\.External Links:1710\.10903,[Link](https://arxiv.org/abs/1710.10903)Cited by:[§3\.1](https://arxiv.org/html/2608.23835#S3.SS1.p2.1)\.
- Vermaet al\.\(2022\)S\. Verma, V\. Boonsanong, M\. Hoang, K\. E\. Hines, J\. P\. Dickerson, and C\. ShahCounterfactual explanations and algorithmic recourses for machine learning: a review\.External Links:2010\.10596,[Link](https://arxiv.org/abs/2010.10596)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1)\.
- Vosoughiet al\.\(2018\)S\. Vosoughi, D\. Roy, and S\. AralThe spread of true and false news online\.Science359,pp\. 1146–1151\.External Links:[Document](https://dx.doi.org/10.1126/science.aap9559)Cited by:[§2](https://arxiv.org/html/2608.23835#S2.p4.1)\.
- Wachteret al\.\(2018\)S\. Wachter, B\. Mittelstadt, and C\. RussellCounterfactual explanations without opening the black box: automated decisions and the gdpr\.External Links:1711\.00399,[Link](https://arxiv.org/abs/1711.00399)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1)\.
- Wuet al\.\(2021\)Z\. Wu, S\. Pan, F\. Chen, G\. Long, C\. Zhang, and P\. S\. YuA comprehensive survey on graph neural networks\.IEEE Transactions on Neural Networks and Learning Systems32\(1\),pp\. 4–24\.External Links:[Document](https://dx.doi.org/10.1109/TNNLS.2020.2978386)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p1.1)\.
- Yinget al\.\(2019\)R\. Ying, D\. Bourgeois, J\. You, M\. Zitnik, and J\. LeskovecGNNExplainer: generating explanations for graph neural networks\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.32\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2019/file/d80b7040b773199015de6d3b848f9b40-Paper.pdf)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1),[§2](https://arxiv.org/html/2608.23835#S2.p1.1),[§4\.1\.1](https://arxiv.org/html/2608.23835#S4.SS1.SSS1.p1.1)\.
- Yuanet al\.\(2021\)H\. Yuan, H\. Yu, J\. Wang, K\. Li, and S\. JiOn explainability of graph neural networks via subgraph explorations\.External Links:2102\.05152,[Link](https://arxiv.org/abs/2102.05152)Cited by:[§1](https://arxiv.org/html/2608.23835#S1.p2.1)\.