Showing 2026Show all
3 papers · 1 filter
cs.LO2026
Two Variables and Two-Dimensional Structures
Bartosz Jan Bednarczyk, Daumantas Kojelis, Krzysztof Szymański
We study the two-variable fragment FO^2 of first-order logic over two-dimensional structures. Formulae may employ two linear orders <=_1, <=_2, their successor relations S_1, S_2,…
cs.LG2026
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…
cs.LG2026
Towards Understanding the Expressive Power of GNNs with Global Readout
Maurice Funk, Daumantas Kojelis
We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible b…