May, 2023

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

PDF
TL;DR本文提出局部 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 层次更具表达能力。
weisfeiler-lemansubgraph countinglocalized versionslayer k-wlrecursive k-wl
发现论文，激发创造
  • 关于 Weisfeiler-Leman 不变性的子图计数和相关图属性

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

    Nov, 2018

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

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

    Sep, 2023

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

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

    Feb, 2024

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

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

    Jun, 2023

  • 有序子图聚合网络

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

    Jun, 2022

  • 从关系池化到子图 GNN：更具表现力的图神经网络的通用框架

    本文提出了一种通过为节点分配标签来提高信息传递神经网络表达能力的方法，并将其扩展到更高维的 WL，实现了比以往任何基于 WL 的方法更广泛的 GNN 框架。我们证明了 $k,l$-GNN 在理论和实验中都具有提高表达能力的能力和广泛适用性。

    May, 2023

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

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

    Apr, 2019

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

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

    Jul, 2023

  • 可证明强大图网络

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

    May, 2019

  • 图形神经网络扩展的理论比较

    本文研究和比较了不同的图神经网络扩展方法，包括基于更高阶 Weisfeiler-Leman 方法、对图中小子结构进行预处理、对图进行局部预处理和计算嵌入等方法，并通过一系列实例构造比较了这些方法的表达能力。

    Jan, 2022