韭菜花音乐|中科院计算所沈华伟：图神经网络表达能力的回顾和前沿( 三 ) 原创蒋宝尚AI科技评论前天作者|蒋宝尚

文章图片
所以，另外一个表达能力的限制就来自于图的结构。下面看两个简单的例子，左上角的图都是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
待讨论问题：图神经网络的前沿