本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL,并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力,发现等变层扩展了局部邻域之外的几何信息,高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。
Jan, 2023
本文提出了一种基于图双连通性的表达能力度量方法,发现大多数常见 GNN 架构在此度量下缺乏表达能力,但 ESAN 框架具有可证明的表达能力。作者进一步引入 GD-WL 模型,该模型可通过 Transformer 与 Weisfeiler-Lehman 算法相结合来计算表达能力,并通过实验表明其在绝大多数数据集上效果显著优于现有 GNN 架构。
基于 k 维 Weisfeiler-Leman(k-WL)层次结构的图学习架构在理论上具有良好的表达能力。然而,这样的架构通常在实际任务中无法提供可靠的预测性能,限制了它们的实际影响。相比之下,基于全局注意力的图变换器等架构在实践中表现出强大的性能,但是与 k-WL 层次结构的表达能力进行比较仍具有挑战性,特别是因为这些架构依赖于位置或结构编码来实现其表达能力和预测性能。为了解决这个问题,我们展示了最近提出的边界变换器(Edge Transformer),一种基于节点对而不是节点操作的全局注意力模型,具有至少 3-WL 的表达能力。在实证上,我们证明了边界变换器相对于其他理论上对齐的架构在预测性能方面的优势,同时不依赖于位置或结构编码。
Jan, 2024
揭示了从图形理论和基准审计中发掘 $k$-WL 不保证等距、可能与现实世界的图形任务无关,并且可能无法促进泛化或可靠性,同时提出了基于基准测试的表达能力的外延定义和测量,为构建此类基准测试提供了指导性问题,这对于进展图形机器学习至关重要。
Jul, 2023
本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络,并将此网络应用于图分类的任务中。实验表明,模型在数据集上表现的优异,证明了本文所提出的模型是有实用价值的。
May, 2019
系统研究了高阶图转换器和稀疏变体的理论表达能力,通过基于邻域信息的稀疏化,提高了传统模型的效率和表达能力。
Apr, 2024
本论文提出了一种基于子结构编码的、具有拓扑感知的信息传递方案 —— Graph Substructure Networks,并通过理论分析和实验评估证明其优于 Weisfeiler-Leman 测试,并在分子图和社交网络等多个领域取得了最先进的结果。
Jun, 2020
图分区神经网络(GPNNs)是一种新颖的 GNN 架构,通过对图进行分区以及顶点集和子图之间的结构相互作用的探索,提高了 GNN 的表达能力,并在各种图基准任务中展示了超越现有 GNN 模型的卓越性能。
Dec, 2023
使用张量语言以及 Weisfeiler-Leman 测试为模型分析提供了一种优雅的方法,通过索引和求和嵌套深度的简单分析得到了对 GNN 的分离能力的边界和某些类的普适性结果,并提供了一些提高 GNN 分离能力的见解。
Apr, 2022
本短文介绍了几个 Weisfeiler-Lehman 算法的变体,这些算法用于衡量图神经网络的表达能力, 并解释了 WL 和 folklore-WL 公式之间的区别。
Jan, 2022