acceptodds
Under review as a conference paper at ICLR 2027

Tree Residual Network: Restoring Graph Connectivity over a Tree Backbone

Abstract

Graph node classification requires both local connectivity and long-range context. Message-passing networks preserve graph edges but require repeated aggregation to communicate over long distances, whereas dense global attention is expensive. We propose Tree Residual Network (TRN), a cycle-completion architecture that assigns global transport to a tree and restores the constraints of omitted edges through the same routing coordinate system. Bidirectional aggregation over a spanning tree establishes graph-wide context with a linear-size backbone. Because a tree can turn one-hop relations into long detours, TRN measures signed discrepancies on omitted edges and redistributes the resulting corrections through the backbone rather than opening a second residual propagation channel. Complementary theoretical analyses, including a signed-pair reference model and a quadratic graph-smoothing surrogate, provide operator-level perspectives on this tree-to-graph correction. Across 14 homophilic and heterophilic node-classification benchmarks, TRN attains the highest or second-highest reported mean on every dataset; controlled ablations and a matched residual-aggregation control support the proposed decomposition.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural networks, Graph Connectivity Restoration, Node Classification

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_WqDxOpenReview ↗
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 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→vM_{u\to 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=1K=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.

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 LL-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.

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

This paper introduces the Tree Residual Network (TRN), a node-classification architecture that equips graph neural networks with both global context and local fidelity. The key idea behind TRN is to separate transport from constraint restoration: it first performs bidirectional (bottom-up and top-down) aggregation over a rooted spanning tree, enabling information exchange between any pair of nodes through a linear-size backbone while avoiding the deep stacking that causes over-smoothing and over-squashing in conventional message-passing networks. Furthermore, the authors provide theoretical support for the proposed "cycle-completion" design through complementary analyses, including a signed-pair analysis and a quadratic graph-smoothing surrogate. Experiments on 14 homophilic and heterophilic benchmarks show that TRN achieves strong performance in most cases, and ablation studies confirm the meaningful contributions of global tree routing, residual correction, and local readout.

Critical strengths
  1. TRN effectively separates transport from constraint restoration, building on an insightful observation: every non-tree edge closes one fundamental cycle with its tree path, allowing residual edges index the cycle-space information absent from the tree. Moreover, theoretical analyses provide direct justification for the design choices. Proposition 3.1 shows a single bidirectional tree aggregation step yields non-zero sensitivity between any node pair; Proposition 4.1 gives an exact tree-to-graph correction identity and provides a finite-iteration certificate.
  2. The proposed method offers Transformer-like receptive fields without the computational overhead of dense attention. A single bidirectional route gives graph-wide reachability, making the method computationally efficient and scalable. The runtime and memory analyses in the appendix further support these efficiency claims.
  3. Experiments on 14 homophilic and heterophilic benchmarks show that TRN achieves strong performance in most cases. The ablation studies further confirm the meaningful contributions of global tree routing, residual correction, and local readout. In addition, K×αK \times \alpha sensitivity maps reveal broad high-performing regions rather than relying on a carefully tuned configuration.
Critical weaknesses
  1. Although Proposition 3.1 establishes nonzero sensitivity between any two nodes, it does not guarantee that meaningful information can be preserved after repeated transformations, gates, and distance-dependent decay. Moreover, the experimental evaluation does not directly measure long-range information preservation or the alleviation of over-squashing.
  2. The experimental results do not convincingly demonstrate the effectiveness of the proposed method and its key components. Specifically, the best configurations on Wisconsin and Actor use K=0K=0, meaning that the proposed residual correction is disabled. Furthermore, the best configurations on Computer and Chameleon use α=0\alpha=0, reducing the predictions to a simple neighborhood average.
Questions for authors
  1. What quantitative or empirical evidence supports the claim that long-range dependency is established, rather than merely establishing theoretical analyses?
  2. The best configurations on Wisconsin and Actor use K=0K=0, and those on Computer and Chameleon use α=0\alpha=0. How do the authors interpret these findings in light of the claimed importance of residual correction and residual aggregation? Under what graph characteristics or conditions are these two components more beneficial?
3 comments

Thank you for your time and help. Below is our response to your comments.


1. Global context and local connectivity. TRN combines graph-wide tree routing with residual-edge correction for node classification. Proposition 3.1 formalizes global reachability along non-degenerate tree paths with routing gates held fixed. As with graph Transformers, global connectivity is an architectural mechanism for combining global context with local information. Proposition 3.1 characterizes structural reachability; classification results, ablations, and the measured efficiency comparison in Appendix H evaluate its practical utility.


2. K=0K=0 and α=0\alpha=0. Wisconsin and Actor use K=0K=0, α=1\alpha=1, so their selected configurations perform tree aggregation followed by classification. The correction module is evaluated through the ablations below. At α=0\alpha=0, however, the readout averages F(K)F^{(K)}, not raw features. Computer (K=2K=2) and Chameleon (K=1K=1) therefore retain tree routing and residual correction (Section 4.3; Appendix E).


3. Component evidence. Removing correction reduces Cornell accuracy from 84.3% to 78.8%. On Photo, the full model reaches 97.0% versus 93.7% for tree-only routing, supporting correction and local readout together. Appendix L additionally reports 84.32±3.15% for TRN versus 70.54±5.33% for direct gated residual aggregation on Cornell.

In the Cora removal study, using the original dataset/configuration and deleting residual edges before training, 100/75/50/25/0% retention gives three-run means of 88.21/88.18/87.60/87.18/86.13% (Section 5.2). Complete removal loses 2.08 points relative to this study's own control. Together, these experiments support residual correction; KK and α\alpha are selected on the validation set for each dataset.


We have incorporated these revisions into the manuscript. Thank you again for your helpful suggestions and valuable insights.

Reviewer_EhirOpenReview ↗

Response to Authors from Reviewer Ehir

Thanks for the clarifications and additional experiments. The new results provide meaningful evidence for the effectiveness of residual correction. However, my primary concern regarding long-range information preservation remains unresolved, echoing a similar concern raised by Reviewer WqDx (see Blind spot). Proposition 3.1 establishes structural reachability under non-degenerate path transitions, but does not demonstrate that meaningful long-range information can be preserved. In particular, neither global connectivity nor structural reachability necessarily implies long-range information preservation. Moreover, the reported classification results and ablation studies do not directly evaluate this aspect.

In addition, although the additional ablations support the effectiveness of residual correction, the authors do not sufficiently clarify the graph characteristics under which residual correction and residual aggregation are beneficial.

Thank you for your time and help. Below is our response to your comments.


1. Global reachability and information preservation. We agree that global reachability does not by itself guarantee meaningful long-range information preservation. Proposition 3.1 establishes a complementary architectural property: under non-degenerate path transitions, one bidirectional tree route provides a graph-wide receptive field beyond the depth-limited neighborhood of local message passing. TRN combines this access to global context with residual-edge correction to exploit local connectivity. Proposition 3.1 characterizes the routing capability, while Proposition 4.1 explains the correction mechanism through a quadratic surrogate.

Our classification results and ablations support the practical value of this combined design, although they do not directly measure long-range information preservation. TRN has demonstrated strong competitive performance against both conventional local message-passing GNNs and graph Transformers on node classification. Time permitting, we will also seek to evaluate TRN on long-range dependency benchmarks to address this question more directly.


2. Graph characteristics relevant to correction and aggregation. The key considerations are the connectivity omitted by the tree and the information carried by its endpoints. In the quadratic surrogate of Proposition 4.1, omitted-edge discrepancies CRHTC_RH_T determine the correction, which vanishes exactly when CRHT=0C_RH_T=0. Appendix A.6 connects the structural mismatch to regularized tree resistance and the tree detours associated with omitted edges. These analyses motivate examining both residual discrepancies and tree–residual mismatch, rather than homophily alone.

Direct residual aggregation can help when omitted neighbors supply compatible predictive information. Residual correction instead adjusts the existing tree representation using endpoint discrepancies and redistributes those adjustments through the tree. This distinction suggests why their relative benefits depend on both graph structure and node representations. In Appendix L, TRN and TRN-GRA are nearly tied on PubMed (89.86 vs. 89.85), while TRN performs substantially better on Cornell (84.32 vs. 70.54). These results support discrepancy-based correction without implying a universal performance ordering based solely on graph topology.


We hope this clarifies the respective roles of global routing and residual correction, and sincerely appreciate your constructive feedback and positive assessment of our work.

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

This paper proposes the Tree Residual Network (TRN) for semi-supervised node classification, aiming to capture both global long-range context and local graph connectivity in linear time with respect to graph size. The core idea is a cycle-completion decomposition over a single precomputed shallow-BFS spanning tree. TRN first establishes graph-wide context via one bottom-up and one top-down message-passing pass over the rooted spanning tree, using gates conditional on endpoints, symmetric degree normalization, and exponential distance decay; because omitting non-tree edges may distort one-hop graph relations into long detours, TRN treats omitted edges as diagnostic constraint channels.

Critical strengths

S1: The paper introduces a structure decomposition for graph representation learning: using a single rooted spanning tree as a linear-size (O((K+1)md2)O((K+1)md^2)) global transport backbone while using omitted non-tree edges as diagnostic constraint channels that inject signed discrepancies back into the same fixed-gate tree router. It is clearly motivated and offers theoretical justification that tries to help us understand the proposed method. It offers a memory-efficient alternative to dense Graph Transformers and multi-tree sampling frameworks.

Critical weaknesses

W1: The theory may be considered a "motivation" for the proposed method, but it does not clearly explain the effectiveness of the learning algorithm. The actual residual update in Eqs. (7) and (9) are quite different from the reference model in Proposition 4.1 and Appendix A.2. Specifically, Eq. (7) uses asymmetric directional gates gR(Fv(k−1),Fu(k−1))g_R(F_v^{(k-1)}, F_u^{(k-1)}) and an asymmetric transformation term (Fv(k−1)WT−Fu(k−1)F_v^{(k-1)}W_T - F_u^{(k-1)}), which neither vanishes for identical endpoint states (Fu=Fv=c  ⟹  c(WT−I)≠0F_u = F_v = c \implies c(W_T - I) \neq 0) nor produces balanced signed pairs (δ,−δ)(\delta, -\delta) required for cancellation. Moreover, iterating Eq. (9) (F(k)=F(k−1)+Tθfix(C(k);T)F^{(k)} = F^{(k-1)} + T_\theta^{\text{fix}}(C^{(k)}; T)) lacks the fidelity term A−1X−H(k)A^{-1}X - H^{(k)} and step size η\eta required by the convergent Richardson-style iteration in Proposition 4.1. W2: The claim of ranking best or second-best on all 14 benchmarks is established against an incomplete comparison set: the tuned GCN*/GAT*/GraphSAGE* variants from the NeurIPS2024 paper exceed TRN's reported means on at least four datasets, and the vanilla GCN in the author's paper is several points higher than that in the NeurIPS2024 paper on several datasets (e.g. Cora), such that I can not see a fair comparison between your method and the baselines.

Reference: Luo et al. Classic GNNs are strong baselines: Reassessing gnns for node classification. NeurIPS2024.

Questions for authors
  1. How much of a gap can you fill between theory and practice?
  2. Can you provide additional experiments that support the performance superiority of your methods over the *variants?
5 comments

Thank you for your time and help. Below is our response to your comments.


1. Theory and the learned update. Proposition 4.1 analyzes the quadratic surrogate; exact cancellation and energy identities apply to their stated reference settings, since learned directional gates and transformations need not preserve them. Its central contribution is to explain how a fixed tree can support full-graph smoothing through residual correction. For fixed graph operators, CRHTC_RH_T determines the entire correction HG−HTH_G-H_T; for τ>0\tau>0, HG=HTH_G=H_T exactly when CRHT=0C_RH_T=0. The proposition identifies the correction space and bounds the tree-only error and its reduction under the prescribed iteration. This gives an optimization interpretation of TRN's discrepancy-and-tree-rerouting design. Section 4.4 and Appendix A.7 explain this connection.


2. Evidence for residual correction. Removing correction reduces Cornell accuracy from 84.3% to 78.8%. Against direct gated residual aggregation (TRN-GRA), TRN obtains 84.32±3.15% versus 70.54±5.33% on Cornell and 97.00±0.12% versus 96.47±0.17% on Photo; PubMed means are nearly identical (Appendix L). These results support the effectiveness of the complete residual-correction design.

The Cora residual-edge removal study uses the original dataset/configuration and removes edges before training. At 100/75/50/25/0% retention, three-run means are 88.21/88.18/87.60/87.18/86.13%. The 2.08-point drop uses this study's own full-retention control (Section 5.2).


3. Strong classical baselines. We expanded Tables 1–2 with tuned GCN*, GAT*, and GraphSAGE* results on our data splits and published reference results from Luo et al. The tables below cover all 14 datasets, showing the highest mean among these three baselines for each dataset. Our supplementary GNN results use three runs; TRN retains its original ten-run results. Values are percentages; Tolokers and Questions use ROC-AUC, the others accuracy.

Our supplementary runs on the TRN splits (three-run mean ± standard deviation).

DatasetStrongest tuned GNNTRN
CoraGCN*: 87.74 ± 1.6688.89 ± 0.87
CiteSeerGCN*: 76.83 ± 1.9478.40 ± 0.95
PubMedGraphSAGE*: 89.49 ± 0.2989.86 ± 0.36
TexasGraphSAGE*: 82.98 ± 5.8988.11 ± 5.43
WisconsinGraphSAGE*: 84.96 ± 5.8391.76 ± 2.88
CornellGraphSAGE*: 79.07 ± 4.7684.32 ± 3.15
ActorGraphSAGE*: 35.86 ± 1.0638.34 ± 1.12
TolokersGAT*: 83.78 ± 0.4383.82 ± 0.69

Published GNN results from Luo et al.

DatasetStrongest published starred GNNTRN
ComputerGAT*: 94.09 ± 0.3793.56 ± 0.13
PhotoGraphSAGE*: 96.78 ± 0.2397.00 ± 0.12
CSGraphSAGE*: 96.38 ± 0.1196.01 ± 0.08
PhysicsGCN*: 97.46 ± 0.1097.70 ± 0.05
ChameleonGCN*: 46.29 ± 3.4045.43 ± 2.73
QuestionsGCN*: 79.02 ± 0.6078.62 ± 0.82

TRN has higher mean accuracy on the seven datasets in our supplementary comparison and comparable ROC-AUC on Tolokers. Among the published reference results, the strongest GNNs lead on Computer, CS, Chameleon, and Questions, while TRN leads on Photo and Physics. The revised rankings and summary claims reflect this broader comparison.

The citation accuracy discrepancy also involves different training splits: Luo et al.'s scripts use 20 training nodes per class, whereas ours use 50%/25%/25% (140 versus 1,354 training nodes on Cora). Our supplementary runs address this difference by evaluating the tuned baselines on the TRN splits.


We have incorporated these revisions into the manuscript. Thank you again for your helpful suggestions and valuable insights.

Area_Chair_WTXcOpenReview ↗

Experimental results

I would like to highlight MLP benchmarking results from another paper [1]:

DatasetStrongest tuned GNNTRNMLP
CoraGCN*: 87.74 ± 1.6688.89 ± 0.8776.44 ± 0.30
CiteSeerGCN*: 76.83 ± 1.9478.40 ± 0.9576.25 ± 0.28
PubMedGraphSAGE*: 89.49 ± 0.2989.86 ± 0.3686.43 ± 0.13
TexasGraphSAGE*: 82.98 ± 5.8988.11 ± 5.4392.26 ± 0.71
WisconsinGraphSAGE*: 84.96 ± 5.8391.76 ± 2.8893.87 ± 3.33
CornellGraphSAGE*: 79.07 ± 4.7684.32 ± 3.1591.30 ± 0.70
ActorGraphSAGE*: 35.86 ± 1.0638.34 ± 1.1238.58 ± 0.25
TolokersGAT*: 83.78 ± 0.4383.82 ± 0.6974.58 ± 0.75
ChameleonGCN*: 46.29 ± 3.4045.43 ± 2.7346.72 ± 0.46
QuestionsGCN*: 79.02 ± 0.6078.62 ± 0.8269.97 ± 1.16

Looking at those numbers, a simple two-layer MLP ourperforms anything on several of the datasets provided. I would encourage to use other datasets instead, there is no reason to still use the legacy heterophilic datasets Texas, Wisconsin, etc. "tolokers" and others are a reasonable alternative.

[1] Luan, Sitao, et al. "Re-evaluating the advancements of heterophilic graph learning." New Perspectives in Graph Machine Learning. 2024.

Thank you for your time and help. Below is our response to your comments.

We agree and have added Squirrel-filtered, Roman-empire, and Amazon-ratings to broaden the evaluation beyond the small legacy datasets.

One clarification: our Chameleon result of 45.43 ± 2.73 is on Chameleon-filtered (Appendix B), whose MLP result in [1] is 38.06 ± 3.98; 46.72 ± 0.46 refers to the original Chameleon. The filtered versions address the duplicate-node leakage identified by Platonov et al. [2].

The expanded results, including the original Chameleon and Squirrel for completeness, are now in Appendix N, Table 11. Once the remaining baselines are complete, these benchmarks will replace selected legacy datasets in Table 2. MLP and GCN results come from [1]. TRN reports three-run means ± standard deviations for the five new experiments and retains ten-run results for Chameleon-filtered, Tolokers, and Questions. Metrics are ROC-AUC for Tolokers/Questions and accuracy otherwise (%).

DatasetTRNMLP [1]GCN [1]
Chameleon-filtered45.43 ± 2.7338.06 ± 3.9841.46 ± 3.42
Squirrel-filtered43.14 ± 1.1138.30 ± 1.2237.33 ± 1.88
Roman-empire80.24 ± 0.6966.04 ± 0.7148.92 ± 0.46
Amazon-ratings53.56 ± 0.4749.55 ± 0.8150.05 ± 0.67
Tolokers83.82 ± 0.6974.58 ± 0.7577.44 ± 1.32
Questions78.62 ± 0.8269.97 ± 1.1672.72 ± 1.93
Chameleon69.76 ± 1.1646.72 ± 0.4664.18 ± 2.62
Squirrel54.43 ± 0.9231.28 ± 0.2744.76 ± 1.39

TRN has higher reported means than MLP and GCN on all six filtered/newer benchmarks. While MLP performs strongly on some small legacy datasets, this does not negate the value of TRN: the expanded results support its ability to exploit graph structure beyond node features alone. These results broaden the empirical support for TRN’s combination of graph-wide tree routing and residual-edge correction beyond the legacy benchmarks.

Thank you again for your helpful feedback. We have incorporated these revisions into the manuscript.

[1] Luan et al., “Re-evaluating the Advancements of Heterophilic Graph Learning.”, New Perspectives in Graph Machine Learning. 2024.

[2] Platonov et al., “A critical look at the evaluation of GNNs under heterophily: Are we really making progress?”, ICLR 2023.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.