acceptodds
Under review as a conference paper at ICLR 2027

On the Computational Complexity of Explaining Graph Neural Networks

Abstract

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.

Primary area:
interpretability and explainable AI
Keywords:
Formal Explainability, Computational Complexity, GNN Explanations, Fixed-Parameter Tractability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_x7XZOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper analyzes the computation complexity of factual and counterfactual explanations for GNNs. The authors formalizes five computational problems and derive hardness and completeness results for fixed bounded AC-GNNs. They show fixed-parameter tractability when parametrized by the tree width of the input graph.

Critical strengths

The paper has systematic complexity theory analysis and analyzing the complexity on data is interesting.

Critical weaknesses
  1. The framework is restricted on only GNNs with binary node attributes and limited graph modifications. In particular, the paper doesn't discuss continuous or categorical node or edge features, which are common in real-world graph data. Graphs can be modified in various ways, such as deleting node or adding new edges, but this paper only considers edge removal and binary node feature flipping. This raises my concern about how the conclusions extend to common GNNs and data.

  2. There is no empirical validation or practical algorithm in the paper, which makes it difficult to assess how practical the theoretical results are. The authors should at least conduct some case study with real concrete algorithms and runtime measurements on some popular GNN architectures and real data. Even a small scale empirical study will substantially increase the paper's quality.

Questions for authors

Could the author briefly clarify what commonly used GNN architectures and data can be covered in the paper's analysis?

2 comments

We thank the reviewer for engaging with our work.

Categorical node features can be one-hot encoded and can therefore be encoded in our framework. Hence, prior work (such as [1,2,3]) treats binary node labels as a standard assumption.

Many practical works learn masks on the node features or existing edges [4,5,6], which aligns with our definition. Indeed, other semantics with edge additions are possible. However, these semantics are less established in the literature. Furthermore, such semantics do not allow exploiting the graph structure, since arbitrary completions with edge additions would, for example, yield graphs of unbounded treewidth. Thus, this is less interesting for our theoretical analysis.

Regarding commonly used GNN architectures: Architectures that use max aggregation (such as the max-pooling variant of GraphSAGE) are captured by our analysis. For a more detailed answer, please see the global reply.

[1] Barceló, et al. The Logical Expressiveness of Graph Neural Networks. ICLR 2020

[2] Martin Grohe. The Logic of Graph Neural Networks. LICS 2021

[3] Cuenca Grau et al. The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic. AAAI 2026

[4] Ying et al. GNNExplainer: Generating Explanations for Graph Neural Networks. NeurIPS 2019

[5] Luo et al. Parameterized Explainer for Graph Neural Network. NeurIPS 2020

[6] Funke et al. Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks. TKDE 2023

Thank you for the responses and revisions. The additional hardness results without node attributes and the clarification of the architectural assumptions strengthen the paper and address several of my concerns.

However, my concern about the broader significance remains. The analysis does not cover continuous features, and the positive tractability results do not generally extend to standard sum or mean aggregation. It is also unclear how the results apply to a broader range of XAI methods, such as Shapley-based or propagation-based explanations. The practical benefits of the FPT results also remain unclear.

Therefore, I would maintain my rating, while I have to clarify that my assessment focuses on the relevance to GNN explainability rather than verification of the complexity-theoretic proofs.

Reviewer_41H5OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the computational complexity of local post-hoc explanations for graph classification tasks. The authors formalise five explanation queries: three factual queries about sufficiency (CSR, MSR, and FMSR), one quantitative query (CC), and one counterfactual query (MCR). The analysis is based on data complexity, i.e., keeping the GNN fixed while allowing the input graph to vary. Building on Theorem 1, assuming that a graph classifier is computable by a bounded AC-GNN with final bounded readout, the authors show that the five queries become fixed-parameter tractable (FPT) when they are parameterised by the treewidth of the input graph.

Critical strengths
  1. Relevant research question: as explained in the paper, formal guarantees for GNN explanations are largely overlooked. The analysis provided here complements well the existing taxonomic and empirical studies.

  2. Data complexity setting: the hardness results hold for a fixed GNN, which seems to differ from previous analysis where the classifier is part of the input. Furthermore, hardness already holds for a restricted architecture. Therefore, it should transfer to more expressive GNNs.

  3. Complete characterisation: the paper provides upper and lower bounds for each query. Additionally, positive results (i.e., the FPT) are shown for bounded treewidth graphs.

Critical weaknesses
  1. Bounded GNN assumption: from my understanding, as mentioned in the strengths, the hardness results transfer to more expressive architectures. However, the positive result in Theorem 7 only holds when AC-GNNs with a final bounded readout are used. In practice, the most popular GNNs rely on sum/mean aggregation and readout, which are not bounded. Thus, the claim that the results 'establish tractability for practically relevant graph classes' does not necessarily hold for the GNNs that are actually used on such graph classes. Could you please clarify this point?

  2. Edge and node information in the proofs: the paper assumes to analyse explanations in terms of subgraphs. In some of the proofs, the edges are fixed and the hardness comes from unspecified/flipped node attributes. However, many GNN explainers keep node features fixed and only select/delete edges. Do the hardness results still hold in this case?

  3. Connection to practical explainers: the formalised queries are exact, but most of the practical explainable methods optimise soft masks or probabilistic objectives. I have the feeling that a discussion linking the theoretical findings (and their implications) to existing explainable methods is missing. Could you please elaborate and expand on this point?

Overall, I lean towards weakly rejecting the paper. I am willing to raise my score if my concerns are addressed.

Questions for authors

See above.

1 comment
Reviewer_41H5OpenReview ↗

Response to rebuttal

I would like to thank the authors for the general response and for the revisions. The new hardness proofs without node attributes (Appendix D) and the discussion of practically relevant bounded architectures address my main concerns. Theorem 8 is also a valuable addition, since it shows that the tractability results do not extend to unbounded sum aggregation in general. The extended related work further clarifies the connection between the formal queries and existing faithfulness metrics. Finally, the practical applicability of the FPT results (e.g., the size of the logical sentence for a trained GNN) remains an open point, but I believe it can be addressed in future work. Overall, considering the overall rebuttal, I am increasing my score to 3.

Reviewer_n7LsOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the computational complexity of exact local explanations for binary graph classification by a fixed GNN. It defines partial instances that specify some existing edges and Boolean node attributes, with completions allowed to restore unspecified existing edges and assign unspecified attributes. Within this framework, it studies checking sufficiency, deciding whether a small sufficient reason exists, finding an inclusion-minimal sufficient reason, counting prediction-preserving completions, and deciding whether a small counterfactual edit exists.

The paper establishes coNP-, (\Sigma_2^P)-, (\mathrm{FP}^{\mathrm{NP}})-, #P-, and NP-completeness, respectively, under its stated reduction conventions. Importantly, the hardness constructions use fixed classifiers, rather than encoding each problem instance into a different GNN. It also establishes a logical characterization of bounded AC-GNN graph classifiers with bounded final readout and uses MSO model-checking, optimization, and counting results to show fixed-parameter tractability in graph treewidth for all five queries. Validation consists of reductions and proofs, with full arguments in the appendix.

Critical strengths
  1. Hardness persists with a fixed classifier. This is the most consequential contribution. Since a GNN can classify graphs of varying sizes, fixing the network gives a natural setting in which to study explanation complexity. The reductions show that computational difficulty can reside in the explained graph itself. The classification also distinguishes verification, cardinality minimization, inclusion-minimal search, counting, and counterfactual search, giving a more informative picture than a single generic hardness result.

  2. A unified tractability result complements the lower bounds. The MSO representation captures partial instances, completions, and sufficiency in one framework, then supports decision, optimization, search, and counting. The counterfactual characterization through maximum-size nonsufficient partial instances is a useful connection. Together, these results identify a precise structural regime in which exact explanation becomes tractable, while the discussion correctly acknowledges that logical meta-theorems do not guarantee useful practical running times.

Critical weaknesses
  1. The implications for purely structural GNN explanations remain limited. The hardness proofs rely substantially on varying Boolean node attributes: CSR encodes colour assignments in attributes, CC encodes vertex subsets in attributes, and the MCR reduction allows a solution entirely through attribute flips. In the MSR and FMSR constructions, structural constraints force sufficient reasons to retain the entire edge set. Thus, these results do not establish the corresponding hardness classifications when node attributes are fixed and explanations may only select or delete edges. This limits the reach of the paper’s connection to subgraph and edge-deletion explainers, although it does not invalidate the stated joint structure-and-attribute results.

  2. The positive result has a narrower architectural scope than the broad motivation might suggest. Fixed-parameter tractability requires bounded aggregation and bounded final readout; it is not established for unrestricted sum or mean aggregation. Moreover, the result follows through general logical meta-theorems rather than a specialized algorithm with assessed dependence on the network and treewidth. The paper acknowledges the algorithmic limitation, but a concrete account of which practical architectures satisfy its assumptions would help establish the significance of the tractable regime.

Questions for authors
  1. Scope clarification: Which hardness classifications, if any, already follow from the presented constructions when node attributes are held fixed and only edges may vary? Please distinguish results established here from cases that remain open.

  2. Architectural clarification: Which commonly used aggregation/readout combinations satisfy the boundedness assumptions exactly? In particular, can you give a concrete architecture illustrating the positive result and explain which assumptions fail for standard sum- or mean-based alternatives?

  3. Explanation-semantics clarification: Can you make explicit which cited practical explainers target preservation across all admissible completions, rather than preservation on a selected subgraph or with high probability under a perturbation distribution? This distinction affects how directly the complexity results apply to existing explanation objectives.

1 comment
Reviewer_n7LsOpenReview ↗

Response to rebuttal.

Thanks to the authors for the response. Most of my comments and concerns have been addressed. I am now more confident to keep the score for weak acceptance.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global reply and summary of the updates

We thank the reviewers for their constructive feedback and for unanimously appreciating our theoretical data-complexity perspective and precise characterization of (in)tractability. Their feedback has motivated important improvements, now incorporated into the updated paper.

We identify three main concerns raised by the reviewers, which we address through revisions to the main text (highlighted in blue) and additional theorems and proofs in the new Appendix D.

C1. [Rev n7Ls W1, Q1 and Rev 41H5 W2] Can hardness arise from graph structure and edge deletion alone?

Although the original hardness proofs use node attributes for simplicity, these are not necessary. We now provide hardness proofs for all explanation queries without node attributes in Appendix D.

The new proofs share a common insight: we can replace node attributes with a characteristic number of leaves attached to each node (see Figure 4, Page 23). Deleting edges connecting these leaves then simulates changes to node attributes, allowing us to adapt the original reductions.

C2. [Rev n7Ls Q3 and Rev 41H5 W3, Rev x7XZ W1] Practical relevance of the explanation semantics.

We have expanded the discussion of related work using notions closer to our formal explanation queries (Section 2). Our factual queries (CSR, MSR, FMSR, CC) formalize sufficient graph explanations. The most relevant works are:

  • Azzolin et al. [1, 2] define sufficient explanations as subgraphs preserving predictions under all completions. They introduce a faithfulness metric, EST [2], that checks this property and empirically show that practical GNN explanations can be misleading when sufficiency is not satisfied.

  • Zheng et al. [3] define robust fidelity (RF), a similar faithfulness measure that considers only edge deletions and averages over the prediction changes. Count Completions (CC) formalizes the counting underlying RF.

  • Funke et al. [4] propose stable explanations, restricting admissible completions to node-attribute flips. They fix a subset of attributes and measure stability as the probability that random assignments of the remaining features preserve the prediction. Maximum stability thus corresponds precisely to a sufficient reason when edges are fixed.

We emphasize that a key contribution of our work is providing precise formal semantics for explanations, which are often defined only heuristically in practical implementations.

Regarding Soft Mask and Probabilistic Robustness: Most GNN explanation methods based on soft-mask optimization use continuous masks as differentiable proxies for discrete subgraph selection. Their prediction-preserving cross-entropy/entropy based objectives are minimised exactly when the masks are hard and assign probability one to the original predicted class.

Methods that estimate probability of the GNN preserving the predictions under changes outside the explanation [2,3,4] are essentially estimating the proportion of extensions that preserve prediction. Our count completion query exactly formalizes the computation required to evaluate such a proportion.

C3. [Rev n7Ls W2, Q2 and Rev 41H5 W1, Rev x7XZ W1] Architectural clarifications and the relevance of bounded aggregation.

  • Although bounded aggregation restricts our tractability results, it covers practically relevant architectures. These architectures include max-pooling GraphSAGE [5], that uses max as the only aggregation. Note that max is a 1-bounded aggregation, as it is oblivious to multiplicities of values, and only uses the absolute maximum. We now discuss this after Theorem 7.
  • Ahvonen et al. [6] show that specific implimentations of summation act as bounded aggregation in their fixed floating-point model, further motivating its study.
  • Bounded aggregations also include max-kk-sum, used in the analysis of monotonic max-sum GNNs [7].

These examples demonstrate the practical relevance and potential architectures that can be constructed using bounded-aggregation GNNs.

We also added Theorem 8 (proof in Appendix C), complementing our tractability results. It shows that unbounded sum aggregation leads to intractability even on bounded-treewidth graphs. The hardness already arises from the ability to compare the numbers of neighbours of different types

[1] Azzolin et al. Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective. ICML 2025

[2] Azzolin et al. GNN Explanations that do not Explain and how to find them. ICLR 2026

[3] Zheng et al. Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks. ICLR 2024

[4] Funke et al. Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks. TKDE 2023

[5] Hamilton et al. Inductive representation learning on large graphs. NeurIPS 2017

[6] Ahvonen et al. Logical characterizations of recurrent graph neural networks with reals and floats. NeurIPS 2024

[7] Cucala et al. On the Correspondence Between Monotonic Max-Sum GNNs and Datalog. KR 2023

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.