关于几何图神经网络表达能力的研究
本文提出了一种基于图双连通性的表达能力度量方法,发现大多数常见 GNN 架构在此度量下缺乏表达能力,但 ESAN 框架具有可证明的表达能力。作者进一步引入 GD-WL 模型,该模型可通过 Transformer 与 Weisfeiler-Lehman 算法相结合来计算表达能力,并通过实验表明其在绝大多数数据集上效果显著优于现有 GNN 架构。
Jan, 2023
本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络,并将此网络应用于图分类的任务中。实验表明,模型在数据集上表现的优异,证明了本文所提出的模型是有实用价值的。
May, 2019
本文提出了一个理论框架,可以比较图神经网络架构的表达能力,证明了实用 GNN 的第一近似保证,FGNN 被证明是最具表现力的架构之一,在 Quadratic Assignment Problem 中的应用表明 FGNN 能够比现有的基于谱、SDP 或其他 GNN 架构的算法表现得更好。
Jun, 2020
本研究提出一种使用特殊算法和线性代数工具来分析图神经网络 (GNNs) 的表征能力的方法,证明 NNG 可以优于 Weisfeiler-Lehman 算法,同时在图同构和图分类等数据集上进行充分实验证明了这种新型的 GNN 架构更具表达力的特点。
May, 2022
本文对静态无向同质图和动态图、属性图等不同类型的图中图神经网络(GNNs)的表达能力进行了理论分析,提出了适当的 1-WL 测试,并证明了 GNNs 与 1-WL 测试在区分动态图和属性图上具有相同的能力,且 GNNs 可以模拟 1-WL 测试,包括大多数实际应用中使用的静态无向同质图(SAUHGs)等。
Oct, 2022
图分区神经网络(GPNNs)是一种新颖的 GNN 架构,通过对图进行分区以及顶点集和子图之间的结构相互作用的探索,提高了 GNN 的表达能力,并在各种图基准任务中展示了超越现有 GNN 模型的卓越性能。
Dec, 2023
本研究介绍了一种基于图神经网络 (GNN) 计算等变多项式的表达能力层级方法,并提出了一种新的具有更具体指导意义的算法工具来评估 GNN 表达能力。同时,通过增加多项式特征或其他操作 / 聚合的方法,提高了 GNN 架构的表达能力,实现了在多个图形学习基准中的最新结果。
Feb, 2023
使用张量语言以及 Weisfeiler-Leman 测试为模型分析提供了一种优雅的方法,通过索引和求和嵌套深度的简单分析得到了对 GNN 的分离能力的边界和某些类的普适性结果,并提供了一些提高 GNN 分离能力的见解。
Apr, 2022
基于同态表示的图神经网络(Graph Neural Networks)的表达能力及其在子图计数等实际需求方面的量化研究。
Jan, 2024