Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture
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.
ProofPaper ↗
Key points
- We ask whether a constant-depth GNN can match the expressive power of 1-WL while using only rational weights.
- We prove that this is the case when Schanuel's conjecture, a famous open problem from transcendental number theory, is taken to be true.
- Our GNN construction works even with integer weights, and more generally with a broad range of rational weights.
- We also prove a partial converse: if a GNN with exponentiation, hyperbolic sine or hyperbolic cosine as activation matches the expressive power of the 1-WL test in a slightly more expressive setting where graphs may contain certain auxiliary vertices, then this implies Schanuel's conjecture restricted to the numbers that arise in computations of the GNN.
Sources (1)
- [1]Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's ConjecturearXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 12, 03:44 PM
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 constant-depth GNN can match the expressive power of 1-WL while using only rational weights.
Extractive summary: sentences quoted from the sources.
Before this
- Oct 12, 2026FEM-Validated Real-Time Modelling of Soft Tactile Deformation
- Oct 12, 2026CryptoFlowBench: Benchmarking Multi-Hop Reasoning on Blockchains for Cryptocurrency Fund Tracing
- Oct 11, 2026A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks
- Oct 10, 2026DeKoR: Decomposed Knowledge Routing for Efficient GNN--LLM Fusion