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

Zhibiao Wang, Yunlong Zhou, Ziwei Zhang, Mengmei Zhang, Shirui Pan, Chunming Hu, Xiao Wang · 2025

Read Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models by Zhibiao Wang, Yunlong Zhou, Ziwei Zhang, Mengmei Zhang, Shirui Pan, Chunming Hu, Xiao Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15845.txt.

Introduction

Zhibiao Wang and co-authors published a computing paper in 2025 on how graph learning models turn graphs into token lists. Listing nodes by distance is the usual hand-made recipe, but the team found a flaw: nearby nodes get over-emphasized and drown out global signals. They call it the hop-overpriority problem, worst on graphs where linked nodes differ.

Their fix is a learnable token list that reweights distance bands and picks informative nodes within each band, using an attention gate. It plugs into existing models without redesign. Theory says it cures the imbalance, and broad benchmark tests back the claim across transformer and language-model graph systems.

Catalog record

CREATORZhibiao Wang, Yunlong Zhou, Ziwei Zhang, Mengmei Zhang, Shirui Pan, Chunming Hu, Xiao Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15845

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models Zhibiao Wang, Yunlong Zhou, Ziwei Zhang, Mengmei Zhang, Shirui Pan, Chunming Hu, Xiao Wang 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 predefined 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. 1 Introduction Graph data, as a powerful data structure for modeling relational information, is ubiquitous in real-world systems, ranging from social networks, citation networks, to molecular interaction networks [ 11 , 12 ] . To enable effective learning for graph data, Graph Neural Networks (GNNs) [ 5 , 6 , 35 , 36 , 41 ] have been proposed, which use message-passing to capture local structural signals and learn high-quality representations from graph data. However, GNNs face challenges such as over-smoothing and over-squashing with deeper layers [ 30 , 31 , 32 , 33 , 34 ] . To tackle these issues, Graph Transformers adopt the global attention mechanism of Transformers [ 16 ] to model long-range dependencies. Despite their effectiveness, Graph Transformers typically need to attend every pair of nodes in the input graph [ 15 , 17 ] , therefore incur high computational costs and limit their scalability for large graphs. More recently, to address the scalability limitations of global-attention Graph Transformers, Tokenized Graph Learning Models (TGLMs) have emerged as a promising paradigm by converting graphs into node-centric token lists (e.g., sequences of aggregated neighborhoods or sampled nodes) [ 9 , 26 , 10 ] . By reducing the input to token sequences with fixed lengths, TGLMs enable efficient attention computation while preserving the global signals via attention mechanisms. Besides accelerating conventional Graph Transformers, the tokenization approach aligns naturally with Large Language Models (LLMs), which has recently drawn considerable attention in the graph machine learning community, particularly for text-attributed graphs [ 52 , 51 , 50 ] . As a result, TGLMs have also been adopted in Graph LLMs to bridge graph structures with LLMs, enabling the powerful modeling and reasoning abilities of LLMs to more effectively handle graph tasks [ 1 , 13 ] . Despite their initial successes, the effectiveness of TGLMs critically relies on the design of the graph token list fed into the model. Existing works have proposed diverse strategies for token lists. For instance, VCR-Graphormer [ 10 ] , a representative Graph Transformer, uses personalized PageRank (PPR) [ 40 ] to inject cluster-level context into token lists. LLaGA [ 1 ] , a representative LLM for graph modeling, employs two fixed-template token lists: one aggregates neighborhood information via average pooling to form central node tokens, and another recursively samples neighborhood nodes to construct token sequences. Although these fixed-template token lists have shown performance in certain scenarios, a critical question remains unexplored: Do pre-defined token lists universally enhance TGLMs, or do they fail under certain scenarios? Investigating this question is critical given the structural diversity of real-world graphs. For example, many practical graphs exhibit relational patterns where neighborhood nodes carry inconsistent signals. Pre-defined strategies with fixed templates could inadvertently prioritize uninformative neighbors. To answer this question, we conduct preliminary experiments for different token lists templates (please refer to Section 4 for detailed settings and results). Strikingly, we observe that pre-defined token lists cannot universally enhance performance, but rather severely deteriorate the performance, especially on heterophilic graphs. The results are consistent across various datasets. To further analyze this phenomenon, we conduct extensive theoretical analyses for the effects of pre-defined token lists, especially for their failure cases. Our results reveal a previous unnoticed hop-overpriority problem : pre-defined strategies explicitly amplify the attention weights of nearby nodes in the token list, overwhelming the model’s ability to balance local and global signals. For example, on heterophilic graphs, where 1-hop neighbors are less informative due to low homophily, this over-prioritization of local nodes forces the model to rely on noisy signals, leading to suboptimal performance. Inspired by our preliminary analyses and to tackle the hop-overpriority problem, we propose Learnable Graph Token List (LGTL), a plug-and-play module designed to replace pre-defined graph token lists in TGLMs. Specifically, unlike fixed templates, LGTL adaptively assigns weights to nodes across different hops using a graph-attention gate module. This adaptive weighting allows LGTL to emphasize informative nodes contextually for both homophilic and heterophilic graphs. Furthermore, LGTL adopts a selection module to assign distinct weights to nodes within-hop, distinguishing the informativeness of individual neighbors beyond hop-level aggregation. We show that LGTL can be easily integrated into various TGLMs, including both Graph Transformers and Graph LLMs. Besides, we provide theoretical analyses to show that LGTL is effective in addressing the hop-overpriority problem. Extensive experiments on various benchmarks and diverse TGLM backbones validate that LGTL significantly improves the performance and effectively mitigates the hop-overpriority problem. We summarize our contributions as follows: • We empirically and theoretically characterize the hop-overpriority problem, a critical yet unexplored problem in pre-defined token lists for tokenized graph learning models covering both Graph Transformers and Graph LLMs, which is especially important for heterophilic graphs. • We propose LGTL, a flexible tokenization method that adaptively adjusts hop weights and prioritizes informative nodes within hops. We theoretically prove that LGTL can address the hop-overpriority problem. • We conduct extensive experiments on both homophilic and heterophilic datasets with various Graph Transformers and Graph LLMs as the backbone. Experiments demonstrate the effectiveness, compatibility and broad applicability of our method. 2 Related Works Graph Transformers and Tokenization . Graph Transformers, inspired by the attention mechanism of standard Transformers [ 16 ] , have advanced graph representation learning by capturing global structural dependencies [ 15 , 19 , 24 , 18 , 20 , 21 , 22 , 23 , 25 ] . Early works like GT [ 17 ] treat nodes as tokens and use dense self-attention over all node pairs to model interactions. However, this global-attention design faces scalability challenges for large graphs, spurring the development of tokenization-based architectures. Subsequent graph transformers with tokenization, such as NAGphormer [ 9 ] , shift focus to node-specific token lists

Read the complete text