Verifying Quantized Graph Neural Networks is PSPACE-complete

Sälzer, Marco; Schwarzentruber, François; Troquard, Nicolas

doi:10.24963/ijcai.2025/519

Verifying Quantized Graph Neural Networks is PSPACE-complete

Marco Sälzer, Francois Schwarzentruber, Nicolas Troquard

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 4660-4668.

https://doi.org/10.24963/ijcai.2025/519

Keywords

Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning
Machine Learning: ML: Other
Knowledge Representation and Reasoning: KRR: Automated reasoning and theorem proving

Abstract

In this paper, we investigate verification of quantized Graph Neural Networks (GNNs), where some fixed-width arithmetic is used to represent numbers.

We introduce the linear-constrained validity (LVP) problem for verifying GNNs properties, and provide an efficient translation from LVP instances into a logical language. We show that LVP is in PSPACE, for any reasonable activation functions. We provide a proof system. We also prove PSPACE-hardness, indicating that while reasoning about quantized GNNs is feasible, it remains generally computationally challenging.

Marco Sälzer, François Schwarzentruber, and Nicolas Troquard. 2025. Verifying Quantized Graph Neural Networks is PSPACE-complete. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 4660–4668. https://doi.org/10.24963/ijcai.2025/519

@inproceedings{ijcai2025p519,
  title     = {Verifying Quantized Graph Neural Networks is PSPACE-complete},
  author    = {Sälzer, Marco and Schwarzentruber, François and Troquard, Nicolas},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {4660--4668},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/519},
  url       = {https://doi.org/10.24963/ijcai.2025/519},
}

TY  - CPAPER
TI  - Verifying Quantized Graph Neural Networks is PSPACE-complete
AU  - Sälzer, Marco
AU  - Schwarzentruber, François
AU  - Troquard, Nicolas
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 4660
EP  - 4668
DO  - 10.24963/ijcai.2025/519
UR  - https://doi.org/10.24963/ijcai.2025/519
ER  -