- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The article introduces a model for node classification, called Tree Residual Network (TRN). The main idea is to first sample a spanning tree which is used as a backbone for information propagation. This is achieved by a bottom-up and top-down pass on the rooted tree, requiring linear effort. Subsequently, the set of omitted edges is used to correct for the missing local connectivity by propagating corrections through the tree in an iterative manner. In an experimental section, the authors compare their method on a multitude of benchmark datasets (both homophilic and heterophilic), showing TRN slightly outperforming all competitors in most cases.
Critical strengths
- The method is slim and provably fast
- The experimental evaluation is quite broad
- The authors provide a range of additional results and details in the supplementary.
Critical weaknesses
- Insufficient comparison to the most closely related work: The approach seems very similar to FGL (Li et al., 2026). While the authors mention this competitor in related work, they compare to it only on three datasets in the appendix. This is also where some differences between the two are pointed out. Since FGL is arguably the most related paper, this is not sufficient. I believe it needs to be discussed in significantly more depth, including a more detailed related work discussion and comparison on all datasets.
- Unclear presentation makes the method difficult to follow:
- The structure of the paper is at times unclear and thus hard to follow. For instance, the preliminary section seems to introduce part of the method and even results in section 3.2. On a lesser note, in section 4.2, the description of the method is interrupted by the "Residual-energy interpretation" paragraph, such that Eq. 9 appears to belong to that paragraph.
- The terminology is sometimes unclear. For instance, the authors interchangeably use "routing coordinate system", "backbone", and "router" for spanning tree.
- Some parts of the paper feel disconnected, such as the paragraph "Connectivity gap after tree routing" which is barely discussed and introduces notations which are largely not used later on.
- Blind spot: While the abstract motivates the method by the need for long-range capability, this seems to be never tested experimentally.
Questions for authors
- Is the reason for the separation of the method description into preliminaries (section 3) and main section (section 4) due to the tree aggregator not being novel? If so, the authors should state where it was taken from.
- Why were FGL results not integrated into the main tables 1 and 2?
- Can you elaborate on where the performance results of competitor methods come from? E.g. for classic methods like GCN, GAT and GraphSAGE, Luo et al. (2024) reports higher numbers.
- Concerning proposition 3. I wasn't sure what the main message of this result is. Do the authors compare a MPNN with limited reach to their tree aggregation that has maximal reach?
- What do the authors mean by "rather than opening a second residual propagation channel" in the abstract? Do the authors compare to such an approach somewhere?
3 comments
Thank you for the response and for addressing my points. I believe the structure is clearer now and I appreciate the transparency about the relation to FGL.
That said, the clarifications make the close relationship to FGL more apparent, which somewhat narrows the scope of the contribution. In addition, TRN seems to perform similarly to the FGL reimplementation, which itself scores lower than the published FGL results. So empirically TRN seems to be rather on par with FGL.
If time allows, I am curious about one more thing. Since the tree aggregator is adopted from FGL, is Prop. 3.1 also taken from FGL or is it a new result?
Thank you for your follow-up and for acknowledging the improvements to the manuscript. We address your remaining concerns below.
1. Relation of Proposition 3.1 to FGL. Proposition 3.1 is our formulation of a reachability property of the adopted tree aggregator, not a new global-aggregation principle. FGL's Theorem 1 derives the bottom-up/top-down recursions for global tree aggregation. Our statement makes the corresponding pathwise sensitivity explicit under fixed gates and non-degenerate transitions, and contrasts it with the finite-hop receptive field of an -layer local MPNN. We include its proof for completeness; the global reachability underlying this statement is already inherent in FGL's aggregator. Its role is to establish the architectural starting point for residual correction, rather than serve as a standalone novelty claim.
2. What TRN adds. The distinction lies in how omitted connectivity is handled. FGL emphasizes constructing and combining informative tree views through homophily-guided sampling and forest fusion. TRN instead uses omitted edges to generate endpoint discrepancies and redistributes these corrections through one fixed tree. This provides an alternative to relying on multiple sampled trees and the associated preprocessing pipeline. Proposition 4.1 explains this design through a quadratic surrogate: omitted-edge discrepancies determine the correction from tree-only to full-graph smoothing. The controlled ablations directly support the added mechanism—for example, removing correction lowers Cornell accuracy from 84.3% to 78.8%—and Appendix J shows robustness across the tested tree choices.
3. Interpreting the FGL comparison. We agree that our reimplementation should not be treated as FGL's performance ceiling. FGL's official code is available, but the current release does not yet provide all the components needed to run the method and reproduce the published results. For the comparison, we therefore used our implementation based on the paper and evaluated it on the same splits as TRN. Table 3 compares both methods on the same splits: TRN has higher reported means on nine of ten datasets and is essentially tied on Computer. Appendix K separately reports published FGL results, which favor FGL on Texas and TRN on Wisconsin and Cornell. These published results use a different experimental pipeline and therefore do not establish a controlled ranking. Our central empirical point is that TRN achieves competitive performance with a single fixed-tree correction design; its contribution does not depend on claiming universal accuracy superiority over FGL.
We hope this clarifies both the provenance of Proposition 3.1 and the contribution of TRN. We would be grateful if you could consider revising your score in light of these clarifications and the additional evidence.
Thank you for your time and help. Below is our response to your comments.
1. FGL and our contribution. Sections 3.2 and 4.1 attribute the tree aggregation backbone to FGL. The distinction is the modeling focus: FGL constructs and combines informative tree views through homophily-aware sampling and forest fusion; TRN corrects connectivity omitted by a fixed tree. Residual edges supply discrepancies, and the same tree router redistributes them with fixed gates. Both methods incorporate local information. Our contribution is the residual-correction mechanism, which enables a single-tree design without FGL's augmentation, homophily-estimator training, and multi-tree fusion pipeline. Appendix K explains this distinction; Proposition 4.1 supplies its quadratic-surrogate interpretation.
Appendix J evaluates shallow-BFS, random-BFS, random-Wilson, and similarity-Wilson trees without retuning. Mean accuracies span 88.17–88.89% on Cora, 78.16–78.40% on CiteSeer, and 89.84–89.95% on PubMed, supporting robustness across the tested trees.
A directly runnable official FGL implementation was unavailable to us at experimentation time. Our reimplementation includes pseudo-label/top-k augmentation, homophily scoring, weighted Wilson sampling, tree aggregation, and fusion with local correction; trees were independently resampled per run. Table 3 compares it on the same splits as TRN: TRN has higher means on nine of ten datasets and is nearly tied on Computer (93.56±0.13% versus 93.57±0.45%). Appendix K separately reports the published FGL results.
2. Organization and notation. Sections 4.1–4.3 now present initial aggregation, residual correction, re-routing, and readout consecutively, followed by analysis in Section 4.4. Section 3.2 defines the directional messages; Mu→v denotes either transmission direction. We replaced “routing coordinate system” with “tree backbone” or “tree-routing operator.”
3. Classical baselines. We added tuned GCN*, GAT*, and GraphSAGE* experiments on the TRN splits, reporting three-run means±standard deviations in Tables 1–2. TRN has higher mean accuracy than the strongest of these baselines on Cora, CiteSeer, PubMed, Texas, Wisconsin, Cornell, and Actor. On Tolokers, performance is comparable: 83.82±0.69% for TRN versus 83.78±0.43% for GAT*.
For the remaining six datasets, we included Luo et al.'s published results, completing the comparison across all 14 datasets. These stronger baselines outperform TRN on four datasets, and our revised conclusions emphasize competitive performance. The supplementary citation runs also resolve a protocol difference: Luo et al.'s scripts use 20 training nodes per class, while ours use a 50% training split.
4. Global reachability and efficiency. Proposition 3.1 establishes graph-wide reachability along non-degenerate tree paths with fixed gates. As with graph Transformer architectures, TRN uses global connectivity to complement local information for node classification. Alongside competitive classification results, Appendix H reports PubMed training/inference times of 0.0196/0.0046 seconds for TRN, 0.4786/0.1374 for GraphGPS, and 0.0727/0.0298 for Exphormer (hidden dimension 128; TRN K=1).
5. Residual aggregation. “Separate residual channel” referred to direct neighbor aggregation over omitted edges. TRN forms discrepancies and re-routes them through its tree. Appendix L compares these designs: Cornell accuracy is 84.32±3.15% for TRN versus 70.54±5.33% for TRN-GRA; PubMed means are nearly identical. These results support the effectiveness of the complete residual-correction design.
We have incorporated these revisions into the manuscript. Thank you again for your helpful suggestions and valuable insights.