On the expressive power of message-passing neural networks as global feature map transformers
This work addresses foundational theoretical limitations in graph neural networks for researchers, but it is incremental as it builds on existing expressiveness studies.
The paper investigates the expressive power of message-passing neural networks (MPNNs) as global feature map transformers, introducing a formal language (MPLang) to compare expressiveness and analyzing conditions like exact vs. approximate transformations and activation functions.
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.