TL;DR
This paper provides the first precise logical characterizations of Graph Transformers and hybrid GPS-networks, revealing a fascinating paradox: transitioning from theoretical real numbers to practical floating-point numbers completely alters their expressiveness. While real-based models can only count relatively (e.g., computing ratios of vertex properties), float-based models exploit numerical underflow and saturation to perform absolute global counting.
What Problem Does This Paper Address?
Transformers have revolutionized natural language processing and computer vision, and they are increasingly being adapted for graph-structured data to overcome the limitations of traditional Graph Neural Networks (GNNs)—such as "over-squashing" and "over-smoothing." While the expressive power of GNNs is well-understood through its alignment with the Weisfeiler-Lehman isomorphism test and modal logic, the precise capabilities of Graph Transformers (GTs) have remained theoretically obscure.
This paper tackles a fundamental question: What can Graph Transformers actually compute, and how does their expressive power change when implemented with practical floating-point numbers instead of idealized real numbers?
Methods
The authors employ tools from finite model theory and mathematical logic to map neural network architectures to formal logic systems. They analyze two primary models under both soft-attention and average hard-attention mechanisms:
- Pure Graph Transformers (GTs): Models that treat graphs as "bags of vertices" and ignore edge structure during attention.
- GPS-Networks: Hybrid models that combine local GNN message-passing layers with global transformer layers.
To analyze these models across different number systems, the authors introduce several novel techniques:
- For Real Numbers ($\mathbb{R}$): They introduce a new structural equivalence relation called global-ratio graded bisimilarity ($\sim_{G\%}$) and prove a new van Benthem/Rosen-style theorem to characterize the limits of what real-based transformers can express within First-Order logic (FO).
- For Floating-Point Numbers (Floats): They exploit the inherent constraints of IEEE 754 float arithmetic. Specifically, they utilize the underflow phenomenon (where numbers close to zero round to exactly zero) and arithmetic saturation (where adding a small float to a large sum eventually stops changing the value) to show how networks can implicitly count.
Datasets
Not discussed in the paper. The authors explicitly state that this work focuses exclusively on theoretical analysis and does not involve any experimental evaluation or empirical datasets.
Key Insights and Ideas
- The Real vs. Float Paradox: In theoretical machine learning, floats are usually treated as approximations of real numbers. This paper shows that for transformers, changing the number system fundamentally alters the model's logic. Real-based models can compute arbitrary relative ratios but cannot absolutely count vertices globally. Float-based models lose exact arbitrary ratio computation but gain the ability to perform absolute global counting.
- Underflow as a Computational Feature: In float-based architectures, underflow is typically seen as a precision bug. Here, the authors demonstrate that a network can deliberately use matrix multiplications to force underflow, creating a sharp binary switch (0 vs. non-zero) that allows the network to check if a specific counting threshold has been crossed.
- Why Unique Hard-Attention Fails: The paper proves that graph transformers using unique hard-attention (attending only to the single vertex with the maximum score) are not isomorphism-invariant on general graphs. This provides a rigorous theoretical explanation for why they are rarely used in practical applications compared to soft or average hard-attention.
Key Results
The paper establishes exact equivalences between transformer architectures and specific fragments of logic:
Real-Number Setting (Relative to First-Order Logic)
- GPS-Networks have the exact same expressive power as Graded Modal Logic with the global modality (GML + G). They can express properties like "the graph contains a vertex labeled $p$," but cannot count absolutely (e.g., "the graph contains at least 10 vertices labeled $p$").
- Pure Graph Transformers match Propositional Logic with the global modality (PL + G).
Floating-Point Setting (Absolute Characterizations)
- Float-based GPS-Networks have the exact same expressive power as GML with the counting global modality (GML + GC). This means practical implementations can perform absolute global counting.
- Float-based Graph Transformers match Propositional Logic with the counting global modality (PL + GC).
Limitations and Future Work
- Naked Models: The primary analysis focuses on "naked" transformers—those operating without positional or structural encodings (like graph Laplacians). While the authors provide a brief appendix showing how to extend the float results to incorporate encodings, a comprehensive logical framework for the vast "zoo" of existing positional encodings remains open.
- Task Generalization: The core proofs target Boolean vertex classification. Although the authors note that the float-based results lift to graph classification and non-Boolean tasks, further formal exploration is required.
- Open Question for Reals: For real-valued networks, it remains an open question whether every GPS-network can be perfectly expressed as a GNN extended with a counting global readout mechanism (GNN + GC).
Summary updated