acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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. 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. As the activation function, it may use logistic sigmoid, hyperbolic tangent, or related functions. It is uniform across all graph sizes. 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. We also conduct experiments showing that the constructed GNNs indeed match the 1-WL test.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Expressive Power, Uniform Expressive Power, Schanuel's Conjecture, Sigmoid Activation, Hyperbolic Tangent Activation

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_tkaMOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies whether constant-depth GNNs with rational weights can match the expressive power of the 1-WL test uniformly over graphs of arbitrary size. The authors answer this question positively for several activation functions, including sigmoid and tanh under the assumption that Schanuel's conjecture hold, which is a conjecture from number theory. The construction works with scalar embeddings and simple integer weights. They also establish a partial converse, connecting the ability to match 1-WL to algebraic independence of certain exponential expressions, and provide numerical experiments supporting their theoretical findings.

Critical strengths
  • The paper addresses a natural question left open by previous results establishing 1-WL expressivity for almost all real weights.
  • The connection to Schanuel's conjecture is mathematically interesting and the explicit construction using simple integer weights is elegant.
Critical weaknesses
  • My main concern is the significance of restricting the weights to rational numbers. Although the weights are finitely representable, the computations still require exact real arithmetic. In particular, distinct embeddings may become arbitrarily close, so the construction does not necessarily translate into a finite-precision implementation. It is unclear to me what the result tells us about the expressivity of practically realizable GNNs.
  • The converse requires a modified architecture with special virtual nodes and only applies to a restricted class of activation functions. Therefore, the claimed bidirectional connection is somewhat weaker than the presentation might suggest.
Questions for authors
  • How should the rational-weight result be interpreted from a computational perspective, given that exact real arithmetic is still required?
2 comments

We thank the reviewer for raising questions regarding theory and practice.

Q: How should the rational-weight result be interpreted from a computational perspective, given that exact real arithmetic is still required?

A: The reviewer is correct that real arithmetic is still required. In this sense, they are also correct that our theoretical results do not immediately apply in practice. We do not wish to claim otherwise. However, our paper continues an established line of research regarding the expressive power of GNNs and their exact relationship to the 1-dimensional Weisfeiler-Leman test. We believe that the addressed questions are very natural, and that our results and the established connection to Schanuel's conjecture add significant insight.

We further believe that our experiments provide strong empirical evidence that our results are relevant also in practice. The experimental findings are remarkably consistent with our theoretical results, showing that also in practice a large number of rational-weight GNNs are able to match the 1-WL test (for an appropriate number of iterations). Even the single parameter choice C=AC=A that was problematic in our theoretical analysis is confirmed in the experiments, exhibiting exceptionally weak performance.

It would be great to link the theoretical and practical analysis in an even closer way by providing a bound on the precision required to meet 1-WL's expressivity, depending on graph size and input feature precision. This, however, is an entirely non-trivial question that at this point we do not know how to answer. Nonetheless we believe that our research paves the way to studying such questions in future work. We will add a discussion to our conclusions section.

I thank the authors for the response. Having revisited the experiments and read the other reviews (especially regarding the possible application of transcendence theory to other architectures), I am convinced that this is a solid contribution and I will raise my score to 3.

Reviewer_KpB4OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies whether fixed-depth, rational-weight message-passing GNNs can uniformly reproduce a fixed number of color-refinement rounds. Assuming Schanuel’s conjecture, it constructs scalar-state GNNs with several exponential-based activations, including sigmoid and tanh, whose node and graph distinctions agree exactly with L-round 1-WL after L message-passing layers and an initialization network. The construction works across graph sizes and permits the same integer self-weight 1 and aggregation-weight 2 in every layer. A partial converse for exp, sinh, and cosh derives algebraic independence of certain computed exponentials from graph-level expressivity in an augmented model with specially defined virtual nodes. Synthetic experiments examine numerical distinguishability at different floating-point precisions.

Critical strengths

The explicit rational/integer construction is the main strength. Almost-everywhere results do not establish the existence of a successful rational parameter choice, let alone a single explicit integer choice shared across layers. Theorem 5 addresses this distinction and also provides a rational-weight initialization for non-negative rational feature vectors. The shared-weight result directly addresses a question left open. This gives a clear advance over the existing existence results.

The converse turns a polynomial relation into two graphs with equal neural readouts but distinct WL color multisets. The extension to sinh and cosh in Appendix C is nontrivial. It gives algebraic independence a role beyond the sufficient invariant in the forward construction.

Critical weaknesses

The gap between exact distinguishability and finite-precision computation remains. The construction does not provide quantitative separation margins or precision requirements as graph size, degree, or depth increases. Section 5 and Appendix D usefully investigate precision and overflow, but the evidence concerns within-graph node partitions on 500 sparse random graphs with 20–100 vertices, using a simplified one-hot initializer. It does not establish robust graph-level separation or the numerical behavior of the general rational-feature initializer. These experiments therefore leave the practical reach of the exact-arithmetic result unclear.

The forward and converse results concern different settings. The converse requires a graph-level guarantee on graphs augmented with specially updated virtual nodes, a scalar final embedding, and exp/sinh/cosh rather than sigmoid/tanh. Consequently, it does not establish that Schanuel’s conjecture is necessary for the ordinary-GNN result in Theorem 5. The paper acknowledges these restrictions; the bidirectional connection remains partial.

Questions for authors

Is the expressivity premise of Theorem 11 known to be realizable, under Schanuel’s conjecture, in the stated virtual-node model? I'd like to understand whether the forward construction extends to this model. This would clarify the relationship between the two results within the stated restrictions.

Appendix D specifies binary equality and software-emulated binary128. How is aggregation order controlled so that rounding does not spuriously distinguish equal WL colors, and how does the experimental one-hot initializer relate to the general initializer in Theorem 5?

1 comment

We thank the reviewer for highlighting these important questions.

Q1: Is the expressivity premise of Theorem 11 known to be realizable, under Schanuel’s conjecture, in the stated virtual-node model?

A1: Yes, the premise of Theorem 11 can be realised under Schanuel's conjecture as follows. Initialise virtual nodes via λ(0)\lambda^{(0)} to, say, σ(0.1)\sigma(0.1) whilst leaving λ(0)(v)=σ((21,…,2N)×σ(λ(v)+1N))\lambda^{(0)}(v) = \sigma((2^1, \dots, 2^N) \times \sigma(\lambda(v) + 1_N)) for ordinary vertices vv. This allows us to distinguish virtual vertices (having embedding σ(0.1)\sigma(0.1)) from non-virtual ones at the very beginning. One can then have the embeddings λ(i+1)(v)=σ(λ(i)(v)+2∑u∈N(v)λ(i)(u))\lambda^{(i+1)}(v) = \sigma(\lambda^{(i)}(v) + 2 \sum_{u \in N(v)} \lambda^{(i)}(u)) for regular vertices vv and λ(i+1)(v)=σ(2∑u∈N(v)λ(i)(u)+0.1)\lambda^{(i+1)}(v) = \sigma(2 \sum_{u \in N(v)} \lambda^{(i)}(u) + 0.1) for virtual nodes vv. Note that the bias vector 0.10.1 in the virtual node update allows us to distinguish between virtual and ordinary vertices. One may proceed as in Proposition 6 and show that the resulting GNN matches the 1-WL test over graphs with virtual vertices. We thank the reviewer for bringing this gap to our attention. We will add a formal argument in (the appendix of) the final version.

Q2: Appendix D specifies binary equality and software-emulated binary128. How is aggregation order controlled so that rounding does not spuriously distinguish equal WL colors, and how does the experimental one-hot initializer relate to the general initializer in Theorem 5?

Regarding aggregation order, the submitted implementation adds aggregated values in vertex order. We acknowledge that this makes the implementation susceptible to pathologies of floating point arithmetic. We have since changed addition in aggregation to be performed from the smallest values to the largest. Below we provide a table of how the success ratio (between 0 and 1, smallest step 0.002, ran on the same exact graphs) in figure 1 changes (sum_in_value_order_results - sum_in_vertex_order_results). Note that the differences are rather minor, with the case of ReLU activation beging most affected, and in most cases performing even worse than before.

C=0.01C = 0.01

Activation/A0.010.020.030.040.050.060.070.080.090.10
sigmoid0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
tanh-0.0020.0000.0000.0000.0000.000+0.0020.0000.0000.000
sinh-0.004+0.002+0.002+0.0020.000+0.0020.0000.0000.0000.000
cosh0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
exp0.0000.0000.0000.0000.0000.0000.0000.000+0.0020.000
ReLU-0.002-0.012-0.010-0.002+0.006+0.004-0.012-0.0080.000-0.004

C=0.1C = 0.1

Activation/A0.10.20.30.40.50.60.70.80.91.0
sigmoid0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
tanh0.0000.000+0.0020.0000.0000.0000.0000.0000.0000.000
sinh-0.0020.0000.0000.0000.0000.0000.0000.0000.0000.000
cosh0.0000.000+0.0020.0000.0000.0000.0000.0000.0000.000
exp+0.002+0.0020.0000.0000.0000.0000.0000.0000.0000.000
ReLU0.000-0.006+0.014+0.010-0.016-0.006-0.014+0.008+0.004-0.010

C=1C = 1

Activation/A12345678910
sigmoid0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
tanh0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
sinh+0.0020.0000.0000.0000.0000.0000.0000.0000.0000.000
cosh-0.0020.0000.0000.0000.0000.0000.0000.0000.0000.000
exp0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000
ReLU0.0000.0000.0000.0000.0000.0000.0000.0000.0000.000

We will upload the new code and update all figures accordingly.

Regarding the initialisation, for the experiments we found that the smaller values 2−1,...,2−42^{-1}, ..., 2^{-4} work better for most activation functions. We believe this is because smaller initialisations delay overflow (sinh, cosh, exp) and also delay values becoming arbitrarily close to 1 (sigmoid, tanh). On the theoretical side one can use the same techinique as in Theorem 5 to obatain results regarding this initialisation. We will explain this discrepancy in the final version.

Reviewer_eHbNOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies when GNNs with rational or integer weights can attain the maximal expressive power of real-weight message-passing GNNs, namely that of 1-WL. They show that this question is connected to Schanuel's conjecture in number theory in both directions. In the forward direction, assuming Schanuel's conjecture, they construct GNNs with scalar internal embeddings whose LL message-passing layers, sharing the same small integer weights, match LL rounds of 1-WL uniformly over graphs of arbitrary size with nonnegative rational input features, after an additional initialization network. In the reverse direction, maximal expressivity in a modified GNN model with virtual nodes and additional architectural restrictions implies Schanuel's conjecture restricted to certain numbers arising in the GNN computation.

Critical strengths
  • The connection between GNN expressivity and Schanuel's conjecture is conceptually interesting and, as far as the reviewer can check, novel. The construction is simple and makes sense, and the forward theorem is uniform over graph size. The problem that the authors are trying to tackle is also well motivated by realistic computation, where arbitrary real-valued parameters cannot be represented exactly. In particular, previous expressivity guarantees for almost every choice of real weights do not establish the existence of suitable rational weights.
  • The use of transcendence theory in this construction seems potentially applicable more broadly, for example to Deep Sets (multiset injectivity), transformers, or higher-order GNNs.
Critical weaknesses
  • The remaining gap to realistic floating-point computation is finite precision. While the paper allows rational inputs and integer weights, activations still produce real-valued outputs, and the computations themselves still use exact arithmetic. While we do not expect fixed-precision scalar embeddings to distinguish infinitely many WL-distinguishable graph classes, it would be more complete to analyze how much precision is needed as a function of graph size and other complexity parameters, including input-feature complexity. Such a scaling analysis, if tight, would provide much more realistic conclusions.
  • Another limitation is the set of restrictions in the reverse direction, including the activation restrictions, the virtual-node model, and the restriction of the resulting Schanuel statement to numbers generated by the network. These are acknowledged by the authors.
  • The paper is also written very densely, and the main paper would benefit from more high-level discussion and intuition about which assumptions are necessary.
Questions for authors
  • Can the authors provide a separation bound between embeddings of WL-distinguishable nodes, or characterize the required numerical precision in terms of graph size, depth, and input-feature complexity, even for a restricted setting?
  • Can the authors provide some intuition about why the extra restrictions are needed for the converse proof? Which of them do the authors believe can be shown to be necessary?
  • Are there nontrivial graph classes or depth regimes for which integer-weight GNNs can match the corresponding number of 1-WL rounds without assuming Schanuel's conjecture?
  • Is the assumption of nonnegative input node features (line 188) necessary?
2 comments

We thank the reviewer for the insightful questions.

Q1: Can the authors provide a separation bound between embeddings of WL-distinguishable nodes, or characterize the required numerical precision in terms of graph size, depth, and input-feature complexity, even for a restricted setting?

A1: These are all excellent, but also very difficult questions. In particular, it would be great to bound the precision in terms of the graph size (and the precision of the input features). We do not see that such a bound can be extracted from the current proofs. Different analysis seems to be needed which we leave as a challenging open problem for the time being.

Q2: Can the authors provide some intuition about why the extra restrictions are needed for the converse proof? Which of them do the authors believe can be shown to be necessary?

A2: We make three assumptions in the converse: 1) the GNN produces a scalar final embedding, 2) graphs are allowed to feature virtual nodes, and 3) the activation function is exp, sinh or cosh.

Regarding 1) we believe that our proof generalises to non-scalar final embeddings. Theorem 11 would now state that there must be a row rr of AL′A'_L for which each entry {er×λ(L−1)(v)∣v∈V}\lbrace e^{r \times \lambda^{(L-1)}(v)} \mid v \in V \rbrace is algebraically independent over Q\mathbb{Q}. The idea is to choose the polynomial P in the proof of Theorem 11 in a more clever way (namely, we take the product of polynomials that witness the algebraic dependence of every row). We will thus make an attempt to eliminate this assumption in the final version of our paper.

Regarding 2) we currently do not have a strategy which allows us to eliminate virtual nodes. We suspect that this assumption is the hardest one to remove. As for intuition, virtual nodes do not carry a previous state. This gives us freedom to manipulate their LL-th embedding directly by changing their neighbourhood. For ordinary nodes it is hard to account for the contribution of the previous state (which changes as we change neighbourhoods).

Regarding 3) we were not able to generalise our results to Schanuel-ready functions or even to sigmoid and tanh. The challenge is to deal with the denominators they introduce to the polynomial P.

Q3: Are there nontrivial graph classes or depth regimes for which integer-weight GNNs can match the corresponding number of 1-WL rounds without assuming Schanuel's conjecture?

A3: One such class is identified in Sammy Khalife, Amitabh Basu: On the Power of Graph Neural Networks and the Role of the Activation Function. SIAM J. Appl. Algebra Geom. 10(2): 350-365 (2026).

It consists of all rooted trees of depth two and the activation functions considered are exp, sigmoid, cosh, sinh, tanh (but not ReLU). We will mention this in the final version. We are not aware of any other such classes.

Q4: Is the assumption of nonnegative input node features (line 188) necessary?

A4: Reconsidering the assumption, it might not be strictly necessary. Consider e.g. sigmoid activation σ\sigma. It might be possible to first convert unrestricted rational numbers qq into positive reals using σ(σ(q)+1)\sigma(\sigma(q)+1), which can be implemented using an FNN. We then have to check carefully, however, that our induction still goes through. Something similar might also work for the more general class of Schanuel-ready activation functions considered in our paper, but this is more challenging. We will look into it carefully for the final version.

I thank the authors for their response to my question. I don't have any additional questions and I am keeping the score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.