Counterfactual Subgraphs

The core principle is identifying the smallest possible change to the input graph that flips the GNN's prediction. This is typically formulated as an optimization problem that minimizes the number of edge deletions or node modifications while ensuring the predicted class changes. The result is a sparse, targeted perturbation that isolates the decision boundary's critical support structure.

Unlike feature attribution methods that only highlight important nodes, counterfactual subgraphs provide prescriptive guidance. They answer the question: 'What specific connections must be removed or added to change this outcome?' This makes them directly useful for:

• Drug discovery: Suggesting which molecular bonds to modify
• Fraud detection: Identifying which transactions to investigate
• Recommendation systems: Explaining why removing an interaction changes suggestions

Counterfactual subgraphs are grounded in structural causal models and the do-calculus. The perturbation represents an intervention on the graph structure—deleting an edge is equivalent to setting that relationship to zero. This causal framing distinguishes counterfactuals from purely correlational explanations, as they estimate what would have happened under a different structural configuration.

Generating counterfactual subgraphs involves balancing two competing objectives:

• Fidelity: The perturbed graph must reliably produce the target prediction
• Compactness: The edit set must be as small as possible to remain interpretable

Methods like CF-GNNExplainer solve this by jointly optimizing a prediction loss and a sparsity regularizer, often using continuous relaxations of discrete edge masks.

Effective counterfactuals must remain within the data manifold—the edited graph should be plausible and not violate domain constraints. For example, in molecular graphs, a counterfactual cannot suggest removing a carbon atom's fourth bond without replacing it. Techniques enforce realism through:

• Adversarial training to distinguish real from generated graphs
• Domain-specific validity rules encoded as constraints
• Latent space optimization that decodes edits from a learned manifold

Counterfactual subgraph quality is assessed using:

• Validity: Does the edit actually flip the prediction?
• Proximity: How many edges or nodes were modified?
• Sparsity: Is the counterfactual subgraph itself minimal?
• Realism: Does the edited graph conform to domain constraints?

These metrics ensure explanations are both faithful to the model's decision logic and actionable for downstream users.

A self-explainable GNN framework where a generator module extracts a concise, causal subgraph called the rationale, and a predictor module makes decisions based solely on that rationale.

• The rationale serves as both the explanation and the input for prediction
• Enforces causal sufficiency: the rationale alone must be sufficient for the decision
• Contrasts with post-hoc methods by baking explainability into the architecture itself

A formal framework representing causal relationships in a graph as a set of structural equations. Used to perform intervention analysis and generate counterfactual explanations for GNNs.

• Models the data-generating process, not just correlations
• Enables answering 'What if?' questions through the do-operator
• Provides a rigorous mathematical foundation for counterfactual reasoning on graphs

A quantitative evaluation score that measures how accurately an explanation subgraph reflects the true reasoning process of the GNN.

• Typically assessed by the drop in prediction performance when the explanation is removed
• A faithful explanation captures the features the model actually used, not just correlated ones
• Critical for distinguishing genuine counterfactual causes from spurious correlations

A fidelity assessment method that measures the change in a GNN's prediction after masking or altering the most important nodes or edges identified by an explainer.

• Positive perturbation: removing important structures should cause a sharp prediction drop
• Negative perturbation: removing unimportant structures should have minimal effect
• Directly validates whether identified subgraphs are truly counterfactually relevant

A principle for learning explainable GNNs by compressing the input graph into a minimal subgraph that retains maximal mutual information about the label.

• Discards irrelevant structural noise while preserving predictive signal
• The compressed subgraph serves as a natural counterfactual explanation
• Balances the trade-off between conciseness and predictive sufficiency