4 papers
The Boolean Power of ReLU
Pablo Barceló, Floris Geerts, Matthias Lanzinger +2
We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in -MPLang, for any collection of eventually c…
A Logical View of GNN-Style Computation and the Role of Activation Functions
Pablo Barceló, Floris Geerts, Matthias Lanzinger +2
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…
Message Passing on the Edge: Towards Scalable and Expressive GNNs
Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy +3
Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attenti…
Homomorphism Counts as Structural Encodings for Graph Learning
Linus Bao, Emily Jin, Michael Bronstein +2
Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on gr…