Explaining GNN Negatives Globally and Locally

This paper studies explanations for graph neural network (GNN) classifiers $\mathcal{M}$ when $\mathcal{M}$ makes negative predictions, such as loan denials, paper rejections, or job application turn-downs. The objective is to (a) provide global explanations of $\mathcal{M}$'s behavior and (b) generate counterfactual explanations locally at a vertex $u$, suggesting the minimal changes to features or topology around $u$ needed to flip $\mathcal{M}$'s prediction. We propose a class of rules that treat negative predictions as their consequences, and employ the 1-dimensional Weisfeiler-Leman (1-WL) test as a predicate, which is at least as expressive as GNN classifiers. We develop algorithms to (a) learn such rules for global explanations and (b) apply them to compute local counterfactuals. Extensive experiments on real-world graphs show that our approach outperforms state-of-the-art methods across major metrics.