江苏龙网

  1. 首页 > 人文 > >

技术编程剖析图神经网络的表达能力和Weisfeiler-Lehman检验( 二 )


Keyulu Xu提出了一种聚合和更新特征的选择 ， 这些特征使消息传递神经网络等效于WL算法 ， 将它们称为图同构网络（GIN） 。 这与标准的消息传递神经网络所具有的功能一样强大 。
但是 ， 不仅仅是一种新的体系结构 ， 主要的影响是在一个简单的环境中提出了表达性问题 ， 这可能与图论中的经典问题有关 。 这个想法已经激发了许多后续工作 。
Weisfeiler-Lehman层次结构
扩展Xu和Morris结果的一个方向是使用更强大的图形同构测试 。 由LászlóBabai提出的k-WL检验是Weisfeiler-Lehman算法的高阶扩展 ， 该算法适用于k个元组而不是单个节点 。 与1-WL和2-WL测试 ， 是等效的 ， 除外（k+1）-WL比k-WL更严格更强 ， 对于任何k ≥2 ， 即存在着在其上的图形的例子k -WL失败,但（k +1）-WL成功 ， 反之亦然 。 因此 ， k-WL是一个层次结构或特征越来越强大的图同构测试 ， 有时也称为Weisfeiler-Lehman层次结构 。
可以设计遵循k -WL测试的图神经网络 ， 因此比消息传递体系结构更强大 。 Morris提出了一个这样的第一个架构 ， k -GNN 。 通过神经网络和诸如高阶GNNS传统消息之间的主要差异是 ， 它们是非本地 ， 作为k -WL算法上操作k节点的元组 。 这对算法的实现及其计算和内存复杂性都具有重大影响：k -GNN需要（n?）个内存 。 为了减少复杂性 ， Morris设计了k-GNN的局部版本 ， 基于局部邻域的聚合 ， 但是其表达能力不如k -WL 。
Haggai Maron提出了一些不同的高阶图体系结构 。 我于2019年9月参加了会议 。 Maron 基于k阶张量定义了一类不变图网络（IGN） ， 并显示出它们与k -WL 一样强大 。 IGNs从一个不同的变体衍生k -WL， 并且在与它们的复杂性方面更有利k -GNNs 。 尤其是 ， 等效于3-WL的IGN具有"仅"二次复杂度 ， 这可能是唯一实际上比消息传递更强大的 ， 实用的图神经网络架构 ， 但与前者的线性复杂度相去甚远 。 从理论上讲 ， 可证明强大的图神经网络的工作提供了严格的数学框架 ， 可以帮助解释和比较不同的算法 。 有许多后续工作使用图论和分布式局部算法的方法扩展了这些结果 。
但是 ， 从实际的角度来看 ， 这些新架构几乎没有产生重大影响：例如 ， 最新的基准测试表明 ， 最近可证明强大的算法实际上不及旧技术 。 在机器学习中 ， 这并不是一种罕见的情况 ， 在理论和实践之间通常存在很大的差距 。 一种解释可能是基准本身的不足 。 但是 ， 也许更深刻的原因是 ， 更好的表现力并不一定能提供更好的概括性（有时恰恰相反） ， 此外 ， 图同构模型可能无法正确捕捉特定应用中图相似性的实际概念 。
可以肯定的是 ， 这一系列工作对于建立与其他学科的桥梁以及将以前在深度学习领域中未使用的方法引入图上而言是非常富有成果的 。


推荐阅读


上一篇：互联网「庆余年先发制人」被判违约：模式本身是对的，吃相不能太难看

下一篇：茂哥|梦幻西游：茂哥暑期物价走势预测 教师节海马和百岁会涨价