图神经网络：方法和应用综述

简介

图代表着一种使用节点和链接表达关系的数据结构，近年来，图模型有了相当多的应用，在面对各种非结构化的数据时，更是需要图模型。图神经网络则是通过节点建立信息的依赖，图神经网络有很多变体，比如图卷积网络、图注意力网络、图循环网络等，这些网络表现出了惊人的性能。
在本文中，作者回顾了各类图神经网络，并对各类应用进行分类，详细如下

• 对近年来现有的图神经网络模型作了一个详细的回顾，并提出了一个可用于各变体模型的通用设计流水线
• 将各类应用概括为结构化场景和非结构化场景

• 提出了进一步研究需要面对的四个问题

  通用设计流水线

  

  图的类别

• 有向图和无向图，主要是指边是单向的还是双向的

• 同构图和异构图，同构图表示边和节点的种类都只有一种，而异构图表示边和节点种类有多种
• 动态图和静态图，是指在输入特征或图的拓扑是否随时间变化
• 超图，是指一条边不只可以跟两个顶点相连，可以连接多个顶点

这些类别可以相互组合。

任务类型

• 点级任务，包括节点分类，节点聚类，节点回归等
• 边级任务，包括边分类和链接预测，判定两点间是否存在边

• 图级任务，图分类，图回归和图匹配等

  计算模块

• 传播模块，传播模块用于在节点之间传播信息，可以使用类似残差网络的跳跃连接

• 采样模块，当图很大时，对其中一部分进行传播

• 汇聚模块，当需要高级子图时，用汇聚模块从节点提取信息

  模型实例

  

  传播模块——卷积操作

  光谱方法

• Spectral Network，该网络卷积计算操作十分复杂

• GCN简化了卷积操作步骤
• AGCN计算了节点之间的隐藏关系
• DGCN使用了两个卷积网络来计算局部和全局之间的关系

• GWNN**改变了光谱波计算的方法

  基本空间方法

• DCNN使用转移矩阵来表达节点的相邻节点，PATCHY-SAN为每个节点提取和归一化K个的节点的领域

• LGCN在节点的灵界矩阵上执行最大池化获得前k个特征元素，再用CNN计算。

• GraphSAGE通过节点的局部邻接采样和聚合特征来生成嵌入

  基于注意力的空间方法

• GAT将注意力纳入了传播步骤，遵循自注意力策略，关注节点的邻居来计算每个节点的隐藏状态，同时使用了多头注意力机制，使用K个头计算隐藏状态。

• GaAN使用了一种自注意力机制来收集来自不同头部的信息来代替 GAT 的平均操作。

  空间方法的一般框架

• MoNet融合了图神经网络和卷积神经网络。

• MPNN先从几个经典模型中提取一般特征。该模型包含两个阶段：消息传递阶段和读出阶段。
• NLNN概括并拓展了计算机视觉中的非局部均值运算，它将某个位置的隐藏转台计算为所有可能位置特征的加权和。

• GN（Graph Network）通过学习节点级、边级、图级表示，比其他网络更为通用

  传播模块——循环操作

  基于收敛的方法

• 在GNN中，更新隐藏状态使用基本方法是将前一迭代的隐藏状态和本次迭代的输入作为参数，输入到训练函数中，得到新的隐藏状态，这要求训练函数可以使得模型收敛，这限制了模型的能力，同时迭代到收敛处的过程是低效的

• GraphESN使用固定的收缩编码函数，并且只训练一个读取函数，收敛性用动力学的收敛性确保。
• SEE提出每个节点嵌入由更新步骤的参数化运算符更新

• LP-GNN将学习任务的形式化为拉格朗日框架中的约束优化问题

  基于门的方法

  有人尝试使用GRU和LSTM机制来减少GNN计算中的计算限制，但是不能保证收敛

• GGNN在传播过程使用门控神经单元，还使用时间反向传播来计算题都

• Graph LSTM传播的过程很容易适应图，这个网络架构是一个简化版本

• S-LSTM将文本转化为图形LSTM来学习，在NLP任务上表现了强大的能力

  传播模块——跳跃链接

  和残差网络相似，为了可以进行更深层的训练同时避免传播来自拓展邻域的指数增长的噪声信息，图神经网络使用了跳跃链接

• Highway GCN使用高速门，将输出与输入相加，并控制权重

• JKN将每一层的中间结点选择性跳到最后一层

• DeepGCNs借鉴了DenseNet的方法，通过残差和密集链接解决梯度消失的问题

  采样模块

  节点采样

  减少相邻节点大小的方法是为每个节点的邻域中选择一个子集

• GraphSAGE采样固定的少量邻接点，一般取2-50

• PinSage提出基于重要性的采样方法，从目标节点开始随机选，找到具有最高归一化访问计数的前T个节点

  层采样

  层采样不是采样邻接点，而是每一层留一组节点聚合

• FastGCN直接对每一层的感受野进行重要性采样

• LADIES训练一个参数化可训练的采样器进行逐层采样

  子图采样

  还可以采样子图，并限制子图中的邻域搜索。

• ClusterGCN通过图聚类算法对子图采样

• GraphSAINT直接对节点或者边进行采样生层子图

  汇聚模块

  在计算机视觉中，卷积层后一般会跟一个汇聚层以获取最重要的特征，这队节点级和图级分类任务非常重要

  直接汇聚模块

• Simple Node Pooling使用节点的最大值/均值/综合/注意力应用于节点的特征

• Set2set使用LSTM为基础的方法处理无序结合生成有序不便表示

• SortPooling现根据节点的结构角色对节点嵌入排序，再将排序结果输入CNN

  分层汇聚模块

  之前的方法只从节点学习，没有关注整个图的结构，接下来讨论分层学习表示方法

• Graclus提供了一种更快的节点集群方式

• ECC设计了具有递归下采样操作的汇聚模块
• DiffPool通过在每一层训练分配矩阵来实现可学习的层次聚类模块
• gPool使用投影向量来学习每个节点的投影分数，并选择最高分数的节点
• EigenPooling联合节点特征和局部特征，用局部图傅里叶变化提取子图信息

• SAGPool用来联合特征和拓扑学习图表示，基于自注意力机制

  图的类型和比例

  
  有向图和异构图一般可以提供更丰富的信息，更被广泛使用

  异构图

  基于关键路径的方法

  关键路径方案被广泛使用，可以捕捉不直接链接的节点的联系

• MAGNN考虑了关键路径中的中间结点，并使用关键路径聚合信息

• GTN在学习节点表示的同时识别未连接节点的新链接

  基于边的方法

• HetGNN通过采样、特征编码和聚合步骤中区别对待不同类型的邻接节点

• HGT将关键路径定义为两个相邻节点类型和链接

  基于关系图的方法

  G2S将边也转换成节点，原始边被拆分为两条新边
  GGNN的聚合函数将节点隐藏表示和关系作为输入
  R-GCN为不同类型的边传播时分配不同的权重矩阵

  多重图方法

  图中的一对节点可以与多个不同类型的边相关联，在不同类边下查看，图可以分为多层，每一层代表和一类边的关系，多重图也成为多视图
  mGCN介绍了 GNN 每一层节点的一般表示和特定维度表示。

  动态图

  图结构的边和节点随着时间不断变化，将图与时间序列一起建模

• DCRNN首先通过GNN收集空间信息，在输入到序列模型中

• ST-GCN同时收集空间和时间信息，并使用时间链接拓展静态图结构
• DGNN将来自每个节点的输出嵌入提供给单独的LSTM
• EvoloveGCN将GCN权重输入RNN捕获图交互的内在动态

  训练技术

  

  图自动编码

  无监督训练一般是使用自动编码器拓展到全图

  对比学习

  通过图级表示和不同尺度（包括节点、边和三角形）的子结构级表示之间的互信息最大化来学习图表示

  GNN设计过程

1. 寻找图结构
2. 指定图类型和比例
3. 设计损失函数
4. 使用计算模块构建模型

   图结构应用

   结构化场景

   图挖掘

   通常，图挖掘算法用于识别下游任务的有用结构。 传统的图挖掘挑战包括频繁子图挖掘、图匹配、图分类、图聚类等。

   物理学

   模拟现实世界的物理系统是理解人类智能的最基本方面之一。 物理系统可以建模为系统中的对象和对象之间的成对交互。 物理系统中的仿真需要模型学习系统的规律并预测系统的下一个状态。

   化学与生物学

   主要有分子指纹，化学反应预测，蛋白质预测，生物工程

   知识图谱

   知识图 (KG) 表示现实世界实体的集合以及实体对之间的关系事实。

   生成模型

   现实世界图的生成模型因其重要的应用而引起了极大的关注，包括建模社交互动、发现新的化学结构和构建知识图。

   组合优化

   图上的组合优化问题是一组 NP-hard 问题，引起了各个领域科学家的广泛关注。 一些特定的问题，如旅行商问题 (TSP) 和最小生成树 (MST)，已经得到了各种启发式解决方案。 最近，使用深度神经网络解决此类问题已经成为一个热点，一些解决方案由于其图结构而进一步利用了图神经网络。

   交通网络

   预测交通状态是一项具有挑战性的任务，因为交通网络是动态的，具有复杂的依赖性。

   推荐系统

   用户项交互预测是推荐中的经典问题之一。通过将交互建模为图形，GNNs可以在这一领域中使用。

   非结构化场景

   图像处理

   主要包括少样本图像分类，视觉推理，语义分割等

   文字处理

   主要包括文字分类，序列标签，神经机器翻译，关系抽取，事件抽取等

   公认问题

• 稳健性
• 可解释性
• 图预训练
• 复杂图结构