沈华为中国科学院计算技术研究所:发展简史 批评是成长的动力
文：周寅张皓
图形神经网络的应用近年来蓬勃发展，但同时也受到了不消退的质疑。比如大规模图形数据的存储，数据集的表达能力和规范问题，就引起了很多讨论。
中科院计算研究所研究员、致远青年科学家沈华为多年来深入图形神经网络领域。在清远谈话的第四期，沈华伟梳理了图形神经网络的发展历程以及他对一些问题和疑惑的看法。
沈华为表示，对领域的每一次挑战都是领域成长的动力，只有挑战解决了，领域才会发展。
报告回放链接：https://hub.baai.ac.cn/activity/details/126
不要忘记自己的主动心态，牢记使命，沈告诉自己华为如何错误地走上科研之路
题外：
01
20世纪90年代末，图形神经网络作为神经网络在不同数据上的一种应用方案，与循环神经网络和卷积神经网络一起被提出。因此，图形神经网络最初应该被称为图形神经网络，但由于图形数据的问题在当时没有得到广泛应用，与迅速崛起的卷积网络相比，GNN发展并不迅速。
经过十几年的沉寂，受CNN发展的启发，人们开始思考如何将CNN的参数共享性质推广到非欧洲结构的数据。作为非欧结构的两大类型之一(图和流形)，图吸引了众多研究者的关注。
然而，如何定义图上的卷积成为困扰该学科发展的一个问题。由于图形数据的性质，每个节点的度是不同的，甚至在社交网络中从1到10 ^ 8不等，这给卷积的定义带来了很大的挑战。
图表示：图可以表示为一个四元组(v，e，w，x)，分别表示节点，边，加权邻接矩阵，节点属性集。
在研究过程中，图的卷积定义经历了谱方法和空间方法两个发展方向。
Yann Lecun首次将卷积的概念应用到神经网络中，提出了谱方法和空间方法两种方法。
但是由于谱方法在空间方法中没有局部性质，即空间不变性，虽然数学形式很美，但是强行定义卷积的效果并不好。
但是空间方法比较直观，类似CNN定义。空间方法通过聚集节点周围邻居的信息来实现卷积。随后的发展表明，空间方法促进了GNN的发展，使人们对GNN的认识进入了信息传递的框架。
发展从分离到融合
Yann Lecun在《图上的谱网络和深局部连通网络》一文中提出以图的拉普拉斯矩阵的特征向量为基，将样本投影到空间中，然后进行卷积运算。
超参数用于控制每次选择的相邻节点数，对变化后的样本进行滤波和相加，然后对输出结果进行拉普拉斯逆变换，输出非线性结果。工作中的方法表明了在谱域进行卷积运算的可能性，并为后续的一系列图形网络奠定了基础。
然而，这种方法仍然存在一些问题。
沈华伟指出，该方法依赖于矩阵的特征分解，且投影计算和逆变换的开销为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，即采用局部采样的方式获得样本，而不用储存整张图。
这些对领域的抨击都是这一领域成长的契机，只有解决了这些抨击的问题，才能获得发展。