ICMLJun, 2024

将 Transformer 与 Weisfeiler-Leman 对齐

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

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

    Jan, 2024

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

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

    Apr, 2024

  • Weisfeiler 和 Leman 稀疏化：走向可伸缩的高阶图嵌入

    本文提出一种基于 Weisfeiler-Leman 算法和神经网络架构的图核方法，能够处理高阶交互，同时具有表达能力、可扩展性和防止过拟合等优点。实验表明，与原算法相比，局部算法（包括核和神经体系结构）具有快速计算时间和防止过拟合的优势，并且在多个基准数据集上实现了最新的图分类技术成果，同时展现了在大规模分子回归任务上的性能。

    Apr, 2019

  • Weisfeiler 和 Leman 进化为神经网络：高阶图神经网络

    本文研究了图神经网络以及其理论背景并将其与 $1$-WL 算法相对比，提出了 $k$-dimensional GNNs 这一扩展方法，证明了它在处理社交网络和分子图像等高阶结构方面的有效性。

    Oct, 2018

  • Weisfeiler 和 Lehman 度量建模：探究 WL 检验的有效性

    揭示了从图形理论和基准审计中发掘 $k$-WL 不保证等距、可能与现实世界的图形任务无关，并且可能无法促进泛化或可靠性，同时提出了基于基准测试的表达能力的外延定义和测量，为构建此类基准测试提供了指导性问题，这对于进展图形机器学习至关重要。

    Jul, 2023

  • 边缘上的 Weisfeiler-Leman：当更多的表达能力很重要

    增强 Weisfeiler-Leman 算法和消息传递图神经网络的表达力的关系对于改进概括能力的条件是不明确的。通过引入子图信息和经典边界理论来探索这种表达力增强和概括能力改善的条件，并提出具有可证明概括性质的基于 $1$-WL 的核和消息传递图神经网络架构的变体。

    Feb, 2024

  • 有序子图聚合网络

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

    Jun, 2022

  • 关于 Weisfeiler-Lehman 测试及其变体的简短教程

    本短文介绍了几个 Weisfeiler-Lehman 算法的变体，这些算法用于衡量图神经网络的表达能力， 并解释了 WL 和 folklore-WL 公式之间的区别。

    Jan, 2022

  • 图变换器的结构表达能力

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

    May, 2023

  • 关系图变换器：用于知识图表示的关系图转换器

    本研究提出了一种新型变压器架构 Relphormer，其中引入 Triple2Seq 来动态采样上下文化子图序列作为输入以解决知识图谱中异构结构和语义信息难以捕获的问题，并提出了一种 novel self-attention 机制以编码关系信息。实验结果表明，相比基线模型，Relphormer 获得了更好的性能。

    May, 2022