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

arXiv: https://arxiv.org/abs/2505.15845 · HTML: https://mlsanity.com/paper/2505.15845/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 52 references that are in the map.
- First posted on arXiv 19 May 2025.

## Builds on (most cited first, 30 of 41)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [LLaGA: Large Language and Graph Assistant](https://mlsanity.com/paper/2402.08170/) (2024)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs](https://mlsanity.com/paper/2206.04910/) (2022)

## Abstract (arXiv)

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.