江苏龙网

  1. 首页 > 人文 > >

韭菜花音乐|中科院计算所沈华伟：图神经网络表达能力的回顾和前沿( 三 )


文章图片
所以 ， 另外一个表达能力的限制就来自于图的结构 。 下面看两个简单的例子 ， 左上角的图都是24个碳原子 ， 有两个有机化学的分子式：左边的结构是两层 ， 一层12个碳 ， 24个碳分成平行的两层 ， 都和自己的邻居相连 。 右边图是24个碳结构变成一个正球体 ， 每个面都由五个碳构成 。 这两个结构 ， 人一眼就能看出它俩的不同 ， 但是GCN无法区分 ， 即使把层次加深到无穷多层也区分不了它俩 。 即使简化成左下角两个更加简单的图 ， GCN也区分不出来 。 所以 ， 这给出的启示是：通过提升GCN的深度来提升图的表达能力 ， 是无法做到的 。 那么它的表达能力受限在哪儿？既然是图的结构相关 ， 那我们就想到可以采用WL-test ， 对两个图是否同构进行测试 。 WLtest的主要是通过聚合节点邻居的label ， 然后通过hash函数得到节点新的label ， 不断重复知道每个节点的label稳定不变 。 稳定后 ， 统计两张图的label的分布 ， 如果分布相同 ， 则一般认为两张图时同构的 。 所以 ， WLtest递归聚合邻居的方式和GNN类似 ， 都是一个递归地来更新自己的特征 ， 只不过更新的方式 ， WLtest做了一个单射函数 ， 但是GNN用的聚合函数 ， 无论是Max、Mean还是Sum ， 大部分情况下都不是单射的 。 也就是说GNN非单射的聚合方式 ， 把原本不一样的东西聚合后变得一样了 ， 这让GNN丧失了表达能力 。 更直白一些 ， WLTest是一个单射函数 ， GNN不是单射函数 ， 于是WLTest为GNN的表达能力提供了一个理论上的上界 。 （注：这里GNN说的是通过邻居聚合 ， 如果别的聚合方式 ， 性能可能超过WLtest的）
韭菜花音乐|中科院计算所沈华伟：图神经网络表达能力的回顾和前沿
文章图片
为什么当前流行的GNN ， 例如GCN、GraphSAGE为什么不是单射呢？原因有两个 ， 一个是每层做特征变换做得不够；另一个是 ， 这些图神经网络用的聚合函数天然具有单射属性 。 所以 ， 在论文《HowPowerfulareGraphNeuralNetworks》中 ， 作者提出来了新的图模型GIN(GraphIsomorphismNetwork) ， 其中I表示图同构 ， 关键思想是构建了一个单射函数 。 有了单射函数 ， GIN也达到了和WLtest类似的表达能力 ， 达到了图神经网络表达能力的上界 。
韭菜花音乐|中科院计算所沈华伟：图神经网络表达能力的回顾和前沿
文章图片
后来作者对GIN模型的表达能力进行了验证 ， 具体是用数据的拟合能力进行测评 ， 验证思想是：如果表达能力足够强 ， 那么数据集上的每个数据都能精确拟合 。 验证结果确实符合作者的预期 ， 通过构造一个单设的聚合函数 ， 能够实现和WLTest一样的表达能力 。 那么 ， 泛化能力如何呢？也即在TestLoss表现如何呢？这里有一个直观上的事实是 ， 如果TrainingLoss做得不好 ， 那么TestLoss表现也不会好 ， 毕竟Train是Test的基准 ， 另外 ， 如果训练集上表现非常好 ， 而在测试集上表现非常差 ， 那么就出现过拟合现象 ， 没有泛化能力了 。 提出GIN的作者也在论文中证实了 ， GIN在表达能力上很强 ， 但是在其他任务上 ， 泛化能力还不如表达能力差的模型 ， 如上图GIN在几个数据集上的表现 。 所以 ， 这给图神经网络带来的启示是：高的表达能力 ， 并不总意味着对下游任务友好 ， 但是低表达能力总是不好的 。 综上 ， 我们还是希望构造出一个强表达能力的图神经网络 ， 这是当前学界研究员的共识 。 总结一下ICLR2019那篇论文的工作：首先GNN在理论上有一个表达能力的上界 ， 这个上界是WLTest；为什么是WLTest？因为它的聚合函数是单射；同时这篇论文又提出了GIN这一有着单射聚合函数的图神经网络 ， 并对其表达能力进行了验证 。 4
待讨论问题：图神经网络的前沿
韭菜花音乐|中科院计算所沈华伟：图神经网络表达能力的回顾和前沿


推荐阅读


上一篇：数码东东|这瓜保熟！OPPO要火了！120Hz/20倍变焦手机只卖1425？

下一篇：大金牛财经|至今才发现，它居然是日本品牌，每年赚走65亿，喝了17年的饮料