3 citations · 4 across the 6 of their papers we have counts for
7 papers
Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu
We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, e…
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…
Homomorphism Counts for Graph Neural Networks: All About That Basis
Emily Jin, Michael Bronstein, İsmail İlkan Ceylan +1
A large body of work has investigated the properties of graph neural networks and identified several limitations, particularly pertaining to their expressive power. Their inability…
On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
Matthias Lanzinger, Pablo Barceló
Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the -dimensional Weisfeiler-Le…