On the Computational Complexity of Explaining Graph Neural Networks

We study the computational complexity of *local post-hoc explanations* for graph classification using Graph Neural Networks (GNNs). These explanations clarify why a GNN predicts a label on a given graph. Explaining these predictions is key to their safe deployment and can enable scientific knowledge discovery. *Factual explanations* highlight a subgraph that suffices for the prediction, and *counterfactual explanations* identify a minimal edit that changes it. We use computational complexity to analyse these explanations. We make three key contributions. First, we formalise computational problems that capture factual and counterfactual GNN explanations. Second, we fully characterise their computational complexity. Our complexity analysis treats the GNN as fixed, rather than as part of the input, and establishes hardness even in this setting. Third, we show that for fixed bounded GNNs, these explanations are fixed-parameter tractable on bounded-treewidth graphs. Our results give a systematic basis for comparing different types of GNN explanations and establish tractability for practically relevant graph classes.