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

CREATORBalder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Schönherr, Arie Soeteman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE251543
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.22852

Browse the full library · About the Tower of Babel