Perturbation Analysis

Perturbation analysis operates on a simple causal principle: if an explanation correctly identifies the critical input features, removing or altering those features should cause a significant change in the model's output. The process involves three sequential steps:

• Extract an explanation from a GNN explainer, which identifies the most important nodes, edges, or node features for a specific prediction.
• Perturb the input graph by masking, removing, or adding noise to the elements deemed important by the explanation.
• Measure the prediction delta by comparing the model's output before and after the perturbation, quantifying the magnitude of change.

Perturbation analysis decomposes explanation quality into two competing quantitative metrics:

• Fidelity+ (or sufficiency): Measures the drop in prediction confidence when only the explained subgraph is retained and the rest of the graph is removed. A high score indicates the explanation captures all necessary information.
• Fidelity- (or necessity): Measures the drop in prediction confidence when the explained subgraph is removed from the original graph. A high score confirms the explanation identifies truly indispensable structures.
• Sparsity: Evaluates the size of the explanation subgraph relative to the original input. Smaller, more concise explanations that maintain high fidelity are preferred.

The method of perturbation critically influences the analysis outcome. Common strategies include:

• Hard masking: Completely removing identified nodes or edges from the adjacency matrix. This is the most direct intervention but can create disconnected graph components that the GNN was never trained on, introducing out-of-distribution artifacts.
• Soft masking: Reducing edge weights or node feature magnitudes by a continuous factor, allowing for gradient-based optimization of the mask itself.
• Feature perturbation: Replacing the features of important nodes with random noise, zero values, or marginal distributions to isolate the contribution of feature information versus structural position.
• Reference-based perturbation: Substituting nodes or edges with a learned or heuristic baseline state rather than simply deleting them, mitigating distribution shift.

A fundamental limitation of perturbation analysis is the out-of-distribution (OOD) artifact. When nodes or edges are removed, the resulting sparsified graph may not resemble any input the GNN encountered during training. The model's prediction change may then reflect its reaction to an anomalous input rather than the true importance of the removed structure.

• Mitigation strategies include training the GNN with random edge dropout during training to increase robustness, using generative models to fill in removed structures with plausible alternatives, or employing GraphMask which learns to mask messages in the latent space rather than the input space.

Perturbation analysis serves as the standard benchmark for comparing post-hoc explainers. In the original GNNExplainer paper, the authors evaluated their method by:

• Identifying the top-k edges for a node's prediction.
• Systematically removing those edges and measuring the drop in mutual information between the original and new prediction.
• Comparing against random edge removal and gradient-based baselines. Similarly, SubgraphX uses Monte Carlo Tree Search to find subgraphs and validates them by demonstrating that removing the identified subgraph causes a larger prediction drop than removing random subgraphs of equivalent size, confirming the explainer's fidelity.

Advanced perturbation frameworks distinguish between associational and causal importance:

• Associational perturbation measures correlation: removing a node changes the prediction because the node's features were predictive in the training distribution.
• Causal perturbation uses structural causal models (SCMs) and intervention operations (do-calculus) to determine if a node is a genuine cause of the label. This requires knowing or learning the causal graph underlying the data.
• Graph rationalization methods like DIR (Discovering Invariant Rationales) explicitly train a generator to extract subgraphs that are causally invariant across different environments, ensuring perturbation analysis reflects true causal mechanisms rather than spurious correlations.

A quantitative evaluation score that measures how accurately an explanation subgraph reflects the true reasoning process of the GNN. It is typically assessed by the drop in model performance when the explanation is removed.

• Core Principle: If the identified nodes/edges are truly causal, removing them must degrade prediction.
• Calculation: Often computed as Accuracy(Original) - Accuracy(Masked).
• Contrast with Fidelity: Faithfulness measures fidelity to the model's internal logic, not just output mimicry.

An evaluation metric that measures how well an explanation mimics the original model's behavior. It is often calculated as the accuracy of the original model when fed only the explanatory subgraph.

• High Fidelity: The subgraph alone reproduces the original prediction.
• Key Distinction: A high-fidelity explanation may not be faithful if the model uses spurious correlations.
• Use Case: Validating that the explainer has captured the decision boundary locally.

The process of systematically removing nodes or edges deemed irrelevant by an explainability metric to create a sparser, interpretable subgraph that preserves the original prediction.

• Mechanism: Masks are applied to the adjacency matrix based on importance scores.
• Goal: Isolate the minimal computational subgraph responsible for the output.
• Relation to Perturbation: Pruning is the structural action; perturbation analysis measures the impact of that action.

The minimal structural perturbations to a graph—such as removing specific edges or nodes—that would alter a GNN's prediction to a different outcome.

• Recourse Logic: Identifies what must change to flip a classification.
• Example: Removing a single bond in a molecule to change toxicity prediction.
• Perturbation Link: Counterfactuals are a specific class of perturbation designed for actionable recourse rather than just fidelity assessment.

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

• Optimization: max I(Y; G_sub) - β * I(G; G_sub).
• Outcome: Naturally yields a faithful explanatory subgraph.
• Advantage: Built-in regularization prevents trivial or over-complex explanations.

A targeted adversarial attack on GNNs that introduces small, imperceptible perturbations to the graph structure and node features to change a specific node's prediction.

• Perturbation Budget: Constrained by degree distribution preservation and feature co-occurrence.
• Dual Use: While an attack, it validates explainability by testing if explainers can detect adversarial structural changes.
• Evaluation: Used to benchmark the robustness of both GNNs and their explainers.