- 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
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.
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=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.