图形神经网络扩展的理论比较
本文提供了一种统一的方法来研究增强次图 GNN 的架构,包括理论框架和对子图增强 GNN 可表达性的已知结果进行扩展,同时研究了三种用于学习采样子图的方法,通过实验证明了数据驱动架构可以提高标准基准数据集的预测精度,同时减少计算时间。
Jun, 2022
本文提出了一种基于图双连通性的表达能力度量方法,发现大多数常见 GNN 架构在此度量下缺乏表达能力,但 ESAN 框架具有可证明的表达能力。作者进一步引入 GD-WL 模型,该模型可通过 Transformer 与 Weisfeiler-Lehman 算法相结合来计算表达能力,并通过实验表明其在绝大多数数据集上效果显著优于现有 GNN 架构。
Jan, 2023
本文研究了图神经网络以及其理论背景并将其与 $1$-WL 算法相对比,提出了 $k$-dimensional GNNs 这一扩展方法,证明了它在处理社交网络和分子图像等高阶结构方面的有效性。
Oct, 2018
本研究提出一种使用特殊算法和线性代数工具来分析图神经网络 (GNNs) 的表征能力的方法,证明 NNG 可以优于 Weisfeiler-Lehman 算法,同时在图同构和图分类等数据集上进行充分实验证明了这种新型的 GNN 架构更具表达力的特点。
May, 2022
最近几年来,有大量的研究专注于扩展图神经网络(GNNs)的表达能力,超越 Weisfeiler-Lehman (1-WL) 框架。在这项研究中,我们从图搜索的角度探讨了 GNNs 的表达能力,提出了一种新的顶点着色方案,并证明经典的搜索算法可以高效地计算超越 1-WL 的图表示。我们展示了这种着色方案从图搜索中继承的有用特性,可以帮助解决图的双连通性问题。此外,我们还展示了在某些条件下,GNNs 的表达能力随着搜索邻域的半径逐层递增。为了进一步研究所提出的方案,我们基于广度优先搜索和深度优先搜索开发了一种新类型的 GNN,突出了它们在 1-WL 之上所能捕捉到的图属性。
Mar, 2024
使用张量语言以及 Weisfeiler-Leman 测试为模型分析提供了一种优雅的方法,通过索引和求和嵌套深度的简单分析得到了对 GNN 的分离能力的边界和某些类的普适性结果,并提供了一些提高 GNN 分离能力的见解。
Apr, 2022
本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL,并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力,发现等变层扩展了局部邻域之外的几何信息,高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。
Jan, 2023
本文对静态无向同质图和动态图、属性图等不同类型的图中图神经网络(GNNs)的表达能力进行了理论分析,提出了适当的 1-WL 测试,并证明了 GNNs 与 1-WL 测试在区分动态图和属性图上具有相同的能力,且 GNNs 可以模拟 1-WL 测试,包括大多数实际应用中使用的静态无向同质图(SAUHGs)等。
Oct, 2022
提出了一种基于 1-WL 和邻居之间的边缘考虑的 NC-1-WL 算法,实现了图同构测试,提高了图神经网络的可表达性;进一步提出了 NC-GNN 框架作为 NC-1-WL 的可微分神经版本,能够在各种基准测试中实现出色的性能。
Jun, 2022
本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络,并将此网络应用于图分类的任务中。实验表明,模型在数据集上表现的优异,证明了本文所提出的模型是有实用价值的。
May, 2019