- 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
-
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.
-
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
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.
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