A Logical View of GNN-Style Computation and the Role of Activation Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917535346065408 |
|---|---|
| author | Barceló, Pablo Geerts, Floris Lanzinger, Matthias Pakhomenko, Klara Bussche, Jan Van den |
| author_facet | Barceló, Pablo Geerts, Floris Lanzinger, Matthias Pakhomenko, Klara Bussche, Jan Van den |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19332 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Logical View of GNN-Style Computation and the Role of Activation Functions Barceló, Pablo Geerts, Floris Lanzinger, Matthias Pakhomenko, Klara Bussche, Jan Van den Machine Learning Logic in Computer Science 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. |
| title | A Logical View of GNN-Style Computation and the Role of Activation Functions |
| topic | Machine Learning Logic in Computer Science |
| url | https://arxiv.org/abs/2512.19332 |