HubGT: Fast Graph Transformer with Decoupled Hierarchy Labeling

We thank the reviewer for the thorough review and suggestions. We elaborate on the comments with further details below.

W1

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?

In 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:

1. 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.
2. 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.
3. 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.
4. 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.

W2

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.

Overall, 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:

• 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.
• 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.
• Other models, such as SGFormer, do not include the typical multi-head attention and hence are named non-GT models.
• 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.

In addition, we also highlight the differences in the following aspects:

1. 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.
2. 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.

We will include more details in Section 2 and Appendix B in the revised version.

I1&I2

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.
Indicate in bold / underline which method is based in computation time for the different elements.

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

I3

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.

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

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

We sincerely appreciate the reviewer for the insightful comments and detailed suggestions. We address all comments and related questions below.

W1&Q4

The core Transformer module is largely standard. The proposed approach could benefit from integrating efficient attention mechanisms to improve scalability.
Is it feasible to combine HubGT with efficient Transformer variants such as FlashAttention or Linformer, and what are the anticipated gains or trade-offs?

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

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

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

[R1] FlexAttention: A Programming Model for Generating Fused Attention Variants. MLSys'25.

W2Z&Q2

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.
Can the authors provide evidence or discuss how the hub label index could be updated incrementally in dynamic or temporal graph settings?

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

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

[R2] Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling. WWW'14.

W3&Q3

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.
Could the authors expand the experimental comparison to include scalable non-GT baselines?

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

W4&Q1

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

An 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:

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

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

W5

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.

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

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

We thank the reviewer for the thoughtful comments. Below, we present more details on experimental comparisons.

W1

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.

In 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:

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

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

^ Results from the original paper since configurations are not provided.

[GCNJK] Representation learning on graphs with jumping knowledge networks. ICML'18.
[MixHop] MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. ICML'19.
[TFGNN] Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach. WWW'24.
[S2GNN] Spatio-Spectral Graph Neural Networks. NeurIPS'24.

We thank the reviewer for the comments. We would like to clarify the following two points.

SGFormer

As mentioned in the SGFormer paper Appendix C, their model includes a global attention module and a convolutional GNN network. Hence, we also consider it as incorporating message-passing mechanisms. In our Appendix B.3, we further clarify that SGFormer does not contain the multi-head attention and encoding modules in common GTs. Therefore, its architecture is largely orthogonal to our focus on GT tokenization and positional encoding. We will amend Appendix B.3 to address the difference more rigorously.

MixHop

We would like to note that our evaluation of MixHop and GCNJK is under the mini-batch setting, which is more relevant to Table 4 & 8 in [1]. We would like to list and compare ours and [1]'s results below. Specifically:

• Our result for MixHop on penn94 is 75.0%, which is closely comparable to the 75.6% in Table 4 in [1]. Note that 60.3% is the result on ogbn-arxiv, not penn94.
• The remaining differences are mainly caused by the batching strategy during test time. [1] adopts mini-batch training and full-graph inference by default. However, this configuration causes OOM in some of our experiments, so we also enable mini-batching uniformly during model inference, which can lead to accuracy drops in some cases.

[1] Lim et al., "New Benchmarks for Learning on Non-Homophilous Graphs", 2021.

We thank the reviewer for the thorough review. We address all the comments and questions below.

W1

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.

We would like to discuss the possibility of secondary effects like thrashing here, and specifically evaluate the application to random graph topologies in Q2.

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

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

W2

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.

We notice that this was caused by a bug in our LaTeX hyperreference. We will carefully correct the notation to "Property" in future versions.

Q1

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.)?

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

[GraphSAGE] Inductive Representation Learning in Large Attributed Graphs. NeurIPS'17.

Q2

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?

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

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

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

[GenCAT] GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems'23.

Q3

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?

In the following table, we present experimental results of hub selection based on other metrics such as closeness centrality and PageRank.

• 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].
• Degree and closeness centrality lead to similar GT accuracy, while PageRank is less representative for selecting useful hubs.
• 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.
• 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.

We appreciate the comments from the reviewer. We would like to clarify some misunderstandings first:

Given that the main contribution of the paper is a set of algorithms for hub labeling of subgraphs around a root node $r$ on to of the existing PLL based hubs

Our contribution mainly lies in the novel tokenization and PE, which enables efficient GT learning on large graphs. To facilitate this, the subgraph SPD problem and Algs 1-3 are proposed.

If not, then there is no benefit since $d(u,v)$ has to be computed via the original PLL hub scheme.

The original PLL Eq.(4) is not required in Alg 3 querying. Instead, the SPD is precomputed by Alg 2 as H-0, which has a lower construction complexity $O(ns^2)$ than the original PLL $O(ns^3)$.

since the hub nodes play equivalent roles to cluster heads and it is highly likely that central nodes are hubs.

Hub labeling is inherently different from clustering, as it adds a number of label edges, while clustering methods only utilize the raw graph and are more sensitive to data distribution.

In the case of heterophilous graphs or even in general for arbitrary $r$ in random graphs, it is quite possible that the subgraph around $r$ has a majority of nodes that do not produce advantageous labels (shortcuts through $r$).
Clearly, it will not be on many shortest paths in the subgraph and so overhead should be higher.

As evaluated in Q2, the overhead in random graphs is actually lower, since global hubs can effectively capture most queries.

C1.Hub Selection

We understand there are concerns that the hub selection process may be affected by data distribution. In our approach, we utilize global and local hubs with considerations of both efficiency and expressiveness, with the primary design goal of facilitating GT learning.

In terms of efficiency, starting from low-degree nodes does not greatly affect the indexing speed, as its complexity is still theoretically bounded by $O(ns^3)$. However, it increases the index size. Note that despite varied graph patterns, high-degree nodes are more likely to be on SPs. Hence, even if the indexing starts from low-degree nodes, high-degree ones are still explicitly added to a large number of labels.

As Sec 3, the effectiveness in GT learning mainly comes from the hierarchy beyond adjacency. Instead of crafting specific subgraph selection strategies for different graph patterns, we choose to build a sufficiently large subgraph and include a wide range of nodes to allow the model to learn the important relationships through attention. This is also our intuition regarding hyperparameter values, that they are less sensitive as long as there is sufficient information to learn.

Regarding the effectiveness on different graph patterns, hub labeling is closer to graph rewiring, which is well-studied for addressing heterophily [R1-R2], than to clustering. As analyzed in [R3-R4], heterophily is mitigated by increasing overall homophily through edge addition, which is in line with our observation in Sec 3&D.1.

[R1] Make Heterophilic Graphs Better Fit GNN: A Graph Rewiring Approach. TKDE'24.
[R2] Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns. KDD'21.
[R3] Towards Understanding and Reducing Graph Structural Noise for GNNs. ICML'23.
[R4] Revisiting Robustness in Graph Machine Learning. ICLR'23.

C2.Multi-device

The setting in Review 1EVJ.W3 is mainly for multi-device training, where the index and input attributes can be shared across devices once precomputed. In this case, HubGT is superior to previous models especially kernel-based ones, since only node-wise inputs are required and can be easily batched.

In distributed settings where the indices also need to be partitioned for training, $\mathcal{L}$ can be divided among devices in a node-wise manner, while $\mathcal{I}$ and attributes $X$ need to be either (1) mirrored or (2) stored centrally and communicated during training, both also in a node-wise manner. (1) is a common practice in distributed hub labeling [R5], where rows $\mathcal{I}_v$ and $X[v]$ are copied to the device with $\mathcal{L}(u)$ and $v \in \mathcal{L}(u)$. (2) shares a similar setting with the distributed training of sampling-based GNNs.

Regarding distributed indexing, hub labeling also benefits from its node-centric design [R6]. As mentioned by the reviewer, there is an extensive body of literature, which is largely orthogonal to our contribution on incorporating hub labeling into GTs. Hence, we only mention its possibility in this paper.

[R5] Planting trees for scalable and efficient canonical hub labeling. VLDB'19.
[R6] Pruned Landmark Labeling Meets Vertex Centric Computation: A Surprisingly Happy Marriage! arXiv.

We sincerely appreciate the constructive feedback and acknowledgment of our main contributions from the reviewer. We reply to all the points below.

W1

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

(1) Exphormer

Difference with HubGT

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

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

Experiments

The 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:

• The efficiency of Exphormer is mostly comparable to kernel-based methods evaluated in our paper, including fast training and less scalable GPU footprint.
• The model accuracy, especially under heterophily, is limited due to the dependency on graph topology and the relatively small model size.
• 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.

---

(2) Graphormer

Difference with HubGT

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.

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

Experiments

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

We will include more comprehensive comparisons for both models in the revised version based on the current discussions and experiments.

W2

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.

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

PLL overview

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

In 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$.

As 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$.

Hierarchical Labeling in HubGT

In 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)$.

To 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)$.

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

W3

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.

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