Statistical Subgraph Explanations for Graph Neural Networks via Latent Node Inference

Post-hoc explanations of graph neural networks (GNNs) often rely on learned edge masks or combinatorial search, leaving the statistical evidence for the selected structure implicit. We recast explanatory subgraph discovery as latent node inference and investigate when departures from background connectivity support explanations of a fixed GNN. We develop two complementary methods without training an auxiliary neural explainer. HierExplainer uses variational inference under a Bernoulli block model for each specific target to estimate posterior node-membership probabilities. HypoExplainer screens prediction label pairs of GNN using edge distribution after Bonferroni correction tests against a supervised background reference, then constructs explanations within each target’s computation graph. Our theory distinguishes structural recovery from predictive faithfulness: under explicit compatibility assumptions, HierExplainer’s posterior objective combines prediction fidelity with structural regularization, while HypoExplainer admits an asymptotic recovery guarantee under edge independence and minimal signal conditions. Experiments assess recovery, faithfulness, stability, and resource cost on synthetic motif benchmarks and a protein-protein interaction network.