Are Targeted Messages More Effective?

Martin Grohe, Eran Rosenbluth

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.

2-sided (anisotropic) message passing where the message depends on both the sender and receiver 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:

  1. 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.
  2. 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

Abstract

Graph neural networks (GNN) are deep learning architectures for graphs. Essentially, a GNN is a distributed message passing algorithm, which is controlled by parameters learned from data. It operates on the vertices of a graph: in each iteration, vertices receive a message on each incoming edge, aggregate these messages, and then update their state based on their current state and the aggregated messages. The expressivity of GNNs can be characterised in terms of certain fragments of first-order logic with counting and the Weisfeiler-Lehman algorithm. The core GNN architecture comes in two different versions. In the first version, a message only depends on the state of the source vertex, whereas in the second version it depends on the states of the source and target vertices. In practice, both of these versions are used, but the theory of GNNs so far mostly focused on the first one. On the logical side, the two versions correspond to two fragments of first-order logic with counting that we call modal and guarded. The question whether the two versions differ in their expressivity has been mostly overlooked in the GNN literature and has only been asked recently (Grohe, LICS'23). We answer this question here. It turns out that the answer is not as straightforward as one might expect. By proving that the modal and guarded fragment of first-order logic with counting have the same expressivity over labelled undirected graphs, we show that in a non-uniform setting the two GNN versions have the same expressivity. However, we also prove that in a uniform setting the second version is strictly more expressive.
BibTeX
@inproceedings{grohe2024are,
  author = {Martin Grohe and Eran Rosenbluth},
  title = {{Are Targeted Messages More Effective?}},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662093},
}
Figure