GNNExplainer

GNNExplainer operates as a post-hoc explainer that treats any trained GNN as a black box. It requires no access to internal model weights or gradients, making it compatible with Graph Convolutional Networks (GCNs), GraphSAGE, GATs, and any other message-passing architecture. This universality is achieved by formulating explanation as an optimization problem over the input space rather than probing the model's internals.

Unlike methods that explain only graph topology or only node attributes, GNNExplainer simultaneously learns:

• A compact subgraph mask that identifies critical edges
• A feature selector mask that highlights relevant node attributes This joint optimization reveals how structural connections and node properties interact to drive a specific prediction, providing a holistic explanation for tasks like molecular property prediction or social network classification.

The explainer frames explanation as an information-theoretic optimization problem. It searches for a subgraph and feature subset that maximize the mutual information with the original model's prediction. Formally, this means finding the minimal explanatory graph that preserves the predicted label distribution, ensuring the explanation captures the true decision boundary rather than spurious correlations.

GNNExplainer supports two operational modes:

• Single-instance explanations: Generates a unique explanation for each individual node, edge, or graph prediction, useful for debugging specific model decisions
• Multi-instance explanations: Aggregates explanations across a class of nodes to discover global patterns and class-level decision rules, revealing systematic behaviors learned by the GNN across the entire dataset

The discrete subgraph selection problem is made tractable through continuous relaxation. Edge masks are parameterized as real-valued weights and optimized via gradient descent. An entropy regularization term and L1 penalty enforce sparsity, driving the mask toward a binary selection of the most critical edges. This yields explanations that are both compact and faithful to the original prediction.

Explanation quality is measured through rigorous metrics:

• Fidelity: The accuracy of the original GNN when evaluated solely on the extracted explanatory subgraph. High fidelity indicates the subgraph captures the essential decision logic
• Sparsity: The fraction of edges retained, with smaller subgraphs being more interpretable
• Contrastivity: The explanation's ability to distinguish the predicted class from alternative classes

The primary quantitative measure of an explanation's fidelity to the original model's reasoning. Faithfulness is assessed by removing the nodes or edges identified as important by GNNExplainer and measuring the resulting drop in prediction probability.

• A high faithfulness score means the explanation captured the true decision boundary
• Calculated as: original_prediction - prediction_on_masked_graph
• Complements the fidelity metric, which measures how well the explanation alone reproduces the original output

The core objective function that GNNExplainer optimizes to select an explanatory subgraph. It seeks a compact subgraph G_S whose structural and feature information has maximum mutual information with the GNN's prediction.

• Formally: max MI(Y, (G_S, X_S)) where Y is the prediction
• Balances completeness (capturing all relevant information) against conciseness (penalizing large subgraphs)
• This information-theoretic approach ensures the explanation is both sufficient and minimal

A fidelity assessment methodology that systematically masks or alters graph components and observes the prediction delta. GNNExplainer's output is validated by checking if removing its identified nodes causes a larger prediction drop than removing random nodes.

• Positive perturbation: removing top-k important nodes should sharply decrease confidence
• Negative perturbation: removing unimportant nodes should leave predictions stable
• Used to benchmark GNNExplainer against baselines like Grad-CAM on Graphs or random attribution

A theoretical principle closely related to GNNExplainer's objective. The Information Bottleneck compresses an input graph into a minimal representation that preserves maximal predictive information about the label, discarding irrelevant structural noise.

• Formalized as: min I(G; G_S) - β * I(G_S; Y)
• GNNExplainer implicitly applies this by regularizing subgraph size
• Directly inspired methods like GSAT (Graph Stochastic Attention) and Graph Rationalization

The minimal structural edits required to flip a GNN's prediction to a different class. While GNNExplainer identifies sufficient explanatory subgraphs, counterfactual methods like CF-GNNExplainer find the smallest edge deletions that change the outcome.

• Answers: 'What would need to be different for the opposite prediction?'
• Provides actionable recourse for graph-based decisions
• Complements GNNExplainer's descriptive explanation with prescriptive intervention paths

A game-theoretic alternative to GNNExplainer that assigns fair importance scores to nodes or edges by computing their marginal contribution across all possible coalitions. Unlike GNNExplainer's single optimization, Shapley methods guarantee axiomatic fairness.

• Satisfies efficiency, symmetry, dummy, and additivity axioms
• GraphSVX and SubgraphX apply Shapley values to graph explanations
• Computationally more expensive than GNNExplainer's gradient-based approach, but provides stronger theoretical guarantees