Pith. sign in

REVIEW 3 major objections 6 minor 73 references

Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A learnable token list fixes the nearby-node bias in graph models

desk verdict Real empirical finding wrapped in a theory that doesn't yet prove the headline claim; worth revising, not rejecting. read the letter →

arxiv 2505.15845 v1 pith:HI4M7VMJ submitted 2025-05-19 cs.LG

Zhibiao Wang , Yunlong Zhou , Ziwei Zhang , Mengmei Zhang , Shirui Pan , Chunming Hu , Xiao Wang This is my paper · ORCID
classification cs.LG
keywords tokenizedgraphlearninghop-overpriorityheterophilicgraphstransformerslargelanguagemodelslearnabletokenlistattentionnodeclassification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

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.

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 (3)
  1. [Section 4.2, Theorems 4.2--4.3] 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.
  2. [Section 5.2, Eq. (10), and Appendix F.3] 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.
  3. [Section 5.2, Appendix F.4.1, and Section 6.1] 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.
minor comments (6)
  1. [Section 5 heading] The heading 'Theoreical Analysis' is misspelled; it should be 'Theoretical Analysis'.
  2. [Section 5.1, first paragraph] The sentence 'LGTL s a simple-yet-effective plug-and-play module' is missing the letter 'i' in 'is'.
  3. [Table 3, PubMed row] 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.
  4. [Theorems 4.3 and 5.2] 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.
  5. [Section 6.1, baseline list] The citation for NodeFormer appears as 'NodeFormer [?]' and should be completed.
  6. [Appendix C.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation found: the paper's theorems follow from stated recursions and explicit bounds, and the LGTL analysis is conditional rather than a fitted prediction renamed as theory.

full rationale

Walking the derivation chain, the core results are not circular. Theorem 4.1 defines the hop-contribution matrices MHO from the recursive message-passing definition of HO and proves their recurrence; Theorem 4.2 substitutes the token expansion into the Transformer attention sum to obtain per-node effective attention and derives near-hop dominance from the row-monotonicity property of MHO; Theorem 4.3 bounds the smoothness error by the triangle inequality plus a Lipschitz condition on features versus labels. None of these equations assumes the conclusion that predefined token lists overemphasize nearby nodes; the conclusion is a derived property of the HO recursion. Theorem 5.1 is a parameter-flexibility statement: by specializing the gate and selection weights, LGTL can recover HO and ND. That is a generality claim about the model family, not a self-justifying input to the argument. Theorem 5.2 and Appendix F.3 provide a conditional bound: if the learned gate scores are larger for hops with higher label consistency, the smoothness error is smaller. This is a mathematical property of the bound, and the paper separately supports the alignment condition empirically in Figure 3. The fact that the gate is trained with downstream labels makes that alignment a fitted behavior, but the paper does not present the observed gate scores as an independent prediction, so this is not a fitted-input-called-prediction circularity. The self-citations present in the paper, such as [4], [28], and [50], are contextual references and baselines; none carries the load-bearing derivation. The only notable concern in the derivation chain is interpretive rather than circular: Theorem 4.3's bound contains the factor |N_i^u|, while the surrounding prose contrasts the per-node attention alpha_i with the hop-level label consistency C_i^u. That is a potential correctness gap in the 'hop-overpriority mismatch' narrative, but it is not a reduction of a result to its own inputs and therefore does not raise the circularity score.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central claim rests on several unverified modeling assumptions: a Lipschitz feature-label relationship, a linear label recovery map, approximately regular graphs for the recursion, and summarized softmax constants. These are stated in the appendices. No new physical entities are introduced; the free parameters are hand-chosen hop depths, sample sizes, and theoretical constants.

free parameters (4)
  • Hop depth L = not reported in main text
    The total number of hops in the token list is a hand-chosen hyperparameter; the gate scores reweight these fixed hops.
  • Neighbor sample sizes n_i = not reported in main text
    The number of nodes sampled per hop in LGTL's selection module is chosen by hand and not disclosed in detail.
  • Lipschitz constant in bounds = not estimated
    The smoothness bounds in Theorems 4.3 and 5.2 depend on an unmeasured Lipschitz constant; the bounds are qualitative.
  • Attention expectation constants gamma_u and eta_u = defined as expectations, not estimated
    Theorem 5.2 treats these as constants, but they depend on the trained query and key values and are not evaluated.
assumptions (5)
  • domain assumption Raw node features are Lipschitz continuous with respect to labels, ||H0_u - H0_v||_F <= L ||y_u - y_v||_F
    Invoked in the proof of Theorem 4.3 (Appendix D.6) and Theorem 5.2, and not verified on the benchmark datasets.
  • domain assumption There exists an invertible linear map from features to one-hot labels, H0 W_C = Y
    Used in Appendix D.6 to justify the smoothness metric analysis; strong for real datasets.
  • domain assumption The graph is approximately regular with average degree n, so the recursion sum_{v in N1_u} H_i^v = H_{i+1} + (n-1) H_{i-1} holds
    Theorem 4.1 and the near-hop dominance results rely on a fixed degree n; real graphs in the experiments are highly irregular.
  • ad hoc to paper The attention softmax over differing labels can be summarized by constants gamma_u and eta_u that are approximately uniform over hops
    Appendix F.3 replaces sums of within-hop attention weights with counts times gamma/eta to obtain the stated bound; this uniformity is not established.
  • domain assumption Downstream training drives the gate scores to align with label consistency C_i^u
    Underlies the claim that Theorem 5.2 explains LGTL's gains; the theorem itself does not guarantee this alignment.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models." pith.science (2026). https://pith.science/paper/HI4M7VMJ

@misc{pith2026250515845,
  author       = {Pith},
  title        = {Pith review of: Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HI4M7VMJ}},
  note         = {Machine review of arXiv:2505.15845}
}
read the original abstract

Graph Transformers, leveraging the global attention to capture long-range dependencies in graph structures, have significantly advanced graph machine learning, but face prohibitive computational complexity. Tokenized Graph Learning Models (TGLMs) address this issue by converting graphs into ordered token lists for scalable processing. Besides, TGLMs also empower Large Language Models (LLMs) to handle text-attributed graphs more effectively and thus are also employed in Graph LLMs. However, existing TGLMs rely on hand-designed token lists and their adaptability to diverse graph learning scenarios remains unexplored. In this paper, we first conduct extensive empirical and theoretical preliminary studies for hand-designed token lists. Surprisingly, we identify an unexplored hop-overpriority problem: the common pre-defined token lists overemphasize nearby nodes and overwhelm the ability of TGLMs to balance local and global signals. This phenomenon is especially harmful for heterophilic graphs. To address this problem, we propose the Learnable Graph Token List (LGTL), a plug-and-play module to replace hand-designed token lists in TGLMs. Specifically, LGTL adaptively adjusts the weights across hops and prioritizes informative nodes within hops through a graph attention gate module and a selection module, respectively. In this way, contextually informative nodes can be adaptively emphasized for both homophilic and heterophilic graphs. Besides, we theoretically show that LGTL can address the hop-overpriority problem. Extensive experiments on benchmarks validate the efficacy of LGTL across both Graph Transformers and Graph LLM backbones.

Figures

Figures reproduced from arXiv: 2505.15845 by the authors.

Figure 1
Figure 1. The average node-homophily for different types of nodes. "Template Better" means nodes [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The overall framework of LGTL, including a [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. The analysis of the score by the gate module vs. the number of hops. “L”, “N”, and “V” [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The label-consistency of the selection mod [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Examples demonstrating the interpretability of LGTL. [PITH_FULL_IMAGE:figures/full_fig_p021_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 47 canonical work pages

  1. [1]

    Llaga: Large language and graph assistant

    Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. Forty-first International Conference on Machine Learning, 2024

    work page 2024

  2. [2]

    The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains

    David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83–98, 2013

    2013

  3. [3]

    How to learn a graph from smooth signals

    Vassilis Kalofolias. How to learn a graph from smooth signals. In Artificial intelligence and statistics, pages 920–929. PMLR, 2016

    2016

  4. [4]

    Less is more: on the over-globalizing problem in graph transformers

    Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is more: on the over-globalizing problem in graph transformers. Forty-first International Conference on Machine Learning, 2024

    work page 2024

  5. [5]

    Semi-supervised classification with graph convolutional networks

    Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017

    2017

  6. [6]

    Graph attention networks

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018

    work page 2018

  7. [7]

    Beyond homophily in graph neural networks: Current limitations and effective designs

    Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793–7804, 2020

    2020

  8. [8]

    Nodeformer: A scalable graph structure learning transformer for node classification

    Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In Advances in Neural Information Processing Systems, 2022

    2022

Show all 73 references
  1. [9]

    Nagphormer: A tokenized graph transformer for node classification in large graphs

    Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. International Conference on Learning Representations, 2022

    2022

  2. [10]

    Vcr-graphormer: A mini-batch graph transformer via virtual connections

    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. In The Twelfth International Conference on Learning Representations, 2024

    2024

  3. [11]

    A neural network approach to jointly modeling social networks and mobile trajectories

    Cheng Yang, Maosong Sun, Wayne Xin Zhao, Zhiyuan Liu, and Edward Y Chang. A neural network approach to jointly modeling social networks and mobile trajectories. ACM Transactions on Information Systems (TOIS), 35(4):1–28, 2017

    2017

  4. [12]

    Skipgnn: predicting molecular interactions with skip-graph networks

    Kexin Huang, Cao Xiao, Lucas M Glass, Marinka Zitnik, and Jimeng Sun. Skipgnn: predicting molecular interactions with skip-graph networks. Scientific reports, 10(1):21092, 2020

    2020

  5. [13]

    Graphgpt: Graph instruction tuning for large language models

    Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 4...

    2024

  6. [14]

    Training language models to follow instructions with human feedback

    Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:2773...

    2022

  7. [15]

    Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877–28888, 2021

    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–28888, 2021

    2021

  8. [16]

    Attention is all you need

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017

    2017

  9. [17]

    A generalization of transformer networks to graphs

    Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI 2021 Workshop on Deep Learning on Graphs: Methods and Applications, 2020

    2021

  10. [18]

    Graphit: Encoding graph structure in transformers

    Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667, 2021

    2021 arXiv

  11. [19]

    Rethinking graph transformers with spectral attention

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

    2021

  12. [20]

    Representing long-range context for graph neural networks with global attention

    Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in neural information processing systems, 34:13266–13279, 2021

    2021

  13. [21]

    Structure-aware transformer for graph representa- tion learning

    Dexiong Chen, Leslie O’Bray, and Karsten Borgwardt. Structure-aware transformer for graph representa- tion learning. In International conference on machine learning, pages 3469–3489. PMLR, 2022

    2022

  14. [22]

    Pure transformers are powerful graph learners

    Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35: 14582–14595, 2022

    2022

  15. [23]

    Recipe for a general, powerful, scalable graph transformer

    Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501–14515, 2022

    2022

  16. [24]

    Specformer: Spectral graph neural networks meet transformers

    Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. International Conference on Learning Representations, 2023

    2023

  17. [25]

    Graph inductive biases in transformers without message passing

    Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pages 23321–23337, 2023

    2023

  18. [26]

    Exphormer: Sparse transformers for graphs

    Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613–31632, 2023

    2023

  19. [27]

    Leveraging contrastive learning for enhanced node representations in tokenized graph transformers

    Jinsong Chen, Hanpeng Liu, John Hopcroft, and Kun He. Leveraging contrastive learning for enhanced node representations in tokenized graph transformers. Advances in Neural Information Processing Systems, 37:85824–85845, 2024

    2024

  20. [28]

    Graphtranslator: Aligning graph model to large language model for open-ended tasks

    Mengmei Zhang, Mingwei Sun, Peng Wang, Shen Fan, Yanhu Mo, Xiaoxiao Xu, Hong Liu, Cheng Yang, and Chuan Shi. Graphtranslator: Aligning graph model to large language model for open-ended tasks. In Proceedings of the ACM Web Conference 2024, pages 1003–1014, 2024

    2024

  21. [29]

    Language is all a graph needs

    Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Language is all a graph needs. Findings of the Association for Computational Linguistics, 2024

    2024

  22. [30]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  23. [31]

    Revisiting graph neural networks: All we have is low-pass filters

    Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550, 2019

    1905 arXiv

  24. [32]

    Graph neural networks exponentially lose expressive power for node classification

    Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2019

    2019

  25. [33]

    Understanding over-squashing and bottlenecks on graphs via curvature

    Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bron- stein. Understanding over-squashing and bottlenecks on graphs via curvature. International Conference on Learning Representations, 2021

    2021

  26. [34]

    Expander graph propagation

    Andreea Deac, Marc Lackenby, and Petar Veliˇckovi´c. Expander graph propagation. In Learning on Graphs Conference, pages 38–1, 2022

    2022

  27. [35]

    Inductive representation learning on large graphs

    Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017

    2017

  28. [36]

    How powerful are graph neural networks? International Conference on Learning Representations, 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019

    2019

  29. [37]

    Query-driven active surveying for collective classification

    Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs, volume 8, page 1, 2012

    2012

  30. [38]

    Pitfalls of graph neural network evaluation

    Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018

    2018

  31. [39]

    Geom-gcn: Geometric graph convolutional networks

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. International Conference on Learning Representations, 2020. 11

    2020

  32. [40]

    Predict then propagate: Graph neural networks meet personalized pagerank

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018

    2018

  33. [41]

    Simplifying graph convolutional networks

    Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861–6871. Pmlr, 2019

    2019

  34. [42]

    Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality

    Wei-Lin Chiang, Zhuohan Li, Ziqing Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality. See https://vicuna. lmsys. org (accessed 14 April 2023...

    2023

  35. [43]

    Llama 2: Open foundation and fine-tuned chat models

    Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023

    2023 arXiv

  36. [44]

    Exploring the potential of large language models (llms) in learning on graphs

    Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (llms) in learning on graphs. ACM SIGKDD Explorations Newsletter, 25(2):42–61, 2024

    2024

  37. [45]

    Can llms effectively leverage graph structural information: When and why

    Jin Huang, Xingjian Zhang, Qiaozhu Mei, and Jiaqi Ma. Can llms effectively leverage graph structural information: When and why. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023

    2023

  38. [46]

    Graphtext: Graph reasoning in text space

    Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. NeurIPS Workshop: Adaptive Foundation Models, Evolving AI for Personalized and Efficient Learning, 2025

    2025

  39. [47]

    Walklm: A uniform language model fine-tuning framework for attributed graph embedding

    Yanchao Tan, Zihao Zhou, Hang Lv, Weiming Liu, and Carl Yang. Walklm: A uniform language model fine-tuning framework for attributed graph embedding. Advances in neural information processing systems, 36:13308–13325, 2023

    2023

  40. [48]

    Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment

    Jianing Wang, Junda Wu, Yupeng Hou, Yao Liu, Ming Gao, and Julian McAuley. Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. Findings of the Association for Computational Linguistics ACL, 2024

    2024

  41. [49]

    Gophormer: Ego-graph transformer for node classification

    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, 2021

    2021 arXiv

  42. [50]

    Graph meets llms: Towards large graph models

    Ziwei Zhang, Haoyang Li, Zeyang Zhang, Yijian Qin, Xin Wang, and Wenwu Zhu. Graph meets llms: Towards large graph models. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023

    2023

  43. [51]

    A survey of large language models for graphs

    Xubin Ren, Jiabin Tang, Dawei Yin, Nitesh Chawla, and Chao Huang. A survey of large language models for graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 6616–6626, 2024

    2024

  44. [52]

    [Yes] " is generally preferable to

    Yuhan Li, Zhixun Li, Peisong Wang, Jia Li, Xiangguo Sun, Hong Cheng, and Jeffrey Xu Yu. A survey of graph meets large language model: progress and future directions. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages 8123–8131, ...

    2024

  45. [53]

    Guidelines: • The answer NA means that the abstract and introduction do not include the claims made in the paper

    Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The abstract and introduction accurately reflect the paper’s contributions and scope. Guidelines: • The answer NA mean...

  46. [54]

    Limitations

    Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We provide detailed discussions about limitations in Appendix C.1. Guidelines: • The answer NA means that the paper has no limitation while the answe...

  47. [55]

    Furthermore, we provide the theory assumptions and proofs of LGTL in Appendix F

    Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: We provide complete theory assumptions and proofs of pre-defined token list in Appendix D an...

  48. [56]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and da...

  49. [57]

    Guidelines: • The answer NA means that paper does not include experiments requiring code

    Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Yes, we provide our code in...

  50. [58]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: Yes, all the training and tes...

  51. [59]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experiment statistical significance 15 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Yes, our main experimental results in Table 2 a...

  52. [60]

    Guidelines: • The answer NA means that the paper does not include experiments

    Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Sufficient information ...

  53. [61]

    Guidelines: • The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics

    Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: Yes, we have read the NeurIPS Code of Ethics and our paper conforms, in every r...

  54. [62]

    Guidelines: • The answer NA means that there is no societal impact of the work performed

    Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We discuss both potential positive societal impacts and negative societal impacts of the work in Appendix...

  55. [63]

    Guidelines: • The answer NA means that the paper poses no such risks

    Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses...

  56. [64]

    17 Guidelines: • The answer NA means that the paper does not use existing assets

    Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We have cited th...

  57. [65]

    Guidelines: • The answer NA means that the paper does not release new assets

    New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: The paper does not release new assets. Guidelines: • The answer NA means that the paper does not release new assets. ...

  58. [66]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? A...

  59. [67]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals...

  60. [68]

    18" pay more attention to 2-hop neighbors and itself. Moreover, the selection module increases the proportion of the feature of node

    Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the ...

    2025

  61. [69]

    MND 0,0 = 1 (root node, 0-hop)

  62. [70]

    MND 1,0 = 0, MND 1,1 = 1 (layer 1 contains only 1-hop neighbors)

  63. [71]

    For i≥ 1 andj≥ 1: MND i,j = MND i−1,j−1 + (n− 1)MND i−1,j+1. Proof. Fori = 0 (the root layer), ND contains onlyu itself, so MND 0,0 = 1 and MND 0,j = 0 forj >0. Rule 1 holds. Fori = 1, sinceu does not appear in layer 1, MND 1,0 = 0;N 1 u appear exactly once per sampled node, s...

  64. [72]

    Near-Hop Dominance: ϕL,k >ϕ L,k+2 for allk≤L (closer hops have higher total weights)

  65. [73]

    ) have ϕL,k > ϕL,k−1 and ϕL,k > (n− 1)ϕL,k+1

    Layer Parity Bias: • If L is odd (L = 2k + 1), odd hops ( k = 1, 3,... ) have ϕL,k > ϕL,k−1 and ϕL,k > (n− 1)ϕL,k+1. • IfL is even (L = 2k), even hops (k = 0, 2,... ) have ϕL,k > ϕL,k−1 andϕL,k > (n− 1)ϕL,k+1. Proof. From within-layer decay, MND i,k > MND i,k+2 for alli≥k. The...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.