Apr, 2019

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

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

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

    Oct, 2018

  • 维斯费勒和勒曼进入了机器学习：迄今为止的故事

    该论文综述了基于 Weisfeiler-Leman 算法的算法和神经结构，其在机器学习中具有图形和关系数据方面的强大功能，特别是在监督式学习方面。此外，该论文还讨论了算法的理论背景，如何在有监督的图形和节点表示学习中使用它，并概述了连接到神经结构的算法扩展和当前应用和未来方向的概述，以刺激进一步的研究。

    Dec, 2021

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

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

    Feb, 2024

  • 使用 Weisfeiler-Leman 算法进行图机器学习的实力

    本文全面概述了基于 Weisfeiler-Leman 算法的机器学习及其在监督学习、图和节点分类、神经架构连接等方面的应用及未来方向。

    May, 2021

  • 将 Transformer 与 Weisfeiler-Leman 对齐

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

    Jun, 2024

  • 关系 Weisfeiler-Leman 预测理论

    我们的研究旨在系统理解知识图谱中图神经网络的表达能力和局限性，并通过关系 Weisfeiler-Leman 算法对不同模型的表现进行表征，最终阐明了一些常用的实际设计选择的优势。

    Feb, 2023

  • Wasserstein Weisfeiler-Lehman 图核

    本文介绍了一种基于 Wasserstein 距离和 Weisfeiler-Lehman embedding 的新型图卷积核方法，以图像高维对象的方式比较图结构之间的相似性并在多个图分类任务上提高了预测性能。

    Jun, 2019

  • 利用本地化提高图神经网络的表达能力

    本文提出局部 Weisfeiler-Leman（WL）算法以提高表达能力和降低计算复杂度，并解决所有 k 的局部 k-WL 的子图计数问题。研究证明，本地 k-WL 可以表达更多模式，但在表达能力上最多与 (k + 1) -WL 一样，比应用于整个图的 k-WL 更具有时间和空间效率。用局部 k-WL 等效的两个图的子图和诱导子图的计数是不变的。该算法也引入了局部和递归的 Layer k-WL 以及一个可扩展片段技术，可用于任意 k，以保证使用仅 1-WL 的确切计数，同时比 Papp 和 Wattenhofer（2022a）提到的 GNN 层次更具表达能力。

    May, 2023

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

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

    Jan, 2022

  • 关于 Weisfeiler-Leman 不变性的子图计数和相关图属性

    本文主要研究维斯费勒 - 利曼算法在子图模式匹配中的应用，关注于 $k=1,2$ 的情况下，探究满足 $k$-WL 不变性的子图模式，其发生次数也同样具有 $k$-WL 不变性，最终在 $k=1$ 和 $k=2$ 情况下得出完整结论。

    Nov, 2018