Are Targeted Messages More Effective?
Martin Grohe Eran Rosenbluth
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.