ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment
Authors: Tomer Borreda
Daniel Freedman
Or Litany
Venue: Accepted by TMLR ()

Abstract: We present ReHub, a novel graph transformer architecture that achieves linear complexity through an efficient reassignment technique between nodes and virtual nodes. Graph transformers have become increasingly important in graph learning for their ability to utilize long-range node communication explicitly, addressing limitations such as oversmoothing and oversquashing found in message-passing graph networks. However, their dense attention mechanism scales quadratically with the number of nodes, limiting their applicability to large-scale graphs. ReHub draws inspiration from the airline industry's hub-and-spoke model, where flights are  assigned to optimize operational efficiency. In our approach, graph nodes (spokes) are dynamically reassigned to a fixed number of virtual nodes (hubs) at each model layer. Recent work, Neural Atoms (Li et al., 2024), has demonstrated impressive and consistent improvements over GNN baselines by utilizing such virtual nodes; their findings suggest that the number of hubs strongly influences performance. However, increasing the number of hubs typically raises complexity, requiring a trade-off to maintain linear complexity. Our key insight is that each node only needs to interact with a small subset of hubs to achieve linear complexity, even when the total number of hubs is large. To leverage all hubs without incurring additional computational costs, we propose a simple yet effective adaptive reassignment technique based on hub-hub similarity scores, eliminating the need for expensive node-hub computations. Our experiments on long-range graph benchmarks indicate a consistent improvement in results over the base method, Neural Atoms, while maintaining a linear complexity instead of $O(n^{3/2})$. Remarkably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub outperforms competitive baselines and consistently ranks among the top performers across various benchmarks.

Published in Transactions on Machine Learning Research (08/2025)
ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment
Tomer Borreda
Comerboreela@esstcnniiioccm
Deportment of Computer Science Technion- Institute of Technology
Daniel Freedman
dfreedman Stauer. tav.ac..
Deportment Applied Mathematics
Tel Aviu University
Or Litany
orlitany@lechntioncco
Department of Computer Science Technson-Isrrel Institute of Technology
NVIDIA
Reviewed on OpenReview: https://openee http:///ppereeieu..eee
UOQQ
Abstract
We present ReHub, novel graph transformer architceture that achieves linear complex- ity through an efficient reassignment technique between nodes and virtual nodes. Graph transformers have become increasingly important graph learning for their ability to uti- lize long-range node communication explicitly, addressing limitations such as oversmoothing and oversquashing found in messagg-passinn graph networks. However, their dense atten- tion mechanism scales quadratically with the number of nodes, limiting their applica billccybility to large-scale graphs. ReHlub draws inspiration from the airline industry's hub-and-spoke model, where flights are assigned to optimize operational efficiency. In our approach, graph nodes (spokes) are dynamically reassigned to a fixed number of virtual nodes (hubs) at each model layer. Recent work, Neural Atoms [Li et al. 2024). has demonstrated impressive and consistent improvements over GNN baselines by utilizing such virtual nodes; their findings suggest that the number of hubs strongly influences performance. However, increasing the number of hubs typically raises complexity, requiring trade-off maintain linear complex- ity. Our key insight is that each node only needs to interact with small subset of hubs to achieve linear complexity, even when the total number of hubs is large. To leverage all hubs without incurring additional computational costs, we propose simple yet effective adaptive reassignment technique based on hub-hub similarity scores, climinating the need for expen- sive node-hub hub computations. Our experiments on long-range graph benchmarks indicate a consistent improvement results over the base method, Neural Atoms, while maintaining linear complexity instead of O(n3/2). Remarkably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub outperforms competitive base- lines and consistently ranks among the top performers across various benchmarks. Code is available on our project webpagd
1 Introduction
Learning on graphs is essential in numerous domains, including social networks for influence prediction, bio- logical networks for understanding protein interactions, molecular graphs for predicting chemical properties,

---

Published in Transactions on Machine Learning Research (08/2025)
knowledge graphs for recommendation systems, and financial networks for fraud detection and risk assess- ment. Graph neural networks (GNNs) have emerged as powerful tools in these areas, operating via message passing between connected nodes. However, a significant challenge with GNNs is their limited communica- tion range. While stacking messago-passing layers can increase the communication distance, it comes at a computational cost and can cause issues such as oversmoothing and oversquashing (Alon & Yahay 2020 Topping et al. 2021).
Inspired by the success of transformers in natural language processing (Vawwani et al 2017 graph trans- formers offer a solution by enabling global node communication through attention mechanisms (Diivedi & Bresson, 2020 Shchzad et al. 2024). This overcomes the communication bottlenecks of GNNs, but it comes at a significant computational cost. The quadratic complexity of dense attention operations limits the scalability of graph transformers, as even modest-sized graphs can exhaust GPU memory. Several methods have been suggested to reduce the complexity of global attention. For example, GraphGPS (Rampášck al. 2020) or Big Bird (Zaheer et al. 2020). Originally designed for processing sequences rather than graph structure, these linear- memory transformers induce significant computational time and do not match the performance of dense attention (Shirzad et al. 2023).
ct al. 2022) combines sparse attention mechanisms like Performer (Choromanski
Recently, transformer-based graph networks have utilized the addition of virtual global nodes, through which graph nodes communicate to sparsify the attention. By constraining the attention to be between the graph nodes and these virtual nodes, the attention complexity reduced to the number nodes times the number of virtual nodes, allowing the overall complexity be governed by the number of virtual nodes. Exphormer (Shirzad et al.] 2023) maintains linear complexity by using fixed number of virtual nodes, while Neural Atoms (Li et al.j 2024] explores both fixed number and ratio relative to the number of nodes. An important finding in Neural Atoms is that adding more virtual nodes increases prediction accuracy, creating a trade-off between computational complexity and accuracy.
In this work, we introduce ReHub, a novel graph transformer architecture that achieves linear complexity by dynamically reassigning graph nodes virtual nodes. We are inspired by complex systems where efficient connectivity and adaptability are crucial for optimal performance. A pertinent example is the airline industry, where flights are dynamically assigned to limited number of major airports (hubs) to optimize operational efficiency. We identify the graph nodes with spokes and the virtual nodes with hubs. The key insight of our approach stems from noting that the transformer's complexity is driven by spoke-hub attention. Therefore, it is not necessary to reduce the total number of hubs to achieve linear complexity; instead, using a fixed, small mumber of connected hubs per spoke is sufficient. To effectively utilize all hubs without increasing computational cost, we introduce a simple yet. efficient adaptive reassignment mechanism. In order do so, and yet avoid the costly computation of the entire set of spoke-hub interactions, our reassignment mechanism is based on hub-hub similarity scores, which are cheap to compute.
In summary, then, our primary contribution is novel graph transformer architecture that integrates global attention with an efficient spoke-hub reassignment strategy, significantly enhancing scalability while main- taining performance. Our experiments on long-range graph benchmarks indicale a consistent improvement in results over the base method, Neural Atoms, while keeping a linear complexity instead of O(n3/3). Re- markably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub performs competitive baselines and consistently ranks among the top performers across various benchmarks.
2 Related work
Learning large graphs Graph learning architectures are well-established and highly active field of rescarch (Wu et al. 2020). Common GNNs, such as GCN/GCN Kipf & Welling. 2016 Chen et al. 2020).
/Velickovic el al. 2017 Brody et al. 2021), GIN/GINI (Xu el al.] 2018 Hu et al. 2019). and GatedGCN (Besson & Laurent 2017). rely on a message- message-passing architecture that aggregates information. In each layer every graph node updates its representation by aggregating the neighboring nodes. This archi- tecture inherently limits their ability accumulate information over large distances due to phenomena such over-smoothing (Alon& & Yahav 2020 where node representations become indistinguishable, and over-
2

---

Published in Transactions on Machine Learning Research (08/2025)
squashing (Topping et al. Consequently, learning large graphs remains a persistent challenge (Duan et al. 2022). To address this issue, some methods focus on reducing the memory footprint. One approach involves dividing graphs into
2021 where the capacity to propagate information is restricted by bottlenecks.
mini-batches (Wu ct al., 2024), while another uses only segments the graph for training (Cao et al. 2024).
Transformer architectures have recently gained popularity for graph-based tasks (Müller et al. 2023 y. These methods address the over-smoothing and over-squashing issues by enabling all nodes to interact with each other through attention (Velickovic et al.) 2017 Ying et al. 2021 However, this approach is computa- tionally inefficient, with quadratic time and memory consumption in the number of nodes. To mitigate these inefficiencies, more efficient transformer architectures have emerged which utilize different approaches to reduce the number of computations such as approximations in Performer (Choromanski et al. 2020), predefined attention patterns in BigBird (Zaheer et al., 2020) and better parallelism and partitioning in FlashAttention (Dao et al. 2022). GraphGPS (Rampášck et al. 2022) proposes a general framework for combining messago-passinn neural networks (MPNNs) with attention at each layer, facilitating the use of such allention mechanisms.
Recent works have introduced approaches that leverage the structure and inherent information of the graph, such as tokenization of hops of node's neighbors in NAGphormer and applying ttructure-preserving attention on encoded sequences of sub-graphs in Gophormer (Chen et al. 2022 Zhao et al. 2021 Some of these works ensure that the computational complexity remains linear in the number of nodes (Shirzad et al., 2023 Chen
it al., 2022 Wu et al. 2024 2022) which allows them to be applied to larger graphs. We also propose a linear complexity architecture that passes nodes' information through a medium that efficiently orchestrates the passage of information in the graph and between nodes.
Finally, we note that recently, State Space Models (SSMs) (Gu & Dao 2023 have emerged as promising approach for efficiently processing large sequences, with their adaptation to graphs showing notable results (Wang et al., 2024; Behrouz & Hashemi 2024). However, in this work, we focus on transformer-basel architectures, which remain the current go-to approach.
Virtual nodes The concept of virtual nodes involves introducing new external nodes that interact with the graph to facilitate information exchange between existing nodes (Gilmer et al., 2017 Recent studies (Shirzad et al. capture long-range information through nodes within the context of transformers (Shirzad et al. 2023 Li et al. 2024 Fu et al. 2024). Similarly, we use virtual nodes that communicate with both each other and the graph nodes through attention. However, unlike prior methods, we dynamically update the connectivity between the virtual nodes and graph nodes at each layer, enhancing the flow of information.
2023; Cai et al. 2023 Hwang et al. 2022) utilize this concept to extend the graph's capability to
passagg... Other research explores the integration of virtual
3 Method
3.1 Pipeline overview
Our proposed architecture, depicted in Figure [ is aimed at handling long-range graph node communication while maintaining computational efficiency. This is implemented through hubs, that act as information aggregators and distributors from and to the spokes. This allows for long range communication to be manifested as hub-hub communication. ReHub is carcfully designed to follow our key observation that the complexity can be kept linear as long as: (1) the number of hubs N₁, is kept small enough, on the order of VNe, where N₂ is the number of spokes; and (2) k, the number of hubs connected to each spoke per layer, is a small constant (e.g., k k=3) 3).
In what follows we describe the architecture of ReHub, define every component and the interaction bet spokes and hubs. First we present an overview of the notation. Then we present an initialization scheme for the hubs and explain each part of the architocture: (1) Spokes-Spokes update (2) Spokes- Suok update (3) Hubs-Hube Hubs update (4) Hubs-Spokes update (5) Hub Assignmeet. Finally, we show that the complexity given by this architecture is linear in the number of nodes.
3

---

Published in Transactions on Machine Learning Research (08/2025)
Input
Long-Range Spoke Update Layer
Hub Init.
+ E, h
525 MPNN
h
S
Reassig meiignment
Task Head
Graph
A
A, S
E, /t
E,
+
E
S2H
H2H
H2S
x
Eigh
d2 d2
Encoder
Asseen pasmmee
Hub
Clustering
Feature Agg.
Hub Initialization
Hub (Re)Assignment
Spokes
Hubs
Figure 1: Illustration of ReHub architecture. (1) Overview of the different steps in the architecture. A is the input (spoke) graph's adjacency matrix; spoke fratures 8; hub features h; hub assignment E; and r contains attention scores from the Hubs-Spokes attention. (2) Hubs initialization. Spokes are first clustered, then each cluster aggregated to compute hub features. Finally, each spoke assigned more hubs. (3) Hub (Re) Assignment.. Each spoke selects the & hubs closest to its most similar hub as its new assignment. (4) Illustration of connectivity between spokes and hubs. Information pass between spokes with MPNN; while the interaction between hubs and spokes is performed via attention and only through available connections Big The hubs pass information wetween themselves via full self-aliention.
3.2 Notation
Spokes and Hubs. Throughout this paper, we refer to the graph nodes as "spokes" " 2 and the added virtual nodes as "hubs". The number of spokes N., and they are indexed with i, = ,,...,N,, Each spoke has features represented by 8,, E IR,, with the collection of all spoke features denoted by 8. Similarly, the number of hubs is denoted by NR, and they are indexed by in .,..., NN. Each hub has features represented by hi, Idd and the collection of all hub features is denoted by h. The binary matrix E E {0, 1) X.x,, referred to as the hub assignment matria, indicates which spokes are connected to which hubs:
NN.
-(0
if spoke is connected to hub in otherwisc
E, E
S.L. EIN, k: IN,, 1
where 1x denotes an all-ones column vector of length N. Namely, given spoke is connected exactly k hubs, where & = O(1). E can be implemented as sparse assignment matrix. Finally, where relevant the network layer is denoted using superscript.
Bipartite graph attention. In our pipeline we utilize graph attention (Brody et al. 2021 between spokes and hubs that interchangeably act as source and target graphs. The definition as follows:
o, r= -Attentio (K, Q.
where the input consists of source graph nodes K E Rm destination graph nodes Q RR and a hub assignment E E {0, 1m, containing the connections between the nodes of the source graph with those of the destination graph. The outputs the per-node updated features O Rooxd of the destination graph. We optionally output the sparse attention scores I E Raax*, computed for the non-zero entries of E. For non ninabitattite graph the same formalism can be applied by taking K Q, enabling self-attention within the graph.
2In this work, we "spokes" to represent graph nodes, deviating from the more common usage where "spokes" refer edges.
4

---

Published in Transactions on Machine Learning Research (08/2025)
3.3 Initialization
We initiate ReHub by creating Na = -rV,, hubs, where r is the hub-ratio, set to in almost all benchmarks. To populate the hubs features with meaningful values we compute them based on (i) clustering the input graph (í.e. the graph of spokes), specified by the adjacency matrix A, and (ii) aggregating the spoke features s. We then assign each spoke to & hubs. This process is illustrated in module (2) of Figure 1
Clustering. We partition the graph A, along with its spoke features 8, into N₁ clusters using METIS (Kryypis & Kumar 1998). This method takes as input an adjacency matrix between spokes A well the desired number of clusters No; and returns as output a cluster index for each spoke. We denote each cluster Cip, where spoke belongs to cluster if i, E Ci.,
Hub features. For each cluster Cik, we compute the initial hub features. For hub-cluster in, we aggregate the spoke features as follows:
0 Aggregate-Feat((E] b.cc,,
There are several options for the Aggregate-Feat function. For categorical or ordinal variables (e.g.,, atom type), one may compute a histogram. For continuous variables, one may compute the average. In our case, we choose average the features after the nodes have passed through positional encoding layer followed by a feedforward layer.
In Section 4.3 compare our initialization scheme with those proposed in previous works and demonstrate that it significantly improves performance.
Hub assignment. We aim to connect each spoke with a total of k hubs. Since each spoke s;, already has a single connection to a hub ha, as result of the clustering, we assign the remaining k 1 1 hub connections for each spoke, by selecting the hubs closest to ha, in terms of feature similarity. The assignment procedure is detailed in Section 3.4 This step results in the spoke-to-hub initial assignment matrix E.
3.4
spoke update layer
A key component of ReHlub's architecture is the long-range spoke update layer, which leverages both the spoke graph and the connections between spokes and hubs. Specifically, maintain efficiency, we avoid global spoke-to-spoke attention operations by using local message passing and global spoke-to-hub operations. We further keep the spoke-to-hub attention efficient by restricting the hub connectivity of spokes to a small constant number of hubs, k. Long-range information flow between spokes occurs through hub-to-hub hub communication, which is made efficient by selecting a number of hubs proportional to the square root of the number of spokes. This relaxes the restriction imposed by previous graph transformer methods (Shirzad et al., 2023). which limited the number of hubs to small constant. This layer is repeated times throughout the network. Each layer E consists of five steps, shown in Figure 1 which describe in detail below.
(1) Spokes + Spokes: For the local spoke update using the neighboring nodes in the graph:
(+ (s")
(4)
where MPNN is a single layer of a message-passnng neural network. Since this operation restricted to the 1-ring neighborhood, it remains efficient. Notably, any type of mossage-passing scheme can generally be integrated into our pipeline.
(2) Spokes + Hubs: Given the updated spokes, update the hubs using the assignment matrix. Since each spoke is connected to exactly & hubs, the operation is sparse and memory efficient.
h g+ AAtentionns" - h E
(5)
(3) Hubs Hubs: The hubs now interact using self-attention. Even though the connectivity Eswu is dense, the overall number of hubs is kept on the order of VN., ensuring overall linear complexity.
h f+1 Attention 4+h h E,Eat)
(6)
5

---

Published in Transactions on Machine Learning Research (08/2025)
(4) Hubs - Spokes:
Given the hubs, update the spokes:
pet1 =Attention(h 2+1 + E E
p N₂ NA
(7)
where the matrix - (E >h" assuring the same efficiency as the Spokes - Hubs step.
(5) Hub (Rc)Assigmmenn)) the method to achieve its full potential, should utilize all available hubs. We achieve this by keeping only k connected hubs per spoke each layer, while allowing each spoke to reassign k -- of its hubs before proceeding to the next layer The reassignment is based on spoke-hub similarity. Selecting the hubs closest to each spoke, however, would require N₂ x No. computations. To avoid this, we leverage the distances between hubs, which are efficient. to compute.
While restricting each spoke to connect with hubs maintains efficiency, for
We then retain the hub most similar to each spoke from the sparse set of connected hubs, replacing the remaining & hubs with those closest to it. This procedure outlined in Algorithm [ The matrix of distances between all hub features is denoted by A. Naturally, hub is closest to itself and would be selected first. Additionally, we use r, the attention score matrix, to identify, for each spoke, the most similar hub to which il is connected.
Algorithm Hub (Re) Assignment
Require: Hub-Spoke cross-altention score matrix p and Hub-Hub distance matrix A {+1
for in to N₂ do H(ir)) = Bottom k- Indices in of A 1+1)
end for
for i, = to N₂ do "n = arg maxi, rf+1 i
1 if in E H(())
E++1 b2th
otherwise
end for return E
Final prediction. The pipeline concludes with task-specific prediction head. In this work, we demon- strate tasks such as graph classification, regression, node classification, and link prediction. These prediction heads use an MLP on the final spoke feature predictions, st, with further aggregation for graph-level tasks, For link prediction, the pipcline computes a similarity score for every pair of nodes connected by an edge.
Complexity Recall that sparse attention is used, where multiplicat ions are performed only between spokes and the k hubs to which they are connected. The resulting time and memory complexity for each Spokes-to to- Hubs interaction step is k(N,k); and for the Hubs self-atlention step, it is O(N2). By taking N₁. = Ov.N.) and & = (1), we achieve linear complexity in the total number of spokes N., as desired.
4 Experiments
Methods in comparison. We compare ReHub against leading graph transformer based methods.
GraphGPS (Rampášck et al. 2022) offers a framework integrate MPNNs of different types (Kipf &
Welling 2016 Chen al.] 2020 Hu al. 2019 Bresson & Laurent 2017) and transformers. Transformer
indicates straightforward adaptation of the standard transformer architecture Vaswani et al. (2017) to graphs. Spectral Attention Networks (SAN) (Kreuzer et al. (021)) employ attention on the fully connected graph in addition to graph attention using the original edgges Closest to our method is Neural Atoms (Li et al.
2024) which utilizes a set of different, learned, virtual nodes at each layer. Neural Atoms is able to propagate long-range information, improve performance across various tasks and can be modularly applied to different MPNNs. As opposed to Neural Atoms, in this work we aim to tackle the efficiency aspect, í.e. to maintain
We note that, although we replace hubs while keeping the clasest hub connected, later layers, that closest hub may change. This flexibility prevents from being overly constrained by the initial hub selection.

---

Published in Transactions on Machine Learning Research (08/2025)
linear complexity in the number of nodes in graph without loss of performance. Exphormer (Shirzdd et al. 2023) introduces transformer architecture that achieves linear computational complexity by leverag- ing expander graphs (Alon, 1986) to define sparse attention patterns. In this model, each node attends only to a fixed number of neighbors specified by a fixed expander graph, and a few global virtual nodes connected to all nodes are used to capture global context. In contrast, our proposed method ReHub employs a dynamic model where virtual nodes (hubs) are connected subsots of nodes (spokes) rather than all nodes. ReHub allows for rewiring connections between layers, enhancing adaptability while avoiding bottlenecks associated with fully connected global nodes, all while maintaining linear computational complexity.
Datasets. Due to lack of large scale datasets that explicitly benchmark long-range capabilities we divide the evaluation to (1) long-range communication ability and (2) large graphs to verify memory efficiency. For long-range communcattio we evaluate ReHub on the long-range graph benchmark (LRGB) which is is widely used to evaluate methods which aim at overcoming issues such as oversmoothing and oversquashing. LRGB comprises five datasots. Two of the datascts are image-based graph datasets: PascalVOC-SP and COCO-SP which contain superpixel graphs of the well known image segmentation datasets VOC and COCO. The latter three datasets are molecular datasets: Peptides-Func, Peptides-Struct and PCQM- Contact, which require the prodiction of molecular interactions and properties that require global aggregation of information. For evaluation on large graphs we show results on graph datasets of citation networks: OGBN-Arxiv and Coauthor Physics which include about 1 170K and 30K nodes respectively, with the task of node class prediction. Additionally, we evaluate peak memory consumption on a custom dataset of large random regular graphs (Steger Wormald 1999] Kim & Vu 2003) of gradually increasing sizes from 10K to 700K nodes. Additional statistics about the datasets is available in Appendix A.
Metrics and evaluation. We evaluate our models using several metrics: Average Precision (AP), Mean Absolute Error (MAE), Mean Reciprocal Rank (MRR), F1 Score, and Accuracy. These are standard metrics and we refer to Dwivedi et al. (2022) for more details. For the evaluation of ReHuub, we report the mean + std over runs, cach with a different random scod. Results for other models, including NeuralAtoms [Li eet al., 2024), Exphormer (Shirzad el al. 2023) and GraphGPS (Rampášek et al., 2022). were reported as published in their original works.
Hardware. All experiments were performed using one NVIDIA L40 GPU with 48GB of memory.
4.1 Long-range graph benchmark
A major challenge in graph learning is long range communication - sccnarios where the prediction relies on information residing at far location of the graph. In this experiment, we evaluate ReHub on a set of such tasks provided by the LRGB dataset. We split the comparison in two, first establishing the modularity of ReHlub by integrating it with various MPNN layers; we then follow with a comparison against leading methods.
MPNN modularity. Similar to Neural Atoms, which improves performance across various MPNNs, ReHub is equally modular. In Table [ we present a comparison of Rellub using several common MPNNs. Results are shown for both the sparse small-ane a dense variant, ReHub-FC, where each spoke is fully connected to all hubs. The performance of both the sparse and dense configurations is compared to Neural Atoms as well the vanilla MPNN technique, demonstrating signifieant improvements across datasets and MPNNs. Interestingly, we observe that the performance of Neural Atoms is strongly affected by the base MPNN used. e.g., for Peptides-fund the final AP ranges between 0.60 and 0.66, while ReHub demonstrates increased robustness ranging between 0.64 and 0.67. Remarkably, thanks to our reassignment procedure, which promotes high utilization of all hubs, our sparse version achieves performance comparable to the dense version.
the number of hubs connected to each spoke per layer, k. is
Comparison with basclines. In Table we present a comparison between our ReHub using the best per- forming MPNN and state of the art methods on the LRGB benchmark. As can be seen, ReHub consistently scores among the top two methods.
7

---

Published in Transactions on Machine Learning Research (08/2025)
Table MPNN modularity. Test performance on datasets from the long-range graph benchmarks (LRGB) (Dwivedi al. 2022) compared various GNN types to Neural Atoms (Li et al. 2024 ReHub- FC has each spoke fully connected to all hubs. Best results are colored: first, second.
Model
Peptides-fum
Peptides-struct
PCQM-Contact
AP 1
MAE
MRR
GCN
0.5930 0.0023
0.3496
0.0013
0.2329
0.0009
NeuralAtoms
0.6220 0.0046
0.2606
0.0027
0.2534
0.0200
+ ReHub-FC
0.6663 + 0.0053
0.2489 + 0.0011
0.3492 + 0.0012
+ ReHub
0.6656 0.0043
0.2497
0.0021
0.3469 + 0.0014
GCN2
0.5543 + 0.0078
0.3471 + 0.0010
0.3161 + 0.0004
NeuralAtoms
0.5996 0.0033
0.2563 0.0020
0.3049 = 0.0006
ReHub-FC
0.6427 0.0085
0.2511
0.0015
0.3386 0.0026
+ ReHub
0.6406 + 0.0030
0.2530 + 0.0029
0.3375 + 0.0013
GINE
0.5498 0.0079
0.3547 + 0.0045
0.3180 = 0.0027
NeuralAtoms
0.6154 = 0.0137
0,2553 + 0.0005
0.3126 = 0.0021
ReHub-FC
0.6682 0.0098
0.2506 0.0012
0.3426 0.0014
ReHub
0.6582 0.0095
0.2514 + 0.0056
0.3429 + 0.0014
GatedGCN
0.5864 0.0077
0.3420 0.0013
0.3218 0.0011
NeuralAtoms
0.6562 + 0.0075
0.2585 + 0.0017
0.3258 + 0.0003
+ ReHub-FC
0.6732 + 0.0107
0.2501 + 0.0034
0.3526 + 0.0014
ReHub
0.6685 0.0074
0.2512 0.0018
0.3534 0.0014
GatedGCN +RWSE
0.6069 0.0035
0.3357 0.0006
0.3242 + 0.0008
NeuralAtoms
0.6591 0.0050
0.2568 + 0.0005
0.3262 + 0.0010
+ ReHub-FC
0.6690 + 0.0025
0.2490 + 0.0075
0.3523 + 0.0012
ReHub 0.6653 0.0054
0.2488 0.0017
0.3528 + 0.0008
Table 2: Test performance on datasets from the long-range graph benchmarks (LRGB) Dwivedi et al. 2022) compared to baselines. For Neural Atoms we show only available results. ReHub-FC has each spoke fully connected to all hubs. Best results are colored: first, second.
Model
Peptides-fune
Peptides-struct
PCQM-Contact
PascalVOC-SP
AP t
MAE
MRR
F1 Score
LapP
0.6326 0.0126
0.2529 0.0016
0.3174
0.0020
0.2694 + 0.0098
0.6384 + 0.0121
0.2683 + 0.0043
0.3350 + 0.0003
0.3230 + 0.0039
GraphGPS
0.6535 1 0.0041
0.2500 1 0.0005
0.3337 + 0.0006
0.3748 1 0.0109
Exphormer
0.6527 0.0043
0.2481 + 0.0007
0.3637 - 0.0020
0.3975 + 0.0037
NeuralAtoms
0.6591 + 0.0050
0.2553 + 0.0005
0.3262 + 0.0010
n/a
ReHub-FC (Ours)
0.6732 + 0.0107
0.2489 + 0.0011
0.3526 + 0.0014
0.3526 + 0.0045
ReHub (Ours)
0.6685 + 0.0074
0.2488 + 0.0017
0.3534 = 0.0014
0.3860 + 0.0172
4.2 Performance on large graphs
Peak memory vs. graph size. Our method demonstrates lincar memory complexity. To showcase this in practice, we compare the peak memory consumption of our approach to other methods on graphs of varying sizes. Since no existing benchmark offers a collection of gradually growing graph sizes we instead construct series of toy graphs with sizes varying between 10K and 700K. The graphs are d-rogular (i.e. each node has d neighbors), and are populated with random node features and edge attributes. In this experiment, set d = 3. To keep the comparison fair, for all methods we used similar parameters like the number of
8

---

Published in Transactions on Machine Learning Research (08/2025)
Peak Memory Consumption vs. Graph Size
Model
25
GraphGPS+Transforee
Peak Memory per Graph (GB)
GraphGPS-Performer
Exphormer
20
Neural Atoms, NAs=0.1 M₂ (Original)
Neural Atoms, NAs=vN;
XOOM
ReHub
15
10
5
0
100
200
300
400
500
600
700
Graph Size (thousands nodes)
Figure Peak memory consumption for different architectures. We compare ReHub to Neural Atoms (Li et al., 2024) and other architectures, and show that ReHub memory consumption is both linear in the number of nodes and requires less memory.
Table 3: Coauthor Physics (hichur et al. 2018 and OGBN-Arxiv (Hu et al.
2020 Lest results show ReHub
achieves comparable accuracy to Exphormer with significant reduction in memory consumption.
Model
Coauthor Physics
OGBN-Arxiv
Peak Memory (GB) 4
Accuracy 1
Peak Memory (GB)
Accuracy f
GraphGPS (Trrnsformer)
OOM
00M
Exphormer
1.77
97.16 +: 0.13
2.83
72.44 +: 0.28
ReHub (Ours)
1.13
96.89 + 0.19
2.45
71.06 + 0.40
layers and hidden dimension. A detailed description of the used parameters is provided in Appendix A.2 For Neural Atoms, follow the guidelines provided in the paper and use ratio of 0.1 for the number of virtual nodes. As this ratio results in asymptotic complexity of O(N2) additionally include results for Neural Atoms with N₁ = VN, for more memory efficient version reaching O(N3/2). For Exphormer, the expander graph has a degree 3, which the same value as used for ReHub. The results, shown in Figure 2 indicate that our method uses less than half the memory of other methods while exhibiting a linear memory usage trend.
Memory consumption and accuracy on large graphs benchmarks. We evaluate ReHub on the competitive Coauthor Physics and OGBN-Arxiv datasets which have about 35K and 170K nodes respectively. Comparing ReHub to Exphormer on Table 3 shows an improved memory consumption by about 36% for Coauthor Physics and 13% for OGBN-Arxi while accuracy is comparable. We follow Exphormer and include GraphGPS (with vanila Transformer) in the comparison highlight that these graph sizes are considered challenging to process.

---

Published in Transactions on Machine Learning Research (08/2025)
Table 4: Ablation study of long-range spoke update layer components. We measure the effect of various components of ReHub on top of a GatedGCN MPNN, using the PascalVOC-SP datasct. The number of hubs used per graph (#Hubs): for 22 it is a static amount and for vN, it is dynamic per graph size. Initial hubs (Hubs Init) can be set as learned parameters or initialized from the assigned spokes as described in 3.3 where we can add a feedforward layer on the spokes (Spokes Enc) before aggregation. Reassignment is as described in 3.4 We use h- = 3 for all runs.
GNN
#Hubs
Hubs Init
Spokes Enc
Reassignment
PascalVOC-SP (FI 1)
0.3152 + 0.0045
22
Learned (As in NA)
0.3084 = 0.0044
+
22
Cluster Mean
0.3574 = 0.0065
+
N
Cluster Mean
0.3703 = 0.0086
N
Cluster Mean
0.3797 + 0.0123
N
Cluster Mean
+
0.3775 + 0.0040
N
Cluster Mean
+
0.3860 = 0.0172
4.3 Ablations and analyses
Long-range spoke update layer components.
As described in Section 8 our long-range spoke update layer is designed to handle long range communication while maintaining memory efficiency. The ablation provided in Table highlights the contributions of the primary design choices, evaluated on PascalVOC-SP which contains an average of 479.4 nodes per graph. (1) Initialization of hub features from spokes vs. learned hub features as parameters, where the latter is analogous to the initialization process of Neural Atoms. The initialization scheme, outlined in Section 3.3 is compared to a configuration where hub features are learned parameters, i.e, hº, = P., E Rd Initializing the hubs from spokes significantly improves performance, while using learned hubs results in reduced performance compared to the GNN baseline. (2) The use of a fixed vs. dynamic number of hubs. For the fixed case, we set the number of hubs to 22, which is approximately the square root of the average number of nodes, V479.4 x 21.9. This is compared to setting the number of hubs as Nv. = VN, dynamically, according graph size. (3) Reassigning spokes to hubs at each layer keeping the same connections fixed across the layers, is shown to improve performance. (4) Including an encoding layer for the spokes prior to aggregation further improves performance.
We provide additional experiments for varying values of hubs ratios and k in Appendix A.4
Assignment of spokes and hubs.
The clustering into hubs and assignment to spokes are crucial components of ReHuub' architecture. The ( illustrates how different clustering and assignment strategies affect ReHub, by evaluating
ablation in Table on PascalVOC-SP. We identify three key constraints that any assignment strategy should satisly: (1) each spoke must be assigned to exactly k hubs, (2) no hub should appear more than once in a spoke's assign- ments, and (3) the number of spokes assigned to each hub should be approximately balanced. We therefore devise two baseline strategies to compare against our feature similarity based strategy: Random and Bal- anced Random. The Random strategy assigns to each spoke l hubs sampled uniformly at random without replacement. While this ensures each spoke has exactly k unique hubs, it does not guarantee balanced distribution of spokes across hubs, and only approaches balance asymptotically for very large graphs. To address this, we propose the Balanced Random strategy, which enforces balance while maintaining some degree of randomness. This assignment task inherently involves a tradc-off between computational complex- ity, randomness, and balance: achieving perfect balance with full randommess is compulationally expensive, while a fully random assignment is efficient but unbalanced. The Balanced Random strategy trades off some randomness to achieve approximate balance with lincar complexity. Specifically, we begin by randomly permuting the hub indices O...., N₁ 1, and for each spoke with index i, assign the consecutive hubs positions (i- u + j) mod N₁, for j = 0, ..... k- 1, where is integer coprime with Nr. This construction
10

---

Published in Transactions on Machine Learning Research (08/2025)
Table 5: Ablation study of spoke-hub assignment strategies. We analyze the impact of various strategies for hub clustering, initial hub assignment, and hub reassignment on ReHub's performance using the POC-SI dataset. Accordingly, the results are grouped into three categories, with ReHub's performance reported at the bottom. The clustering methods include random, balanced random, and METIS. For hub assignment and reassignment, we evaluate random, balanced random, feature similarity-base assignment, and no reassignment. Reassignment based on Attention Scores is as described in Section 3.4 We use = 3 for all runs. Our findings show that neither of the random strategies improve the results and actually degrade performance. This further supports our contention that our feature similarity based strategy leverages meaningful spoke-hub hub relationships.
Clustering
Hubs Assignment
Reassignment
PascalVOC-SP (FI f)
Random Balanced Random
Features Similarity
Attention Scores
0.3503 + 0.0143
Features Similarity
Attention Scores
0.3622 = 0.0060
METIS
Features Similarity
Attention Scores
0.3860 + 0.0172
METIS
Random
Attention Scores
0.3619 + 0.0083
METIS
Balanced Random
Attention Scores
0.3618 = 0.0126
METIS
Features Similarity
Attention Scores
0.3860 = 0.0172
METIS
Features Similarity
No Reassignment
0.3775 + 0.0040
METIS
Features Similarity
Random
0.3514 + 0.0121
METIS
Features Similarity
Balanced Random
0.3486 = 0.0106
METIS
Features Similarity
Attention Scores
0.3860 + 0.0172
preserves partial randomness, guarantees lt unique hubs per spoke, and distributes spokes evenly across hubs. For implementation details, see Appendix A.3
We evaluate both random assignment strategics in three modules: (1) Clustering, as defined in Section 3.3 is used for hub feature aggregation and can be performed randomly or in a balanced random manner, both following the same algorithmic logic described above with k 1. This is compared against METIS, which is the clustering strategy used by ReHub; results are shown in rows 1-3 of Table 5 (2) Initial Hub Assignment is evaluated on random and balanced random strategies, and also compared against ReHub's strategy that assigns hubs based on feature similarity. Results are shown in rows 4-6 of Table 5 (3) Reassignment can
be cither disabled, performed randomly, balanced randomly, or with the attention score based mothod as described Section 3.4 Results are shown in rows 7-10 of Table
Our findings show that both random strategies degrade performance, further supporting the contention that our feature similarity based strategy leverages meaningful spoke-hub relationships.
Hub utilization.
To gain insights into the reassignment dynamics, we measure the level of hub utilization. We define hub utilization U as the number of hubs that have at least one spoke connected to them. Formally, U ii E.i, IN, 2 t}1 where E.s,. represents the set of all spokes connected to hub én The percentage of used hubs is then given by U/Ne, which reflects the proportion of hubs that are connected at least one spoke. Figure 3 shows histograms of hub utilization across graphs, where the X-axis represents the percentage of used hubs (in bins of size 10), and the Y-axis represents the percentage of graphs falling into each bin Separate histograms are shown for each layer (Layers 1-4) and for different configurations of hub ratio r and connected hubs k based on the validation split of the Pascal dataset. The results demonst rate that in the vast majority of graphs, nearly all hubs are utilized across all layers, with the peak typically near 90%-100% usage. This finding suggests that the network maintains robust information flow between spokes and hubs, regardless of the number of hubs or the number of spokes per hub. We also present an additional metric based the Bhattacharyya coefficient in Appendix A.4
11

---

Published in Transactions on Machine Learning Research (08/2025)
r= k=
r= 4, k=
r=1,k=5
r= k=5
100
% of Graphs
10
8
x
@
8
8
100
100
100
100
Used Hubs %
Used Hubs %
Used Hubs %
Used Hubs %
Layer 1
Layer 2
Layer 3
Layer 4
Figure 3: Hub utilization. Histogram of used hub percentages across graphs in the Pascal valida- tion set, for different configurations of hub ralio and number of connected hubs k. Each subplot shows hub utilization across four layers. Percentages grouped using bins of size 10%. Nearly all hubs are utilized across all layers, with the peak typically near 90%-100% usage.
5 Conclusion and future work
In this paper, we introduced ReHub, a novel graph transformer architecture designed to enhance long-range range communication in large graphs through dynamic reassignment of virtual nodes. This approach facilitates efficient information passage, enabling effective learning on large graphs while maintaining linear compu- tational complexity and reduced memory usage compared existing methods. Our experimental results demonstrate that Rellub consistently outperforms Neural Atoms and ranks among the top two methods against various baselines. It achieves competitive accuracy compared to Exphormer with lower memory con- sumption across all evaluated scenarios. ReHub achieves its efficiency through proposed reassignment mechanism, which maintains sparse spokc-hub conncetivity, as highlighted by our ablation studies. The modular design of ReHub allows for easy integration with various MPNNs.
Future work While consistently improving computational efficiency, our spoke- communication main- tainod strong performance, ostablishing foundation for future works. Additionally, our current design lacks inherent support for positional information available in geometric graphs. In future work, we aim to extend method to support tasks requiring long-range communication positional information into the spoke-hub attention and reassignment mechanisms. We also plan to make the reassignment module learnable, and optimize it towards the prediction task to further boost accuracy. Finally, integrating ReHub into architectures like Exphormer to enable the reassignment of expander graph edges between layers presents a promising direction to further enhance long-range communication.
geometric graphs by incorporating
References
Noga Alon.
Eigenvalues and expanders. Combinatorica, 6(2):83-90 96, 1986.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.0522 05200. 2020.
Ali Behrouz and Farnoosh Hashemi. Graph mamba: Towards learning on graphs with state space models. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 119 119-130, 2024.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv:1711.07558. 2017.
12

---

Published in Transactions on Machine Learning Research (08/2025)
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv:2105.1449) 2021.
arXiv preprint
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph trans- former. In International Conference on Machine Learning, pp.
PMLR, 2023.
Kaidi Cao, Mangpo Phothilimthana, Sami Abu-El-Haija, Dustin Zelle, Yanqi Zhou, Charith Mendis, Jure Leskovee, and Bryan Perozzi. Learning large graph property prediction via graph segment training. Advances in Neural Information Processing Systems, 36, 2024.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. arXiv preprint arXiv:2206.04910 2022.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pp. 1725-1735. PMLR, 2020.
Krzysztof Choromanski, Valerii Likhoshersoov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint EXXiv:200.147790 2020.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344-16359, 2022.
Keyu Duan, Zirui Liu, Peihao Wang, Wenqing Zheng, Kaixiong Zhou, Tianlong Chen, Xia Hu, and Zhangyang Wang. A comprehensive study on large-scale graph training: Benchmarking and rethinking. Advances in Neural Information Processing Systems, 35:5376-5535 5389, 2022.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks graphs. arXiv preprint arXiv:2012.09699 2020.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326 22340, 2022.
Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. Ver-graphormer: A mini-batch graph transformer via virtual connections. arXiv preprint arXiv:2403.16032 2024.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263 1272. PMLR, 2017.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
Aric A. Hagberg, Daniel A. Schult, Picter Swart, and JM Hagberg. Exploring network structure, dynamics, and function using networkx. Proceedings of the Python in Science Conference, 2008. URL litps:: /api.
semanticscholar.org// Cotp:r//CCCoooss:110000000
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv:1905.122 12265, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datascts for machine lcarning on graphs. Advances in neural information processing systems, 33:22118 22133, 2020.
EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis of virtual nodes in graph neural networks for link prediction. Tn The First Learning on Graphs Conference, 2022.
13

---

Published in Transactions on Machine Learning Research (08/2025)
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):3559335) 392, 1998.
Jeong Han Kim and Van H Vu. Generating random regular graphs. In Proceedings of the thirty-fifth anmual ACM symposium on Theory of computing, pp. 213-222, 2003.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.0220 02907, 2016.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34: 21618-21629, 2021.
Xuan Li, Zhanke Zhou, Jiangchao Yao, Yu Rong, Lu Zhang, and Bo Han. Neural atoms: Propagating longerange interaction in molecular graphs through efficient communication channel. In The Twelfth International Conference on Learning Representations, 2024.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers.
arXiv preprint arXiv:2302.04181, 2023.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501 14515, 2022.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint #xXiv:1811.05865, 2018.
Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey. arXiv preprint arXiv:2407.09777 2024.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Ex- phormer: Sparse transformers for graphs. In International Conference on Machine Learning, pp. 31613- 31632. PMLR, 2023.
Angelika Steger and Nicholas Wormald. Generating random regular graphs quickly. Combinatorics, Probability and Computing, 8(4):377 396, 1999.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:211..14522. 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Pelar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, el al. Graph attention networks. stat, 1050(20):10 (0000)0):0-455000 48550, 2017.
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXiv:2402.00788) 2024.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35: 27387-27401, 2022.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nic, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36, 2024.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey graph neural networks. IEFE transactions on neural networks and learning systems, 32(1):: 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks?
arXiv preprint arXiv:1810.00826, 2018.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-2888 28888, 2021.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Onlanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances neural information processing systems, 33:17283-172991
2020.
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. arXiv preprint arXiv:2110.13088 13.994 2021.
15

---

Published in Transactions on Machine Learning Research (08/2025)
A Appendix
A.1 Datasets
In Tables D and we summarics the details of the datasets used for evaluation.
Table 6: Statistics of the five dataset proposed in the long-range range graph benchmark. Source: LRGB (wwivedi
al.
2022
Total Graphs
Total Nodes
Avg Nodes
Mean Deg.
Total Edges
Avg Edges
Avg Short.Path.
Avg Diameter
Dataset
PascalVOC-SP
11,355
5, 5,443,545
479.40
5.65
30,777,44 444
2,710.48
10.74:0.55
77.62222.11 13
COCD-SP
123,286
68,793.216
476.88
5.65
332,091,900
2,693.67
00.56
27.89++2.14
PCQM-Contact
629,434
18,955,687
30.14
2.03
32,341,644
61.09
9.86+1.79
Pept:ides-fune
15,535
2,344,859
150.94
2.04
4,773.974
307.30
20.89419.79
56.99422877
Peptides-struct
15,535
2,344,859
150.94
2.04
4,773,974
307.30
20.80499.9
56.99112.772
Table 7: Dataset statistics of LRGB, OGBN-Arxiv and Coauthor Physics.
Source: Exphormer
Shirzad
et al.
2023
Dataset
Graphs
Avg. nodes
Avg. edges
Prediction Level
No. Classes
Metric
PascalVOC-SP
11,355
479.4
2,710.5
inductive node
21
F1 MRR
COCO-SP
123,286
476.9
2,693.7
inductive node
81
PCQM-Contact
5299.334
30.1
61.0
inductive link
(link ranking) (regression)
Pept-ides-
15.535
150.9
307.3
graph
Average Precision
Peptidea-struct
15,535
150.9
307.3
gruph
Mean Absolute Error
-OBN-Arxiv
169.343
1,166.243
node
40
Accuracy
Coauthor Physics
34493
247962
Accuracy
16

---

Published in Transactions on Machine Learning Research (08/2025)
A.2 Hyperparameters
Long-range graph benchmark. In the experiments done the datasets: Peplides-fune, Peplides-strucl and CCQU-CContct we follow the hyperparameters of Neural Atoms (Li et al., 2024). For other datasets we follow the hyperparameters of Exphormer (Shirzad et al. 2023 Althongh we follow the hyperparamoters configurations, there may be subtle changes due to the difference in architecture.
In Tables we provide the hyperparameters used in our experiments.
Table 8: Hyperparameters for the LRGB datasets used for evaluation. For Peptides-func, Peptides-struct and PCQM-Contact some of the hyperparameters are model-specific and presented in additional tables.
Hyperparameter
PCQM-Contact
Peptides-func Peptides-struct PascalVOC-SP
Dropout
0
0.12
0.2
0.15
Attention dropout
0.2
0.2
0.2
0.2
Positional Encoding
LapPE-10
LapPE-10 16
LapPE-10
LapPE-10
PE Dim
16
20
16
PE Layers
2
2
2
2
PE Encoder
DeepSet
DeepSet
DeepSet
DeepSet
Batch size
256
128
128
32
Learning Rate
0.0003
0.0003
0.0003
0.0005
Weight Decay
0
0
0
0
Warmup Epochs
10
10
10
10
Optimizer
AdamW
AdamW 200
AdamW 200
AdamW
# Epochs
200
300
MPNN
GatedGCN
# Layers
4
Hidden Dim
96
# Heads
Hubs Ratio
k
# Params
590,051
Table 9: Modcl-specific hyperparameters for PCQM-Contact, and the number of model parameters.
Hyperparameter
# Layers
Hidden Dim
# Heads
Hubs Ratio
k
# Params
GCN
300
1
1
3
5,127,544
GCNII
100
1
3
287,240
GINE
100
3
638,240
GatedGCN
72
1
3
655,992
Table 10: Model-specific hyperparameterss for Peptides-fune, and the number of model parameters.
Hyperparameter # Layers
Hidden Dim
# Heads
Hubs Ratio
k
# Params
GCN
155
0.5
3
1,372,563
GCNIL
88
1
0.5
3
452,204
GINE
88
2
0.5
3
491,804
GaledGCN
88
0.5
3
611,044
17

---

Published in Transactions on Machine Learning Research (08/2025)
Table 11: speelfspecific hyperparameters for Peptides-struct, and the number of model parameters.
Hyperrparameter # Layers
Hidden Dim
#
Heads
Hubs Ratio
# Params
GCN
5
155
0.5
1,376,382
GCNII
88
1
0.5
453,152
GINE
5
88
2
0.5
492,752
GatedGCN
5
88
1
0.5
3
611,992
Large random regular graph. In Table 12 we provide the hyperparameters used in our experiments. The same configuration of hyperparameters is used for experiments except for modcl-specific parameters.
Note that although Exphormer does not utilize its expander graph algorithm here the * "Add edge index" hyperparameter enabled and sets the graph edges the expander edges, Due to the regularity of the graph, i.e. having degree of d = 3 for all nodes, the same linear complexity is imposed.
Table 12: Hyperparameters for the forward pass of the large random regular graph dataset for all the models, including the model-specith configuration.
Hyperparameter
Large Random Regular Graph Exphormer
ReHub
MPNN
GCN
# Layers
3
Hidden Dim
52
# Heads
4
Add edge index
True
Num Virtual Nodes
Hubs Ratio
k
OGBN-Arxiv and Coauthor Physics. For OGBN-Arxiv and Coauthor Physics we follow the hyper-
parameters of Exphormer (Shirzad al.) (023), adding our configuration of hubs ratio and k. In Table 13 we provide the hyperparameters used in our experiments.
Table 13:
Hyperparamoters for OGBN-Arxiv and Coauthor Physics datasets used for evaluation, and the number of model parameters.
Hyperparameler
OGBN-Arxiv Physics
Dropout
0.3
0.4
Attention dropout
0.2
0.8
Learning Rate
0.001
Weight Decay
0.001
0.001
Warmup Epochs
Optimizer
AdamnW
AdamW
# Epochs
MPNN
GCN
GCN
# Layers
Hidden Dim
80
72
# Heads
Hubs Ratio
# Params
2-40,24
850,281
18

---

Published in Transactions on Machine Learning Research (08/2025)
A.3 Implementation details
In the following we describe in more detail how the architecture is implemented.
We use the open-source code provided by GraphGPS (Rampášek et al. 2022) and available on https:// caaiiii.cco//mapaskkee /araaapaek//GrapGPPSSSS GraphGPS We merge into that code parts from Exphormer (Shirzad et al. 2023) which are relevant for the training and evaluation of the OGBN-Arxiv and Coauthor Physics dalasets.
Clustering. During preprocessing we use the METIS partitioning algorithm (Karypis & Kumar 1998 to divide each graph to clusters according to the required number of hubs. In practice, we use the python wrapper PyMetis Rl which allows to map each spoke to single hub. According to the METIS paper [Karypis & Kumar 1998), this clustering step runs in approximately O(N + M) time and requires only O(N) additional memory beyond the input graph, for a graph with N nodes and M edges, For graphs where M = O(N), as in many practical cases, both the runtime and the additional memory simplify to O(N). The clustering is implemented as a modular preprocessing stage and can, in principle, be replaced with any other clustering algorithm without affecting the overall ReHub framework.
Hub features. Throughout the implementation we use sparse data structures that allows to keep the complexity linear even when rumming on multiple graphs simultaneously (é.e. in batch). The hubs are stored in similar fashion to how spokes are stored in a batch. i.e. the features are kept in a 2D matrix #Graphs}N indicating which graph cach
X E Nxd together with a 1D graph index matrix B E node belongs lo, where N is the nunber of nodes in the whole batch.
When aggregating the spokes to calculate hub features we use the scatter functions which allows us to aggregate the spokes to two matrices. (1) 2D matrix H R and (2) a 1D graph index matrix Bu E (0...., :...,:#rraphe #Graphs) indicating which graph each hub belongs to, where H is the number of hubs in the whole batch.
Hub assignment and reassignment. Note that the initial hub assignment is implemented identically to the reassignment algorithm but with iz set to the initial hub found in the clustering step.
Attention. Opposed to other transformer architectures which require the conversion of the spokes to a dense representation, we can keep both spokes and hubs in their sparse representation. For each attention module we use GATv2Conv implementation provided in pytorch geometric which accept as input this type of sparse representation. Moreover, this implementation accept as input bipartite graphs and here use it to pass information between the graph of spokes and graph of hubs.
Large random regular graph. As mention in Section 4.2 we would like to construct graphs of arbitrary size. To achieve this, we generate a dataset of large random regular graphs, which can be produced at any scale while ensuring connectivity between nodes (i.e. avoiding isolated subgraphs) due to the regularity property, i.e. A d-regular graph is a graph where each node has number of neighbors. To do that we use the random_ random_regular. www.rrrrggaaapppeeeeeeeeer NetworkX library (Hagberg et al. 2008), which takes as an input the number of nodes to be constructed and the degree of each node d. Additionally, to ensure compatibility with the models, we assign random values to the graph's edge attributes, node features, and prediction labels.
(Kim & Vu 20033 Steger & Wormald, 1999) function from the open-source
Peak memory usage. To sample the peak memory usage of the models we use the function torch. cuda. max www.eeeeealeeeeeeeeeeeeee This function returns the peak memory allocation since running the torch. rww..reset.t.e.eeeeeeeeeeeeeeeee reset_pttppee peak memory_mmrrreeeeeee _sstts function, which we call just before the call to the model.
httpss//gthhbb.ccm///nerr/////pp
19

---

Published in Transactions on Machine Learning Research (08/2025)
Balanced random assignment. In Section 4.3 and Table 5 present ablation study of the spoke- hub assignment components. Specifically, we discuss a balanced random assignment, strategy that balances the number of spokes assigned to each hub while keeping the number of hubs assigned to each spoke strictly equal to This strategy ensures per-spoke uniqueness and global balance, at the cost of introducing some structure inlo the randomness. Given N₂ hubs and N, spokes, we first sample a uniform random permutation x of the hub indices (O..... -1) We then choose random stride E {1,..., NN-1] such that ged N/) = 1, ensuring full cycle through the hubs. For each spoke i (0,...,,N, N,,1), we assign it l distinct hubs with indices
B 1 [(i 5) mod Nol: 0 k-
By construction, each spoke assigned exactly distinct hubs, and each hub is assigned approximately the same number of spokes. The partial randomness of and ensures diversity of assignments, while the cyclic structure maintains balanced and distinct connections per spoke.
Algorithm Balanced Random Assignment of Hubs
Require: Number of hubs Na, number of spokes N,, number of hubs per spoke k
Sample a random permutation т of {0, , N4-1} Sample a random stride u E fl,..., Nº, 11] such that ged(u, N1.) = 1
for = to N, do for to k- do Eij - m(i u + mod No] end for end for return Assignment matrix E
Why is it important for u to be coprime with N₂ Tf u and N₁ are coprime, then the sequence of values (i u) mod N for i = 0, I. - 1 forms a permutation of {0, I...., N - 1}. That is, each value in the sequence appears exactly once before the sequence repeats. To see this, suppose (i-u) mod N = (j-u) mod for some 0 & < jj < N. Then (j - i) u is a multiple of N, but since u and N are coprime, j - i must be multiple of N. However, < j - N, contradiction. Hence all N values are distinct, and since they all lie in ( 1}, they must form permutation of this set.. This property ensures that all hubs are used evenly.
20

---

Published in Transactions on Machine Learning Research (08/2025)
A.4 Additional ablations
Long-range spoke update layer components. In addition to the result shown for POSCaIVOC-SP
presented in Section 4.3 we provide in Table 14 the same components analysis for Peptides-func
Table 14: Ablation study. We measure the effect of various components of ReHub on top of GatedGCN MPNN, using the Peptides-fune dataset. 'hee number of hubs used per graph (#Hubs): for 22 it static amount and for vN, it is dynamic per graph size. Initial hubs (Hubs Init) can be set as lcarned parameters or initialized from the assigned spokes as described in 3.3 where can add feedforward layer on the spokes (Spokes Enc) before aggregation. Reassignment is as described in 3.4 We use h = 3 for all runs.
GNN
#Hubs
Hubs Init
Spokes Enc
Reassignment
Peptides-fune (AP 7)
0.5864 + 0.0077
12
Learned (As Neural Atoms)
0.5738 + 0.0027
12
Cluster Mean
0.6626 + 0.0068
V..
Cluster Mean
0.6616 + 0.0063
V.
Cluster Mean
0.6661 + 0.0062
Cluster Mean
0.6612 + 0.0068
V
Cluster Mean
0.6683 + 0.0069
Sensitivity to hubs ratio For ReHub, practical guideline for selecting the hubs ratio and & is 1 and k = 3. Figure g presents an ablation study on these parameters for the Peptides-func and PascalVOC-SP datasets.
For Peptides-func the best results are achioved with a hubs ratio 0.5 for both = 3 and 5, which may attributed to the small graph sizes and the potential tendency to overfit on such datasets. On average, each graph contains approximately 150 nodes, resulting in roughly hubs. Furthermore, it notable that for other hubs ratio values, the results remain consistent, with an average performance between AP 0.66 and AP = 0.67, indicating the robustness of our method.
For PascalVOC-SP, which includes larger graphs with an average of approximately 500 nodes per graph, a different trend observed compared to Peptides-fune. Specifically, for varying values of k, the optimal performance achieved with different hubs ratios. However, the performance variation outside the optimal hubs ratio is relatively minor, with the best results obtained when r = 1 and k 3.
PascalVOC-SP Test Result Score)
PascalVOC-SP Test Result vs Hubs-Ratio
Peptided- Test Result vs Hubs-Ratio
0.42
Peptided-Fumm Fanod---ncco Test Result (AP)
K
Km5
K=3
0.69
K=3
0.40
0.68
0.38
0.67
0.66
0.36
0.65
0.64
0.34
0.63
0.32
1.0
4.5
0.62
2.0
5.0
Rabs-Ratio
Hubs-Ratio
Figure 4: Results for various hubs ratio and k, which is the number of hubs each spoke is connected to. We shown this on PascalVOC-SP (Left) and Peptides-fume (Right) datasets with k [3,5] and |0.5, 2,4,,
21

---

Published in Transactions on Machine Learning Research (08/2025)
Bhattacharyya Coefficient Uniform Distribution The Bhattacharyya Coefficient for discrete probability distributions P and Q is measurement, of how similar the two probability distributions are. It is defined as:
BC(P,Q)= Σ (()))(z)) ZEX
BC(P, Q) lies between 0 and 1, where the higher the coefficient the more similar the distributions are. our setup, P the distribution over spokes connection per hub; i.e. it is the number of spokes connected to each hub, divided by the overall number of connections from spokes hubs (so that the result is indeed a probability distribution). We then set. Q be the uniform distribution, i.e. 1/N₂ for each hub. By doing so, see how close the actual distribution P is to the uniform distribution, where uniform indicates the optimal balanced assigument of spokes to hub where every hub has exactly the samn number of spokes. For convenience, we define the Bhattacharyya Percentage as the Bhattacharyya Coefficient multiplied by 100.
In Figure 5 we present a graph illustrating the percentage of graphs with a Bhattacharyya Percentage below a given threshold for the PascalVOC-SP dataset. As in Section 1.3 this is shown for each layer, and for varying values of hubs ratios and k on the validation split of the dataset. The results demonstrate that regardless of the number of hub and number of hubs per spoke, most graphs have Bhattacharyya Percentage above 80%. This suggests that our reassignment method spreads nodes quite evenly across the various hubs, and does not create high concentration of spokes which remain connected to only few hubs.
Bhattacharyya Distribution, k=3
Bhattacharyya Distribution, k=5
100
1= k=3
100
r=1, k=5
Cumulative % Graphs
Layer 1, AUC-1.81
Cumulative % Graphs
Layer 1, AUC=1.41
80
Layer 2, AUCC9.04
Layer 2. AUC=5.76
Layer 3, AUC-12.34
Layer 3, AUC-8.27
Layer AUC==13.70
Layer AUC=14.01
60
r=4, k=3
60
r=4, k=5
Layer AUA-AUC--.
Layer AUC-1.55
40
Layer
Layer AUC=8.63
Layer 3, AU1-10.5
Layer AUC=11.72
Layer 4, A39993.99
Layer 4, A4C-
20
0
20
40
60
100
0
20
40
60
80
100
Bhattacharyya %
Bhattacharyya %
Figure 5: Percentage of graphs with a Bhattacharyya Percentage below a given threshold for the validation split of the PascalVOC-SP dataset. Results are shown for varying and hubs ratio r. Left: & with (1, 4}. Right: with (1,4).
22


Reviews:
[{"review_id": "rjS8Mc2gjF", "reviewer": "Reviewer_9vge", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The paper is clearly written and easy to follow.\n- The method is conceptually simple and well-motivated.\n- Compared to Neural Atoms, ReHub is both simpler and better performing, showing that sparse hub assignments and averaged hub initialization can be effective design choices.\n\n---\n\n### Weaknesses\n- While the method performs well, it does not outperform other recent linear graph transformers such as **Exphormer**, which somewhat limits the strength of the empirical contribution.\n- The **hub reassignment strategy**, which is central to the method’s claimed novelty, is not well justified or thoroughly evaluated. It is only briefly discussed in the ablation study, and it remains unclear how much it contributes to the overall performance.\n- The initial **clustering step** (e.g., k-means) is also treated as fixed, and it is unclear whether a simpler, more efficient alternative (e.g., random partitioning) would suffice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Summary\n\n**ReHub** is a linear-time graph transformer that introduces virtual nodes (hubs), initialized as cluster centroids of the input graph. The model alternates between spoke-to-hub cross-attention and hub-to-hub self-attention. Its main novelties over prior work (Neural Atoms) are:  \n1. **Sparse and dynamic spoke-to-hub assignment**: Each spoke (node) attends to only a small subset of hubs, with the assignment dynamically recomputed at each layer based on hub-hub similarity.  \n2. **Non-learned hub initialization**: Hubs are initialized by simply averaging the features of their assigned spokes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Requested Changes\n\nI would like to see a more thorough discussion and empirical evaluation of the hub (re)assignment strategy, as it is central to the method’s novelty. Specifically:\n\n1. **Reassignment alternatives**: Please include experiments comparing the learned similarity-based reassignment to simpler alternatives — for example, *random* hub reassignment at each layer, while ensuring *load balancing* (i.e., each hub is assigned approximately $\\frac{k N_s}{N_h}$ spokes). This would help determine whether the similarity-based assignment is truly beneficial, or if any form of reassignment suffices to improve information flow.\n\n2. **Clustering at initialization**: Similarly, please evaluate the necessity of the k-means clustering used to initialize hubs. Can a *random but balanced* partitioning of nodes into hubs yield similar performance? If so, this could reduce preprocessing cost and simplify implementation further.\n\nThese additions would strengthen the paper by clarifying which parts of the design are truly necessary for performance and which are incidental or replaceable.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ukoSjh4MxG", "reviewer": "Reviewer_KC3j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Paper is generally well written.\n- The method is innovative.\n- ReHub performs similarly to SOTA methods while utilizing less memory and compute time.\n\n### Weaknesses\n- Some parts of the text lack clarity (see requested changes below).\n- The experimental sections is lacking some details to insure fair comparison between methods (see requested changes below).\n- While the method is interesting, its impact is somewhat limited. ReHub outperforms Neural Atoms but does not quite reach the accuracy of Exphormer.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel graph transformer architecture ReHub. ReHub utilizes virtual nodes to avoid the common oversmoothing and oversquashing issues in GNNs, this is similar to prior work such as Neural Atoms [1]. However, unlike other works utilizing virtual nodes, ReHub maintains linear complexity with respect to the number of nodes, enabling this method to scale much better to large graphs. ReHub achieves this by dynamically setting the number of virtual nodes for each graph to be $\\sqrt N$ (where $N$ is the total number of nodes in the graph) and only connects each node in the graph to a small constant number of virtual nodes $k$. The model also relies on a hub reassignment step, which changes the connectivity between the graph nodes (spokes) and the virtual nodes (hubs) after every layer based on the distance between their features, this better leverages the features of each hub. The authors test their method on long range graph benchmarks, showing that ReHub is modular and can be used effectively with a variety of GNN architecture, and that it outperforms NeuralAtoms. ReHub is also compared to other graph transformer architectures and achieves competitive results. Lastly, the authors show that their method achieves lower peak memory consumption than other graph transformer architectures and they conduct an ablation to show the usefulness of each ReHub component.\n\n[1] Xuan Li, Zhanke Zhou, Jiangchao Yao, Yu Rong, Lu Zhang, and Bo Han. Neural atoms: Propagating\nlong-range interaction in molecular graphs through efficient communication channel. In The Twelfth\nInternational Conference on Learning Representations, 2024.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The complexity of the clustering also needs to be discussed in my opinion since it is a required step for each new graph being analyzed.\n- Where are the performance numbers for the other methods coming from? Did the authors implement all the baselines methods on the considered benchmarks or were the numbers taken directly from past works? If the methods were tested by the authors directly then how did the authors make sure the comparison is fair in terms of choosing the best hyper-parameters for each method (lr, num epochs, etc. etc.)? If the numbers were taken directly from past works then the exact references need to be specified, i.e. which number was taken from which paper?\n- Similar to the above point, for a fair comparison between methods it would also be important to note the number of trainable parameters since, for example, ReHub contains other modules (eg. the feature embedding layer for the hub initialization) which other methods do not.\n- Last sentence of the second to last paragraph of the intro needs to be re-written \"In order to so and yet...\"\n- Fig 1 Caption \"(3) Hub (Re)Assignment. A spoke connected to...\"  is extremely confusing and should be re-written for clarity.\n- Fig 3 is hard to interpret, from a quick glance I initially got the impression that the hubs were highly un-utilized. Maybe a histogram of count or % of graphs (y axis) for each % Unused Hubs (bins, x axis) would be clearer, although multiple histograms might be necessary (one per layer for example).", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nLQHexgv3V", "reviewer": "Reviewer_HPXK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper demonstrates that integrating the ReHub mechanism with standard GCN backbones yields competitive performance across benchmark datasets.\n2. The figures in the paper illustrate the reduction in space complexity.\n3. The paper includes thorough ablation studies and dataset/model statistics.\n4. The writing is clear, well-organized, and easy to follow.\n\nWeaknesses and Suggestions\n1. In Figure 1, Part (4) is intuitive, but Part (1) is hard to understand -- H and S rectangles appear the same size, so readers may assume that they have equal node counts. I suggest using a similar graph of part (4) to replace S2H, showing message passing from the large S graph to the small H graph. Then, replace H2H as the attention of the small H graph and replace H2S as a message passing from the small H graph to the large S graph. This would clearly convey that attention is computed only over the small H graph. This adjustment obviously depicts that attention is only computed over the small H graph instead of the large S graph, effectively highlighting your main innovation.\n\n2. In the first paragraph of Section 4.3, it would be helpful to explicitly state that the experiments involve the PascalVOC-SP dataset, which contains an average of 479.4 nodes per graph. Initially, I was confused by the mention of only 22 hubs until I cross-referenced Table 4 and Appendix A1 to confirm the graph sizes. Including this context earlier would improve the reader’s understanding.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces ReHub, a novel graph transformer architecture designed to handle large graphs with linear time complexity. The key idea is to use a small set of hub nodes to reduce attention complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Suggestions", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)