中科院计算所沈华伟：图卷积神经网络的思想起源

智源社区 & AI科技评论

作者 | 周寅张皓

小到分子相互作用，物质结构，大至气候变化，星系模型，很多自然界和社会生活中的现象都能用图结构描述。而如何将神经网络应用到图网络中进行计算，在几年前却是悬而未决的难题。

现今，我们提到的图神经网络，往往指图的卷积，那么，卷积是如何应用在图的非欧结构上的？带着这个问题，我们一起走进10月30日，中科院计算所研究员沈华伟在CCL2020“图卷积神经网络”的报告，报告中沈华伟介绍了卷积应用于图模型的思想起源、谱域方法和空间方法的发展，探讨了其表达性能，并对未来发展方向进行思考。

沈华伟，博士，中国科学院计算技术研究所研究员，中国中文信息学会社会媒体处理专委会副主任。研究方向为网络科学和社会计算。先后获得过CCF优博、中科院优博、首届UCAS-Springer优博、中科院院长特别奖、入选首届中科院青年创新促进会、中科院计算所“学术百星”。2013年在美国东北大学进行学术访问。2015年被评为中国科学院优秀青年促进会会员（中科院优青）。获得国家科技进步二等奖、北京市科学技术二等奖、中国电子学会科学技术一等奖、中国中文信息学会钱伟长中文信息处理科学技术一等奖。出版个人专/译著3部，在网络社区发现、信息传播预测、群体行为分析、学术评价等方面取得了系列研究成果，在Science、PNAS等期刊和WWW、SIGIR、CIKM、WSDM、AAAI、IJCAI等会议上发表论文60余篇，引用1700余次。担任PNAS、IEEE TKDE、ACM TKDD等10余个学术期刊审稿人和WWW、CIKM、WSDM等20余个学术会议的程序委员会委员。

1

非欧空间的卷积

卷积，在泛函中，指使用一个算符(函数)，与另一个函数运算产生新的函数。若对连续函数f(x)，g(x)使用该运算，可以使用积分公式。直观上看，卷积可以看作是一个函数对另外一个函数的平均。

沈华伟指出，神经网络的卷积通常是对欧式空间数据的操作。例如图片数据，可以看作是在固定形状的矩阵通道上取不同的值。将卷积操作拓展于离散数据，就成了使用固定的卷积核(函数f(x))对固定通道（函数g(x)）进行相乘求和(积分)。然而在图结构中，通道往往各不相同，即每张图都有其特殊结构，无法固定卷积的函数，相对于矩阵这种在欧氏空间的数据，图的非欧性质使其很难找到有效的方法应用卷积。

图1：函数的卷积

2

从谱域到空间域

2.1 谱域

1. Yann LeCun的方法

面对以上问题，卷积神经网络的提出者LeCun，提出了谱域(spectral)和空间域(spatial)两种方法。在'Spectral Networks and Deep Locally Connected Networks on Graphs'中，作者提出将图的Laplacian矩阵的特征向量作为基底，将样本投影到该空间后，进行卷积操作。采用超参控制每次选择的相邻节点的数量，对变化后的样本做filter和求加，再将输出结果进行拉普拉斯的逆变换，并输出非线性化后的结果。

图2：节点选择

该方法展示了在谱域进行卷积操作的可能性，并为后续的一系列图网络奠定了基础，但该方法仍存在一些问题，沈华伟指出，该方法依赖于矩阵的特征分解，且投影计算和逆变换的开销为O(n²)，计算开销过大。另外，该方法并不是在局部空间上操作的，这让这种方法失去了直观上的意义。这些问题也给未来的工作提供了一系列改进的空间。

2. ChebNet

17年的“ChebNet: Efficient and Stable Constructions of Deep Neural Networks with Rectified Power Units using Chebyshev Approximations”使用切比雪夫多项式近似。该方法一次性解决了谱域方法中存在的三个问题。

沈华伟表示，该方法避免了分解Laplacian矩阵，而是采用特征值对角矩阵作为基底。避免了使用过多自由参数导致的学习困难，同时代入计算公式减少了对特征向量矩阵U的依赖。研究证明了该方法与谱方法有同样的误差上界，且计算复杂度降低到了O(|E|)，极大改善了谱方法图卷积的性能，同时启发了空间方法GCN，作为该方法的一阶近似。

3. Graph Wavelet Nerual Network(GWNN)

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

2.2 空间域

1. 工程思维的启发

2016年“Learning Convolutional Nerual Networks in Graph”引起了人们对于空间方法的关注。文中方法思路简洁：对于一个结点进行卷积操作时，固定该点并将该点的固定邻域节点排序，采用加权平均的方式得到节点值。

该方法固定了每次卷积操作使用的节点个数，采用非常工程化的思维，实现了权重值的共享。其中，该工作采用了对于节点相似度的度量确定邻接节点的选择，这启发了后续的一系列工作。例如在GraphSAGE中，作者采用聚合函数，通过对访问节点进行随机遍历，相当于对所求节点的邻接节点进行聚合，避免了权重共享的问题。

2. GCN

在先前工作的基础上，GCN对节点的一阶邻近节点进行访问，通过一阶层次化的堆叠，可以实现对二阶、三阶信息的获取。但进一步的分析发现，该方法在计算中并未使卷积操作参数化而共享，其共享的参数是实现特征变换的W，这使得该方法本质上是对邻接节点的加权聚合，使用邻居信息来平滑自身，可以在很多任务中表现出不错的效果，但表达能力受限。因此，后续工作诸如Graph Attention Network 采用self-attention来控制自身信息与邻接节点信息的表达，实现了卷积操作的参数化。

图3：GCN模型

2.3 融合

《MoNet：A General Framework for Spatial Methods》给予图卷积方法一种规范化的描述。文中指出，图卷积的实质是使用参数化的权重对定义的距离矩阵加权聚合。这个框架同时给予谱方法一种新的解释，沈华伟说，相较于空间方法在原始空间定义聚合函数，谱方法在规范后实质上是对变换到新的空间中的样本进行卷积。因此谱方法可以被看作是变换空间后的空间方法，其从属于空间方法这一类别。

图4：谱方法和空间方法的关系

3

图的表达能力

近年来，图卷积网络的一系列应用展现出其在特定任务上的优越性能，在节点分类、预测中得到了很好的效果。在量子化学的应用中，它能在给定物质结构的基础上，精确的预测物质具有的性能，且精度达到了化学精度，相较于传统的泛函分析，大大节省了计算开销和时间。

沈华伟指出，与一般的卷积神经网络类似，图的卷积使用加权聚合和空间变换等操作实现了参数共享，使得模型的参数量得到下降，在一定程度上，降低了模型训练的难度，因此在一些节点预测和分类等任务上取得了不错的成果，但这依赖于对领域知识的利用，其表达性同样不如常规的神经网络。简单的分析可以证明其性能上的缺陷，例如在一般的分类中，通过增加网络层数，获取二阶、三阶等信息，能够区分一些一般的图结构，但对于一些相似结构的特例，GNN并不能有效区分。

图5：无法分辨的节点

WL test提供了GNN表达能力上界的解释。与神经网络不同，GNN对于节点的运算采用聚合操作，无论是加权平均、求和，或是求均值、求Max，输入输出并不能保证单射的性质，因而限制了网络的表达能力。例如，采用均值的情况下，样本（2，4）和（1，5）可以有相同的均值，同理，在图网络上，如果采样的节点具有相似的结构，且采样顺序相同时，在进行平均聚合运算后会产生相似的结果，导致网络无法区分。

4

未来的方向

与神经网络类似，GNN的设计很大程度上依赖于启发式的设计，缺乏对其理论和性能上的认识。在一些图网络性能研究工作中已有进展，但仍待更深入的研究，以帮助进一步理解图卷积网络。

报告最后，沈华伟介绍了目前图卷积网络研究中的问题和未来的推进方向。

1. 图网络的学习性能：是否真正学到结构化的信息。

2. 解决训练导致的过平滑问题：由于图卷积实质是利用周围节点平滑所求节点信息，当网络深度增加时，容易导致过渡平滑。

3. 图的预训练模型。

4. 对抗攻击: 一些研究表明，图卷积网络在一定程度上受限于稳定性问题，需要设计出更加稳定的网络。

5. 扩展应用领域。