Faithfulness Metric

Fidelity measures how well an explanation mimics the original model's behavior. A faithful explanation must preserve the GNN's prediction when only the explanatory subgraph is retained. The Fidelity+ score calculates the accuracy of the original model on the extracted subgraph, while Fidelity- measures the drop in performance when the explanation is removed. High fidelity indicates the explanation captures the true decision boundary.

The gold standard for faithfulness assessment involves perturbation analysis. This systematically removes or masks the top-k most important nodes and edges identified by an explainer and measures the resulting change in prediction probability. A faithful explanation causes a sharp drop in confidence when removed. Key variants include:

• Node Removal: Deleting critical nodes and observing prediction flip
• Edge Masking: Zeroing out important adjacency matrix entries
• Feature Perturbation: Adding noise to salient node features

A faithful explanation must be both contrastive and sufficient. Sufficiency means the extracted subgraph alone is adequate to produce the original prediction—no additional context is needed. Contrastivity ensures the explanation distinguishes the predicted class from alternative outcomes. A subgraph that is sufficient but not contrastive may simply be a universal salient structure, failing to explain why a specific class was chosen over another.

Sparsity acts as a critical inductive bias for faithfulness. A compact explanation subgraph is more likely to isolate the causal structure rather than capture spurious correlations. Methods like the Graph Information Bottleneck explicitly optimize for minimal subgraphs that retain maximal mutual information with the label. Sparsity is measured as the fraction of original edges retained; lower values indicate more concise explanations, but only if fidelity remains high.

True faithfulness requires causal grounding, not mere correlation. An explanation may achieve high fidelity by capturing shortcut features that correlate with the label in training data but fail under distribution shift. Structural Causal Models and invariant risk minimization principles are increasingly used to evaluate whether an explanation captures the true generative mechanism. A causally faithful explanation remains valid under interventions on the graph structure.

A faithful explanation must exhibit stability—small, imperceptible perturbations to the input graph that do not change the prediction should not significantly alter the explanation. This is distinct from adversarial robustness. Stability is evaluated by adding controlled noise to non-salient regions and measuring the Jaccard similarity between the original and perturbed explanations. Unstable explanations indicate the explainer is fitting to brittle, non-robust features of the GNN.