# Are Targeted Messages More Effective?

arXiv: https://arxiv.org/abs/2403.06817 · HTML: https://mlsanity.com/paper/2403.06817/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 11 Mar 2024.

## Builds on (most cited first, 11 of 11)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [Graded modal logic and counting bisimulation](https://mlsanity.com/paper/1910.00039/) (2019)
- [First-Order Logic with Counting: At Least, Weak Hanf Normal Forms Always Exist and Can Be Computed!](https://mlsanity.com/paper/1703.01122/) (2017)

## Built on by (most cited first, 1 of 1)

- [Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks](https://mlsanity.com/paper/2603.14846/) (2026)

## Abstract (arXiv)

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.