5 papers
Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data
Arie Soeteman, Balder ten Cate, Maurice Funk +3
The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent…
Expressive Power of Deep Homomorphism Networks over Relational Databases
Moritz Schönherr, Balder ten Cate, Maurice Funk +3
The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism…
Expressive Power of Graph Transformers via Logic
Veeti Ahvonen, Maurice Funk, Damian Heiman +2
Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph tr…
Logical Characterizations of GNNs with Mean Aggregation
Moritz Schönherr, Carsten Lutz
We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function, with the following results. In the non-uniform setting, such GNNs have exactly…
Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
Veeti Ahvonen, Damian Heiman, Antti Kuusisto +1
In pioneering work from 2019, Barceló and coauthors identified logics that precisely match the expressive power of constant iteration-depth graph neural networks (GNNs) relative t…