acceptodds
Under review as a conference paper at ICLR 2027

Groot: Node-Specific Global Graph Propagation via Bidirectional Forest Scans

Abstract

Long-range graph propagation often relies on deep local message passing or dense global interaction mechanisms. We introduce GROOT (Global Rerooting Operator over Trees), a graph neural layer built around a bidirectional forest-scan operator. It compiles a sparse graph into a cached rooted spanning forest and computes node-specific global states through one bottom-up aggregation followed by one top-down rerooting scan. Learned channel-wise gates induce an implicit path kernel in which every source can influence every target within its forest component, without materializing a dense node-pair matrix. Edges outside the forest contribute through a single sparse source-correction term injected into the shared scan. We prove the exact equivalence between the scan and the normalized path- product kernel, characterize its conditional permutation equivariance, and establish O(ED + N D) structural work and O(E + N D) memory for width D. A custom CUDA implementation enables training on large-scale sparse graphs. Across five random seeds, GROOT consistently improves over strong local and global baselines in power-flow estimation, gas-network state estimation, water-network sensor recovery, and graph classification. On a large-scale London road graph, GROOT improves accuracy over GraphSAGE and IM-MPNN by 4.98% and 0.94%, respectively. Controlled experiments isolate the contributions of bidirectional scanning and learned gates, while molecular and citation tasks further characterize the forest-path bias. Overall, these results establish forest scanning as a practical global operator for sparse graphs with reusable tree-aligned propagation structure. Code is available at https://anonymous.4open.science/r/groot-FCC2.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, long-range graph learning, global graph propagation, forest scans, scalable sparse graph learning

Reviews

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

The paper proposes GROOT, a graph layer that propagates information globally over a fixed spanning forest of the input graph. Each layer runs two passes over the forest: (1) a bottom-up pass, which summarizes every subtree, and (2) a top-down "rerooting" pass, which gives every node a summary of the rest of its tree.

Learned gates on the tree edges control how much each edge passes on. The authors prove that the two passes compute a normalized weighted average over all nodes in the component, where the weight between two nodes is the product of the gates along their tree path. Edges that are not in the forest enter only through one sparse correction added to the inputs. The layer has linear cost and comes with a custom CUDA implementation.

Critical strengths
  1. The idea is simple and well explained overall. The proof that the two passes compute the path-product kernel exactly is clean and easy to check.

  2. The implementation work is substantial using CUDA.

  3. The infrastructure tasks (power, water, gas networks) are a nice choice. These graphs are sparse and close to trees, so a tree-based operator is a natural fit, and GROOT is clearly better than the included baselines there.

  4. The authors are honest about failure cases. They report tasks where GROOT loses and limitations such as attenuation on cycles and memory cost.

Critical weaknesses

The engineering is solid, and the results on near-tree infrastructure networks are good. However:

  • The core operator, a normalized path-product kernel over a spanning tree computed exactly in linear time by two passes, has been published before in vision (the learnable tree filter, NeurIPS 2019, and its follow-ups). None of that work is cited.
  • The empirical comparison uses a different, small set of baselines for each task.
  • On standard graph benchmarks the method is mostly behind simple baselines.
  • The paper is hard to read because the text is overloaded with numbers and implementation details.

I detail the major comments below.

  1. The main operator is not new. Very similar ideas are already published and not cited:
    • Learnable Tree Filter (Song et al., NeurIPS 2019) builds a minimum spanning tree over the input and computes, in linear time with a two-pass algorithm, a normalized weighted average over all nodes, where the weight between two nodes depends on the edge weights along their tree path. This is very close to Eq. (10)–(11) and Proposition 1. A follow-up (LTF-V2, NeurIPS 2020) makes the spanning tree learnable.
    • Both build on the classic tree filtering method of Bao et al. (2014), which already had a linear-time two-pass algorithm on a minimum spanning tree.
    • GrootVL / MambaTree (Xiao et al., NeurIPS 2024) generates a spanning tree from the input and propagates features over it with a linear-time dynamic program, explicitly to improve long-range interactions. Beyond the content overlap, the near-identical name may confuse readers.
    • FGL (Li et al., ICLR 2026) is cited and is also very close. It already propagates over spanning trees for node classification, with a linear-time tree aggregator that realizes all node-pair interactions.

The paper is incremental although it argues that its contribution is the complete "layer contract" (single fixed forest, channel-wise gates, one non-tree correction, CUDA operator). I find this a fairly thin difference. The authors should clearly explain what is new compared with these works, and ideally compare against a tree-filter-style layer and FGL on the same tasks.

  1. Baselines change from task to task, and some strong ones are missing.

    • In Table 1, each dataset has its own small set of baselines. SimBench has no GCN, SGFormer or APPNP. GasLib has no GCN or GatedGCN. PROTEINS is compared only against GCN and GIN, with no virtual-node model, no transformer, and no tree-based or hierarchical model.
    • The PROTEINS accuracy is in the range commonly reported for standard GNNs under other protocols, so I am not convinced this shows a real advantage of global propagation.
    • The synthetic path/cycle experiment compares only against a 2-layer GCN, which must fail beyond two hops by construction. A comparison with a virtual node, a deep GCN, APPNP or a graph transformer would be more informative.
  2. The headline City-Networks gain partly comes from a weaker rerun of the baseline.

    • The abstract claims a gain of almost 5 points over GraphSAGE on London. But the authors' own rerun of GraphSAGE is clearly below the number the benchmark authors report (Table 3). Against the published number, the gain is roughly half as large.
    • Against IM-MPNN the gain is under one point, while GROOT uses more than three times the memory.
    • All methods were still improving at the fixed epoch budget, so the comparison is not at convergence.
    • I would tone down the claims in the abstract and introduction.
  3. Results on standard benchmarks are weak.

    • On OGBN-Arxiv, GROOT is several points below plain GCN.
    • On ECHO-Synth, it is more than twice as bad as Stable-ChebNet.
    • On Peptides-func, it beats small baselines but is far from current models.
    • The paper calls these "boundary results", which is fair. But together with item 2, it suggests the method mainly helps on graphs that are close to trees, which is a narrower claim than "a practical global operator for sparse graphs".
  4. Limits of the single-path bias are not studied enough.

    • Each pair of nodes interacts only through one tree path. All other edges are folded into a single scalar-weighted correction (one α per layer, shared across all nodes, channels and edges). This is a strong simplification for graphs with many cycles. It shows up in the drop on the cycle task and in the large error without the correction on ECHO.
    • The gates lie between 0 and 1, so long paths are multiplied down, and after normalization nearby nodes dominate. The "component-wide receptive field" is therefore mostly nominal on large graphs. A measurement of how much influence actually reaches distant nodes in the trained models would help.
    • Permutation equivariance holds only given the forest, and the forest depends on a random seed. Results for several forests are shown only on SimBench.
  5. The efficiency claims need more context.

    • The operator is linear, but it needs one GPU launch per tree level, and road graphs have trees hundreds of levels deep.
    • Building the forest on the CPU takes minutes for a million-node graph.
    • GROOT is about 2 to 3 times slower than GCN per epoch, and uses much more memory on London.
    • The scaling plots measure synthetic random graphs, not the real ones.

This is all reported, but scattered over many appendix tables. A short, honest summary of the cost in the main text would be clearer than the current "practical at scale" wording.

  1. Positioning against cheap long-range methods. The paper motivates GROOT through over-squashing and long-range dependencies. It does not discuss low-cost alternatives that target the same problem by changing the graph rather than the layer, such as:
    • spectral or curvature-based rewiring (e.g., spectral graph pruning, NeurIPS 2024; AFRC rewiring, LoG 2023);
    • hierarchical message passing (e.g., HGNet ICLR 2025);
    • low-cost oversmoothing & oversquashing detection and fixing across varied topologies (e.g., DeltaGNN, TPAMI 2026).

IM-MPNN is included, which is good, but a short discussion of why a fixed spanning forest is preferable to these approaches would help readers place the work.

  1. Heavy writing. The method section is clear, but the rest of the paper is hard to read. Compare it with well-written papers from a few years ago, such as GCN (Kipf & Welling), GAT or GIN. Those papers put results in tables and use the text to explain what the numbers mean, usually citing only one or two key values. This paper does the opposite: almost every paragraph is packed with numbers, and many have more precision than is useful.
Questions for authors
  1. How does GROOT differ from the learnable tree filter (NeurIPS 2019/2020), GrootVL (NeurIPS 2024) and FGL (ICLR 2026)? Can you compare against a tree-filter layer and FGL on at least a few of your tasks?
  2. Can you use the same set of baselines for every task in Table 1, including a virtual-node model, a graph transformer and APPNP/GCNII?
  3. How much influence actually reaches distant nodes in trained models, given that gate products shrink along long paths?
  4. How sensitive are the main results to the choice of forest (BFS, DFS, MST, different seeds) beyond SimBench?
  5. Would a richer non-tree correction (e.g., per-edge or per-channel weights instead of one scalar) close the gap on cyclic graphs such as ECHO?
3 comments
AuthorsOpenReview ↗

Revised Novelty Positioning, Added Controls, and Calibrated Cost Claims

Thank you for the detailed review. We agree that the submission under-cited tree filtering and overclaimed from accuracy. We now cite Bao et al. (2014), LTF/LTF-V2, MambaTree, and FGL. For fixed trees and symmetric group-shared gates, the normalized path-product scan has LTF's kernel form, up to numerical stabilization; we do not claim the recurrence as new. GROOT's claim is a native layer on a supplied sparse graph combining a compiled forest, endpoint-conditioned channel-wise directed gates, path-mass normalization, one sparse non-forest correction, residual composition, and exact factorization. CUDA is a separate systems contribution. MambaTree is relevant tree-state-space work on visual trees and language sequences; GrootVL is its earlier preprint title.

FGL combines homophily-guided multiple-tree sampling, directed scalar attentions with a shared transition, local propagation, tree fusion, and a local-global residual for semi-supervised node classification. GROOT uses one fixed forest and channel-wise gates with complementary-edge correction. These are method-level differences, not dismissal based on task. Its linked code was not retrievable as a verifiable runnable repository, so no direct FGL accuracy, preprocessing, runtime, or memory comparison is available. A five-seed TreeFilter-V2-style BattLeDIM control gives GROOT 0.11832 +/- 0.01328 m MAE versus 0.45322 +/- 0.17160 m (5/5 wins). This adapts the image recurrence and is not official LTF-V2; gate and source-correction changes are bundled, so it is not a causal component test.

Coverage remains task-dependent. We completed code-derived SGFormer runs on BattLeDIM, SimBench, and GasLib, plus GraphGPS GatedGCN on GasLib; adapters will be documented. BattLeDIM MAE is 0.1183 +/- 0.0133 m for GROOT and 0.5252 +/- 0.0304 m for SGFormer. GasLib unobserved NRMSE is 0.1427 +/- 0.0101 for GROOT, 0.2247 +/- 0.0692 for SGFormer, and 1.2066 +/- 0.0488 for GatedGCN. SGFormer does not use edge attributes, so this is not fully input-matched. SimBench lacks vanilla GCN/APPNP; PROTEINS has only GCN/GIN, not modern graph-classification SOTA. APPNP is not evaluated. The retrieval task adds shared-summary, virtual-node, 16-layer GCN, SGFormer-operator, and TreeFilter-style controls without a universal baseline set.

The multi-source diagnostic addresses whether a shared summary can solve the single-source task. On a 4,097-node tree with anonymous query branches and independent source labels, five-seed GROOT reaches 1.000 query and whole-set accuracy at K={4,16,32,64}. The strongest control reaches 0.659 query accuracy at K=4 and at most 0.576 at K>=16; all controls have zero whole-set accuracy at K>=16. A 16-layer GCN reaches the source within its receptive field but remains at chance. This supports target-specific retrieval in this construction, not universal superiority. The original path/cycle test still compares only with a two-layer GCN.

We will correct the London headline: 57.96% is 2.56 points above the authors' GraphSAGE result (55.4%), not 4.98 points; 4.98 is the gap to our direct rerun (52.98%). The gap to the direct official-code IM-MPNN rerun is 0.94 points (57.02%). All direct runs use a 5,000-epoch cap and still have late validation optima; these are fixed-budget, not converged or equal-compute results. GROOT uses about 40,480 MiB and has slower cached epochs. Our one-million-node scaling sweep is synthetic, not a real-graph scaling curve; there GROOT costs about 2x GCN. CPU forest construction at one million nodes takes 86.7/152.9/294.7 s for average degree 4/8/16, and launch synchronization grows with tree height. We will summarize these costs in the main text.

We retain the observed boundaries: Stable-ChebNet beats GROOT on ECHO-Synth (0.2660 +/- 0.0196 vs. 0.6028 +/- 0.0046 MAE), GROOT trails GCN/GCNII on OGBN-Arxiv (0.6776 vs. 0.7174/0.7191 accuracy), and stronger models exceed it on Peptides-func. Each pair has one forest path; gates attenuate long paths and the non-forest correction is one scalar per layer, not a per-edge/channel cycle model. For the BattLeDIM validation sensitivity diagnostic, 300 source-target pairs, including 297 at graph distance >=8, were evaluated across four independently trained checkpoints. Mean absolute input Jacobians are 0.02782 +/- 0.00250 for GROOT and 0.02726 +/- 0.00338 for Virtual-GINE, indicating measurable but not greater distant dependence. Five-seed BFS/DFS/MST retraining is available only on SimBench; BattLeDIM forest changes used frozen checkpoints, not retraining. The forest is compiled from the supplied graph; complementary edges enter through source correction, and the cached schedule amortizes preprocessing. Our London experiments already include the hierarchical IM-MPNN. Additional rewiring methods have not been directly evaluated. We will move detailed values to tables/appendix and keep only trend-defining numbers in the text.

Dear Reviewer,

As the rebuttal period is coming to an end, I would like to kindly ask you to read the authors' response and reply as soon as possible.

Thank you for your prompt attention.

Best regards,

Area Chair

Reviewer_LmVYOpenReview ↗

Maintaining my recommendation

I maintain my reject recommendation. While I appreciate the authors' detailed response, acknowledged mistakes, and the additional experiments, I do not believe the revisions sufficiently address my fundamental concerns regarding the novelty and overall contribution of the work.

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

GROOT performs node-specific global propagation through bottom-up aggregation and top-down rerooting on a cached spanning forest. Learned channel-wise gates define a normalized path-product kernel, while non-tree edges enter through a sparse source correction. The paper establishes exact factorization and linear structural work, provides a custom CUDA implementation, and evaluates predictive performance, mechanisms, and scaling.

Critical strengths
  1. Explicit and mathematically clear operator. The path-kernel formulation makes source–target coefficients interpretable, and the subtree-subtraction argument correctly establishes the two-pass factorization. The distinction between global reachability and influence attenuation is appropriately acknowledged.

  2. Substantial implementation effort. Cached schedules, analytic backward, workspace reuse, and recomputation support practical large-graph execution. The authors report detailed output and gradient consistency checks, with scaling experiments reaching one million nodes.

  3. Informative evaluation and scope reporting. Five-seed results, paired comparisons, component ablations, and separate preprocessing measurements provide useful evidence. Gains on physical-network tasks and London are accompanied by explicit negative or neutral results on other benchmarks.

Critical weaknesses
  1. The contribution relative to FGL remains insufficiently established. FGL already uses spanning trees and bottom-up/top-down aggregation with subtree removal. GROOT introduces a specific gated kernel, normalization, source correction, and execution strategy, but lacks a direct comparison with this closest predecessor. Consequently, the practical value of these additions is difficult to isolate.

  2. The mechanism evidence does not fully establish the necessity of node-specific propagation. Single-source bit recovery demonstrates global communication, but a shared global summary could also solve this task. Multi-source, multi-query controls would better test target-dependent weighting. Forest robustness is assessed through alternative constructions only on SimBench, while learned gate attenuation and sensitivity to forest seeds remain insufficiently characterized.

  3. Predictive gains need a clearer full-model cost and fairness assessment. Baseline tuning budgets and matching of non-core architectural components are not sufficiently documented. PROTEINS comparisons are limited to GCN/GIN, and some results are training-budget limited. Although costs are disclosed, London’s approximately 40,480 MiB allocation and slower cached epochs warrant a more direct accuracy–time–memory comparison. Equal epoch limits do not establish equal computational budgets.

Questions for authors
  1. How does GROOT compare with FGL or a matched single-/multi-tree variant in accuracy, preprocessing, runtime, and memory? Which additions account for the difference?

  2. Can target-dependent weighting be isolated using a multi-source, multi-query task with parameter-matched virtual-node or shared-global-summary controls?

  3. What search spaces and tuning budgets were used for each baseline? Can representative comparisons be supplemented with matched wall-clock budgets or longer-training results?

  4. How do forest seeds, forest-path lengths, and learned gate products affect accuracy? Can these measurements identify when the single-tree bias is beneficial?

2 comments
AuthorsOpenReview ↗

Clarifying GROOT’s Relation to FGL and Testing Target-Dependent Retrieval

Thank you for identifying the missing comparison to FGL and the need to isolate target-dependent propagation. We agree that sharing a tree recurrence is relevant prior art and that a different task domain alone does not establish architectural novelty. We now cite Bao's classical tree filter, LTF/LTF-V2, MambaTree (the conference title of the earlier GrootVL preprint), and FGL. For a fixed tree with symmetric group-shared gates, GROOT's normalized path-product scan has the same kernel form as LTF, up to numerical stabilization; we do not claim two-pass tree filtering or rerooting as new. GROOT's claimed contribution is the full native sparse-graph layer: directed endpoint-conditioned channel-wise gates, normalized path propagation, one sparse correction for non-forest edges, residual graph-layer composition, exact factorization, and a CUDA forward/backward implementation. We separate this implementation contribution from model novelty.

FGL is the closest native-graph predecessor. It uses homophily-guided multiple-tree sampling, directed scalar attentions with a shared transition, local propagation, tree fusion, and a local-global residual for semi-supervised node classification. GROOT instead compiles one fixed forest and uses a channel-wise normalized path kernel with complementary-edge source correction. We could not retrieve a verifiable runnable version from the official FGL link, so we cannot provide an official accuracy, preprocessing, runtime, or memory comparison. We do not claim that the task difference makes FGL irrelevant. As a closer mechanism check, a five-seed TreeFilter-V2-style control on BattLeDIM obtains 0.45322 +/- 0.17160 m versus 0.11832 +/- 0.01328 m for GROOT (GROOT wins 5/5). It adapts the published recurrence to the same sparse graph/forest, and is not official LTF-V2. Because it changes the gate parameterization and omits source correction together, it is a bundle comparison; it does not isolate which addition explains the difference, and no matched timing/memory claim is made.

The new topology-paired task tests multiple anonymous source-query branches with independent bits and no shared IDs. Across five seeds and K={4,16,32,64}, one-layer GROOT reaches 1.000 query and whole-set accuracy. At K=64, shared-summary and virtual-node controls reach 0.540 and 0.550 query accuracy; at K>=16, no control has nonzero whole-set exact recovery. All models use width 64 and identical episodes, seeds, validation selection, and frozen tests. This is width-matched, not parameter-matched: GROOT has 4,994 parameters, versus 13,057 for shared summary, 17,345 for virtual GCN, 38,593 for the SGFormer operator, and 69,121 for 16-layer GCN. Some global controls hit the 1,000-epoch cap. We therefore interpret this as evidence on target-dependent retrieval under a common epoch budget, not equal-compute superiority.

Existing five-seed ablations identify where components matter. On ECHO-Synth, MAE is 0.6028 for full GROOT, 1.8053 without source correction, 1.0450 with uniform gates, and 0.5881 with shared-direction gates. On BattLeDIM 2018 development, full GROOT is 0.0266, no-source is 0.0267, uniform gates are 0.1443, and shared-direction gates are 0.0308. These results support learned gates and both scan directions; source correction is important on this cyclic synthetic task but neutral on the near-tree BattLeDIM split. They do not show that every component improves every domain.

For a real-task sensitivity diagnostic, we evaluated the same 300 source-target pairs, including 297 at graph distance >=8, across four independently trained BattLeDIM checkpoints on the 2018 validation split. Mean absolute distant-pair input Jacobian is 0.02782 +/- 0.00250 for GROOT and 0.02726 +/- 0.00338 for Virtual-GINE, and zero for four-layer GCN. This shows measurable distant dependence, not an advantage over Virtual-GINE or causal utility. Five-seed BFS/DFS/MST retraining is available only on SimBench (MAEs 1.4170/1.3575/1.3785 x 10^-5); BattLeDIM forest changes were evaluated only with frozen checkpoints on validation, not retrained. Broader hyperparameter search, matched-wall-clock training, and FGL remain unresolved. Equal epoch caps are not equal compute. London uses about 40,480 MiB and has slower cached epochs; we report this as an accuracy-cost tradeoff.

Thanks for the new results. The multi-source task largely addresses my concern about the original experiment. The TreeFilter-style comparison is also useful. It changes several components at once, so it cannot explain the effect of each component. But it does provide evidence for the full Groot design. Could you clarify which parts of LTF-V2 are kept in this control? In particular, does it include the learnable unary term?

My main concern is still the contribution over prior work. LTF already uses a normalized path-product kernel and two tree passes. FGL also uses tree aggregation with subtree removal for graph learning. I did not give this overlap enough weight in my initial review. Groot has useful differences. I also value the implementation and the results on physical networks. But I am still unsure whether these differences are enough to support acceptance. The new TreeFilter result helps, but it is one adapted control on one dataset. I am therefore changing my score to 2 (weak rejection). More detail about this control and the reasons for the performance gap would help me assess the remaining contribution.

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

The paper introduces GROOT, a graph neural network architecture designed to improve long-range information propagation through bidirectional spanning-forest scans. It combines established tree-based propagation techniques with learned channel-wise gates, non-tree-edge corrections, and efficient implementation to enable node-specific global information exchange with linear structural complexity.

Critical strengths
  1. The paper addresses the important challenge of long-range information propagation in GNNs, particularly over-squashing and the computational limitations of existing approaches.

  2. The approach leverages established tree-based propagation with learned gating and efficient computation.

  3. Experiments span synthetic long-range tasks, physical networks, graph classification, and large graphs, showing promising predictive performance across settings.

Critical weaknesses
  1. Bidirectional tree propagation is well established, and advantages over closely related tree-based approaches have not been sufficiently established.

  2. Controlled long-range tasks are included, but downstream performance alone does not isolate information-flow improvements. Direct sensitivity measurements between distant nodes could clarify whether the method mitigates over-squashing.

  3. More systematic comparisons with graph-rewiring and over-squashing methods, as well as related forest-based propagation methods, would help establish the advantages.

  4. The baseline coverage is incomplete and inconsistent, for example PROTEINS is compared only to GCN and GIN. SimBench and BattLeDIM lack SGFormer, GasLib lacks GatedGCN, and APPNP is listed in Sec. 5.1 but appears in no table This makes it hard to attribute gains.

5.Forest choice is tested only on SimBench.

Questions for authors

see weakneses

2 comments
AuthorsOpenReview ↗

Additional Evidence on Distant Influence, Forest Sensitivity, and Baseline Coverage

Thank you for the constructive review. We agree that the two-pass tree primitive is established and that the original submission did not sufficiently compare GROOT with related tree methods or measure distant influence directly. Our revised related-work discussion now cites classical tree filtering (Bao et al., 2014), LTF/LTF-V2, MambaTree, and FGL. For a fixed tree and symmetric group-shared gates, GROOT's normalized path-product scan has the same kernel form as LTF, up to numerical stabilization. We do not claim the rerooting recurrence itself as new. We instead identify GROOT's contribution as a native sparse-graph layer that combines directed endpoint-conditioned channel-wise gates, path-mass normalization, one sparse non-forest source correction, a residual layer interface, an exact factorization, and a CUDA implementation. CUDA is an implementation contribution, not by itself a novelty claim. FGL is also a native-graph predecessor; its multi-tree sampling, scalar directed attention, shared transition, local branch, and tree fusion differ from GROOT's fixed-forest channel-wise kernel. We could not obtain a verifiable runnable version of its linked code, so we do not claim direct FGL superiority.

We added a topology-paired multi-source retrieval diagnostic to distinguish target-specific routing from access to a shared summary. On a 4,097-node tree, anonymous source-query branches carry independent bits and no shared IDs or positional features. Across five seeds, one-layer GROOT obtains 1.000 query accuracy at K={4,16,32,64}; the strongest virtual-node control obtains 0.659 at K=4 and at most 0.576 at K>=16. No control has nonzero whole-set exact recovery at K>=16. This is evidence on a constructed task, not a general proof that GROOT removes over-squashing.

For a real-task sensitivity diagnostic, we computed Jacobians for 300 source-target pairs, including 297 pairs at graph distance >=8, evaluated across four independently trained BattLeDIM checkpoints on the 2018 validation split. Mean absolute distant-pair sensitivity is 0.02782 +/- 0.00250 for GROOT, 0.02726 +/- 0.00338 for Virtual-GINE, and zero for four-layer GCN. GROOT therefore has measurable distant dependence, but not a demonstrated sensitivity advantage over Virtual-GINE. We retain attenuation as a limitation.

We also ran a five-seed TreeFilter-V2-style mechanism control on BattLeDIM: GROOT has 0.11832 +/- 0.01328 m frozen-test MAE versus 0.45322 +/- 0.17160 m for the control. This is not official LTF-V2: the published image code's 2-D tree builder and CUDA interface are not a native sparse-graph baseline. The adaptation changes symmetric guide-dependent gates and removes non-tree correction together, so it is a bundle-level comparison, not a causal attribution. We completed five-seed code-derived SGFormer runs on BattLeDIM, SimBench, and GasLib, and official GraphGPS GatedGCN on GasLib. We reused the pinned official SGFormer two-layer TransConv/GCN propagation (one head, alpha=0.5, graph_weight=0.8, whole-graph Frobenius normalization) with task-specific regression wrappers. Runs use seeds [0,17,42,123,2027], fixed task splits, validation-selected checkpoints, a 1,000-epoch cap, and one frozen-test read. SGFormer consumes node features and graph topology but not edge attributes. BattLeDIM MAE is 0.11832 +/- 0.01328 m for GROOT and 0.52515 +/- 0.03039 m for SGFormer; SimBench voltage-magnitude MAE is 1.42037e-5 +/- 6.36908e-7 for GROOT and 0.00219145 +/- 0.00002640 for SGFormer. GasLib unobserved NRMSE is 0.1427 +/- 0.0101 for GROOT, versus 0.2247 +/- 0.0692 for SGFormer and 1.2066 +/- 0.0488 for GatedGCN. SimBench still lacks vanilla GCN/APPNP; PROTEINS has only GCN/GIN. We narrow these claims and do not present APPNP as an evaluated result. Our London experiments already include the hierarchical IM-MPNN. Additional rewiring methods have not been directly evaluated. Forest retraining with BFS/DFS/MST is five-seed evidence on SimBench only. BattLeDIM inference-forest perturbations use frozen checkpoints and validation data, not retraining. We will keep the prose focused on these patterns and move detailed values to tables.

I thank the authors for their rebuttal. The original novelty concern remains, and the new acknowledgment of the LTF kernel equivalence arguably makes it more important. I am therefore maintaining my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.