REVIEW 3 major objections 5 minor 21 references
ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read ReHub claims that a graph transformer can carry long-range information across large graphs in linear time and memory, matching the accuracy of a dense hub-based model by having each node attend to only a small constant number of virtual…
desk verdict ReHub is a genuine efficiency contribution to virtual-node graph transformers, with a new per-layer hub reassignment mechanism and a mostly sound experimental core, but the hub-hub similarity proxy needs direct validation and one LRGB dataset is missing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the hub assignment matrix $E\in\{0,1\}^{N_s\times N_h}$ with exactly $k$ ones per row, together with Algorithm 1's reassignment rule: use the attention-score matrix $\Gamma$ from the hubs-to-spokes step to find the spoke's best hub $i_h^*$, then set the spoke's connections to the bottom-$k$ hubs in the hub-hub distance matrix $\Delta$. This replaces the expensive per-spoke top-$k$ over all hubs with a per-hub bottom-$k$ computed once for all spokes, keeping reassignment at $O(N_s k + N_h^2)$ and letting every hub stay in use across layers.
What would settle it
Run ReHub on a mid-size graph (e.g., Peptides-func) and replace Algorithm 1's reassignment with the exact top-$k$ hubs per spoke computed from full spoke-hub attention scores, keeping all other hyperparameters fixed; if the exact reassignment clearly outperforms ReHub's hub-hub proxy, the proxy is the limiting factor. Alternatively, on a graph where hub features are clustered but spoke communities are disjoint, measure hub utilization and validation accuracy after the proxy reassignment to see whether spokes are routed to irrelevant hubs.
Extended reading notes
Core claim
The paper argues that the bottleneck in hub-based graph transformers is not the number of hubs but the number of hub connections per spoke. Because spoke-hub attention costs $O(N_s k)$ and hub-hub self-attention costs $O(N_h^2)$, choosing $N_h = O(\sqrt{N_s})$ and $k = O(1)$ yields linear complexity. The reassignment step then makes all hubs usable: each spoke first identifies its most-attended hub from the sparse attention matrix $\Gamma$, then replaces its remaining $k-1$ connections with that hub's nearest neighbors in hub-feature space, computed from the cheap hub-hub distance matrix $\Delta$. The paper shows empirically that this sparse scheme matches its dense counterpart, ranks among the top two methods on LRGB tasks, and uses less memory than Exphormer on large graphs.
Load-bearing premise
The method assumes that the hubs closest to a spoke's current best hub, in hub-feature space, are also the hubs most useful to that spoke, so hub-hub distance can stand in for spoke-hub relevance without computing spoke-hub similarities.
Editorial extensions
If this is right
- With $N_h = O(\sqrt{N_s})$ and $k = O(1)$, ReHub scales linearly in the number of nodes, in both time and memory.
- The sparse model's accuracy matches its dense fully connected variant, so the reassignment recovers the information that dense hub attention would provide.
- ReHub plugs into standard MPNNs (GCN, GCNII, GINE, GatedGCN) and improves each one's long-range benchmark results over Neural Atoms.
- Memory usage stays linear up to graphs of hundreds of thousands of nodes, with peak memory below that of GraphGPS and Exphormer.
- The reassignment keeps nearly all hubs utilized across layers, so the sparse connectivity does not starve any virtual node of information.
Reading between the lines
- The hub-hub proxy is a form of approximate nearest-neighbor routing; on graphs whose communities occupy well-separated hub-feature regions it should concentrate traffic, but on graphs where similar hubs serve dissimilar spokes it may misroute, suggesting a learnable reassignment (which the paper lists as future work) as a natural fix.
- The dynamic reassignment resembles token routing in mixture-of-experts models; the reported hub-utilization histograms and Bhattacharyya coefficients suggest the load stays balanced, which would matter for distributed implementations.
- A direct extension would inject positional or geometric information into the hub-hub distance matrix, addressing the paper's acknowledged gap for geometric graphs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces ReHub, a graph transformer architecture in which each graph node (spoke) is connected to a small constant number k of virtual nodes (hubs), and the spoke-to-hub assignment is adaptively reassigned at every layer. To avoid the O(N_s * N_h) cost of exact spoke-hub similarity computation, the reassignment in Algorithm 1 selects, for each spoke, the k hubs closest (in hub-feature space) to the hub with the highest current attention score. The authors set N_h = O(sqrt(N_s)) and k = O(1), obtaining linear complexity in the number of nodes. Experiments on four LRGB datasets show that ReHub matches or outperforms its dense variant ReHub-FC, consistently improves over Neural Atoms, and ranks in the top two among baselines. Additional experiments on OGBN-Arxiv and Coauthor Physics and on synthetic graphs up to 700K nodes demonstrate reduced peak memory compared to Exphormer and Neural Atoms, with comparable accuracy.
Significance. If the claims hold, ReHub addresses a real limitation of virtual-node graph transformers: the trade-off between the number of hubs (which controls accuracy) and computational cost. The paper ships a clear complexity analysis, ablations of the main design choices, and a memory-scaling study on graphs up to 700K nodes. The sparse-dense parity is demonstrated on several benchmarks, and the improvement over Neural Atoms is consistent across MPNN backbones. The main weakness is that the efficiency-critical hub-hub similarity proxy is not validated against the exact spoke-hub assignment it approximates; the paper shows that reassignment helps and that random reassignment hurts, but it does not show that the proxy selects the hubs that an exact computation would select. This is the central risk to the paper's contribution.
major comments (3)
- [Section 3.4, Algorithm 1] The hub-hub similarity proxy that avoids the O(N_s * N_h) spoke-hub computation is the load-bearing approximation of the method, but the paper provides no comparison with the exact per-spoke top-k hub assignment. Table 5 shows that random reassignment degrades performance (F1 from 0.3860 to 0.3514), and Figures 3 and 5 demonstrate hub coverage and balance, neither of which establishes that the selected hubs are the informative ones. Since the central claim of sparse-dense parity depends on this reassignment rule, the authors should add a direct comparison on a small dataset (e.g., PascalVOC-SP, where N_s ~ 480 makes exact assignment feasible) between the hub-hub proxy and the exact assignment, and ideally also a variant that uses a learned or oracle assignment. This would confirm that the linear-time proxy does not sacrifice the performance of the ideal reassignment.
- [Section 3.4, 'Complexity' paragraph] The complexity analysis accounts for the Spokes-to-Hubs and Hubs-to-Hubs operations (O(N_s k) and O(N_h^2), respectively) but omits the cost of the reassignment step in Algorithm 1, which includes computing the N_h x N_h distance matrix Delta and the per-spoke selection. Under the stated regime N_h = O(sqrt(N_s)) and k = O(1), these costs are O(N_s) and thus preserve linear complexity, but the analysis should state this explicitly. The paper's central claim is linear complexity, so the formal derivation should cover every step of the layer.
- [Table 2 and Section 4.1] The LRGB evaluation reports results on four of the five LRGB datasets, omitting COCO-SP, which is part of the standard benchmark suite and is mentioned in Section 4.1 as one of the five datasets. The abstract's claim of ranking 'among top performers across various benchmarks' is supported by the four reported datasets, but reporting COCO-SP (or explicitly justifying its omission) would make the evaluation complete. In addition, the baseline numbers in Tables 1-2 are copied from prior publications rather than re-run in the same codebase; re-running at least Neural Atoms under the same hardware and training pipeline would strengthen the comparison, given that the improvement over Neural Atoms is a central claim.
minor comments (5)
- [Abstract] The notation 'O(n3/2)' should be written as 'O(n^{3/2})' for clarity.
- [Section 3.4, step (5)] The text says 'we retain the hub most similar to each spoke from the sparse set of connected hubs,' but the algorithm actually retains the hub with the maximum attention score Gamma, not necessarily the most similar in feature space. The wording should be aligned with the algorithm.
- [Section 4.3, Hub utilization] The definition of utilization, 'U = |{i_h | E_{:,i_h} . 1_{N_h} >= 1}|', has a dimension mismatch: E_{:,i_h} is an N_s-dimensional column vector, so the inner product with 1_{N_h} is not defined. It should be E_{:,i_h}^T 1_{N_s} (or equivalently the sum over spokes).
- [Section 4.2] There is a typo in 'GraphGPS (with vanila Transformer)' — 'vanila' should be 'vanilla'.
- [Section 3.3 and Appendix A.3] The complexity of the METIS preprocessing step is stated as O(N+M) in the appendix but is not mentioned in the main complexity analysis. Since METIS is a one-time preprocessing cost, it does not affect the per-layer linear complexity, but mentioning it in Section 3.4 would make the pipeline description complete.
Circularity Check
No significant circularity found; the complexity and performance claims are self-contained algorithmic and empirical results.
full rationale
The paper's central complexity claim (Section 3.4) is a direct operation count of its own sparse spoke-hub attention, hub self-attention, and reassignment routines: with N_h = O(sqrt N_s) and k = O(1), each per-layer step is O(N_s k + N_h^2) = O(N_s); this is a standard algorithmic derivation, not an input restated as a prediction. The performance claim ('sparse model achieves performance on par with its non-sparse counterpart') is an empirically reported comparison against the paper's own ReHub-FC variant and external LRGB baselines; no fitted parameter is defined in terms of the reported metric, and no load-bearing premise is justified by self-citation. The hub-hub similarity proxy in Algorithm 1 is a heuristic approximation to exact spoke-hub selection, and while it is the main correctness risk, it is not circular: the paper does not define the reassignment criterion in terms of the target performance, nor does it rename a known result as a new contribution. Accordingly, no circular step is exhibited.
Assumptions & free parameters
free parameters (2)
- hubs ratio r =
1 for most benchmarks; 0.5 for Peptides-func and Peptides-struct
- k (hubs per spoke) =
3 (ablations also use 5)
assumptions (3)
- domain assumption METIS clustering yields informative hub initializations and initial spoke-hub assignments.
- domain assumption Hub-hub feature distance is a sufficient proxy for spoke-hub relevance in the reassignment step.
- domain assumption Reported baselines from prior publications are reliable and comparable under the chosen hyperparameters.
Cite this review
Pith. "Pith review of ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment." pith.science (2026). https://pith.science/paper/ZMAOKVKL
@misc{pith2026241201519,
author = {Pith},
title = {Pith review of: ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZMAOKVKL}},
note = {Machine review of arXiv:2412.01519}
}
read the original 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 LRGB indicate a consistent improvement in results over the base method, Neural Atoms, while maintaining a linear complexity. Remarkably, our sparse model achieves performance on par with its non-sparse counterpart. Furthermore, ReHub outperforms competitive baselines and consistently ranks among top performers across various benchmarks.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[4]
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,
-
[7]
Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. Vcr-graphormer: A mini-batch graph transformer via virtual connections.arXiv preprint arXiv:2403.16030,
-
[8]
Mamba: Linear-time sequence modeling with selective state spaces.arXiv preprint arXiv:2312.00752,
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces.arXiv preprint arXiv:2312.00752,
-
[11]
Attending to graph transformers
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. arXiv preprint arXiv:2302.04181,
-
[12]
Pitfalls of graph neural network evaluation.arXiv preprint arXiv:1811.05868,
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation.arXiv preprint arXiv:1811.05868,
-
[15]
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces.arXiv preprint arXiv:2402.00789,
-
[16]
How powerful are graph neural networks? arXiv preprint arXiv:1810.00826,
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826,
-
[17]
Gophormer: Ego-graph transformer for node classification.arXiv preprint arXiv:2110.13094,
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification.arXiv preprint arXiv:2110.13094,
Show all 21 references
-
[21]
Additionally, to ensure compatibility with the models, we assign random values to the graph’s edge attributes, node features, and prediction labels
function from the open-source NetworkX library (Hagberg et al., 2008), which takes as an input the number of nodes to be constructed and the degree of each noded. Additionally, to ensure compatibility with the models, we assign random values to the graph’s edge attributes, nod...
2008
-
[1986]
On the bottleneck of graph neural networks and its practical implications.arXiv preprint arXiv:2006.05205,
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications.arXiv preprint arXiv:2006.05205,
2006 arXiv
-
[1998]
In practice, we use the python wrapper PyMetis4 which allows us to map each spoke to a single hub
to divide each graph to clusters according to the required number of hubs. In practice, we use the python wrapper PyMetis4 which allows us to map each spoke to a single hub. According to the METIS paper (Karypis & Kumar, 1998), this clustering step runs in approximatelyO(N +M ...
1998
-
[1999]
Understanding over-squashing and bottlenecks on graphs via curvature
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:2111.14522,
-
[2003]
Semi-supervised classification with graph convolutional networks.arXiv preprint arXiv:1609.02907,
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.arXiv preprint arXiv:1609.02907,
-
[2008]
semanticscholar.org/CorpusID:16050699
URL https://api. semanticscholar.org/CorpusID:16050699. 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.12265,
1905 arXiv
-
[2017]
How attentive are graph attention networks?arXiv preprint arXiv:2105.14491,
12 Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks?arXiv preprint arXiv:2105.14491,
-
[2018]
Graph transformers: A survey.arXiv preprint arXiv:2407.09777,
Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey.arXiv preprint arXiv:2407.09777,
-
[2020]
Rethinking attention with performers
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009.14794,
2009 arXiv
-
[2021]
Table 6: Statistics of the five dataset proposed in the long-range graph benchmark
15 A Appendix A.1 Datasets In Tables 6 and 7 we summaries the details of the datasets used for evaluation. Table 6: Statistics of the five dataset proposed in the long-range graph benchmark. Source: LRGB (Dwivedi et al., 2022). Dataset TotalGraphs TotalNodes Avg Nodes MeanDeg....
2022
-
[2022]
A generalization of transformer networks to graphs.arXiv preprint arXiv:2012.09699,
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs.arXiv preprint arXiv:2012.09699,
2012 arXiv
-
[2023]
Add edge index
Dataset Graphs Avg. nodes Avg. edges Prediction Level No. Classes Metric PascalVOC-SP 11,355 479.4 2,710.5 inductive node 21 F1 COCO-SP 123,286 476.9 2,693.7 inductive node 81 F1 PCQM-Contact 529,434 30.1 61.0 inductive link (link ranking) MRR Peptides-func 15,535 150.9 307.3 ...
-
[2024]
Residual gated graph convnets
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv:1711.07553,
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.