Forest-Based Graph Learning for Semi-Supervised Node Classification
Authors: Jin Li
Shenghao Gao
Kaichen Zhang
Xinlong Chen
Ying Sun
Hui Xiong
Venue: ICLR 2026 Poster (2026)
Keywords: Graph neural networks
Graph learning
Node classifications
Primary area: learning on graphs and other geometries & topologies

Abstract: Existing Graph Neural Networks usually learn long-distance knowledge via stacked layers or global attention, but struggle to balance cost-effectiveness and global receptive field. In this work, we break the dilemma by proposing a novel forest-based graph learning (FGL) paradigm that enables efficient long-range information propagation. Our key insight is to reinterpret message passing on a graph as transportation over spanning trees that naturally facilitates long-range knowledge aggregation, where several trees--a forest--can capture complementary topological pathways. Theoretically, we demonstrate that as edge-homophily estimates improve, the induced distribution biases towards higher-homophily trees, which enables generating a high-quality forest by refining a homophily estimator. Furthermore, we propose a linear-time tree aggregator that realizes quadratic node-pair interactions. Empirically, our framework achieves comparable results against state-of-the-art counterparts on semi-supervised node classification tasks while remaining efficient. Codes are available at \url{https://anonymous.4open.science/r/FGL/}.

Published as a conference paper at ICLR 2026
FOREST-BASED GRAPH LEARNING FOR SEMI- SUPERVIEER NODE CLASSIFICATION
Jin Li', Shenghao Gao', Kaichen Zhang', Xinlong Chen', Ying Sun",, Hui Xiong!.
'Thrust of Artificial Intelligence. The Hong Kong University of Science and Technology (Guangzhou) "College of Computer and Data Science, Fuzhou University
'The Hong Kong University of Science and Technology (Hong Kong SAR) jslijin201 58out com, gaoshenghao51 2 com kzhangbi&comas ust. hk, fixinlonge gmanl com yingsehkust-pg edu.ce en, xionghui @ust. hk
ABSTRACT
Existing Graph Neural Networks usually learn long-distance knowledge via stacked layers or global attention, but struggle to balance cost-effectiveness and global re- ceptive field. In this work, break the dilemmaa by proposing novel forest-bar based graph learning (FGL) paradigm that enables efficient long-range information propa- gation. Our key insight over spanning trees that naturally facilitates long-range knowledge aggregation, where several trees-a forest-can capture complementary topological pathways. Theoretically, we demonstrate that as edge-homophily estimates improve, the induced distribution biases towards higher-homophily trees, which enables gen- erating high-quality forest by refining a homophily estimator. Furthermore, we propose a linear-time tree aggregator that realizes quadratic node-pair interactions. Empirically, our framework achieves comparable results against state-of-the-art counterparts on semi-supervised node classification tasks while remaining efficient. Codes are available at httts::///// anonymous 4open. science/:/Eiii
reinterpret message passing on a graph transportation
INTRODUCTION
Graph Neural Networks (GNNs) (Wu et al. 2020
Chen et al. 2020b Thomas et al. 2022) attract
much attention in recent years due to their expressivity in sol solving varous graph-related tasks (e.g..
node and graph classifications (Feng et al. 2020 Xie et al. 2022) or clustering Bianchi et al. 2020))
link prediction (Yun et al.) 1), and anomaly detections (Dong et al. 2025 Gong al. 2023)
with also many applications in, e.g., texts (Wang et al.) 2024b), images (Nazir et al. 202 1 Guan
al. (2022), generation (Zhuang et al. 2025 Gong & Sun 2025), traffic (Jiang & Luo 2022). and
other domains (Gong & Sun 2024 Cui et al. 2026). Despite their popularity and successes, most GNNs restrict receptive fields 2-/3-hop local neighborhoods and focus on nearby information aggregation while ignoring distant knowledge, which would limit their
application scopes when dealing with challenging tasks where long-range interactions are critical and necessary. For example, as discussed in Sec. [ the imbalance of densities or degrees often causes insufficient local knowledge for some nodes, which becomes more severe under graph heterophily and risks further over-fitness from label scarcity. In this paper, we focus on semi-supervised node classifications to underscore labeling challenges.
To facilitate long-distance interactions, existing works have devoted much effort and can be generally categorized into two different architectures: (1) Deep local models (e.g., deep GNNs (Chen et al.)
2022c Li et al.) 2019 Chen et al.) 2020al) ) expand the global receptive fields by stacking multiple local layers, with each considering only first-order information. (2) Shallow global models (e.g.,
Global Graph Transformers (Ying et al. 2021; Kreuzer et al.] 202Th) integrate or 2 non-local
aggregating operators (e.g., global attentions), encapsulating all pairwise node interactions in single layer. Unfortunately, most of them suffer from high time and space complexities (Li et al. 2021 Wu
* Corresponding authors: Ying Sun (yingsunnconnecc. hkust- seeettggggeuuu..... edu. cn) and Hui Xiong
thuixi ongeunst.t.t......m............. hk).

---

Published as a conference paper at ICLR 2026
et al. 2022), due to excessive unparallelizable layers (former) quadratic node-pair interactions (latter). Recently, few prior works attempt to mitigate complexities via some sparsity techniques such Adaptive Selection (Chen al. [022b Wu et al. 2022) and Graph Rewiring (Shirzad et al.) 2023). Yet, they sacrifice global coverage and have to make selections, and thus either risk dropping some important node interactions heavily rely on extra sophisticated selection strategies. Overall, such methods fail to simultaneously address comprehensive long-range knowledge extraction and cost-effectiveness, which rooted in the inherent limitation of existing learning paradigms.
Such a graph learning dilemma urges us to rethink existing paradigms and explore an alternative that breaks the unavoidable trade-off between cost-effectiveness and a global receptive field. The essential observation is that these paradigms view graph as a fusion of structures, whose total costs can be calculated as follows:
Total cost (cost per structure) (number of structures).
Thus, when modeling with local primitives first-order neighborhoods (Li et al. 2019) short random walks (Zhang et al. 2020) the per-structure cost is low, but numerous such struc- tures are required for covering long distances. In contrast, global operators (Ying al. 2021) can reduce the number of structures, yet at the expense of prohibitive per-structure cost due to dense pairwise interactions. Based on the above analysis, we naturally raise question: Does there exist structure that simultaneously controls these two factors? To answer this question, we recognize that a spanning tree is the minimal subgraph connecting all nodes. Therefore, under limited structure counts, such a tree is the simplest structure that achieves global coverage (Fig. D indicating that may be more suitable for long-range propagation. Furthermore, we suggest using forest (tree set), since single spanning tree may be insufficient to capture all topological knowledge.
In this paper, we propose forest-based graph learning (FGL), a novel paradigm that models information propagation on a graph as transport on forest of spanning trees, economically achieving global cov- erage. To obtain a high-quality forest, we expect to sample the trees from distribution biased towards homophilous trees. Theoretically, we demonstrate that as edge-homophily estimates improve, the in- duced tree distribution asymptotically approaches the ideal one. Accordingly, we propose tree sampler, based on a well-trained edge-homophily estimator, to enable generating several spanning trees with higher homophily via the weighted Wilson algorithm (Wil)
M
Our paradigm (right) utilizes the most sparse structures of graph, i.e., span- ning trees, to aggregate global messages against the prior paradigms (left).
Figure 1:
son 1996). Besides, we design a general tree aggre- gator by deriving two recursions on trees, which propagates global messages in linear running time. Additionally, a post-hoc mean operator is adopted as our tree fuser to merge knowledge from different trees. These components constitute full framework, illustrated in Fig.
Our contributions are summarized as follows: New Paradigm: We introduce a forest-based graph learning paradigm FGL, which can comprchensively capture long-range knowledge with high efficiency. 2. Theoretical Insight: We establish a rigorous asymptotic relationship between the accuracy of the edge-homophil estimator and the quality of the induced tree distribution, which reveals that refining the estimator provably yields a better tree distribution. 3. Effective Approach: We propose 1) a homophily estimator-based tree sampler, which generates homophilous trees with higher probability; and 2) general tree aggregator that conducts quadratic pairwise node interactions with only linear complexities. 4. Experimental Results: Our framework achieves competitive results against -oe-----ttttrrtt counterparts in supervieee node classifications with higher efficiency, e.g., 11.90 1..90 and 16. 14% average relative gains against GCNII and DIFFormer (representative Deep GNN and Graph Transformer), respectively.
Here, tree aggregator is to aggregate intra-tree messages, while tree fuser merges the inter-tree messages.
2

---

Published as a conference paper at ICLR 2026
2 RELATED LITERATURE
Deep Local Models. Deep Graph Neural Networks (GNNs) expand their receptive fields by iteratively stacking local aggregators, enabling fine- grainnd control over neighborhood information at each layer Yang et al. (2020); Fang et al. (2023;; Chen et al. (020a). This depth provides strong expressiveness but comes with notable drawbacks: sequential computation limits parallelism, higher time/space complexities, and the risk of over-smoothing. To mitigate over-smoothing, various strategies have been explored, including normalization layers ZZhao & Akoglu (2020); ; Zhou al.
(2021): Yang et al. 2020), random dropping techniques|Ron et al. (2020b)) Huang et al. (2020); Fang al. (2023), and skip connections Li al. (2019): Chen al. (2020a); Luan al. 2019); Xu et al.
(2018). Despite these improvements, deep local models inherently rely on step-wise neighborhood
aggregation, which prevents efficient global message passing and parallelization.
Shallow Global Models. Graph Transformers (GTs) adopt contrasting perspective: instead of gradual local aggregation, they model direct pairwise interactions among nodes, often in just a few global layers Min al. (2022): Hussain al.
2022); Ying et al. (2021). This shallow global paradigm (G x x - VVy allows rapid global communication but typically incurs quadratic complexity. To improve scalability, recent works either sparsify interactions via sampling pruning (e.g., Gophormer ZZhao et al.j (202I), NodeFormer Wu et al.] (2022), Exphormer [Shirzad et al. (2023)), ) or simplify attention mechanisms to reduce computation (e.g. SGFormer Wu al. (2024). GOAT Kong et al. (2023)). While these strategies address efficiency, they often lose structural bias, motivating the use of positional encodings Ying et al.] (202T); Chen al.] (2022a) or walk-based formulations Zhang et al. 2020). However, designing encodings that are both expressive and efficient remains challenging.
Tradeoff Between Local and Global Models. Deep Local Models excel at capturing fine-grained neighborhood structures but struggle with scalability and long-range dependencies. In contrast, Shallow Global Models enable efficient global message propagation with fewer layers, but often overlook nuanced local structures or incur high complexity without careful approximation. Hybrid designs attempt to combine both perspectives Wu al. (2021: Rong et al. (2020a); Kreuzer et al. (202I). In contrast, we analyze the essential limitation of existing learning paradigms and propose a novel forest-based paradigm that enables efficient long-range modeling along with natural structural knowledge preservation, addressing this dilemma from a more fundamental perspective.
3 PRELIMINARY
Notations. Let G = (V, E) be an unweighted graph with n nodes V = [= and m edges E }. The graph is represented by a feature matrix X E Rgx and an adjacency matrix A E {0, (0,1)aM0 nxn, where Aij 1 if and only if (v,, uz) E. We also define the normalized adjacency
matrix A = D (A + T)D 2, where is the degree matrix of A+ I.
Problem Formulation. In semi-supervised node classification, subset of nodes V,. V has labels y: E {0, c- 1). while the remaining nodes are unlabeled. The goal is to learn node embeddings H" E RRadd such that simple linear predictor can be applied to H" to predict node labels for all
E V, leveraging both labeled and unlabeled nodes.
METHOD
Existing paradigms suffer from the trade-off between cost-effectiveness and a global receptive field. To obtain global coverage, deep local models with small local structures require stacking large number of structures, while shallow global models with large complex structures incur high per-structure computational costs. In this work, introduce an intermediate-leve structure-thn that offers principled way to balance this trade-off, exhibiting a new learning paradigm. A tree connects all nodes in graph in cost-efficient and non-redundant manner.
We build on this insight to propose the Forest-based Graph Learning (FGL) framework illustrated in Fig. 2, which is composed of four key components: (1) Pre-processing, which augments the original input graph to facilitate downstream computation; (2) Tree Sampler, which derives a target distribution spanning trees and generates multiple trees accordingly; (3) Tree Aggregator,
3

---

Published as a conference paper at ICLR 2026
Forest-based Graph L Learning
Fuser
H
IV
Pre- processing
Tree Sampler
Tree Aggregator
Tree Fuser
Step1
Step
Step III
Step
M caa
Pre-processing
III
Graph A Aummenter
Original Graph G
ugmmented
H)
Tree
H
Graph G
Aggregator
H
Define
0.7
0.8
HE
Tree Distribution
Sample
0.8
0.6
Pz(T)
Homophily
0.3
Tree
Tree Tx
Estimator
Sampler
Figure 2: Our framework contains key steps: (I) Pre-processing first augments the vanilla graph;
(II) Tree Sampler then generates multiple spanning trees from a derived distribution; (III) Tree Aggregator efficiently propagates messages (H in Eq. [] over each tree next; and (IV) Tree Fuser finally integrates the aggregated messages from all trees into unified embeddings H'
which performs message passing along each individual spanning tree; and (4) Tree Fuser, which integrates the aggregated messages from all sampled trees into a unified representation.
4.1 PRE-PROCESSING
Real-world graphs are often not connected, which hinders the subsequent spanning tree sampling process. To address this issue, we begin by computing pseudo-labed for each node, denoted as Y' E paxe, For heterophilous graphs, we employ simple feed-forward layer, Y' o oXXW) GCN layer, Y (AXW). The learnable parameters W E Rdxe are optimized on the labeled nodes using the standard cross-entropy loss. We then construct an augmented graph G by leveraging the pscudo-labels, For each node, we use its pseudo- label representation y/ lxe identify its k nearest neighbors. an edge does not already exist between the node and one of these neighbors, we introduce a new edge.
whereas for homophilous graphs,
This pre-processing step offers two key benefits at the same time. First, ensures graph connectivity, which is necessary for subsequent spanning tree sampling. Second, it increases the homophily ratio-the proportion of edges linking nodes with similar class labels whhch has been shown to improve performance in semi-supervised node classification (Chien et al. 2021).
4.2 TREE SAMPLER
To generate high-quality forest composed of several spanning trees, we identify two essential principles: 1) homophily ratios: Since we target node classification, it is critical measure on graphs and thus can be naturally transferred to trees. 2) diversity: if these trees tend to overlap, then the forest would be degraded into a single tree, which may be insufficient to cover all the topological knowledge of graph, therefore necessitating diversity.
Therefore, we expect to sample the trees independently from a distribution Pa (T) biased towards with high homophily ratios. We assume each tree T has score s(T) that can be calculated as the product of edge scores se)), thereby defining the tree distribution on graph as follows:
s(T)
HEET s(e) ΣTcâ
Pg (T)
Ercas(T) (T))
HITe s(e)
The only remaining step is to determine the edge scores s(e). Our main idea is to assign higher scores to those homophilous edges and lower scores to heterophilous edges, which intuitively improves
4

---

Published as a conference paper at ICLR 2026
Fa(y)
Sy f To S. (((H)))
H = M (S M (Haato) Sw))
Information flow: son father
Information flow: father - son
cut
Figure 3: Illustration of the tree aggregator. The red node denotes the root, and the blue node indicates the focal node. (a) Red dashed lines depict the bottom-up computation of S, while blue dashed lines represent the computation of H.. (b)(c) Detailed computations along the focal edge are shown.
the probabilities assigned to homophilous trees. We justify this intuition in Sec. 4.6 by theoretically demonstrating that this scoring strategy induce distribution biased towards higher-homophe homophily trees (Theorem[]. Therefore, we introduce a homophily estimator to find those homophilous edges and assign higher scores to them. Here, we implement this homophily estimator via local attention:
exp (Q:K3 /VC)
0i EvEN()) exp (V,)./vo)
VijeeV
where Q = XWQ. X=Wx, and V XWv with learnable Wa. WK. , Wv Rd NN, denotes the first-order neighborhood of node i V. We train the local graph attention by minimizing the cross-entropy loss with targets y'. Thus, the edge score s(e) for e = (i,j) is defined by
s(e) = (0:= + a)--s) /2. Finally, tree sampler generates Nr independent spanning trees from (T) via the algorithm of Wilson (996) in nearly O(n) time per-tree.
4.3 TREE AGGREGATOR
The tree aggregator S&gg over tree 7 with root r is defined as Skag H E Raxd + H' E R which is designed based on a general message aggregator SAgs (-). The idea is rooted in a key observation: for neighboring nodes u. V on tree T, the globally merged messages targeting them differ only at one edge direction (visualized in Fig, 33. Leveraging this observation can facilitate efficient tree propagation by any general J'agz (-) that satisfies: given two message sets A, with possible auxiliary information (e.g., weights), if merging A into B getting S, then there always exists two operators M/ (.) to make the following sufficient properties hold.
fags (S) M (fAss (B), fAsS (A)), Property (I): Combine
(4)
Sa (B) = MI (SARR (S), SayR (A)), Property (II): Disentangle
where M+/- (i. b) denote adding vector 6 to ā deleting Ō from ā which are allowed unsymmet- rical via auxiliary information. These identified properties do not sacrifice the generality of fags (-)- Indeed, many popular rego-segressive sequence models and first-order GNN aggregators can be adopted, e.g., linear attention Zhou et al. (202T); Wu et al. (2024), linear Recurrent Neural Networks
(RNNs) [ Juu et al. (2024), and State Space Models (SSMs) Sarem et al. (2024); /Zhan et al. (025):
Xiao al. 2024) as well as non-linear variants (Sec. A.6). thus highlighting its generality.
Based on these properties, we can theoretically derive a general tree aggregator ((T)) high-levelly via two recursions Theorem [ The proof and further explanation can found in Sec. B. Appn.
Theorem 1. Given tree T with root r E V, each node E V has a subtree (((sub) with nodes ((ub) V. Denote the father node and the children nodes of u on tree T as Fa (v) and Child (v). Let S, represent the aggregated message at node v from all messages from ((Sub) Then, given any message aggregator Jwee ()) satisfying Properties (I) and (II) as well as function g (-), our tree aggregator f .H + H' E Raxd can be always derived as two recursions via operators M+/-
V n EV, Su = -SeR (15+) (eChiach)))))) U Og (Hw))) Recursion (I)
(5)
5

---

Published as a conference paper at ICLR 2026
V =² (S., MM (His)o): H = Sp,
Recursion (II)
(6)
where H, H' E Raxd denote node embeddings before and after aggregation.
This theorem provides efficient way to propagate long-distance information tree: (1) First, to calculate S, for each node u E V. it suffices to collect all distant messages targeting the root once, by recursively calling fAx (-): (2) Then, apart from the root H; S,, we can calculate H1' for other nodes efficiently via the operator M followed by MM*
Implementation Despite the strong generality, still prioritize a linear variant for simplicity and ease of implementation. Specifically, adopting fagg and M as weighted sums, .M" as weighted difference, and g as a linear transformation, we implement Eq. [ and Eq. 6 follows:
VuEV, S =
Σ
(av-m WA) S, - WB H. E RR.
(EChild(u)
VVEV, H. = S. + OFFa())+v WA (Hiaa))) - ac-sPa(o) (
WA S.) Rd
(8)
where Wa E Raxd and WB E dxd are learnable matrices. The local attentions {at-s Is. (defined in Eq. 3 are utilized to enhance the impact of homophilous edges and weaken heterophilous edges.
Acceleration and Extensions Note that parallelization can be conducted both between trees and between aggregations inside single tree. For higher parallelization, can intuitively make rooted tree shallower yet wider to support many threads working together by selecting its centroid as the root. Furthermore, there exist different greedy strategies for nodes' priority for different recursions (Eq.5 and Eq. 6) to reduce the waiting time of threads. We discuss their specific implementations several potential extensions of the above tree aggregators in Sec. of Appn., which includes how to: (1) efficiently integrate global linear attention the framework similar Wu et al. (2024) and conveniently incorporate the kernel decomposition techniques (e.g., Random Feature Likhosherstov et al. (2022) to improve
in Sec. D of Appn. Due to space limits, we will discuss
the expressivity of attention; (2) conduct fine-gras fine-grained propagation control, such discounting or truncating the distance, similar to some deep GNNs Xu et al. (2018); Chen et al. (2020a); (3)
generalize forests to eliminate the need for Recursion (II), i.e., Eq.
4.4 TREE FUSER
Motivated by prior work Wu et al. (2024): Kreuzer et al. (202)): Wu al. (202T), we utilize local module to supplement local knowledge to mitigate the local sparsity of trees. Thus, the tree fuser first computes the local information H from input features X, which is formalized as below:
H- B1 Ag + B2 +1 B1 (2)
Inxn)
XW E Baxd
(9)
where 31 + 82 < 1, Kr. < 2 are tlyer-parametern and WN i are training parameters.
The tree fuser then computes the results of Ny different tree aggregators, H (k) = (Te) (H), E
[L, Nr]. For each H' (k), the tree fuser normalizes each row to using the L2-norm for numerical stabilization. Afterwards, the tree fuser averages all the tree aggregators as global information:
H' = Mean (RoonNorm
(H)
Raxd
(10)
KE(1, Nr))
Subsequently, the tree fuser uses a residual connection controlled by the hyper- 7 E [0, to balance local and global information, which can be formulated as follows:
H" 7) H' + 7 H.
(11)
The H" are final node embeddings that can be fed into linear predictor for node classification.
4.5 COMPLEXITY ANALYSIS
The comprehensive time and space complexities per epoch are linear against the number of nodes and edges, i.e., n and m, well as hidden dim d. Specifically, suppose sample and utilize Ny trees. Each pre-training epoch costs O ((n + m) d) time and space. Each training epoch of the student requires only O (nn m) K Kd) time and space, which can be further parallelized.

---

Published as a conference paper at ICLR 2026
Table The results of performance comparison (with the best bolded and the runner-ups underlined)
Method
Caiegury
Cura
Clieseer
Pubmed
Actor
Cocnell
Texas
Wascunsin
Arsiv
Flickz
Avg. Rank
MLP
Classic
55.30
38.68
72.94
35.62
72:70
77.84
79.01
32.84
42.01
14.11
GCN
GNN
82.06
60
79.58
17.88
53.11
69.19
57.25
53.77
38,40
14,80
GAT
40.32
ArighSAGE
81.40
78.50
SupertiATsp 30
GNN
82.70
72. 50
81.30
30.18
54.59
69:73
58.04
51.52
36.24
13.22
APPNP
GNN
$4.10
72.14
80.02
33.47
61.08
71.35
65.10
55.60
43.07
9.22
ClusterCCN
GapiSAINT
82.00
70. 30
77.55
61.96
35.26
Paimorm
DeepGNN
72.12
Nodesorm
DeepGNN
80.14
60.74
78.64
29.74
40.00
06.49
48:24
54.22
44.11
16.33
Meannonu
DesPNNN
79.54
72.16
73.06
25.46
25.41
61.62
$2.04
20.37
42,40
19.67
Drogkdge
DeeGNNN
32.11
GCNU
DNN
73.24
79.88
24,64
74.61
51.91
41.79
ShadowCINN
DeeGNNN
82.32
70.06
77,30
29.45
51.35
64.32
62.35
53.35
37.59
17.00
GT
77.38
66.
76.48
37.15
61.62
74,60
71.76
00M
OOM
15.57
SAN
GT
77.00
68.64
76.62
37.79
63.24
75.14
77.25
00M
00M
13,00
Graphommer
63.08
61.08
00M
00M
62.70
76.76
72.16
00M
00M
15,40
ANS-GT
77.98
38.29
Nodefommer
GT
79.02
09:66
76.05
34,80
08.11
77.84
75.47
29.47
40.31
13.11
NAGphurmer
CT
79.51
67.34
78.32
37.33
63.78
71.89
66.27
$2,00
38.59
13:44
GUAT
35.53
Exghormer
71.63
SGFormer
82.38
71.82
90.64
37,80
63.65
78.92
80.00
45.73
10.13
7,22
DiFFermer
GT
83.32
74.46
78.16
34.51
00:00
68.11
63.92
53.60
44.25
10.56
TDGNN
$5.35
73.78
80.20
32.84
35.68
61.35
38.25
15,00
GraphMambuu
Mamba
54.36
58.98
70.90
36.05
74.05
77.29
80.39
33.59
42.30
13.89
Ours
Forss
85.46
74.42
81,00
39,88
83.24
91.89
86.27
56,47
47.22
1.22
4.6 THEORETICAL DISCUSSION
In this subsection, provide theoretical justification for rigorous asymptotic relationship between the accuracy of the edge-homophily estimator and the quality of the induced tree distribution. Formally, we define PT(T') Il s(eig)/ Erce IT s(e;)), where the edge score is given by s(ey)) = p if nodes and j share the same label (a homophilous edge), and s(e,)) = q otherwise (a heterophilous edge). Based on this formulation, establish the following result:
Theorem 2. Let G be any connected graph, and define the expected edge homophily ratio under the score ratio A = p/q > 0 as:
R₂(A): = Br [h(T)),
where (T) ) is the edge homophily ratio of tree T. Then there exists a Do > such that:
Monotonicity. If N' Dg, then Rg(A)= > R²(A').
Upper Bound. For all A Z Ao. Ra(A) S 1 NHCC(G)-1 where NHCC(G) denotes the number of homophilous connected components of
n-1
Asymptotic Tightness. As A +oc, Ra(A) + NHCC
R-1
Theorem shows that, for a given graph G, as the ratio A = p/q increases, PT(T) gradually shifts toward homophilous trees. Moreover, the upper bound of R2(A) is determined by the number of homophilous connected components in G. which reflects the inherent structural limitation of the graph. In the limit A + R approaches this structural bound. In other words, assigning a higher score > 0 to homophilous edges and a lower score > to heterophilous edges drives (T) toward the maximum level of edge homophily permitted by the graph.
5 EXPERIMENTS
This section verifies the effectiveness of the proposed method in the semi-supervised node clas- sification task via extensive experiments. Due space limits, some experimental details such as environments, dataset statistics, algorithm implementation details, hyperparameter optimization strategy and configurations, and some visualizations are moved to Sec. K Appn.
Benchmarks and Baselines The experiments include nine real-world benchmarks, covering two types: (1) homophilous graphs: Cora, Citeseer, Pubmed (Sen et al. 2008), and OGBN-ArXiv (Hu et al. 2020) at large node scale; (2) heterophilous graphs: Flickr (Zeng al. 2019), Texas, Wis- consin, Cornell (Pei et al., 2020a), and Actor (Tang et al. (2099). Their full statistics are detailed in Tab. of Appn. For fair comparison, semi-supervised data splits adopted for OGBN-ArXe
7

---

Published as a conference paper at ICLR 2026
Liteaa Inento
Munder Trees
Munder Trees
Nartio Times
(o) Cora
(1) Pubmod
(c) Actor
Figure 4: Model performance with varying number of trees Nr.
Marión
(a) Cura
(b)
Puhmed
(c) Astor
Figure 5: Effecc of homophily estimator accuracy (p is the average score assigned homophilous edges).
and Flickr (Sec. K.2)). and other datasets strictly follow the standard public splits in Kipf & Welling
2017). Twenty-six counterparts are selected for a thorough comparison, including: (1) classic
method: MLP: (2) seven GNNs: GCN (Li et al. 2019), GAT (Veličković et al. 2018), GraphSAGE,
SuperGAT sD (Kim & Ohl 2021), APPNP (Gasteiger et al.
| 2019a), ClusterGCN CChing et al. 2019)
and GraphSAINT (Zeng et 2019);; (3) six Deep GNNs: Pairnorm (Zhao & Akoglu 2020), Node-
norm (Zhou et (021)) Meannorm (Yang et al. 2020), DropEdge (Rong et al. 2000bb. GCNII (Chen
et al. 2020a) and ShadowGNN (Zeng al. (021); 1); (4) eleven Graph Transformers: GT (Dwivedi & Bresson Bresson|2020), SAN (Kreuzer et al. 2021). Graphormer Yiin et al.) 2021), ANS-GT (Zhang et al.
2022). NodeFormer (Wu et al. 2022). ,. GOAT (Kong et al. 2023), NAGphormer (Chen al. (022bb
Exphormer (Shirzad et al.) 2023), SGFormer (Wu et al. (022). DIFFormer (Wu et al. 2023). and
TDGNN (Qu et al. 20200; : (5) Mamba: GraphMamba ( (Wang et al. 2024a).
Comparative Experiments All experiments run with ten different initializations. We report mean accuracy in Tab. with also their standard deviations in Tab. of Appn. We empirically show our framework has significant advantages for both homophilous and heterophilous datasets: against GT, DIFFormer, GCN, and GCNII, the mean accuracy is relatively increased by 16.2%, 16.1% %, 24.5% and 11.9%, respectively. Particularly on Wisconsin, we obtain 20.2%, 35.0%, 50.7%, and 22.7% relative gains. Against recent models like TDGNN, ShadowGNN, and GraphSAINT, our framework also shows significant relative gains of 39.3%, 24.8%, and 27. 27.0%, respectively. These performance gains are attributed to our ability to effectively capture long- min-diitance knowledge, thus highlighting the potential of the proposed forest-based paradigm, even under label scarcity.
Ablation Studies We conduct ablation studies in Tab, Jndd drop or substitute key parts. For convenience, we refer to Eq. 9 and Eq 10 as Local and Global Submodules, respectively. We (1) drop Global Submodules to verify its long-range modeling capability; (2) drop Local Submodules to test the effects of supplementing local knowledge; (3) Sample trees from a uni- form distribution and apply the attention weighting mechanism from Eq 8 (4) sample only a single tree to explore the po-
Table 2: Running time comparison (sec/epoch)
Method
Cora
Cileszer
Pubmed
Flickr
ArXiv
GT
0.011
0.014
0.254
00M
00M
SAN
0.165
0.154
0.241
Graphurmer
0.433
0.639
00M
00M
00M
ANS-GT
1.453
2.973
3.435
7.756
24,540
Nodeformer
0,188
0.217
0.292
0.838
1,360
NAGghermer
0.014
tential of multi-tree fusion. Comparing (4) vs. (3) reveals that sampling a single tree from the homophily-guides distribution outperforms multiple random trees, emphasizing the impor- tree sampling. Comparing (1)(2) vs.
GOAT
1.026
1.045
1.450
28 28
58. 38.772
Exphormer
0.086
0.135
0.348
1.112
1.948
SGFvmmer
0.010
0.011
0.021
0.051
0.114
DIERamer
0.030
0.297
GraphSAINT
0.013
0.022
0.030
0.658
0.951
tance of homophily-
Pairsem
0.053
0.071
0.647
0.300
1.387
(5) shows the significance of each submodule. Comparing (5) vs. (4) shows sampling multiple trees (a forest) can consis- tently surpass a single tree from our distribution, confirming that a forest can effectively capture more comprehensive and complementary topological knowledge.
Nedenomm
0.013
0.032
0.285
0.310
1.357
Meamorm
0.012
0.030
0.279
0.296
1.461
Dropedge
0.017
GCNT
0.066
0.033
1.306
1.373
2,843
Ours
0.005
0.019
0.020
0.079
Hyper-Paranee Parameer Studies We conduct several dyper-parameter studies in Sec. J. Here, due space limits, we focus only on the impact of the tree number Nr on performance in Fig. which reveals an optimal range of 6 to 10 trees across different datasets, highlighting our efficient coverage of global knowledge. In Fig. 4 the performance first consistently rises and then fluctuates or decreases, meaning that our framework covers the essence of the graph structure with only few trees, and
8

---

Published as a conference paper at ICLR 2026
Table 3: The results of ablation studies.
No.
Method
Cora
Citeseer
Pubmed
Actor
Corneil
Tosas
Wisconsin
AdXiv
Flickr
(1)
v.o. Global Submodale
80,00
71.63
36.13
34.23
15.68
82.85
$3.92
55.05
39,63
Local Submoduile
82.18
71.55
77.48
35.08
74.77
69.93
75.49
54.92
32.17
Liifors Tree Sampling
83.83
72.32
78.45
72.97
82.58
54.30
55.11
42.77
Single Homophily goided Free
83.73
22.58
78.55
36.32
26.35
84.83
85.
55.12
12.95
(5)
FGL SSL-OOm -Onn
85.46
74.42
81.00
39,88
83.24
91.89
86.27
56.47
47.22
more trees provide marginal benefits and risk redundancy, highlighting our efficiency due to a lower number of structures in the calculation of the total cost, i.e., Eq. [
Efficiency Comparison Besides the theoretical complexity analysis in Sec. 4.5 we compare the method runs faster than baselines in most cases. For
practical running time in Tab. where example, compared with recent GTs like ANS-GT and GOAT, which require over 1 second per epoch on small graphs and dozens of seconds on large graphs. our method runs in under 0.02 seconds on small graphs and 0.246 seconds on ArXiv. Even against efficient GTs like DIFFormer and deep GNNs like GCNII, our method shows 2 to 5 times speedup. While few baselines run slightly faster than ours, their performance is generally worse than ours, since they overlook some critical structural knowledge due to over-simplified designs. Compared with these baselines with strong performance, we have the highest efficiency. highlighting the advantages of the linear complexities and higher parallelizability of the proposed forest-based learning paradigm.
Homophily Estimator Comparison To explore the effects of different homophily estimators, we compare six variants in Tab. 4 (A) Non-attention auxiliary module (NAAM) via single-layer GCN for homophilous graphs or MLP for heterophilous graphs to generate pscudo-labels; (B) Naive attention based estimator via a single local graph transformer layer where attention coefficients serve as bidirected average edge homophily scores; (C) 2-stage homophily estimation that first generates pseudo-labels via non-attention estimator, then uses these labels to guide the training of attention- based estimator for more stable homophily scores; (D) FGL (Uniform) as baseline that samples trees uniformly; (E) FGL (Naive attention estimator) that uses attention scores from (B) to guide tree sampling: (F) FGL (2-stage estimator) Ours, incorporating the full two-stage estimation process for robust homophily-guide tree sampling. Comparing (B) vs. (E), FGL using an attention based estimator performs competitive or better than the standalone attention estimator, demonstrating FGL's 's effective utilization of homophily scores through structured tree aggregation. Comparing (C) vs. (E), two-stage estimation significantly outperforms FGL with only attention- based estimation in most cases, confirming that pseudo-labels from non-attention estimators provide valuable supervision to improve homophily estimation quality, especially under label scarcity. These empirical observations further support our theoretical analysis (Theorem 2 and directly confirm the accuracy of the edge homophily estimator has a positive impact on our final results.
Interpretability Studies We propose strategy to design our tree distribution, which is justified by Theorem 2 Here, we provide some empirical evidence to under- stand our performance gains. revealss that as the accuracy of homophily estima- tor increases, model performance consis- tently improves across all datasets, with perfect estimation (accuracy is 1) leading to perfect classification, demonstrating no performance bottleneck and motivating the pursuit of high-quality homophily estima- tors. To further understand the mechanism, we introduce global homophily metric (Sec. J.2 Fig. 6 shows that trees sampled from our homophily-gume -guided distribution significantly facilitate higher long-range homophilous information propagation compared uniform sampling. Such trees allow the subsequent tree aggregator much easier to capture and exploit beneficial distant graph information, which fundamentally interprets our performance gains.
0.0052
Ous
00626
Huundoo
Raedon-Spawingg Trin
EL77100
Our
homophly
02
03
Datanets
Figure 6: homophily ratio comparison based on different sampling strategies
CONCLUSION
To break the dilemma of existing graph techniques, i.e., the challenging trade-off between complexities and comprehensive long-distance knowledge, we fundamentally analyze its root cause and propose

---

Published as a conference paper at ICLR 2026
Table Comparison of different homophily estimators.
No.
Model
Cora
Ciieseer
Fuhmed
Actor
Cumell
Texas
Wiscensin
AdXiv
Flickr
(A)
Non-attestion aucliaay module (NAAM)
77.42
09.62
76.64
55.35
72.97
72.97
$2.35
47.65
38.36
(8)
Naive attention based extimater
75.18
65.78
74.32
34.87
20.27
75.00
73.04
53.45
40.90
Two-stage atteation)
FGL (Uniform) OL usenntio))
78.40
73.13
34.47
70.27
52.30
41,05
(2-stuge)
novel forest-based graph learning paradigm. The key insight to understand a graph as a fusion of some sampled spanning trees, similar to bagging, since tree can connect all nodes economically. We provide a technical framework, where we first induce a tree distribution proven biased towards homophily, and then efficiently conduct all node-pair interactions in each tree via general tree aggregator with linear complexities and higher parallelizability. Compared with deep GNNs or GTs, our framework has better global coverage and structural understanding, with higher efficiency. Extensive experiments on semi-supervised node classifications show we can achieve competitive or even better results than state-of-the-ee art counterparts. We believe our forest-based paradigm is significant step towards the future development of long- distance graph learning.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
This work is partly supported by the National Key Research and Development Program of China (No. 2023YFF0725001), the National Natural Science Foundation of China (No. 92370204, 62306255), the Guangdong Basic and Applied Basic Research Foundation (No. 2024A151501 1839). the Guangdong Basic and Applied Basic Research Foundation (Grant No.2023B1511112005 the Key-Area Special Project of Guangdong Provincial Ordinary Universiteex202244ZZZZXXX0
REFERENCES
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference Machine Learning, pp. 874 883. PMLR, 2020.
Francesco Bonchi, Claudio Gentile, Francesco Paolo Nerini, André Panisson, and Fabio Vitale. Fast and effective gnn training through sequences of random path graphs. Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining V. pp. 49 60, 2025.
Andrei Z. Broder. Generating random spanning trees. In FOCS, volume 89, pp. 442 0472444,11 1989.
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning. pp. 3469-3489. PMLR. 2022a.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, 2022b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference Machine Learning, pp. 1725-1735, 2020a.
Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: A comprehen- sive benchmark study. IEEE Transactions on Pattern Analysis and Muchine Intelligence, pp.
DO1:10. 000::0.1099PPMMM222231114153 2022c.
Zhiqian Chen, Fanglan Chen, Lei Zhang, Taoran Ji, Kaiqun Fu, Liang Zhao, Feng Chen, Lingfei Wu, Charu Aggarwal, and Chang-Ties Tien Lu. Bridging the gap between spatial and spectral domains: A survey on graph neural networks, 2020b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266. 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021. URL
net/ (o
Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Shuting Cui, Ying Sun, Yuting Zhang, Qingxin Meng. and Hengshu Zhu. Lim-enhanced career knowledge graph understanding for job mobility prediction. ACM Transactions on Management Information Systems, 2026.
Xiangyu Dong, Xingyi Zhang, Yanni Sun, Lei Chen, Mingxuan Yuan, and Sibo Wang. Smoothgnn: Smoothing- gnn for unsupervised node anomaly detection. In Proceedings of the ACM Web Conference 2025, pp. 1225-1236, 2025.
David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Proceedings of the 49th Anmual ACM SIGACT Symposium Theory of Computing, pp. 730-742, 2017.

---

Published as a conference paper at ICLR 2026
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
Taoran Fang, Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. Dropmessage: Unifying random dropping for graph neural networks, 2023.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for superviee learning graphs. Advances in neural information processing systems, 33:22092-22103 2020.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2019a.
Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019b.
Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. On the trade-off between over-smoothing and over-squashing in deep graph neural networks. In Proceed- ings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM '23, pp. (66,,77, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701244 245. doi: 10.1145/3583880.66149999 3583780
Zheng Gong and Ying Sun. Graph reasoning enhanced language models for text-to-qll, In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp.
2024.
Zheng Gong and Ying Sun. Outlier- aware post-training quantization for discrete graph diffusion models. In Forty-second International Conference on Machine Learning, 2025.
Zheng Gong, Guifeng Wang, Ying Sun, Qi Liu, Yuting Ning, Hui Xiong, and Jingyu Peng. Beyond homophily: Robust graph anomaly detection via neural sparsification. In Ijcai, pp. 2104-2113, 2023.
Caterina Graziani, Tamara Drucks, Monica Bianchini, Thomas Gärtner, et No pain no gain: More expressive gnns with paths. In NewrIPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Yonghang Guan, Jun Zhang, Kuan Tian, Sen Yang. Pei Dong, Jinxi Xiang, Wei Yang, Junzhou Huang, Yuyao Zhang, and Xiao Han. Node-aligned graph convolutional network for whole-slide image representation and classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 18813-18823, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18-22133, 2020.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over-smoothing for general graph convolutional networks, 2020.
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Global self-attention replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 655-665 2022.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmax. arXiv preprint arXiv:1611.0m (ww.166111011444 144, 2016.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 207:1 17221, nov 2022. doi: 10.1016j.esw.2222211991 URL
https://don worg/10gg....... 10. 10166 eswa. 2022. 117921
Jeff Johnson, Matthijs Douze, and Hervé Jégou, Billion-seas similarity search with GPUs. IEEE Transactions Big Data, 7(3):535-547, 2019.
12

---

Published as a conference paper at ICLR 2026
George Karypis and Vipin Kumar. A software package for partitioning unstructured graphs, partition- ing meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesora, Department of Computer Science and Engineering. Army HPC Research Center, Minneapolis, MN, 38, 1998.
Jonathan Kelner and Aleksander Madry. Faster generation of random spanning trees. 2009 50th Annual IEEE Symposium Foundations of Computer Science, pp. 13-21. IEFE, 2009.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. In International Conference Learning Representations, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International
Conference on Learning Representations, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, 2017.
Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference on Machine Learning, pp- 77375-17399 PMLR, 2023.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létoumeau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 14:21618-21668 2021.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9267-9276, 2019.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference machine learning, pp. 6437-6449 6449, 2021.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International 102--12566 13256. PMLR, 2022.
conference on machine learning, pp. 13242-
Valerii Likhosherstov, Krzysztof M Choromanski, Kumar Avinava Dubey, Frederick Liu, Tamas Sarlos, and Adrian Weller. Chefs' random tables: Non- -on-trigonometric random features. Advances in Neural Information Processing Systems, 35:34559-3457 2022.
Zhe Liu, Jinghua Hou, Xinyu Wang, Xiaoqing Ye, Jingdong Wang. Hengshuang Zhao, and Xiang Bai. Lion: Linear group rmn for 3d object detection in point clouds. Advances in Neural Information Processing Systems, 37:13601-13626 2024.
Sitao Luan, Mingde Zhao, Xiao Chang, and Doina Precup. Break the ceiling: stronger multi- scale deep graph convolutional networks. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. (0945-10955, 2019.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wa Wen Chang, and Doina Precup. heterophily a real nightmare for graph neural networks to node classification? arXiv preprint (10iv:220900666 2021.
Gaspard Michel, Giannis Nikolentzos, Johannes F Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, pp. 24737-24755. PMLR, 2023.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455. 2022.
Usman Nazir, He Wang, and Murtaza Taj. Survey of image based graph neural networks, 2021.
13

---

Published as a conference paper at ICLR 2026
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style,high- performance deep learning library. Advances in neural information processing systems. 32: 8024-8035 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conferencee on Learning Representations, 2020a.
URL
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint (rXiv:2002.05287. 2020b.
Liang Qu, Huaisheng Zhu, Qiqi Duan, and Yuhui Shi. Continuous-time link prediction via temporal dependent graph neural network. In Proceedings of The Web Conference 2020, wWW '20, pp. New York, NY, USA, 2020. ISBN 450370337 doi: 10. 0o.1145//3664223330077
URL /tttps://doi.orrot wtt.:o////..11/331..1.
1145/ 038.33666633333007770 3380073
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information 2020a.
Processing Systems,
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2020b.
Mudar Sarem, Tarek Jurdi, Laya Albshlawy, and Ebrahim Massrie. Improving long text classification based on selective state space model (mamba). In 2024 IEEE 17th International Symposium on Embedded Multicore/Many-com
Pystems-on-Chip (MCSoC), pp. 32-38. IEEE, 2024.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-95 2008.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning. pp. 31613-31632. PMLR, 2023.
Henan Sun, Xunkai Li. Zhengyu Wu, Daohan Su, Rong- Hua Li, and Guoren Wang. Breaking the entanglement of homophily and heterophily in semi-supervised node classification. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 2379-2392 IEEE, 2024.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp- 1541-1551, 2021.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 807-816, 2009.
Josephine M Thomas, Alice Hoallemy-Ourek Silvia Beddar-Wiesing, neural networks designed for different graph types: survey, 2022.
Wiesing, and Clara Holzhüter. Graph
Domenico Tortorella and Alessio Micheli. Beyond homophily with graph echo state networks. arXiv preprint 1rXiv:2210.1577 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00789 2024a.
Kunze Wang, Yihao Ding, and Soyeon Caren Han. Graph neural networks for text classification: A survey. Artificial Intelligence Review, 190, 2024b.
14

---

Published as a conference paper at ICLR 2026
David Bruce Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the ewenty-eighth annual ACM symposium on Theory of computing, pp. 296-303, 1996.
David Bruce Wilson and James Gary Propp. How to get exact sample from generic markov chain and sample a random spanning tree from a directed graph, both within the cover time. In SODA, pp. 448-457. Citeseer, 1996.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27401, 2022.
Qitian Wu, Chenxiao Yang. Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. Dif- former: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.0947. 2023.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36, 2024.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 1e.132666-32799 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Yicheng Xiao, Lin Song, Shaoli Huang, Jiangshan Wang, Siyu Song, Yixiao Ge. Xiu Li, and Ying Shan. Mambatree: Tree topology is all you need in state space model. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https 7/openreview. wwt.:/eeetooommdmdeeemm..m
Yu Xie, Shengze Lv, Yuhua Qian, Chao Wen, and Jiye Liang. Active and semi-supervised graph neural networks for graph classification. IEEE Transactions on Big Data, 8(4):920-933) 2022. doi:
10.1109/TBDNTA.200 2021.3 114.115
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462, 2018.
Chaoqi Yang, Ruijie Wang. Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens, 2020.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34:13683-13694, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference Learning Representations, 2019.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.). Advances in Neural Information Processing Systems, 2021. URL htt.tttps... http:::://pperev... www.net/eeet forum?
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
15

---

Published as a conference paper at ICLR 2026
Xiangyu Zhang, Qiquan Zhang, Hexin Liu, Tianyi Xiao, Xinyuan Qian, Beena Ahmed, Eliathamby Ambikairajah, Haizhou Li, and Julien Epps. Mamba in speech: Towards an alternative to self- attention. IEEE Transactions Audio, Speech and Language Processing, 2025.
Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. Hierarchical graph transformer with adaptive node sampling. Advances in Neural Information Processing Systems, 35:21171-21183, 2022.
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. arXiv preprint arXiv:2110. 13094, 2021.
Lingxiao Zhao and Leman Akoglu. Paimnrrm Tackling oversmoothing in gnns. In International Conference Learning Representations, 2020.
Yilun Zheng, Jiahao Xu, and Lihui Chen. Learn from heterophily; Heterophilous information- enhanced graph neural network. arXiv preprint arXiv:2403.1755/ 2024.
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation in deep graph convolutional networks. Proceedings of the 30th ACM International Conference Information & Knowledge Management, pp. 1728-2737, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
Yuanxin Zhuang. Dazhong Shen, and Ying Sun. Ngtm: Substructure-base based neural graph topic model for interpretable graph generation, arXiv preprint arXiv:2507. 2025.
16

---

Published as a conference paper at ICLR 2026
A DISCUSSIONS
In this section, we will provide extensive discussions on some different aspects of our framework, including some intuitions and motivations well theoretical insights.
A.1 DISCUSSION ON DEGREF IMBALANCE AND THE MERITS OF LONG-DISTANCE KNOWLEDGE
In real-world graphs, degree/density imbalance is a common phenomenon, where a small number of nodes have many connections while most nodes have only a few connections, especially in, e.g., social networks, citation networks, and biological graphs. For example, in social media, a few influential users may have thousands of followers, but most of the others have limited neighbors. Degree imbalance biases graph learning algorithms to focus on highly connected nodes and ignore low-degree nodes. More severely, it fundamentally worsens overfitting in graph learning. Low-degree nodes in the training set face a significant issue. Constrained by training objectives, they must fit their labels, but their limited local knowledge may not be enough. With sufficient expressivity, they will use noisy information for fitting to achieve their learning goal and reduce their training losses. Since noise varies among nodes, classification rules learned from noise cannot generalize unseen nodes, thus causing overfitting issues, On the other hand, for low-degree or low-density nodes in the test set, the limitation of local knowledge poses another challenge. Graph learning models rely on training data to learn classification rules to generalize. However, for those unseen low-degree nodes in the test models struggle generalize, since their valuable knowledge on which the generalizable rule is based is insufficient, directly causing misclassification.
set, even
Therefore, distant information becomes crucial. By supplementing the scarce local information of low-degree nodes, it helps models understand these nodes better, capture global graph context, and learn general patterns, thus reducing overfitting. In summary, distant knowledge is critical in graph learning, especially under degree or density imbalance. Even when local information seems sufficient, integrating distant knowledge can partly improve performance, which is currently underestimated.
A.2 DISCUSSION ON AGGREGATING BEHAVIOR COMPARISON AMONG DIFFERENT PARADIGMS
We find that our tree-based paradigm and some other counterparts can be rewritten in a united path-decomposition form with different path weighting strategies, which is shown below:
Definition 1. Define the path-decomposition of a graph learner or aggregator as follows:
H = Agg ((Hu)uEV)
Σ
Σ
Hu (p(p) PP.(),
(12)
NEV
P(L-VIJEG:
PO P PL
where (p) II 1p with Wz-ry is the weight of directed edge -> y and PE (p) is extra path-based positional encoding beyond vanilla pair-wise relative positional encoding.
We find that: (1) Infinite-layer deep local SGC, deep local GT, or infinite-step random walk ag- gregation all have this form, with Wa-ty as values in the normalized adjacency matrix/transition matrix/layer-sharr sharrd attention coefficients, and PE (p) = II PE (pt). where PE (px) is the sum of the discounted edge weight product in all circles of any length. This shows that these methods focus more on local environmental importance of a path, egg., densities or degrees of nodes contained in it. (2) Tree-Set (i.e., Forest) Layer also has this form, with PE (p) as the sum of weight products of all spanning trees the graph obtained by merging path P into a single node. This shows that our paradigm focuses more on global transport importance of path, i.e., how connectivity or communication this path can facilitate if it is built as a highway with no communication cost along it.
We provide the detailed derivations in Sec. B.4 of Appn.
A.3 DISCUSSION ON OVER-S SVER-SMOOTHNESS ALLEVIATION OF OUR PARADIGM
In this subsection, we provide a theoretical discussion on the relationship between our graph learning paradigm and the ovor-smog issues. Our analysis be divided into parts: (1) Analysis on
17

---

Published as a conference paper at ICLR 2026
the over-smoothness of fixed-distance aggregation: (2) Analysis the over-smoothhess of infinite- distance (i.e., comprchensively global) aggregation. This analysis not only highlights one of the merits of our paradigm, but also provides some novel insights for alleviating over-smoothing issues from the perspective of the aggregating operators themselves as well as their adaptive aggregating scopes.
We first consider the first case, Le., fixed distance, which is based on similar theoretical evidence as those deep GNNs from, e.g., Rong et al. (2020b) or Chung (1997).
Lemma 1 Chung (197)) ) Let G = (V, E) be connected graph with its diameter D(G) 2 4. Then the second smallest eigenvalue X2 (G) of its normalized Laplacian matrix satisfies:
X2 (G) 21
V [mmaxev do) (1
(1- (-G)))
2
2 D(G)'
(13)
maxuEv de
where X2 (G) is also known as the spectral gap of the graph G.
This lemma provides upper bound for the spectral gap for graph G. The next lemma shows how 22 (G) can connect to the over-smoothness.
Lemma (Chung 1997)) ). Let be an ergodic random walk transition matrix, where G is connected
and non-bipartite, let π be its stationary distribution, and let f be any initial distribution. For any s E N we have:
| p -|| S 8X max, Vdl
(14)
miny Vaz" where X X2 x2) if 2 AN (G) 1, and 2 AN otherwise. P D-D-IA A is the random walk transition matrix. For any initial node distribution f V R with ΣnEV f(v) =, 1, the node distribution after steps is given by f pk. where f E IR Nx1 is the vector of initial distributions such that f() is the function evaluated on the ith node. The random walk is ergodic when there is unique stationary distribution k satisfying that lim pp π Chung 1997).
Therefore, we can compute the value of such that || P T as follows:
8 2
(15)
X log
max; Vin
min, Vd,
where we can always add self-loops with weights du for node v E V to make X' = A22 (G).
Theorem 3. Let = (V, E) be a connected graph with vertex degrees {dr Joe,, maximum degree M maxvev du and diameter D(G) 2 4. For any spanning tree T = (V, ET) of G, denote the degree of vertex v in as d(T), its maximum degree as MT = mmaxvev dlS), and its diameter as D(T) > D(G). Let s(G) and s(T) be the number of steps required for node distributions in G and to be within e of their stationary distributions, respectively. Based on Lemma I and Lemma we have the lower bounds of (-): (1) For graph G:
s(G) 2
(16)
1- 1-2.1M-1
1
VM-1 (1- M
2 + D(G) DiG)
log
mAXi Vid
<miny ddz
and (2) for its spanning tree T:
s(T) N
(17)
(1 1-
My-1 MT
(1-
D(T)
2
+
2 log +D(T)
eminy
v C
((()) S for all v E V, implying Mr S M; (2) Diameter extension: D(T)) D(G) > 4, the monotonicity analysis of the bounds of s with respect to M yields: T has a tighter (larger) lower bound of sTT) against that of G. Since a larger s indicates more steps needed before distributions approach the stationary node distribution of the Markov Chain. Thus, for fixed distance aggregation, the spanning tree structure T can alleviate wvor-snoo issues.
Since spanning tree T satisfies: (1) Degree constraint:
18

---

Published as a conference paper at ICLR 2026
H. = M (5.. (S.. S
Figure 7: The detailed illustration of the recursion formulas (Eq, 30 and Eq, 31 described in Sec, B. of the main text. We demonstrate the derivation of these two relationships via several steps. Given a tree T, consider a pair neighboring key nodes u and v, which are colored red and blue, respectively (a) With the red node u as the root of T, all other nodes send global messages to u (colored red dashed line), and we can clearly observe the information flow direction of each edge. Denote the expected total global messages of node u with H" (b) With the blue node as the root of T, all other nodes send global messages blue solid line), and we can clearly observe the information flow direction of each edge. Denote the expected total global messages of node with H'. (c) We put (a) and (b) together. From the comparison, we can clearly see that the only difference between these two distinct information flows is the direction of a single key edge (f.e., the edge d ++ v). In other words. the directions of all other edges remain consistent, (d) Then, we cut the key edge and observe the remaining message aggregation processes. (e) With another node y E V as the root of tree T, node u will become the father of node v. After cutting the key edge u ++ v. the remaining global messages flowing into node u = Fa (v) is denoted as Space) (red) while the remaining global messages flowing into node is denoted as S, (blue), (0) This sub- sub-figue figure more clearly shows the father-son relationship between node and node The black dashed line explicitly highlights this relationship. Note that the black line does not represent any information flow or its direction. (g) If we add back the key edge with son -> father (i.e. V. - fa (v) == w), we can restore the lotal global messages into node Fa (v), i.e. (o(s)))) by merging the information from (i.e, blue S,) into that of Fa (v) (i.e. red Pa(t)) which derives one formula (Eq. 31.. Note that the long red dashed line - u denotes the direction of the information flow. (h) we add back the key edge with father -> son (Le,, fa (v) = + v), we can restore the total global messages into node v, Le.. H', by merging the information from = Fa (v) (ic. red Spw))) into that of (i.e, blue S.). which derives another formula (Eq, 30), Note that the long blue solid line - denotes the direction of the information flow. These figures detailedly show the derivations of two formulas, both of which utiliize the operator M (::) but with different or opposite merging directions.
(colored
S
(oua)
cut
(d)
Facos
hh)
Fa(t)
Information flow: - -o0
Wigoo M (Sraco Ss,)
(C)
Fa( FooD))
Informatio flow: 500 - father
This snow denules fallur 500 mlltinnhippa mat
(b)
Fo(t)
(I)
(a)
Fott))
Fa(v)
H
19

---

Published as a conference paper at ICLR 2026
The proof can be found in Sec. B.3 of Appn.
We then consider the second case, i.e., infinite distance. Recall Eq. 30and and the illustration on their derivations in Fig. 7
and Eq 31 provided in Sec. B.1
H = M (Se, Skate))
(18)
H Bato) = M (Seuco) Sw)
(19)
where M+ (.--) -) a directional merging operator, merging the right term into the left term. Note that the term S. and Sat denoting knowledge from different parts in the graph G (the sub-tree of node and its complement, Fig. 7) which means that there is nearly over-lapped (or intersected) information among them. Therefore, it is reasonable to suppose that: ||SPato)) Soll2 2 is not small, which gives:
H (a)))) H2 MM (so.)) - -M* (Shan))
MM+
s.).l,=
(20)
This equation implies that the difference between the node embeddings of a pair of neighboring nodes can be bounded by the extent of asymmetry. Since the M+ (---) can be specifically designed by practitioners, we have the opportunity to directly alleviate the over-smoothness. For the simplest example, we set M (a, b) = 3a + b, and thus we obtain:
(a Hlll = (35. + Sku(os) - (3S%ato) + su)ll
(21)
2 | -
S.]12
(22)
Since we assume that (S S,ll2 not small (i.e., the two terms inside have non-trivial differences because they aggregate information of completely different sets of nodes, illustrated in Fig-Z7 the over-smoothness can be naturally controlled. Yet, for traditional deep GNNs with very deep layers, the differences between H', and Hy are bounded by embeddings from the last layer, which already have too many similarities due to overlapping or even the same global scope, intuitively improving the risk of over-smoothness.
A.4 DISCUSSION ON PROPAGATION BOTTLENECK ALLEVIATION OF OUR PARADIGM
In this subsection, we briefly discuss how framework alleviates the propagation bottleneck. When the knowledge is propagated along the edge of a single tree, it would be discounted with distance even blocked when the distance becomes too long. To address this issue, we integrate several trees (NT trees), i.e., a forest, rather than single tree. Furthermore, we can additionally integrate simple local shallow GNN (i.e., several local layers) before and/or after the proposed global layer (i.e., Forest Layer in Fig. 2
Suppose we have NT trees and add Kz/2 local sub-layers before and after our global layer, re- spectively. One message from node to node u has only single path in tree with the distance dist (v, w). After improving, the number of candidate paths becomes K - 22K,, where d is as- sumed to be the average degree of all nodes on graph. Furthermore, the distance can be significantly shortened as follows:
dist (TTahen, mn) (v, u)
(23)
dist (v, + dist (G) (u, (u, + min dist (W) (u),
min w': (i (k,12) u': (ist (u, K
(24)
kEll, K]
which means that the message from v to can first select Kz/2-order neighbor on the vanilla graph, then be quickly sent to another neighbor u' of u, and finally be propagated from u' to The overall path is: + o' + u' + u, which mimics the real-world transport strategies, where people walk into a highway system and walk outside it.
The distance dist ( (Tet, k)) can be shortened the minimum value, i.e., the length of their shortest path in the vanilla graph, i.e., (G) (u, v). since:
dist. (1Th Jeep, xq) (u, w) 2 dist (G) (v, u') + dist (w, (u, n') + (Gs (u', e²) dist (S) (v. u). (25)
20

---

Published as a conference paper at ICLR 2026
where u', v' are the optimal nodes of the last equation. When improving the value of K2, the above distance tends to approach the optimal value, if K2 2 D(G) and letting u' = r'. This case deteriorates into traditional deep GNN, propagating knowledge only via stacking local layers. Thus, from the perspective of propagating distance, our framework can be viewed as an interpolation between deep GNNs and shallow global counterparts. Moreover, with some graph augmentation tricks, e.g., Expander Expander[Shirzad Shirzad et al. (2023) or prediction-based one (Sec. [L. the shortest path length on the vanilla graph can be further reduced, which means the distance can be adjusted into appropriate values between large interval. Therefore, we can find good K2, and Nr to adjust those distances to the most appropriate values. Note that too large K2 and Ny can nearly address the propagation bottleneck, but with extra computational overhead. Also, it would make over-smoothness severe due to their essential trade-off reported in Giraldo et al. (2023). Thus, we keep Kr. S 2 and Nr S 15 (Nr S 6 for larger graphs), and empirically obtain competitive performance.
A.5 DISCUSSION ON THE MOTIVATION OF OUR ATTENTION-BASHI ESTIMATOR
In this subsection, we will detail our motivation for the design of an attention-basee edge weight or homophily estimator, well as discussion on its impact on future attention exploitation, which will essentially provide an explanation of our performance gain from a very high-level perspective, even though we utilize the most basic auxiliary models to guide the training of local attention learning.
We expect to sample spanning trees from a tree distribution defined via scores defined based on a homophily estimator. In the node classification tasks, the quality of homophily estimator is assumed to be positively proportional to its performance (despite the fact that it is not the only factor related to the performance). Therefore, we hope the auxiliary models to have better performance. Attention coefficients tend to measure the utility of the information of one object on the learning of another one, homophily estimator. However,
which is intuitively a good implementation of the under label scarcity in the semi-supervised settings, attention based models risk over- -ver-fitting issues due to their strong expressivity, which would deteriorate their performance as well as their quality of attention. To address this issue, before learning effective attention coefficients, we expect to adjust or polish the way of pre-training the attention- based auxiliary models, i.e., T1. Yet, how to better pre-train this auxiliary model Ti is quite a big problem, which may be significantly beyond our work. But we can consider this problem at a high level and utilize a simple trick: use another pre-training process before the training of Ti and inject some valuable knowledge K2, into the latter. The extra knowledge Ky can be viewed as some extra guidance, hints, or rules (e.g., the pseudo-labels or predictions from To). The attention learning will be generalized Ko. we extract new knowledge Ki from Ti. We trust the ability of the model Ti, but sometimes it may suffer from some issues due to some reasons. The outputs Ky have the potential to stabilize its training. Also, Ko can be extracted from another model To. For our case, the K4 can be simply set to the predictions, i.e., the node label predictions from the previous auxiliary model To. The intuition is that this K, can supplement the supervision, which has effects on alleviating over- over-fitting issues. As evidenced in our estimator comparison experiments (i.e., Tab. (4) the introduction of IKg can effectively improve the performance of the iitention-based model Ti in most cases.
conditional training, i.e., with
A.6 DISCUSSION ON THE GENERALITY OF THE MESSAGE AGGREGATOR
Despite the restrictions posed on SAgg (.) due to the discovered properties, we show Sags (.) can still be quite general. To see this, recall the fact that many aggregators are designed with a weighted sum of transformed embeddings (including attention) followed by a simple element wise activation. If the activation is an identity map, then the linearity perfectly admits the properties (Eq. [4). Besides, if it is non-linear and invertible, we can first invert S, and H Fa(u) easily in Eq. 34 (the first arguments in M+ and --), and then repose non-linearity after M Moreover, for those non-invertible non-linear activation functions o (-), we can use a trick, i.e., only storing before-activation values into s(") and
H [b] avoid invertibility and then reposing nin-liiyy follows:
Fa(v)
[b] (fo (s(b1 ).ECHIO Og (G (Fw)))
VUEV,
5 u
Recursion (I))
(26)
H = M+ (s!t) a (M (Ma)))) (5 )))
VVEV,
Recursion (II)
(27)
21

---

Published as a conference paper at ICLR 2026
V = (H S, = a (5!"m) flas (-) = a (fAgs (-))
(28)
This insight allows almost all famous first-order local aggregators fags (-), including many local attention-based GNNs and typical RNNs, even beyond linearity.
A.7 DISCUSSION ON THE INSIGHTS OF EXPRESSIVITY
Recall that the expressive power of GNNs typically refers to their ability to discriminate whether two given graphs are isomorphic or not. Thus, the first natural question is whether the proposed framework can successfully identify two given isomorphic graphs. Here, we consider two graphs, G1 = (V1, Ei) and G2 (V2, Eg), with exactly the same number of nodes and edges (i.e., [V1
[V/] and
[E = E2) Provided that they are isomorphic, there must exist a bijective function y V1 + V/2 such that (u, a) E E = [((((),, (p)) E E2} for any u, v E V1, where I[-} is the indicator function. In other words, these two graphs, G1 and G2, look exactly the same, up to a node relabeling. Assume that our paradigm encodes a graph G (V, E) into an embedding HG))
R where H(G)= Pool (L (G) and (G) = (T~P((G) [ (v) with sa (v) E R denoting the global message obtained via node v by the tree T. Therefore, we can successfully identify that these two graphs G1 and G2 are isomorphic, since H (G1) = H(22). To see this, considering any spanning tree Ti- = (V. FTT,) S G1, there must exist a corresponding tree T2 C G2, where To 4p (T)) = (V, sp F )), such that Ti and T2 are isomorphic and the position of node e in T3 is symmetrically the same as that of node (p() in T3. Thus, we have l'kez (v) = fAix (v(()),
and consequently we can obtain that for any node v E V. (G,) Ha(r) (G2), due to the fact
that (T)))((G Ags (v) = (T)) fAäs (sp (v)) This concludes the proof of H (G1) =
(G2), showing the ability of the proposed framework to identify isomorphic graphs
Besides, we can further provide some insights into the ability to identify non-isomorphic graphs. We present two example graphs, G1 and G22, that are not isomorphic and can be successfully identified by our paradigm, yet fail to be identified by typical GNNs. One case is that: let Gi be a six-node circle and G2 be two three-node circles with all node features assigned scalars 1s (we call this case Case A). For typical GNNs, including GIN, their appressiveddiscriinatt 1-WL, which is a theoretical framework for encoding graphs based on iterative local aggregations and hashing. In this case, by mathematical induction, each node in each graph has intrinsically the same color set of first-order neighbors (e.g.. {1,1)). 1}), and thus they will be colored exactly the same after hashing at each iteration in the 1-WL. test algorithm (e.g., all nodes implies that both of 1 and G2 obtains the same graph encoding, i.c., the multi-set {1, 1,... ,1,,, 1}. and cannot be distinguished. More high-levelly, since 1-WL gains global power by local stacking, works well for local structures, but may fail at some simple global structural recognitions. We know that graphs can be viewed as approximated discrete manifolds. From the perspective of manifolds, local structures do not directly imply the global topology, and how such local structures are organized still matters. That is why 1-WL techniques fail to deal with Case A. In contrast, Graph Transformers (GTs) directly conduct global aggregations and have the potential to address this case. Yet, without sophisticated positional or structural encodings (PEs or SEs), GTs fail to capture such long-distance topological knowledge (c.g., connectivity, connected components, or communities). It would produce node embeddings 1s for all nodes (i.e., (G1) = H (G2) = Pool (f1, 1, ... ,1)) for each graph), and thus still fail to discriminate graphs in case A. Therefore, it necessitates a complex PE for GT's such as Laplacian-based encodings, which, nevertheless, would result in a higher complexity to achieve such a stronger power. But in our paradigm, taking any spanning tree (with edges weights 1) for each connected component of the graphs, we can efficiently obtain H(G)) = Pool (16, 6, ... 6)) and (G2) Pool (f3, .................... 3)). which easily distinguishes these two graphs G1 and G2 without the necessity of any hand-craft high-complexigg PEs or SEs. This case can be generalized to any two non-isomorphic k-rrgular graphs G, and G2 (Case B), where each node has the same degree k. Similarly, by mathematical induction, 1-WL will still produce the same encoding for both G1 and G2. and thus fails to discriminate them. And GTs still require sophisticated PEs/SES to encode subtle structural differences. But our FGL can implicitly encode such differences into edge probabilities in a tree (i.e., p(e). denoting how likely an edge e would appear in a spanning tree), and then affect the probabilities of propagating paths. The sensitive probabilistic differences will naturally differentiate the passed node messages and make final graph encodings distinct. This insight shows the potential of our FGL to surpass the expressive power of typical GNNs.
powers are restricted within
colored with 1), which
22

---

Published as a conference paper at ICLR 2026
A.8 DISCUSSION ON DEALING WITH DENSE GRAPH
It is not practical for us to utilize only several trees (e.g., K trees) to comprehensively capture all topological information of densely connected graph, such graph with n nodes and (nn)) edges. In other words, it would unavoidably cause some information loss in this situation. The intuition is that seems not enough for these trees to well represent first-order neighborhoods, since K trees cover only K- n degrees (K < n), but the total node degree positively correlates to the number of edges, i.e., (n²) edges. However, we can straightforwardly mitigate the information loss by increasing the number of trees, K, with extra complexities no more than the number of edges O(n²). The reason is that in this situation, the graph itself would become the essential bottleneck of complexities, and thus, there are no efficient ways to process it without any information loss. Moreover, we empirically find that adding only a few trees may be sufficient to cover the main information. That is to say, the number of trees utilized for dense graph can be sublinear in the number of nodes, n, with a very limited extra computational burden compared to the graph itself. To show this clearly, we introduce dense graph and empirically test the relationship between the number of trees and the final performance. We construct the graph by adding many edges to the Cora dataset (100 extra edges for each node), while maintaining the vanilla edge homophily rate p (adding a homophilous edge with probability p and a heterophilous edge with probability 1 - -p). The results are shown in Sec. Sec.I.6 We observe that the addition of extra trees can further improve performance compared to using only few. However, introducing too many trees cannot improve performance and may even slightly degrade it, as they introduce redundancy and would increase the risk of overfitting or weer-smotthing issues. Therefore, even dealing with very densely connected graph, limited number of trees would be enough to encode the essential structural knowledge, without the need to introduce too many trees.
A.9 DISCUSSION ON A CASE WHERE OUR PARADIGM MIGHT UNDERPERFORM
Here, we supplement a discussion with a case where our paradigm might underperform. The case would be highly disconnected graph with too sparse edges. This graph has too many connected components (O(n) components), and each of them is very small in size (0(1) nodes per component). In this graph, our paradigm might fail to extract valuable long-distance knowledge and thereby degrade the final performance, possibly due to its heavy dependence on the pre-processing stage to address the high dis-connectivity. Yet, notably, deep GNNs still have this limitation, while GTs might have some merits in avoiding this issue.
B PROOFS AND DERIVATIONS
B. PROOF FOR THEOREM
Recall the design of our tree aggregator fAge: it is designed based on a general message aggregator
Ja (.). Any Jae (.) can applied here it satisfies the following two sufficient properties:
SS, A, B, s.l., S = BUBBUU A, B B A = 0:
fAgs (S) = M+ (fARE (B), fAge (A)), Property (I)
(29)
fags (B) = SAgE (S) A) .M (JAgs (S), saes (A)), Property (II)
where A, S are sets of messages (e.g., node embeddings).
Two merging operators M+ (ā, 8) and M (z.. b) denote adding (or deleting) vector to (or from)
vector a. Note that the -+/- can utilize auxiliary information and thus are allowed to be unsymmetrical.
Then, we provide the proof of Theorem I as follows:
Proof. Let A H + H' Raxd denote our general tree aggregator, where H, H' Raad denote the node embeddings before and after aggregation. Let node r e V is the root node of tree T.
First, we prove Recursion (I). Consider a node u E V: the notation S, denotes the combination of all messages from the subtree (sub)) (nodes v((uub). Note that all such messages will either pass
23

---

Published as a conference paper at ICLR 2026
through one of the children nodes Child (u) (denoted as u) or be generated from itself (i.e., g (H.)). Provided that node u has K₂ children on tree T, we can classify the aforementioned messages into K,, + categories. At each one of the first K,, categories (aussming passing through the child v), messages are merged into S.- Merging these K2 + catergories, i.e., (Sa ) veChild(x))) U {9( H.)), which naturally derives Recursion (I), concluding the proof. Therefore, one can easily pre-process all S, for all E V with the simple recursion, i.e., Recursion (I). Then, will assume that all S, known.
Second, we prove Recursion (II). Recalling the observation we found in Sec. 4.3 and the intuitive visualization in Fig. 7 we can obtain: the globally merged message at node (i.e.. HD) and that at its father node Fa (2) (i.e., Hate)) differ only at the direction of one edge
(v, Fa (v)). other
words, the messages arriving at node partially pass the edge Fa (v) + v, and those at node Fa (v) partially pass
Fa (v)). Thus, if we delete the edge e, the left messages nodes and Fa (v) (denoted as S, and (Fa()) are from a subtree (aab (i.e., nodes v.(eub) and from its complement set (i.e,, nodes V (((nb)),, respectively. It means that Hy and Faaco) are formed by exactly the same two parts with different merging directions, which can be formulated as follows:
H MM (Se: SEaco)
(30)
H Pa(o) = M (S%acco) 5s)
(31)
The above insight allows us to derive an recursion that directly connects H. and Hatoo Provided with S,,, according Properties (I) and (II), can first inverse Eq. 31 easily calculate Sa(o) from Pa()) by taking .M- (-, Sy) at both of its sides:
Spa(e) M (M+ (Sesco) S.). s.) M (Heatoy) S.)
(32)
Note that we can combine Properties (I) and (II), which implies that:
M- (M+ (p, 2), 9) =
(33)
In other words, we first add q into p (obtaining p q) and then subtract q from p + q, then we will obtain p itself, showing the invertability of M and M
Then, injecting Eq. 32 into Eq. 30 provides us with Recursion (II), i.e. Eq.
V
==
(S.. M (HE))))) S.))
Recursion (II)
(34)
Putting these two parts together concludes the whole proof of this theorem.
B.2 PROOF FOR THEOREM 2
Recall the theorem we present in Sec. designed tree distribution, iee,, trees sampled from it tend to preserve the first-order homophily ratios. Next, we provide its proof.
Sec. 4f6 the main text, which justifies the quality of the specifically
Theorem 2. Let & be any connected graph, and define the expected edge homophily ratio under the score ratio A p/q 0 as:
R₂(A) = pop [h(T)),
where (TT) is the edge homophily ratio of tree T. Then there exists Ao such that:
Monotonicity, If A Ag, then
Ra(A)>Ra))
Upper Bound. For all A > Au.
N -
R₂(A) S1
n-1
where (HCC(G) denotes the number of homophilous connected components of G.
24

---

Published as a conference paper at ICLR 2026
Asymptotic Tightness. As A - toc,
NHCC(G) -1
R₂(A) + 12
Proof. Based on an introduced homophily indicator function Iihomo (-) denoting wether an edge is homophilous, we can define the first-order homophily ratio of a tree T of size n (assuming it is sampled from a graph G = (V, E') of n nodes and m edges), i.e., ((T), as follows:
((T)=
Thomo (e):
(35)
12
CET
where Ihomo (e= (u v)) Denote as T (G)) the space/set of all spanning trees of the graph G. where we suppose G is connected. For convenience, we also define n (T), n mT(T) E N as the numbers of edges in the tree T that are homophilous and heterophilous, respectively. Therefore, based on their definitions, we immediately have:
if node labels Y, Y. I (e= (u+ ++ u)) -0 otherwise.
ATET G n (T) + (T) = n n-
(36)
n (T) I((c).
(37)
EET
Recall the definition of the designed tree distribution pln. 9) (T) < < 1) conditioned on the graph G:
G
Hee [hoooo y2 ((hommo) (e)
V
píp. 4) (T) ETET(O) HETT p (ithomm)(e) (e) g² [(homo))())
(38)
where >> 0 is the score we assign for the homophilous edges, > 0 is the score for the heterophilous edges, and we assume q < p. Then we can analyze the expected homophily ratio follows:
PTppp "(T) (T)]
Σ
pf. 4) (T) (T)
(39)
G
G
n (T)
Σ
plp. 4)
(T)
(40)
G
1
Σ
ple. 9) (T) n (T)
(41)
n
TET(G)
1 p (hommo (6) 9² ((bamoo)) (e)
-nt (T)
n ( Erer(o) HOET. pl(baroo(()) 9² [(hamo))
(42)
1 Exer(a) HETT D (homos) (c) - ((hhmmo))) (e) n (T)
(43)
n 1 Erer(E) HeET p Whomo) (e) -- ((hom))) (c)
Due to the fact that:
II p eET
Chomo)
g [homo) (T) (T) gr (T)
(44)
Injecting Eq. 44 into Eq.
43 we can obtain:
ΣtET(O) (T) gm nn (T)
E Ew
plr (T)) 1/1 (T)
(45)
Eree(G) ppt(TT) 9.r (T') (T')
n
25

---

Published as a conference paper at ICLR 2026
According to Eq. 36 we have:
n (T) = n 1 - (T).
(46)
Injecting this into Eq. 45 we can obtain the following formula:
E P ((r) [h (T)) = ΣTET(G) pp)((()) (T) (p n (T) We can cancel out the term qn11 and then get:
(47)
E (r pat(T) -n-1-n (TD)
PT (T) [h (T) 1 E pr q nn (T)
(48)
(r pn q-n
0
ETEN(O) (2)ml(( .n* (T)
(49)
Even(() "T(T))
Let P >>>>> 1, then have: 9
ETET(G) Ant(r no (2) E T~ (T) (T) n ETer(G) Ant(r))
(50)
Observing this formula, we find that can both the numerator and the denominator as polynomials of the variable À > 1. Moreover, they have different coefficients for different terms: all the terms of the denominator have exactly the same coefficient, i.e., 1, while the term t of the numerator has the coefficient + (T), which hints at us to disentangle the constant.
Denote the maximum value of n+ (T') as nitax and the number of n² (T') among all trees T in T (G) as N (n+ (T)), formally:
N (no) # # {T: TE::TT(( (G) n (T) =no
(51)
n max TeT(G)
max n (T).
(52)
Based these notations, reformulate Eq. 50 as follows:
1
N.
E Eywple (T) [h (T)
(53)
Σxzo N
n
For ((k)= > O, kimax = N+ max the above equations:
We can disentangle the constant
Amax Nikmaxi
kmax
N from max
N (Kemax)
Σnzo .
1
E E 5 orr [h (T))
N max
N max
(54)
ΣxZO N
Exzo Nh. k. (k)) EE2O A N (k:) N+
1
N+ max
max
Σx20 X . (k))
(55)
Exzo 2 (N -k) N (k)
N+ max
(56)
1
NE. ((k)
Enshent
A (Nitax kt) N (k)
1
N+ max
(57)
EOCKS N N..N. (k)
Observed from the above equation, the order of the numerator LockeN# N *N.N max N is less than N T but the order of the denominator E Losk No A N (k) exactly N+ - Therefore,
26

---

Published as a conference paper at ICLR 2026
the order of the numerator is less than the order of the denominator. Thus, intuitively, as À + to0, the growth rate is much faster than that of the numerator. There must exist constant λ satisfying
that when Au the fraction part of the above formula LaskeNt (N -R)-(() -R)-N()) increases. Thus, the proof of part (1) the theorem concludes.
decreases as
DuSASN NF.N(K)
To prove parts (2) and (3) of the above theorem, should further prove that:
N
max = (NHCO (?) -1) (n (m=1)) 1).
(58)
n
immediately follows and only
N max
NHCC (G)
(59)
Suppose the graph G has Nи NHCC è numbers of homophilous connected components (i.e., considering only the homophilous edges) C1,'.. .NN N is the maximum value of N+ (+) Eegr ([hemmo) (e). This fact means that N is the sum of weights contained in the maximum spanning tree of the graph G with the weights [(homo) (e). Considering the Kruskal's algorithm we sort all edges of G according to their weights, which means that all edges e with [hhom) (e) will be considered first. The rest of the edges with weights have no influence on the answer the maximum spanning tree question.
All edges with weights 1 are divided into NE components. Each component has a mutually indepen- dent solution. The answer of the component C; (i E [1, Nn)) is obviously |C;] F 1, since adding any further edge will cause a circle. Therefore, we have:
NH
NH NH =n NN = n NHCC (G).
N+ MHX
(1C - 1) Σ Call
(60)
which shows that Eq. 59 follows.
Injecting Eq. into Eq. 57 concludes the proof the theorem.
B.3 PROOF FOR THEOREM
In this subsection, we provide the rigorous proof for Theorem 3 which heavily based on the monotonicity analysis of s with Respect to Maximum Degree M.
Proof. According to Lemma T and Lemma we can derive the following formula for the lower bound of s (-):
8
(61)
1-2 2.
M M (1 - 3) + b)
log
max, dit. E emnn ddz
where M = max d, and = D(G) 2 4.
First, simplify the denominator part involving M:
1- VM -
2
2 D
1
+
M
D)
2( 2(VM -1)
2
1
+
M
D
D
M -((VM 1)
4(VM M - 1) 2
+
M
MD
D
M -2VM +2
4VM 4 2M
+
M
MD
27

---

Published as a conference paper at ICLR 2026
D(M - 2V 2) + +4/M - 4
MD
Thus, the formula for can be rewritten as:
MD
82 (D(M - 2VM 22 + 4v M 4 2M) log
(62)
max; vd emin, Vd,
To analyze the monotonicity of s with respect to M, define:
MD
(63)
D(M 2VM +2) 4vM 4
and compute its derivative
dy ZM
Using the quotient rule (:) 4 + 2M:
a'v-av' 22
where u = MD and v D(M 2 + + 4VM
First, compute
d'
d
DDMM 2 + + 4v M + 2M
dM
= (1
2
+
+
VM
V
M
Then, compute y':
y = D D MD m'
22
D D(M 2/M +4VM - 4+ 2M
MD D
)
+
JM
v
Simplifying the numerator:
Numerator D VM + 2D2 + 4DVM 4D 2DM
- MD + MD. D
1
2MD
2MD
VM
VM
= -D² D2) D2MM + (-202 + D +4D 2D) VM 202-22220
= =(-D² + 2-2DDDVMM +2D -DD
=-D(D 2) +DD(D 2)
D(D (2 - VM).
Thus, the derivative simplifies to:
D(D- 2)(2 VM)
y/ -VM +2) 4VM + 2M)
(64)
Given 2 4, we have D 2 0 and 0. The sign of y determined by VM:
When M < 4, 2 - VM > 0 = y' > 0, so is increasing.
When M = 4,2 VM- = 0 = y 0, so y reaches a critical point.
When M 4,2 M <0 y' 0. y is decreasing.
28

---

Published as a conference paper at ICLR 2026
Therefore, the lower bound of first increases and then decreases with respect to the maximum degree M, reaching its peak at M = 4. In our case, we typically have M 2 4 since there exist some nodes with larger degrees than other nodes. Besides, have a graph augmentation before graph learning, which has an effect on improving the maximum degree of nodes, making it more likely to satisfy M 2 4.
Then, to analyze monotonicity of y on D, write:
MD
(65)
D(M 2V + 2) + 2M + +4VM
By the quotient rule, the derivative is:
dy
M(2 + 4V M- -4)
(66)
dD
D(M 2 M + + + 2M + 4vM
For M 2 1, since 2M + 4v M 4 2 2 0, it follows that increasing in D.
dy
0. Therefore, is monotonically
A
Putting two monotonic analyses together concludes the proof of the theorem.
B.4 DERIVATIONS OF PATH DECOMPOSITIONS FOR SOME PARADIGMS
Recall several formulas in Sec. A.2 of Appn.:
H = Agg( (Hu)
= Σ
Σ
H₂ . :((w PE()).
(67)
BEV
PEP PEP (G):
(= (po - s.. u.
Here, w(f) is the path weight for path ý = (po. ,i....,PP...
w(p) Pp
(68)
where Wy-ty is the weight of the directed edge - y- And PE(ý) is extra path-based positional encoding beyond vanilla pair-wise relative positional encoding:
PE(p) fputh- (p. G, [Way) }).
(69)
B.4.1 OTHER PARADIGMS
Infinite-layer deep local SGC, deep local GT, or infinite-step random walk aggregation all have this form (Equation equation 67). The "infinite-layer" or "infinite-step" nature implies that the summation Epep...(G)) Equation equation 66 considers all paths (walks) of any length & from to v. For these models, the components are identified as:
(1) The edge weights Wa-ry used in Equation equation 68 are specified as:
For Infinite-layer SGC (Simple Graph Convolution): Wz+ty = S2y, where S is the normalized adjacency matrix (c.g., S 1-1/2 with Á = A I). The path weight becomes wsGc (p) 11 Sp 18; The full aggregation often takes form like t== H' = (E $55²) Hm or (T - 3S) Hm- The sum over paths in Def. 1, when combined with the PE term, captures this.
shared For Infinite-layer deep local GT (Graph Transformer/AAtentionn) Wy-ty a yz representing a layer-shared attention coefficient for information flowing from x to y (where is the target node in the attention mechanism). The path weight is wer (ū) I
1==1 o P,P5-1"
shared
29

---

Published as a conference paper at ICLR 2026
For Infinite-step random walk aggregation: We-y Tay. entry from the probability transition matrix T, where Tay = P(next node = y/current node = z). The path weight
becomes WRw(D) I1 j - This corresponds to the probability of traversing the
path p. Aggregations like those based on Personalized PageRank Li=o geT inherently over weighted paths.
(2) The path-basa positional encoding PE(ý) for a path ş (Po, (Po.Pr... ......, Pk)) is given by a product of node-specific positional encodings for all nodes along the path:
PE(p) II PE(p:).
(70)
Each node-specific positional encoding PE(p:) defined the sum of the discounted edge weight product in all circles (cycles) C of any length Le that pass through node p;. Let C(ps, G) be the set of all simple cycles containing node p; graph G. It can formulated as follows:
PE(P:)
Σ 8(Lc) CEC(P..G)
II
Wx-ty
(71)
((W)))((C)
where FI(C) are the directed edges forming the eycle C, Le is the length (number of edges) of cycle C, and ö(Lc) is discount factor that depends the length of the cycle (e.g., 6(Lc) - for some 0 < y S 1). The edge weights Wy-vy in this context are the same as those defined above for SGC, GT, RW respectively. This structure (Equations equation an equation (T) demonstrates that these methods focus more on local environmental importance of a path, e.g., densities or degrees of nodes contained in it, captured by the properties of cycles involving nodes the path.
B.4.2 OUR PARADIGM
Tree-Set (i.e., Forest) Layer also has this form (Equation equation 67 with PE(p) as the sum of weight products of all spanning trees of the graph obtained by merging path into single node.
Let G be the graph obtained by contracting the path أ (Po..... Pk:) into a single supernode Up. The edges incident to Up are derived from edges incident to any Pi E in G. Let T(G))
be the set of all spanning trees in G³-- For each spanning tree T E T(G)), its weight product is ( I(T) w/y where w/e are the (possibly re-defined) edge weights in T. The path positional encoding is:
PE(
Σ W(T) =
Σ
w/ eeEET
II
(72)
TET(GG)
TET(G,))
This shows that this paradigm focuses the global transport importance of path, i.e., how connectivity or communication this path can facilitate if it is built as a highway with no communication cost along
C EXTENSIONS OF OUR TREE AGGREGATOR
In this section, we will introduce some extensions of our tree aggregator in Sec. 4.3 which not only shows the potential of the proposed general aggregator, but also reveals how it can be technically combined with other popular techniques, exhibiting some possible future research directions on general graph learning.
C.1 INTEGRATED WITH GLOBAL ATTENTIONS
Based on kernel decomposition, i.e., k(z, y) f(x)² f2)). We can easily inject global linear and even general attention paradigm into our aggregator. In the attention mechanism, k(Q, K)V f(Q)f(K)TV Thus, treat f (K)TV as messages fed into the aggregator. Note that Q need to conduct tensor product with (K))VV. Dimension reduction can be further utilized to reduce the memory consumption.
30

---

Published as a conference paper at ICLR 2026
C.2 FINE- PROPAGATION CONTROL
In this subsection, we design fine-grained propagation control, such as discounting or truncating the distance, which can make the aggregators more flexible and better filter the possible distant noise.
We can discount the distance by introducing a discounting weight and multiplying it by the edge weight. We can truncate the distance by introducing extra variable store how distant the currently embedding aggregates information.
C.3 GENERALIZE FORESTS
In this subsection, we generalize forests to eliminate the need for Recursion (II.. We can generalize the forests to the Directed Acyelic Graphs (DAGs) forests. Each time, we randomly sample one directing solution for each edge and form a DAG. And use a similar tree aggregator to aggregate distant messages and conduct fusion for them. Yet, it needs extra sampling strategy and tools for DAGs, which is still under-developped.
D ACCELERATIONS OF OUR TREE AGGREGATOR
In this section, we introduce some tricks accelerate our tree aggregator.
D.1 SELECTING CENTROID AS RoOT
We can select the centroid node as the root to conduct the recursions trees rather than choose the node 0, since the width of the rooted tree would be larger and the depth of the rooted tree would be smaller. This would facilitate higher parallelizability. For example, when conduct leaf to--ot recursion, multiple threads can be better utilized. The centroid node can be found via two Depth-Fire First Searches, which are efficient.
D.2 DIFFERENT GREEDY STRATEGIES FOR DIFFERENT RECURSIONS
Our recursions can use greedy strategies to improve parallelizability. When conducting leaf-to-root recursion, we can calculate the depth dep (v) and sub-tree depth (sph) (sub) (v) of each node We
treat (sub) (v) as the first key-words and treat dep (v) as the second key-words to sort all nodes.
When conducting root-to-leaf recursion, we can use dep (u) as the only keyword. We can assign
nodes for threads one by one based on i mod N, where N is the number of threads.
E DETAILS OF BLOCK ACCELERATION OF TREE SAMPLER
As described in Sec. 4.2 in the main text and Sec. G of Appn. well as Algorithm 2 we follow some Theoretical Computer Science previous works Wilson (199) and adopt a random walk- based spanning tree sampler. It can sample random tree exactly from the given tree distribution with linear running times in most cases. However, when dealing with larger graphs, a linear time complexity is sometimes not enough satisfy practical requirements. The essential reason that the parallelizability is based on the specific input graph structure. When the graph becomes more dense, a single thread may have a shorter life period, and more threads needed. Yet, when more threads simultaneously work at nearby locations in graph, they may interfere with each other. For example, supposing that two threads produce two paths P1 and P2 after circle/loop stripping, Pi and P2 can intersect many times. To maintain the correctness of this sampler, we must drop some parts of these paths, which definitely causes computational waste to some extent. More severely, as the multi-threaded working paradigm proceeds, the under-explored area in the graph becomes much localler (akin to some smaller connected components), and a nearby environment, the number of threads must be reduced (otherwise the useless walk/path would frequently occur), which reduces the parallelizability.
In this section, propose simple trick (i.e.. Algo B) which calls the vanilla Tree Sampler (i.e., Algo 2) with some extra tools and intuitively improves its parallelizability with only limited precision sacrifice. In other words, propose conduct approximate sampling with ignorable deviations, yet
31

---

Published as a conference paper at ICLR 2026
make better use of modern architectural advantages. We describe some specific details in Algo. For the convenience of implementation. Furthermore, we provide detailed explanations of the algorithmic pseudo-code in Sec. [ of Appn.
The key idea is to identify some unimportant edges in the original graph and attempt to drop them or least some of them. If the graph can be divided into several disconnected parts, we are then allowed to conduct a separate tree sampling for each of them.
How to integrally achieve this end poses a challenge, especially considering we expect to minimize the number of dropped edges. To demonstrate our motivation more clearly, we consider solving the problem starting from simple greedy strategy. Since we already know the importance score of each edge, i.e., s (recall Sec. (.c. natural heuristic greedy strategy is to sort all edges by the edge scores ascendingly and then drop the edges one by one until the number of connected components achieving the pre-defined number, e.g., Kg. However, the significant issue of the greedy strategy is that to achieve the number Kg. we may risk dropping too many edges. Despite the fact that some of these dropped edges are low-score, the cumulative effect cannot be ignorable. To understand this, consider the following example with K = 2. Suppose that we have an n-sized random tree T which is uniformly sampled from an n-sized complete graph. We label all edges in T with edge scores 1. Assuming n is even, we can find the two centroid nodes of the tree T and denote them as nodes u and c. Cutting the edge u ++ e would cause the tree T to become two parts. We denote the left node set and the right node set with notations Viett S V and Vright S V. We then continuously add edges with uniform random edge scores between 0 and 1 (i.e., 8 (e) Uniform (0, 1) and 0 < 1) to the Veet-in Vien-induced subgraph (denoted Gient) and the Vrigh--induce subgraph (denoted Gright) until both of them becoming complete graphs. Next, we consider the solution derived from the above greedy strategy for the constructed graph G. It will drop all the edges with scores smaller than 1, i... all the edges that are added after sampling the initial tree T, and then drop one of the edges in T. An obvious issue of this method is that the sum of all the dropped edges would be too large to ignore their cumulative effects. In fact, the expected sum of the dropped edges is (n²). On the other hand, the optimal solution of the constructed graph G is obvious, i.e., deleting the single edge u ++ u with the total edge scores equaling 1 (i.e., O (1)). From another perspective, we expect the obtained two components are relatively balanced, i.e., |Vent ~ |Vightl The optimal solution follows this requirement, yet the greedy strategy may fail to achieve this, due to the randomness of the sorting algorithm for those edges with exactly the same scores.
Therefore, based on the above analysis, we can outline the conditions that we expect the graph division technique holistically satisfy: (1) The divided parts are expected to be maximally balanced. (2) The number of dropped edges is expected to be minimal. (3) The sum of scores of the dropped edges is expected to be minimal. We notice that these conditions are almost the merits of some graph cut techniques, e.g., METIS library Karypis & Kumar (1998), which is treated as an operator (denoted as GraphCut (-)) called in the first step of our algorithm.
After obtaining the several components split via GraphCut (-), we call Algo. 2 to separately sample a tree for each component and then we obtain several trees Ti, .... TKg. However, how to merge them and how to consider the dropped edges remain challenging. To this end, we propose to collapse each component to single node labeled with the component label (i.e., the block number, labeled, e.g., between 1 and K B). Then all edges between these components (i.e., blocks) can be re-labeled with their end nodes' block numbers and will become multi-edges connecting two newly labeled nodes. For example, vanilla edge 73 <+ 254 would become 4 ++ 7, where 73 and 254 are two vanilla node labels as well as and 7 are two block numbers (i.e., two new labels of merged/collapsed new nodes, 73 comes from 4-th block, and 254 comes from 7-th block). Along this way, we can obtain a highly collapsed small graph with exactly Kg nodes and many edges coming from vanilla edges connecting two different blocks/components. We call this new graph G'. It contains no self-loops since we drop all intra-block vanilla edges (note that when sampling Ti, ..., TKg we retain only these edges and drop all the other edges). It also contains many edges that connect two same pair of nodes (new nodes), which we call multi-edges. We then merge a multi-edge (containing many edges) into a single edge, with its edge weight as the sum of vanilla edge weights. Here, our idea is to sample a tree for this new graph G', and then down-sample a selected tree edge (corresponding to a multi-edge before merging) into a vanilla edge contained in the corresponding multi-edge. This process can be proven equivalent to directly sampling a tree for the new graph with repeating edges that have different edge weights, where the latter cannot be conveniently implemented via directly calling Algo. 2
32

---

Published as a conference paper at ICLR 2026
The edge down-sampling process requires to simultancously conduct multiple (exactly KB) sampling operations from variable-length categorical distributions. For example, we are required to parallelizably sample from the categorical distribution [3 1. $1 and at the same time, sample
from another distribution with different length, e.g., [ $.. This makes GPU-level parallelization
inconvenient. The challenge can be addressed via a Gumbel trick, described below. We first normalize the edge weights in each first-order neighborhood to construct each categorical distribution. This step can be done via a Scatter Add operator to efficiently calculate the sum of first-order edge weights. Then, we compute the log values for all probabilities and add element-wise Gumbel random variables, ie., - log (- log (4)), L ~ Uniform (0, 1). Next, the most key step is conduct Scatter_Arg.Me (.) operator to allow the sampling distribution to have different lengths, which is significantly beyond vanilla ArgMax (.) after some operation such
reshape (-). Through these steps, we can efficiently conduct edge down-sampling and obtain a new tree with vanilla node labels (between 1 and n). We call this tree Tg. Merged with other obtained trees, ie.,Ti, , ,"" TKm can obtain the final tree T = M ((Zi)welo, Ky))
F DETAILS OF ALGORIHTS
In this section, we provide several algorithmic pseudo-codes support the detailed implementations of our main framework, as well as some discussions in other sections of this Supplementary Mate- rials. In each algorithm, we will shortly provide a description of this algorithm, the input/output, important
learnable parameters, and other notes on, e.g., some extra definitions or clarifications of symbols or operators, as well as some tools called from another library. In the corresponding subsection of one algorithm, we will provide line-by-line explanations to detail the specific implementation, including some notable points.
F.1 ALGORITHM OF OUR FRAMEWORK
We provide detailed introduction part by part in Sec. 4 the main text. Next, we will provide an algorithmic pseudo-code (i.e., Algo. T to connect these parts from a more holistic perspective for better understanding.
Furthermore, we will provide a line- bine-by-line description for this algorithmic pseudo-code (i.e., Algo. follows:
Line extracts some knowledge from the non-attennion--assed model To via pretraining. In our implementation, for simplicity, we select single-layer GCN/MLP for our To show our true potential (rather than based on powerful candidates). Also, K, is treated as direct node predictions, i.e., node label prediction probabilities. Other implementations may also be acceptable or better.
Line 2 augments the vanilla graph into an augmented variant, based on the extracted predictions Kg (note it is optional). The main motivation is to make the graph connected and to improve the initial homophily ratio or its NHCC ( especially for heterophilous graphs ). A simple top-k augmentation is enough to achieve this end (Sec. LD.
Line 3 extracts new knowledge K, from the attention- based model Ti based on the old yet
necessary auxiliary information Kg. The detailed motivation for why we need additional old information Ko to extract new knowledge K₁ can be found in Sec. 4.2 of the main text and Sec. A.5 In our implementation, the new knowledge is modeled as attention coefficients of the module Tı, and thus it also be viewed kind of attention learning.
Line 4, based on the knowledge K,, defines a tree distribution conditioned on the graph G, i.e., Pa (T).
Line + separately sample a tree from the tree distribution Pa (T)). We sample Ny trees in total and these trees can be viewed iid. sample of size Ny from the distribution.
* Line inputs the vanilla graph G as well as its feature matrix X into our Local Submodule (Sec. 4.4) of our architecture, and we obtain the node embedding matrix H Raxd
Line 9 + 11 separately fed the sampled tree Tş well the embedding matrix H into the tree aggregator, and obtain new embeddings H' (1(k) Raxd The tree aggregator will
33

---

Published as a conference paper at ICLR 2026
aggregate distant messages each tree independently. In other words, H (8) on the k-th tree.
H*()) depends only
Line 12 fuses all these node embeddings from different trees into single ones, i.e. H' IRx We directly implement the operator Fuse (-) via simple post-hoc mean fusion. Yet, note that other sophisticated alternatives are options, too.
Line represents residual connection governed by hyper-parameter ? [0, 1]. which controls the trade-off between the local knowledge and global knowledge.
34

---

Published as a conference paper at ICLR 2026
Algorithm Algorithm Our Framework
Description: The holistic architecture of our FGL framework mainly contains four critical steps. Input: an input graph G = (V, F)) with feature matrix E R and normalized adjacency matrix A. the node labels in the training set Yr., graph augmenter Aug (G; K) (to augment graph with some auxiliary information K), a non-attention-bent
graph layer To. an local attention-based graph layer T1, training operator Train (T IK) returning the outputs predictions of the trained auxiliary modules (e.g., To and T1 where auxiliary information K may contain both training labels and training inputs as well testing inputs, tree distribution definer Define (.), and some key technical
components including Tree Sampler TreeSampler (-), Tree Aggregators f (-), and Tree Fuser Fuse (-).
Output: node embeddings H" Baxd
Parame-aasssstes::
81. A2, the hyper-parametens in our Local Submodule (Eq. 9
7, the residual coefficient;
K2 < 2, the number of sub-layers of our Local Submodule;
Nr, the number of sampled trees
Trainable- Paabble-aarameters: learnable parameters in Local and Global Submodules as well as auxiliary modules (layers), i.e., To and Ti
Note: For brevity, here we aim to present the high-level idea, and detailed text descriptions are provided in Sec. of the main text.
1: Kg + Train (To G, Y2)
2: G < Aug (G; Kn)
>> The main motivation is to make the graph connected and to improve the initial homophily ratio or its NHCC. A simple top-k augmentation is enough to achieve this end.
3: K₁ Train
Ti Ka, G, YL
4: Pa (T') < Define (K₁)
Define distribution based on the knowledge K1 (Sec. 4.2).
5: for each E [1, Nr] do
6: Th TreeSampler (Pa (-))
7: end for
8: H + Local (X; B1, B2, G, KI, Kr.) E Baxd
9: for [1, Nr] do
10:
H'(h) +
(Th) Agg
(H) E Raxd
end for
Fuse ([u'(0) RE(1, Nr)
H'
> We directly implement the operator Fuse (+) via a simple post-hoc mean fusion. Yet, note that other sophisticated alternatives are options, too.
13: H" + 7- H' + (1--) И E Rodd
14: return H" E Raxd
35

---

Published as a conference paper at ICLR 2026
F.2 ALGORITHM OF TREE SAMPLER
Recall the brief description of the utilized tree sampler in Sec. 4.2 and a more detailed introduction in Sec. of Appn. To facilitate better understanding. in this subsection, will provide algorithm pseudo-code as well as line-by-line explanations for the convenience of implementations or some possible future extensions and improvements.
We give an explanation of Algorithm 2 as follows:
Lines 1 computes the transition matrix a Markov Chain defined based on edge weights
{seleeg according Eq. 74
Lines 2 randomly generate node permutation aH} with its first element the of the sampled tree in the graph.
Lines 3 - 5 initialize the arrays Next[-] and In Treef]]. The former denotes a temporary linked array pointing from the leaf nodes to the root node of the sampled tree (we treat the temporary tree as a rooted tree with root node alO)). The latter denotes whether a node is contained in the current (rooted) sampled tree.
Line takes the root node a(0).
Line 7 + 23 finds a node E V that is not in the current tree and starts new walk (recall the above-mentioned Markov Chain) from the node (until encountering a node already in the current tree). The walk would contain some repeated nodes, and we should strip all circles or loops to obtain path, Finally, we take the nodes and edges, and merge them into the tree node and tree edge sets, respectively.
Line + 11 attempt to identify a new node that is not in the current tree to start new walk.
Line 12 + 16 sample a walk step by step (each time sampling a node in a categorical distribution) and record this walk in the way of Next pointers. Notably, the iteratively sampling operations implicitly strip all the loops or circles by substituting the old Next (u) with a new value, considering this point from the perspective of linked array, and obtain directed path. The walk (or the directed path) will end at node that is already contained in the current tree, i.e. InTroc[o]] Truc.
Line 17 22 add all nodes and edges in the path into the tree node and the tree edge set, respectively.
Line 24 returns the sampled tree.
36

---

Published as a conference paper at ICLR 2026
Algorithm 2 Algorithm of Tree Sampler
Description: Given a positively weighted directed graph G, define a tree distribution conditioned on graph G as Pg (T), with the unnormalized score equaling the product of all edge weights in tree (Recall Eq. 2 in the main text). Return a spanning tree of graph G sampled from Pa (T'). Check Sec. for the line-by-line explanations of this algorithm.
Input: a graph G = (V, E) with first-order neighborhoods (No)eEv (or equivalently the adjacency list G), edge weights s = {s (E)}eE where e E E is a undirected edge of graph G
Output: the T Pa (T) with T = (V1, Er), where Vr and Er denote its node and its (undirected) edge set, respectively
Note: (1) Next [v] is "next" pointer directing the next node after node e, noting that it implicitly includes a loop-striping process. The Next [-] operator with Head node defines a linked array, representing a random walk. Since implicitly includes loop-stripping process, the above random walk is essentially path. In'Tree [u] E {'True, False) denotes whether node e is in the current tree.
(2) This tree sampler can be highly parallelized via, e.g., the OpenMP library https: / www. openmp org/ Besides, it can naturally support simultancously sampling multiple trees. We also provide block acceleration trick (Algo. 3. which can further improve parallelizability with only an ignorable deviation from standard sampling.
1: Calculate Markov Chain (transition matrix) based on the edge weights recalling Eq, 74
8 (e = (i ++ j))
Pi--j
_ s(e') [].
(73)
2: Generate a random permutation of = {vo, V1 ... Un-1), i.e., a [t], where n = V..
3: for each E V do
4: Next [u] t 1-1, In'Tree [v] <- False
5: end for
6: In'ree (a [0]] <- True, Vr [a[0), Er +- 0
7: for each t [0, do
8: U U+ u+alth a[t],
+
9: if In [u] then
Continue
11: end if
12:
while In Tree (r] False do
13:
+ Sample (u: (Po-NtuEN..)
14:
Next [u] +
15:
16:
end while
17:
while In Tree [va] False do
18:
InTree [vo] True
19:
Vi < Vr U {ma)
20:
ET ET U (vo Next [vo]]
Uo + Next [vu]
22:
end while
23: end for
24: return T (VT, Er)

---

Published as a conference paper at ICLR 2026
F.3 ALGORITHM OF BLOCK ACCELERATION OF TREE SAMPLER
As introduced in Sec. E we propose a block acceleration tree to improve the parallelizability of the tree sampler (see Algorithm 2, which can be efficiently and conveniently implemented via Tensor operations (using Torch library htttps://pytorch:: org/) as well as some other tools.
We give an explanation of Algorithm as follows:
Line call the GraphCut operator to cut the graph into several blocks and return the block numbers of all nodes in V. where BlockNo (v) denotes the block number of node V. The motivation can be found in Sec. [ for details.
Line 2 calculates the new edge index of the graph G with new node labels, i.e., block numbers.
Lines 3 - obtain the edge index and the corresponding edge weights inside each block.
Line 7 obtains the edge mask indicating edges between blocks. These edges are essentially edges in G", but note the node labels.
Line + 9 obtaín vanilla edges and weights between blocks.
Line 10 relabel the between- blookk edges (i.e., the edge index) inside G' (recall Sec.
Line 11 merges multi-edge into a single edge. The weight of the single edge is the sum of the edge weights of vanilla edges contained in this multi-edge.
Line 12 14 calls the operator TrecSampler (-) to separately sample a tree for each block, including the special block O, which takes blocks as new nodes.
Line 15 + 16 compute the row index of each related edge positioned in the edge index of the tree To. which is also the ID of a multi-edge. Each related edge is contained in multi-edge and can be numbered with the ID of the multi-edge. In other words, Index [i] = j represents the i-th related edge (relabeled with the respective block number) corresponds to the j-th tree edge in block 0 (i.e., TreeBlock [0]) Each tree edge in TreeBlock [0] (i.e., an above-mentioned single multi-edge) corresponds to many relabeled edges (called related edges).
Line 17 selects all the related edges. The edge index has many repeating rows, e.g., [3, 5), [3, 5], [3. 5), where 3 and 5 denote the 3-th and the 5-th collapsed nodes (i.e., block numbers). Note that they represent different vanilla edges.
Line 18 selects those edge weights. Different repeating rows in the edge index may have different edge weights, since they are essentially different edges, yet with the same pair of end node block numbers.
Line 19 calculates the edge weight of multi-edge as the sum of all the related edges it contains. For example, there are numbers of [3, 5]s with edge weights 80, ....... 96, and then they will be merged into single edge (a multi-edge) with the weight s Σi 8;. Now, there is only one copy of [3, 5).
Line 20 represents a normalization operation, which can calculate n categorical distributions with possibly different lengths.
Line 21 represents Gumbel sampling step. We calculate the log values and add inde- pendently sampled Gumbel variables to them. Please refer Jaagg al. (2016) for detailed introduction to Gumbel sampling or the Gumbel Softmax trick, which is popular for categorical sampling.
Line 22 is the most key step. We utilize the operator Scatter_ArgMan (-) to select the maximum element for each group simultaneously. which is typically much more efficient than those less-optimized simple variants of practitioners.
Line 23 concatenates all the trees from different blocks (i.e., To, .. TTe into single tree T, which is our sampled tree.
Line 24 returns the tree T.
38

---

Published as a conference paper at ICLR 2026
G DETAILS OF EFFICIENT TREE SAMPLER
Restricting the tree distribution into such a parametric class (Eq. 2 has another benefit, L.e., it has deep connection with extensive prior studies on random spanning trees Theoretical Computer Science Wilson (1996); Broder (199); Kelner & Madry (2009); Durfee et al. (2017); Wilson &
Propp 1996). Sampling such trees conditioned on a given graph can be achieved via different techniques, e.g., determinant calculation/Matrix Tree Theorem, random walk Wilson| (196)), and effective resistance Durfee al. (2017). For simplicity and implementation convenience, we follow the study Wilson (199)) and adopt random walk-based tree sampler (demonstrated in Algorithm 2 maintains real-time tree node and edge sets Vi and Er, and at each iteration, find node o Vr and start new random walk W. from (i.e., W. = (v 21
e²)) until encountering a node v E Vr. The walk W. is produced following the Markov Chain induced from the edge scores {s (c)) ie::
s (e (i++ 5))
Pi-j
Ee= s(e')
E [0,
(74)
After loop stripping, all nodes and edges contained in W LoopStrip (WW) are merged into V and Er, respectively. More details are provided Algorithm 2 This sampler is simple and efficient with only O (T (p)) running time, where 7 (p) denotes the expected hitting time of two random nodes u, E V sampled from stationary distribution Tp of the Markov Chain p (Eq. (74):
T (p) = Eu Step (u - u) = Σ Tp(u)= Tp(u) Step (u + v) M,VVV
(75)
where Step (u - v) denotes the expected number of steps for a random walk from node u to (hit) node v at the first time. As pointed out in Wilson (1996), O (T (p)) 2 O ((VI) for most random graphs, which is much faster than their cover time (lypically O (VV log [V[)). Notably, it can also be parallelized and sample multiple trees simultaneously. Moreover, we propose further optional block acceleration when dealing with very large graphs (detailed in Algorithm and Sec. Se Appn.) with Graph Cut technique and Gumbel-Softmal edge down-sampling, which sacrifices only some unimportant low-score edges.
39

---

Published as a conference paper at ICLR 2026
H SET OF MOTIVATION EXPERIMENTS
In this section, we will provide some motivation experiments, whose results will justify some parts of the design of our framework.
H.1 STUDIES EFFECT HOMOPHILY ESTIMATION GENERALIZABILITY
Based on Fig- g can be clearly seen that as the accuracy rate of the homophilous estimator increases, the performance on all our datasets consistently and continuously growing. Moreover, in extreme cases, when the homophilous estimator has absolute performance (with an accuracy rate of 1), the precision of all datasets also reaches 1. Thus, it can be proved that when we find better homophilous obtain better generalization performance, and there is bottleneck. Therefore, tells us to pursue the quality of the homophilous estimator rather than randomness.
estimator,
Meaunacuragy
Mean Accuracy
Standard Deviation
Standard Deviation
Mean Accuracy
Accuracy
15
12
(a) Cora
(b) Pubmed
Meannmmaraty
Mwar Actewcy
Standdedd Devitiio
Slandar Devisiio
Mean Accuracy.
Accuracy
(c) Actor
(d) Cornell
Figure 8: Effect of homophily estimator accuracy on model performance
40

---

Published as a conference paper at ICLR 2026
H.2 EFFECTS OF PREDICTION-BASED GRAPH AUGMENTATION ON NHCC
We conduct study on how the graph augmentation affects the values of NHCC. As illustrated in Fig. 2 the distillation-based top-k augmentation strategy (Sec. D can effectively improve the NHCC values (i.e., the number of homophilous connected components), which are the theoretical upper bounds of our designed ideal tree distributions.
1400
NHCC
Enhanced edge count (per node)
Enhanced edge count (per node)
(a) Cora
(b) Pubmed
MHCC
1000
NHCC
0.50
1800
150
800
400
Enhanced edge count (per node)
Enhanced edge count (per node)
(c) Actor
(d) Cornell
Figure 9: Variation of NHCC with graph augmentation edge numbers. Discussed in Sec. H.2
41

---

Published as a conference paper at ICLR 2026
H.3 STUDIES ON DEGREE IMBALANCE ISSUE OF SIGMOID EDGE ESTIMATOR
There is an important alternative comparison for the definition of tree distribution scores mentioned in in Sec. [4.2 of the main text. If modify the score definition sample based the edge weights of the embedded inner product sigmoid, the generated tree will face a serious degree imbalance problem. This imbalance phenomenon stems from the fact that the sigmoid function tends to generate a polarized weight distribution, resulting in some nodes receiving excessive connections and attention while others are ignored or marginalized.
The proposed tree sampling distribution can effectively alleviate this problem and achieve an improve- ment in degree balance nearly 40% for most moderate-sizee graphs. In terms of implementation, we adopt the variance of the node degrees the tree as the key metric to measure the degree balance, i.., the smaller the variance value, the more uniform the degree distribution between nodes and the more balanced the tree structure. Formally, the metric of node degree imbalance can be formulated as follows:
videgree)
Vivi
Σ (de dd) NEV
(76)
where d, is the degree of node E V and d = M Evey de-
Fig. 10 indicates that the spanning tree generated by the traditional sigmoid sampling method based on the embedded inner product has a relatively high degree variance, reflecting serious structural imbalance. Sampling trees from this distribution significantly reduces this variance, leading more uniform node connections in the tree structure. The improvement of this degree balance not only helps to avoid deviations in the process of information aggregation, but also ensures that each node in the network can obtain relatively fair information dissemination opportunities and the richness of information, thereby enhancing the expressive ability and generalization performance of the overall model.
Sigmoid 23.4475
Ours
Sigmaid Inner Product of Embedding
Degree Variance
Ours 15.6117
Sigmoid 6.9282
Sigmoid 7.0050
Sigmoid
Ours 4.5505
Ours
5.9588
Cora
Actor
Pubmes
Comell
Datasets
Figure 10: Degree variance comparison of two sampling methods on four datasets. The solid columns represent the method we proposed, and the diagonal columns represent the sampling method based on the sigmoid value of the inner product between node embeddings.
42

---

Published as a conference paper at ICLR 2026
1 MORE DISCUSSIONS OF EXPERIMENTS OF EFFICIENCY COMPARISONS
In Table we present a comparison of the running times of different models across multiple datasets. These datasets encompass graph-structured data of varying scales and complexities, facilitating comprehensive evaluation of each model's 's efficiency. As observed in T our method achieves the fastest running times across all evaluated datasets. Specifically, several GTs (GT. SAN, Graphormer) encounter out-of of out-of-memne memory issues on larger graphs like Flickr and ArXiv, while our method scales efficiently to these datasets. For computationally intensive methods like ANS-GT and GOAT, which require over second per epoch even on small graphs and escalate to 20-50+ seconds on larger datasets, our method maintains sub-0.02 second runtime on small graphs and only 0.246 seconds on ArXiv. Even when compared to recent efficient GTs like SGFormer and DIFFormer, deep GNNs like GCNII, our method demonstrates 2-5x speedup across different dataset scales. This outcome aligns with the theoretical complexity analysis conducted in Sec. 4.4 affirming that method holds a computational complexity advantage in practice.
J SUPPLEMENTARY EXPERIMENTS
In this section, we provide some supplementary experimental results for a better understanding of our graph learning paradigm and framework.
J.1 HYPER-PARAMETEE STUDIES
In our experimental implementation, there are several key hyper-parameterd that have significant impact on the model's performance. First, there is the tree quantity parameter Ny, which determines the number of trees included in the forest model. Under certain quantity, the prediction performance of the model will improve as the value of NT increases. However, when N1 reaches a certain quantity, the performance improvement will stop even decline, and the computational complexity will also increase accordingly. Therefore, it is necessary to find the optimal balance point between model performance and computational efficiency.
Secondly, there are the parameters 31 and 32. These two parameters jointly adjust the contribution weights of different sub-models in the All-In-One Local Layer. 31 controls the influence intensity of the first GCN, while 32 regulates the contribution degree of the attn model. By adjusting the propor- tional relationship of these parameters, the optimal fusion among different model components can be achieved, thereby improving the overall prediction accuracy.
Finally, there is the residual parameter y. It is responsible for balaneing the importance weights between the Forest Layer and the Local Layer. A larger value will enhance the influence of the Forest Layer, making the model focus more on long-range information. And the smaller value will highlight the role of the Local Layer, allowing domain information to have more significant proportion.
43

---

Published as a conference paper at ICLR 2026
J.1.1 THE STUDY ON THE NUMBER OF TREES, i.e., Nr
In the experiment on the number of trees K, tested the impact of different numbers of trees on the model performance on four different datasets. To ensure the fairness and reliability of the results, we conducted experiments on five random seeds and calculated the mean and variance, which are all reflected in Fig.
The experimental results show that the number of optimal trees on different datasets is fixed, but it often falls within the range of 6 to 10. We find that there is an obvious trade-off relationship in the number of trees: When the number of trees is too small, the model faces the problem of insufficient information richness and is unable to fully capture the complex patterns in the data; When the number of trees too large, it difficult to ensure that each tree maintains a high quality standard. Trees of lower quality will aggregate incorrect information to nodes, thereby leading to decrease in the overall prediction accuracy. can be clearly observed from the line graph of the experiment that the performance curves of all datasets show similar trend: The model performance gradually improves with the increase the number of trees, and begins to decline after reaching the peak. is worth noting that while the performance declines, the variance of the model's prediction results often increases accordingly, which further confirms that the negative impact of too many low-quality trees can reduce the robustness of the model.
Moan Accuracy
Moan Accuracy
Standard Deviation
Standard
Pubmed Accuracy
Cora Accuracy
Number Trees N:-
Number of Trees (b) Pubmed
(a) Cora
Mean Acturacy
Arsunrrrr Standard Devation
Standard Devitioo
Comell Accuracy
Actor Accuracy
Number of N7 (c) Actor
Number of Trees
(d) Cornell
Figure 11: Model performance with varying number of trees.
44

---

Published as a conference paper at ICLR 2026
J.1.2 THE STUDY ON THE HYPER-PARAMAN PARAMETERS OF LOCAL SUBMODULE, i.e., $1, B2
the in-depth study the parameters 31 and 32, we discovered an important phenomenon: Different types of datasets show obvious preference differences for the architecture design of the Local Layer, and this preference pattern directly reflects the inherent graph structure characteristics of each dataset.
Two completely differrnnt optimization modes can be clearly observed from the experimental results of the Fig. [2 For the two homophilous graph datasets, PubMed and Cora, the model performance shows significnnt positive correlation with the value of B1 the higher the proportion of [3.. the better the model performance. It is particularly notable that when 31 and 3g approach O simultaneously, the performance of both datasets has decreased significantly. The fundamental reason for this phenomenon lies in that at this time, the Local Layer degenerates into the traditional multi-layer Perceptron (MLP) structure, and MLP unable effectively handle the strong correlations and neighborhood dependencies among nodes in homophilous graphs.
9.
0,4.5
Wean
05
8.7
R
(a) Cora
(b) Pubmed
(c) Actor
(d) Cornell
Figure 12: Heat map of the influence of parameters 91 and 8n on the model performance of the four datasets. (a) Cora dataset, (b) PubMed dataset, (c) Actor dataset, (d) Cornell dataset. The depth of
color represents average accuracy rate. The horizontal axis B, and the vertical axis is (3.
In sharp contrast, the two heterophilous graph datasets, Coreell and Actor, exhibit completely opposite optimization characteristics. Both these two datasets achieve the best performance under the condition that 31 and 32 are both 0, fully demonstrating that the heterophilous graph structure more suitable for using MLP as the architectural choice for the Local Layer. This is because in heterophilous graphs, adjacent nodes often belong to different categories. Traditional graph neural networks are prone to interference from neighborhood noise, while MLP can better capture the feature information of the nodes themselves.
Further analysis also revealed the differences in sensitivity among the datasets: The Actor dataset sensitive the changes in the ratios of 31 and B2 compared the Cornell dataset, and the
45

---

Published as a conference paper at ICLR 2026
performance degradation significant when the parameters deviated from the optimal values. Relatively speaking, our method shows stronger robustness on the Cornell dataset and has a larger fault-tolerant range for parameter selection.
J.1.3 THE STUDY ON THE RESIDUAL COEFFICIENT, i.e.,
The parameter 7, as a key parameter in the model, responsible for balancing the weight distribution between the remote information (Forest Layer) and the short-range information (Local Layer). Through systematic experiments on the dataset, we observed consistent and significant forms and patterns of performance changes.
Based on the observation of Fig. 13 whether overly relies on short-range information or overly emphasizes long-range information, it will lead to significant decline in the model performance. The performance curves of all datasets show a similar inverted U-shaped trend (with different peaks): As the 7 value increases, the model performance gradually improves first, reaches a peak certain specific proportion, and then begins to decline. This phenomenon fully proves that balance point needs to be found between long-rut oong-range information and short-range information in order further exert the performance of the model. However, even if the overall trend remains consistent, we can
EX2
Moan Accussy -
-Q Moan Accuracy
Standard Dasition
Standerd Devition
Pubmed Accuracy
Cora Accuracy
0.0
6.79
6.3
176
078
035
Alpha Residual
Alpha Residual y
(a) Cora
(b) Pubmed
Meen Accuracy
Meart Accunacy
Standard Deviation
Standard Devition
Comell Accuracy
Actor Accuracy
1.1
6.2
174
Alpha Residual
Alpha Residual
(c) Actor
(d) Cornell
Figure 13: The curves of the model performance varying with the parameter y the four datasets. (a) Cora dataset, (b) PubMed dataset, (c) Actor dataset, (d) Cornell dataset. The purple solid line represents the average accuracy rate, and the blue shaded represents the range of standard deviations.
clearly observe that different datasets have different degrees of dependence on long-range information and short-range information. This difference reflects the inherent graph structure characteristics of each dataset. For example, the Actor dataset shows stronger dependence remote information compared to other datasets, and its optimal y value is significantly biased towards remote information. This preference may stem from the fact that the ding-iitance dependency relationships among nodes in the Actor dataset are more important, and a tree structure is needed to capture a broader global pattern.
46

---

Published as a conference paper at ICLR 2026
J.1.4 THE STUDY ON THE HIDDEN DIMENSION HYPER- SHIER-PARAMETER. i.e., d
In this subsection, we investigate the sensitivity of our model the hidden dimension d by conducting experiments with four different settings: d = 128, d = 256, d = 512, and d = 1024. Across all three datasets (i.e., Cora, PubMed, and Citeseer), the accuracy curves remain extremely stable, with fluctuations within only 0.5% 1.0%. This consisteney demonstrates that our model is highly insensitive to the variations of the hidden dimension d and does not rely on delicate hyperparameter tuning, making it robust and easy to deploy in practical, large-scale scenarios.
Hidden Dimension Study
90.0
Cora
Pubmed
Chteseer
85.0
Accuracy (%6
82.5
80.0
77.5
75.0
72.5
70.0
1024
Hidden Dimension
Figure 14: Hidden Dimension Study
47

---

Published as a conference paper at ICLR 2026
J.2 INTERPRETABILITY STUDIES
Based on the theoretical proof of Theorem 2 we have verified that trees sampled from our tree distribution can obtain theoretical guarantees the first-order homogeneity. In this section, hope to further conduct in-depth research and explain the internal mechanism of the model performance improvement, and reveal the essential principle performance growth by directly analyzing the quantity of long-range information aggregated by nodes and the validity of this information.
To quantify the benefit of this kind of information aggregation, we introduce a metric of global homogeneity. This metric can be directly achieved through our Forest Layer- the calculation can be completed simply by passing the one-hot encoding of the node as input into the network.
It can be clearly observed from the experimental results of Fig. 15 that in all scenarios, the trees sam- pled from our distribution exhibit significantly higher remote homophilous information aggregation capabilities. This phenomenon indicates that our method can capture and utilize the long-distance information in the graph more effectively, thereby aggregating into more feature representations with discriminative value. It is precisely because of this enhanced remote information aggregation capability that our model can achieve better performance on various datasets.
Ours 0,9052
Ours 0.9026
"Ours" **
0.8888
Random 0.8018
Random Spanning Tree
Random 0.7756
0.8
Random 0.6758
homophily ratio
Ours 0.5662
0.8
Random
0.4
0.0
Datasets
Figure 15: homophily ratio comparison based on different sample method
This analysis not only verifies and explains the effectiveness of our method from empirical perspective, but also reveals the fundamental reason for the performance improvement from the perspective of information theory that is, the more full utilization of valuable remote information is achieved through the improved sampling strategy.
J.3 NODE EMBEDDING VISUALIZATIONS
We plot some node embeddings produced by ours, SGC, and original features in Fig. [6] Observed from Fig. [6 our framework can obtain much clearer gap between node embeddings from different node classes, i.e., between-class embedding margins. It partly explains performance gain of ours against some counterparts.
48

---

Published as a conference paper at ICLR 2026
Original Features on Cora
GCN on Cora
Ours on Cora
Original Features on Citeseer
GCN on Citeseer
Ours on Citeseer
Original Features on Pubmed
GCN Pubmed
Ours Pubmed
Original Features on Wisconsin
GCN on Wisconsin
Ours on Wisconsin
Figure 16: Scatter plots of original features and embeddings output via GCN and our method on real-world benchmarks Cora, Citeseer, Pubmed, and Wisconsin.
49

---

Published as a conference paper at ICLR 2026
J.4 NOISY-FEATURE NODE CLASSIFICATION TASKS
To evaluate model robustness, we introduce a task called Noisy-Feature Node Classification, where inject Gaussian noise (5%, 10%, 15%) into the input node features and observe how classification accuracy varies under increasing perturbation. We visualize the results in Fig. 17 and Fig. [8] to facilitate clear comparison. By comparing accuracy trends across different models, assess whether our method maintains performance more effectively than existing baselines under node feature noise. Across all three benchmark datasets -CORA, PUBMED, and CITESEER our framework exhibits significantly stronger robustness to feature noise with various levels (i.e., 5%, 10%, 15%) compared with existing baselines. While all comparative methods show rapidly degrading accuracies as noise level increases, our framework consistently maintains clear and stable performance superiority. For example, on CORA and PUBMED, the advantage is clear: even at the highest noise level (15%), our model retains 0.631 and 0.646 accuracy respectively, far above the second-bes models, whose performance typically falls into the [0.37, 0.49] range. This indicates that our method substantially less sensitive perturbations in node features. The trend is similar in CITESEER, where accuracy remains above 0.44, while other models are much lower, and NodeFormer collapses severely due its instability under noise. The bar plots (see Fig. ??) clearly illustrate that although all models naturally decline with increasing noise, ours declines much more gracefully, preserving a significantly higher accuracy. Overall, the results demonstrate that the proposed method possesses superior noise resilience and thus can maintain high discriminative power with valuable knowledge even when node features are heavily corrupted.
50

---

Published as a conference paper at ICLR 2026
Noise Level: 5%
memmom
0.0
ciformn redefement
sctepalmon
0.6
0.4
0.2
COKA
PUBMEDD
CITESEEN
(a) Noise Level: 5%
Noise Level: 10%
cilteras
redeformer
scr-paimom
Curs
PUBMED
CITESEER
(b) Noise Level: 10%
Noise Level: 15%
0.7
0.5
0.3
(c) Noise Level: 15%
Figure 17: Robustness Comparison under Feature Noise various levels on Cora, Pubmed, and Citeseer
51

---

Published as a conference paper at ICLR 2026
Accuracy under Noise CORA
0.5
0.6
Accirscy
0.3
0.1
mearnon
nedaformar
parnorm
(a) Cora
Accuracy under Noise PUBMED
0.7
0.5
Acc./aac
0.4
0.2
0.1
moainomm
nedeformer
palmorm
(b) Pubmed
Accuracy under
CITESEER
0.4
Accuracy
0.1
nodeformer
parnorm
(c) Citescer
Figure 18: Robustness Comparison under Feature Noise various levels on Cora, Pubmed, and Citeseer
52

---

Published as a conference paper at ICLR 2026
J.5 EXPERIMENTS ON BARGER-SCALLE GRAPH BENCHMARK
In this subsection, we supplement experiments on a larger-scale graph dataset, i.e. AMiner-CS, and report the results in Fig. 19 and Tab. 5 including final performance comparisons well as the efficiency comparisons. Across all comparative baselines, our framework achieves the best classification accuracy, exceeding the second-best method by a significant margin. In addition to its superior predictive performance, our approach is also substantially faster, requiring only 0.152 seconds per epoch, which is notably lighter than baseline models such Difformer and dramatically more efficient than deep GNN methods like Meannorm and Pairnorm. These results collectively demonstrate that our method effectively breaks the challenging trade-off between accuracy and computational efficiency, making it highly suitable for large-scale graph learning scenarios.
Accuracy Comparison on AMiner-CS
0.60
0.55
0.50
Accuracy
0.45
0.40
0.35
0.30
Ours
Difformer Meannorm
Pairnorm Nodeformer
Figure 19: Accuracy comparison the AMiner-CS dataset.
Table 5: Training speed comparison on AMiner-CS (seconds per epoch).
Method
Avg Epoch Time (s)
Difformer
0.2524
Meannorm
1.1620
Pairnorm
1.2253
Nodeformer
0.3771
Ours
0.152
53

---

Published as a conference paper at ICLR 2026
J.6 EXPERIMENTS HIGHLY CONNECTED GRAPH BENCHMARK
In this subsection, we supplement experiments on a dense graph, i.c., Dense Cora, and report the results in Fig. 20 Dense Cora is highly connected graph constructed by adding 100 extra edges node while keeping comprehensive homophily rate. Observed from Fig. 20 the accuracy first increases slightly when the number of trees Nr grows from 10 12, but then decreases slightly as the number of trees Nr is further enlarged to 15 and 20. In other words, we observe that the addition of extra trees can further improve performance compared to using only a few. However, introducing too many trees cannot improve performance and may even slightly degrade it, as they introduce redundancy and would increase the risk of overfitting or over-smoothing issues. Therefore, even dealing with very densely connected graph, limited number of trees would be enough to encode the essential structural knowledge, without the need to introduce too many trees.
Accuracy vs. Number Trees on Dense CORA Graph
0.875
0.825
Accuracy
0.800
0.750
0.700
Number of Trees
Figure 20: Accuracy vs. Number of Trees on the Dense cora Graph
J.7 GRAPH CLASSIFICATION TASKS
In this subsection, we supplement some experiments on graph classification tasks on the ENZYMES dataset. We report the results in Fig. 21 with comparisons against seven baselines. While our method primarily designed
node classification, we show that still achieves best performance when directly applied to the graph classification task, surpassing all attribute- structure- based, and kernel- sernel-based based graph classification baselines. This demonstrates that the learned embeddings generalize effectively from node-level supervision adaptability, generality, and robustness our model.
prediction, indicating strong
Graph Classification Performance Comparison
60
50
Accuracy (96)
30
20
18t base
GCN-Mtt
Scuct base
CraphKerrel
GW--Struct
GCN Stw-ttruct
Ours
Figure 21: Graph Classification Accuracy Comparison the ENZYMES Dataset
54

---

Published as a conference paper at ICLR 2026
J.8 COMPARISONS WITH PATH-BASED GNNS
While both our work and some path-based methods (such as PAIN Graziani et al. (2023) and PathNNS Michel al. (2023)) can expand GNNs' receptive fields, our forest-based paradigm is fundamentally distinct. The path-based works rely on enumerating fixed-length paths (with exponen- tial complexity like ( ) and stacking layers (with an additional factor L >> to approximate global coverage. These factors (path numbers, path lengths, and layer numbers) make path-based based graph learning inherently suffer from severe trade-off between global coverage comprehensiveness and computational cost. In sharp contrast, our forest-based paradigm enables native pairwise node interaction in a single layer. achieves full global coverage in linear time, thereby avoiding complex structural encoding, layer stacking, and path-length constraints.
In this subsection, we supplement some experimental comparisons with some path-based GNN baselines the Cora, Citeseer, and Pubmed datasets. We report the results in Fig. 22 with comparisons against path- path-based baseline. Compared with PAIN Graziani et al. (2023), our method consistently achieves higher classification accuracy all three citation networks. On Cora, Pubmed, and Citeseer, our model improves the performance from 81 .44% to 85.46 35,,, from 19.14% to 81.20 1020%, and from 71.86% 74.42%, respectively, demonstrating clear and stable advantage over PathGNN across different datasets.
Comparison of PathGNN and Ours
90.0
PathGNN
87.5
Ours
85.0
Accuracy (%)
82.5
80.0
77.5
75.0
72.5
70.0
Cora
Pubmed
Citeseer
Figure 22: Comparison of PathGNN and Ours on Cora, Pubmed, and Citeseer.
55

---

Published as a conference paper at ICLR 2026
J.9 COMPARISONS WITH HETEROPHILY GNNS
In this subsection, we supplement some experimental comparisons with some Helerophill-Orreeneed GNN baselines the Actor, Cornell, Texas, and Wisconsin datasets. We report the results in Tab. 6 From this figure, we can clearly see that our method achieves the highest accuracy on all four heterophily datasets. outperforming recently proposed heterophily-speccfie GNNs such as ADPA [Sun et al. (2024), GESN Tortorella & Micheli] (2022), and HiGNN Zheng et al. 2024). The improvements are particularly large on Texas and Wisconsin, where our e reaches 89% and 86.27% substantially surpassing the best existing results and demonstrating its strong capability of capturing informative structural patterns even under severe heterophily. These results confirm that our approach generalizes effectively across diverse heterophilous scenarios and consistently provides State-of-the-aee performance.
Table 6: Performance comparison on heterophily datasets (Actor, Cornell, Texas, Wisconsin). The best result each column is shown in bold.
Method
Actor
Cornell
Texas
Wisconsin
ADPA Sun et al. (2024)
38.8 + 0.3
82,9 + 3.0
83.8 2.7
81.6 3.5
GESN Tortorella & Micheli (0022)
34.56 + 0.76
81.14 + 6.00
84.31 + 4.44
83.33 + 3.81 85.88 3.18
HiGN
Zheng el al. (0244)
37.21 + 1.35
80.00 + 4.62
86.22 4.67
Ours
39.88 + 0.43
83.24 + 2.02
91.89 + 0.0
86.27 + 0.0
56

---

Published as a conference paper at ICLR 2026
J.10 COMPARISONS WITH OTHER RANDOM TREE-BASER GNNS
We find a recent work, i.e., Bonchi et al. (0025). has some similarities with ours, but we are fundamentally different, Bonchi al. 2025 also introduces the structures to the graph learning domain. However, it is different from our graph learning paradigm in the following perspectives:
(I) Core ideas and main motivations: It introduces random trees mainly to accelerate the local GNN aggregations, by leveraging the tree sparsity to reduce the average number of neighbors. In contrast, we aim break the trade-off between complexities and comprehensive global aggregations, i.e., providing insights on how to conduct all pairwise node interactions (achieving global coverage) while significantly reducing running cost compared to traditional graph learning paradigms (with only linear complexities), which is more challenging and needs novel fundamental revolutions.
(2) Techniques sample and utilize trees are different: It samples trees from uniform distribution, while our technical framework samples trees from distribution that theoretically biases towards homophily, facilitating beneficial node knowledge propagations via linearization based path splits straightforward depth-first search (DFS) visit order, which reduces informative neighbors for nodes in a tree and risks introducing noisy neighbors. Moreover, they focus more local aggregation and still require layer stacking to cover global receptive fields. Yet, our work proposes powerful tree aggregator to explicitly address knowledge propagation along tree paths, achieving global coverage single layer without information loss, while keeping efficiency.
tree. It deals with such trees
Furthermore, supplement some comparative experiments and empirically find that technical framework consistently achieves better results compared to GERN-GCN et al. (2025). The results are reported in Fig. 23
Comparison of GERN-GCN and Ours
90
GERN-GCN
Ours
85
Accuracy (%)
80
75
70
65
60
Cora
Pubmed
Citeseer
Figure 23: Comparison of GERN-GCN and Ours
We can observe that our method significantly outperforms GERN-GCN across three datasets. On Cora, our model achieves an accuracy of 85.46%, while GERN-GCN achieves only 81.17%. Similarly, on Pubmed and Citeseer, our method shows clear superiority, with accuracy improvements of approximately 3.0% and 2.5% respectively. These results highlight that approach not only surpasses GERN-GCN in accuracy but also exhibits strong generalization across diverse datasets.
57

---

Published as a conference paper at ICLR 2026
K MORE EXPERIMENTAL DETAILS
In this section, more details of the experiments are provided to complement the experiments in the main text, including the experimental environments or platforms, dataset descriptions, and the specific hyper-parameter configurations, searching strategies, and searching space.
K.1 EXPERIMENTAL ENVIRONMENTS, PLATFORMS, AND TOOLS
We implement it via Pytorch Paszke et al. (2019) and optimize with Adam Optimizer Kingma Ba (2015), All experiments are performed on an Ubuntu system with single NVIDIA RTX A6000 GPU (4SGB Memory) and 32 AMD EPYC 7543 CPUs.
K.2 DATASET DESCRIPTIONS AND EXPERIMENTAL SETUP
We summarize some important details of all the graph benchmarks in Tab. 7utilized for evaluation. including the specific splits. We adopt the standard splits similar to GCN Kipt & Welling (0117). For large-scale graph datasets Flickr and Arxiv, we randomly generated 20 class-balanced data splits to ensure statistical robustness and report the average results across all splits. This multi-splir evaluation approach mitigates potential bias from single data partitions and provides more reliable performance estimates. To guarantee fair comparison, all baseline methods were evaluated under identical experimental conditions, including the exact same 20 data splits, consistent hyperparameter search spaces, and uniform optimization procedures. This standardized evaluation protocol ensures that performance differences reflect genuine algorithmic capabilities rather than experimental varia- tions. Our comprehensive comparison framework eliminates potential confounding factors, enabling objective assessment of each method's true performance on these challenging large-scale benchmarks. Notably, in semi-supervised settings, have only limited labeled nodes since the labels are quite expensive to obtain in the real world, which is quite significant in our world, since collecting so many data samples is already challenging enough, alone collecting enough labels. our cross-dataset rank analysis, we employed a fair ranking methodology to handle Out-of-Memory (OOM) scenarios. For algorithms without OOM issues, we calculated their average ranking across all nine datasets. When algorithms encountered OOM errors due to their inherently high space complexity, we excluded those specific datasets from their ranking calculation to ensure fair performance comparison. For example, if an algorithm experienced OOM on 2 out of datasets, its final ranking was based on the average across the remaining 7 datasets. While OOM represents a fundamental scalability limitation of certain architectures, this approach prevents hardware constraints from skewing comparative analysis, focusing instead on actual algorithmic performance.
Table 7: Dataset statistics nine real-world benchmarks with their splits
Dataset
Nodes
Edges
Ave. Wegree
Features
Classes
train/val/test
Cora
2,708
5,429
4,0
1,433
140/500/ 1000
Citeseer
3,327
4,732
2.84
3,703
120/500/ 1000
PubMed
19,717
44,338
4.5
60/500/100 1000
OGBN-ArXiv
169,343
1,166,243
13.77
128
40
800/800/ 200/800/167745
Texas
183
309
3.38
1,703
87/59/37
Wisconsin
251
499
5.45
1,703
5
120/80/51
Cornell
183
295
3.22
1,703
87/59/37
Actor
7,600
33,544
8.83
931
3648/2432/1 520
Flickr
89,250
899,756
10.08
500
7
100/440/88900
58

---

Published as a conference paper at ICLR 2026
K.3 HYPER-PARAMERR PARAMETERS
We tune hyper-parameters via two-stage strategy. For the first stage, we treat a tree as a hyper- parameter and we tune all of them together. In every stage, choose the hyper-parameters according to their best validation performance. After the first stage, we enter the second tuning stage. We select the best trees based on the best validation results, and then fix the trees and tune the other The search spaces of all meaningful tlyer-parameten are listed in Tab. _ and we omit some unimportant ones because they are actually robust model performance. For every kind of experiment, we search in the space randomly for 200 times in total. Additionally, for better reproducibility, we report all haper-parameters configurations used by Ours for comparative experiments in Tab. 8
Table 8: The Hyper-parameter Configurations of Ours for semi-supervised node classification tasks on nine public graph benchmarks.
Dataset
Hyper-parameter Configurations
I= 0.01, epochs = 50, d 256, Nr 12, dropout = 0.9, weight_ = 0.85, 0.7, 31 1.0, 32 0.0, KL =
Cora
Ir 0.005. epochs = 100, d = 128, NN 12, dropout = 0.9, weight decay 0.75, 0.7. 31 1.0, 32 0.0, K2 =
Citeseer
Ir 0.001, epochs 100,
Nr
Pubmed
dropout 0.6, weight_decay 0.0001, 7 = 0.7, 31 = 1.0, 83 = 0.0, K =
Ir 0.01, epochs = 90, d = 128, Ny 5,
Actor
dropout = 0.9, weight decay = 0.0. 7 0.9, 31 0.0, 32 0.0, K2 =1
Ir 0.01, epochs 60. d 256, Ny 15,
Comell
dropout 0.7. weight decay 0.001, 7 0.3.
81 0.0, 32 0.0. K,
Ir epochs 100. 256, N₂ 5,
Texas
dropout 0.5, wewght_dccay = 0.00001, , y 0.6, 81 0.4, 32 0.0, K, =
Ir 0.01, epochs = 100, d 128 Nr = 5,
Wisconsin
dropout = 0.6, weight decay = 0.0, 0.1, 31 0.2, 32 0.8, KL =1
Ir 0.0005, epochs 10, d 256, Ny = 4,
Ogbn-Arxiv
dropout 0.8. weight decay 0.0, 7 0.5,
31 0.4, 32 0.6, K₁,
0.01, epochs 30. 128, Nr
Flickr
dropout 0.3, weight_decay = 0.00001, 7 0.6,
81 1.0, 8n 0.0, K2 =
59

---

Published as a conference paper at ICLR 2026
Table 9: The Search Spaces.
Haper-paramcters
Hyper-parameter Search Spaces 0.01, 0.001, 0.0005
epochs
linspace(10,, 110, 10), 200
64, 128, 256
Nr
4, 5, 6, 8, 10, 12, 15
dropout
linspace 1, 1, 0.1)
weight decay
linspace(O.6, 0.95, 0.05), 0.0, 0.001, 0.0001, 0.00001
linspace 1, 0.1)
82
linspace I, 0.1)
31
linspace(O.1,, 1, 0.1)
K2
1, 2
60

---

Published as a conference paper at ICLR 2026
L DETAILS OF PREDICTION-BASED GRAPH AUGMENTATION
As mentioned in Sec. 4.2 and Sec. F.1 of Appn., we introduce a simple graph augmentation to support our framework. The motivation is basic: we expect make the vanilla graph G' become connected, and thus we can effectively and conveniently sample trees on the augmented variant. Besides, we also find that it can also improve the NHCC value of the graph (Sec. H.2
In our implementation, we adopt Maximum Inner Product Search (MIPS) between Kg. i.e., node label predictions, which is efficient and easy to implement via the Faiss Johnson et al. (2019) library (supporting even billion-scale similarity search with GPUs). We conduct top-k selection for each node (via the metric inner product) on the vanilla graph for simplicity. Further improvement can be developed to, e.g., consider node specialty (e.g., densities or degrees) and shrink the number of added graphs. The added edges are merged into the vanilla edge set and drop those duplicated edges. For reproducibility, add 12, 10, 15, 15, 10, 5, 8, 8, and edges for each node datasets ora Citeseer, Pubmed, Actor, Corelll, Texas, Wisconsin, OGBN-Arxiv, and Flick, respectively. We find that the is not sensitive hyper-paramette and its influence performance is limited. Yet, note that the heterophilous graphs may require slightly larger value, since, highlighted above, improve the value of the NHCC for the vanilla graph, which has theoretical connection with the upper bound of the tree quality (Sec. 4.6)
the generalizability of final
M ILLUSTRATION OF COMPARISONS BETWEEN DIFFERENT GRAPH LEARNING PARADIGMS
We provide figure (i.e., Fig. 24
illustrate and compare different graph learning paradigms, e.g., neighborhood-baat walk-based, and our forest-based paradigms.
61

---

Published as a conference paper at ICLR 2026
U
Sampling/A1l II
Sampling
22
W
F Fusing
Fusing
W
(a) Path/Walk-base based paradigm
(b) Neighborhood-basee paradigm
Sampling
Fusion
(c) Our Forest-based paradigm
Figure 24: Graph Learning paradigm Comparison: (a) Path/Walk- based paradigm; (b) Neighborhood-
based paradigm; (c) Our Forest- based paradigm.
62

---

Published as a conference paper at ICLR 2026
Avg.R
14.11
14:80
12.78
11.00
13.22
9.22
17.67
22.56
16.
19.67
8.78
17.00
15:57
13.00
15.40
13:22
13.11
13:44
12.67
7.2
10:36
Fleckr
0-47
08.402220 2.23
1.75
4142 0.09
26,24 4.15
43,07 0.85
25.26
111122 2:26
42.40 2.12
22111
41.9
37.59
00M
DCM
4.4
5655 1.16
15.33
22.79
10.13 2-
0.06 44.25
22
42.01
38.40
4142
29.58
3141
4411
42.30
47.22
Table 10: The results of performance comparison (with the best bolded and the runer-ups ups underlined).
40.3
Amaiv
12884 + 0.20
53.77 0.34
31-42 0:21
5152 2 0.37
18112
3355 1.244
54.8
2004
54.22 1087
2037 16.44
1923
5191 5191 1.50
5335
O0M
COM
0OM
4183 0.60
39447 - 1000
52.00 0.330
1112
1 161
53.60 0.00
5573
55.0
53.35
2037
41
1112
1573
Wisconsia
7941 +: 1.01
57.25 - 135
76.00 038
= 107
038
323
01.96 108
1135
48.44300
366
52.4 124
7031
4.75
02
11.88111 175
77.25 - 135
480
038
038
1.00
58.1
65,10
52.94
48.24
52.44
70.11
71.76
72
76-77
76.07
66.27
23.30
70.98
00:00
63.22
+ 1:14
144
121
121
1 148
62.78 2:2
41.08 = 18
66 00 226
62
60 605
84 148
24 2366
76 4 226
7
171
4 148
171
1 1.21
2.36
Toxas
68 19 -
25 44
75 1
08 3:
77 84
09.73
71.15
62
77
71.50
76.76
92
77.29
75
78
61
Comell
72 20 2: 1.99
63 2
11 121
1.8
08.05 191
4000
2541 1353
22911
7461 464
51353331
6162
63.24 11 18
00.00
1.86
21 1311
1.8
04.30-22.00 2.00
2.42
68
1:
4:15
53.5
56.59
61.88
08.65
4068
61
24.92
08
63.78
68
60.00
74.05
0 1
27 88 0.07
0.339
0.39
4.18
0.25
0.388
0.38
0.19
101
25-46 0.00
2241
M64 16
2845 0.08
5715
37.79 0.20
0.45
0.
37.6
53 53 00
0.47
34.1 0.76
32 0:76
Acter
36.24
1
2133
2074
35
26.71
3018
33.47
29.55
2638
57
37.79
31.0
31.33
37
37
36.05
Pulcoed
72.00 94 0.05
79. S8 - 36
30 0-44
81. 0.50
0.50
00.9
77.36 024
12
0.52
7300 300
72.000811
0.30
7648 2013
02
099
0.8
70.3000000 0.00
0.52
16 0.22
+
19
2
8000
22
78
19.8
76.2
76.06
78.30
7946
80.61
78
Cleceer
+ 0.04
71 11.00:1 0.30
0.30
72.50 0.80
1
0221
1001:000 021
44.00 123
18
0.51
0,
02
000 005
66.4 122
01.0820000
66 1.16
6 06100
67 34 14
71 110
01S
0
74.46 1 0.41
59 08
11.08
12
70.30
74
66.9
71
50.98
68
72
58 10 = 0.11
- 0.69
$1.40 - 080
052
0.3
020
06.3 1.88
051
0114
70 1954 0.56
10000000
343400
02.22002 024
77.58 7220 022
A7 AN 023
ONI
02 - 057
7V.11 - 0.90
82 - 138
08 1 0.70
80.32 6 0.2
Cára
80 06
82.70
82.00
81.00
80
83
Caleggrry
Clasiic
GNN
ONN
ONN
GNN
GNN
ONN
GNN
DeSOON
DesOON
DesONN
DepONN
DeePONN
Deep GNN
GT
GT
GT
GT
GT
GT
CT
61
Mechod
MLP
GCN
GraphS AGE
APENP
ClnterGON
GrapISAINT
Paimurm
Nedeneem
GCNI
SindowONN
GT
SAN
ANS-GT
Nodeformer
NAGppurrET
Exphormet
SCFomer
DiFFormer
TDGNN
GrahMMamaa
63

---

Published as a conference paper at ICLR 2026
Algorithm 3 Algorithm of Block Acceleration of Tree Sampler
Description: Given a positively weighted directed graph G, define a tree distribution conditioned on graph G as Pg (T), with the unnormalized score equaling to the product of all edge weights in tree (Recall Eq. 2in in the main text). Return a spanning tree of graph G approximately sampled from Pg (T) yet with higher parallelizability via trick called Block Acceleration (Sec. and Sec. F.3). The key idea is to identify a set of unimportant edges with relatively low scores and distinguish them from other edges by first ignoring and then reconsidering them, which provides a way that first divides the input graph into several blocks, parallelizably processes intra-block edges, and finally adds inter-block edges. Check Sec. F3 for the line-by-line explanations of this algorithm.
Input: graph G = (V, E) with its edge index EdgeIndex E Im=x2 and its edge weights EdgeWeights m where m = E| and we also denote n = [V]
Output: the tree T ~ Pa (T) with T (VT, ET), where VT and Er denote its node set and its (undirected) edge set, respectively
Hyper-Parameterr
KB. the number of blocks
Note: (1) We will call Algorithm with the operator TreeSampler (EdgeIndex, Edge EdgeWeights)) (2) We will call graph cut technique GraphCut (EdgeIndex, Fdge (e.g., efficient METIS Library for implementations), which will return a partition solution the node set V of an input graph G' with its edge index and its undirected edge weights;
(3) We denote the operator LookUp (S, X) E N4x1 with R E R to find the row index of row X; in S (-1 for not contained), assuming two rows in S are exactly the same; Scatter_ArgMas ArgMax (a, Index) from library torch_scatter, scatter, where Index[]] denotes the class number of the i-th row of the matrix a, with their definions as follows:
(4) We will call two operators Scatter Add (a, Index) and Scatter.
Scatter Add (a, Index) [t] = |a|
Σ I [Index[f] = i) a[j],
(77)
Scatter Scatter_ArgMMax (a, Index) [ argmax,, os/</a/& Index]j) a[j].
1: BlockNo +- GraphCuu (EdgeIndex, Weight)) Nax1
2: BnLeft, BnRight t BlockNo (EdgeIndex([ 0)), BlockNo (EdgeIndex(:, 1))
3: for each i [1, F do
4: Mask <- (BnLeft BnRight & BnLeft =
5: EdgeIndexBlocki], Edge WeightsBooolskk EdgeIndex(Mast] EddgeWeighss//p [Mask]
6: end for
7: ZeroMask (BnLeft + BnRight)
8: BegelnndesBlockeennaaiill + Edgelnneex(ZerrMMass)
9: BdgeWaightsBloeeZenn + Edggagggs///ggsssnnnnasssss
10: + hww.://oeeeeecccccooo-oeeeeeeeen
11: EdgckndexBlook(0]] EdgeWeightssBlock00 + Merge (EdgllnlesBeccZZeoBolokkk Aogaeooeoooooggeeeeeeeeeeeooeooo EdgeeWigghtsBlockZerr
12: for [0, Ka] do
13: TreeBlockkj] + TreeSampler (Bjj]
EdggeWeightssllock/]]]
14: end for
15: Index + LookUp (TreeBlock(0), EagchndoxBBocc2eccooooooo))
Index <- Index [Index 2 0)
17: e + hag.e
http:///eeeecccoiiieeeeeeeeeeeee +
[ndex
19: EdgeSum + Scatter Add
Ttg.sseeeeeettttteaeaaeaaaaaaaan [Edgg-Wigghhshoooeeeelhhhheee Index)
20: EdgeProbabilities Edge WeiiggeeeihghaBBBeeeeeeonreeee Bedgrreee/dSSSSeeneeeeeeee
21: tmp + log (EdgeProbabilitics + Gumbels, where each element in Gumbels is x
log (- log (4)) { Uniform (0,
22: TreeBlock(O) +- Weightss
(tmp, Index)]
V1 Er < Concat (TTre
64
24: return T (Vr, Fr)

---

Published as a conference paper at ICLR 2026
N MORE RELATED WORK
In this section, we will provide more discussions on the literature related to our work.
N.1 GNNS ON HETEROPHILIC GRAPH
While traditional graph neural networks (GNNs) excel at semi-supervised node classification un- der the homophily assumption, they face challenges in heterophilic wraphs-where dissimilar nodes (with different labels) are often connected- to misleading message aggregation and wverssmothhnggExissimi heterophilic GNNs can be categorized into three main types: aggrega- tion calibration, graph modification, and other approaches. (1) Aggregation calibration methods optimize message aggregation mitigate heterophily's negative effects while preserving local topology. H2GCN Zhu et al. (2020) distinguishes between ego-node and neighbor representations, combining node embeddings balance local and global information. ACMGCN LuGGnNLLannnn et al.) (2021) adaptively mixes different frequency signals via low-pass, high-pass, and identity channels, which successfully separates meaningful information from noise in heterophilic scenarios. (2) Graph modifi- cation methods adjust the original graph structure to enhance semantic similarity between connected nodes. Geom-GoomGiiii GNNN Pei al. (2020b) constructs structural connections via geometric measurements, preserving topological properties while linking semantically relevant nodes. WRGAT Suresh et al. (2021) learns a new computation graph based on node proximity and local structural similarity, thereby breaking the constraints imposed by the original edges. GloGNN et al. (2022) captures node correlations
Wuresh
feature and topology similarity by learning a coefficient matrix, strengthening connections between semantically similar nodes. DIGL et al. (2019b) utilizes generalized graph diffusion (e.g., personalized PageRank) to adjust edge weights, thereby promoting connectivity between nodes with short diffusion distances, aligning with semantic similarity. Other methods adopt alternative techniques to overcome the limitations of traditional pesssage-passingg GNNs on heterophilic graphs. GESN Tortorella & Micheli (2022) employs reservoir computing framework, where node embeddings are generated by an unlearnable recursive message-passing function, thereby avoiding over-smoothing by controlling the Lipschitz constant effectively encode structural knowl- edge. ADPA Sun et al. (2024) proposes the AMUD framework to assess how node features interact helps determine whether the graph should be modeled as undirected or directed-aan and utilizes hierarchical attention to integrate message information across different scales. HiGNN ZZeng al. (2024) defines heterophilous information as the label distribution of each node's neighbors, constructs new adjacency matrix to connect nodes with similar heterophilous information, and fuses this matrix with the vanilla graph structure to improve performance.
with directed topology
O LLM USAGE STATEMENT
Large language models were employed in this study exclusively for the purpose linguistic refine- ment and stylistic enhancement.
65


Reviews:
[{"review_id": "Ofo4dJLPBj", "reviewer": "Reviewer_GwAw", "summary": "This paper proposes a Forest-based Graph Learning (FGL) framework to address the trade-off between global receptive fields and computational efficiency in graph neural networks. The authors reinterpret graph information propagation as a transmission process across multiple spanning trees (a forest) to efficiently achieve long-range information aggregation. Methodologically, the paper designs a tree sampler based on homogeneity estimation and a linear-time tree aggregator, achieving Transformer-like global interaction capabilities while maintaining linear complexity. Experimental results demonstrate that FGL outperforms existing GNN and Graph Transformer models on multiple semi-supervised node classification tasks while maintaining significant training efficiency.", "questions": "Does FGL struggle with relatively dense graphs, resulting in more edges and information being discarded in the generated tree compared to the original graph?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This is an interesting paper. The methodology of this paper represents a significant innovation compared to GNN and GT.\n2. I really like the design of Tree Aggregator and it's quite interesting. The paper also provides ample theoretical analysis.\n3. The paper is well-written and easy to follow. The experimental results demonstrate the superiority of this method.", "weaknesses": "1. Given that the paper emphasizes the efficiency of this method, experiments on large-scale graph datasets may be warranted. In my view, the experimental data presented in the paper is insufficiently large.\n2. Compared to GNN and GT, the expressive power advantage of FGN remains unknown. I look forward to the authors providing further insights on this aspect in their paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SGcxWberGu", "reviewer": "Reviewer_Tajx", "summary": "This paper proposes a Forest-Based Graph Learning paradigm for semi-supervised node classification, addressing the trade-off between cost-effectiveness and global receptive field in existing GNNs and Graph Transformers. FGL models information propagation as transport over a forest of spanning trees, generated via a homophily-guided sampler. It incorporates a linear-time tree aggregator for efficient long-range interaction and a tree fuser to merge multi-tree knowledge. Experiments on show FGL outperforms state-of-the-art methods (e.g., 11.9% gain over GCNII, 16.1% over DIFFormer) with linear complexity and faster runtime.", "questions": "See weaknesses", "limitations": "", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.Breaks the local-global trade-off by leveraging spanning trees, enabling efficient global coverage with low structural cost.\n\n2. Linear time/space complexity per epoch, with 2–5× speedup over GTs (e.g., DIFFormer) and deep GNNs (e.g., GCNII).\n\n3. Excels on both homophilous (Cora, Pubmed) and heterophilous (Actor, Cornell) graphs, with robust generalization under label scarcity.", "weaknesses": "1.Using a forest to address homophily–heterophily problems is not a particularly novel idea, as many path-based methods [1] also aim to expand the receptive field. The idea of employing trees follows a similar intuition, broadening the range to enhance the model’s ability to capture global structural knowledge.\n\n2.In line 252, there seems to be a definition error — what does Fa(u) and g(u) represent, and how do they satisfy Properties (I) and (II)? If both letters H and S denote embeddings, it would be better to use a consistent notation, otherwise it becomes confusing. I suggest the authors clarify this theorem more explicitly.\n\n3.My main concern with this method lies in the semi-supervised setting: how to accurately characterize homophily becomes a major issue. The paper uses “the cross-entropy loss with targets... We train the local graph attention by minimizing...” to obtain pseudo labels. However, if the model performs poorly, the predicted homophily may deviate significantly from the true one, leading to a tendency toward over-smoothing.\n\n4.In Section 4.1, what does c represent? If Y is a one-hot label, then finding k nearest neighbors in the representation space seems meaningless.\n\n5.The paper lacks a discussion of related work on heterophilous graphs, and there is also a lack of baselines specifically designed for heterophilous GNNs", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a1dpc0LRM4", "reviewer": "Reviewer_oK4D", "summary": "The paper propose the forest-based graph learning paradigm, which achieve the efficient long-range information propagation. The core idea is to reinterpret graph message passing as transport over spanning trees.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel conceptual paradigm. The proposed Tree Aggregator is a meaningful and technically novel formulation that enables composable and reversible message passing on trees, achieving efficient long-range propagation with linear complexity.\n\nWell writing. \n\nThe experiment section is solid and broad. The evaluation includes both homophilous and heterophilous benchmarks with extensive baselines, ablations, and hyperparameter analysis. The empirical performance (especially on Wisconsin, Texas) is notably strong.", "weaknesses": "While the paper emphasizes “forest-based” modeling, the connection to existing tree decomposition / hierarchical GNN approaches(For example, [1]) is not clearly distinguished.\n\nOverly complex pipeline: The four-stage pipeline (preprocessing → tree sampling → tree aggregator → tree fuser) introduces multiple training stages and parameters (β₁, β₂, γ, Kᴸ, N_T), yet lacks analysis on training stability and sensitivity.\n\n\n[1] Fast and Effective GNN Training with Linearized Random Spanning Trees", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1aBfM5kvT0", "reviewer": "Reviewer_vja3", "summary": "The paper proposes Forest-Based Graph Learning (FGL) to reconcile global receptive fields with efficiency in GNNs. Instead of deep stacking or quadratic global attention, FGL models message passing as transport over a small forest of spanning trees: (i) build an augmented graph via pseudo-label kNN; (ii) sample trees using a homophily-guided, weighted Wilson method; (iii) run a two-pass, linear-time tree aggregator (bottom-up then top-down) on each tree; and (iv) fuse normalized per-tree embeddings with a lightweight local module via a residual. Theoretically, better homophily scoring increases expected tree homophily and approaches a structural upper bound.  FGL reports competitive or superior accuracy and favorable runtime on node classification benchmarks.", "questions": "Please address the concerns raised in the weaknesses section.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper proposes a novel graph learning framework—Forest-Based Graph Learning (FGL) that combines global structural modeling with local feature propagation by viewing graphs through a forest of spanning trees to capture hierarchical node dependencies. \n\n2. The technical quality is strong: the objectives and their links to smoothing and spectral properties are clearly derived, and extensive experiments across benchmarks. \n\n3. The writing is clear and well-structured.", "weaknesses": "1. The approach largely reads as a straightforward assembly of existing components: pseudo-label kNN augmentation (standard self-training/graph augmentation), weighted Wilson sampling driven by attention scores (classic LERW with learned edge weights), two-pass tree DP (bottom-up/top-down rerooting), and RowNorm + mean + residual fusion. There seems to be little apparent redesign of the modules or new learning objectives beyond composition.\n\n2. The paper primarily evaluates on semi-supervised node classification, leaving unclear whether the forest paradigm generalizes to broader settings (graph classification/regression, link prediction, inductive and dynamic graphs, heterophily extremes, robustness to noise, and scalability in billion-edge graphs). Broader tasks and protocols would better establish practical generality.\n\n3. The method introduces multiple hyperparameters ($\\beta_1, \\beta_2, \\gamma$ etc.) that require careful tuning for different scenarios. The hyper-parameter part implies that performance may be deeply dependent on these parameters, which could make the method difficult to deploy in practice, potentially limiting its practical applicability.\n\n4. The paper does not thoroughly examine when the forest paradigm might underperform. For instance, what happens when node features are noisy or weakly correlated with the graph topology? Does the method perform well on highly dense graphs where local tree-structured neighborhoods may not be able to effectively capture the graph’s global dependency patterns?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)