Graph Pruning

The most direct pruning approach where each node or edge receives an importance score from an explainer, and components falling below a predefined threshold are removed.

• Global threshold: A single cutoff value applied uniformly across the entire graph
• Percentile-based: Retains only the top-k% most important elements
• Adaptive thresholding: Adjusts cutoffs per node neighborhood based on local score distributions

Example: After running GNNExplainer, edges with importance scores below 0.1 are pruned, reducing a molecular graph from 200 edges to 45 while maintaining 98% prediction fidelity.

Prunes the graph by selecting a subgraph that maximizes the mutual information between its structural representation and the GNN's prediction.

• Formally: max I(G_sub; Y) where G_sub is the pruned subgraph and Y is the prediction
• Naturally discards spurious correlations that don't contribute to the decision
• Often implemented with a variational bound for tractable optimization

This approach is the theoretical foundation for methods like GIB (Graph Information Bottleneck), which compresses the input while preserving label-relevant structure.

Identifies the minimal set of edges whose removal would change the model's prediction to a different class, then prunes everything outside this critical set.

• CF-GNNExplainer searches for the smallest edge subset that flips the prediction
• Produces actionable recourse: shows exactly what must change for a different outcome
• Pruned graph contains only the causal backbone necessary for the original prediction

Example: In a credit risk graph, removing 3 specific transaction edges changes a default prediction from high-risk to low-risk, revealing the decisive financial connections.

Uses learned stochastic masks over graph edges during message passing to identify and prune irrelevant connections, as implemented in GSAT (Graph Stochastic Attention).

• Injects randomness into attention weights during training to prevent overfitting to noise
• A regularization term penalizes large subgraphs, encouraging minimal explanations
• After training, edges with consistently low attention probabilities are pruned

This method produces inherently sparse, interpretable subgraphs without requiring a separate post-hoc explainer, making it a self-explaining pruning technique.

An iterative process that incrementally removes low-importance components while monitoring the fidelity metric to ensure the pruned graph still mimics the original model's behavior.

• Step 1: Rank all edges/nodes by importance score
• Step 2: Remove the lowest-ranked component
• Step 3: Re-evaluate the GNN on the pruned graph
• Step 4: Stop when fidelity drops below a threshold (e.g., 95%)

This guarantees the pruned graph remains a faithful surrogate for the original prediction, balancing sparsity against explanatory accuracy.

Extends Layer-wise Relevance Propagation (LRP) to prune graphs by backpropagating the prediction score through each GNN layer and removing nodes with negligible relevance.

• GNN-LRP assigns relevance scores to input nodes by decomposing the output backwards
• Nodes with near-zero relevance across all target classes are structurally pruned
• Preserves the hierarchical flow of information through the network

Example: In a protein interaction graph, LRP pruning removes 60% of peripheral proteins while retaining the binding site subgraph critical to function prediction.

A model-agnostic framework that identifies the compact subgraph structure and small subset of node features most influential for a GNN's prediction. It learns a soft mask over edges and features by maximizing mutual information with the original model's output.

• Outputs a minimal, explanatory subgraph
• Can be applied to any GNN architecture without modification
• Provides both structural and feature-level explanations

A principle for learning explainable GNNs by compressing the input graph into a minimal subgraph that retains maximal mutual information about the label. This directly formalizes the pruning objective: discard structural noise while preserving predictive signal.

• Balances compression against prediction accuracy
• Provides a theoretical foundation for pruning decisions
• Naturally filters out spurious correlations in the graph

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

• High faithfulness means the pruned subgraph captures genuine decision logic
• Complements fidelity metrics for comprehensive evaluation
• Essential for validating pruning results before deployment

A self-explainable GNN framework where a generator module extracts a concise, causal subgraph (the rationale) and a predictor makes decisions based solely on that rationale. This bakes pruning directly into the model architecture.

• Generator and predictor are trained cooperatively
• Produces inherently interpretable predictions
• Eliminates the need for post-hoc explanation methods

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. Directly validates whether pruned components were truly irrelevant.

• Quantifies the impact of removing specific graph elements
• Used to benchmark different explainability methods
• Provides empirical justification for pruning thresholds

An explainability method using Monte Carlo Tree Search to efficiently explore and identify the most critical subgraph structures for GNN predictions. Unlike edge-level methods, it evaluates entire subgraphs as cohesive units.

• Captures higher-order structural interactions
• Uses Shapley values as the subgraph scoring function
• Particularly effective for molecular and biological graphs