- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes Tiny Recursive Graph Neural Networks (TRGNNs), which repeatedly apply a small, shared message-passing block while updating a persistent prediction. The previous prediction is fed back into both the message-passing block and the prediction head. This allows the number of iterations to increase without increasing the parameter count and provides a prediction at each iteration. The paper motivates the approach through the different propagation depths needed by different graph topologies. It provides conditional convergence results and evaluates the method on a synthetic shortest-path task, Reddit graph classification, DrugOOD, and Peptidesstruct.
Critical strengths
The architecture is simple and offers a useful combination of parameter sharing and prediction refinement. In particular, retaining the previous prediction gives the model a direct mechanism to preserve an answer when further message passing is no longer helpful. The reported parameter savings are substantial on some datasets. This makes the approach interesting for settings where model size and memory are important, even though more iterations do not necessarily mean faster inference.
The paper provides several complementary experiments to understand the method. The controlled shortest-path experiment studies how convergence changes with graph topology, while the prediction-feedback ablation examines the contribution of the persistent output state. Appendix G also reports variability across folds or seeds and demonstrates an accuracy-computation tradeoff using early stopping. These results provide useful empirical evidence that the proposed recurrence can support progressively improving predictions.
Critical weaknesses
The theoretical results do not establish topology-adaptivity as defined in Definition 4.1. Proposition 4.2 gives an upper bound on effective depth under an assumed contraction. Proposition E.1 gives a topology-dependent upper bound for a restricted component of the dynamics. Ordering these upper bounds does not imply an ordering of the actual effective depths, particularly since the initial distance to the fixed point also depends on the graph. The statement in Remark E.1 that effective depth is ordered as in Definition 4.1 therefore needs additional justification. Neither convergence nor the ability to preserve a prediction guarantees improving task accuracy. There is also an architectural inconsistency: for graph-level tasks, the pooled prediction is broadcast back to every node. This introduces global communication, so the strictly local receptive-field claim in Section 3.1 does not generally hold. These issues matter because topology-adaptivity and preserving locality are central to the paper’s explanation of its contribution.
The experiments do not sufficiently establish the advantage over well-tuned alternatives. Appendix C.2 explicitly states that DrugOOD hyperparameters and checkpoints are selected using OOD validation AUROC and that the same metric is reported. These results therefore need confirmation on the untouched OOD test sets. The controlled experiment compares a 128-iteration TRGNN with only four- and five-layer GINs, without a matched recurrent baseline to isolate the effect of prediction feedback. On Peptides-struct, Table 1 omits the tuned standard GNN baselines reported by Tönshoff et al., which already achieve approximately the reported TRGNN performance. The related-work discussion also omits Errica et al.’s Adaptive Message Passing framework. Finally, Appendix D.3 attributes PEARL’s runtime to an eigendecomposition at every forward pass, whereas PEARL generates its positional encodings through message passing. This factual error needs correction, and the timing setup needs clarification.
The “elasticity window” is not sufficiently justified as a necessary range of useful depths. Section 2.1 sets the minimum depth to the graph diameter, but this is a worst-case communication requirement, not a requirement for every prediction task. A graph-level property may be predictable from local information followed by pooling. Likewise, the time at which a bound on Dirichlet energy decreases by a factor of 1/e is not established as the depth beyond which task-relevant information is lost. This also depends on the features, learned transformations, and prediction target. Consequently, non-overlapping windows do not by themselves establish that no fixed-depth model can perform well across the dataset. This matters because the paper uses this argument to present adaptive depth as a structural requirement of message passing, rather than an architectural choice whose benefits need to be demonstrated for particular tasks.
Questions for authors
Can you explain how Propositions 4.2 and E.1 imply the ordering of actual effective depths required by Definition 4.1? If they establish only a topology-dependent upper bound, would you revise the corresponding claims, including Remark E.1?
For graph-level tasks, how is the local receptive-field statement compatible with broadcasting a globally pooled prediction to every node? Can you separate the benefit of prediction refinement from that of global communication, for example using a comparable recurrent model with a pooled global state that is not a prediction?
Can you report DrugOOD OOD test results after validation-only selection, and compare against a matched recurrent baseline on the controlled task and tuned standard GNNs on Peptides-struct? These comparisons would help determine whether the improvements come from the proposed feedback mechanism.
Which PEARL implementation and configuration were timed in Table 5, and which operation was identified as an eigendecomposition? The explanation currently conflicts with the construction of PEARL.
4 comments
W1.3/Q2: Broadcasting the pooled prediction is global, so the locality claim fails for graph-level tasks
For graph-level tasks, each node does receive the graph-level prediction. This is by design and is stated in the architecture (lines 255–257, Equation 6). The receptive-field property in Section 3.1 (lines 280–282) refers to message passing: all exchange between nodes remains restricted to edges, for both task types. We have made this distinction explicit in the revised text.
We would also like to emphasize that this is not the dense communication our locality claim is contrasted against (lines 083–086). Every node receives the same -dimensional vector, so no node-to-node routing takes place through it. This vector is also small: on Reddit-B and DrugOOD and 5 on Reddit-M, against .
Finally, our adaptivity results do not involve this channel at all. The controlled task is node-level (lines 397–398), where and no pooled signal exists. Both the accuracy gains and the topology-dependent convergence of Figure 2 are obtained there. The control the reviewer suggests is a useful addition for the graph-level benchmarks, and we will include it.
W2: The experiments do not sufficiently establish the advantage over well-tuned alternatives.
We strongly disagree with this characterization. Please see our responses to the concerns you raise below.
W2.1/Q3 DrugOOD is selected and reported on OOD validation
This is correct but is clearly stated in our manuscript(lines 1155–1157, captions of Fig. 3 and Table 2) and we argue that it does not affect the soundness of the validation:
First, the comparison is fair across models. All four models are trained with one protocol, with the same selection split, the same selection rule, and the same sweep budget (lines 1126–1132). Any optimism from selecting on validation therefore applies to every model alike. Moreover, Base-U is reported at its sweep maximum, whereas TRGNN is reported at the smallest configuration that matches it, not at its own maximum (lines 1151–1154). The protocol does not favor TRGNN.
Second, the reported split is itself out-of-distribution. In DrugOOD, the OOD validation set is drawn from domains unseen during training (lines 1076–1078), so OOD-validation AUROC measures generalization under domain shift. It is among the metrics reported in prior work on this benchmark (Kanatsoulis et al., 2025).
Regardless, we will add OOD-test AUROC at the validation-selected checkpoints in the revision as a source of additional information.
W2.2/Q3 Controlled task has no matched recurrent baseline
This experiment was not designed as the feedback ablation. It tests that fixed depth trades reach against over-smoothing, which GIN-4 and GIN-5 show by crossing over as varies (lines 399–401), and that TRGNN’s effective depth tracks topology. The GINs are parameter-matched within about 3% (lines 1104–1106). Prediction feedback is isolated on five benchmarks (Sections 5.1–5.2) through TRGNN$^{-y}$, the matched weight-tied recurrence. We will add it to the controlled task.
W2.3/Q3 Table 1 omits Tönshoff et al. and related work omits AMP
Table 1 follows the Peptides-struct comparison used by recent architectural work on GNNs [5, 6]. We use the same baselines, the same 500K parameter budget, and results as reported there (lines 1161–1163). We adopted this set so that our results are directly comparable to that line of work, and so that the baseline set is inherited and not selected by us.
Tönshoff et al. study a different axis. They retune standard MPNNs and attribute most of the gain to a deeper prediction head, with structural encodings in every tuned model. These are choices of training recipe and input features, not of the message-passing architecture. TRGNN reaches the same MAE (0.247 vs. 0.246–0.248) without structural encodings (lines 1114–1116), consistent with the claim of Section 5.3 (lines 461–462). We will add their reported results to Table 1.
We will also add AMP to the related work alongside ADMP-GNN (lines 887–889). AMP learns one depth distribution shared across inputs and allocates separate parameters to each layer. In contrast, in TRGNNs, effective depth varies per graph and parameter count is independent of depth.
W2.4/Q4 PEARL runtime and timing concerns
The cost we report is from PEARL's own analysis: PEARL propagates random (R-PEARL) or basis (B-PEARL) signals per graph through its encoding GNN at every forward pass, giving a complexity of and computation, respectively, with and memory when parallelized (Kanatsoulis et al., 2025, Sections 4.4 and 5.2). By the authors' own account, B-PEARL's cost is quadratic on molecular graphs, which is the regime of Peptides-struct.
Our sentence attributing this cost to an eigendecomposition (lines 1241, 1251–1252) misstates the mechanism and will be corrected. However, the measurements in Table 5 are unaffected and moreover are derived from the official implementation released by the PEARL authors.
W3.1. The elasticity window is not justified as a necessary range of useful depths.
The elasticity window characterizes the message-passing operator, not a particular task (lines 195–196). The paper presents both endpoints as the reviewer describes them: as a worst-case requirement (line 161) and as an "effective upper bound" under regularity assumptions (lines 165–166, 174), hence the in Equation 5. Both follow from standard results: the -hop receptive field of Equation 1 and the over-smoothing rate of Equation 3 (Oono & Suzuki, 2020; Cai & Wang, 2020). Our argument requires only that these endpoints shift with topology, not that either is tight for a given task.
W3.2. Non-overlapping windows do not establish that fixed depth fails, so adaptive depth is an architectural choice to be demonstrated, not a structural requirement.
The paper does not claim that fixed-depth models cannot perform well. It claims that no fixed is "uniformly admissible" when windows fail to overlap (line 195), so depth must depend on the input for every graph to lie in its window. This holds for the operator regardless of the task, which is the sense of "structural" (lines 195–196).
Whether it matters for a given task is an empirical question, and we treat it as one. On the controlled task, neither fixed depth dominates across topologies, while TRGNN reaches 0.17 MAE against 0.62 for the best baseline (lines 399–403). On real benchmarks we claim parameter efficiency at matched accuracy, not that fixed depth fails.
Thanks for clarifying the theory and locality claims. I’m keeping my score at 2 because the DrugOOD comparison still relies on the validation split and the shortest-path experiment lacks a matched recurrent baseline.
Thank you for your thoughtful review of our work and for highlighting the overall utility of prediction feedback as a prediction preserving mechanism, the empirically verified parameter savings, and the comprehensive nature of our overall empirical work. We directly address your concerns and questions below:
The scope that you describe here is the scope we intend throughout our paper, though lines 309-311 and 412 could be more carefully worded, so we have revised them accordingly. Topology-adaptivity is claimed empirically (lines 022–023, 120–123), and our theoretical contribution is carefully qualified elsewhere (e.g. lines 023–025, 124–126, 374–376, 323, 1311–1314).
Moreover, we argue such a restriction is quite standard in the context of the related literature: Prop. E.1 holds in the normalized-adjacency, bounded-weight-norm setting in which the over-smoothing rate κ(G) Eq. 3 is derived [1, 2]. As argued throughout the manuscript, a general relation between convergence and κ(G) cannot be stated in greater generality than κ(G). Additionally, the convergence hypothesis of Proposition 4.2 is a standing assumption of recurrent and implicit GNNs [3, 4] and is easily enforceable by common techniques such as spectral normalization (lines 370–371).
We would also emphasize that we empirically measure the ordering of effective depths. Specifically, Teff is computed for each graph relative to its own initial residual value (lines 1111–1112), thus controlling for dependence on initial distance. Across the held out test set in our synthetic experiment, Teff correlates strongly with ∣λ2(A^)∣ (Pearson 0.91, Spearman 0.88, Figure 2c) and moreover persists under an absolute stopping rule (r up to 0.78; Table 8). Topology-adaptivity is therefore observed directly in the trained model, and in the restricted setting, Prop. E.1 explains why the bound on effective depth depends on topology.
In response to your feedback, we have edited the sentence at line 1308–1309 to refer to the bound on effective depth in order to avoid any other reading.
[1] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
[2] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13318, 2020.
[3] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009.
[4] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems, 33:11984–11995, 2020.
We agree with such an assessment but emphasize that the manuscript states this explicitly. Proposition 4.1 is a capacity result: the architecture “permits prediction preservation but does not guarantee that learned parameters achieve it” (lines 357–358). Also, Prop. 4.2 concerns only convergence.
Whether iteration improves accuracy depends on the learned parameters, so we treat it as an empirical question (lines 447–448) and measure it in our experimental work. For instance, in the controlled experiment in Section 4, test error decreases monotonically with iteration for every graph family (Figure 2b). On all five benchmarks of Section 5.1, iteration and performance have Spearman ρ≥0.95 (Figure 5) and this is moreover stable across folds and seeds (Table 7).
Finally, our experimental ablation connects our theoretical contribution to accuracy improvement: When we remove prediction feedback (that is, the mechanism behind Proposition 4.1), monotonically non-decreasing accuracy is lost and thus iteration can degrade performance (eg Spearman ρ≈−0.6 on DrugOOD-Size, lines 449–450). Monotone improvment is thus tied to the mechanism behind Prop 4.1.