Sufficient Reasons for Explaining GNNs

Explanations of graph neural network (GNN) predictions are almost universally subgraphs of the input (or soft masks over it), judged by fidelity, asking whether keeping or removing the subgraph preserves or changes the prediction. Yet the real reason behind a GNN prediction routinely involves more than what is present—a missing edge, a negative condition on every neighbor, the absence of a motif. No subgraph can express such non-monotone reasons, though one may still pass every fidelity test. We propose sufficient reasons for GNNs: inclusion-minimal sets of (positive and negative) facts about the input such that every graph of the same size satisfying them receives the same prediction. The explanation is thus a certificate rather than a score. Analysing GNN decision classes in the counting logic C${}_2$, we show that they can be stratified by graph size, which fixes the context in which explanations are valid. Since checking every graph consistent with a candidate explanation is generally infeasible, we give a randomized algorithm that, with PAC guarantees, returns an $\epsilon$-sufficient reason from which no fact can be removed. In controlled synthetic experiments with GNN-expressible target properties, our method finds an $\epsilon$-sufficient explanation for every instance, while existing subgraph explainers do so only for a minority of instances, seldom for non-monotone properties, and with larger explanations whenever they succeed.