{"id":"9898e198-2783-4c97-90a6-d7a0dddaa7cd","arxiv_id":"2505.15845","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A learnable graph token list that adaptively reweights hops and selects informative within-hop nodes alleviates the hop-overpriority problem in tokenized graph learning models, especially on heterophilic graphs.","lead":"This paper identifies a hop-overpriority problem in tokenized graph learning models, where hand-designed token lists overweight nearby nodes and hurt performance on heterophilic graphs. It proposes LGTL, a learnable token list module that reweights hops and selects informative neighbors, with consistent gains across Graph Transformers and Graph LLMs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's near-hop dominance is per-node; once hop sizes |N_k| are counted, the claimed hop-level overpriority is not established, weakening the theoretical core.","rationale":"The paper's central claim has two pillars: an empirical demonstration that fixed token lists hurt heterophilic graphs, and a theoretical account of why (hop-overpriority) plus a proof that LGTL fixes it. The empirical pillar is credible: Table 1 shows large degradations on Cornell, Texas, and Wisconsin, and LGTL consistently improves in Tables 2 and 3. The weaker pillar is the theory. The most serious problem is not only that gate scores are not proven to align with label consistency (the reader's weakest_assumption), but that the hop-overpriority concept itself is inferred from a per-node inequality while the model output and the paper's own smoothness bound depend on per-hop total mass. Since |N_k| typically grows with k, per-node decay can coexist with total-mass growth; the regular-tree calculation for HO shows a token can be dominated by its frontier hop. Therefore Theorem 4.2 does not by itself imply the \"overemphasis of nearby nodes\" stated in Section 4.2, and the qualitative interpretation of Theorem 4.3 is not justified. This is an internal-consistency issue rather than a disagreement with community consensus. A concrete computational check on the actual datasets can settle whether the mismatch appears. Separately, the proof of Theorem 5.2 in Appendix F.3 appears to replace LGTL's per-hop within-subgraph softmax with a global softmax over all hops, and the gate-alignment premise is unproven; these reinforce the need for a revised theory. If the total-mass check fails, the theoretical contribution needs substantial revision, but the empirical claim about LGTL may still stand. This is consistent with the reader's CONDITIONAL verdict, so no verdict change is recommended.","tokens_in":27565,"tokens_out":17690,"duration_ms":196191,"concrete_test":"On Texas/Cornell (or a regular-tree toy graph), instantiate the HO/ND contribution matrices from Theorem 4.1 and Appendix E, set token attention to uniform (and also to learned LLaGA attention when available), and compute per-hop total mass \\hat\\alpha_k |N_k^u| and the smoothness terms \\hat\\alpha_k |N_k^u|(1-C_k^u) for k=0..L. If this total mass is not monotonically decreasing with k—or is largest on the high-C hop—the hop-overpriority mismatch described in Section 4.2 is not reproduced, and the theoretical narrative needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the inference from Theorem 4.2 to the \"hop-overpriority problem.\" Theorem 4.2 shows that the effective attention \\hat\\alpha_k of a single node v in N_k^u is larger for small k (Near-Hop Dominance). But each hop contains |N_k^u| nodes, so the total influence of hop k on the representation is \\hat\\alpha_k |N_k^u|, not \\hat\\alpha_k. The smoothness bound in Theorem 4.3 is stated with \\hat\\alpha_i |N_i^u|(1-C_i^u), so the text's conclusion that \"hops with low C_i^u receive high \\hat\\alpha_i, while hops with high C_i^u receive low attention\" compares per-node weights to whole-hop label consistency without accounting for neighborhood growth. On graphs where |N_k| grows in k, the product \\hat\\alpha_k |N_k| can increase with k while \\hat\\alpha_k decreases. For the HO recurrence on a regular tree, T_3 carries total mass on hop 3 of about ((n-1)/n)^2 and on hop 1 of about 1/n; the frontier aggregate dominates, not the nearby nodes. Thus the claimed mismatch driving the hop-overpriority phenomenon is not established by the stated theorems; it may be an artifact of using per-node attention as the measure of overpriority. This leaves the theoretical motivation of LGTL on weak ground, even though the empirical gains may be genuine.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Tokenized Graph Learning Models (TGLMs), which convert a graph into an ordered token list that is processed by a Graph Transformer or a Graph LLM. The authors claim that hand-designed token lists suffer from a previously unrecognized 'hop-overpriority problem': fixed templates allocate excessive per-node attention to nearby hops, which is especially harmful on heterophilic graphs where 1-hop neighbors are label-inconsistent. The paper supports this with preliminary experiments on LLaGA (Table 1), theoretical results on the Hop-field Overview (HO) template (Theorems 4.1--4.3) and on the Neighborhood Detail (ND) template (Appendix E), and proposes LGTL, a plug-and-play module with a gate module that reweights hops and a selection module that reweights nodes within a hop. The authors prove that LGTL generalizes HO and ND (Theorem 5.1) and claim a smoothness bound showing LGTL mitigates the hop-overpriority problem (Theorem 5.2). Experiments on text-attributed graphs with LLaGA and on non-text benchmarks with NAGphormer and VCR-Graphormer show consistent gains, particularly on heterophilic datasets.","tokens_in":27899,"tokens_out":9512,"duration_ms":99859,"significance":"If the claims hold, LGTL is a practically valuable contribution: it is simple, plug-and-play, and the reported gains on heterophilic graphs are large across three distinct backbones and multiple datasets. The paper also provides a useful empirical documentation of the failure modes of fixed token lists on heterophilic graphs, and it ships code and error bars, which strengthens reproducibility. However, the theoretical component is load-bearing for the paper's central narrative: the 'hop-overpriority problem' is defined and motivated through Theorems 4.2--4.3, and the claim that LGTL 'provably' fixes the problem rests on Theorem 5.2. As detailed below, the hop-level conclusion does not follow from the per-node theorem, and the proof of Theorem 5.2 contains an unjustified replacement of attention sums by label-count constants. The empirical results may well be genuine, but the theoretical justification in the current manuscript is not yet established.","major_comments":[{"comment":"The inference from per-node near-hop dominance to a hop-level overpriority problem is not justified. Theorem 4.2 proves that the effective attention of a single node v in N_k^u, denoted \\hat\\alpha_k, decreases with k. But the total influence of hop k on the representation is \\hat\\alpha_k |N_k^u|, and this product is not shown to decrease. This matters because the smoothness bound in Theorem 4.3 is stated with the aggregate term \\hat\\alpha_i |N_i^u|(1-C_i^u), and the concluding paragraph of Section 4.2 compares per-node weights \\hat\\alpha_i with whole-hop label consistency C_i^u. On an n-regular tree, the HO token T_3 carries coefficient 2(n-1)/n^2 on hop 1 and (n-1)^2/n^2 on hop 3; for n>3 the hop-3 aggregate exceeds the hop-1 aggregate even though the per-node weight on hop 1 is larger. Thus the claimed mismatch between low-C hops and high attention is not established at the hop level, and the central theoretical motivation for LGTL is weakened. Additionally, Theorem 4.1's recurrence assumes a fixed degree n for all nodes; for irregular graphs the substitution \\sum_{v\\in N_u} H_i^v = H_{i+1}^u +(n-1)H_{i-1}^u is only an approximation and should be stated as an assumption rather than a definition.","section":"Section 4.2, Theorems 4.2--4.3"},{"comment":"The proof of Theorem 5.2 is not a valid derivation from the model equations. In Eq. (6), the within-hop attention weights \\beta_{u,i,v} are normalized inside each subgraph G_i^u, but the second equality in Appendix F.3 replaces the sum over mismatched labels by a global softmax denominator containing \\gamma_u and \\eta_u over all hops, with no derivation connecting these objects. In addition, the actual adjusted attention in Eq. (7) is \\hat\\alpha_{u,i} = \\alpha_{u,i}\\hat{s}_{u,i}/\\langle\\alpha\\cdot\\hat{s}\\rangle, so the base attention \\alpha_{u,i} appears in the aggregation; Eq. (10) and the F.3 proof drop this factor entirely and bound an object involving only \\hat{s}_{u,i}, which is not the LGTL output defined in Eq. (8). Furthermore, Eq. (5) defines \\hat{s} by a softmax that sums to 1, while F.3 begins by assuming \\sum_i \\hat{s}_{u,i}=L+1, changing the effective scaling of the bound. Finally, the theorem's bound is independent of \\beta_{u,i,v}, so the selection module's within-hop prioritization is not covered by the theorem at all.","section":"Section 5.2, Eq. (10), and Appendix F.3"},{"comment":"The theoretical claim is conditional in a way that is not acknowledged, and it does not match the frozen-LLM experimental setup. Theorem 5.2 only states that IF the gate scores \\hat{s}_{u,i} are larger for hops with larger label consistency C_i^u, THEN the smoothness error decreases. Nothing in the paper proves that minimizing the downstream classification loss drives a gate module to learn this alignment; the gate is trained on the same labels that appear in C_i^u, so the improvement is partly a fitted outcome rather than an independent prediction. Moreover, the main derivation assumes the Transformer attention \\alpha can be adjusted as in Eq. (7), but Appendix F.4.1 states that for a frozen LLM, LGTL instead scales the input tokens directly (Eq. (55)). The LLaGA experiments in Table 2 use this frozen-LLM setting, so the theorem is not shown to apply to the variant that actually produces the headline results.","section":"Section 5.2, Appendix F.4.1, and Section 6.1"}],"minor_comments":[{"comment":"The heading 'Theoreical Analysis' is misspelled; it should be 'Theoretical Analysis'.","section":"Section 5 heading"},{"comment":"The sentence 'LGTL s a simple-yet-effective plug-and-play module' is missing the letter 'i' in 'is'.","section":"Section 5.1, first paragraph"},{"comment":"The entry '92.70±0.2747.37±3.25' is missing a separator between the Photo accuracy and the Cornell accuracy; the table is hard to read at that point.","section":"Table 3, PubMed row"},{"comment":"The symbol L is used both for the hop depth and for the Lipschitz constant in the same bound, which is confusing; use a distinct symbol such as \\mathcal{L} for the Lipschitz constant.","section":"Theorems 4.3 and 5.2"},{"comment":"The citation for NodeFormer appears as 'NodeFormer [?]' and should be completed.","section":"Section 6.1, baseline list"},{"comment":"The limitations discussion lists only future graph types and does not mention the theoretical assumptions behind Theorems 4.3 and 5.2, such as approximately regular graphs, Lipschitz continuity of features with respect to labels, and the softmax-normalization approximations in Appendix F.3.","section":"Appendix C.1"}],"recommendation":"major_revision","confidential_remarks":"The empirical contribution is substantial and the method seems practically useful, but the paper's central theoretical claims are currently not supported: the hop-level overpriority conclusion does not follow from the per-node theorem, and the proof of Theorem 5.2 contains unjustified steps. I recommend asking the authors to either repair these proofs or substantially weaken the theoretical claims and reposition the paper as an empirical study of adaptive tokenization. If the proofs cannot be repaired within a revision, the 'theoretically show' claims should be removed rather than left in their current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know up front. The empirical core is genuine: the paper identifies a failure mode—predefined token lists that over-weight near-hop nodes hurt performance on heterophilic graphs—and a plug-and-play fix (LGTL) with consistent gains across LLaGA, NAGphormer, and VCR-Graphormer. The theory is the weak load-bearing wall: the hop-overpriority problem is not actually established by the stated theorems, and the main bound for LGTL has a derivation gap. Treat this as an empirical contribution with a promising but unfinished theoretical wrapper.\n\nWhat is new is real: the hop-overpriority diagnosis, the gate-plus-selection mechanism, and the empirical study of how token templates behave on heterophilic text-attributed graphs. That is a genuine gap in the TGLM literature. The experiments are extensive, the gains on Cornell/Texas/Wisconsin are large, and the ablation isolating gate vs. selection is informative. The preliminary results in Table 1 and Figure 1 deserve credit.\n\nThe soft spots, in proportion:\n- The stress-test concern holds up. Theorem 4.2 shows per-node effective attention decreases with hop, but hop-level influence is \\hat\\alpha_k |N_k|. On a regular tree, |N_k| grows, so aggregate far-hop mass can dominate. The paper's own bound in Theorem 4.3 uses \\hat\\alpha_i |N_i^u|, so the verbal conclusion that \"low-consistency hops receive high attention\" ignores neighborhood growth. The claimed mismatch is not proven.\n- Theorem 4.1's recursion assumes a fixed degree n while claiming only average degree. That is an unstated regularity assumption.\n- Appendix F.3 replaces sums over the selection attention \\beta with plain counts and constants \\gamma_u, \\eta_u without a clean derivation. As written it looks like a softmax ratio that does not match the per-hop GAT normalization in Eq. (6).\n- Theorem 5.2 is conditional: if gate scores concentrate on high-label-consistency hops, the bound improves. Nothing proves training drives the gate there; the Figure 3 plots are suggestive, not proof.\n- Minor: the arXiv text says code is in supplementary material but no link appears in this version; that needs fixing for reproducibility.\n\nThese are addressable. Sharpen the aggregate-hop statement, state the regularity assumption, and either prove the beta-count step or reframe Theorem 5.2 as an interpretation of the mechanism rather than a guarantee. Who is this for: anyone working on tokenized graph transformers or graph LLMs. It is a useful empirical finding and a practical module. I would send it to a serious referee; the empirical claims alone justify a revision, not a rejection.","headline":"Real empirical finding wrapped in a theory that doesn't yet prove the headline claim; worth revising, not rejecting.","tokens_in":28409,"tokens_out":3259,"would_cite":true,"duration_ms":35771,"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":"A learnable token list fixes the nearby-node bias in graph models","keywords":["tokenized graph learning","hop-overpriority","heterophilic graphs","graph transformers","graph large language models","learnable token list","graph attention","node classification"],"falsifier":"Train LGTL on a heterophilic benchmark, record the learned gate weight per hop, and compare it with the label-consistency of that hop; the paper's mechanism would be refuted if the gate systematically assigns higher weights to hops with lower label consistency while the accuracy gains remain, since then the gains would have to come from something other than the stated hop rebalancing.","tokens_in":27388,"feed_emoji":"🔗","tokens_out":8394,"duration_ms":75674,"temperature":0.7,"pith_summary":"The paper seeks to establish that tokenized graph learning models (TGLMs) — models that turn a graph into an ordered list of tokens for a Transformer or large language model — fail on low-homophily graphs because their hand-designed token lists systematically over-weight nearby nodes. That bias is named the hop-overpriority problem, and the paper characterizes it both empirically and theoretically: pre-defined token lists allocate more effective attention to near neighbors and treat all nodes in a hop as indistinguishable. The proposed cure, the Learnable Graph Token List (LGTL), replaces the fixed list with a plug-in module that learns a weight for each hop and a weight for each node inside a hop. If the claim is right, any tokenized graph Transformer or graph LLM can be made substantially more robust to heterophily by swapping in LGTL, with the largest gains exactly where fixed templates currently hurt.","feed_headline":"A learnable token list fixes the nearby-node bias in graph models","feed_subtitle":"Graph Transformers and graph LLMs gain about ten points on heterophilic benchmarks when token lists learn hop weights.","key_machinery":"The load-bearing object is the hop contribution matrix $M^{HO}_{k,i}$, which records how much a token at depth $k$ is built from features of $i$-hop neighbors. It obeys a recursion that yields two consequences Theorem 4.2 states: near-hop dominance, where closer hops receive more effective attention, and within-hop indistinguishability, where all nodes at the same hop share one attention weight. Theorem 4.3 then converts this bias into a smoothness bound that grows when attention falls on hops with low label consistency. LGTL's machinery is a pair of graph-attention modules: a gate module producing per-hop softmax weights from the central node's subgraph, and a selection module weighting sampled neighbors inside each hop. The gate weights renormalize the transformer attention, which is the step that lets the model shift priority away from noisy nearby hops.","core_discovery":"The paper's central claim is that the failure of pre-defined token lists is not accidental but structural. For the hop-overview template, the paper derives a hop contribution matrix $M^{HO}_{k,i}$ and proves two properties: distant hops get exponentially less effective attention than nearby hops, and every node within the same hop receives identical attention. On low-homophily graphs, where nearby hops have low label consistency and farther hops have higher label consistency, this near-hop bias forces the model to emphasize noisy signals. LGTL counters the bias directly: a graph-attention gate module learns a softmax weight for each hop from the central node's subgraph, and a selection module computes within-hop attention over sampled neighbors; the model's raw attention scores are then renormalized by the learned hop weights. The paper proves that LGTL generalizes the hop-overview and neighborhood-detail templates as special cases and that its smoothness bound is minimized when gate weights track label consistency across hops.","pith_inferences":["Editorial inference: if hop-overpriority is as general as the paper argues, other pre-defined tokenizations — random-walk sequences, PPR-based context, or sampled computational trees — should show the same near-hop bias, and a gate module like LGTL's could be tested directly on them.","Editorial inference: the learned gate scores provide a cheap empirical diagnostic for heterophily: a model that systematically down-weights hop 1 and up-weights hop 2 is telling you the graph's 1-hop neighbors are label-inconsistent, which could seed a lightweight homophily estimator.","Editorial inference: in the frozen-LLM setting LGTL approximates attention adjustment by scaling token features rather than training attention; fine-tuning the LLM jointly is the natural next experiment, though it would give up some plug-and-play simplicity."],"forward_implications":["Substituting LGTL for the fixed token list in LLaGA improves node-classification accuracy on all six text-attributed datasets tested, with the largest margins on low-homophily graphs such as Texas and Wisconsin.","Integrating LGTL into NAGphormer and VCR-Graphormer raises accuracy on heterophilic benchmarks by about ten points on average while preserving or slightly improving homophilic performance.","The theoretical bounds imply the benefit is mechanism-driven: assigning higher gate scores to hops with higher label consistency directly shrinks the smoothness bound.","Because HO and ND are special cases of LGTL, existing token-list designs are not wasted; they become one endpoint of the learnable family.","Removing either the gate module or the selection module degrades results, and the degradation is larger on heterophilic graphs, so both hop-level and within-hop adaptation are necessary parts of the proposal."],"supporting_citations":[{"why":"Supplies the LLaGA Graph-LLM backbone whose fixed HO/ND token lists are replaced by LGTL in the paper's central experiments.","marker":"[1]"},{"why":"NAGphormer is a tokenized Graph Transformer backbone; replacing its predefined token list with LGTL tests the method without text features.","marker":"[9]"},{"why":"VCR-Graphormer provides a second Graph Transformer backbone whose extended cluster-token list LGTL must remain compatible with.","marker":"[10]"},{"why":"Graph Attention Networks provide the attention mechanism reused by LGTL's gate and selection modules.","marker":"[6]"},{"why":"The graph-signal-processing formulation supplies the Frobenius-norm smoothness metric used in Theorems 4.3 and 5.2.","marker":"[2]"},{"why":"The smooth-signal learning view supports the same smoothness metric and is cited jointly with [2] for the norm used in the bounds.","marker":"[3]"},{"why":"H2GCN is the heterophily-focused GNN baseline that LGTL must surpass on low-homophily datasets.","marker":"[7]"},{"why":"The over-globalizing problem in Graph Transformers is the comparison point for LGTL's smoothness bound, showing the fixed-token bound matches earlier transformer analysis.","marker":"[4]"}],"fun_headline_variants":["Learnable token lists fix hop-overpriority in graph models","Adaptive tokenization balances local and global graph signals","Graph models learn which hops matter for each node","Hop gates unlearn near-node bias in graph Transformers","Token lists that learn hop weights boost heterophilic graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument rests on the assumption that the gate module learns to give more weight to the hops whose neighbors share the central node's label; the theory only describes what happens if that alignment is achieved, not what makes the training procedure reach it.","fun_headline_variants_meta":{"raw":{"variants":["Learnable token lists fix hop-overpriority in graph models","Adaptive tokenization balances local and global graph signals","Graph models learn which hops matter for each node","Hop gates unlearn near-node bias in graph Transformers","Token lists that learn hop weights boost heterophilic graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000662,"raw_usage":{"total_tokens":3061,"prompt_tokens":1019,"completion_tokens":2042,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":1965}},"tokens_in":635,"tokens_out":2042,"duration_ms":16420,"temperature":1.0,"reasoning_tokens":1965,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:27:25.654546+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train LGTL on a heterophilic benchmark, record the learned gate weight per hop, and compare it with the label-consistency of that hop; the paper's mechanism would be refuted if the gate systematically assigns higher weights to hops with lower label consistency while the accuracy gains remain, since then the gains would have to come from something other than the stated hop rebalancing.","supporting_citations":[{"cited_title":"Llaga: Large language and graph assistant","cited_arxiv_id":null,"evidence_quote":"Supplies the LLaGA Graph-LLM backbone whose fixed HO/ND token lists are replaced by LGTL in the paper's central experiments."},{"cited_title":"Nagphormer: A tokenized graph transformer for node classification in large graphs","cited_arxiv_id":null,"evidence_quote":"NAGphormer is a tokenized Graph Transformer backbone; replacing its predefined token list with LGTL tests the method without text features."},{"cited_title":"Vcr-graphormer: A mini-batch graph transformer via virtual connections","cited_arxiv_id":null,"evidence_quote":"VCR-Graphormer provides a second Graph Transformer backbone whose extended cluster-token list LGTL must remain compatible with."},{"cited_title":"Graph attention networks","cited_arxiv_id":null,"evidence_quote":"Graph Attention Networks provide the attention mechanism reused by LGTL's gate and selection modules."},{"cited_title":"Less is more: on the over-globalizing problem in graph transformers","cited_arxiv_id":null,"evidence_quote":"The over-globalizing problem in Graph Transformers is the comparison point for LGTL's smoothness bound, showing the fixed-token bound matches earlier transformer analysis."}],"review_version":1}