Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture

Daumantas Kojelis, Carsten Lutz

A landmark result states that the expressive power of graph neural networks (GNNs) is bounded from above by the 1-dimensional Weisfeiler-Leman (1-WL) test. We ask whether a constan…