图神经网络研究综述(GNN)，非常详细收藏我这一篇就够了！

图神经网络由于其在处理非欧空间数据和复杂特征方面的优势，受到广泛关注并应用于推荐系统、知识图谱、交通道路分析等场景。

大规模图结构的不规则性、节点特征的复杂性以及训练样本的依赖性给图神经网络模型的计算效率、内存管理以及分布式系统中的通信开销带来巨大压力。本文首先简要介绍图神经网络模型中的消息传递机制，分类介绍常见的图神经网络模型，并分析其在大规模数据训练中面临的困难和挑战；然后对面向大规模数据的图神经网络算法模型进行分类总结和分析，包括基于节点、边和子图的采样算法；接着介绍图神经网络编程框架加速的相关进展，主要包括主流框架的介绍以及优化技术的分类总结和分析。

1 引言

图结构可描述复杂关系，如基因结构、通信网络、交通路线、社交网络等。图计算挖掘结构信息，但无法学习节点特征。神经网络在欧氏空间数据上表现优越，但无法直接应用于非欧氏空间的图数据。图神经网络结合图计算和神经网络优势，处理非欧氏空间数据及其复杂特征，应用于网络链接预测、推荐系统和交通道路分析等场景。实际应用中，图数据规模庞大，如百亿级节点、千亿级边，存储开销超过10TB。GNN在大规模数据中面临计算效率、内存管理和分布式通信开销的挑战。图神经网络模型在大规模数据应用中面临的挑战可分为图数据结构、图神经网络模型、数据规模、硬件平台。

(1) **图数据结构。**图数据结构的不规则性、稀疏性、动态性、节点邻居数量呈幂律分布及样本间相互依赖，对高效访存和分布式计算系统提出挑战。

(2) **图神经网络模型。**节点高维表示是图神经网络的显著特征，提高模型能力，但计算和内存开销增大，尤其在大规模数据中面临挑战。深层图神经网络模型因迭代更新机制，面临邻居节点爆炸问题。

(3) 数据规模。图神经网络整批训练受内存限制，分批训练增大数据划分和迭代更新难度。

(4) 硬件结构。图神经网络模型在图数据结构和复杂特征方面有建模需求，需要灵活的不规则数据读取和高效的密集计算。CPU和GPU各有优势，但无法同时满足这两点需求，增加了大规模图神经网络模型加速的难度。

为了提高[图神经网络（GNN）]模型的可拓展性、加速运行过程和减小内存开销，以应对和缓解相关困难和挑战。研究者在应用模型方面，针对自然语言处理、交通预测和推荐系统等应用场景，提出提高图神经网络处理效率的策略。在算法模型方面，针对内存不足问题，研究采用分批训练，如GraphSage、FastGCN等。在编程框架方面，为解决训练样本依赖性，提出DGL、PyG等编程框架。在硬件结构方面，结合CPU、GPU、FPGA等硬件结构，提出优化策略或专用硬件加速结构，如HyGCN。如图1：

图1 GNN 整体框架图

表1列出了本文相关综述。综述[29-32]关注图神经网络模型的全图训练模式及其应用。然而，当节点或边数量庞大时，训练过程受限于单块GPU内存。为解决此问题，采样算法支持图神经网络模型从全图训练转向分批训练，并应用于大规模数据。图神经网络编程框架结合深度学习框架和图结构特征，提高存储利用率和计算效率，促进大规模数据应用。综述[33-34]主要总结图神经网络编程框架进展。综述[36-38]关注分布式平台，总结分析分布式GNN在算法模型、软件框架和硬件平台等方面的进展。

表1 图神经网络相关综述

本文针对大规模图神经网络，从算法模型和框架优化两方面进行调研、总结和分析。首先介绍GNN基础知识和典型算法，接着总结不同粒度采样策略的图神经网络模型，以及主流加速框架及相关技术。为后续图神经网络在大规模数据应用中框架-算法的协同优化提供思路。

本文内容组织如图2所示：

图2 本文内容组织

2 图神经网络

图神经网络(GNN)是一种用于图结构数据的神经网络模型，结合图计算和神经网络优势，捕捉图结构并抽象节点特征。图计算模型擅长捕捉拓扑结构，但无法处理高维特征。典型神经网络适用于欧氏空间数据，如卷积神经网络处理网格数据，循环神经网络处理序列信息。针对非欧氏空间复杂图数据，建模过程需要新处理机制。目前受欢迎的消息传播模式通过获取高阶邻居信息提升节点表达能力，包括邻居聚合和节点更新两步。

本节从消息传递机制出发，介绍图神经网络模型的聚合和更新操作，分类介绍图卷积神经网络、图注意力网络、循环图神经网络和自编码器图神经网络，分析其在大规模数据训练中的挑战，并总结挑战。

2.1 消息传递机制

基于神经网络的消息传递机制描述了节点特征在网络中进行传播的过程, 传播结果最终会通过神经网络操作迭代地更新在节点表示中。图神经网络表示模型能够捕捉图结构信息和建模复杂的节点特征

2.2 常见模型

**图卷积神经网络（Graph Convolutional Network, GCN）****。**GCN是常见图神经网络模型，通过卷积操作实现邻居节点聚合。GCN模型分为基于谱域和基于空间域两类，其中基于谱域的方法基于图信号分析和图谱论，基于空间域的方法关注邻居节点的直接聚合方式。

大规模数据训练中，GCN面临内存不足和邻居爆炸问题。分批训练可缓解内存限制，但增加计算和内存消耗。随着层数增加，资源消耗呈指数级增长。

**图注意力网络（Graph Attention Network,GAT）。**GAT是一种深度学习模型，用于处理图结构数据。它通过引入注意力机制，为每个节点分配不同权重，以捕捉节点间的依赖关系。GAT在图神经网络中具有高效性和可扩展性，广泛应用于社交网络、推荐系统和生物信息学等领域。

大规模数据训练中，GAT与GCN均存在内存不足和邻居爆炸问题。GAT采用注意力权重加权聚合，计算和存储资源消耗更多。

循环图神经网络（Gated Graph Neural Network，GGNN）。循环神经网络（RNN）用于建模序列信息，如文本、用户历史记录和音视频。长短期记忆网络（LSTM）和门控循环单元（GRU）是RNN的两种常见形式。GGNN模型基于GRU，针对输出状态序列的任务，而GCN和GAT模型以静态图为输入。GGNN以时间演化图为输入，通过遗忘门和更新门等结构捕捉图结构演化特征。

大规模数据训练中，GGNN需载入整个邻接矩阵，占用更大内存。训练涉及大量参数，内存挑战显著。分批训练中，图数据不规则性增加冗余计算。

基于自编码器的图神经网络（Structural Deep Network Embedding，SDNE）。自动编码器由编码器和解码器组成，通过无监督学习高效学习节点表示。SDNN模型将自动编码器应用于图结构数据，和典型自动编码器模型相同, SDNN 需要减小节点的重构损失。此外, 还考虑节点间的相似性。

SDNE无法捕捉节点间的高阶关联，需通过损失函数捕捉节点间直接关联，但在大规模数据训练中，内存限制导致分批训练产生冗余计算。尽管采用负样本采样，图数据的不规则性仍带来挑战。

表3概括了图神经网络模型、图数据结构以及数据规模三个方面基于不同模型训练方式（整批训练和分批训练）的挑战。

表3 图神经网络在大规模数据应用中存在的挑战

(* 表示产生相关挑战的主要原因)

3 图神经网络采样算法

针对图神经网络在大规模数据训练中面临的挑战，已经开展了一些有意义的算法优化工作。大部分的工作都集中在数据的优化上，其中最主要的方法是使用不同粒度的采样算法实现分批训练。这些算法主要可以按照采样粒度分为以下三类：基于节点的采样算法、基于层的采样算法以及基于子图的采样算法。

3.1 基于节点的采样算法

GraphSage。GraphSage采用节点采样进行表示学习，优化模型参数。如图3(b)所示，针对目标节点，随机采样固定数目邻居节点，使用聚合函数进行特征聚合，借助反向传播学习。通过优化模型实现新数据表示，并借助随机节点采样算法将不规则图结构数据规则化，实现参数共享。

PinSage。PinSage算法结合随机游走和图卷积操作，用于大规模推荐系统。通过节点采样构建计算图，捕捉图结构特征，提高图卷积神经网络模型在大规模数据上的可拓展性。提出基于重要性的节点采样算法，如图 3©所示，利用随机游走策略评估节点重要性，对每个节点选择最重要的k个节点作为采样节点，并在聚合过程中进行重要性加权。

VR-GCN。VR-GCN是一种新的采样算法，解决了大规模图神经网络参数共享问题，通过方差消减保证收敛性，并证明采样规模不影响局部最优性能。如图 3(d)所示，针对目标节点，VR-GCN仅采样两个节点，利用历史激活节点减小方差，显著减小估计梯度的偏置和方差。与考虑所有邻居节点的情况相比，VR-GCN仅考虑2个邻居节点，大大减小了模型训练的时间复杂度和内存开销。

LGCL。LGCL将图数据结构化以满足卷积操作的要求，通过节点特征重组将不规则图结构数据转化为欧氏空间，便于利用CNN算法进行优化。然而，基于显著特征的重组方式在一定程度上破坏了节点特征多样性，加剧了节点表示过度平滑问题。以图3(e)为例，采样均值聚合方式导致节点特征值趋于接近对应特征最大值，最终所有节点表示趋于相似，加剧图卷积神经网络的过度平滑问题。

总结。针对图神经网络中直推式训练模型存在的局限性，GraphSage提出了基于节点的采样算法，通过随机采样一阶和二阶邻居以适应归纳式任务。PinSage提出了基于重要性的采样算法，并在节点聚合中进行重要性加权。VR-GCN关注采样算法的收敛性，通过减小梯度估计的偏置和方差来提高算法收敛性。LGCL从特征粒度进行筛选重组为新的节点进行聚合。

图3 基于节点的采样算法

3.2 基于层的采样算法

FastGCN 。FastGCN通过将图卷积操作转化为概率分布积分形式，如图4(a)所示，并利用蒙特卡洛法估计积分值，解决了图神经网络大规模数据训练中的时间和内存开销问题。FastGCN采用层级采样避免邻居节点爆炸，并基于采样的损失函数和梯度函数进行模型训练，同时通过重要性采样优化性能。

AS-GON。AS-GON是一种自适应层级采样算法，通过逐层固定采样节点数避免GCN中邻居节点爆炸问题。基于上层采样结果对下层节点进行采样，使下层采样邻居节点被尽可能多的上层节点共享。AS-GON还通过连接跳跃捕捉二阶相似性，利用连接跳跃策略获取二阶邻居特征，传播高阶邻居特征信息，无需额外采样开销。

LADIES。LADIES是一种新的采样算法，旨在解决基于节点和基于层的采样算法中存在的挑战。如图4(d)所示，该算法根据上层节点及其邻居节点构建二分图，计算重要性分数作为采样概率，并依概率采样固定数目的邻居节点作为下层节点。通过迭代构建整个计算图，可以有效地降低计算和内存开销。

总结。PastGCN通过层级采样估计积分值，避免邻居节点爆炸，但存在连接稀疏和冗余节点问题。AS-GCN通过显式方差消减保证收敛性，并捕捉二阶关联性。LADIDS基于二分图构建相邻两层节点，进行层级重要性采样，缓解邻居节点爆炸问题，但全局节点复用有限。

图4 基于层的采样算法

3.3 基于子图的采样算法

Cluster-GCN。Cluster-GCN通过子图采样算法提高了GCN分批训练的计算效率。通过聚类感知的划分算法Metis将节点划分为c块，并将邻接矩阵转化为对角矩阵A和B。将GCN的表示函数分解到不同的聚类分块中，并通过随机组合分块来缓解存在的边遗漏和估计误差的问题。在分批训练中，每一批随机选择多个聚类分块而不是将单个分块作为训练数据。

**RWT。**RWT是一种逐层游走的训练策略，用于解决 Cluster-GCN 在大规模图应用中的时间和空间开销问题。通过子图采样算法实现图数据分批，每批次构建图神经网络模型进行训练。采样策略综合考虑随机性和图结构连接性，采用逐层扩张方式从当前子图邻居节点中采样并更新子图，直至达到阈值。RIWT 在 GCN 和 GAT 上验证了有效性。

**GraphSAINT。**GraphSAINT是一种基于采样的图神经网络模型，通过先采样子图再构建网络模型，消除分批训练偏差，并降低分批方差。首先，估计节点和边的采样概率，然后在每个训练批次中进行子图采样，并构建完整的GON模型进行训练。通过归一化方法消除偏差，同时借助随机游走策略优化采样算法。Zeng等提出了GraphSAINT，通过偏差消除和误差降低提高精度。他们提出了一个并行训练框架，通过子图采样分批训练，提高程序并行性。采样器间和采样器内并行化理论上带来近线性加速比。特征传播方面，通过数据划分提高缓存利用率，减小通信开销。此外，他们还提出了运行时调度器，通过重排操作顺序和调整分批图优化并行性能。

SHADOW-GNN。SHADOW-GNN是一种图神经网络模型，旨在解决大规模数据带来的挑战，并缓解过度平滑问题。通过解耦节点接受区域与图神经网络深度之间的关联，实现深层网络表达能力，同时避免过度平滑。SHADOWGNN采用子图采样策略，形成不同子图，然后在子图上应用任意深度的图神经网络模型，获得节点表示。

**总结。**Cluster-GCN通过节点聚类提高节点利用率，如图 5©所示；RWT借助随机游走策略逐层扩张子图，如如图 5(b)所示；GraphSAINT侧重减小估计偏差与方差，提高模型性能；SHADOWGNNI63借助图采样策略增强模型可拓展性，缓解过度平滑问题，如图 5(d)所示。

图5 基于子图的采样算法

Zeng等人在5个数据集上（表4）比较了4种采样算法在节点分类任务上的准确性性能对比结果如表 5所示，基于子图的采样算法在不同数据集上表现更好，micro E1指数更高且方差较小。GraphSage在数据集Flickr、Reddit、Yelp和Amazon上的节点分类准确性与基于子图的采样算法接近，但训练时间较长。

表4 数据集统计信息

表 5 节点分类性能对比

针对大规模数据训练中存在的挑战，本节总结了不同粒度的采样算法（如表6所示），如节点级、层级和子图级采样算法。这些算法在一定程度上缓解了大规模数据训练中存在的内存限制问题，增加了模型的可拓展性，并通过重要性采样、方差消减、随机组合等方式提高模型收敛性。然而，目前的采样算法主要基于静态的同构图进行优化，忽略了现实应用中图数据的异构性、动态性、幂律分布等复杂特征。

表 6 采样算法总结