Meta AI曾涵清：子图神经网络可扩展应用与表达力应用

图神经网络作为深度学习的一大活跃领域，受到人工智能学家广泛关注。由于可以将图论和深度学习紧密融合在一起，充分利用图上拓扑信息，图神经网络为解决传统深度学习单纯欧氏空间中分析非欧氏空间的对称性和传递性提供了思路。图神经网络的发展中，主要面临两大阶段性挑战。一方面，由于工业应用中图多具有大规模特点，图上传统k-hop消息传递面临指数增长的挑战，对图神经网络获取图上深层拓扑信息产生障碍。另一方面，传统图神经网络在图同构测试和Weisfeiler-Lehman test仍有较大提升空间。

基于对子图网络应用的深入研究，Meta AI Research Scientist曾涵清博士对上述两个问题分别提出新的思考；一方面，如何在不同任务中开发子图的不同含义，从而降低大图上的计算瓶颈并突破原始GNN的表达能力上限。当通过“等比例缩小”原图得到子图时，在子图上训练的GNN可以近似大规模全图上训练的GNN（基于模型的泛化能力）。由此引申出的一系列基于子图采样的工作大大降低了训练的计算/存储成本。另一方面，当把子图视为原图拓扑信息的增强时，我们可以从多种角度设计全新的GNN模块（如子图内以及跨子图的消息传递）从而增强模型表达力。在经典的图同构测试问题上，子图GNN超越了理论上最强的全图GNN。

展望未来，如何同时取得高效以及高表达能力仍是子图GNN需要解决的重要问题。曾博士提供了一种思路，通过结合节点分类和图分类两个任务中的子图GNN的核心模块，以达到计算开销和表达力的平衡。

一、图神经网络基础知识

首先来介绍一下传统图神经网络的概念、基本任务及面临的挑战，将子图神经网络应用于上述问题的基本思路，以及子图神经网络与全图神经网络的对比。

1、图神经网络与图表示学习

图表示学习任务可分为节点维度的信息嵌入、边层面的信息嵌入及图层面的信息嵌入。在节点层面，根据图的输入，产生针对每个点嵌入。在图层面，对节点嵌入信息的池化可以得到图层面的嵌入信息。

2、子图图神经网络与图神经网络

①差异：子图差异表现在拓扑信息的获取、节点特征信息的提取、消息传递、池化层等方面。

②联系：子图作为全图的一部分，对子图进行计算产生的信息可以应用于全图神经网络的计算。

3、图神经网络现存问题

由于现实数据图的固有特点，传统图神经网络在工业应用中往往面临多种问题，具体表现为可扩展性问题和表达力问题。一方面，工业应用中图的节点数往往远大于实验用图数据，由此产生的计算复杂度往往使得全图神经网络难以真正被用于图数据的计算。设计出可以用于大规模图数据的图神经网络，是图神经网络亟待解决的问题。另一方面，为了区分图数据中不同节点的信息，图神经网络应可以对不同相似节点产生不同节点嵌入信息。在对节点的分析中，传统以消息传递为基础的图神经网络的理论上限被证明为1-WL，如何设计出高区分度的图神经网络，也是图神经网络面临的挑战。

4、最近的工作

下图中列出了最近的一些工作，并标出了每篇文章关注的重点。

二、子图神经网络与可扩展性

针对上述图神经网络的挑战，曾博士从子图神经网络角度提出了思考。通过对经典子图神经网络算法GraphSIANT的分析，剖析子图神经网络的可扩展性方法。

1、图训练：小批量训练

对数据容量小于原图但保留原图特征的子图进行图神经网络计算，可以使得图神经网络训练在近似原图训练的同时减少计算复杂度。另外，由于子图中消息传递的节点数小于总节点数，通过设定子图节点数，子图神经网络邻居点数可以被限制在一定有效范围内，从防止邻居节点指数级增长带来计算复杂度。

2、GraphSAINT基于子图采样的普适图训练架构

小批量训练在训练中体现出的性能建立在采样方法可以以小样本采集到原图结构信息基础上。如何能够设计出可表征原图信息的子图采样方法，成为小批量训练的关键问题。

曾博士提出的GraphSAINT框架，第一步，基于importance node/edge sampling、Random-walk及其变种等采样算法，采样子图。第二步，利用神经网络对子图进行计算。GraphSAINT还加入了normalization以减小不同采样算法之间差异带来的影响，同时利用variance reduction增强对重要子图的提取能力，以增强子图采样的整体可信度并利用随机性采样增加泛化能力。另外，Cluster-GNN也可视为子图神经网络采样的一种方案。

综上，子图神经网络的第一种应用方法可概括为设计采样方式在原图中采样能够反映原图信息的子图，以此降低计算复杂度并对产生与全图神经网络相近的计算结果。

三、子图神经网络与表达力

传统图神经网络被证明以1-WL为表达力上限，如何设计出能够依据图产生更多信息，并以此增加图神经网络的表达能力，也是图神经网络亟待解决的问题。

1、图表达力的子图应用

图神经网络表达能力的评判，关键在于算法能否区分相似但不同的“regular graph”。在曾博士看来，当引入子图时，一个重要的直觉就是“regular graph的子图不一定是regular的” –- 全局（全图）的对成型被局部（子图）的不对称所打破。所以在这样的子图上运行1WL（及相对应的GNN），我们就可以区分出这两个图不同构。

2、Shadow-GNN：子图与节点分类

不同于GraphSAINT，在shaDow-GNN看来，每个子图不再代表全图的性质，而是作为每个目标节点的一个“指纹”。整体architecture如下：对每个目标节点，我们在其周围提取一个小的临域子图（这里“小”可以是几亿节点的全图中的200个节点构成的子图，这200个节点可以通过Personalized PageRank score或其他方法进行filter）；这个小的子图可能只包含目标节点的一（小）部分1-hop与2-hop neighbor，但是我们在这个浅层的子图里运用一个深层的GNN（比如5层），以保证子图的信息能够被模型彻底吸收提取。注意这里GNN的层数（比如5）不再直接与子图的深度（比如2）挂钩，所以我们说这个模型是decoupled。进一步拓展，每个目标节点可以由多个临域子图来描述，这样我们就有多个GNN并行地提取subgraph embedding，最后通过ensemble得到目标节点的embedding。

3、子图神经网络与图分类

（1）思路：传统GNN的kernel是对所有直接邻居的信息聚合，而subgraph-GNN的kernel是对整个subgraph的多层的信息聚合。

（2）Nested GNN：内层（inner）GNN类似于shaDow-GNN的操作：对每个节点取一个邻居子图，然后对此子图跑多层的GNN生成subgraph embedding。外层（outer）GNN对所有内层GNN的subgraph embedding再做了一次全局的pooling，从而得到整个全图的embedding，以此对全图生成预测的标签。由于shaDow-GNN超越了1WL的表达力，Nested GNN也超越了1WL。

（3）GNN-AK：GNN-AK进一步拓展了kernel的用法，它是Nested GNN的一种衍生模型。Nested GNN在全图层面对所有subgraph embedding做了一次信息聚合，而GNN-AK则进行了多次subgraph embedding的聚合。直观来看，GNN-AK是把多个Nested GNN叠加，相当于一个多层的Nested GNN。这样的模型层面的拓展也带来表达能力的提升。理论上GNN-AK也超越了1WL；GNN-AK可以区分某一些3WL不能区分的图。如果我们对每个节点取一种特殊的邻居subgraph，即k-hop subgraph，那么当k增大时，GNN-AK的表达能力也得到提升。这说明更大的subgraph包含更多信息，进而更能提升表达力。

（4）OSAN and ESAN:信息增强：OSAN的子图集合定义为所有k个节点可能组成的子图。该子图用来生成1-WL的初始颜色（由于GNN和1WL的等价性，拓展1WL的初始颜色相当于增强每个GNN节点的初始特征）。每个节点和每个k指定大小子图匹配起来都可以生成一组初始颜色。这样相比于原始的1-WL（每个节点只有一种初始颜色），OSAN的消息传递的信息更加丰富。并且由于k-sized subgraph包含了原图的结构信息，由子图生成的新的信息也使得GNN可以提取更丰富的结构信息。公式展示了每次WL迭代中更新颜色的过程。一式对应原始的WL，二式对应基于子图的WL。下面的C（v，g）表示此处v的颜色也取决于子图g。

表达能力方面，OSAN在增大k值时表达能力逐渐增强。

另一经典应用为ESAN：利用子图，增加信息传递的种类。

与在构建的子图上进行独立的信息传递不同的是，ESAN增加了新的信息传递操作：子图间的信息传递。即在不同图同时进行神经网络计算，并对不同子图的同一层输出进行信息整合，形成“子图间”的信息传递，达到丰富信息传递的目的。

（右图：基于edge-deletion的子图构建方法：在原图中的所有边中删除一条边后得到的子图就是ESAN的一个子图。并展示了对原图的多种删除边方法。）

四、未来展望

1、问题与解决

同一计算方法，对于可扩展性和表达力的提升往往处于矛盾状态：表达能力强的subgraph-GNN计算起来不高效。主要原因为：① GNN需要处理非常多的子图，每个子图大小差异巨大。②K步子图包含的子图数目及节点数随着k的增加呈指数级增加。③node-deleted subgraph个数等于全图的节点个数。曾博士给出的解决方式为进一步采样，即在子图集合中采样部分数据用于训练。但是如何在进一步采样时减少表达能力的损失，仍需要更多的研究。

针对不同下游任务，图神经网络面临的挑战也有所不同：图嵌入任务多用于分子图等小型图数据，而节点分类更多用于社交网络等大规模图计算，因此需要更多精力解决图神经网络的可扩展性问题。

2、未来展望

展望未来，我们可以以shaDow-GNN为基本框架，结合为节点分类和图分类两种任务设计的不同的subgraphGNN，从而取得节点分类任务中对超巨图的expressivity与scalability的更好的平衡。我们可以在巨大的社交网络里抽取小的子图，然后在小的子图上运行那些为图分类问题设计，表达能力更高但计算成本也更高的subgraph-GNN。这样我们既提升了shaDow-GNN的表达能力，又仍然服从模型整体复杂度的要求（相对全图的线性复杂度；相对小的子图的多项式复杂度）