arXiv:2505.15845cs.LG2025-05

提出自适应分词机制,解决图模型中邻近节点过度优先的问题。

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

  • 设计可学习的图分词列表,动态调整跨跳权重和节点优先级
  • 在异质图上显著提升性能,尤其改善远距离依赖捕捉能力
  • 适用于各类图Transformer与图LLM,即插即用且理论可证

图Transformer利用全局注意力捕捉图结构中的长程依赖,显著推动了图机器学习的发展,但面临计算复杂度过高的问题。分词图学习模型(TGLMs)通过将图转换为有序分词列表实现可扩展处理,同时使大语言模型更有效地处理带文本属性的图,在图LLM中也得到应用。然而,现有TGLMs依赖人工设计的分词列表,其对不同图学习场景的适应性尚未探索。本文首次对人工分词列表进行广泛的实证与理论研究,发现一个未被关注的‘跨跳优先’问题:预定义分词列表过度强调邻近节点,削弱了TGLMs平衡局部与全局信号的能力,尤其在异质图中危害严重。为此,我们提出可学习图分词列表(LGTL),作为TGLMs中替代人工分词列表的即插即用模块。具体而言,LGTL通过图注意力门控模块自适应调整跨跳权重,并通过选择模块在每跳内优先选择信息量高的节点。该方法可自适应增强上下文相关节点的重要性,适用于同质与异质图。此外,我们从理论上证明了LGTL能缓解跨跳优先问题。大量实验在多个基准数据集上验证了其在图Transformer与图LLM骨干网络中的有效性。

原文摘要 · Abstract (English)

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.

图神经网络自适应分词注意力机制图模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。