Verifying Quantized Graph Neural Networks is PSPACE-complete

Marco Sälzer, François Schwarzentruber, Nicolas Troquard
2/22/2025
cs.LOcs.CCcs.LG

No confident code implementation found for this paper.

Abstract

In this paper, we investigate the 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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Lecture Notes on Verifying Graph Neural Networks

82% match2025

Exact Verification of Graph Neural Networks with Incremental Constraint Solving

79% match2025

A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

79% match2024

On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmetic

79% match2024

Verifying message-passing neural networks via topology-based bounds tightening

78% match1 repo62024

Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure

78% match2024

Cite this paper

@article{slzer2025verifying,
  title  = {Verifying Quantized Graph Neural Networks is PSPACE-complete},
  author = {Marco Sälzer and François Schwarzentruber and Nicolas Troquard},
  year   = {2025},
  eprint = {2502.16244},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2502.16244v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2502.16244.svg)](https://codeofpaper.com/paper/2502.16244)

Discussion