Jul, 2023

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

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

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

    May, 2019

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

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

    Jan, 2022

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

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

    Sep, 2023

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

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

    Feb, 2024

  • 关于几何图神经网络表达能力的研究

    本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL，并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力，发现等变层扩展了局部邻域之外的几何信息，高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。

    Jan, 2023

  • kth 阶不变图网络的表达能力

    研究了图神经网络形式语言的表达能力，通过比较 k-WL 图同构测试，发现 kth-order 不变性（线性）图网络具有与 k-WL 相同的图区分能力，得出 k-WL 和 kth-order 不变性图网络在区分图形上相同的结论。

    Jul, 2020

  • 图神经网络的表达能力和逼近性质

    使用张量语言以及 Weisfeiler-Leman 测试为模型分析提供了一种优雅的方法，通过索引和求和嵌套深度的简单分析得到了对 GNN 的分离能力的边界和某些类的普适性结果，并提供了一些提高 GNN 分离能力的见解。

    Apr, 2022

  • Weisfeiler--Lehman goes Dynamic: 分析图神经网络在属性和动态图上的表现能力

    本文对静态无向同质图和动态图、属性图等不同类型的图中图神经网络（GNNs）的表达能力进行了理论分析，提出了适当的 1-WL 测试，并证明了 GNNs 与 1-WL 测试在区分动态图和属性图上具有相同的能力，且 GNNs 可以模拟 1-WL 测试，包括大多数实际应用中使用的静态无向同质图（SAUHGs）等。

    Oct, 2022

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

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

    Nov, 2018

  • 通过图二连通性重新思考 GNN 的表达能力

    本文提出了一种基于图双连通性的表达能力度量方法，发现大多数常见 GNN 架构在此度量下缺乏表达能力，但 ESAN 框架具有可证明的表达能力。作者进一步引入 GD-WL 模型，该模型可通过 Transformer 与 Weisfeiler-Lehman 算法相结合来计算表达能力，并通过实验表明其在绝大多数数据集上效果显著优于现有 GNN 架构。

    Jan, 2023