ICLRMar, 2024

Weisfeiler 和 Leman 的循环：图形表示学习的新层次结构

PDF
TL;DR介绍了一种新的图同构测试层次结构和相应的 GNN 框架，可以计算长度为 r+2 的环的数量，并且能够计算仙人掌图的同态数量，实验证明该框架在多个合成数据集上具有表达能力和计数能力，并在多个真实数据集上取得了最先进的预测性能。
发现论文，激发创造
  • Weisfeiler 和 Leman 进化为神经网络：高阶图神经网络

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

    Oct, 2018

  • 可证明强大图网络

    本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络，并将此网络应用于图分类的任务中。实验表明，模型在数据集上表现的优异，证明了本文所提出的模型是有实用价值的。

    May, 2019

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

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

    Jan, 2022

  • Weisfeiler Leman 对于欧几里德等变机器学习的应用

    本文通过扩展 $2$-WL 测试，研究了图神经网络在处理包含位置和速度的点云数据方面的表达能力，并建立了能够处理位置 - 速度对、具有置换和刚体运动等等变换性质的函数的 WeLNet 体系结构，并通过实验验证了它在动力学任务和分子构象生成任务上取得了新的最先进结果。

    Feb, 2024

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

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

    Feb, 2024

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

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

    Nov, 2018

  • 关于 Weisfeiler-Leman 测试对图形模体参数的能力

    本文研究了图神经网络的表达能力与 Weisfeiler-Leman 测试的关联，提出了 WL 维度的精确特征，并给出了子图计数问题的 WL 维度的多项式时间算法，回答了之前的研究中的一个开放问题。

    Sep, 2023

  • 通过重新思考 Weisfeiler-Lehman 传说走向在 $O (n^2)$ 空间内任意表达的 GNNs

    本文提出了一种新的图神经网络的框架 $k$-FWL+，并探究其表达能力及其设计空间的灵活性，使用此框架设计的 N2-GNN 在 ZINC-Subset 和 ZINC-Full 两个数据集上显示了比之前最先进的结果更好的性能。

    Jun, 2023

  • 限制距离的民间传说 Weisfeiler-Leman GNNs 具备可证明的循环计数能力

    我们提出了一种新的 GNN 模型，$d$-DRFWL (2) GNNs，通过在原始图中对限制距离的节点对进行信息传递，避免了子图 GNN 模型中昂贵的子图提取操作，从而降低了时间和空间复杂度。实验证实了我们的理论，我们的模型在计算 3、4、5、6 环等循环结构时是迄今为止效率最高的 GNN 模型。

    Sep, 2023

  • 图神经网络的细粒度表达能力

    该研究探讨了基于图神经网络的表达能力，提出了一种连续化的方法来反映图之间的相似程度并给出了各种拓扑特征的理论框架来描述基于树距离的图表达能力。

    Jun, 2023