中科院计算所沈华伟:GNN发展简史,诟病才是成长动力

2021
01/25

+
分享
评论
学术头条
A-
A+


文:周寅张皓


图神经网络(Graph Neural Network)的应用在近年来蓬勃发展,但同时对其质疑也从未消失。诸如对与大规模图数据的存储问题,表达能力问题,以及数据集的规范问题引发了许多讨论。

中科院计算所研究员、智源青年科学家沈华伟在图神经网络领域深耕多年。在青源talk第四期中,沈华伟梳理了图神经网络的发展历程,及对于一些问题、质疑的看法。

沈华伟表示,每一次对领域的质疑都是该领域成长的一次动力,只有解决了质疑的问题,领域才会得到发展。

题外:  不忘初心,牢记使命,沈华伟自述,如何误打误撞走上科研这条道路

01


发展|从分离到融合  

上世纪 90 年代末,作为神经网络在不同数据上的应用方案,图神经网络与循环神经网络、卷积神经网络一同被提出。因此最初 Graph Neural Network 应该被称为 Neural Network for Graph,但由于图数据的问题在当时并没有很广的应用场景,因此相较于迅速崛起的卷积网络, GNN 并未得到快速发展。

在沉寂了十多年后,人们由 CNN 的发展得到启发,开始思考如何将 CNN 的参数共享的性质泛化到非欧结构的数据中,而图作为非欧结构的两大类型之一(图与流形),被许多研究者关注。

但如何在图上定义卷积,成了一个困扰学科发展的问题。由于图数据的性质,每个节点的度大小不一,在社交网络中,甚至可能从1到10^8,这给卷积的定义带来了很大挑战。


图的表示:图可以被表示为一个四元组(V,E,W,X),分别代表节点、边、加权邻接矩阵和节点属性集。

在研究过程中,对图的卷积定义主要经历了两个发展方向:谱方法与空间方法。

最早将卷积概念应用于神经网络的 Yann Lecun 在面对这个问题时,提出了谱域 (spectral) 和空间 (spatial) 两种方法。

但由于谱方法没有在空间方法上的局部性质,即空间上的不变性,虽然数学形式优美,但强行定义卷积的效果并不好。

而空间方法较为直观,与 CNN 定义类似,空间方法则是通过对节点周边邻居的信息聚合来实现卷积。后续的发展表明,空间方法推动了 GNN 的发展,让人们对 GNN 的认识进入了信息传递的框架。

谱方法

在 「Spectral Networks and Deep Locally Connected Networks on Graphs」一文中,Yann Lecun 提出将图的拉普拉斯矩阵的特征向量作为基底,将样本投影到该空间后,进行卷积操作。


采用超参控制每次选择的相邻节点数量,对变化后的样本做 filter 和求加,再将输出结果进行拉普拉斯的逆变换,并输出非线性化后的结果。工作中的方法展示了在谱域进行卷积操作的可能性,并为后续的一系列图网络奠定了基础。

但这种方法,仍然存在一些问题。

沈华伟指出,该方法依赖于矩阵的特征分解,且投影计算和逆变换的开销为O(n^2),计算开销过大。另外,该方法并不是在局部空间上操作,这让这种方法失去了直观上的意义。

这些问题给未来的工作提供了一系列改进的空间。

2017年的「Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering  」使用切比雪夫多项式近似。  该方法一次性解决了谱域方法中存在的三个问题。


沈华伟指出,该方法避免了分解拉普拉斯矩阵,而是采用特征值对角矩阵作为基底。操作避免了使用过多自由参数导致的学习困难,同时代入计算公式后,减少了对特征向量矩阵 U 的依赖。

研究证明了该方法与谱方法有同样的误差上界,且计算复杂度降低到了 O(|E|) ,极大改善了谱方法图卷积的性能,同时启发了空间方法 GCN,作为该方法的一阶近似。

沈华伟认为,ChebNet在使用多项式近似时限制了卷积操作的自由度,使得该模型在实际使用中并不能有很好的效果。因此采用图的小波基作为基底U。由于小波变换的性质,U为一个稀疏矩阵,降低了计算开销,同时其局部性质也使得WaveletNet在实际应用中展现出不错的效果。

空间方法

2016年发表的文章「Learning Convolutional Neural Networks for Graph」发现,从CNN向GCN的卷积过程的迁移问题在于,需要确定一个固定的邻域,后续卷积的「定序」、「参数共享」步骤都可以在确定邻域后解决。因此该工作选择了每个节点固定个数的邻接节点作为邻域。但是,该工作确定邻域需要设计某种启发式的距离度量,后续工作对此作出了改进。


在GraphSAGE「Inductive Representation Learning on Large Graphs」中,作者采用了采样的方法确定邻域。在卷积操作的节点进行固定个数的随机行走,得到固定大小的邻居节点。由于随机行走能够更大概率获得与起点节点更近的节点,因此该方法采样能够得到相似的邻居集。得到了集合后,算法对邻居节点做信息聚合。


在先前工作的基础上,GCN对节点的一阶邻近节点进行访问,通过一阶层次化的堆叠,可以实现对二阶、三阶信息的获取。

但进一步的分析发现,该方法在计算中并未使卷积操作参数化而共享,其共享的参数是实现特征变换的 W ,使得该方法本质上是对邻接节点的加权聚合,使用邻居信息来平滑自身,其可以在很多任务中表现了不错的效果,但表达能力受限。

因此,后续工作诸如「Graph Attention Network」采用 self-attention 来控制自身信息与邻接节点信息的表达,实现了卷积操作的参数共享。


后续的研究发现,谱方法可以被定义为空间方法的一个子集。

「Geometric deep learning on graphs and manifolds using mixture model CNNs」给予图的卷积方法一种规范化的描述。文中指出,图卷积的实质是使用参数化的权重对定义的距离矩阵加权聚合。这个框架同时给予谱方法一种新的解释。


沈华伟指出,相较于空间方法在原始空间定义聚合函数,谱方法在规范后实质上是对变换到新的空间中的样本进行卷积。

因此谱方法可以被看作是变换空间后的空间方法,其从属于空间方法这一类别。而谱方法将显式地写出了空间变换,空间方法直接将 kernel matrix 定义出来,未写明变换的空间。


谱方法与空间方法的关系

02


反思|实践在先  

Pooling

沈华伟指出,近年来关于GNN的理论进步十分有限,但是采用同样思想,从 CNN 结构迁移的技术比如 Graph Pooling 仍然不断发展,大致可分为两类:

  • 其一是通过对图进行层次聚类后,定义 pooling;

  • 另一种直接使用 attention 的方式,为每个节点计算attention weight,筛选节点。


但是,pooling 是针对图任务而言的,若需要节点级别的任务,则 Graph Pooling 就显得并不必要。

和 CNN 相比,由于图像任务处理的是图像本身,使用 pooling 能够从局部表示学习到全局的表示,而图的任务很多都是针对节点和边的,采用 pooling 反而会丢失信息,与任务本身并不匹配。因此,该领域需要尽快理清发展的目标。

表达能力

表达能力有两种形式:一是模型能够刻画的空间,另一种是拟合能力,是否可以逼近复杂函数。

由于神经网络在表达方面的强大能力,因此GNN提出以来,少有工作怀疑其表达能力。

但有研究发现,GNN并不能为图结构的数据提供万能近似的功能。WL test 为 GNN 的表达能力提供了理论的上界。

不过表达能力的限制同样带来了GNN的优势:易训练且开销小,相比于同等规模的全连接网络,GNN能够更快收敛。

与表达能力不足相反,GNN 通常在泛化能力上表现很好。这让其在特定任务上比神经网络具有更加优秀的表现,例如在样本稀少的任务上,GNN能够有很好的泛化性能。

然而,当加深 GNN 时,模型反而会出现过平滑问题,甚至在 training loss 上出现了不降反增的现象。分析表明,这源于 GCN 的跨层共享的硬编码矩阵 A,而 GAT 并不存在这个问题,因此某种意义上多头 GAT 才是真正意义上的 GCN。

03


应用|通用的跨学科图数据表示器  

图神经网络的应用可以从三个领域来讨论,分别是 (1)节点层面、(2)图层面和 (3)信号层面。

在学科方面,推荐系统是一个参与众多的应用方向。

另一个极有前景的领域是知识图谱。由于知识图谱本身就是图结构,使用GNN或许会产生非常好的效果。

此外,诸如量子化学、物理等领域,GNN 都展现出了不错的能力。作为处理图的一个方便的工具,GNN 对其他学科的图类型的数据都可以做到很好的表达。

GNN在其他学科的应用

04


One More Thing  

问:如何看待 GNN 的诟病?

沈华伟:  针对 GNN 的诟病很多都来自最初几年发展的时候,学科发展的不规范,例如benchmark数据规模小,固定划分等不符合机器学习的常规规范。但简化了的研究验证过程也方便了研究者进行快速实验,在短短几年间就完成了理论的积累,走向蓬勃发展。在之后几年,研究者们便开始对GNN的研究作出规范,修正了当初的问题。因此对最初几年的诟病是正确的,但这是在特定阶段的便宜之计,因为这样有利于快速发展。

表达能力的问题正如报告中所说,存在一定局限。另一种批评是图在做 transductive learning时需要完整图的知识,对大规模的图做transductive learning开销很大。当前的发展方向倾向于inductive learning,即采用局部采样的方式获得样本,而不用储存整张图。

这些对领域的抨击都是这一领域成长的契机,只有解决了这些抨击的问题,才能获得发展。


本文由作者自行上传,并且作者对本文图文涉及知识产权负全部责任。如有侵权请及时联系(邮箱:nanxingjun@hmkx.cn
关键词:
GNN,沈华伟,诟病,计算,网络,数据

人点赞

收藏

人收藏

打赏

打赏

我有话说

0条评论

0/500

评论字数超出限制

表情
评论

为你推荐

推荐课程


社群

精彩视频

您的申请提交成功

确定 取消
剩余5
×

打赏金额

认可我就打赏我~

1元 5元 10元 20元 50元 其它

打赏

打赏作者

认可我就打赏我~

×

扫描二维码

立即打赏给Ta吧!

温馨提示:仅支持微信支付!