Verifying Quantized Graph Neural Networks is PSPACE-complete
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916894697586688 |
|---|---|
| author | Sälzer, Marco Schwarzentruber, François Troquard, Nicolas |
| author_facet | Sälzer, Marco Schwarzentruber, François Troquard, Nicolas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16244 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Verifying Quantized Graph Neural Networks is PSPACE-complete Sälzer, Marco Schwarzentruber, François Troquard, Nicolas Logic in Computer Science Computational Complexity Machine Learning 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. |
| title | Verifying Quantized Graph Neural Networks is PSPACE-complete |
| topic | Logic in Computer Science Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2502.16244 |