HubGT: Fast Graph Transformer with Decoupled Hierarchy Labeling
Authors: Ningyi Liao
Zihao Yu
Siqiang Luo
Gao Cong
Venue: NeurIPS 2025 poster ()
Keywords: Graph neural networks; Graph Transformer; Shortest Path Distance
Primary area: deep_learning
TL;DR: We propose HubGT as a scalable Graph Transformer enabling fast and hierarchical embeddings.

Abstract: Graph Transformer (GT) has recently emerged as a promising neural network architecture for learning graph-structured data. However, its global attention mechanism with quadratic complexity concerning the graph scale prevents wider application to large graphs. Effectively representing graph information while ensuring learning efficiency remains challenging, as our analysis reveals that current GT designs targeting scalability still suffer from the computational bottleneck related to graph-scale operations. In this work, we tackle the GT scalability issue by proposing HubGT, a scalable Graph Transformer boosted by fully decoupled graph processing and simplified learning. HubGT represents the graph by a novel hierarchical scheme exploiting hub labels, which is shown to be more informative than plain adjacency by offering global connections while promoting locality, and is particularly suitable for handling complex graph patterns such as heterophily. We also design algorithms for efficiently constructing and querying the hub label hierarchy tailored for the GT attention training in scalable deployments. Notably, the precomputation and training processes of HubGT achieve complexities linear to the number of graph edges and nodes, respectively, while the training stage completely removes graph-related computations, leading to favorable mini-batch capability and GPU utilization. Extensive experiments demonstrate that HubGT is efficient in terms of computational enhancement and mini-batch capability over existing GT designs on large-scale benchmarks, while achieving top-tier effectiveness on both homophilous and heterophilous graphs.

HubGT: Fast Graph Transformer with Decoupled Hierarchy Labeling
Ningyi Liao" Nanyang Technological University 1iac00908e ntu. atu.edu..... edu.sg
Zihao Yu" Nanyang Technological University zihao yuentu. edu. sg
Siqiang Luo Nanyang Technological University siqiang. luoentu. edu.
Gao Cong
Nanyang Technological University gaocongentu.edu
Abstract
Graph Transformer (GT) leveraging the powerful Transformer architecture learn graph-structured data. However, effectively representing graph information while ensuring efficiency remains challenging, as our analysis reveals that graph-scale operations still constitute the computational bottleneck in current GT designs and limit their applications large graphs. this work, we tackle the GT scalability issue by proposing HubGT, which is boosted by decoupled graph computation and hierarchical graph representations. HubGT represents graph information with a novel hub labeling scheme, which encompasses enriched neighborhoods for node token generation, and fast computation for distance- based positional encoding. Notably, the precomputation and training of HubGT achieve complexities linear to the number of graph edges and nodes, respectively, while the training stage completely removes graph-related computations, leading to favorable mini-bated capability and GPU utilization. Extensive experiments demonstrate that HubGT offers efficient computation and mini-batch capability over existing GT designs large-scale datasets while achieving top-tier effectiveness. Our code is available at: httts:///gthhni git............ com gdmm 1/ubbT
1 Introduction
Graph Transformers (GTss) has recently emerged as family of neural networks that introduce the advantageous Transformer architecture [ to the realm of graph data learning. These models have garnered increasing research interest for tasks such as knowledge graph retrieval, molecule analysis,
and Large Language Model alignment 2 3 4 S Despite their achievements, vanilla GTs are highly limited to specific tasks because of the full- aall-graph attention mechanism, which has computational complexity at least quadratic to the graph size, rendering it impractical for single graph with more than thousands nodes. Enhancing the scalability of GT's is thus a prominent task for enabling these powerful models to handle wider range of graph data at large scales.
To apply Graph Transformers to large graph data, existing studies explore various strategies divide and represent the graph structure into smaller batches and employ mini-batch training. One approach is simplify the Transformer architecture with a specialized attention module based on graph topology 66, [ [8, which learss on existing edge connections instead of all-pair interactions. Alternatively, sophisticated representations are developed for inputting graph information to GT models as node embeddings and positional encodings. These works feature graph processing techniques such as adjacency-based spatial propagation
( 10,, polynomial spectral transformation III and
"Both authors contributed equally this research. "Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Complexity analysis on GT models. "Precomputation" and "training time" represent the complexity of one-time processing and iterative forward passing computation, respectively. "RAM" and "GPU memory" indicate the sizes of overall data and variable representations during learning. Data "scale" is represented by the largest graph node size and edge size used in the original papers.
Taxonomy
Model
Precompute Time
Train Time O(LaFF) O(LaFF)
RAM Mem. O(n²)
GPU Mem. O(Lx*F)
Scale
Vanilla
Graphoreer
O(n²)
0.3K/0.6K
(FB)
GRPE
B
O(xe)
O(12)
O(LnFF)
0.3K/U.K
GraphGPS
7
O(a²) O(da)
OflaF2 + LmnP)
+
O(Emp +.m) m)
LOK/3.0K
Kernel- based (NS)
Exphormer
19
O[InF2 + LmnP)
O(uF
OL +m)
0.2M/1. 2M
NodeFormer
0
O[LnF² LmF)
OinF
OLLmgF m)
2,4M/60M
DIFFormer
g
O[LnF² + LInF)
Oin +m)
OiLm,P + m))
166/40M
PolyNormer
O[LnF² LIP))
O(nF m))
OLLmpP + m)
2.4M/0. JB
NAGphommer
O(LmFo)
O(LoFe)
O(LnF)
2.4MU60M
PolyFormer
L.
OLLnFF)
O(LnF)
O(Ln(F
0,2M/30M
Hierar- chical
ANS- GT
[3
O(ns + m
Ol F Lm]] O + ns? mdd")
OfLinF + mist)
20KJ0.2M
(RS)
GOAT
10
O(nF)
O(LnE2 LmP))
OGuP
OLLag + Ln + m)
1B
HSGT [4]
Oin + mdd))
O LmF)
OtaF + mal
Log LngF + Lm)
2,4M/O,1B
HubGT (ours)
O(na + ma]
O(LnP2 + Las F)
O(nF + ns?)
OiLngF + m6a")
I. 16600 IB
Nocations: L are model depth and width, respectively. m//n average degree the graph. is sample size subgraph mechods.
hierarchical graph coarsening 13 14]
However, we identify two major drawbacks of existing
scalable GTs: in terms of efficacy, most models primarily concentrate on local topology, which is
highly diluted in large graphs and undermines GT expressivity in capturing global information; in terms of efficiency, graph-scale operations still persist throughout their training iterations, and the computational overhead substantially increases as the graphs become larger.
In this work, we specifically target the above two challenges brought by scalability. We propose HubGT, a scalable Graph Transformer exploiting the hub labeling technique to produce rich hierar- chical graph information with efficient computation. HubGT is inspired by the well-studied concept of graph labeling, which identifies important hubs in the graph structure and imparts fast computation of the shortest path distance (SPD) for node pairs 15 16 17.. We innovatively introduce the graph label hierarchy to enhance GT capability by establishing global connections to influential graph hubs, which is shown to provide more inclusive receptive field than the conventional adjacency- scheme. To further represent node-pair interactions, HubGT is the pioneering work to employ SPD as positional encoding for large-scale GTs, which is only practicable under its efficient calculation. The expressive representations empower HubGT to capture graph knowledge beyond edges and excel in complex graph data patterns ranging from homophily to heterophily.
Then, to address the efficiency issue, we design a three-level index for computing and storing the graph data, where the dedicated computation process and acquired graph labels share the same hierarchy, comprising of both local edges and global hubs. The indexing process can be fully decoupled as precomputation with (m)) overhead from the iterative training. Then, querying SPD on the index can be performed in only O(1) time, rendering HubGT learning as simple as training normal Transformers under (n) complexity without interweaving graph topology, where mn and n are the numbers of graph edges and nodes, respectively. Both precomputation and training of HubGT achieve theoretical complexities on par with the respective state-of-the-aa GTs and are significantly faster in practice thanks to the simplicity of our graph representation based on hub labeling. We summarize the contributions of this work as follows:
We propose HubGT as an efficient Graph Transformer with novel hicrarchical sampling based on the hub labels, effectively embedding local and global graph topology. We also enable the powerful SPD positional encoding on large-scale graphs.
We design hicrarchical index dedicated to HubGT graph processing, featuring construction under linear complexity and (l)) query overhead. The decoupled precomputation and simple training contribute fast and scalable mini-batch GT training.
We conduct comprehensive experiments evaluate the effectiveness and efficiency of HubGT on up to million-scale graphs. HubGT achieves top-tier accuracy and demonstrates competitive scalability, especially demonstrating the fastest inference speed.
2 Preliminaries and Related works
Graph Transformer and Positional Encoding. Consider graph G = (V,E) with n = | nodes and |8| edges. The graph adjacency matrix is A and average degree is d = m/n. The node

---

attribute matrix is X E R=xPo, where Fo is the dimension of input attributes. A Transformer layer [ first projects three representations given an input matrix H RTxF:
Q HWQ. == HWK, V = HWW,
(1)
where We E FKFK WK E RFFK, Wv E PxFx are learnable weights. For multi- head self-attention module with NH heads, each attention head possesses own representations Qi K, V 1,.., Nu, and then the output H across all heads is calculated as:
QuKk VFK
P)V.
H. = softmax
PP) V.
= |HHw) Wo:
(2)
where -||- denotes the matrix concatenation operation. The projection dimension is usually set as
FR = F/NH. Beside the representation H. positional encoding (PE) P in Eq. (2) can also
incorporate graph topology into the GT attention module by encoding pair-wise information. Typical
encoding approaches include graph proximity 22 13 20 Laplacian eigenvectors 21 22 and
shortest path distance [8 23 24
Scalable GT and Training Schemes. The majority of vanilla GTs 211 3 are typically proposed
for graph-level learning tasks on small graphs with full-batch training (FB). This is relevant to their quadratic complexity revealed by Table T For large-scale graphs, model scalability is primarily dominated by the graph-scale terms m and n, which renders a critical bottleneck in these models as indicated in Eq. ( due to representing nodes with On F) time and memory overhead.
To mitigate the quadratic complexity and foster scalable learning, scalable GTs employ mini-batch training, which replaces the full representation H with batches containing nodes and reduces memory complexity to (n F). Kernel-bused GT's 7 & 19 12 generate batches by neighborhood sampling (NS) and utilize graph kernels, i.e., functions modeling node-pair relations, for attention computation to exploit edge connections. Typically, they necessitate iterative processing of graph data with O (Lm complexity throughout learning. When the graph scale is large, this term becomes dominant since the edge size m is significantly larger than the node size n. Hence, we argue that such design is not sufficiently scalable.
exploit the power of GTs learn node relations by embedding node-level identity through the input data X. Its core design is crafting an effective embedding scheme to comply with GT expressivity. Since the graph topology embedded in an sermutation-invariant manner, mini- mini-batching can be performed through random sampling (RS). The model can enjoy better scalability the graph processing is fully independent of GT attention. Ideally, hierarchical GTs process graph topology in O(m) complexity in precomputation and employ RS during training for better scalability. Nonetheless, we note that existing models, except for NAGphormer [9] and PolyFormer [ЛI) still involve graph-level operations during training in Table I which hinders GPU utilization and causes additional overhead. A thorough analysis of the related models can be found in Appendix
Alternatively, hierarchical GT's
3 Motivating Study
Graph hierarchy beyond adjacency. The expressiveness of GT's mainly stems from the full-graph attention formulated in Eq. (2). which captures critical node pairs in the graph topology to learn node representations 2 6) However, since the mini-batch scheme replaces it with in-batch attention, its capability is potentially hindered. To compensate the information loss, scalable GTs usually invoke more powerful embedding and encoding techniques, enhancing the global graph view for more candidate nodes by expanding the receptive field. In canonical mini-batch GT models (2 6 91, the graph information is typically derived from the graph adjacency A, which symbolizes neighborhood information E. For both serel-basee and hicrarchical GT variants, their expressiveness distinguishing different graph structures is characterized by the substructure used in attention tokens
Motivation 1:
24
However, recent advances in message- passing GNNs reveal that, the adjacency alone is insufficient for retrieving topological information in graph learning 225.. complicated scenarios such as heterophilous graphs, the local graph topology may be ambiguous or even misleading [26] 27 28
To illustrate, Figure shoows the distribution of node neighbors considering their classification labels depicted by the homophily score 29). A lower homophily score implics high heterophily, where less
3

---

Rey
Labokd
CHAMMPLOO
220
DORA
415
CUTESROR
0.0
0.2
0.4
0.6
0.8
1.0
Homophily Score
Figure 1: Relative distribution homophily scores between original and extended graphs. A higher score implies more similar nodes in the neighborhood.
(a) L-hop Adjacency
(b) SPD
Figure 2: Comparison of PEs as attention hiases CITESEER.
neighbors share the same label with the ego node. On graphs such as CHAMELEON and SQUIRREI,, a large portion of nodes exhibits homophily, indicating that substructures depending graph edges barely include neighbors with the same label for GT' to attend.
We are thence motivated to improve GT by augmenting the existing graph connections & to an extended edge set & containing additional node interactions beyond the neighborhood. As shown in Figure []] establishing more edges enhances nodes of lower scores with more homophilous connections, effectively addressing the zero-homophily issue. Therefore, encompassing both local connections and global knowledge capable of forming a hierarchical structure beyond the original graph adjacency, which benefits the model in retrieving wide spectrum of information B 10
Dense PEs for large graphs. While an array of PE schemes are utilized for explicitly integrating graph knowledge into GT learning, they are shown to possess various information aspects and expressiveness 22 5]. In particular, shortest path distance (SPD) as a form of pairwise PE
Motivation 2:
2 is revealed to be at least expressive as the Weisfeiler-Lehme and empirically superior in graph classification tasks (30 31). However, the conventional
(WL) graph isomorphism test
algorithm for calculating whole-graph SPD entails O(n²) time and O(n²) space, which is prohibitive to large graphs.
On the other hand, scalable GTs commonly employ sparse PEs such as L-hop Adjacency ID-1/2(A+ D)D D)23// which is straightforward to acquire by sparse matrix multiplication in loosely connected, the in-batch PE under mini-batch training can be too sparse to represent pairwise relationships. As observed in Figure [(a] PE values only significant between the ego node and two direct neighbors, while diminishing to zero for more distant nodes in the same batch. The values for non-ego node pairs also small, rendering the bias ineffective in attending node-pair interactions.
Omddh) complexity [3 [4]. However, since nodes in large graphs
To this end, we attempt to apply the more effective pairwise SPD for encoding arbitrary node pairs on large graphs. Figure 2(b) suggests that the scheme is superior in providing rich information covering both positive and negative relationships, even for nodes that are not directly connected. Therefore, also more suitable for the extended hierarchical graph structure & involving global connections to distant nodes.
Efficient Hierarchical Labeling
In light of the limitations of existing scalable GTs on large graphs, our HubGT aims to address these two challenges simultaneously while ensuring computational efficiency: (1) The dedicated data structure provides expressive graph information for generating node embeddings that represent the graph hierarchy beyond mere adjacency. (2) Node-pair SPD can be efficiently calculated based on the hierarchy, which then used as positional encoding. this section, we first introduce concept and novel settings of our graph labeling approach. Then, we focus on designing the respective indexing and querying algorithms, while their integration into GT learning is claborated in Section 5
4.1 Problem Statement
Conventional Hub Labeling: Full-graph SPD. Computing the shortest path between graph nodes is fundamental problem in graph analysis. Canonical hub labeling algorithms [32 33 are proposed to efficiently answer full-graph SPD queries between arbitrary node pairs. achieve this, an index C(t) is constructed for each node v E V, containing number of labels. Each label for

---

node typically consists of an end node u and the corresponding shortest distance b(u, v) between the node pair. Then, given query involving two arbitrary nodes u, v V. the SPD can be promptly answered by looking up and combining relevant labels from the graph index L. thereby preventing exhaustive traversal of the entire graph.
Our Settings: Subgraph SPD. In HubGT, construct the graph index through separate precomputation phase that occurs prior to GT learning. Note that each label represents a node pair (u, v) and the distance b(u, v). Hence, we able to extend the graph structure to weighted, directed graph by regarding the labels as graph edges, i.e., 9 EV,E), where & {(u, v) | E [v))). Appendix A. provides proooovv thorough elaboration on the theoretical properties of the extended graph when generated by our hub labeling approach.
To facilitate node representations for GT learning, here, we consider an SPD querying problem different from conventional full-graph queries, which allows HubGT to simultancously perform node token generation and SPD calculation in an end-to-end manner. The subgraph SPD problem can be explained as follows: Given a node r, we aim (1) sample a subgraph, i.e., a set of nodes S(r), such that (u, r) E & or (r, u) E & for u E S(r) solely based on the built index; (2) at the same time, acquire SPDs b(u, v) for all node pairs u, e E S(r). Considering the iterative nature of such queries during training, our primary design objective is to minimize querying overhead while maintaining reasonable time and space indexing overhead.
4.2 HubGT Indexing
Under the conventional full-graph SPD problem, the representative Pruned Landmark Labeling (PLL) algorithm 35 36) offers an indexing strategy with efficient search space and minimal index size. The algorithm searches labels by pruned Breadth First Search (BFS) for each node following a particular order. During construction, PLL tends to regard foremost nodes in search as hubs and connecting more edges to them, while climinating the labeling from latter nodes. Hence, a hierarchy of nodes are intrinsically formed by labeling.
To address the specific requirements of node sampling and SPD calculation in the subgraph SPD problem, we design the HubGT algorithm for hub labeling, which is based on the intuition of search- and-prune from PLL. This leads to a distinct three-level hierarchy in both index construction and querying, with the aim to strategically balance index size and query time. Our Algorithms | to 3 are detailed in Appendix A.2
Hierarchy-1 1 (H-1): Local hub labeling. Unlike the SPD query on an arbitrary node pair addressed by PLI., the query for b(u, u) in HubGi always orients an intermediary node r. In other words, v, v
are at most 2-hop neighbors in É. To leverage this relevance, we broaden the derivation of 2-hop labeling [35] to these subgraph nodes, that the distance candidate orienting b, (u, v) can be acquired by utilizing the connectivity with the local hub node r:
6()) v) = b(u, r) + b(r, - 8,
(3)
where u,, 2, or 0 depending the relative position between (u,r) and (0,r) in G: denote (M) = {w E (r(r b(r, -),b( v) = i), i = 1, 0, or 1, where (h(reeN((r) [w[(w,)) E E is the neighborhood orienting in G. The node sets (f) of different integers i effectively characterize the relative position of the node of interest v with respect to the intermediary node r. When when (M( o Ø or Mt MM( o Ø,
(M) (M)))) # Ø, there is (u, v) there is 6,, v) = 1; otherwise 6, v) = O.
We develop Algorithm a the first level of hierarchy. On top of the pruned BFS in typical PLL, also record the neighbor sets (x) and M)(x)) for nodes added to labels L(u) along with their indices and distances. Additionally, we maintain an inverse label set L'(v) such that E L'(v) if and only if E C(u). Therefore, each label in L(v) ) or L'(v) is a quadruple (u, b(,, v). M!,),, (u)), which suffices the distance query based on Eq. ( In specific, we explicitly impose maximum capacity (ss) for each node label L(v) in Algorithm This is because at most & neighbors are required to form the subgraph in our problem.
Hierarchy-2 2 (H-2): Global hub labeling. H-1 index presents the idea of utilizing the relative position orienting a given hub r to compute the distances of 2-hop node pairs in query. It can be further generalized to some global hubs by indexing their labels as another level of hierarchy, which
5

---

corresponds to the bit bit-parallel BFS in [35.. More specifically, we select small set of nodes with low indices in the search order, and perform Algorithm []
B without pruning. For each global node I, the label (b(u, (), Mi (v), M.( (ri) is computed and stored for all V. Then, the candidate
distance of an arbitrary node pair b, (u, 2) can be similarly computed by Eq. orienting hub
Hierarchy-O (H-0): 2-hop pair eaching. Although the H-1 and H-2 query Eq. produces the shortest distance 6(u, v) when 6/" (u, v) 2 b(u, v) + 6, (u, v), it is possible that the actual shortest path P P(u, v) does not pass through r or its neighbors. In this case, the exact SPD calculation falls back to the classic node labeling scheme:
( (u. v)
min wEC(w)nC(e)
(b(u, w) + b(w,))),
(4)
where labels L are computed by Algorithm Note that b(u, = 0.
We regard the 2-hop labeling scheme as the fundamental hierarchy as it guarantees answer to any queries. However, calculation by Eq. 44) results in a complexity of O(([())] + [()))), which is still not satisfying under the repetitive querying in GT training. To further improve query speed, we choose to cache the frequently queried 2-hop shortest distances b(u, v) and index them by the end node as [u[u] for u < v. By employing an appropriate data structure, such as hash map for each v, checking the existence and acquiring I. [u] for a given node pair can be completed in ((1)
The precomputation for building the H-O index is in Algorithm We utilize two structures I and I!") to respectively record the distances acquired by Eq. 4 and Eq. (3). and save the distance to index I, only if there exists node r that cannot calculate the shortest distance using the H-1 index. In this way, we effectively constrain the H-O index size, and ensure that only caches the cases where H-1 may not produce the shortest distance.
4.3 HubGT Querying
After building the indices H-2, H-1, and H-O successively, querying label neighbors S(r) and their distances as in Section 4.1 can be achieved solely the I. without resorting to the raw graph structure. In Algorithm 3 we showcase the sampling procedure given an ego node r and respective sample sizes Sout and Sin. for out- and in-connections stored in L(r) and ('(r), respectively. The node-pair distance inside S(r) is presented as a symmetric matrix B,, and its entry value [u, v) B, fe, u] ((u,)). The distance query on (u, v) consecutively accesses H-0, H-1, and H-2 indices. If the H-O distance I,, [u] exists, it indicates the shortest distance according to Algorithm 2 Otherwise, the distance is either achieved by the local global hub labeling following Eq. (3) orienting a particular intermediary node r or I. Notably, queries regarding the ego node S(r) can be performed by only accessing the index of r without referring to others, which offers better memory locality and runtime efficiency.
As analyzed in Appendix A.I generating subgraph structures from the constructed labels preserves local neighbors while adding global hubs (Property []. This is preferable than the traditional adjacency- neighborhood sampling for GTs, it extends the receptive field beyond local neighbors described by graph adjacency and highlights those distant but important hubs in the whole graph for learning node interactions (Property 2 Meanwhile, non-hub nodes, usually the less significant nodes under heterophily, are constrained in local substructures with more similar neighbors (Property 3) From the efficiency aspect, it maintains the form of 1-hop sampling and prevents the exponential multi-hop operations.
Complexity Analysis. Let the label size [C(v)] bounded by Oss), H-1 and H-2 indexing complete the traversal of all nodes in O(ns + ms) time. The total index size is therefore bounded by O(ns). For H-O labeling in Algorithm 2) the computational overhead is O(nss),, where is the average size of L' Empirically, we enforce the index size to be less than s² for every I,, In summary, the time and memory complexities for the three-level indexing are O(ns² + ms) and O(ns?), respectively. substantially smaller than the
We highlight that the empirical label sizes observed in experiments theoretical bound thanks to the hierarchy that effectively reduces redundant information.
Querying one node pair distance by Algorithm 3 can be achieved in O(1) time when bit parallel and accessing hash map are both O11) operations. By selecting sample sizes such that s = 8in + Sout + 1, the subgraph size for each query node is [S() In consequence, querying every node r E V in

---

Input Graph & [H-0: 2-hop pair
Pair-wise SPD
Prediction
Output Classifier
Aga Aggregale
Residual
Subgraph Readout
PE Bias
Node Attention
H-I: local hub
H-2: global hub
Transfommer Encoder
doàoà
Ego
Neighbors
Linear Projection
Readout Block
Subgraph Sampling Token
Transformer
Label
Graph
Querying
Precomputation
Model Training
Figure 3: HubGT framework with precomputation and training stages. The precomputation stage processes the input graph and constructs the label index. During training, subgraph nodes and SPDs are queried from the index and applied as different Transformer inputs. Querying on CPU and training on GPU are pipelined and conducted simultaneously.
each training iteration, with each query node possessing at most 2 pair-wise distance computations, entails Onns)) overhead.
HubGT Framework
Once the index is built in precomputation, it remains static the RAM throughout GT training iterations, To efficiently exploit the labeling structure in HubGT, in this section, we claborate our end-to-end design querying graph hierarchy for both graph embeddings and positional encoding to facilitate GT learning. Figure illlustrates the overview of the pipeline.
5.1
Graph Information Querying
Subgraph for Node Embeddings. We leverage the subgraph hierarchy in the index, i.e., neighboring nodes in labels ((v) and ('(v) to generate node embeddings. Since the neighborhood size is variable, convert into fixed-length token S(v) by sampling in Algorithm The relative values of hyperparameters 8in and 8out can be used to balance the ratio between local long-tailed nodes and distant landmark nodes in respectively. The node embedding is generated by concatenating the raw attributes X [u] of subgraph nodes u Svv), denoted as X [S()))
SPD for Positional Encoding. Thanks to the efficient graph labeling, we are able to efficiently acquire SPD inside subgraphs by performing queries on the index. For each node r. Algorithm calculates the distances B, of node pairs inside the token S(r) under (ss²) complexity. learnable embedding scheme I'n NN + IR is then employed to map the distance of each entry in B, to the attention bias P used in Eq. (2). that P(u, v) = fn B, v)).
Global Hubs. Section 4.2 signifies set of global nodes used for H-2 labeling. For generating node embeddings, we further leverage these nodes as global lubs, that we consider these hubs connected to every nodes E V and can be similarly sampled during token generation. In HubGT training, set their attributes to be learnable along with model weights. This scheme actually generalizes the virtual node utilized in 2 to of hubs. The learnable embeddings able aggregate information from connected nodes throughout learning, which eventually offers an representation of the graph in higher level of hierarchy, and benefits GT for retrieving graph-level information.
5.2 Representation Learning
Since our contribution focus on the labeling process, HubGT adapts the scalable GT architecture 2 I3 incorporating subgraph precomputation and mini-batel training, which can potentially be enhanced by further acceleration techniques developed for the Transformer architecture.
The input subgraph embeddings are first projected as H [v] = MLPx (X ((D))) by an MLPx. Then, L Transformer layers characterized by Eqs. (1) and (2) are applied to predict the node representation H [u] with positional encoding P. Lastly, introduce readout block to calculate attention within
7

---

the token S(u) to aggregate the output of each ego node before the output classifier MLP2:
(H H [u]) [u])WE
Z [0] MLP2
H [v]
H
Σ uES(v)
au (uHH(L))) ml). where au Eues(o) exp ((H H [M] WE)
exp
(5)
Complexity Analysis. During model training. one epoch of I--layer feature transformation on all nodes entails F(InF)) complexity, while positional encoding is performed under (ns²). The RAM footprint is (nns²) and O(nsF) for sampled tokens and features, respectively. For mini-batch training with batch size nb. the VRAM overhead on GPU for batch node representations and bias matrices is OLL,,F)) and nyss respectively. It can be observed that the GPU memory footprint is determined only by batch size and is independent of the graph scale, ensuring favorable scalability.
Remarkably, querying a batch of nodes by Algorithm 3 can be conducted in parallel. The SPD query on CPU can be pipelined with GT training on GPU, so that training can be performed seamlessly without blocked by the querying process. HubGT inputs of embedding and encoding can be manipulated in-place on X and B,, and no graph-scale computation is required during learning iterations. Therefore, only strides of X and batches of B, are loaded onto GPU.
Experiments
6.1 Experimental Settings
Tasks and Datasets. We focus on the node classification task on 14 benchmark datasets covering both homophily (37 38 [3] and heterophily 44 41. Compared to conventional graph learning tasks used in GT studies, this task requires learning on large single graphs, which is suitable for assessing model scalability. We follow common data processing and evaluation protocols as detailed in Appendix C Evaluation is conducted on a server with 32 Intel Xcon CPUs (2.4GHz), an Nvidia A30 GPU (24GB memory), and 5 512GB RAM.
Baselines. Since the scope of this work lies in the efficacy and efficiency enhancement of the GT architecture, we primarily compare against lcading scalable Graph Transformer models with attention- based layers and mini-batch capability. Methods including Exphormer [19) DIFFormer 8 and PolyNormer [12] are considered as kernel-based approaches. NAGphormer [. GOAT [10),
HSGT [4], and ANS- GT 13 stand for hierarchical GTs. Three message-passiin GNNs, including
GCNJK 42). MixHop 43 and SGFormer 44 are also included for comparison.
6.2 Performance Comparison
Table 2 presents the efficacy and efficiency evaluation results on 8 large-scale graphs, while results on other datasets can be found in Appendix[D.] Visualization of the experiment results are presented in Figure 4 As an overview, HubGT demonstrates fast computation speed and favorable mini- batch scalability throughout the learning process and is applicable to million-scale graphs. It also achieves top-tier accuracy 11 out of 14 datasets, demonstrating favorable balance between effectiveness and efficiency.
Time Efficiency. Benefiting from the decoupled architecture, HubGT is powerful in achieving competitive learning and inference speeds with existing efficiency--rientee GTs. It consistently showcases the fastest inference, since Section elaborraes that label querying can be pipelined in asynchronous execution, and the process is as simple as Transformer operations without the interference of graph computation.
In comparison to other hicrarchical GTs, HubGT excels with the fastest training and overall learning time. Specifically, its precomputation is 250-1000x faster than ANS-GT, which also relatively fast in model training and inference. Aligned with our complexity analysis in Section 2 the overhead of HubGT indexing is mainly relevant the node size n and is less affected by m and F compared to precomputation in other methods, which ensures its efficiency on denser graphs such as REDDIT and PENN94. Baselines models employing graph-altered learning schemes including DIFFormer, PolyNormer, and SGFormer are empirically fast in training due to the simplified model architecture. However, it is noticeable that their inference reply on the full-graph structure and can be only performed on CPU without GPU computation, resulting in slower and less scalable performance.
8

---

Table 2: Effectiveness and efficiency results on large-scale graph datasets, while more evaluations are in Appendix D.2, "Pre." "Epoch", and "Infer" are precomputation, training epoch, and inference time (in seconds), respectively. "OOM" implies that the model encounters the learning process exceeds the time limit of 24 hours before convergence, Respective results of the first and second best performances are marked in bold and underlined fonts.
error. "TLE" means the
Homophilous
PHYSICS
DGRN-ARXIT 169, 119,313/2, 2, 315,598 Eguch Infor
REDINT
OGBN-MAG
Scale
34, 193 195, 921 Eguch Infer
232, 965 / 1114, 615,
736, / 792, 672
Metries
Pro.
Ace
Pro.
Ace
Pre.
Eguch Infor
Ace
Prv.
Epoch Infer
Ace
GCNJK
0.49 0.05 94.67=0.02
0.29 0.02 60.03
1.6 0.16 88.9940.39
0.96 0.10 28.65
MixHop
1.0 0.07 95.3720.12
0.79 0.05 60.3810.08
1.6 0.12 91.6110.13
0.68 0.06 30.52:0.04
SGFormer
0.52
96.33+0.29
0.82
72.55+0:28
21 95.63+0.29
1.7
5.1 33.47+0.6
Exphormer
84
1.7 1.0 96.08a0.11
32
1.8
0.46
67.8720.18
(OOM)
(OOM)
DIFFormer"
1.7
3.8
16.1011.11
0.89
4.1 55 90.90+884 23
2.4 21 94, 377
1.7
9.7 31.13+0.48
PolyNormer'
0.76
2.4
16.5910.16
0.83
11
13.24
5.3 246 06.6440.77
20
992 32,42a0.15
NAGphormer
33
8.4
2.4
96.5220.24 24
4.4
2.2
67. 85
280
3.2 2.1
95.7740.08 08
10.3
2.2 33,23+0.06
ANS-GT GT
2203
63
96.31=0.28
16205
109
2.7
71.0640.45
(OOM)
(OOM)
GOAT
14
12
96.24.0.15
1823
48
61 69. 67.06610.7
628
141
104
(TLE)
2673
116
102
(TLE)
HSGT
12
41
62
96.05=0.50
16
475
142
68.
30.30HH0..0 32
614
453
482
(TLF)
182
582
629
(TLF)
HubGT (ours)
2.0
2.9
0.31
96.3810.25
30
9.3
1.3
69. 19..33
192
21
1.6
94.3920.06
523
62
1.2
33.7420.24
Heterophilous
PENN94
GENIUS
TWITCH-GAMER
POKEC
Scule
41, 564 2, 724, 458
421, 961 1, 848,,,773 736
168, 165,114 114/ 505, 114
1, 6,632, 803 / /4, 603, 928
Metries
Pre.
Epoch Infer
Ace
Pre.
Epoch Infer
Ace
Pre.
Epoch Infer
Ace
Pre. Epoch Infer
Ace
GCNJK
0.35 0.04 65.9 10.16
0.06 0.03 80.65
0.15 0.03 59.91
0.06 0.09 59.3820.21
MixHop
0.31 0.04 75.00 25.00+0.37
0.08 0.01 80.63+0.04
0.11 0.01 01
0.15 0.03 64.02+0.02
SGFormer*
0.95 0.55 77.52a0.56
0.72 2.4 85.0120.25
0.38
3.3 65.93a0.15
4.4 29. 13.1320.16
Exphormer
(OOM)
(0OM)
42
1.3
0.41 64.2440.35 35
(OOM)
DIFFormer*
0.53 0.65 61.77=3.41
0.77
5.5 84.52+0.36
0.61
5.1
60.81+0.44
4.6 15 73.89=0.35
PolyNormer'
0.58
18.4 79.87=0.06
0.77
28 85 6..40...
1.5
89
64.72a0.65
4.2
67 81.0320.08
NAGphormer
237
6.1
2.1
74.45=0.60
38
5.4
1.0
83.88+0.13
16
1.9
2.4
61.92+0.19
70
3.1 16.1
73.06e0.05
ANS-GT
3889
42
67.76x1.32
34092
37
5.0
67.7611.32
12924
19
6.7
61.5520.45
(OOM)
GOAT
33
71.42+0.44
2664
28
39
00.1242.37
3348
63
61.3840.83
3855
760 804
(TLEF
HSGT
115
110
67.77a0.27
98
114
84.03
68
235
253
61.60.0.09
551
1420
1557
(TLE)
HubGT (ours)
7.3
3.4
0.29 78.13=0:43
125
23
2.5
89.68+0048
44
49
12
1.2 67.03+2.17
5422 99
13
76.96=0.44
Inference of these models is performed on the CPU in full-butch manner due to their requirement of the whole graph.
We additionally note that while some models claim to be applicable to million-scale graphs as shown in Table [] they exhibit excessive training time in our settings and fail to produce convergent results in one day. Hence, we only record the efficiency evaluations in Table In particular, ANS-GT demands a high memory footprint for storing and adjusting its subgraphs, which exceeds the memory limit of our platform for the largest graphs.
Memory Footprint. In modern computing platforms, GPU memory is usually highly constrained and becomes the scalability bottleneck for the resource-intensive graph learning. HubGT exhibits efficient utilization of GPÚ for training with larger batch sizes while avoiding the out-of-memory issue. In comparison, drawbacks in several model designs prevent them from efficiently performing GPU computation, which stems from the adoption of graph operations. Notably, kernel-based models require full graph message-passing in their inference stage, which is largely prohibitive on GPUs and can only be conducted on CPUs. HSGT faces the similar issue caused by its graph coarsening module. We note that these solutions are less scalable and hinder the GPU utilization during training.
Prediction Efficacy. HubGT successfully achieves top or comparable accuracy on evaluated datasets in Table 2 and Table with significant accuracy improvement several graphs such as CHAMELEON and TWITCH-GAMER. We attribute the performance gain to the application of the label graph hierarchy and SPD positional encoding in HubGT, which offers global information and effectively addresses the heterophily issue of certain graphs as analyzed in Section 4.1 The label sampling scheme also facilitates learning hierarchy throughout queries under controlled overhead. Since the label graph also preserves edges in the raw graph, the performance of HubGT is usually not lower than learning on the latter.
In comparison, baseline methods without hierarchical graph designs, including DIFFormer, NAG- phormer, and HSGT, perform relatively worse especially under heterophily. This is because their

---

Oveall
Cherall
Misllp
80
Rolativ Litoenoy
70
Infir
jo
DiEFsesac
Explaeas
Infer
100
DePFeeme NMGgaam
30+
30
ANS-CT
NSSCT
Bepler Seeeaa Norzaer
12
40
GOMT
30
BSST
HSCT
300
100
Epoch
Epoch
Rellttie Accurary (53
(a) Overall Efficiency Acc
(b) Metrics for kernel based (left) and hierarchical (right) GTs
Figure 4: Relative model compassion for average evaluation metrics (in %) across datasets in Table 2 (a) Trade-off between efficiency and effectiveness. Models on the upper right corner exhibit better efficiency and accuracy. HubGT showcases favorable balance for achieving top-tier accuracy with better efficiency. (b) Detailed relative scores for respective metrics and models. Detailed computation for the scores explained in Appendix D.2
models tend to rely on the raw adjacency or even promote it with higher modularity. As consequence, node connections retrieved by GT attention modules restrained in the local neighborhood and hardly produce accurate classifications. On the other hand, while PolyNormer achieves remarkable accuracy on several graphs thanks to its strong expressivity, its performance is largely suboptimal on small homophilous graphs as we further evaluated in Appendix D.2
6.3 Ablation Study
Table examines the respective effective- ness of the hierarchical modules in the HubGT network architecture, where we separately present results on homophilous and heterophilous datasets. It be ob- served that the model without SPD bias suffers the greatest accuracy drop, since topological information represented by po- sitional encoding is necessary for GTs retrieve the relative connection between nodes and gain performance improvement over learning plain node-level features.
Table Ablation study of HubGT model components. The first line shows the accuracy of the complete HubGT architec- ture. Each subsequent line indicates the performance differ- when the specified module removed.
Dataset
CITESEER
A
CHAMELEON
A
HubGT
75.47
43.63
w/o Node Readout
72.21
-3.26
38.76
-4.87
w/o Global Hubs
71.15
-4.32
37.08
-6.55
SPD Bias
68.55
-6.92
36.52
-7.11
In HubGT, the learnable global hub representation is invoked to provide adaptive graph-level context before Transformer layers, while the attention- based node-wise readout module aims to distinguish nodes inside subgraphs and aggregate useful representation after encoder transformation. in Table both modules achieve relatively higher accuracy improvements on the heterophilous graph CHAMELEON, which validates that the proposed designs are particularly suitable for addressing the heterophily issue by recognizing hierarchical information.
shown
7 Conclusion
In this work, we present HubGT, a novel PE calculation featuring the decoupled graph hierarchy through hub labeling. Our analysis reveals that the label graph exhibits an informative hicrarchy and enhances GT attention learning on the interaction between nodes. Regarding efficiency, construction and distance query of the label graph can be accomplished with linear complexity and are decoupled from iterative model training. Hence, the model benefits from scalability in computation speed and mini-batch training. Empirical evaluation showcases the superiority of HubGT, including efficacy under both homophily and heterophily, as well as efficient computation especially for inference on large-scale graphs of up to millions of nodes.
10

---

Acknowledgments and Disclosure of Funding
This research supported by the National Research Foundation, Singapore under its AT Singapore Programme (AISG Award No: AISG3-RP-2024-00
Singapore MOE AcRF Tier-2 funding (MOE- SDEP20122-0003) and NTU startup grant (020948-00001), Ningyi Liao supported by the Joint NTU- Brunk Research Centre on FinTeec,, Nanyang Technological University, Singapore. Zihao Yu supported by STAR RIE2025 Manufacturing, Trade and Connectivity (MTC) Programmatic Fund (M24N660043) administered by S
References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, t. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[2] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems. 34:28877-28888. 2021.
[3] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266-1333 13279, 2021.
[4] Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Global self- attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 655 665,, 2022.
[5] Wenhao Zhu, Tianyu Wen, Guojie Song, Liang Wang, and Bo Zheng. On structural expressive power of graph transformers. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3628-3637, Long Beach CA USA, August 2023.
ACM.
[6] 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.
[7] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501114455 2022.
[8] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. Difformer: Scalable (graph) transformers induced by energy constrained diffusion. In The Eleventh International Conference Learning Representations, 2023.
[9] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. In 11th International Conference on Learning Representations, February 2023.
[10] 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, pages 17375-17390 PMLR, 2023.
[11] Jiahong Ma. Mingguo He, and Zhewei Wei. Polyformer: Scalable graph transformer via polynomial attention. 2023.
[12] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expressiee graph transformer in linear time. The Twelfth International Conference on Learning Representations, 2024.
[13] Zaixi Zhang, Liu, Qingyong Hu, and Chee- Lee. Hierarchical graph transformer with adaptive node sampling. Advances in Neural Information Processing Systems, 35:21171-21185, 2022.

---

[14] Wenhao Zhu, Tianyu Wen, Guojie Song, Xiaojun Ma, and Liang Wang. Hierarchical transformer for scalable graph learning. In Proceedings of the Phiroy-Second International Joint Conference on Artificial Intelligence, pages 4702-4710, 2023.
[15] Yosuke Yano, Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 1601-1606, 2013.
[16] Takuya Akiba, Yoichi Iwata, Ken ichi Kawarabayashi, and Yuki Kawata. Fast shortest-pate distance queries on road networks by pruned highway labeling. 2014 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pages 147-154.
[17] Ye Li, Leong Hou U. Man Lung Yiu, and Ngai Meng Kou. An experimental study on hub labeling based shortest path algorithms. Proc. VLDB Endow., 11(4):445-44 457, December 2017.
[18] Wonpyo Park, Woong- Gi Chang, Donggeon Lee, Juntae Kim, al. Grpe: Relative positional encoding for graph transformer. In ICLR2022 Machine Learning for Drug Discovery, 2022.
[19] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In Proceedings of the 40th International Conference Machine Learning, pages 3 31613-31632. PMLR, July 2023.
[20] Cong Chen, Chaofan Tao, and Ngai Wong. Litegt: Efficient and lightweight graph transformers. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 161-170, 2021.
[21] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
[22] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Pro- cessing Systems, 34:21618-21629, 2021.
[23] Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pages 3469-3489. PMLR, 2022.
[24] Haiteng Zhao, Shuming Ma. Dongdong Zhang, Zhi-Hong Deng, and Furu Wei. Are more layers beneficial to graph transformers? The Eleventh International Conference on Learning Representations, 2023.
[25] Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Make heterophilic graphs better fit gnn: A graph rewiring approach. IEEE Transactions on Knowledge and Data Engineering. 36(12):8744 8757, December 2024.
[26] Qimai Li, Xiaotong Zhang, Han Liu, Quanyu Dai, and Xiao-Ming Wu. Dimensionwise separable 2-d graph convolution for unsupervised and semi-supervised learning on graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 953-963, Virtual Event Singapore, August 2021, ACM.
[27] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In 39th International Conference on Machine Learning. June 2022.
[28] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In 10th International Conference on Learning Representations, 2022.
[29] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Repre- sentations. arxiv, February 2020.
[30] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal, GraphiT: Encoding graph structure in transformers, June 2021.
12

---

[31] Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriang Puneet K. Dokamia, Mark Coates, Philip Torr, and Ser-Nam Lim, Graph inductive biases in transformers without message passing. In 40th International Conference on Machine Learning, volume 202, pages 23321-23337 PMLR, May 2023.
[32]
Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. A bub- labeling algorithm for shortest paths in road networks. In Panos M. Pardalos and Steffen Reben- nack, editors, Experimental Algorithms, pages 230-241, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[33] Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Wernec. Hierarchical hub labelings for shortest paths. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012, pages 24-35, Berlin, Heidelherg, 2012. Springer Berlin Heidelberg.
[34] Dian Ouyang, Dong Wen, Lu Qin, Lijun Chang. Xuemin Lin, and Ying Zhang. When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries road networks. The VLDB Journal, 32(6): 1287 November 2023.
[35] Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pages 349-360. ACM, June 2013.
[36] Takuya Akiba, Takanori Hayashi, Nozomi Nori, Yoichi Iwata, and Yuichi Yoshida. Efficient top- k shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
[37] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008.
[38] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /.1.0866,, 2018.
[39] Weihua Hu, Matthias Fey, Marinka Zitiik Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, Jure Leskovec, Regina Barzilay, Peter Battaglia. Yoshua Bengio, Michael Bronstein, Stephan Günnemann, Will Hamilton, Tommi Jaakkola, Stefanie Jegelka, Maximilian Nickel, Chris Re, Le Song, Jian Tang, Max Welling, and Rich Zemel. Open Graph Benchmark: Datasets for Machine Learning on Graphs. 33rd Advances in Neural Information Processing Systems, 2020.
[40] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. In 34th Advances in Neural Information Processing Systems, 2021.
[41] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at evaluation of gnns under heterophily: Are we really making progress? In //th International Conference on Learning Representations, 2023.
[42] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In 35th International Conference on Machine Learning, volume 80. PMLR, 2018.
[43] Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In 36th International Conference on Machine Learning, volume 97. PMLR, 2019.
[44] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for surge-graph representations. Advances in Neural Information Processing Systems, 36, 2023.
[45] Yuxuan Shi, Gong Cheng, and Exgeny Kharlamov. Keyword search over knowledge graphs via static and dynamic hub labelings. In Proceedings of The Web Conference 2020, pages 235-245, Taipei Taiwan, April 2020. ACM.
13

---

[46] Guoming Li, Jian Yang, Shangsong Liang, and Dongsheng Luo. Polynomial selection in spectral graph neural networks: An error-sum of function slices approach. In Proceedings of the ACM Web Conference, January 2025.
[47] Simon Markus Geisler, Arthur Kosmala, Daniel Herbst, and Stephan Günnemann. Spatio- spectral graph neural networks. Advances in Neural Information Processing Systems, 37:49022- 49080, December 2024.
[48] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[49] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In 8th International Conference on Learning Representations, 2017.
[50] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. 7th International Conference on Learning Representations, pages 1-15, 2019.
[51] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 6861-6871, 1 6 2019.
[52] Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji Rong Wen. Scalable graph neural networks via bidirectional propagation. 33rd Advances in Neural Infor- mation Processing Systems, 2020.
[53] Ningyi Liao, Dingheng Mo, Siqiang Luo, Xiang Li, and Pengcheng Yin. Scara: Scalable graph neural networks with feature-oriented optimization. Proceedings of the VLDB Endowment, (5(11):3240-3245 2022.
[54] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, pages 1-15, 2018.
[55] 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 of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. pages 257-266, 2019.
[56] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. In 33rd Advances in Neural Information Processing Systems, 2019.
[57] Wenzheng Feng, Yuxiao Dong, Tinglin Huang, Ziqi Yi.. Xu Cheng, Evgeny Kharlamov, and Jie Tang. Grand+: Scalable graph random neural networks. In Proceedings of the ACM Web Conference 2022, pages 3248-3258. ACM, April 2022.
[58] Chenhui Deng, Zhiqiang Zhao, Yongyu Wang. Zhiru Zhang, and Zhuo Feng. Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding. In 8th International Conference on Learning Representations, February 2020.
[59] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, volume 1, pages 6684 Virtual Event Singapore, August 2021. ACM.
[60] Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. In 9th International Conference on Learning Representations, February 2021.
[61] Ningyi Liao, Siqiang Luo, Xiang Li, and Jieming Shi. Ld2: Scalable heterophilous graph neural network with decoupled embedding. In 36th Advances in Neural Information Processing Systems, volume 36, pages 10197-10209, Curran Associates, Inc., December 2023.
14

---

[62] Pak Lon Ip, Shenghui Zhang, Xuckai Wei, Tsz Nam Chan, and Leong Hou U. Bridging indexing structure and graph learning: Expressive and scalable graph neural network via core-fringe. OpenReview preprint, 2024.
[63] Juechu Dong, Boyuan Feng, Driss Guessous, Yanbo Liang, and Horace He. FlexAttenion:: A programming model for generating fused attention variants. In 8th Conference on Machine Learning and Systems, May 2025.
[64] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with Py Torch Geometric. In 7th International Conference on Learning Representations, ICLR 2019 Workshop Track Proceedings, 2019.
[65] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In 3/st Advances in Neural Information Processing Systems, 2018.
[66] Seiji Maekawa, Yuya Sasaki, George Fletcher, and Makoto Onizuka. GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Infor- mation Systems, 115:102195, 2023.
[67] Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Dynamic and historical shortest-paid trattsst--athhhe distance queries on large evolving networks by pruned landmark labeling. In Proceedings of the 23rd international conference World wide web, pages 237-248. ACM, April 2014.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We accurately claim our contributions Section !
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations and potential improvements are discussed in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
Preliminary and assumptions are provided in Section 4.1 and Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experiment details and configurations are in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [Yes]
Justification:
Reproducibility instructions and scripts are available in the codebase.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /niipe.cc/pullic/guiii wwwtc//ggui////eeeeceoocc CoodeSubeiiieeee ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experiment details are Appendix Guidelines:
C
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are reported in main experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiment details are in Section 6.1 and Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics atttps://nee httppris///eriiss... httpp//p......bi.cctttcsooooooo.
Answer:
[Yes]
Justification:
We conform the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader impacts discussed in Appendix H
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
19

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is for foundational research and do not foresee such risks. Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:
[Yes]
Justification: Baselines and datasets are cited and referred in the codebase and discussed in Appendix B
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsspipeaattteeeeee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
20

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our model setups are in Appendix Tuning scripts are in the codebase.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not require IRB approvals.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
21

---

A Detailed Theoretical Analysis
A.1 Label Graph Properties
In SPD calculation, the index C(u) is said to form 2-hop cover if for an arbitrary node pair u, v E V. there exists a node E (((v), A 2-hop cover ensures that any SPD queries can be acquired by Eq. 44. A straight-forward approach to build the 2-hop cover is to traverse the whole graph for each node successively. This is, however, prohibitive due to the repetitive traversal and overlapped labels.
As briefed in Section 4.2 the Pruned Landmark Labeling (PLL) algorithm searches labels by a pruned BFS for each node in V/ relying on a particular order. Denoting each node by unique index 1, n, indicates that node u precedes node in the sequence. The labeling process performs a pruned Breadth First Search (BFS) for each node from 1 to n, adding hubs with shorter distances into the label set while eliminating the search from insignificant nodes. Notably, the algorithm agnostic to the search order. In this work, we follow [I5] to adopt the descending order of node degrees as it can be efficiently acquired and offers decent performance. While other orders such as betweenness centrality are adopted for labeling [5 34], they nonetheless incur additional computational overhead.
In this part, we formally formulate the hierarchy in graph labels. By considering the nodes in labels as edge relationship, the wholistic label set L can be regarded as derived graph 9 (V, E) with directed and weighted edges, namely the label graph. Its edge set depicts the elements in node labels computed by graph labeling, that an edge (u, v) E E if and only if (v, 5,) E L(u), and the edge weight is exactly the distance in graph labels 6,- = b(u, v). The in- and out-neighborhoodss based on edge directions are Nin = (u, v) E E and Noue(v) = {ul(t, u) E ε), respectively. For simplicity, assume that the original graph 9 is undirected, while properties for a directed G can be acquired by separately considering two label sets Lin and Lour for in- and out-edges in E.
We summarize the following three properties of the label hierarchy produced by PLL:
Property For an edge (u, v) E E, there is (v, u) E é when u < u, and (u, v) E E when u >> v.
Referring Algorithm I when the current node is u and direct neighbor of v. Hence, (e, 1) is added to label C(u) at this round, which is equivalent to adding edge (u, v) to E. Similarly, (v, u) E & holds when e > u. For example, the edge (1, 4) in Figure 5(a) is represented by the directed edge (4, in Figure 5(b) Property [ implies that (w)) C Nin (v) U.Noue (e), i.e., the neighborhood of the original graph is also included in the label graph, and is further separated into two sets according to the relative order of neighboring nodes.
u, 6, 1 holds since u is the
Property 2 For a shortest path P(u,u) u) in G. there is (w, E E for each E P(u,, u) satisfying
w > C.
35 proves that there is u E L(w) for E P(u, v) and w > v. Therefore, considering shortest paths starting with node v of a small index, i.e., being a "landmark" node, then succeeding nodes w > v in the path are connected to v in G. In Figure 5()) the shortest path between (1, passing node 2 results in edges (2, 1) and (5, 1) in Figure 5(c) since nodes 2 and 5 are in the path and their indices are larger than node 1. When the order is determined by node degree, high-degree nodes
Input Graph
Edge (4, 1)
Edge (2, 1), (5, 1)
NO Edge for (5, 6)
4
2
4
2
4
2
4
2
5
5
5
5
X
3
3
3
3
6
G
6
6
(a) Raw Graph
(b) Property 1
(c) Property
(d) Property
3
Figure 5: Examples of properties of the label graph 9 corresponding to the original graph g. Number inside each node denotes its index in descending order of node degrees.
22

---

appear in shortest paths more frequently, and consequently link to majority of nodes, including those long-tailed low-degree nodes in G.
Property 3 For a shortest path P(u, v) in G. if there is w E P(u, 2) and w < v, then (u, v) & E.
According to the property of shortest path, there is b(u, u) b(u, w) + b(w, v). Hence, the condition of line in Algorithm[|] is not met at the v-th round when visiting w. In other words, the traversal from is pruned at the preceding node w. By this means, the in-neighborhood N... (v) is limited in the local subgraph with shortest paths ending at landmarks. As shown in Figure the shortest path between (5, 6) passes node 1, indicating that (5, 6) are not directly connected since their distance can be acquired by edges (5, 1) and (6, 1). As consequence, the neighborhood of node 5 in 9 is constrained by nodes 1 and 2, preventing connections to more distant nodes such as 3 or 6.
In brief, Property ensures that neighboring nodes in the raw graph 9 are still connected in C. Properties 2 and jointly imply that a small number of hub nodes, or landmarks, naturally emerge when more shortest paths pass through these nodes, and reside in a large number of node labels during the labeling process. On the contrary, for insignificant nodes with higher indices, the pruned traversal constrains the visit to the local neighborhood and limit their label size. Thus, we reckon that the PLL process builds a hierarchy embedded in the node labels, distinguishing global hubs while preserving original adjacency.
A.2 Discussion on Indexing
Intuitively, facilitate label pruning during indexing, the hierarchy needs to be built in top-down manner, i... first performing Algorithm I [without pruning (line 11) for global hubs to generate H-2; then performing the actual Algorithm to build H-1; lastly, remaining miss cases are stored to H-2.
Hierarchy-2. In our implementation, the H-2 construction is performed prior to H-1, offering an additional condition for BFS pruning and cache saving. As demonstrated in [35], the bit-parallel global index design is advantageous in reducing the overall label size and facilitating faster indexing time. It also benefits from bit-parallel processing and fast SPD computation similar H-1.
Hierarchy-L. In Algorithm I distance calculation and set intersection can be boosted by bit- parallel operations. MV.(v) (v) can also be stored bit-wise in a word. Hence, constructing the H-1 index shares the same overhead with PLL. while offering the extended distance information based on local computation orienting hubs.
Hierarchy-0. Examining Property 2 it can be inferred that the intermediary node presents on the shortest path r E P(u, v) if and only if r E [(u) n C(v). We hence equivalently rearrange the traversal order of 2-hop pairs u ('(r), r E L(v) for all possible presence of shortest paths in Algorithm 2] where L, L' are produced by Algorithm [ The search and I, construction for each node can be performed parallel since they are mutually independent.
A.3 Discussion on Querying
Conversely, to ensure fast query speed, Algorithm B performed in a bottom-up sequence with early termination: for each node pair, if the distance is cached in H-0, then it is the exact SPD and can be immediately returned; otherwise, distances from H-1 and H-2 are calculated, and the smallest one is chosen the SPD answer. Performing the pair-wise query for all node pairs in S(r) naturally leads to the sampled subgraph as well as the SPD matrix.
B Detailed Comparison with Existing Models
B.1 Kernel-based GTss
GraphGPS 7 combines rich positional and structural encodings with interleaved local message-passing and linear global attention to achieve both expressivity and linear complex- ity in node and edge counts. However, its preprocessing stage (e.g., computing structural encodings) incurs an O(N3) time complexity.
Exphormer [19 leverages virtual nodes and expander graphs to augment the input graph for GT training. The expander graph adds random edges and preserves certain properties of
23

---

Algorithm 1: HubGT H-1 Indexing
Input: Graph g (V,E), Max neighbor size Output: H-1 Labels C, C²
1 Sort V based on degree d(u)
2 C(v) < Ø, (v)) t- Ø for all v eV
for no
(oc, 2,0) for aorallo ev (L. Ø) for all c Queue 2 + ((r,0), (.). (0,0,
(e)
(e)
7
while Q Ø do
8
Q + Ø, @ -
Pop the Get (v,) from Bg. 4 with existing labels
(v. b( r)) from 2
if ((v,r) < ((0) (w,r) [[e) < then
[(v) + (r, ((),))
13
('(r) < C'(r) (v, b(e,r))
14
for all u (u)) such that > do
15
if g(u) q(u) then
Push (u, (),,)(
the end Q @' p' ((u,))) q(u) q(v) +1
else q(u) ((v) then
Q +- @ ((,,))
20
for all (u,v) E Q do
21
(u(u) e- (M((() (v)
for all (u, Q' do
.M(w) (M (M)
MY((M) - M.)
return C'v) for VV
Algorithm HubGT H-O Indexing
Input: Graph labels C, L
Output: H-0 Index I
for v to
in parallel]
I + oc, [x] + -oo
2
3
for all E L(v) de
4
for all a E (r(r) such that a do
Get 6f (o,w) u) from Eq.
s
(f (v. > I [u]
then I (v, u)
(10) (n, + b(urr) b(r,
if (()((,))
I!" [u] then Z [ [u] (v,
9
for all E V such that I(") [u]
do
if z (0) [u] _ [u] and Zul < s² then
10
[M] I ( []]
return for all v
Algorithm 3: HubGT Query for node
Input: Index C, L' I. Sumple sizes
Output: Sampled subgraph nodes S(r) and SPD matrix B, S(r) fr)
Sample Soue nodes from ((F)) into S(r)
Sample sen nodes from (r) into S(r)
for all uu such that S(r), v S(r), do
if If [u] exists then
b(u, v) Io(u
7
Get (L v) from Eq.
Get ((2) (u, v) from Eq. for all global
b(,,e) +- (B(2) (u, ( (2, v)) [r|u, u] +- b(u, v). B.(v, [u, u] b(,,0) return S(r) and B,
24

---

the graph structure. Its GT component is mainly built upon GraphGPS, sharing the similar computational complexity.
NodeFormer [ introduces kernelized Gumbel-Softmax operator to enable linear-time all-pair message passing for scalable graph structure learning.
DIFFormer [
proposes an energy energy-constrained diffusion framework that derives closed- form optimal diffusivity to build diffusion- Transformer encoder.
PolyNormer presents a salyyomial-expresiii graph Transformer that learns high- degree equivariant polynomials via linear local-to-global attention scheme.
Overall, all kernel-based models incur per-layer training and inference costs of Q + L.FF) and memory O(nF + m), scaling linearly with both nodes and edges. Due to the lack of all-pair attention, they also exhibit stronger inductive bias of graph information and weaker expressive power compared to our method and hicrarchical GTs, particularly on heterogeneous graphs. In contrast, our method's computation and memory during training and inference depend only on node features, independent of edge count, which provides markedly better scalability on large, sparse graphs.
B.2 Hierarchical GTs
NAGphormer 9
aggregates multi-hop neighborhood features into a fixed-length token sequence per node (via Hop2Token] enabling true mini- batch Transformer training large graphs.
PolyFormer 11 builds a hierarchical Transformer by progressively coarsening the graph and exchanging information between levels to capture both local and global structure.
ANS-GT [3
uses an adversarial bandit to adaptively sample informative nodes and two-stage local/global attention scheme to capture long-range dependencies. its adaptive sampling requires O(ns² Lm) preprocessing, making it costly on large graphs.
GOAT [10] implements approximate global self-attention via low -ow-dimensional projection (K-Means) plus a local sampling module to support both homophilous and heterophilous graphs. however, the projection and codebook updates add extra overhead and approximation error.
HSGT [4] leverages multi-level graph coarsening and dedicated horizontal/verte Trans- former blocks to fuse information across scales. yet it demands hicrarchical sampling and historical embedding maintenance, increasing implementation complexity.
Overall, hierarchical GTs typically achieve stronger expressive capabilities than kernel-based models, especially for capturing complex, heterogeneous relationships across multiple scales. However, except for NAGphormer and PolyFormer, whose training and inference costs are independent of edge count, other hierarchical GTs still incur per-layer training and inference costs of OLLnF2 + LmFF) and memory (n + m) or even higher overhead, greatly undermines model efficiency when the graph is large. In contrast, our method's computation and memory during training and inference depend only on node features, independent edge count, offering superior scalability on large, sparse graphs
B.3 Non-GT GNNs
records individual layer representations as parallel channels for the last-layer concatenation and prediction, adding up hierarchical graph topological representations in the spatial domain.
GCNJK 42
MixHop 43 concatenates multi-hop spatial propagations in each of its message-passing layer. Such aggregation results in expanding width of representations over multiple layers.
TFGNN [46]
employs approximation of the graph spectrum by slicing, preserving topologi- cal properties and achieving practical streamlined processing.
integrates the spatial operator for local information and the spectral operator for global knowledge. The utilization of iterative eigen-decomposition also entails positional encodings to further augment the learning.
S:GNN 47
25

---

SGFormer [4 utilizes a single-layer global attention coupled with a simple GNN to capture all-pair interactions in one propagation step, achieving ON + E) complexity without any positional encodings, pre-processing. or edge embeddings, but with limited expressive power for complex graph structures. SGFormer offers O + F) efficiency but lack the rich positional and structural encodings that give graph Transformers their superior expressivity.
Generally, while these cesssag--assiigg GNNs offer linear time complexity, different issues may arise. For instance, GNNs using full graph topology for propagation usually entail (m))) memory overhead, which is less scalable. Similar to GT, this be addressed by baii-bbtchhnng with RS, but risks hindering efficacy. Empirically, these GNNs also exhibit more training epochs than GTs before convergence. Consequently, while the epoch time seems shorter, the total training time is par with GTs.
We highlight that these works are largely orthogonal to HubGT, focus is advancing the capabilities of graph Transformer models, rather than benchmarking against message- saaesagg--asingggg GNN architectures.
B.4
Scalable and Heterophilous Convolutional GNNs
The scalability issue has been extensively examined for convolutional Graph Neural Networks (GNNs) some of the largest graph datasets with linear or 52 5 Graph simplification techniques including sampling
48
49]. featuring the decoupled processing
even sub-linear complexity (50 5T
554
55 [66
57) and coarsening [58 59 60) are also explored for reducing the graph scale at different
hicrarchy levels. Although the levellevel idea of designing convolutional GNNs is helpful for GTs,
Transformer- models are unique in respect to their graph data utilization and architectural bottlenecks, and hence require specific techniques for addressing these issues.
Heterophily is another prominent drawback of common GNNs, which describes the scenarios that neighboring nodes belong to different classes, and the inductive bias in these models are no longer effective. Addressing the issue usually requires tailored management of the underlying graph hierarchy beyond edges, typically realized by enhancing convolution operations [26 27 61] or augmenting the graph topology refine graph convolution.
28 25
A recent work 62 also employs the idea of hub labeling to
B.5 Traditional Hub Labeling
We highlight that HubGT and canonical hub labeling address distinct query scenarios and design goals, leading to different performance index construction and SPD querying. In HubGT, we prioritize querying with (1) overhead and local label access, in order to prevent the excessive queries from blocking GT training. To this end, we adopt the H-O cache with additional precomputation and index size for fast distance access, while leveraging the neighboring property on label graph to construct H-1 index. Contrarily, classic hierarchical labeling approaches [35) (44] are designed for arbitrary node-pair queries. which is not applicable to the intermediary node technique in our H-1 local labeling, and entails (s) query time.
C Detailed Experiment Settings
Dataset Details. Table 4 displays the scales and heterophily status of graph datasets utilized in our work. Undirected edges twice in the table. CHAMELEON and SQUIRREL are the filtered version from [T), while OGBN-MAG is the homogeneous variant. We employ 60/20/20 random data splitting percentages for training, validation, and testing sets, respectively, except for OGBN-MAG, where the original split is used. Regarding efficacy metrics, ROC AUC is used on TOLOKERS following the original settings, and accuracy is used for the rest.
Hyperparameters. Parameters regarding the precomputation stage for graph structures are discussed in Appendix [33] For subgraph sampling, we perform parameter search for relative ratio of in/out neighbors represented by Sowt in rage [0, 48).
For network architectural hyperparameters, we use L = 4 Transformer layers with N₂ 8 heads and F 128 hidden dimension for our HubGT model across all experiments. The dropout rates for inputs (features and bias) and intermediate representation 0.1 and 0.5, respectively. The AdamW
26

---

optimizer is used with learning rate of 10 The model is trained with 300 epochs with early stopping. Since baseline GTs employ different batching strategies, is difficult to unify the batch size across all models. We set the batch size to the largest value in the available range without incurring out of memory exception on our 24GB GPU, intending for fair efficiency evaluation considering both learning speed and space.
Evaluation Metries. We use ROC AUC the efficacy metric TOLOKERS and classification accuracy on the other datasets. For efficiency evaluation, we notice that there is limited consensus due to the great variety in GT training schemes. Therefore, evaluation considering processing times of different learning phases for a fair comparison. Model speed is represented by the average training time per epoch and the inference time on the testing set. For models with graph precomputation, the time for this process is separately recorded.
attempt to employ comprehensive
D Additional Experiments
D.1 Empirical Observations
Visualization of Layer-wise Attention Bias. Corresponding to Figure 2 Figure presents the PE
bias matrices P(u, r) / (Br [u, ul) of the same SPD matrix B learned all layers in the GT model. The encodings are able to exhibit distinct values throughout GT layers, signifying the shift of receptive fields for the in-batch attention to nodes in different distances: in initial layers, node Identities are highlighted; in higher layers, clusters of similar neighbors are captured.
(a) L ==0
(b) -=
(c) (=)=2 =2
(d) L 3
Figure 6: SPD PE attention bias in different GT layers CITESEER.
Visualization of Graph Structures. An exemplary illustration of 4 small graphs is displayed in Figure 7 The original CHAMELEON graph heterophilous, i.e., connected nodes frequently belong distinct classes. In Figure 7 different classes are mixed in graph clusters, which pose challenge for GT' perform classification based on edge connections. contrast, nodes in the graph marked
Table 4: Statistics of graph datasets. f and No are the numbers of input attributes and label classes, respectively. "Train" is the portion of training set w.r.t. labeled nodes.
Heterophily
Dataset
Nodes m
Edges m
N₂
Train
CORA
2, 708
10, 556
1433
7
60%
CITESEER
3, 279
9, 104
3703
60%
PUBMED
717
88, 648
500
3
60%
Homophily
PHYSICS
34,
495,924
8415
60%
OGBN-ARXIV
169, 343
2, 315, 598
128
40
54%
REDDIT
232, 965
114, 615, 892
602
41
60%
OGBN-MAG
736, 389
10, 792, 672
128
349
85%
CHAMELEON
890
17, 708
2325
60%
SQUIRREL
2.3
93, 996
2089
60%
TOLOKERS
11, 758
1, 0388 000
10
2
60%
Heterophily
PENN94
41, 554
2,724,455
4814
2
60%
GENIUS
421, 961
1, 1,845, 736
12
2
60%
TWITCI-GAMER
168, 114
13, 595, 114
7
2
60%
POKEC
6362, 803
30, 60,,,22,5
65
60%
27

---

by graph labels in Figure 7 clearly form multiple densely connected clusters. exhibiting dis- tinct hierarchy. Certain classes can be intuitively identified from the hierarchy, which empirically demonstrates the effectiveness of our utilization of graph labeling.
(a) CORA Raw Graph
(b) CORA Label Graph
(c) CITESEER Raw Graph
(d) CITESEER Label Graph
(c) CHAM. Raw Graph
(f) CHAM. Label Graph (g) SQUIRREL Raw Graph (h) SQUIRREL Label Graph
Figure 7: Visualization of the hierarchy of original and label graphs on realistic datasets. Color of each node denotes its class.
D.2 Main Experiments on Small Graphs
Table presents the main effectiveness and efficiency evaluations on relatively small datasets. Discussion on the results are in Section 6.2
Table 5: Effectiveness and efficiency results small-scale datasets. "Pre." "Epoch", and "Infer" are precomputation. training epoch, and inference time (in seconds), respectively. "Mem." refers to peak GPU memory throughout the whole learning process (GB). Respective results of the first and second best performances on each dataset are marked in bold and underlined fonts.
Homophilous
CORA
CITESEER
PUBMED
Pre. Epuch
Infer
Mem.
Ace
Pre. Epoch Infer Mem.
Acc
Pre.
Epoch Infer Mem.
Apc
DIFForee"
0.11
0.13
1.2
83.37
0.07 0.07 1.7 74.65
0.37
0.35
2.7
75.77a0.40
PolyNormer
0.11
0.65
1.4
80.43+1.55
0.21 0.86
1.6
68.70+0.95
0.86
6.07
2.5
75.80e0.46
NAGphorner
0.68
0.01
0.06
0.5
76.9620.73
1.26
0.01
0.38
0.5 62.26x2.1
3.05
0.01
0.04
0.5
1.04
ANS-GT
43
2.0
1.12
2.0
85.42a0.52
59.9
11.65
4.25
11.9
73.5820.98
529
14
3.52
1.9
89.53
GOAT
10.1
0.25
0.93
2.5
78.26=0.17
11.1 0.31
1.04
64.69=0.43
57.4
0.34
1.61
5,3
77.76=0.97
HSGT*
0.1
1.81
2.33
0.5
81.73
0.06
0.87
1.23
0.9
69.72a1.02
5.0
3.89
4.44
24
88 8620.46
HubGT (ours) 0.42
0.20
0.02
2.5
88.58
0.43
0.24
0.02 2.0
75.47
2.6
1.47
0.16
1.7
89.80
Heterophilous
CHAMELEON
SQUIRREL
TOLOKERS
Pre. Epnch Infer
Mem.
Ace
Pre.
Epoch Infer Mem.
Acc
Pre.
Epoch Infer Mem. ROC AUC
DIFFormer"
0.09
0.38
0.50
37.83
0.05 0.05 0.7 35.73x1.37
0.16 85.8 0.88 74 74.88
PolyNormer
0.03
0.17
1.1
40.70=3.38
0.07 0.49
1.2 38.40=1.10
1.27
15.5 9.4
79.39=0.50
NAGphormer
0.27
0.03
0.03
0.5
33.18
0.85
0.08
0.08
0.5 32.0243.93
1.59
0.11
0.02
0.5
79.32a0.39
ANS-GT
11.2
1.98
0.78
2.8
41.19a0.69
28.1
4.48
1.95 6.6
37.15a1.10
716
2.37
3.42
10.7 79.31
GOAT
1.99
0.44
0.4
35.02+1.15
6.66
0.37 0.58
30.78+0.91
36.1
5.49 5.87
79.4620.57
HSGT*
0.01
0.73
32.28=2.43
0.01
0.42 0.74
34.32+0.51
2.62
7.76
8.12 17.4 79.24=0.83
HubGT (ours) 0.04 0.08 0.007
1.6
43.63+2.34
0.24 0.18 0.01 2.6 37.16#0.57
1.4 0.99 0.02 2.2 79.8640.47
Inference of these models performed on the CPU in full-batch manner due their requirement of the whole graph
The relative score for each metric is computed as the percentage with respective to the best record each dataset, i.e., the fastest efficiency and highest accuracy. Unavailable entries are regarded as 0% scores. Efficiency metrics contain the following perspectives and are computed in logarithm: "Epoch" and "Infer" are average training epoch time and inference time, respectively. Overall "Learn" time is computed by the sum of precomputation time and total
Visualization in Figure 4
28

---

Table 6: Effect of different search orders for hub labeling and HubGT learning outcomes on the homophilous CORA and the heterophilous CHAMELEON. Presented results include average index size (i.e., the number of labels) for each node, precomputation time (in seconds), and accuracy (in %). The best result for each column is marked in bold.
CORA
CHAMELEON
Centrality
H-1
H-0
Pre.
Acc
H-1
H-0
Prc.
Acc
Closeness
9.9
12.9
0.03
86.0
4.7
6.5
0.02
39.9
PageRank
2.3
2,4
0.04
85.8
1.1
1.1
0.02
36.0
Degree
2.4
2,5
0.02
86.0
1.3
1.3
0.02
38.9
Table 7: Effect of the maximum subgraph sample size s on the label graph based on CORA and PHYSICS. Presented results include the average degree after labeling (dafter), clustering coefficients before and after hub labeling (Chefores Cafter), index sizes (average number of labels), and total index file size (in MB).
Sample Size
CORA
PHYSICS
farter
Cuefore
Cafter
H-1
H-0
Size
dafter
Cuefore
Cufter
H-1
H-O
Size
16
3.90
0.241
0.648
2.4
2.5
6.2
14.38
0.377
0.302
22.6
135.0
118
32
3.90
0.241
0.621
2.4
2.5
6.2
14.38
0.377
0.306
40.6
230.9
147
48
3.90
0.241
0.584
2.4
2.5
6.2
14.38
0.377
0.300
55.9
294.6
170
training time. The overall efficiency in Figure 4(a) represents overall learning time, inference speed, and memory utilization.
D.3 Effect of Hyperparameters
Search Order. In Table 6 we present experimental results of | BFS based on different metrics such closeness centrality and PageRank. It can be observed that, closeness centrality results in larger average label sizes for both H-1 and H-O indices, which is in line with the observation in (35). Degree and closeness centrality lead to similar GT accuracy, while PageRank is less representative for selecting useful hubs.
As noted in Appendix [..11 the main consideration in hub selection is indexing efficiency. While other measures may be useful, there is additional overhead for computing these scores, which makes them less applicable to large graphs. Hence, we still recommend degree centrality, which can be efficiently acquired.
Subgraph Size in Indexing. 7 presents more details with varying s when constructing labels. We compute the average clustering coefficient C' before and after hub labeling, showing that hub labeling can flatten the node distribution by increasing the clustering property on less clustered graphs such CORA. Conversely, for highly clustered graphs and larger label sizes, C' is slightly reduced, as additional label connections make the graph denser with a more dispersed edge distribution.
For small graphs such as CORA, the average H-1 label sizes +C'+ do not vary with different upper bounds of s, which implies that the hubs are sufficiently connected to graph nodes. On the larger PHYSICS, increasing the small s = 24 can increase the actual label size, effectively incorporating more remote nodes to form the subgraph. However, the increase is less sigmificant for 48, which indicates that the hubs are already sufficiently connected. As the H-O label size [Z] is based on H-1 construction, it also exhibits less increase with larger 8, as the larger H-1 is able to cover more SPD pairs and suppress the need for H-O. For most configurations, the H-O size is significantly smaller than the theoretical bound (s²2). ensuring empirical space efficiency.
Subgraph Size in Querying. We then study the effectiveness of the label graph hierarchy in HubGT featuring the subgraph generation process in Figure &, which displays the impact of sample sizes s and Sout corresponding to Algorithm 3 Regarding the total subgraph size s, can be observed that a reasonably large s is essential for effectively representing graph labels and achieving stable accuracy. In the main experiments, we uniformly adopt constant s = 48 token size across all datasets, as is large enough to cover the neighborhood of most nodes while maintaining computational efficiency. As reference, the actual average H-1 index sizes of [((w) + [C' (v) among all nodes are 40.6 on PHYSICS and 47.7 PENN94, while the average H-O sizes [ [(v) are 230.9 and 1, respectively.
29

---

Both are significantly smaller than the theoretical bounds of 2s and s², which validates the efficiency of our three-level hierarchical labeling.
Within the fixed token length, the relative size of Sout indicates the preference of hubs with lower node indices. Comparing Fig- ures ((a) and [(b] of varying Sout under 48, can be observed that the accuracy tends to increase on the homophilous CITESEER. On the opposite, the performance on CHAMEI FON decreases when in- troducing more out labels under heterophily, showing that our Algorithm 3 sampling design effective in retrieving distinct graph information by adjusting the hyperparameters of 5out and Sin-
Jee
Sungle Sie
Sacipl Sta
(a) CITESEER
(b) CHAMELEON
Figure 8: Effect of sample sizes on different datasets.
Alternative Transformer Architecture. Thanks the decoupled design, HubGT is able seam- lessly integrate with alternative efficient Transformer architectures. To demonstrate, we implement FlexAttention (33 to replace the standard Transformer (MHA). The results presented in Ta- 8 Overall, FlexAttention achieves 10-20x speedup and significant reductions GPU memory footprint, verifying the benefits of improving the Transformer architecture.
Table 8: Effectiveness and efficiency results for alternative architectures.
Model
CORA
GENIUS
Epoch
Infer
Mem.
Acc
Epoch
Infer
Mem.
Acc
HubGT+MHA
0.20
0.018
2.5
86.0
23.7
2.58
14.3
89.8
HubGT+FlexAttn
0.14
0.013
1.8
86.9
21.5
2.15
1.5
89.1
D.4 Evaluation on Random Graphs
Conventionally, hub labeling is developed for realistic graphs such road networks and social networks, which assume properties such as sparsity and certain locality/hierarchy. The application to random graphs is usually different and signified by considerable dispersed connections across different local structures. In Table /
we present a preliminary study to evaluate the effectiveness of our HubGT labeling diffferent synthetic graphs with 1000 nodes, including BARABASI-ALBERS and ERDOS-REXT REDON implemented by PyG [64, CSBM 665. and GENCAT [66].
For BA, ER, and CSBM graphs, both H-1 and H-O label sizes are relatively small, and there are extreme cases where no H-1 and H-O labels are required when the edge probability p is high and the graph is dense. These cases imply that the H-2 computation is especially effective, and fixed number of global hubs are sufficient for SPD computation. fact, for most node pairs, there SPD(u, v) cover. GENCAT graph generator closer to realistic graphs with power-law degree distribution, where larger indicates "steeper" distribution with more hubs and less long-tailed nodes. In this case, the label sizes are similar to realistic graphs, where more hubs result smaller H-l and larger H-0.
or when the raw graph is sufficiently connected, implying that it is already 2-hop
Table 9: Effectiveness and efficiency results on random graphs with varying synthesis parameters. Presented results include average index size (i.e., the number of labels) for each node and precompu- tation time (in seconds).
Dataset
Param.
H-1
H-0
Pre.
Param.
H-1
H-0
Pre.
CSBM
p = 0.01, g = 0.0
30.1
62,3
0.02
= 0.1, q = 0.1
0.0
0.0
0.02
ERDOS RENYI
= 0.01
1.6
2.1
0.02
0.1
0.0
0.0
0.02
BARABASI-AL BERET
d 10
1.7
1.7
0.02
d 100
0.5
0.6
0.06
GENCAT
3.0
30.6
72.7
0.04
2.0
32.8
67.3
0.03
30

---

In summary, as noted in Properties and B the hierarchy can naturally emerge during the hub labeling process. For random graphs with dispersed/non-locai connections, the pattern can be effectively utilized by H-2 to compute SPD.
E
Discussions
E.1 Algorithmic Generality, Limitation, and Future Direction
Dynamic Graph and Update. Hub labeling for dynamic graphs has been studied in previous works such [67] In brief, prevents full index updates and only updates the affected labels on candidate paths. Nonetheless, we consider a promising direction to integrate dynamic hub labeling with GT learning to better handle graph changes.
Multi-device Computation. As HubGT employs the fully decoupled architecture, it renders the future possibility to deploy multi-device training: once the precomputation is completed, data parallelism be employed with multiple Transformers, each handling batch of tokens, since node tokens are mutually independent and SPD querying is highly local storage. One potential limitation may be related to the large H-O index, rendering index duplication less efficient. In this case, HubGT superior to previous models, especially kernel-based ones, since only node-wise inputs are required and be easily batched. With respect multi-device settings for indexing computation across distributed graph partitions, the index L can be divided among devices in a node-wise manner, while the index Z and attributes X need to be mirrored or synchronized throughout the computation.
E.2 Broader Impact
As our work primarily focuses on theoretical contributions to improve the scalability of graph neural networks, we do not foresee having direct negative social impact.
31


Reviews:
[{"review_id": "Sl3axP7qXI", "reviewer": "Reviewer_1EVJ", "summary": "The paper is an approach to deal with scalability of Graph Transformers (GT). This paper uses graph structure to solve two separate issues for scaling GT. \n1. Since a large graph cannot be held in memory and the attention mechanism is quadratic, naive attention does not work. Mini batching is a way to deal with large graphs. Batching might only capture parts of graph, which can be problematic for hetrophilic graphs. \n2. Positional encoding is an important problem to solve for graphs. On regular sequences the relative position of the tokens leads to natural positional encodings which do not work for permutation-invariant structure of graphs.\n\nThe area of GraphTransformers are using many techniques from the graph theory literature to deal with efficient representation learning and improved accuracy on large graphs.  This paper uses Pruned Landmark Labelling (PLL) approach by Akiba et al. [33,34] to represent the graph topology. PLL was introduced in 2013-14 in the context of large (web, social etc.) graphs to solve the shortest paths between a pair of nodes. It uses the idea of using landmark nodes to quickly compute distance between a pairs of nodes.  These are used for both batching to include representation from other nodes (especially in heterophilous graphs) and for positional encoding.\n\nEven though HubGT does not outperform many of the methods (Table 2), it is close to the performance metrics of the other good methods.  The idea proposed is good for the field and I would like the authors can address the weaknesses described below.", "questions": "Described in the weaknesses section above.", "limitations": "Not applicable", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper is well written. The time complexity analysis is very useful.\n\nWeaknesses/potential future directions:\n(I) The paper compares against NAGphormer, SGFormer and DIFFormer, which are good benchmarks for mini batching.  There are at least a couple of approaches that are not cited/compared against in the paper. \n(1) The first is Exphormer (Shirzad et al. 2023) which uses (1) virtual nodes and (2) uses an overlay graph (like in HubGT, but using a different intuition).  It would be interesting to see the mixing properties due to the two overlay graph approaches. How many additional edges are needed in HubGT are comparable to the degree of the expander graph in Exphormer? How many virtual nodes smooth the network vs. in HubGT? Exphormer might not scale well with minibatching, but SpExphormer might be better in that aspect. So comparison to HubGT will be valuable.\n\n(2) The second paper that might be relevant is Graphormer (Ying et al., 2021), where structural features (centrality and spatial encoding) for GT was proposed.  Graphormer was before the introduction of Long Range benchmarks. I am not sure if there have been studies in applying it to the LongRange benchmark. So a study here will be valuable to understand which structural approaches are more valuable.\n\nFor the final version, a discussion and some simple comparison would be valuable. And further work will be useful to understand the space well.\n\n(II) Description of the HLL algorithm.\nI found it hard to follow the labelling ideas for HubGT. I went back and forth between section 4 and appendix, but had to read the original paper to understand the approach better. The complexity of BFS approach for SPD as described in the paper is clear. I would like an easier-to-follow description of the algorithm --- how pruning works, what labels represent (Appendix A refers to algorithm 1, which uses a 3-tuple. It is too hard to follow). An easier English description would be valuable.\n\n(III) Scaling properties. The authors spend a lot of time on the complexity analysis of the paper. Scaling to REDDIT, ogbn-mag and Pokec is impressive.   However, I would also like to see the scalability in terms of memory, compute times and graph sizes. I would like a study (instead of brief paragraphs) on the memory and scalability issues. From the description it is not clear what the limitations are on a single GPU or in a multiGPU setting. A thorough description of the experimentations would be very helpful.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the constructive feedback and acknowledgment of our main contributions from the reviewer. We reply to all the points below.\n\n## W1\n> The paper compares against NAGphormer, SGFormer and DIFFormer, which are good benchmarks for mini batching. There are at least a couple of approaches that are not cited/compared against in the paper. (1) The first is Exphormer (Shirzad et al. 2023) which uses (1) virtual nodes and (2) uses an overlay graph (like in HubGT, but using a different intuition). It would be interesting to see the mixing properties due to the two overlay graph approaches. How many additional edges are needed in HubGT are comparable to the degree of the expander graph in Exphormer? How many virtual nodes smooth the network vs. in HubGT? Exphormer might not scale well with minibatching, but SpExphormer might be better in that aspect. So comparison to HubGT will be valuable.  \n> (2) The second paper that might be relevant is Graphormer (Ying et al., 2021), where structural features (centrality and spatial encoding) for GT was proposed. Graphormer was before the introduction of Long Range benchmarks. I am not sure if there have been studies in applying it to the LongRange benchmark. So a study here will be valuable to understand which structural approaches are more valuable. For the final version, a discussion and some simple comparison would be valuable. And further work will be useful to understand the space well.\n\n### (1) Exphormer\n#### **Difference with HubGT**\nThe large-scale variant of `Exphormer` is based on `GraphGPS` [7] according to its paper, exploiting the kernel-based approach to reduce overhead and sharing the similar complexity as in our Table 1. Additionally, the original evaluation mostly focuses on graphs under homophily, and the performance under heterophily is not presented.\n\nThe **expander degree** is set to $6$ for node classification in Exphormer, i.e., adding $6$ edges for each node. For comparison, the empirical average label size in HubGT is $2.0$ and $15.0$ on `cora` and `penn94`. Exphormer utilizes $1$ **global node**, while HubGT uses $8$ hubs. We would like to remark that the selection of both hyperparameters in HubGT is additionally affected by the consideration of indexing efficiency and may be further reduced in GT learning by down-sampling. \n\n#### **Experiments**\nThe efficiency (precomputation time, training epoch time, and peak GPU memory) and accuracy evaluations of Exphormer are presented in the table below, complementary to **Table 2&5** in our paper. Note that to prevent OOM in our settings (24GB VRAM cap vs 40GB in the original paper), we reduce the model size to $layer=2, width=32, n_{head}=2$, so the results may be different. It can be observed that:\n* The **efficiency** of Exphormer is mostly comparable to kernel-based methods evaluated in our paper, including fast training and less scalable GPU footprint.\n* The model **accuracy**, especially under heterophily, is limited due to the dependency on graph topology and the relatively small model size. \n* Empirically, applying expander graph and virtual nodes (`VN`) leads to significant **overhead** in precomputation and training, respectively. We will present more discussions regarding the trade-off between efficiency and accuracy of different Exphormer variants in the revised paper.\n\n| Dataset | cora | | | | ogbn-arxiv | | | | twitch-gamer | | | |\n|---|---|---|---|---|---|---|---|---|---|---|---|---|\n| Model   | Pre | Epoch | VRAM | Acc | Pre | Epoch | VRAM | Acc | Pre | Epoch | VRAM | Acc |\n| `Exphormer`-w/o VN | 0.1 | 0.05 | 1.2 | 85.3 | 23.3 | 0.8 | 14.8 | 67.9 | 50.8 | 0.9 | 16.3 | 62.3 | \n| `Exphormer`-w/ VN | 0.1 | 0.07 | 1.5 | 85.8 | 32.0 | 1.2 | 18.8 | 67.9 | 41.5 | 1.3 | 19.4 | 64.2 |\n\n---\n### (2) Graphormer\n#### **Difference with HubGT**\n`Graphormer` [2] is a pioneering work introducing structural encoding and the global virtual node. As analyzed in **Table 1**, it is a full-graph GT, which is usually applied to many small graphs such as molecules.  \n\nIn Table 5 of the Graphormer paper, it is demonstrated that SPD is better than Laplacian as **positional encoding**, which aligns with the intuition from our motivating study 2 in Section 3.\n\n#### **Experiments**\nEven with neighborhood sampling and mini-batching, Graphormer incurs OOM on small datasets such as `cora` in our environment. The same issue is also observed in other studies such as [9]. Therefore, we are unable to provide further experimental results.  \n\nWe will include more comprehensive comparisons for both models in the revised version based on the current discussions and experiments.\n\n## W2\n> Description of the HLL algorithm. I found it hard to follow the labelling ideas for HubGT. I went back and forth between section 4 and appendix, but had to read the original paper to understand the approach better. The complexity of BFS approach for SPD as described in the paper is clear. I would like an easier-to-follow description of the algorithm --- how pruning works, what labels represent (Appendix A refers to algorithm 1, which uses a 3-tuple. It is too hard to follow). An easier English description would be valuable.\n\nWe will enhance the representation of the hub labeling algorithm in Section 4 and Appendix A to improve clarity. As an overview, we elaborate on the PLL algorithm and the differences with our Algs 1-3 below.\n\n### PLL overview\nThe classical PLL algorithm proposed in [33] aims to address the conventional *full-graph SPD* query: given two arbitrary nodes $u,v\\in\\mathcal{V}$, the SPD between them can be answered by visiting the labels following our Eq. (4). This is achieved by the two-stage process of indexing as precomputation and the $O(s)$ querying.\n\nIn the **indexing** phase, it constructs labels for each node by pruned BFS. Each label $\\mathcal{L}(u)$ is a set of tuples $(v, b(u,v))$ denoting the end node $v$ and SPD $b(u,v)$. BFS starting from $u$ and visiting $v$ aims to compute $b(u,v)$ based on the existing labels and add it to $\\mathcal{L}(v)$ during the search. It is pruned when the computed SPD $b(u,v)$ is smaller than the BFS distance from $u$, which implies that the SP between $u,v$ has been accessed through a better intermediate node $r$ searched before $u$.\n\nAs it intends to answer arbitrary queries, the **querying** phase needs to iterate over all labels of $u$ and $v$ and find the SPD through the best intermediate node $r$. \n\n### Hierarchical Labeling in HubGT \nIn our paper, we design Algs 1-3 to address a different *subgraph SPD* problem formulated in line 158: given a root $r$, we aim to efficiently compute SPD $b(u,v)$ for node pairs in the induced subgraph $u,v\\in\\mathcal{S}(r)$. \n\nTo achieve this, we include additional elements in the label **index**, i.e., $\\mathcal{M}_r^{0}(v), \\mathcal{M}_r^{1}(v)$ in Alg 1, which are used to compute SPD by Eq. (3). Intuitively, $\\mathcal{M}_r(v)$ denotes the *relative position of neighbors* in $\\mathcal{S}(r)$ with respect to $v$, and can indicate potential \"shortcuts\" in SPD computation without increasing the label size. $q(v)$ in Alg 1 is the auxiliary variable representing the search *distance* between $v$ and $r$ for $\\mathcal{M}_r(v)$ construction, i.e., nodes $u$ with $q(u) = q(v)$ are added to $\\mathcal{M}_r^0(v)$, while nodes with $q(u) < q(v)$ are added to $\\mathcal{M}_r^1(v)$.\n\nIn this case, the **prune conditions** are lines 11 & 15 in Alg 1, where the former corresponds to the classical PLL, and the latter further prunes when a shortcut through $\\mathcal{M}_r(v)$ or $\\mathcal{M}_r(u)$ exists. The difference of Alg 1 with the bit-parallel PLL [33] is that, the strategy only applies to global hubs in [33] for full-graph SPD, while in our setting, each root node $r$ can be regarded as a \"local\" hub within the subgraph. Hence, it can be integrated into labels to boost querying. \n\n## W3\n> Scaling properties. The authors spend a lot of time on the complexity analysis of the paper. Scaling to REDDIT, ogbn-mag and Pokec is impressive. However, I would also like to see the scalability in terms of memory, compute times and graph sizes. I would like a study (instead of brief paragraphs) on the memory and scalability issues. From the description it is not clear what the limitations are on a single GPU or in a multiGPU setting. A thorough description of the experimentations would be very helpful.\n\n* **GPU Memory:** Evaluation of GPU memory on some datasets is available in **Table 5**, while the others will be included in the revised version. In general, it aligns with our complexity analysis in **Table 1**, showing that `HubGT` is highly scalable, as the GPU memory can be *arbitrarily adjusted by batch size* to prevent OOM. Our additional experiments with `FlexAttention` in **Review 1kw8.W1** further show that the main GPU memory bottleneck is the standard Transformer architecture, and can be addressed by incorporating more efficient designs. In comparison, GTs such as `ANS-GT` and `Exphormer` in **W1** incorporate graph-scale data, which leads to OOM on large datasets.\n* **Computation Time and RAM Memory:** The time scalability of `HubGT` is mainly dominated by precomputation time, especially H-1 and H-0 indexing corresponding to the $O(ns^3)$ term in complexity. The RAM memory is dominated by the $O(ns^2)$ H-0 index, which is still considerable for large datasets. As suggested by **Review Hvuy.I3**, we will add a new figure to study model performance under varying graph scales in the revised version.\n* **Multi-GPU Setting:** As `HubGT` employs the fully decoupled architecture, it benefits multi-GPU and even distributed training. Once the precomputation is completed, *data parallelism* can be employed with multiple Transformers, each handling a batch of tokens, since node tokens are mutually independent and SPD querying is highly local in storage. One potential limitation may be related to the large H-0 index, rendering index duplication less efficient."}, {"review_id": "gV01At6XFy", "reviewer": "Reviewer_c6sP", "summary": "The authors describe HubGT, a Graph Transformer (GT) framework designed to tackle scalability issues that hinder the application of traditional GTs to large graphs. HubGT achieves this by decoupling graph structure processing from model training through an offline precomputation step. This step constructs a 3-level hierarchical index based on hubs, which are specially selected nodes with high connectivity that serve as central reference points within subgraphs. The index, inspired by techniques like Pruned Landmark Labeling (PLL), assigns labels to nodes based on their relationships to hubs, enabling efficient encoding of shortest path distances. During training, this hierarchical index allows shortest path distance (SPD) computation in $O(1)$ time and enriches node tokens with global \"hub context\", enhancing the model’s ability to capture broader graph structures. As a result, HubGT simplifies GT training to resemble that of a standard Transformer, supporting CPU/GPU pipelining, reducing memory overhead, and delivering state-of-the-art performance on graph benchmarks.", "questions": "- For practitioners/application developers, how are $s_(sample size)$ and $s_out$ (in/out-neighbor ratio) determined heuristically? Are optimal values related to properties of the entire graph (e.g. diameter, average degree, sparsity, etc.)?\n\n- Your hub selection is based on node degree. How robust is this strategy on graph topologies that lack clear high-degree hubs, such as random graphs or stochastic block models?\n\n- Have you experimented with other centrality measures for hub selection, and how does HubGT's performance change when high-degree nodes are not the most effective structural landmarks?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Some strengths of the paper are obviously related to the benefits of PLL. For example, HubGT’s hub labeling scheme has constant time for SPDs during training. Moreover a nice property is that the hierarchical indexing enriches node tokens with global “hub context,” capturing long-range dependencies and structural patterns. Finally, the idea of decoupling graph structure processing from model training should enable CPU/GPU pipelining which is an advantageous property.\n\nI do note some possible weaknesses also related to hub based labeling. For example, the dependence on quality of hub selection could potentially limit generalizability in graphs with uneven degrees or more complex network topologies (e.g. Erdos-Reyni, Barabasi-Albert, Stochastic Block Model). What about secondary effects like thrashing? For example, it is possible that the $H_0$ cache’s fixed size limit ($s^2$) could thrash in the face of many alternative paths especially with denser graphs.\n\nIn terms of clarity, mostly ok, but some problematic notation, viz. the terms theorem and property are used interchangeably, so property should be used throughout the text as the observations do not require proofs.", "was_revised": true, "final_justification": "The main contribution of the paper is distance PE encoding achieved through hub labeling. The tradeoff is the high complexity of deriving hub labels both for the full graph through PLL or distributed PLL and then computing favorable $H_1$, $H_0$ etc. labels when sampling a subgraph through a root node $r$ (advantageous if SPs through $r$ exist otherwise just original hub distances.) versus the lower complexity of SP distance calculation once hubs are calculated. I still have a couple of concerns: 1) This method should not work well for dynamic graphs and also under inductive settings because the hub labels and distances will change under dynamism and the preprocessing is likely a wasted overhead. 2) concern about the significance of achieving this through hub labeling as opposed to other measures such as centrality etc. I wish the authors had some theoretical results to back this up, everything is empirical. 3) Hub labeling under distributed as well as dynamic graph scenarios is very challenging and require a very different set of algorithms.\nThus I am retaining my original score. The authors should definitely include the explanatory comments about challenges in distributed graphs and the new references in their final version.", "rebuttal": "We thank the reviewer for the thorough review. We address all the comments and questions below.\n\n## W1 \n> I do note some possible weaknesses also related to hub based labeling. For example, the dependence on quality of hub selection could potentially limit generalizability in graphs with uneven degrees or more complex network topologies (e.g. Erdos-Reyni, Barabasi-Albert, Stochastic Block Model). What about secondary effects like thrashing? For example, it is possible that the $H_0$ cache’s fixed size limit ($s^2$) could thrash in the face of many alternative paths especially with denser graphs.\n\nWe would like to discuss the possibility of secondary effects like thrashing here, and specifically evaluate the application to random graph topologies in **Q2**.\n\nAs introduced in **Appendix A**, the goal of hub labeling is to add \"highway\" connections as labels to the graph in order to form a 2-hop cover, where arbitrary node pairs can be reached within 2 hops. On graphs with dense or non-local edge connections, some *existing edges can already be regarded as \"highway\" edges*, linking nodes in different local structures. Hence, the number of additional labels is usually small on dense graphs.\n\nIn implementation, this is achieved by the *H-2 computation*, which utilizes a set of global hubs connecting to all nodes in the entire graph. When H-2 effectively captures most SPD queries, the sizes of the H-1 and H-0 indices are significantly reduced. We further study in **Q2** that, on these graphs, it is highly likely that *SPD is small and multiple shortest paths exist*. In other words, only a small portion of hubs is sufficient to form a 2-hop cover for the majority of graph nodes, which prevents potential thrashing.\n\n## W2\n> In terms of clarity, mostly ok, but some problematic notation, viz. the terms theorem and property are used interchangeably, so property should be used throughout the text as the observations do not require proofs.\n\nWe notice that this was caused by a bug in our LaTeX hyperreference. We will carefully correct the notation to \"Property\" in future versions.\n\n## Q1\n> For practitioners/application developers, how are $s_{sample size}$ and $s_{out}$ (in/out-neighbor ratio) determined heuristically? Are optimal values related to properties of the entire graph (e.g. diameter, average degree, sparsity, etc.)?\n\n* **Sample size** $s_{sample}$: The subgraph size $s$ in GT learning is similar to the sample size in `GraphSAGE`, indicating the receptive field of node representation. While ideally *at the scale of average degree*, it may also be affected by factors such as heterophily, where more nodes are favored to capture non-local information. Hence, we set it to be sufficiently large as $s_{sample}=48$, and leave the model to learn the important relationships.\n* **In/Out neighbor ratio** $s_{in}/s_{out}$: As analyzed by the three properties and evaluated in **Figure 7**, $s_{in}$ and $s_{out}$ are closely related to hub and fringe nodes, respectively. In practice, a larger ratio of $s_{in}$ to $s_{out}$ is hence preferred when *non-local information* is important, such as under heterophily. Since it is mainly affected by specific dataset properties, we consider it as a hyperparameter to be tuned.\n\n[GraphSAGE] Inductive Representation Learning in Large Attributed Graphs. NeurIPS'17.\n\n## Q2\n> Your hub selection is based on node degree. How robust is this strategy on graph topologies that lack clear high-degree hubs, such as random graphs or stochastic block models?\n\nYes. Hub labeling can be effectively applied to graphs with different topologies. Conventionally, hub labeling is developed for realistic graphs such as road networks and social networks, which assume properties such as *sparsity and certain locality/hierarchy*. The application to random graphs is usually different and signified by considerable dispersed connections across different local structures. To demonstrate the effectiveness, we present a preliminary study on synthetic graphs with $n=1000$ nodes and varying parameters, while a similar evaluation on realistic datasets can be found in **Review 1kw8.W4**.\n* For `BA`, `ER`, and `CSBM` graphs, both H-1 and H-0 label sizes are relatively small, and there are extreme cases where no H-1 and H-0 labels are required when the edge probability $p$ is high and the graph is dense. These cases explain **W1**, that the *H-2 computation is especially effective*, and a fixed number of global hubs are sufficient for SPD computation. In fact, for most node pairs, there is $SPD(u,v) = 1 \\text{ or } 2$ when the raw graph is sufficiently connected, implying that it is already a 2-hop cover.\n* `GenCAT` is a graph generator closer to realistic graphs with power-law degree distribution, where larger $\\alpha$ indicates a \"steeper\" distribution with more hubs and less long-tailed nodes. In this case, the label sizes are similar to realistic graphs, where more hubs result in smaller H-1 and larger H-0.\n\nIn summary, as noted in **Property 2&3**, the hierarchy *can naturally emerge* during the hub labeling process. For random graphs with dispersed/non-local connections, the pattern can be effectively utilized by H-2 to compute SPD. We will include more comprehensive discussions and experiments regarding generalizability on different graphs in the revised version.\n\n| Dataset | Parameters | H-1 Size | H-0 Size | Pre. Time |\n|---|---|---|---|---|\n| `CSBM` | $p=0.01, q=0.0$ | 30.1 | 62.3 | 0.02 |\n| `CSBM` | $p=0.1, q=0.1$ | 0.0 | 0.0 | 0.02 | \n| `Erdos-Renyi` | $p=0.01$ | 1.6 | 2.1 | 0.02 |\n| `Erdos-Renyi` | $p=0.1$ | 0.0 | 0.0 | 0.02 |\n| `Barabasi-Albert` | $d=10$ | 1.7 | 1.7 | 0.02 |\n| `Barabasi-Albert` | $d=100$ | 0.5 | 0.6 | 0.06 |\n| `GenCAT` | $\\alpha=3.0$ | 30.6 | 72.7 | 0.04 |\n| `GenCAT` | $\\alpha=2.0$ | 32.8 | 67.3 | 0.03 |\n\n[GenCAT] GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems'23.\n\n## Q3\n> Have you experimented with other centrality measures for hub selection, and how does HubGT's performance change when high-degree nodes are not the most effective structural landmarks?\n\nIn the following table, we present experimental results of hub selection based on other metrics such as closeness centrality and PageRank. \n* Closeness centrality results in larger **average label sizes** for both H-1 and H-0 indices, which is in line with the observation in [33].\n* Degree and closeness centrality lead to similar **GT accuracy**, while PageRank is less representative for selecting useful hubs.\n* As noted in **Appendix A.1**, the main consideration in hub selection is *indexing efficiency*. While other measures may be useful, there is **additional overhead** for computing these scores, which makes them less applicable to large graphs. \n* Hence, we still recommend degree centrality, which can be efficiently acquired. Alternatively, the number of hub/fringe nodes in the subgraph can be controlled by the ratio $s_{in}/s_{out}$ as in **Q1**.\n\n| Dataset | Measure | H-1 Size | H-0 Size | Pre. Time | Acc |\n|---|---|---|---|---|---|\n| `cora` | Degree | 2.4 | 2.5 | 0.02 | 86.0 |\n| `cora` | Closeness | 9.9 | 12.9 | 0.03+2.59 | 86.0 | \n| `cora` | PageRank | 2.3 | 2.4 | 0.04+0.04 | 85.8 |\n| `chameleon` | Degree | 1.3 | 1.3 | 0.02 | 38.9 |\n| `chameleon` | Closeness | 4.7 | 6.5 | 0.02+0.74 | 39.9 |\n| `chameleon` | PageRank | 1.1 | 1.1 | 0.02+0.06 | 36.0 |"}, {"review_id": "RkSxhk4Bbo", "reviewer": "Reviewer_UKq4", "summary": "This paper proposes HubGT, a novel and efficient Graph Transformer architecture that leverages hierarchical hub labeling to enable scalable training and inference on large graphs. The key idea is to decouple the graph computation from the transformer training by introducing a three-level indexing structure for precomputing neighborhood and shortest-path information. The authors demonstrate both theoretical and empirical improvements over existing Graph Transformer baselines, especially on large-scale graphs under both homophily and heterophily settings.", "questions": "NA", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The idea of decoupling graph computation from transformer training is novel and leads to significant efficiency gains.\n\n2. The three-level hierarchical hub labeling scheme (local, global, and 2-hop caching) is theoretically well-grounded and empirically effective.\n\n3. The paper conducts comprehensive experiments on 14 datasets, including million-scale graphs, showing consistent improvements in speed and accuracy compared to state-of-the-art graph transformers.\n\n**Weakness**\n\nThe evaluation only includes comparisons against Graph Transformer baselines. Stronger message-passing GNNs are missing, which limits understanding of the accuracy-efficiency tradeoff relative to GNNs.", "was_revised": true, "final_justification": "I think my score is reasonable.", "rebuttal": "We thank the reviewer for the thoughtful comments. Below, we present more details on experimental comparisons.\n\n## W1\n> The evaluation only includes comparisons against Graph Transformer baselines. Stronger message-passing GNNs are missing, which limits understanding of the accuracy-efficiency tradeoff relative to GNNs.\n\nIn the paper, we include `SGFormer` as a strong baseline representing message-passing GNNs. Here we conduct experiments on 4 additional GNNs, including two heterophilous MPNNs `GCNJK` and `MixHop` with neighborhood sampling (RS), and two efficient spectral GNNs `TFGNN` and `S2GNN`. Results on precomputation time, training epoch time, peak GPU memory, and accuracy are shown below. In general, we note the following differences for MPNNs:\n* GNNs using full graph topology for propagation usually entail $O(mF)$ **memory overhead**, which is less scalable. This can be observed from the OOM issue on datasets such as `reddit`. Similar to GT, this can be addressed by mini-batching with RS, but risks hindering **efficacy**, such as `GCNJK` and `MixHop` on `ogbn-arxiv`.\n* Empirically, MPNNs entail more **training epochs**, with up to 1000 epochs in practice. In comparison, most GTs converge within 100–200 epochs. Consequently, while the epoch time seems shorter for MPNNs, the total training time is on par with GTs.\n\nWe will include more results extending Table 2&5 in the revised version. As suggested by **Review Hvuy.I3**, we will add new visualizations to study the accuracy-efficiency tradeoff under varying graph scales in the revised version. \n\n| Dataset | reddit | | | | ogbn-arxiv | | | | penn94 | | | | twitch-gamer | | | |\n|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|\n| Model   | Pre | Epoch | VRAM | Acc | Pre | Epoch | VRAM | Acc | Pre | Epoch | VRAM | Acc | Pre | Epoch | VRAM | Acc |\n| `GCNJK` | / | 0.83 | 12.0 | 89.0 | / | 0.29 | 2.8 | 60.0 | / | 0.35 | 4.6 | 65.9 | / | 0.15 | 7.3 | 61.5 |\n| `MixHop` | / | 0.79 | 2.3 | 91.6 | / | 0.21 | 6.0 | 60.3 | / | 0.31 | 1.5 | 75.0 | / | 0.11 | 1.5 | 52.1 |\n| `TFGNN` | | | OOM | | / | 0.11 | 1.2 | 75.2^ | / | 0.19 | 1.9 | 75.8 | / | 0.15 | 0.7 | 59.5 | \n| `S2GNN` | | | OOM | | 195.4 | 0.34 | 6.3 | 69.9 | 148.1 | 0.42 | 6.9 | 75.1 | 668.6 | 1.2 | 15.9 | 65.9 |\n\n^ Results from the original paper since configurations are not provided. \n\n[GCNJK] Representation learning on graphs with jumping knowledge networks. ICML'18.  \n[MixHop] MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. ICML'19.  \n[TFGNN] Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach. WWW'24.  \n[S2GNN] Spatio-Spectral Graph Neural Networks. NeurIPS'24."}, {"review_id": "bBL1L4e5VV", "reviewer": "Reviewer_1kw8", "summary": "The paper introduces HubGT, a novel Graph Transformer (GT) framework that addresses the scalability bottlenecks of existing GTs. The paper introduces a decoupled hub-based hierarchical labeling scheme that supports efficient subgraph sampling and distance-based positional encoding (SPD). The method avoids graph operations during training and enables O(1) SPD querying, making it suitable for large-scale graphs with millions of nodes and edges. Empirical results on 14 benchmark datasets demonstrate state-of-the-art efficiency and strong predictive performance, especially in heterophilous and sparse graphs.", "questions": "1. Can the authors provide an in-depth analysis of hub selection, such as the statistical properties of selected hubs, cross-dataset patterns, or their structural significance?\n2. Can the authors provide evidence or discuss how the hub label index could be updated incrementally in dynamic or temporal graph settings?\n3. Could the authors expand the experimental comparison to include scalable non-GT baselines?\n4. Is it feasible to combine HubGT with efficient Transformer variants such as FlashAttention or Linformer, and what are the anticipated gains or trade-offs?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "> Strengths of the Paper:\n\n1. The paper introduces a 3-level hub-labeling scheme (H-0, H-1, H-2) to capture both local and global graph structures. It leverages Pruned Landmark Labeling for efficient index construction and SPD approximation and cleanly decouples precomputation from training to support mini-batch learning without graph traversal.\n2. The framework achieves linear-time precomputation and training complexity independent of edge count. It consistently demonstrates the fastest inference speed across all large-scale benchmark datasets.\n3. The paper enables the use of Shortest Path Distance (SPD) as a dense positional encoding, a strategy previously too expensive for large graphs, effectively enhancing representation power, especially under heterophily.\n4. The model is evaluated on 14 benchmark datasets covering a wide range of scales and homophily levels. Ablation studies confirm the importance of SPD bias, global hub connections, and attention-based node readout for performance gains.\n\n> Weaknesses of the Paper:\n\n1. The core Transformer module is largely standard. The proposed approach could benefit from integrating efficient attention mechanisms to improve scalability.\n2. The hub-label index is constructed in a one-time pre-computation phase and remains fixed. This design may be inadequate for dynamic or temporal graphs, where incremental updates to the label hierarchy are necessary.\n3. While the focus is on Graph Transformers, the paper lacks a direct comparison with recent scalable convolutional GNNs, which also address large-scale and heterophilous settings. The only non-GT baseline included is SGFormer, which limits the scope of empirical benchmarking.\n4. The paper does not provide an in-depth analysis of hub selection, such as the statistical properties of selected hubs, cross-dataset patterns, or their structural significance, which limits the interpretability of the hub hierarchy used in H-1 and H-2 indices.\n5. Model performance depends on choices like subgraph size and the balance between \"s_in\" and \"s_out\". While the impact is partially evaluated (Figure 7), the method lacks adaptive mechanisms to optimize these parameters across diverse datasets.", "was_revised": true, "final_justification": "The author has address part of my concerns on the weakness. I would like to keep my current score.", "rebuttal": "We sincerely appreciate the reviewer for the insightful comments and detailed suggestions. We address all comments and related questions below.\n\n## W1&Q4\n> The core Transformer module is largely standard. The proposed approach could benefit from integrating efficient attention mechanisms to improve scalability.  \n> Is it feasible to combine HubGT with efficient Transformer variants such as FlashAttention or Linformer, and what are the anticipated gains or trade-offs?\n\nYes. While we utilize the standard Transformer in the paper, as it is orthogonal to our main contributions on tokenization and positional encoding, `HubGT` *is compatible* with other Transformer architectures. As in **Section 5.2**, this flexibility is a remarkable advantage of the decoupled design, enabling seamless integration with efficient Transformers.\n\nTo demonstrate, we implement `FlexAttention` [R1] to replace the standard Transformer, as prior methods such as `FlashAttention` and `Linformer` do not support trainable attention bias. The results are presented below. Overall, FlexAttention achieves a 10–20× speedup and *significant reductions in GPU memory footprint*, while the accuracy remains comparable, verifying the benefits of improving the Transformer architecture. \n\nWhile the improvement is promising, the speedup is less substantial compared to [R1] results, mainly because the speed is also *affected by I/O and computation of PE* in HubGT. As our current implementation is highly straightforward, better pipelining may further improve efficiency performance. We will further enhance the implementation and include more evaluations to showcase the benefits of efficient Transformers in the revised version.\n\n| Dataset | cora | | | | genius | | | | \n|---|---|---|---|---|---|---|---|---|\n| Model   | Epoch | Infer | VRAM | Acc | Epoch | Infer | VRAM | Acc |\n| `HubGT` | 0.20 | 0.018 | 2.5 | 86.0 | 23.7 | 2.58 | 14.3 | 89.8 |\n| `HubGT` w/ `FlexAttention` | 0.14 | 0.013 | 1.8 | 86.9 | 21.5 | 2.15 | 1.5 | 89.1 |\n\n[R1] FlexAttention: A Programming Model for Generating Fused Attention Variants. MLSys'25. \n\n## W2Z&Q2\n> The hub-label index is constructed in a one-time pre-computation phase and remains fixed. This design may be inadequate for dynamic or temporal graphs, where incremental updates to the label hierarchy are necessary.  \n> Can the authors provide evidence or discuss how the hub label index could be updated incrementally in dynamic or temporal graph settings?\n\nYes. Hub labeling for dynamic graphs has been studied in previous works such as [R2]. In brief, it prevents full index updates and only *updates the affected labels* on candidate paths. \n\nDue to implementation constraints, we are unable to provide experimental evidence for utilizing the algorithm for dynamic GT. Nonetheless, we consider it a promising direction and will include further discussions in the revised version.\n\n[R2] Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling. WWW'14.\n\n## W3&Q3\n> While the focus is on Graph Transformers, the paper lacks a direct comparison with recent scalable convolutional GNNs, which also address large-scale and heterophilous settings. The only non-GT baseline included is SGFormer, which limits the scope of empirical benchmarking.  \n> Could the authors expand the experimental comparison to include scalable non-GT baselines?\n\nWe have conducted additional experiments on 4 GNNs, including two heterophilous MPNNs `GCNJK` and `MixHop` applicable to neighborhood sampling, and two efficient spectral GNNs `TFGNN` and `S2GNN`. The results are presented in **Review UKq4.W1**. In summary, while convolutional GNNs achieve faster epoch speed, they particularly suffer from issues including *slower convergence, less scalable memory overhead, and performance drop under mini-batching*. \n\n## W4&Q1\n> The paper does not provide an in-depth analysis of hub selection, such as the statistical properties of selected hubs, cross-dataset patterns, or their structural significance, which limits the interpretability of the hub hierarchy used in H-1 and H-2 indices.  \n> Can the authors provide an in-depth analysis of hub selection, such as the statistical properties of selected hubs, cross-dataset patterns, or their structural significance?\n\nAn empirical study regarding the hub labeling properties is presented in **Appendix D.3**, including the label size and visual clustering effect. Here, we would like to present more details with varying $s$ when constructing labels. A similar study on synthetic graphs is presented in **Review c6sP.Q2**. We note the following observations:\n* We compute the average **clustering coefficient** $C$ before and after hub labeling to evaluate the change in graph topology. Similar to the results in **Figure 1**, hub labeling can *flatten the node distribution* by increasing the clustering property on less clustered graphs such as `cora`. Conversely, for highly clustered graphs and larger label sizes, $C$ is slightly reduced, as additional label connections make the graph denser with a more dispersed edge distribution. \n* For small graphs such as `cora`, the **average H-1 label sizes** $|\\mathcal{L}|+|\\mathcal{L}'|$ do not vary with different upper bounds of $s$, which implies that the hubs are sufficiently connected to graph nodes. On the larger `physics`, increasing the small $s=24$ can increase the actual label size, effectively incorporating more remote nodes to form the subgraph. However, the increase is less significant for $s>48$, which indicates that the hubs are already sufficiently connected. \n* As the **H-0 label size** $|\\mathcal{I}|$ is based on H-1 construction, it also exhibits less increase with larger $s$, as the larger H-1 is able to cover more SPD pairs and suppress the need for H-0. For most configurations, the H-0 size is significantly smaller than the theoretical bound $O(s^2)$, ensuring empirical space efficiency. \n\nDue to the restriction on including figures during rebuttal, we will present more results regarding the relationship between hub properties and node distribution in the revised paper.\n\n| Dataset | Max Label Size $s$ | Avg Degree | $C_{before}$ | $C_{after}$ | H-1 Size | H-0 Size | Index Size | \n|---|---|---|---|---|---|---|---|\n| `cora` | 24 | 3.90 | 0.241 | 0.648 | 2.4 | 2.5 | 6.2 MB |\n| `cora` | 48 | 3.90 | 0.241 | 0.621 | 2.4 | 2.5 | 6.2 MB |\n| `cora` | 72 | 3.90 | 0.241 | 0.584 | 2.4 | 2.5 | 6.2 MB |\n| `physics` | 24 | 14.38 | 0.377 | 0.302 | 22.6 | 135.0 | 118 MB |\n| `physics` | 48 | 14.38 | 0.377 | 0.306 | 40.6 | 230.9 | 147 MB |\n| `physics` | 72 | 14.38 | 0.377 | 0.300 | 55.9 | 294.6 | 170 MB |\n\n## W5\n> Model performance depends on choices like subgraph size and the balance between $s_{in}$ and $s_{out}$. While the impact is partially evaluated (Figure 7), the method lacks adaptive mechanisms to optimize these parameters across diverse datasets.\n\nAs detailed in **Review c6sP.Q1**, we set the subgraph size $s$ to be *sufficiently large* to ensure indexing speed and receptive field. The $s_{in}/s_{out}$ ratio is mainly *affected by dataset properties* such as heterophily, so we consider it a hyperparameter to be tuned. \n\nIn addition, our complexity and experimental analysis of GTs with **adaptive schemes** such as `ANS-GT` imply that such mechanisms come with *additional overhead*. Hence, we consider efficient, adaptive tokenization/positional encoding a promising yet challenging task for GT research."}, {"review_id": "3OnOC9ESZW", "reviewer": "Reviewer_Hvuy", "summary": "This paper proposes a hierarchical method to improve the efficiency of graph transformers. In particular they provide an algorithm which is linear in the number of graph edges and nodes, in precomputing and training. The training stage completely removes graph-related computation. In the paper a thorough analysis is made of the complexities of related algorithms and also the", "questions": "See weaknesses", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strenghts:\n- Thorough design optimizing several aspects in the computation\n- Good analysis of the complexity of different methods.\n- Significant speed ups with respect to state-of-the-art methods \n\nWeaknesses:\n- It remains a bit unclear where the real benefits lie. Table 2 which is the main experimental result shows that for many of the datasets other methods are better in terms of accuracy. In terms of precomputation, time for epoch, and time for infer there is no clear winner. It is also hard to determine what the overall timing means. Is every epoch for the different methods comparable? Do all methods require the same number of epochs?\n- It remains unclear what the competing methods especially the ones with similar performance do. There is some more description in the appendix but also there not much is said about the actual differences with the proposed method. \n\nImprovements: \n- In the caption of table 1 it would be good to mention all variables that play a role in the complexity. L, n, F, M etc.\n- Indicate in bold / underline which method is based in computation time for the different elements.\n- Can't you create a scatterplot like visualization with the tradeoff between acc and computation? Probably separate for training and testing. Your main message is that you can reach a similar accuracy in much less time. A table doesn't easily convey this message.", "was_revised": true, "final_justification": "The authors have addressed my questions and overall I think this is an interesting paper worthy of presentation at Neurips. Hence I raised my score to accept.", "rebuttal": "We thank the reviewer for the thorough review and suggestions. We elaborate on the comments with further details below.\n\n## W1\n> It remains a bit unclear where the real benefits lie. Table 2 which is the main experimental result shows that for many of the datasets other methods are better in terms of accuracy. In terms of precomputation, time for epoch, and time for infer there is no clear winner. It is also hard to determine what the overall timing means. Is every epoch for the different methods comparable? Do all methods require the same number of epochs?\n\nIn this paper, we aim to present an efficient GT with novel tokenization and positional encoding (PE). We elaborate on our considerations of model performance and efficiency following the priorities below:\n1. Most importantly, the model should be **scalable** enough, that is, capable of completing training within a reasonable time without incurring OOM. Compared to the baselines, our `HubGT` achieves favorable GPU memory and time scalability, including simple mini-batching as well as fast precomputation and PE querying. We provide a more thorough discussion regarding the scalability of HubGT in **Review 1EVJ.W3**.\n2. Next, we expect the model to achieve **competitive accuracy** across different datasets, which relates to the effectiveness of batching strategy and PE. As discussed in **Section 6.2**, the permutation-invariant batching, hierarchy in tokens, and dense PE contribute to HubGT's performance on both homophilous and heterophilous datasets. \n3. Under comparable accuracy, we comprehensively consider the model **efficiency**, especially training and inference time. Distinguishing the two times is essential for applications with varied frequencies of training/inference. In particular, if model inference is significantly slower than training, such as `DIFFormer`, `PolyNormer`, and `SGFormer` in our evaluation, the efficiency benefit is less practical. \n4. Regarding training time, the **average epoch time** is preferred over total training time. This is because: (1) GTs with similar Transformer architectures usually share a similar convergence speed. In our experiments, most GTs converge within 100–200 epochs, so the epoch time is comparable. (2) The total training time is easily affected by other factors such as additional computation and stopping criteria, rendering it hard to present a fair comparison. The epoch time is also used in previous works such as [40]. We will include more detailed discussions and experimental results in the revised version.\n\n## W2\n> It remains unclear what the competing methods especially the ones with similar performance do. There is some more description in the appendix but also there not much is said about the actual differences with the proposed method.\n\nOverall, the design space of GTs includes *batching strategy, tokenization, positional encoding (PE), and Transformer architecture*. We categorize the baselines into two categories mainly based on the *Transformer architecture*. We further compare `HubGT` with the baselines in each category:\n* **Kernel-based GTs**: These models are signified by the graph kernels in their *attention mechanism*, i.e., utilizing the graph structure to modify Eq. (2) computation. Different models employ their distinct kernels, resulting in varying complexity and empirical performance. Corresponding to the dependency on topology, they entail neighborhood sampling as the *batching strategy*. \n* **Hierarchical GTs**: These models use the standard *Transformer architecture* and choose to retrieve graph information by *tokenization* and *PE*. The difference lies in the design of *tokenization* exhibiting varied utilization of graph topology. For example, `PolyFormer` uses the coarsened graph as tokens, while `ANS-GT` adaptively samples nodes in the induced subgraph to form each token. Before `HubGT`, most of these models use graph Laplacian as *PE*. The common *batching strategy* is random sampling among the tokens. \n* Other models, such as `SGFormer`, do not include the typical multi-head attention and hence are named **non-GT** models. \n* `HubGT` is considered as a hierarchical GT, and is thus mainly compared to this category in empirical evaluation. The novelty of `HubGT` lies in *tokenization* and *PE* designs highlighting both efficacy and efficiency: it exploits the label graph hierarchy as *tokens* to introduce global information, and is the first to introduce the dense SPD *PE* on large graphs, while both parts can be efficiently computed. \n\nIn addition, we also highlight the differences in the following aspects:\n1. **Complexity**: We consider the time and space complexity as the most inherent differences among the GTs, which can largely predict their empirical efficiency. As analyzed in **Table 1**, the complexity of `HubGT` is among the best. For the two most important terms dominating scalability: (1) **GPU memory**: HubGT completely removes graph-related terms $n,m$, which is scalable in preventing OOM. (2) **Training time**: HubGT's complexity is linear to the node size $n$, which is more scalable than models linear to the edge size $m$, as $m$ increases faster on large graphs.\n2. **Empirical performance**: As detailed in **Section 6.2**, overall, the efficiency of HubGT is the best among hierarchical GTs, which are directly comparable. Considering the limitations of other GTs as in **W1.(3)**, its efficiency gains are also significant.\n\nWe will include more details in Section 2 and Appendix B in the revised version.\n\n## I1&I2\n> In the caption of table 1 it would be good to mention all variables that play a role in the complexity. L, n, F, M etc.  \n> Indicate in bold / underline which method is based in computation time for the different elements.\n\nWe thank the reviewer for the suggestion and will improve the notation in Table 1. $L$ and $F$ are the depth and width of the model, respectively. $d=m/n$ is the average degree of the graph, and $s$ is the sample size for subgraph-based methods. The critical terms affecting scalability are mainly the node size $n$ and edge size $m$ of the graph. Between these two, $m$ is more significant as it increases faster and becomes the bottleneck on large graphs. \n\n## I3\n> Can't you create a scatterplot like visualization with the tradeoff between acc and computation? Probably separate for training and testing. Your main message is that you can reach a similar accuracy in much less time. A table doesn't easily convey this message.\n\nWe thank the reviewer for the useful comment. As adding new figures is not available during the rebuttal period, we will add this scatter plot as a visualization of Table 2 in the revised version. We will also provide more comprehensive comparisons distinguishing training and inference performance using a radar plot. \n\nIn general, from the **efficacy** perspective, `HubGT` achieves competitive accuracy on most datasets, while most kernel-based GTs exhibit accuracy drop on at least one dataset. The **efficiency** of `HubGT` is remarkable, with the best memory scalability and fast speed, especially superior to hierarchical baselines. Hence, we believe it achieves a favorable efficiency-accuracy trade-off."}]

Author rebuttal:

Meta-review: (a) Scientific Claims and Findings 

The paper claims to tackle the scalability issue of Graph Transformers by proposing HubGT, a framework that decouples graph processing from model training. Its main findings are: (1) A novel hierarchical hub labeling scheme can efficiently pre-compute and store graph structural information, including local and global connections. (2) This pre-computed index enables O(1) querying of Shortest Path Distance (SPD), making it feasible to use dense SPD as an effective positional encoding on large-scale graphs for the first time. (3) The resulting training process is independent of graph-scale operations, achieving linear complexity, favorable GPU utilization, and the fastest inference speed among baselines on large graphs.  


(b) Strengths 

1.	High Efficiency and Scalability: The core strength is the decoupled architecture, which separates the heavy graph computation into a one-time pre-processing step. This design significantly improves training and inference efficiency, reduces GPU memory bottlenecks, and makes the model highly scalable for large graphs.

2.	Novel and Effective Graph Representation: The paper innovatively uses a hierarchical hub labeling scheme for both node tokenization and enabling dense SPD-based positional encoding. This provides a richer representation of graph structure beyond local adjacency, proving effective on both homophilous and heterophilous graphs.

3.	Strong Empirical Results: The paper is supported by extensive experiments on 14 benchmark datasets, demonstrating state-of-the-art efficiency (especially inference speed) while maintaining competitive or superior accuracy. The complexity analysis is also thorough.

(c) Weaknesses in the initial rebuttal stage

1.	Static Graphs Limitation: The pre-computation-based approach is inherently unsuitable for dynamic graphs, as any change in the graph structure would require a costly re-computation of the entire index.

2.	Hub Selection Strategy: The method relies on a simple degree-based heuristic for hub selection. Reviewers noted that this might not be optimal for all graph topologies and that a deeper analysis or comparison with other centrality measures was initially missing.

3.	Limited Initial Baselines: The initial submission lacked comparisons to some relevant and strong baselines, including other scalable GTs (e.g., Exphormer) and recent message-passing GNNs. 


(d) Reasons for Acceptance 

The paper is accepted because it makes a significant and practical contribution to the field of Graph Transformers. Its core idea of decoupling graph computation is powerful and effectively addresses the critical challenge of scalability. The proposed HubGT framework is technically sound and is validated by strong empirical evidence, showing a superior efficiency-accuracy trade-off, especially its state-of-the-art inference speed. During the rebuttal, the authors provided a comprehensive response that successfully addressed the main weaknesses pointed out by the reviewers. They added new experiments against stronger baselines, provided deeper analysis on design choices like hub selection, and integrated a more advanced attention mechanism to demonstrate the framework's flexibility. This thorough rebuttal strengthened the paper significantly and demonstrated the robustness of their method.  

(e) Rebuttal Discussion Summary / Rebuttal 

The rebuttal period was very productive. The authors provided detailed responses and new experimental results that addressed the reviewers' primary concerns.

•	For Reviewer 1EVJ: The reviewer was concerned about missing baselines (Exphormer, Graphormer), the clarity of the HLL algorithm, and the lack of a detailed scalability study. The authors addressed this by adding experimental results for Exphormer , explaining OOM issues with Graphormer , providing a clearer explanation of their HLL algorithm in relation to classic PLL , and elaborating on the model's scalability in terms of memory and computation time. 

•	For Reviewer c6sP: The reviewer questioned the generalizability of degree-based hub selection and the choice of hyperparameters. The authors responded by evaluating their method on various synthetic random graphs to demonstrate robustness and comparing different centrality measures for hub selection. They also clarified the heuristics for setting hyperparameters. In the final justification, the reviewer maintained their score, noting concerns about dynamic graphs and the empirical nature of the findings, but the authors had already acknowledged the former as a limitation and provided extensive empirical validation for the latter.

•	For Reviewer UKq4: The main weakness identified was the lack of comparison with strong message-passing GNNs. The authors added experiments against four additional GNN baselines (GCNJK, MixHop, etc.). A follow-up discussion clarified a results discrepancy, which the authors attributed to different inference settings (mini-batch vs. full-graph) due to hardware constraints.

•	For Reviewer 1kw8: The reviewer pointed out several weaknesses, including the standard Transformer core, limitations on dynamic graphs, and missing baselines. The authors demonstrated the flexibility of HubGT by integrating it with FlexAttention, showing significant performance gains. They acknowledged the limitation regarding dynamic graphs as a future direction and addressed the other points in responses to other reviewers. The reviewer was satisfied with the response and maintained their high score.

•	For Reviewer Hvuy: The reviewer initially found it hard to see the clear benefits from the tables. The authors elaborated on their evaluation priorities (scalability, accuracy, then efficiency) and the novelty of their approach. They also agreed to add better visualizations (e.g., scatter plots) to convey the accuracy-efficiency trade-off more clearly in the final version. This clarification was convincing, and the reviewer raised score to "Accept".
Decision: Accept (poster)