- 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
-
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.
-
The implementation work is substantial using CUDA.
-
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.
-
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.
- 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.
-
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.
-
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.
-
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".
-
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.
-
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.
- 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.
- 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
- 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?
- 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?
- How much influence actually reaches distant nodes in trained models, given that gate products shrink along long paths?
- How sensitive are the main results to the choice of forest (BFS, DFS, MST, different seeds) beyond SimBench?
- 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
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
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.
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.