提出无需位置编码的稀疏图Transformer,通过可控感受野提升效率与性能。
HopFormer: Sparse Graph Transformers with Explicit Receptive Field Control
- 用头级n跳掩码稀疏注意力显式控制感受野
- 计算复杂度随掩码稀疏度线性增长,性能优于或媲美全局注意力
- 适用于不同结构的图,尤其在小世界图上局部注意力更稳定
图Transformer通常依赖显式的位置或结构编码以及密集的全局注意力来融入图拓扑。本文表明,这两者并非必需。我们提出HopFormer,一种仅通过头特定的n跳掩码稀疏注意力注入结构信息的图Transformer,不使用位置编码或架构修改。该设计实现了显式且可解释的感受野控制,同时支持真正稀疏的注意力,其计算成本随掩码稀疏度线性增长。在节点级别和图级别基准上的大量实验表明,该方法在多种图结构上均达到竞争性或更优性能。结果进一步揭示:密集全局注意力往往非必要;在具有强小世界特性的图上,局部注意力表现更稳定且持续高效;而在小世界效应较弱的图上,全局注意力收益递减。这些发现挑战了图Transformer设计中的主流假设,凸显稀疏可控注意力作为一种原则性且高效的替代方案。
原文摘要 · Abstract (English)
Graph Transformers typically rely on explicit positional or structural encodings and dense global attention to incorporate graph topology. In this work, we show that neither is essential. We introduce HopFormer, a graph Transformer that injects structure exclusively through head-specific n-hop masked sparse attention, without the use of positional encodings or architectural modifications. This design provides explicit and interpretable control over receptive fields while enabling genuinely sparse attention whose computational cost scales linearly with mask sparsity. Through extensive experiments on both node-level and graph-level benchmarks, we demonstrate that our approach achieves competitive or superior performance across diverse graph structures. Our results further reveal that dense global attention is often unnecessary: on graphs with strong small-world properties, localized attention yields more stable and consistently high performance, while on graphs with weaker small-world effects, global attention offers diminishing returns. Together, these findings challenge prevailing assumptions in graph Transformer design and highlight sparsity-controlled attention as a principled and efficient alternative.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。