Abstract
This paper investigates the expressivity of Graph Neural Networks (GNNs) by comparing 1-sided (isotropic) and 2-sided (anisotropic) message-passing schemes. While intuitively more powerful, 2-sided GNNs are shown to be equivalent to 1-sided GNNs in non-uniform settings. However, a separation exists in uniform settings specifically for SUM aggregation, a distinction rooted in the relationship between modal and guarded fragments of first-order logic.
Introduction: 1-Sided vs. 2-Sided Messaging
In Graph Neural Networks (GNNs), the fundamental operation is message passing. A "standard" approach involves a node broadcasting the same message to all its neighbors, known as 1-sided or isotropic message passing. Conversely, many advanced architectures utilize "targeted" or 2-sided (anisotropic) messages, where the message is a function of both the source and target node states.
The central question is whether this added complexity of "targeting" messages actually increases the computational power of the GNN—that is, can 2-sided GNNs compute functions that 1-sided GNNs cannot? This question ties deeply into Descriptive Complexity, specifically the difference between "modal" and "guarded" fragments of first-order logic with counting.
Theoretical Framework
The authors employ two primary strategies to tackle this problem:
- Logical Characterization: They map GNN architectures to specific fragments of logic. 1-sided GNNs correspond to the modal fragment (MFO+C), while 2-sided GNNs correspond to the guarded fragment (GFO+C). By proving these logics are equivalent (Theorem 1.3), they conclude that "targeted" quantification doesn't add power to this specific logic over undirected graphs.
- The Hashing Trick: To prove this equivalence, the authors introduced a novel "hashing trick." They show that information requiring guarded variables (which see both nodes at once) can be encoded into large numbers, hashed, and passed through modal quantifiers without loss of essential information.
The Expressivity Gap: Uniform vs. Non-Uniform
The study reveals a critical distinction between "uniform" and "non-uniform" settings:
- Non-Uniform Setting: If we can choose a different GNN for every graph size, 1-sided and 2-sided GNNs are exactly equal in power. This suggests that for many practical applications with consistent graph sizes, the extra complexity of anisotropic messages may not provide fundamental gains in expressivity.
- Uniform Setting: If a single GNN must work across all graph sizes, 2-sided GNNs finally pull ahead. They can solve queries (like "does this node have a neighbor with a higher degree?") that 1-sided GNNs cannot (Theorem 5.1).
The Deciding Factor: Aggregation Functions
The superiority of 2-sided GNNs in the uniform setting is highly dependent on the choice of aggregation function. The authors prove that the advantage of 2-sided GNNs only exists when using SUM aggregation. If the GNN is restricted to MEAN or MAX aggregation, the 1-sided and 2-sided versions become equivalent again (Theorem 5.9). This is because MAX and MEAN are less sensitive to exact counts, allowing 1-sided GNNs to simulate 2-sided behavior using one-hot encodings of neighbor states.
Conclusion and Future Work
While 2-sided GNNs appear more sophisticated, their theoretical advantage is confined to uniform settings with SUM aggregation. In many practical non-uniform scenarios, the two are expressively equivalent. Future work remains to explore these dynamics in recurrent GNNs, polynomial-size families, and link-prediction tasks. While the paper proves theoretical equivalence in some cases, 2-sided GNNs might still be easier to train or more sample-efficient in practice, even if they aren't "more expressive" in a limit-case sense.
Summary updated