# On the expressive power of message-passing neural networks as global feature map transformers

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 17 Mar 2022.

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

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [On the expressive power of query languages for matrices](https://mlsanity.com/paper/1709.08359/) (2017)
- [On the expressive power of linear algebra on graphs](https://mlsanity.com/paper/1812.04379/) (2018)

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

- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Learning Graph Neural Networks using Exact Compression](https://mlsanity.com/paper/2304.14793/) (2023)
- [Graph Neural Networks and Arithmetic Circuits](https://mlsanity.com/paper/2402.17805/) (2024)
- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)
- [Halting Recurrent GNNs and the Graded μ-Calculus](https://mlsanity.com/paper/2505.11050/) (2025)
- [Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks](https://mlsanity.com/paper/2507.20226/) (2025)
- [The Boolean Power of ReLU](https://mlsanity.com/paper/2608.12617/) (2026)

## Abstract (arXiv)

We investigate the power of message-passing neural networks (MPNNs) in their capacity to transform the numerical features stored in the nodes of their input graphs. Our focus is on global expressive power, uniformly over all input graphs, or over graphs of bounded degree with features from a bounded domain. Accordingly, we introduce the notion of a global feature map transformer (GFMT). As a yardstick for expressiveness, we use a basic language for GFMTs, which we call MPLang. Every MPNN can be expressed in MPLang, and our results clarify to which extent the converse inclusion holds. We consider exact versus approximate expressiveness; the use of arbitrary activation functions; and the case where only the ReLU activation function is allowed.