A Logical View of GNN-Style Computation and the Role of Activation Functions
This work provides foundational insights into GNN expressiveness, which is incremental but clarifies the role of activation functions in graph learning.
The authors tackled the problem of understanding the expressive power of graph neural networks (GNNs) by analyzing MPLang, a declarative language capturing GNN computation, and showed that GNNs with ReLU are strictly more expressive for numerical queries than those with eventually constant activations and linear layers.
We study the numerical and Boolean expressiveness of MPLang, a declarative language that captures the computation of graph neural networks (GNNs) through linear message passing and activation functions. We begin with A-MPLang, the fragment without activation functions, and give a characterization of its expressive power in terms of walk-summed features. For bounded activation functions, we show that (under mild conditions) all eventually constant activations yield the same expressive power - numerical and Boolean - and that it subsumes previously established logics for GNNs with eventually constant activation functions but without linear layers. Finally, we prove the first expressive separation between unbounded and bounded activations in the presence of linear layers: MPLang with ReLU is strictly more powerful for numerical queries than MPLang with eventually constant activation functions, e.g., truncated ReLU. This hinges on subtle interactions between linear aggregation and eventually constant non-linearities, and it establishes that GNNs using ReLU are more expressive than those restricted to eventually constant activations and linear layers.