用图随机特征实现线性注意力的拓扑掩码，提升图数据建模效率。
Linear Transformer Topological Masking with Graph Random Features
- 将拓扑掩码参数化为加权邻接矩阵的可学习函数，引入强结构先验
- 通过图随机特征近似，实现线性注意力下的 $oldsymbol{ ext{O}(N)}$ 复杂度
- 在超3万节点的图像与点云任务中显著提效，适合大规模图数据
在图结构数据上训练变换器时，融入底层拓扑信息对性能至关重要。拓扑掩码作为一种相对位置编码，通过调整查询与键之间的注意力权重来实现这一目标。本文提出将拓扑掩码参数化为加权邻接矩阵的可学习函数——一种新颖且灵活的方法，引入了强大的结构归纳偏置。通过图随机特征近似该掩码（我们证明了首个已知的浓度界），展示了如何使其完全兼容线性注意力，保持相对于输入标记数的 $ ext{O}(N)$ 时间和空间复杂度。此前最快的替代方案为 $ ext{O}(N ext{log} N)$，且仅适用于特定图结构。高效的掩码算法在图像和点云任务中带来显著性能提升，支持超过3万节点的数据。
原文摘要 · Abstract (English)
When training transformers on graph-structured data, incorporating information about the underlying topology is crucial for good performance. Topological masking, a type of relative position encoding, achieves this by upweighting or downweighting attention depending on the relationship between the query and keys in a graph. In this paper, we propose to parameterise topological masks as a learnable function of a weighted adjacency matrix -- a novel, flexible approach which incorporates a strong structural inductive bias. By approximating this mask with graph random features (for which we prove the first known concentration bounds), we show how this can be made fully compatible with linear attention, preserving $\mathcal{O}(N)$ time and space complexity with respect to the number of input tokens. The fastest previous alternative was $\mathcal{O}(N \log N)$ and only suitable for specific graphs. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data, including with $>30$k nodes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。