Expressive Power of Deep Homomorphism Networks over Relational Databases
Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Schönherr, Arie Soeteman · 2026
Read Expressive Power of Deep Homomorphism Networks over Relational Databases by Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Schönherr, Arie Soeteman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22852.txt.
Introduction
Schönherr and five coauthors study the expressive power of Deep Homomorphism Networks for learning over relational databases, motivated by limits of message-passing graph networks. Relating these networks to fragments of first-order logic, they tie max, sum, and mean aggregation variants to the unary negation fragment plus counting and ratio quantifiers. Through the logic-SQL correspondence, the results clarify how these networks relate to SQL queries. They also settle decidability of emptiness and subsumption problems for the networks.
Catalog record
| CREATOR | Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Schönherr, Arie Soeteman |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 251543 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22852