mlsanityData to 7 Oct 2026

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

arXiv 2203.09555 ↗First posted 17 Mar 2022cs.AI cs.LGcited by 8

Not on the map. Why?

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.

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

Builds on

9 of 24 references.

References · 9

  1. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  2. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  3. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  4. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  5. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  6. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  7. 2021The Logic of Graph Neural Networkscited by 84
  8. 2017On the expressive power of query languages for matricescited by 14
  9. 2018On the expressive power of linear algebra on graphscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 1; 2025: 3; 2026: 1.

8 papers.

  1. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  2. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  3. 2023Learning Graph Neural Networks using Exact Compressioncited by 3
  4. 2024Graph Neural Networks and Arithmetic Circuitscited by 3
  5. 2025A Logical View of GNN-Style Computation and the Role of Activation Functionscited by 3
  6. 2025Halting Recurrent GNNs and the Graded μ-Calculuscited by 2
  7. 2025Improving Subgraph Matching by Combining Algorithms and Graph Neural Networkscited by 1
  8. 2026The Boolean Power of ReLUcited by 0