Expressive Power of Deep Homomorphism Networks over Relational Databases

ArXi:2605.22852v1 Announce Type: cross The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of powerful graph learning architectures. We advocate Deep Homomorphism Networks (DHNs) as a model particularly well-suited for learning over relational databases, due to their close connection to important fragments of SQL such as conjunctive queries. We study the precise expressive power of DHNs by relating them to various natural fragments and extensions of first-order logic (FO.