图神经网络理论述评与应用初探

陈 明 魏哲巍

中国人民大学 北京 100872

引言

近年来，人工智能技术取得了巨大的成功，影响到了人们生活的方方面面，其中，深度学习(Deep Learning)作为人工智能技术中最关键的一部分，发展尤为迅速。深度学习推进了模式识别和数据挖掘领域的研究，将现实世界中的每一个概念都定义为更加抽象的概念，即通过深度神经网络来提取样本特征。目标检测、机器翻译、语音识别等许多机器学习任务曾高度依赖手工特征工程来提取信息特征，但多种端到端深度学习方式(卷积神经网络、长短期记忆网络和自编码器)改变了这种状况。深度学习在多个领域的成功主要归功于计算资源的快速发展(如GPU)、大量训练数据的收集，还有深度学习从欧几里得数据(如图像、文本和视频)中提取潜在表征的有效性。尽管深度学习已经在欧几里得数据中取得了很大的成功，但许多领域存在非欧几里德空间的底层结构数据，包括计算社会科学中的社会网络、通信中的传感器网络以及脑成像中的功能网络等等，这样的数据庞大且复杂，它们需要有效分析。例如，在电子商务领域，一个基于图的学习系统能够利用用户和产品之间的交互以实现高度精准的推荐；在化学领域，分子被建模为图，新药研发需要测定其生物活性；在论文引用网络中，论文之间通过引用关系互相连接，需要将它们分成不同的类别，图神经网络(Graph Neural Networks，GNNs)应运而生。从视觉推理到开放性阅读理解问题，从药物分子的研发到医疗诊断，从交通流量预测到3D点云数据的学习，几年时间，图神经网络技术的相关应用研究已经拓展到了极其宽广的局面上，展示出了极其重要且极具渗透性的应用能力，并带来极高的产业价值。

1 图神经网络

图(Graph)是计算机科学中一类重要的数据结构，与“文本”“图像”“语音”共同构成数字世界的基础组成部分。图结构通过将现实场景中的实体转化为节点，将实体间的关系转化为边，借助节点和边的数据结构对实体及其关系进行抽象建模。在“万物互联”的大环境下，图结构对现实场景中研究对象间的作用关系具有很强的表达能力。

将传统的深度学习算法应用于图时存在诸多挑战，与图像、音频和文本具有清晰的网格结构不同，图具有不规则的结构，如图1所示，与网格结构相比，图的节点无序，图中的每个节点都与其周围的其它节点存在复杂的依赖关系[1]。因此现有的深度学习算法，例如，卷积神经网络(CNNs)仅适用于网格结构数据(图像)，递归神经网络(RNNs)仅适用于序列(文本)数据。图神经网络的核心在于建模节点间的依赖关系，从而对图节点进行表示，并对接下游机器学习任务。

图1 网格数据(左)与图数据(右)

基本的图神经网络模型最初由谱方法导出，将卷积核作用在谱空间的输入信号上，并利用卷积定理实现图卷积，以完成节点之间的信息聚合。在信号上的卷积被定义为

1.1 图神经网络的空间邻域聚合

从研究层面来说，GCN将图神经网络从谱域卷积的研究转向了空间域卷积的研究。为了适应现实世界中复杂的图数据，研究人员通过设计不同聚合函数来结合中心节点和其邻域节点信息。一个有效方法是将注意力机制融入到图学习方案中。注意力机制通过允许模型专注于输入中最相关的部分，从而帮助模型做出决策，在融合注意力机制的GNN模型中，图邻接矩阵仅被用来定义邻域节点，而节点间的权重计算则依赖于节点特征。例如图注意力网络GAT[4]的注意力权重计算公式为其中可学习参数用于计算节点间的注意力权重。如图2所示，得到注意力权重后每个邻居节点按照不同的权重聚合信息到目标节点。大量研究表明，注意力机制在生物分子领域尤为重要。相比GCN和GraphSAGE[5]等仅利用均值权重聚合的模型，GAT和GrapStar[6]等方法学习到的权重分布方差更大，在标准的蛋白质功能分类任务中的预测精度可以提升20%左右。注意力也使模型的结果更易于解释。例如，通过分析模型对医学本体图中不同组件的关注度，可以确定导致特定医疗状况的主要因素[7]。然而目前基于注意力机制的图模型参数量大，运行效率不高；其次，大多数基于注意力的图神经网络仅通过节点特征学习聚合权重，忽视了图结构信息。因此如何使注意力机制结合图结构信息，如何提升注意力图模型的运行效率仍然具有很大的挑战。

图2 图注意力网络根据权重聚合信息

1.2 深度图神经网络

尽管目前图神经网络的表现力得到了广泛的认可，但目前大多数GNN模型都是浅层网络，如GCN和GAT等都在两层模型中实现了最佳预测性能。这种浅层结构限制了它们从高阶邻居中提取信息的能力。然而，叠加更多网络层并增加非线性往往会降低这些模型的性能，随着层数的增加，GNN中节点的表示倾向于收敛到某个值，因此节点变得不可区分，这种现象被称为过度平滑。有许多研究工作表明这种过度平滑更深层的原因是随机游走的稳态分布(Steady-State Distribution)，因此阻碍或改变稳态分布的收敛是缓解过度平滑的可行方式。例如通过密集跳跃连接来组合模型每一层的输出，来学习不同图子结构的不同阶表示，以保持节点表示的局部性；或者在训练时从输入图中随机删除一些边，以此缓解过度平滑的收敛速度并提高模型泛化能力。这些方法在全监督的直推式或归纳式学习中将图模型层数增加至16到32层，且大幅度提升了模型预测性能。然而增加的模型层数使得模型训练时更易受到过拟合的影响，因此如何在学习高阶交互信息的同时保证模型泛化性是该研究中需要重点关注的。另一方面，还可以将GNN中的信息传播和特征变换解耦，用PPR(Personalized PageRank)或者HKPR(热核PageRank)等存在局部性的图传播方案代替原本GNN中的高阶概率转移方案，从而避免过平滑，例如SGC[8]、APPNP[9]、GDC[10]等方法。虽然可以在学习图中高阶交互关系时避免过平滑，但这些方法只是对每一层的邻域特征进行线性组合，失去了深层非线性结构的强大表达能力，可能会限制相应的GNN模型性能。目前的深度图神经网络理论集中于同质图的研究，而在具有多种节点和边类型的异构图中，如何训练深层模型，从而尽可能的捕获高阶交互所带来的收益，是一个重要研究方向。

2 图神经网络的训练技术

随着互联网中数据量的高速增长，现实世界的图很容易有数千万甚至数十亿个节点和边。因此，如何设计可伸缩模型，最好是相对于图节点数量或边数量具有线性时间复杂度的模型，是一个关键问题。经典的GCN使用的是一阶拉普拉斯多项式滤波器近似图上的卷积操作，并使用全批量训练网络，时间复杂度与卷积层数呈线性关系，但需要将全部图结构及其节点特征加载进显存，无法支持大规模图数据的训练。GraphSAGE[4]利用小批量训练提高GCN模型的收敛性并通过随机游走采样来减少学习节点的表示所需的邻域大小，缓解“邻居爆炸”问题，但是训练的时间复杂度和GCN阶数仍呈指数关系，仅能支持浅层模型的训练，无法发挥深层神经网络的优势。Cluster-GCN[11]使用图聚类算法预先将图分割为多个子图，每个子图作为一个批量来进行GCN的训练，将训练的时间复杂度和GCN阶数降为线性关系，但对于大规模的图数据，标注数据非常稀少，图聚类无法控制将指定个数的标注节点分配到同一个子图，影响了小批量训练的效果。最近，GraphSAINT[12]提出了多种轻量级采样算法(例如节点采样、随机游走采样)来代替图聚类，提高了采样的速度与灵活性，可以支持只包含少量标记数据的半监督学习任务。但是如何在大规模图数据中学习远距离节点之间的关系、提高图模型推理速度仍然是有待解决的问题。

另外有很多研究者尝试从系统角度提高图学习效率。PyG[13]是几何深度学习库，利用稀疏GPU加速和高效的小批量处理来实现高数据吞吐量，并为不规则数据(图、点云、流形)提供统一易用的接口。Wang等人构建的图上深度学习软件包DGL[14]，可以集成不同深度学习框架(PyTorch、TensorFlow、MXNet)，提供send、recv两种基本原语执行图计算，自动检测操作模型并进行优化，在生命科学、知识图、推荐系统、自然语言处理和图像处理等不同领域为用户提供灵活的接口。Euler[15]是阿里提出的工业级分布式图学习框架，通过缓存批训练过程中的中间结果，优化批训练所需的指数级计算力，并利用分布式并行支持数十亿级别图的训练。阿里还搭建了综合图神经网络平台AliGraph[16]，根据度分布优化缓存，在分布式环境中优化图存储、分割及采样算子，并利用异步训练等技术提高图模型训练效率，应用于多种业务场景。

3 图神经网络的应用

图神经网络被广泛应用在计算机视觉、自然语言处理、推荐系统、网络分析、交通、分子预测、组合优化等领域。下面介绍了图神经网络几种具有代表性的应用场景。

3.1 计算机视觉

图形神经网络的最大应用领域之一是计算机视觉，在图像分类、视觉推理、语义分割、场景图生成和动作识别等多个方面都存在利用图结构的方法。

图像分类是计算机视觉领域中一项非常基础和重要的任务，受到了广泛的关注。利用图神经网络可以将结构信息融合到图像分类中。例如可以构建知识图，其中每个节点对应一个对象类别，并将节点的单词嵌入作为预测不同类别分类器的输入，由此构建的知识图可以作为零样本识别的额外信息。此时GNN可以在图像之间进行消息传递，学习图像之间的相似性，实现零样本或少样本识别。相比于基于CNN的分类模型，上述方法在零样本识别任务中的预测精度提升约4%左右。随着图的增大，基于CNN的模型性能几乎没有改变，而基于GNN的分类效果可以持续上升。此外，捕获到图交互信息的分类模型可以稳健地处理知识库中的脏数据。但是零样本识别任务完全依靠类别间的消息传递进行学习，存在非平衡环境的问题，即因为某条消息的错误而扩大错误范围面导致识别的不可靠性，因此在今后的工作中可以尝试添加主动学习，即在识别过程中添加少量与用户的问答，及时纠正错误。

计算机视觉系统通常需要结合空间和语义信息进行推理。因此，为推理任务生成图是很自然的。典型的视觉推理任务是视觉问答，即回答给定图片的相关问题。为回答该问题，需要学习图中各个部分的空间关系，但是传统的基于CNN或者LSTM的视觉问答算法受只能编码单一向量的限制而只能处理图中某一部分，如CNN特征向量不能有效地捕捉多个对象实例、LSTM将问题处理为一系列的词因此不能反映语言结构的真实复杂性。相反，Teney等人[17]分别构建图像场景图和问题句法图，然后用GNN来训练嵌入以预测最终答案。实验表明通过使用GNN，在“抽象场景”多项选择基准测试中，准确率从71.2%提高到74.4%，在更具挑战性的“平衡”场景中，准确率从34.7%提高到39.1%。除了学习图像的空间信息，Norcliffebrown等人[18]还构造了问句间的关系图，从而执行更精细的关系探索和更可解释的推理过程。虽然视觉问答研究已经取得一些研究，但就从目前发展形势来看仍然面临一定局限性。比如现有方法整体准确率不够高，特别是在较有挑战性的“平衡”场景下，准确率远低于人类水平。改进方向可以关注在如何提升图像和文本之间的关系特征，现有方法分别关注在这两方面的各自表示而没有将它们很好地融合。

此外，视觉推理还可用于目标检测、交互检测和区域分类。在目标检测中，GNN可以用于计算感兴趣区域特征；在交互检测中，GNN可以用作人与目标之间的消息传递工具，如图3所示，其中红色标记人，绿色标记物，白色为交互行为生成的图；在区域分类中，GNN可以对连接区域和类的图进行推理[19]。

图3 人-物交互图

语义分割是图像理解的重要一步。这里的任务是为图像中的每个像素分配唯一的标签(或类别)，即密集的分类问题。近年来兴起的自动驾驶、虚拟现实、增强现实等应用都需要用到语义分割技术。由于图像中的区域通常不是网格状的，并且三维语义分割和点云分类等需要利用更多的几何信息，因此很难用二维CNN进行建模。因此可以在点云的基础上构造了k近邻图，图中的每个节点都对应了一组点，并与一个隐藏的表示向量相关联，利用GNN作为传播模型，按一定的时间步长展开后，以每个节点的隐藏状态为输入，预测其语义标签。GNN利用了二维显示信息和三维几何关系，能够捕获图像中的长期依赖关系，是传统方法难以建模得到的。但是目前已有的数据集并不能满足语义分割发展的需求，因此构建数据量大、种类丰富且有效的数据集非常重要。此外，现有的三维数据较为单一，大部分局限于室内场景和城市街道场景，而少有户外点云场景数据集与遥感三维数据集。

图形神经网络在计算机视觉中应用的可能方向也在不断增加，例如基于结构化场景图的生成图像方法，可以显式地描述对象和关系，并生成具有许多可识别对象的复杂图像；将人体骨骼连接形成图，应用时空神经网络识别视频中的人类动作有助于从机器方面更好地理解视频内容。

3.2 自然语言处理

虽然文本是单词序列，图神经网络仍可以应用于多种基于文本的任务，例如文本分类、机器翻译、关系抽取等。文本分类是自然语言处理中一个重要而经典的问题，可用于文档组织、新闻过滤、垃圾邮件检测、观点挖掘等应用中。传统的文本分类模型如RNN和CNN等，都能很好地捕捉局部连续词序列中的语义和句法信息，但可能会忽略具有非连续和远距离语义的语料库中的全局词共现。运用GNN便可解决上述问题，有三种建模方式。第一，通过词共现网络建模文本信息从而进行文本分类，其中词共现网络的节点是非停用词、连边是在给定窗口下的词共现关系。第二，利用文档间的结构信息构建文档关系网络进行文本分类。第三，将文档和单词同时作为节点来构建异构语料库图，使用异构图神经网络直接来学习单词和文档的嵌入。多种基准评测表明，在没有任何外部词嵌入或者知识库的情况下，基于GNN的文本分类效果要优于基于RNN或CNN的分类效果。此外，随着训练数据百分比的降低，基于GNN的文本分类效果相对于其他方法变得更加突出，这表明基于GNN的文本分类对较少训练数据具有鲁棒性。基于GNN的文本分类效果最佳的主要原因是建模成图既能捕捉文档词关系，又能捕捉全局词关系。但是值得注意的是，传统GNN不适合做情感分类任务，例如在电影评论数据集MR[20]上GNN的效果不如CNN和RNN，这是因为传统GNN无法建模在情感分类中非常重要的词序，且MR构建的图结构较为稀疏，限制了节点间消息的传递。因此如何在GNN模型中建模节点顺序信息，并提升GNN模型在稀疏图上的性能，是一个重大的挑战。

机器翻译旨在利用神经网络将文本从源语言自动翻译成目标语言，它通常被任务是一个“序列到序列”的任务，使用序列编解码器完成。例如Transformer[21]引入注意力机制，代替了传统RNN模型。实际上，Transformer假设所有单词之间有一个完全连通的图形结构，这就给基于GNN的机器翻译带来了可能。传统序列编解码器缺乏任何语法或语言层次结构的明确建模，因此添加句法信息并不会对翻译效果带来提升。而依赖GNN实现的编码器可以实现自动将源语句的句法邻域信息合并到特征向量中，从而潜在地提高翻译输出的质量。Bastings等人[22]首次完全依赖GNN实现机器翻译，GNN使用源语句的预测句法依赖树来产生对其句法领域敏感的单词表示，即编码器的隐藏层。输入源语句至GNN，模型会返回目标语句。此外，Marcheggiani[23]等人利用句法GNN整合了关于源句谓词论元结构的信息，即语义角色表征，并比较了仅整合句法信息、仅整合语义信息和两者的结果。相比传统的序列化算法，GNN的使用使得对象之间的复杂的语义关系得到了有效的挖掘[24]，在各项自然语言处理任务上都出现了一定的提升。

3.3 推荐系统

不论是电商还是社交网络，用户和商品的交互关系、用户和用户的关注关系天然形成了图结构，因此图神经网络在推荐系统中变得无处不在。在基于图的推荐系统中，以项目和用户为节点，其中的文本图像等信息形成节点特征，项目与项目、用户与用户、用户与项目之间的关系形成边，推荐系统的关键是评价一个项目对用户的重要性。因此，可以将其转换为一个链路预测问题，目标是预测用户和项目之间丢失的链接。RNN等序列模型只能对相邻的两个项目或物品的单向转移关系进行建模，忽略了其他项目，而GNN可以捕获节点间的高阶交互关系从而学习出高质量的节点表示。虽然基于GNN的推荐系统已经取得了很大的进展，但一些挑战仍然没有得到很好的解决，因此需要作出更多的努力。首先，在现实世界中，对象(包括用户和项目)以及它们之间的关系随着时间的推移而变化，从而产生的是动态图而非静态图。这种动态可能会对推荐结果产生重大影响，甚至会随着时间的推移而改变。然而这种情况往往被忽视或研究较少。其次，是基于因果推理的关系图学习。因果推理是发现对象或动作之间因果关系的主要技术。尽管在可解释的推荐方面已经取得了一些进展，但是我们还远远没有完全理解用户选择的原因和意图，这对于做出可靠的、可解释的推荐是非常关键的。

3.4 其他领域

除了以上三个领域外，图神经网络还可以应用于众多领域，如交通流量预测，通过将路网数据转换为时空图结构，利用GNN结合RNN在时空图上进行多元时间序列预测，从而进行出行路线指导；将原子和化学键转换为图结构从而进行分子性质预测；将不同模态的医学影像利用图神经网络结合，学习脑功能分区对双向情感障碍的影响等等。

4 结语

图神经网络的出现，很好地填补了将深度学习应用于关系数据建模的技术空白，实现了图数据与深度学习技术的有效结合。随着图神经网络研究的发展与落地，超大规模图数据、动态图数据、实时交互式等应用场景也为图学习的研究带来了新的挑战。例如，如何在连续时间内对网络变化进行建模，如何支持模型参数的增量更新，如何保证可解释性和鲁棒性等。图上深度学习是关系数据建模的一个重要组成部分，这是一个很有前途和快速发展的研究领域，也是朝着人工智能技术未来迈出的重要一步。