SOFIA: Quantifying Sampling-Induced Explanation Instability in Graph Neural Networks

Abstract Post-hoc explainability tools for Graph Neural Networks rest on an implicit assumption: that the explanations they produce reflect stable properties of a node's structural role in the graph. This assumption is violated whenever the underlying model was trained with neighbor sampling — a universally adopted scalability practice that restricts each node's visible neighborhood to a randomly drawn subset during training. We introduce Sofia, a framework for measuring Sampling-induced explainability instability in GNNs, and present the first systematic empirical study of how training-time neighbor sampling affects post-hoc explanation outputs. Sofia trains matched pairs of full-neighborhood and sampled Graph Convolutional Networks on three real-world datasets spanning different homophily levels and degree distributions — Cora, Reddit, and Actor — and compares their explanations using Jaccard overlap against an empirically measured same-model noise floor, controlling for both explainer stochasticity and node degree. Across all conditions, sampled models maintain accuracy parity with full-neighborhood models, isolating training-time neighborhood visibility as the sole varying factor. On Reddit, a high-degree graph where aggressive sampling excluded a mean of 89.7% of true neighbors, cross-model explanation agreement dropped to 0.292 against a noise floor of 0.538, with the influential-neighbor exclusion fraction significantly predicting per-node instability after degree control (β = 0.687, p = 3.33e-15, partial R² = 0.095). On Actor, a heterophilous graph, a significant effect emerged at a lower mean exclusion fraction of 71.1% (β = 0.255, p < 0.001, partial R² = 0.130), consistent with the prediction that signal concentration in heterophilous neighborhoods amplifies instability independently of raw exclusion magnitude. On Cora, a low-degree homophilous graph, no significant effect was observed (β = -0.116, p = 0.401), confirming that the instability is structure-dependent. These results demonstrate that post-hoc GNN explanations in production systems are partially determined by an arbitrary training hyperparameter rather than by genuine structural node properties, and establish the SOFIA-Index as a practical per-node diagnostic for sampling-contaminated explanations.