{"id":"86f5d1b2-6001-46ea-9e7f-9985dc3a252b","arxiv_id":"2412.01519","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"ReHub keeps spoke-to-hub attention sparse by connecting each node to only k hubs per layer and reassigning those hubs via hub-hub similarity, reaching O(N) complexity with accuracy on par with its dense variant.","lead":"A new graph transformer, ReHub, keeps memory cost linear in graph size by giving each node only three virtual 'hub' connections per layer, and it adaptively reassigns those connections between layers using cheap hub-to-hub scores. On long-range graph benchmarks it beats the Neural Atoms baseline it builds on, and on large citation graphs it uses less memory than Exphormer with a small accuracy trade-off.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The hub-hub similarity proxy in Algorithm 1 is the load-bearing assumption: if hub-hub distance does not track spoke-hub relevance, reassignment degrades toward random and sparse-dense parity lacks support; a direct exact-assignment comparison is needed.","rationale":"The reader's weakest assumption identifies the same structural risk I would flag: the reassignment step is where the method departs from exact spoke-hub scoring, and the paper provides no theoretical argument that hub-hub similarity is a faithful surrogate. The empirical hub-utilization and Bhattacharyya analyses show that all hubs are used and that assignments are balanced, but neither property implies that the assigned hubs are the ones that maximize information flow for each spoke. The internal evidence in Table 5 strengthens this concern: random reassignment causes a large drop (0.3860 to 0.3514), while no reassignment drops only to 0.3775, so the exact choice of replacement hubs is consequential. This makes the proxy genuinely load-bearing for the claim that the sparse model is on par with the dense ReHub-FC model. The other issues raised by the reader (test-set-based hyperparameter selection in Figure 4, omitted COCO-SP results, and the 1.4-point OGBN-Arxiv gap labeled comparable) are real but secondary: they affect the strength of specific empirical claims rather than the architectural premise. Given the available evidence and the absence of any indication of misreporting, the appropriate disposition remains conditional: the central claim is likely to hold if the proxy is validated on additional settings and the experimental reporting gaps are closed. My recommended verdict is therefore unchanged from the reader's CONDITIONAL.","tokens_in":958,"tokens_out":928,"duration_ms":95890,"concrete_test":"On PascalVOC-SP and Peptides-func (sizes where O(Ns*Nh) is feasible), rerun ReHub replacing Algorithm 1's hub-hub proxy with exact top-k selection: for each spoke, compute the full spoke-hub attention or dot-product similarity over all Nh hubs and connect to the k highest-scoring hubs at each layer, keeping all other hyperparameters fixed. Compare test F1/AP and per-layer assignment overlap (e.g., Jaccard index) against the proxy version across the same 5 seeds. If exact selection outperforms the proxy by more than one standard deviation, the hub-hub proxy is a bottleneck and the sparse-dense parity claim should be re-scoped; if results are statistically tied, the proxy is validated for these regimes and the central claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.4 step (5) and Algorithm 1, ReHub avoids the O(Ns*Nh) spoke-hub computation by replacing each spoke's next k hubs with the k hubs nearest in feature space to the spoke's current most-attended hub. The paper's only evidence for this proxy is hub-utilization histograms (Figure 3) and Bhattacharyya balance curves (Figure 5), which measure coverage and balance, not whether the chosen hubs are actually the informative ones. Table 5 is the key stress point: replacing the similarity-based reassignment with random reassignment drops PascalVOC-SP F1 from 0.3860 to 0.3514, while disabling reassignment only drops it to 0.3775. Thus the method's accuracy is highly sensitive to the quality of the hub-selection rule, and the proxy is exactly the place where no correctness argument is supplied. If hub-hub distance is a poor proxy (for instance, if H2H attention makes hub features homogeneous, or if the argmax hub is not a reliable anchor), the sparse model could lose the parity with ReHub-FC that the central claim promises. Because the sparse-dense parity in Tables 1-2 is the empirical core of the contribution, this unvalidated proxy is the most load-bearing assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19083,"tokens_out":5726,"duration_ms":51185,"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":[{"comment":"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":"Section 3.4, Algorithm 1"},{"comment":"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.","section":"Section 3.4, 'Complexity' paragraph"},{"comment":"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.","section":"Table 2 and Section 4.1"}],"minor_comments":[{"comment":"The notation 'O(n3/2)' should be written as 'O(n^{3/2})' for clarity.","section":"Abstract"},{"comment":"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":"Section 3.4, step (5)"},{"comment":"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":"Section 4.3, Hub utilization"},{"comment":"There is a typo in 'GraphGPS (with vanila Transformer)' — 'vanila' should be 'vanilla'.","section":"Section 4.2"},{"comment":"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.","section":"Section 3.3 and Appendix A.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is solid in its empirical delivery: the complexity analysis is essentially correct, the sparse-dense parity is demonstrated on multiple datasets, and the memory scaling study is a nice addition. The main risk is the unvalidated hub-hub proxy; a direct comparison with exact assignment would substantially raise confidence. The omission of COCO-SP and the use of copied baseline numbers are secondary but worth addressing. I would be comfortable with acceptance after the proxy is validated and the complexity analysis is made fully explicit."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real contribution to making virtual-node graph transformers scale. The per-layer reassignment idea is new, the complexity analysis is correct, and the experiments largely support the main claims. The biggest open question is whether the hub-hub similarity proxy actually stands in for spoke-hub relevance; the paper never tests that directly.\n\nWhat is new: instead of fixing a small set of virtual nodes (Exphormer) or learning them (Neural Atoms), ReHub connects each spoke to k hubs and reassigns those hubs each layer using distances between hubs. This avoids the O(Ns*Nh) cost of exact reassignment. With Nh ~ sqrt(Ns) and k constant, complexity is linear. The METIS-based hub initialization is a nice addition, and the ablation shows it beats learned virtual nodes.\n\nWhat works: sparse/dense parity is shown on three LRGB datasets, and on PascalVOC-SP the sparse model actually outperforms the dense variant. The memory benchmark up to 700K nodes shows clear linear scaling and lower peak memory than Exphormer and Neural Atoms. The modularity across MPNNs is a genuine plus.\n\nSoft spots, in rough order. (1) The reassignment heuristic is load-bearing but under-validated. The ablation shows it beats random reassignment, but that only says it is better than chance, not that it is close to exact top-k assignment. A direct comparison on a small dataset would settle this. (2) COCO-SP is missing from the LRGB comparisons, weakening the claim of consistent improvement across the benchmark. (3) Figure 4 selects the hubs ratio and k using test-set curves; this should be clarified or moved to validation. (4) The OGBN-Arxiv gap to Exphormer is about 1.4 points, which is not really 'comparable'; it is a trade-off and should be reported as such.\n\nThis paper is for anyone working on scalable graph transformers or virtual-node designs. It deserves a serious referee. I would recommend acceptance after revision, with the exact-assignment ablation and COCO-SP results as the key asks.","headline":"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.","tokens_in":19672,"tokens_out":4740,"would_cite":true,"duration_ms":41403,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["graph transformers","virtual nodes","hub-spoke reassignment","linear complexity","sparse attention","long-range graph benchmark","memory efficiency","graph neural networks"],"falsifier":"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.","tokens_in":18622,"feed_emoji":"✈️","tokens_out":4577,"duration_ms":38385,"temperature":0.7,"pith_summary":"ReHub is a graph transformer designed to carry long-range information without the quadratic cost of dense attention. Its central claim is that you can keep the total number of virtual nodes (hubs) at $\\sqrt{N_s}$ while letting each real node (spoke) attend to only a small constant $k$ of hubs per layer, giving linear time and memory in the number of spokes $N_s$. The method's key move is to reassign which hubs each spoke connects to at every layer using only hub-hub similarities, avoiding the $N_s \\times N_h$ computation that exact spoke-hub reassignment would cost. If the claim holds, large graphs that previously forced a choice between global communication and memory budget can have both, and the reported experiments show the sparse variant performing on par with its fully connected counterpart while improving over Neural Atoms on long-range benchmarks.","feed_headline":"Reassigned hubs give graph transformers linear cost, full accuracy","feed_subtitle":"A sparse model where each node talks to k hubs matches the dense virtual-node baseline on long-range benchmarks.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the Neural Atoms baseline and virtual-node design that ReHub extends and must beat.","marker":"[Li et al., 2024]"},{"why":"Exphormer is the linear-complexity transformer baseline used for accuracy and memory comparisons.","marker":"[Shirzad et al., 2023]"},{"why":"GraphGPS supplies the framework and hyperparameter setups that ReHub builds on for training and evaluation.","marker":"[Rampášek et al., 2022]"},{"why":"METIS clustering initializes hub features and the initial spoke-hub assignment.","marker":"[Karypis & Kumar, 1998]"},{"why":"The long-range graph benchmark datasets that provide the main evaluation tasks.","marker":"[Dwivedi et al., 2022]"},{"why":"GATv2 attention is the mechanism used for the sparse spoke-hub and dense hub-hub updates.","marker":"[Brody et al., 2021]"}],"fun_headline_variants":["Adaptive hub reassignment: linear graph transformers, full accuracy","Hub-spoke graph nets go linear with adaptive reassignment","ReHub: sparse hub attention matches dense, stays linear","Graph transformers reach linear cost via hub reassignment"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive hub reassignment: linear graph transformers, full accuracy","Hub-spoke graph nets go linear with adaptive reassignment","ReHub: sparse hub attention matches dense, stays linear","Graph transformers reach linear cost via hub reassignment"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000656,"raw_usage":{"total_tokens":3044,"prompt_tokens":1024,"completion_tokens":2020,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":640,"completion_tokens_details":{"reasoning_tokens":1954}},"tokens_in":640,"tokens_out":2020,"duration_ms":12499,"temperature":1.0,"reasoning_tokens":1954,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T04:17:22.786505+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}