acceptodds
Under review as a conference paper at ICLR 2027

Arithmetic Growth Controls Recurrence Complexity in Uniform GNNs

Abstract

We study how the arithmetic gate basis inside a shared recurrent GNN cell affects the recurrence cost of graph-level color refinement. One-round graph colors form classes, while every fixed round refines classes. For a fixed rational ReLU-MLP (continuous piecewise-affine, CPWA), output-coordinate numerator and denominator bit lengths grow by only per recurrence. This gives an lower bound for fixed , even with a recurrent global sum. More generally, consider a fixed-dimensional cell and readout with a polynomial-growth envelope, polynomial-magnitude initialization, and inverse-polynomial separation between distinct class outputs. For fixed , such a model needs recurrences. We meet this bound with one fixed rational arithmetic cell over affine maps, scalar ReLU, and exact binary multiplication gates. Given and , it computes graph-level in recurrences using only neighbor sums. Its integer outputs are unit-separated, and its states have bits. For output radius and separation , every fixed-dimensional representation still satisfies . Thus adding exact multiplication reduces fixed- recurrence complexity to without removing this output cost. The same cell computes stable color refinement in recurrences, while locality gives an lower bound. Exact circuit certificates and independent color-refinement implementations check the construction. The results do not address trainability or fixed-word execution.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, recurrent neural networks, color refinement, Weisfeiler--Leman, learning theory, arithmetic circuits, recurrence complexity

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_FSENOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work researches how different arithmetic operations impact the complexity of GNNs for each recurrence during WL color refinement algorithm. The main takeaway is that the author shows that standard ReLU GNNs need more steps to compute WL coloring, but if we add exact multiplication, we can save a lot of steps. They propose a fixed recurrent GNN that achieves this improvement using efficient color encoding. However, on the practical side, their proposal requires extremely large numbers. To sum up, this paper proposes interesting design and highlights the tradeoff between recurrence complexity and numerical precisions in GNNs.

Critical strengths

∙\bullet This paper is theoretically sound and novel because it builds a clear separation in recurrence complexity between standard ReLU GNNs and multiplication GNNs for WL coloring, which give us new insights in how arithmetic operations impact the computational complexity of GNNs. This method and proposal can potentially help us to analyze models beside GNNs.

∙\bullet To the best of my knowledge, main theorems are correct, where I checked several proofs and I don't find problems.

Critical weaknesses

∙\bullet The assumption on numerical precision bothers me where the proposed method relies on exact multiplication of extremely large integers. In practice, we have finite precisions, and the assumption of very huge precision is impractical, which pose questions whether the theory can really describe the practice.

∙\bullet This paper measures the efficiency mainly via the number of recurrences, and the authors seem to treat the multiplication of very large integers as a constant-cost operation.

Questions for authors

Q1: Can the authors explain the practicality of their proposed multiplication GNN when precision are finite? For example, finite floating point precisions? Will their GNN achieve similar reductions in recurrence complexity under this setting?

Q2: If you consider the cost of multiplication of very large integers, what will the computational efficiency be?

2 comments
AuthorsOpenReview ↗

Response on finite precision and bit complexity

Thank you for checking several proofs and for highlighting the cost-model issue. With fixed floating-point precision, the exact guarantee does not survive: the construction relies on exact no-carry integer packing and exact equality of canonical codes. More generally, our output-precision lower bound rules out a fixed-dimensional, fixed-word, unit-separated exact encoding for all graph sizes.

If precision is allowed to grow, the recurrence count can remain logarithmic, but multiplication must then be charged according to the increasing operand length. Our theorem does not imply a reduction in bit operations, communication volume, memory, or wall-clock time; the explicit upper cell may use nO(k+1)n^{O(k+1)}-bit states. The revised abstract, introduction, and Section 5 make this distinction prominent and directly call the result an algebraic round-complexity separation. Bounded-precision approximate fingerprints are a separate and potentially practical research direction, but they relax the exact all-graph target analyzed here.

I sincerely appreciate the response from the authors; however, after considerations, I decide to maintain the score of 2.

Reviewer_cXHnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies how the arithmetic gate basis in a uniform recurrent GNN affects the recurrence complexity of graph-level color refinement (CR). It first establishes that the number of graph-level CR classes is 2Θ(n)2^{\Theta(n)} after one round and 2Θ(n2)2^{\Theta(n^2)} after two rounds. Combining this counting result with bounds on numerical growth, the paper shows that fixed-dimensional recurrent GNNs with fixed rational ReLU cells require Ω(n2/log⁡n)\Omega(n^2/\log n) recurrences to simulate any fixed k≥2k\geq 2 rounds of CR. With exact multiplication, the authors construct a fixed recurrent cell that completes the simulation in O((k+1)log⁡n)O((k+1)\log n) recurrences, achieving the optimal recurrence complexity of Θ(log⁡n)\Theta(\log n) for fixed k≥2k\geq 2. This improvement relies on high-precision exact arithmetic and does not directly imply a reduction in actual running time.

Critical strengths

The paper presents several clear theoretical contributions by studying how the arithmetic gate basis affects the recurrence complexity of graph-level color refinement in a shared recurrent GNN. For a fixed number of refinement rounds, the main recurrence bounds are tight or nearly tight, and these results should be of interest to researchers studying the theoretical foundations of GNNs. One technical aspect I find particularly interesting is the upper-bound construction using a single multiplication-augmented recurrent cell whose architecture and parameters are independent of both the graph size n and the target number of refinement rounds k.

Critical weaknesses

My main concern is that the motivation and positioning of the contributions could be explained more clearly. In particular, I would appreciate a more intuitive explanation of why recurrence count is an informative computational resource under the exact-arithmetic model considered in this paper. Although the paper discusses related work, I found it difficult to extract a concise comparison showing which results improve on prior work and under what assumptions. The introduction presents many results and technical qualifications in quick succession, making the central message difficult to follow for readers who are not specialists in this area. A clearer high-level explanation of the problem's significance, followed by a more focused comparison with the closest prior work, would improve the presentation.

Questions for authors

As stated above, please clarify more about the motivation of the problem and the improvement over any existing related or prior works. Another question that I would like to see is: in Theorem 5, the first round of construction is O(n); how can we avoid the possible cost of Θ(n2)\Theta(n^2) for appending each unary-degree key and its multiplicity to the output?

2 comments
AuthorsOpenReview ↗

Response on positioning and the first-round construction

Thank you for both questions. We have reorganized the introduction around the following high-level message: the target invariant contains Θ(n2)\Theta(n^2) bits of graph-level information; a fixed CPWA cell exposes only O(log⁡n)O(\log n) new exact bits per recurrence; exact multiplication accelerates state-magnitude growth but cannot remove the output-precision cost. Compared with the closest uniform result of Rosenbluth and Grohe, which proves sufficiency with a generic polynomial-overhead recurrent ReLU construction and leaves lower complexity and lower bounds open, we provide the first nearly quadratic CPWA recurrence lower bound for fixed k≥2k\geq2, the graph-level CR2 entropy theorem that drives it, a robust arbitrary-real packing version, and a jointly (n,k)(n,k)-uniform multiplication-augmented upper cell. The paper does not claim that multiplication is a new neural operation or that it increases 1-WL distinguishing power.

You are also correct that literally appending every unary degree key u(d)u(d) together with its multiplicity can cost Θ(n2)\Theta(n^2). That copying is unnecessary for CR1\mathrm{CR}_1, and the current specialization should state the simpler construction explicitly. The controller enumerates d=0,…,n−1d=0,\ldots,n-1 in fixed order. For each dd, a global sum obtains

md=∣{v:deg⁡(v)=d}∣,m_d=|\{v:\deg(v)=d\}|,

and the shared unary field routine appends only u(md)u(m_d) and its delimiter. The degree dd is implicit in the field position, so u(m0)⋯u(mn−1)u(m_0)\cdots u(m_{n-1}) is an injective encoding of the degree histogram. There are O(n)O(n) fixed-order probes, and the total number of emitted unary symbols is

∑d=0n−1md+n=2n,\sum_{d=0}^{n-1}m_d+n=2n,

up to constant latency per field. Hence this first-round specialization costs O(n)O(n) recurrences and does not traverse or copy the unary degree keys. An optional u(n)u(n) prefix also costs O(n)O(n) and distinguishes graph orders, although the theorem's refinement contract compares same-order graphs. We have replaced the misleading trie/key-copy sentence in the proof of Theorem 5 and Appendix C with this direct histogram construction. The fixed-k≥2k\geq2 construction and its Ok(n2)O_k(n^2) accounting are unchanged.

Thank you for your reply. My concerns are partially resolved and I believe a better presentation is still needed in the revised version. Given my current positive evaluation, I'd like to maintain my score.

Reviewer_mm5QOpenReview ↗
Rating
2(−1)
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the recurrence complexity of uniform GNNs for graph-level color refinement. The authors theoretically show that adding exact multiplication gates can significantly reduce the required number of recurrences compared to conventional ReLU-MLP cells. The paper further provides an explicit arithmetic cell construction and computational checks to support the theoretical results.

Critical strengths

[S1] The theoretical contribution is interesting. The paper provides a clear distinction between conventional ReLU-based GNNs and multiplication-augmented GNNs in terms of recurrence complexity.

[S2] The authors provide detailed mathematical analyses and explicit constructions, along with computational verification efforts.

Critical weaknesses

[W1] The practical implications of the theoretical results are somewhat unclear.

While the proposed approach significantly reduces recurrence complexity, it relies on exact arithmetic with potentially very large intermediate representations. The authors acknowledge this limitation, but it remains unclear whether reducing the number of recurrences can provide actual computational benefits in realistic GNN implementations.

I understand that this paper primarily focuses on theoretical complexity rather than system performance. Nevertheless, a more detailed discussion of the practical implications would help readers better understand the significance of the results.

Questions for authors

Thank you for submitting this paper.

My main question concerns the practical implications of the proposed approach.

[Q1] Could the authors further explain how the reduced recurrence complexity might translate into actual computational efficiency when accounting for arithmetic precision and multiplication costs? In particular, under what assumptions could the proposed approach offer practical benefits over conventional GNN implementations?

I understand that the paper is primarily theoretical, and I do not expect additional system-level experiments. However, I believe such a discussion would strengthen the paper.

As my expertise is primarily in computer systems, my assessment focuses on the computational implications and presentation rather than independently verifying the detailed mathematical proofs.

4 comments
AuthorsOpenReview ↗

Response on computational implications

We agree that fewer recurrences do not automatically imply lower computational cost. The only setting in which the construction could offer a round-level benefit is one where synchronization/communication latency dominates and exact large-integer arithmetic and state bandwidth are treated as available local resources. We do not argue that this is a realistic model for current GNN hardware.

Under ordinary bit-cost accounting, a multiplication of BB-bit operands is not unit cost, and our states can have nO(k+1)n^{O(k+1)} bits. Consequently, the paper establishes a recurrence separation, not an end-to-end efficiency improvement. Its computational implication is primarily diagnostic: any use of recurrence count as a complexity measure must specify the arithmetic basis and precision budget. The revised definition of recurrence and Section 5 now make this distinction explicit, together with the alternative contracts—bounded graph size, growing width, randomized fingerprints, or approximate outputs—under which practical implementations might instead be investigated.

Reviewer_mm5QOpenReview ↗

Proposal for a promising direction as a computer system reviewer

Thank you for the detailed clarification. After reviewing the paper, and since my expertise is not in this domain, I spent some time considering whether I could offer helpful comments as a reviewer in the computer systems domain. The following are my thoughts after submitting the review.

Regarding the rebuttal comments, I agree that the proposed recurrence separation does not directly establish an end-to-end efficiency improvement.

I would like to suggest one additional systems perspective that might help strengthen the practical interpretation in Section 5.

Prior work on distributed GNN training, such as PipeGCN (Wan et al., ICLR 2022) and GraNNDis (Song et al., PACT 2024), highlights the substantial overhead of repeated inter-partition communication and synchronization, particularly across multiple servers.

Although these systems are not directly comparable to the exact color-refinement computation studied here, they motivate considering a simple latency-bandwidth cost model.

For a baseline exact CPWA implementation (B) and a multiplication-augmented implementation (M), suppose distributed execution time is approximated as:

\quad j\in\\{B,M\\}.$$ Here, $R_j$ denotes the number of communication-active synchronization rounds, $\alpha$ the effective per-round latency, $V_j$ the total transmitted data volume, $\beta$ the effective network bandwidth, and $C_j$ the local computation cost, including arbitrary-precision arithmetic. The multiplication-augmented approach could offer an end-to-end benefit when: $$(R_B-R_M)\alpha > \frac{V_M-V_B}{\beta}+(C_M-C_B).$$ This condition captures an interesting possibility: reducing message-passing rounds may decrease not only synchronization overhead but also total communication volume, provided the reduction in exchanges outweighs the growth in transmitted representations. I also noticed that the arithmetic construction communicates selected aggregated coordinates rather than necessarily the entire 22-dimensional state, and that its preparation phases consist of local arithmetic operations. It may therefore be useful to distinguish total recurrences from communication-active recurrences when discussing a hypothetical distributed implementation. Of course, the potentially enormous exact-integer representations may dominate both communication and computation costs, so this model does not establish practical speedups on current hardware. Nevertheless, I think presenting such a conditional break-even regime could give the theoretical result a useful systems interpretation. It would help clarify when recurrence reduction might translate into actual execution benefits and when precision and bandwidth costs would dominate. I am not requesting additional experiments or changes to the main theoretical contribution. This is simply a suggestion that might make the practical significance of the recurrence-complexity separation more accessible to systems researchers. References: - Wan et al., "PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication," ICLR 2022. https://openreview.net/forum?id=kSwqMH0zn1F - Song et al., "GraNNDis: Fast Distributed Graph Neural Network Training Framework for Multi-Server Clusters," PACT 2024. https://doi.org/10.1145/3656019.3676892 I hope this suggestion may help strengthen the paper's system-side benefit.

Based on the current rebuttal/revision, I'll change my score to 2, because my concern related to system benefits is not addressed.

Thank you for the concrete latency-bandwidth formulation. We agree that our previous response stated the limitation but did not operationalize your suggestion. We have now revised Section 5 and Appendix E.4 to do so.

Let a=⌈log⁡2(2n)⌉a=\lceil\log_2(2n)\rceil. Inspecting the six phases of the explicit cell shows that only one EvalInit recurrence and the aa Eval recurrences in each of the k+1k+1 packing blocks use a neighbor aggregate. Thus a phase-scheduled implementation has RMcomm=(k+1)(a+1)R_M^{\mathrm{comm}}=(k+1)(a+1) communication-active recurrences, excluding the final graph reduction. If a static graph's degrees are available from metadata or cached after one exchange, this becomes (k+1)a+1(k+1)a+1. The Prep, exit, and Commit phases are local.

Following your suggestion, for an implementation X∈{B,M}X\in\{B,M\} we now write TX≈rXτ+VX/β+CX+GX,T_X\approx r_X\tau+V_X/\beta+C_X+G_X, where rXr_X is the number of communication-active synchronized recurrences, VXV_X is critical-path transmitted volume, CXC_X is local arithmetic time, and GXG_X is graph-level collective time. When rB>rMr_B>r_M, the multiplication implementation can be faster only if

\frac{(V_M-V_B)/\beta+(C_M-C_B)+(G_M-G_B)} {r_B-r_M}.$$ Appendix E.4 also makes the precision term explicit. During refinement block $j$, the transmitted Eval value satisfies $$u_v<K^{h+1},\qquad \operatorname{bits}(u_v) \le (h+1)(\log_2(2n)+hL_j)+O(1),$$ together with the displayed recurrence and closed upper envelope for $L_j$. This identifies the conditional regime you described: high synchronization latency and bandwidth, a small inter-partition cut, and moderate observed integer lengths favor the multiplication construction; low-latency execution, large cuts, or rapidly growing exact integers do not. We cite PipeGCN and GraNNDis only as motivation for separating latency from communication volume; their distributed training workloads are not evidence for the exact color-refinement construction. We continue to make no empirical speedup claim. The quantities $r_B,V_X,C_X,G_X,\tau,\beta$ must be measured for a specified pair of implementations before an actual break-even point can be asserted. We hope this directly addresses the systems interpretation you proposed.
Reviewer_C2jWOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers a quantitative version of the connection between message-passing GNNs and color refinement: once a recurrent GNN is required to use one fixed shared update rule for graphs of all sizes, how long does it take before it can encode the information obtained after kk refinement rounds?

The paper provides a lower bound: a fixed ReLU/CPWA recurrent cell can only create a limited amount of distinguishable exact information per recurrence, and therefore needs nearly quadratically many recurrences for any fixed refinement depth beyond one. A related packing argument extends this conclusion to arbitrary real parameters under an inverse-polynomial output-separation condition.

If exact multiplication is added, the cell can repeatedly square and combine quantities so as to encode the whole multiset of neighbour colours much more quickly. This yields a single constant-dimensional recurrent cell that computes any requested fixed number of color-refinement rounds in logarithmically many recurrences. The construction is explicit, including the finite control logic and an integer encoding of the final graph invariant.

Critical strengths
  1. The paper considers an interesting quantitative question beyond the usual statement that GNNs are as expressive as 1-WL: when one fixed recurrent update rule must work uniformly across graph sizes, how many recurrences are actually needed to realize a given amount of color refinement? This is a natural refinement of existing expressiveness results.

  2. The CR$_2$ entropy lower bound and the resulting arithmetic separation are conceptually strong. In particular, the sharp jump in the number of possible graph-level invariants between one and two refinement rounds gives a clear explanation for why the standard ReLU/CPWA model needs many recurrences, while exact multiplication can reduce their number dramatically.

Critical weaknesses
  1. The upper bound is a unit-cost, unbounded-precision result, rather than an efficient or practical GNN computation. Exact multiplication of increasingly enormous integers--whose bit lengths can be nO(k+1)n^{O(k+1)}--is charged as one cell operation. Thus, the separation primarily shows that exact multiplication enables very rapid growth of representable information when bit complexity is ignored. The paper acknowledges this limitation, but it considerably narrows the significance of the result for GNNs as used in machine learning.
Questions for authors
  1. Could the authors clarify the practical implications of the proposed arithmetic separation? In particular, is there a bounded-precision or numerically stable variant of the multiplication-based construction that retains a meaningful recurrence advantage, or should the result be understood purely as a separation in an exact unbounded-arithmetic model?
2 comments
AuthorsOpenReview ↗

Response on exact arithmetic and practical implications

Thank you for identifying the central limitation precisely. The result should be understood as a separation in an exact, unbounded-arithmetic model, not as a claim about a deployable GNN.

Under the same fixed-dimensional, exact-output contract, there is no uniform fixed-word version that retains the theorem: the paper proves that a unit-separated output for fixed k≥2k\geq2 requires an Ω(n2)\Omega(n^2)-bit coordinate on some nn-vertex input. Therefore bounded precision independent of nn cannot represent all required classes. Allowing precision to grow with nn preserves the recurrence statement, but large-integer multiplication is then nonconstant-cost and the paper gives no bit-time advantage. Floating-point substitution also does not preserve the proof because rounding can introduce carries or collisions.

A numerically stable approximate or randomized variant is an interesting open direction, but it would necessarily relax at least one of exact refinement, fixed dimension, all-graph worst-case correctness, or the prescribed output separation. We now state this negative boundary directly in the abstract, introduction, and Section 5.

Thank you for the response and the proposed revision. The authors have clarified the computational model and its limitations, which addresses my request for clarification. My main reservation, which appears to be shared by several other reviewers, concerns the significance of the resulting separation. The unbounded-precision arithmetic setting is interesting as an academic exercise, but I remain unconvinced that the result is sufficiently compelling for ICLR. I therefore maintain my original score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Author response and summary of revisions

We thank all reviewers for recognizing the soundness and novelty of the main theoretical results. We also appreciate the consistent criticism concerning practicality and presentation. We agree that our multiplication construction should not be interpreted as a practical GNN acceleration result.

The intended contribution is an exact round/recurrence-complexity separation under an explicitly stated arithmetic model. For fixed k≥2k\geq 2, the target graph invariant has 2Θ(n2)2^{\Theta(n^2)} classes. A fixed CPWA/ReLU cell grows the bit length of exact rational states by only O(log⁡n)O(\log n) per recurrence, which yields the Ω(n2/log⁡n)\Omega(n^2/\log n) lower bound. Exact multiplication can instead increase bit length exponentially with the number of recurrences, giving the Θ(log⁡n)\Theta(\log n) recurrence construction. This reduces sequential shared-cell rounds, but it moves cost into arithmetic precision rather than removing it.

Indeed, our output-precision corollary shows that this cost is unavoidable under the paper's contract: any fixed-dimensional representation that separates all fixed-kk color-refinement classes satisfies

log⁡(M(n)+1)+log⁡(1/δ(n))=Ω(n2).\log(M(n)+1)+\log(1/\delta(n))=\Omega(n^2).

Thus a fixed-dimensional, fixed-word implementation cannot preserve exact refinement with unit or inverse-polynomial separation for all graph sizes. Our explicit multiplication construction uses exact integers with nO(k+1)n^{O(k+1)} bit length. If multiplication is charged by operand bit length, we obtain no bit-complexity or wall-clock speedup theorem. With ordinary floating point, rounding can destroy the no-carry encoding, so we do not claim numerical stability or the same guarantee. Approximate/randomized fingerprints, growing width, a fixed maximum graph size, or a vanishing output margin may yield different practical tradeoffs, but they change the problem contract and remain outside our result.

Why study recurrence count, then? It measures sequential applications and synchronization/communication rounds of one shared update rule. Our result shows that this resource is meaningful only together with the gate basis and precision contract: weight sharing alone does not control the rate at which exact information can grow. The broader contributions are therefore (i) the 2Θ(n)2^{\Theta(n)} to 2Θ(n2)2^{\Theta(n^2)} graph-level entropy transition from one to two color-refinement rounds, (ii) the resulting CPWA and robust-real lower bounds, (iii) the architecture-independent output-precision floor, and (iv) an explicit fixed-cell construction showing that a stronger arithmetic basis changes round complexity without eliminating precision cost.

The revised manuscript now states this interpretation in the abstract and before the construction, defines exactly what one recurrence charges, gives a shorter closest-prior comparison, and makes the “no practical speedup” boundary prominent in Section 5. It also corrects the first-round specialization in the proof of Theorem 5 and Appendix C as explained in our reply to Reviewer cXHn below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.