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

文章图片
关于GNN的标准框架，目前用得比较多的是Aggregate+Combine ，此框架比较灵活，图分类任务和节点分类任务都适用，其策略方式是通过迭代，用邻居的表示迭代更新自己的表示。策略一共分两步，第一步是聚合邻居信息；第二步是把邻居信息和自己上一轮的信息进行耦合。下面举几个这种框架的例子，第一个是2017年提出的GraphSAGE ，其操作是把邻居的表达进行变换之后，取里面最大的一个赋给自己，然后再把学到的表达和自己上一轮的表达做整合，随后得到新的表达。值得一提的是， GraphSAGE用了Max-pooling的方式，此方式限制了他的表达能力，是导致表达能力丧失关键的一步。 GCN的表达方式直接，将邻居进行特征变换，然后按照矩阵规划进行传递，它的特点是把AGGREGATE和COMBINE两个操作进行了整合。值得注意的是， GCN采用了Mean-pooling的方式，此方式也限制了它的表达能力。另外， GCN的改进版是GAT ，其采用的方式是weightedmeanpooling 。 3
图神经网络的表达能力如何
【韭菜花音乐|中科院计算所沈华伟：图神经网络表达能力的回顾和前沿】前面是关于图神经网络基本介绍，现在回到今天的主题：图神经网络的表达能力。我们先讨论2019年发表在ICLR上的《Howpowerfularegraphneuralnetworks》。

文章图片
首先明确什么是表达能力，所谓表达能力一般有两个方面，第一个方面是表示的空间大小，例如，一个N位的二进制能表达N的二次方个数。这种表达能力旨在表示多少不同的东西，不同的结果。第二个方面是关于近似能力。例如设计一个神经网络能够近似什么样的函数。值得一提的是，在1989年的时候就有了证明：神经网络的层次只要足够深，就可以逼近任意连续函数。这个“万能近似定理”也解释了为什么深度学习从来不担心表达能力的原因。但是GNN提出之后，深度学习表达能力的话题又被提起， 2017年有研究员发现深度学习的表达能力和深度神经网络的层次是指数关系，假如网络有D层，那么表达能力与“某个数”的D次方成正比，大家感兴趣可以看相关的论文。 GNN引进之后，对于表达能力有什么样的启示呢？如上述左图所示，如果不看结构，节点的标号标1还是标2是区分不开。如果想区分这个不同的“标号1” ，需要观察标号的邻居，可以通过邻居信息进行区分。 GCN可以把邻居信息进行聚合，提升区分节点的能力。如上图左下所示，在一层GCN操作完成之后，已经可以区分一些标号，但左下图四个“标3”的点还是区分不出来。

文章图片
所以，一层GCN区分能力并不够，那能否通过加深层次解决表达能力呢？两层GNN之后，如上图所示，变成了八个点，并可以完全区分开。所以，如果用两层GCN对上述节点进行分类，无论Label标记成何种方式， GCN的表达能力都能满足分类要求。上面是两层GCN完全可以区分的例子。回到刚才的问题，把GNN加深就一定能把表达能力做上去吗？也就是说，我们能不能通过深度实现无穷大的表达能力？2019年那篇ICLR文章回答：不可以！上面是节点的角度，下面从图的角度进行讨论，也即如果把不同的图做成一个表示， GNN表示图的方面表达能力如何。这里有两个关键因素，一个是节点的特征，一个是图的结构，节点的特征刚才已经讲过了，如果把节点做深度神经网络，已经可以帮我们解决掉表达能力问题。