图不变的线性变换器（Graph-Agnostic Linear Transformers）

《Neural Networks》：Graph-Agnostic Linear Transformers

Graph Transformers (GTs) integrate local graph structures with global attention, but face computational overhead. We propose GALiT by decoupling graph structures and simplifying attention mechanisms. Graphs are used only to denoise node features before training, which are then cached and指导 Transformers. Simultaneously, we replace complex attention with weighted cosine similarity, reducing complexity to O(N+E) while maintaining performance. Experiments show GALiT outperforms GNNs and GTs on benchmarks, achieving high efficiency and effectiveness.

　　

郭志宇|刘阳|敖翔|唐亚腾|陈新焕|郑学浩|何清

机构：中国科学院计算技术研究所人工智能安全国家重点实验室 城市：北京 邮政编码：100190 国家：中国

摘要

图变换器（Graph Transformers，简称GTs）作为处理图结构数据的基础编码器，由于将局部图结构与全局注意力机制相结合，展现出了良好的性能。然而，复杂的注意力函数及其与图结构的耦合导致了显著的计算开销，尤其是在大规模图中。在本文中，我们将图结构与Transformer分离，并提出了图不可知线性变换器（Graph-Agnostic Linear Transformer，简称GALiT）。在GALiT中，图结构仅用于在训练前对原始节点特征进行去噪处理，因为我们的研究发现这些去噪后的特征已经整合了图结构的主要信息，可以替代图结构来指导Transformer的工作。通过将图结构从训练和推理阶段排除在外，GALiT成为了一个图不可知的模型，显著降低了计算复杂性。此外，我们简化了从传统Transformer继承的线性注意力函数，进一步减少了计算开销，同时仍然能够捕捉节点之间的关系。通过加权组合，我们将去噪后的特征整合到注意力机制中，理论分析表明线性注意力与去噪特征之间的协同作用对于提高表示多样性至关重要。尽管分离了图结构并简化了注意力机制，我们的模型在基准图上的表现仍优于大多数图神经网络（GNNs）和图变换器（GTs）。实验结果表明，GALiT在保持甚至提高性能的同时实现了高效率。

引言

在包含节点和边的图上进行学习是数据挖掘中的一个基本问题，在社会科学和自然科学中有广泛的应用（参见Ding等人（2025年）；郭等人（2025年）；李、陈、刘、王、何、程、敖（2024年），李、刘、敖、何（2023年）；刘、敖、冯、马、李、楚亚、何（2023b年），刘、敖、秦、池、冯、杨、何（2021年）；袁等人（2025年）的研究）。一个主要挑战是从图结构数据中提取有效的节点表示，以便用于各种下游任务，尤其是在计算资源有限的情况下。

作为新兴的基础编码器，图变换器（GTs）（参见Chen等人（2022a年）；Rampá?ek等人（2022年）；Wu等人（2023b年）；Ying等人（2021年））在图结构数据的节点表示学习方面表现出了良好的性能。与图神经网络（GNNs）（参见Gasteiger等人（2018年）；Kipf和Welling（2016年）；Veli?kovi?等人（2017年）；Wu等人（2019年）不同，GTs通过从所有节点自适应地聚合信息，并利用了来自传统Transformer（Vaswani等人，2017年）的全局注意力机制。同时，它们利用图结构生成边嵌入（Rampá?ek等人，2022年），指导注意力权重的学习（Wu等人，2022b年），或者直接将Transformer与GNNs结合（Wu等人，2023b年）。因此，由于图结构与Transformer的结合，GTs能够在捕捉全局潜在关系的同时利用局部关系信息，从而比GNNs具有更强的表达能力。然而，这些优势是以效率为代价的，这限制了GTs在大规模图上的应用。

图结构与Transformer的耦合是影响GTs可扩展性的主要因素。已经有许多努力（参见Chen等人（2022b年）；刘等人（2023a年）；Wu、Zhao、Li、Wipf、Yan（2022b年），Wu、Zhao、Yang、Zhang、Nie、Jiang、Bian、Yan）致力于提高GTs的可扩展性。SGFormer（Wu等人，2023b年）将Transformer与浅层GNN结合以提高可扩展性，但牺牲了多层GNN的表达能力，并未消除图结构引入的计算开销。相比之下，我们认为将图结构与Transformer分离是消除图结构引起的复杂性的更有效方法。为了说明这一点，我们首先使用图结构对原始节点特征进行去噪处理，然后将去噪后的特征直接放入两层MLP中，而不使用图结构信息。图1中的结果显示，带有去噪特征的MLP在效率和效果方面都表现得更好。因此，我们相信去噪后的原始节点特征已经整合了图结构的主要信息，可以用来指导Transformer内的自适应聚合过程。

此外，现有GTs中的复杂注意力函数引入了不必要的计算开销，并增加了过拟合的风险。具体来说，特征向量通过单独的线性变换转换为查询向量和键向量，然后使用缩放的点积计算注意力权重。为了降低传统Softmax注意力（Vaswani等人，2017年）的高复杂度，最近的研究（Rampá?ek等人（2022年）；Wu、Yang、Zhao、He、Wipf、Yan，Wu、Zhao、Li、Wipf、Yan，2022b年，Wu、Zhao、Yang、Zhang、Nie、Jiang、Bian、Yan）将线性注意力（Han等人，2023年；Katharopoulos等人，2020年）引入到GTs中，从而实现了较低的计算复杂度，使其适用于大规模图。为了进一步简化线性注意力机制并减少计算开销，我们用低参数的加权或映射余弦相似度替换了复杂的注意力函数。此外，通过加权组合，我们将去噪特征整合到注意力机制中，理论分析表明线性注意力与去噪特征之间的协同作用对于提高表示多样性至关重要。实验结果表明，我们的简化可以在保持节点间关系的同时减少计算开销。

在本文中，我们将上述两种技术——分离图结构和简化注意力机制——整合到通用的GT框架中，并提出了我们的模型GALiT（Graph-Agnostic Linear Transformer）。在GALiT中，图结构仅用于在训练前获得去噪后的原始节点特征。这些预处理后的特征被缓存，然后用于指导Transformer内的自适应聚合过程。因此，GALiT在训练和推理阶段对图结构是不可知的。这一区别至关重要，因为它通过将图依赖性限制在一次性的低成本预处理步骤中，显著降低了计算复杂性。此外，我们简化了从传统Transformer继承的线性注意力函数，进一步减少了计算开销，同时仍然能够捕捉节点之间的关系。尽管分离了图结构并简化了注意力机制，我们的模型在基准图上的表现仍优于大多数GNNs和GTs。实验结果表明，GALiT在保持甚至提高性能的同时实现了高效率。除了当前的结果，我们相信所提出的方法可以为简化图编码器的设计开辟新的技术路径。

总结来说，我们的贡献如下：

• 我们发现将图结构与Transformer分离是降低图变换器计算复杂性的有效方法。
• 我们使用加权或映射形式的余弦相似度简化了GTs中的传统线性注意力机制，进一步减少了计算开销，同时仍然能够捕捉节点之间的关系。
• 我们在同质图、异质图和大规模图上进行了广泛的实验，以验证所提模型的合理性和有效性。

本文的其余部分安排如下：第2节介绍本文的定义和问题陈述。第3节详细介绍了提出的GALiT框架，第4节展示了实验结果。第5节回顾了相关文献，第6节总结了本文。

初步内容

定义

我们用表示一个图，其中节点集包含N个节点，边集包含E条边（包括自环）。每个节点都与一个D维的特征向量相关联，所有节点特征表示为。图的结构可以用邻接矩阵A?∈?{0, 1}^N?×?N表示，其中表示存在自环的情况，否则表示不存在自环。此外，我们将所有节点标签表示为one-hot向量Y?∈?{0, 1}^N?×?C，其中C是类别的数量。

方法论

在本节中，我们将详细阐述分离图结构和简化注意力机制的两种技术，并将它们整合到通用的GT框架中。

实验

在本节中，我们对提出的GALiT模型在基准数据集上进行了全面评估，旨在回答以下研究问题：

• •
  RQ1： GALiT在基准图上的表现是否优于现有最先进的方法？
• •
  RQ2：
  GALiT在大规模图上的可扩展性和效率如何？

•

RQ3：

关键组件如何贡献于GALiT的性能？

•

RQ4：

GALiT对不同超参数的敏感性如何？

•

RQ5：

实证研究的结果如何？

图神经网络

构建具有强大表达能力的GNN在图机器学习中是基础。GNN通常采用消息传递范式，从相邻节点递归地聚合信息以生成表示。早期模型（如GCN，Kipf和Welling，2016年）直接利用观察到的结构进行消息传递。后续模型（如GAT，Veli?kovi?等人，2017年）将注意力机制集成到观察到的结构中，使得消息传递受到...

结论

在这项工作中，我们提出了图不可知线性变换器（GALiT），这是一个适用于大规模图的简化图变换器框架。在GALiT中，我们首先利用图结构获得训练前的去噪原始节点特征。然后使用这些去噪特征来指导Transformer的工作。此外，我们简化了从传统Transformer继承的注意力函数，进一步减少了计算开销...

未引用的表格

缺失的引用表格3

CRediT作者贡献声明

郭志宇：撰写——审稿与编辑，撰写——初稿，可视化，验证，方法论，调查，形式分析，数据整理，概念化。刘阳：撰写——审稿与编辑，监督，项目管理，资金获取。敖翔：监督，项目管理，资金获取。唐亚腾：资源提供。陈新焕：资源提供。郑学浩：资源提供。何清：监督，项目管理，资金获取。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。

致谢

本研究工作得到了国家自然科学基金（项目编号62406307、62576333和62476263）和中国科学院战略性先导科技专项（项目编号XDB0680201）的支持。敖翔还得到了北京市自然科学基金（项目编号JQ25015）和信息通信技术创新基金（CAS，项目编号E461060）的支持。刘阳还得到了中国博士后科学基金会（CPSF）的博士后奖学金（项目编号GZB20240761）的支持。