🤖 machine learning

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable

This paper introduces a logical language to characterize quantized aggregate-combine graph neural networks with global readout (ACR-GNNs) and proves that verifying these models is (co)NEXPTIME-complete, demonstrating that while they are computationally intractable to verify, they remain lightweight and accurate in practice.

Original authors: Artem Chernobrovkin, Marco Sälzer, François Schwarzentruber, Nicolas Troquard

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Artem Chernobrovkin, Marco Sälzer, François Schwarzentruber, Nicolas Troquard

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a high-tech security system for a massive, complex city. This system uses "Graph Neural Networks" (GNNs)—essentially super-smart AI detectives that don't just look at individual people, but at the connections between them (who is friends with whom, who lives where, who works where).

This paper is about two things: making these detectives "lighter" so they can run on cheap, tiny devices (like a smartwatch instead of a supercomputer), and proving whether we can actually trust them once they’ve been made lighter.

Here is the breakdown of the paper using a few metaphors.

1. The "Quantization" Problem: The Sketch Artist vs. The Photographer

In their original, "full-precision" state, these AI detectives are like high-resolution photographers. They see every tiny detail, every nuance, and every microscopic pixel. They are incredibly accurate, but their "files" are massive. If you try to put a high-res photographer into a tiny drone, the drone will crash because the files are too heavy.

To fix this, engineers use Quantization. This is like turning the photographer into a sketch artist. Instead of using millions of colors, the artist only uses 8 shades of gray. The "files" are now tiny and lightweight, meaning the drone can carry them easily.

The catch? When you turn a photographer into a sketch artist, you might lose the ability to tell the difference between a "dangerous person" and a "person holding a banana." You might make mistakes.

2. The "Verification" Problem: The Impossible Exam

The researchers wanted to know: "If we turn our photographer into a sketch artist, can we mathematically prove that they will still follow the rules?" (For example: "Will the sketch artist always identify a power plant as 'essential' if it serves 1,000 people?")

They discovered that this is a mathematically "intractable" problem.

Think of it like this: Imagine you have a massive, infinite library of every possible city layout in the universe. You want to prove that your sketch artist will never make a mistake in any of those cities. Because the cities can be any shape, any size, and have any number of connections, the number of "test cases" you would have to check is so astronomically large that even the fastest computer in the world would take longer than the age of the universe to finish the exam.

In technical terms, they called this (co)NEXPTIME-complete. In plain English: It is a nightmare to prove.

3. The "Global Readout" Twist: The Gossip Effect

The paper specifically looks at a type of GNN called an ACR-GNN. The "R" stands for Readout.

In a normal GNN, detectives look at their immediate neighbors. But with "Global Readout," the detectives also look at the entire city at once. It’s like a gossip effect: a detective in one corner of the city knows what is happening in the opposite corner because they are part of the "global" conversation.

This "gossip" makes the AI much smarter and better at understanding the whole picture, but it makes the "Verification Exam" (the one we mentioned above) even harder. It’s like trying to prove a rule is true when everyone in the city is constantly whispering to everyone else—the complexity explodes!

4. The Good News: The Sketch Artist is actually pretty good!

Despite the math being a nightmare, the researchers did some real-world testing. They took these "sketch artist" (quantized) models and put them to work on real data (like protein interactions).

Their findings were surprisingly positive:

Accuracy: The sketch artists were almost as good as the photographers! They kept most of the intelligence while being much smaller.
Efficiency: They were much faster and took up way less memory.
The "Sweet Spot": They found that if you use 8-bit or 6-bit "shades of gray," the AI stays very smart. If you try to go too low (like 4-bit), the AI starts to get confused and loses its edge.

Summary in a Nutshell

The researchers proved that while it is mathematically almost impossible to perfectly guarantee that a lightweight, "sketchy" AI will never make a mistake, we can still build these lightweight models and be very confident that they will work well in the real world. They’ve provided the "rulebook" (the logic) that future scientists will use to try and make these systems even safer.

Technical Summary: Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable

1. Problem Statement

Graph Neural Networks (GNNs) are increasingly deployed in critical domains such as drug discovery, social network analysis, and infrastructure monitoring. However, their "black-box" nature makes them difficult to verify for safety and regulatory compliance (e.g., the EU AI Act).

While previous research has addressed the verification of GNNs using formal logic, most models assumed idealized arithmetic (arbitrarily large integers or rationals). In real-world applications, GNNs are quantized (using INT8, FP8, or IEEE 754 floats) to reduce memory footprint and increase inference speed. Furthermore, most graph classification tasks rely on a global readout mechanism (aggregating all node features into a single graph-level vector). The authors identify a critical gap: the formal verification of quantized GNNs that include this global readout component is poorly understood and potentially computationally overwhelming.

2. Methodology

The authors approach the problem through three distinct lenses: logical characterization, complexity analysis, and empirical validation.

Logical Framework ($qL$): The authors introduce a new logical language, $qL$, designed to reason about Aggregate-Combine Graph Neural Networks with global Readout (ACR-GNNs). This logic is expressive enough to capture quantized computations with arbitrary activation functions. They demonstrate that $qL$ can simulate modal logics, allowing users to specify complex graph properties (e.g., "Does this node belong to a community where more than half the members have property $X$ ?").
Complexity Theory: To determine the difficulty of verification, they reduce the satisfiability problem of $qL$ to a quantized version of Quantifier-Free Boolean Algebra with Presburger Arithmetic (QFBAPA $\mathbb{K}$ ). They use Hintikka sets to encode constraints and a reduction from the Wang tiling problem to prove hardness.
Bounded Relaxation: Recognizing that the general problem is intractable, they relax the problem by bounding the number of vertices ( $N$ ). This transforms the problem into an NP-complete task, which they implement as a proof-of-concept using the ESBMC (Efficient SMT-based Context-Bounded Model Checker).
Empirical Quantization Study: They perform extensive experiments using Dynamic Post-Training Quantization (PTQ) on both synthetic (Erdős–Rényi) and real-world (Protein-Protein Interaction - PPI) datasets to evaluate the trade-off between model size, accuracy, and verification feasibility.

3. Key Contributions

Logical Characterization: Defined the logic $qL$, providing a formal "lingua franca" to represent both the GNN computation and the graph properties being verified.
Complexity Proofs: Proved that verifying quantized ACR-GNNs is (co)NEXPTIME-complete. This is a significant jump from the PSPACE-completeness of GNNs without global readout, proving that the readout mechanism makes verification highly intractable.
Decidability Result: Established that while the problem is computationally "hard" (intractable), it is nonetheless decidable.
Practical Baseline: Provided a prototype implementation for verifying GNNs in a bounded setting (limited number of vertices) and a comprehensive analysis of how different activation functions (ReLU, Sigmoid, GELU, etc.) affect quantization robustness.

4. Results

Complexity: The verification tasks (Sufficiency, Necessity, and Consistency) are proven to be (co)NEXPTIME-complete. This implies that finding a counterexample for a quantized GNN with readout is fundamentally difficult.
Quantization Performance:
- Accuracy: Quantized models (specifically 8-bit and 6-bit) maintain high accuracy, often within $\pm 1\%$ of the full-precision (FP32) models.
- Model Size: Dynamic PTQ achieved a significant reduction in model size (approximately 74% reduction).
- Robustness: The study found that accuracy degradation is highly dependent on the activation function and the bit-width. For example, trReLU and Softplus showed higher sensitivity to low precision, while ReLU and ELU were more robust.
Verification Scalability: The SMT-based verification tool (ESBMC) demonstrated a "state-space explosion." Even a small increase in the number of vertices leads to an exponential increase in verification time, confirming the theoretical complexity results.

5. Significance

This paper provides a theoretical "reality check" for the GNN community. It mathematically proves that verifying the safety of quantized, readout-enabled GNNs is one of the hardest problems in computational logic.

By establishing the (co)NEXPTIME-completeness, the authors steer future research away from attempting "perfect" general-purpose verifiers and toward more practical approaches, such as:

Verifying models within bounded graph sizes.
Developing quantization-aware training (QAT) specifically designed to improve formal verifiability.
Focusing on specific activation functions that are more "SMT-friendly" (e.g., piecewise-linear functions like ReLU).

Ultimately, the work bridges the gap between high-performance machine learning (quantization) and high-assurance software engineering (formal verification).