3-(F) WL 是否足够区分所有的三维图形?
本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络,并将此网络应用于图分类的任务中。实验表明,模型在数据集上表现的优异,证明了本文所提出的模型是有实用价值的。
May, 2019
揭示了从图形理论和基准审计中发掘 $k$-WL 不保证等距、可能与现实世界的图形任务无关,并且可能无法促进泛化或可靠性,同时提出了基于基准测试的表达能力的外延定义和测量,为构建此类基准测试提供了指导性问题,这对于进展图形机器学习至关重要。
Jul, 2023
本文主要研究维斯费勒 - 利曼算法在子图模式匹配中的应用,关注于 $k=1,2$ 的情况下,探究满足 $k$-WL 不变性的子图模式,其发生次数也同样具有 $k$-WL 不变性,最终在 $k=1$ 和 $k=2$ 情况下得出完整结论。
Nov, 2018
本短文介绍了几个 Weisfeiler-Lehman 算法的变体,这些算法用于衡量图神经网络的表达能力, 并解释了 WL 和 folklore-WL 公式之间的区别。
Jan, 2022
本文研究了图神经网络的表达能力与 Weisfeiler-Leman 测试的关联,提出了 WL 维度的精确特征,并给出了子图计数问题的 WL 维度的多项式时间算法,回答了之前的研究中的一个开放问题。
Sep, 2023
研究了图神经网络形式语言的表达能力,通过比较 k-WL 图同构测试,发现 kth-order 不变性(线性)图网络具有与 k-WL 相同的图区分能力,得出 k-WL 和 kth-order 不变性图网络在区分图形上相同的结论。
Jul, 2020
证明了所有有限平面图的 Weisfeiler-Leman (WL) 维度至多为 3,并使用至多 4 个变量的一阶逻辑可定义每个有限平面图。通过分类讨论得出 3 联通平面图的分类,并证明了 3 维 WL 算法可以确定 3 联通平面图的轨道。
Aug, 2017
研究了使用递归 $k$-dim WL 方法构造的 Cai、F"{u} rer 和 Immerman 以及 Evdokimov 和 Ponomarenko 等 '$k$- 等价 ' 图族的属性,提出了一种递归 $k$-dim WL 方法的扩展,该方法能够在一定条件下高效地描述所有这些类型的 ' 反例 ' 图,这些假设在所有已知情况下均成立。
Jan, 2011
本文通过扩展 $2$-WL 测试,研究了图神经网络在处理包含位置和速度的点云数据方面的表达能力,并建立了能够处理位置 - 速度对、具有置换和刚体运动等等变换性质的函数的 WeLNet 体系结构,并通过实验验证了它在动力学任务和分子构象生成任务上取得了新的最先进结果。
Feb, 2024
本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL,并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力,发现等变层扩展了局部邻域之外的几何信息,高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。
Jan, 2023