走向基于原理的图变换

Jan, 2024

Towards Principled Graph Transformers

Luis Müller, Christopher Morris

TL;DR基于 k 维 Weisfeiler-Leman（k-WL）层次结构的图学习架构在理论上具有良好的表达能力。然而，这样的架构通常在实际任务中无法提供可靠的预测性能，限制了它们的实际影响。相比之下，基于全局注意力的图变换器等架构在实践中表现出强大的性能，但是与 k-WL 层次结构的表达能力进行比较仍具有挑战性，特别是因为这些架构依赖于位置或结构编码来实现其表达能力和预测性能。为了解决这个问题，我们展示了最近提出的边界变换器（Edge Transformer），一种基于节点对而不是节点操作的全局注意力模型，具有至少 3-WL 的表达能力。在实证上，我们证明了边界变换器相对于其他理论上对齐的架构在预测性能方面的优势，同时不依赖于位置或结构编码。

Abstract

graph learning architectures based on the k-dimensional Weisfeiler-Leman (k-WL) hierarchy offer a theoretically well-understood expressive power. However, such architectures often fail to deliver solid predictive

graph learning architectures k-dimensional weisfeiler-leman hierarchy global attention-based models expressive power edge transformer

发现论文，激发创造

将 Transformer 与 Weisfeiler-Leman 对齐

图神经网络架构与 $k$ 维 Weisfeiler--Leman（$k$-WL）层次结构相吻合，其在理论上具有良好的表达能力。然而，这些架构在实际应用中往往无法提供最先进的预测性能，从而限制了它们的实用性。最近的一些研究将图变换器架构与 $k$-WL 层次结构相结合，展示了有希望的实证结果，但是将变换器用于更高阶的 $k$ 仍然存在挑战，因为自注意力的运行时间和内存复杂度过高，并且存在不切实际的架构假设，例如不可行的注意力头数。在这里，我们推进了将变换器与 $k$-WL 层次结构相结合的研究，展示了每个 $k$ 更强的表达能力结果，使得它们在实践中更可行。此外，我们发展了一个理论框架，可用于研究已建立的位置编码，如拉普拉斯位置编码和 SPE。我们在大规模 PCQM4Mv2 数据集上评估了我们的变换器，展示了与最先进方法的竞争性预测表现，并在小尺度分子数据集上进行微调时展示了强大的下游性能。我们的代码可在此 https URL 找到。

Jun, 2024

关于高阶图变换器的理论表达能力和设计空间

系统研究了高阶图转换器和稀疏变体的理论表达能力，通过基于邻域信息的稀疏化，提高了传统模型的效率和表达能力。

Apr, 2024

大型图形表示中的 Transformer 简化与授权

本文旨在提出一个简化的图结构 Transformers 算法架构 (SGFormer)，该架构基于一个简单的 attention 模型，可在处理大规模图结构时实现高效信息传播，同时在节点属性预测基准测试中取得了出色的表现。

Jun, 2023

边缘变压器的系统化概括

提出了一种新型边缘 Transformer 模型，实现了自然语言理解中的系统化概括，并在关系推理、语义解析和依赖解析等几个设置中优于 Relation-aware、Universal 和传统 Transformer 基线模型。

Dec, 2021

图变换器的结构表达能力

介绍一种名为 SEG-WL 测试的算法，测试了结构编码对图 Transformer 的表达能力的影响，并提出了一种新的结构编码方法 Shortest Path Induced Subgraph。

May, 2023

将 Transformer 模型作为图到图模型

我们认为 Transformer 模型本质上是图到图的模型，序列只是一种特殊情况。注意力权重在功能上等价于图中的边。我们的图到图 Transformer 架构明确地表达了这个能力，通过将图的边作为输入用于注意力权重计算，并使用类似于注意力的函数预测图中的边，从而将显式图集成到预训练的 Transformer 模型中学习出的潜在图中。添加迭代的图优化过程提供了输入、输出和潜在图的联合嵌入，使得非自回归图预测能够优化完整图，无需任何专门的流水线或解码策略。实证结果表明，该架构在对各种语言结构建模方面取得了最先进的准确性，与预训练学习的潜在语言表示非常有效地集成在一起。

Oct, 2023

基于关系注意力的图结构任务通用 Transformer

本文描述了如何使用关系注意力处理图数据，以及在各种基准测试中比图神经网络做得更好的关系变压器。

Oct, 2022

大规模图的图转换器

本研究使用可扩展的图转换器（GT）框架来进行单个大规模图的表示学习，并提出了快速的采样技术和局部注意机制，以解决全局注意机制在大规模图上的计算复杂性问题。在三个大规模节点分类基准测试中，我们验证了 LargeGT 框架，并取得了 3 倍的加速和 16.8％的性能提升。

Dec, 2023

超图变换器用于半监督分类

通过全球节点和超边之间的全球关联以及捕捉节点和超边之间的局部连接性，提出了一种新颖的超图学习框架，称为 HyperGraph Transformer（HyperGT），该框架利用基于 Transformer 的神经网络结构来有效地处理超图结构化数据，实现了全面的超图表示学习，并在超图节点分类任务中取得了出色的性能，超过了现有方法，建立了新的基准水平。

Dec, 2023

有序子图聚合网络

本文提供了一种统一的方法来研究增强次图 GNN 的架构，包括理论框架和对子图增强 GNN 可表达性的已知结果进行扩展，同时研究了三种用于学习采样子图的方法，通过实验证明了数据驱动架构可以提高标准基准数据集的预测精度，同时减少计算时间。

Jun, 2022