acceptodds
Under review as a conference paper at ICLR 2027

Recursive Message Passing is Topology-Adaptive

Abstract

Graph neural networks perform message passing through a fixed sequence of layers and thus couple parameterization, receptive field, and computation. We identify this _coupling problem_ as a central structural limitation of message passing: no single depth can simultaneously avoid over-smoothing dense, low-diameter graphs while reaching across elongated or weakly connected ones. We argue that input-adaptive depth is therefore a structural requirement of the message-passing paradigm, and introduce Tiny Recursive Graph Neural Networks (TRGNNs) to realize it. TRGNNs combine _recursive message passing_, which decouples effective depth from parameterization, with _iterative prediction refinement_, which refines node predictions at each recursive step so that effective depth emerges from a learned function of the downstream accuracy, where predictions stabilize as effective depth increases, rather than a predetermined layer count or other external halting signal. We show empirically that these mechanisms yield _topology-adaptive effective depth_. Moreover, we establish a restricted formal connection between the rate at which latent representations approach a fixed point and the spectral quantity governing over-smoothing. Empirically, TRGNNs match or exceed GNN performance while using far fewer parameters and support anytime prediction.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph machine learning, adaptive learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_WE7dOpenReview ↗
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

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:

W1.1/Q1 Our theoretical discussion relies on an upper bound on effective depth and thus does not establish topology-adaptivity as defined in Definition 4.1

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)\kappa(G) Eq. 3 is derived [1, 2]. As argued throughout the manuscript, a general relation between convergence and κ(G)\kappa(G) cannot be stated in greater generality than κ(G)\kappa(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, TeffT_{eff} 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, TeffT_{eff} correlates strongly with ∣λ2(A^)∣|\lambda_2(\hat{A})| (Pearson 0.91, Spearman 0.88, Figure 2c) and moreover persists under an absolute stopping rule (rr 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.

W1.2: Convergence and preservation do not guarantee better accuracy.

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\rho \geq 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\rho \approx -0.6 on DrugOOD-Size, lines 449–450). Monotone improvment is thus tied to the mechanism behind Prop 4.1.

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 dyd_y-dimensional vector, so no node-to-node routing takes place through it. This vector is also small: dy=1d_y=1 on Reddit-B and DrugOOD and 5 on Reddit-M, against dh≥32d_h \geq 32.

Finally, our adaptivity results do not involve this channel at all. The controlled task is node-level (lines 397–398), where yˉ=y\bar{y}=y 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 pp 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 MM random (R-PEARL) or NN basis (B-PEARL) signals per graph through its encoding GNN at every forward pass, giving a complexity of Θ(MNF2+M∣E∣F)\Theta(MNF^2+M|E|F) and Θ(N2F2+N∣E∣F)\Theta(N^2F^2+N|E|F) computation, respectively, with Θ(MNF)\Theta(MNF) and Θ(N2F)\Theta(N^2F) 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: TreachT_{reach} as a worst-case requirement (line 161) and TsmoothT_{smooth} as an "effective upper bound" under regularity assumptions (lines 165–166, 174), hence the ≲\lesssim in Equation 5. Both follow from standard results: the LL-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 LL 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.

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

In message passing, a single depth simultaneously governs parameterization, receptive field and computation, so no fixed depth can both avoid over-smoothing on dense, low-diameter graphs and reach across elongated or weakly connected ones. This paper proposes TRGNN, which decouples effective depth from parameterization through weight-shared recursive message passing and feeds a persistent prediction back into the latent update, so that additional iterations need not degrade the output. Stop-gradient on intermediate iterations keeps training memory constant and yields anytime inference. On graph-classification, out-of-distribution and long-range benchmarks, TRGNN matches much larger baselines with far fewer parameters.

Critical strengths
  1. The "coupling problem" and the elasticity window are a genuinely useful conceptual frame. The frame observes that a single depth L simultaneously constrains parameterization, receptive field and computation, and therefore cannot satisfy the opposing demands of avoiding over-smoothing while reaching across long ranges; the resulting elasticity window T_reach(G) ≤ L ≲ T_smooth(G) has a location and width that depend on the topology. It is simple, correct, and gives the field a compact way to talk about why depth tuning is topology-dependent.

  2. The mechanism is minimal and cleanly isolated, and both parameter efficiency and anytime behaviour are measured rather than asserted. Putting the prediction y^(t) into the recurrent state (rather than merely recursing on latents) is a small change with a clear rationale, and the TRGNN−y ablation is exactly the classical weight-tied GNN recurrence, so the comparison is a true ablation rather than a strawman. Parameter efficiency is reported against both a parameter-matched and an unconstrained baseline, and the paper does not overclaim — it reports matching the unconstrained baseline rather than beating it; anytime monotonicity is quantified with Spearman ρ, with the ablation's spread reported alongside its mean.

Critical weaknesses
  1. The title claim (topology-adaptive effective depth) is not demonstrated on any real dataset. Adaptivity is defined as a per-graph property, yet the only evidence for it comes from a synthetic Watts–Strogatz shortest-path task with a one-dimensional input and 64-node graphs; the adaptive-stopping experiment is likewise synthetic only. On the real benchmarks the model runs a fixed T selected by a sweep, and the results report parameter efficiency and monotone improvement with T — never that different graphs in a real dataset want different depths. More importantly, on the only real long-range benchmark, Peptides-struct, TRGNN reaches MAE 0.247, tying R-PEARL but behind SUN (0.245) and GViT (0.243) — so in the very real-data regime where a longer effective depth should pay off most, the paper again provides no positive evidence.

  2. Compute is never controlled, and matching parameters alone favours recursion. Every headline comparison matches parameters, never compute. In the controlled experiment the recursive model runs 128 outer iterations at full width while the fixed-depth baseline's hidden width is shrunk analytically to match parameters — i.e. roughly 32× more message-passing operations — and inference is several times slower than the unconstrained baseline on real data. "Fewer parameters" and "less compute" are different claims, and only the first is supported.

Questions for authors
  1. (Adaptivity on real data). Please report, for at least one real benchmark (Reddit-B, DrugOOD-Scaffold or Peptides-struct), a per-graph T_eff (or halting iteration under the residual stopping rule) against |λ₂(Â)|, diameter or graph size, with a correlation coefficient — i.e. the synthetic-graph figure redone on real graphs. This is the direct evidence for CW1 and a prerequisite for raising my score.

  2. (Compute-matched comparison). Please add a compute/FLOP-matched comparison: (a) on the controlled task, deeper fixed-depth models at full width plus residual / PairNorm / GCNII-style over-smoothing mitigations; (b) on the real benchmarks, a baseline matched on inference cost rather than parameters. Does the reported gap survive when the fixed-depth model is allowed the same number of message-passing operations?

  3. (Reporting consistency). Please reconcile the parameter counts and accuracies reported for the same model–dataset pair across the main-text and appendix tables, and confirm which configuration each table uses. Please also add paired significance tests for the main results and comment on the unusually large standard deviation of the ablation on one of the datasets.

1 comment

Thanks for your thoughtful review and for highlighting the soundness and utility of the coupling problem and elasticity window, the minimal and cleanly isolated mechanism, and the experimentally demonstrated parameter efficiency gains and anytime behavior.

We had planned to include additional experiments in this response, including per-graph effective depth against ∣λ2(A^)∣|\lambda_2(\hat{A})| and diameter on Reddit-B, compute-matched comparisons on the controlled task and the real benchmarks, and paired significance tests for the main results. Unfortunately, we lost access to our compute and storage during the response period due to a security incident beyond our control. We have therefore answered each concern as fully as possible with existing results, and will include these experiments in any possible camera-ready version.

W1.1 / Q1. Adaptivity is shown only on synthetic data.

We deliberately chose a controlled synthetic setting to demonstrate adaptivity in an interpretable and sound way: Adaptivity is a claim about how effective depth depends on topology, and testing it requires varying topology while holding the task and features fixed. Watts-Strogatz rewiring is thus suitable for this task as it does exactly this (lines 394–397). On real datasets, topology co-varies with features, labels, and graph size, so a correlation there cannot be attributed to topology alone. Our manuscript carefully and clearly qualifies this: adaptivity is shown "across controlled experiments" (lines 121–122), and the real benchmarks run a fixed TT (lines 1383–1385).

What the real-world evaluation benchmarks do establish is the property that makes per-graph depth useful in practice: predictions improve monotonically with iteration (ρ≥0.95\rho \geq 0.95, Figure 5) and converge approximately geometrically (Figure 4).

W1.2 Peptides-struct results.

We believe you may be miss-interpreting Table 1: TRGNN (0.247) is ahead of SUN (0.250), B-PEARL, GPS, SAN, and GNN-AK+, level with R-PEARL, and behind only GViT (0.245) and B-PEARL+SRF (0.243). As explained in the manuscript, GViT uses attention over graph patches with random-walk encodings, and B-PEARL+SRF relies on PEARL at about 32×32\times the runtime of TRGNN (lines 462–466). Our main claim in Section 5.3 is that we can reach similar performance with message passing alone.

W2 / Q2 Compute is not controlled, and matching parameters favors recursion.

We agree that "fewer parameters" and "less compute" are different claims, but our manuscript makes only the former: we name sequential inference as an explicit limitation (lines 483–485) and report runtime for each tested model (Table 4). We would like to respectfully push back on two of your premises. First, the main comparison in Figure 1 is not only parameter-matched. In addition, Base-U is unconstrained and independently tuned (lines 427–428), with TRGNN matching performance. Second, inference is not uniformly slower: on Reddit-B, TRGNN is faster than Base-U in training and inference (0.47 vs. 1.20 s/epoch, 0.040 vs. 0.064 s/pass). However, it is slower on DrugOOD. Also, our controlled experiment in Section 4 tests the depth tradeoff, not efficiency, and with a simple stopping rule the same model needs 36% fewer iterations to achieve the same accuracy (Table 8).

Q3 Potential consistency issues

Regarding parameter counts and accuracies: Tables 2 and 6 have both different configurations and reporting protocols. Table 2 uses the selection described in Section 5.1 (e.g. the smallest TRGNN that matches Base-U) and reports 10-fold validation accuracy (lines 1150–1157) as is standard for the Reddit datasets. Table 6 uses the configurations described in Section 5.2. That is, models are retrained with Ttrain=16T_{train}=16 (lines 1143–1145, 1331), with selection on a held-out split and test accuracy reported (lines 1333–1335). We will further clarify these methodological differences and more explicitly link it to their respective standard practices for the given datasets in the Appendix.

On statistical significance: Our central claim in Section 5.1 is that TRGNN matches performance Base-U but with far less parameters. This is underscored clearly by experimental evidence, namely that all but one result in Table 2 lies within one standard deviation. Paired tests against the classical recurrent baselines are in Appendix F (p≤0.02p \leq 0.02). However, in response to your feedback we commit to including paired tests for the results in Section 5.1 in any future camera ready version of the manuscript.

On ablation variance: The large variance observed in the accuracy of TRGNN$^{-y}$ on the Reddit-M dataset is consistent with the non-monotonicity we report and describe throughout the paper. That is, without prediction feedback, accuracy at a fixed TT depends on where each fold's trajectory happens to lie (Figures 4 and 5). We hypothesize that this instability doesn't occur in the non ablated TRGNN due to the presence of the feedback mechanism.

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

This paper addresses the well-known problem of using a fixed depth GNN on a heterogeneous graph structure where different nodes may require different depth for attaining optimal neighborhood information without underreaching or oversmoothing with a more fundamental recurrent solution with shared weights and potentially infinite depth rather than an elaborate fixed depth architecture.

Critical strengths

The paper realizes adaptive depth in a parameter-efficient solution. The architectural element of conditioning the output head explicitly on the previous prediction, rather than relying on optimization to find a network representation that preserves it, is an interesting, simple modification that seems to be quite effective for converging without explicit halting.

Critical weaknesses
  1. The first contribution claimed by the paper, i.e., the coupling problem, is not novel, and the mismatch between fixed-depth computation and input-dependent topology has been identified for quite a while now, also leading to several works on not only adaptive depth but also other aspects of message passing, such as learning a task-aligned balance between retaining self-representation and updating state with the aggregated neighborhood at the node and layer level. This is not to say that I do not acknowledge that the maximum depth is fixed in most such cases, which makes the second listed contribution of this paper viable and important. However, MGNNI [1] also introduces effective depth on implicit GNNs, so it also merits a discussion or empirical comparison.

  2. Heterophilous graphs, such as the benchmark in [2], which are a common case for evaluating adaptive depth approaches in GNNs, are not used for evaluation. Also, only a single dataset from the LRGB is evaluated, even though this is also an important case for adaptive depth GNNs.

  3. The tradeoff between parameter and time efficiency should be mentioned more explicitly in the main paper as well, since the training times are significantly higher than any performance gains.

[1] MGNNI: Multiscale Graph Neural Networks with Implicit Layers (NeurIPS 2022).

[2] A critical look at the evaluation of GNNs under heterophily (ICLR 2023)

Questions for authors

Why is the input encoder fixed instead of being trainable?

2 comments

Thanks for your thoughtful review of our work and for highlighting the parameter efficiency of our approach, the simplicity and effectiveness of conditioning the prediction head on the previous prediction, and the importance of our adaptive-depth contribution.

We had planned to include additional experiments in this response, including evaluation on the heterophilous node-classification benchmark of [2] and on two further LRGB datasets (Peptides-func and PascalVOC-SP). Unfortunately, we lost access to our compute and storage during the response period due a security incident outside of our control. We have therefore answered each concern as fully as possible with existing results, and will include these experiments in any possible camera-ready version of the manuscript.

We respond to each of your concerns below.

W1. The coupling problem is not novel

We respectfully but firmly disagree. We do not claim to have discovered underreaching or over-smoothing. Indeed, both Section 2.1 and Appendix A.3 clearly attribute both concepts to prior work. Our contribution is more precise: we argue that a single depth LL simultaneously governs the parameter count, receptive field, and computation of a given MPNN (lines 046–053), and the elasticity window (Equation 5) formalizes the range of admissible depths per graph. The adaptive-depth and neighborhood-balancing methods from prior work you describe act inside a fixed stack, so parameters and maximal receptive field remain tied to LL (lines 887–889, 913–915). Additionally, as you note, their maximum depth is fixed. This is precisely what we call the coupling problem, and what prior methods leave unresolved.

MGNNI studies the effective range of implicit GNNs, which the contraction of their fixed-point formulation restricts (they resolve this with a novel intervention). Thus, such a work belongs to the implicit-layer line of literature we already discuss and distinguish from TRGNN (lines 214–216, 860–885). We have now added MGNNI to this Section. Such models solve for an equilibrium under a contraction constraint while TRGNN iterates explicitly, feeds back its prediction, and requires no contraction (lines 1345–1347).

W2. No heterophilous benchmarks are used, and only one LRGB dataset is evaluated.

Our evaluation follows the benchmark suite of recent architectural work [1]. It includes seven datasets and splits spanning social, molecular OOD, long-range, and controlled node-level tasks (line 1049). The heterophilous benchmark of [2] and further LRGB datasets probe complementary settings. However, as stated in the top level comment, we will include such results in any camera ready version of the manuscript.

W3. The tradeoff between parameter and time efficiency should be more explicit in the main paper.

We state this tradeoff explicitly in the manuscript: the conclusion section names sequential inference as the method's limitation (lines 483–485). However, we also note that this limitation is shared by weight-shared methods more broadly, and, despite this, such methods have shown widespread utility in real world applications (as motivated in Section 2).

We also note that the premise does not hold uniformly: Our experiments show that on Reddit-B, TRGNN trains and infers faster than Base-U (0.47 vs. 1.20 s/epoch, 0.040 vs. 0.064 s/pass; Table 4) while it is slower on DrugOOD. The benefit we claim is 22–205×205\times fewer parameters at matched accuracy (Table 2), not accuracy gains.

Q1. Why is the input encoder fixed instead of being trainable?

The encoder ηα\eta_\alpha is trainable – its parameters α\alpha are learned jointly with θ\theta and ω\omega (lines 243–245, 278). The "held fixed" (line 254) refers to its output XencX_{enc}, which is computed once and reused across iterations since the input does not change. We will reword this sentence for sake of clarity.

[1] Charilaos Kanatsoulis, Evelyn Choi, Stefanie Jegelka, Jure Leskovec, and Alejandro Ribeiro. Learning efficient positional encodings with graph neural networks. In The Thirteenth International Conference on Learning Representations, 2025.

Thank you to the authors for their response. While 'coupling' has also been used earlier to describe the joint feature transformation and message propagation at each layer in GNNs, in this paper, if I understand correctly, it refers to separating the parameter count and maximum depth from the number of layers. Since shared weights are used to learn the feature transformation, I think that is also decoupled from the depth. I have just a couple of follow-up questions. With TRGNNs, am I correct to believe that the adaptive depth is only at the graph level, and not at the node level? Secondly, apart from the architectural elements particular to Transformers, such as attention, is the core idea any different from Looped Transformers?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.