A Comprehensive Survey on Graph Neural Networks

发表于

Introduction

  在这篇综述中，作者对图神经网络做了全面的概述。作者提出了一种新的分类，将图神经网络分为五类，分别是：图卷积网络，图注意力网络，图自动编码器，图生成网络和图时空网络（graph spatial-temporal networks）。作者对这些分类之内或之外的方法做了彻底的评论，比较和总结。然后，作者介绍了图神经网络广泛的应用，总结了关于图神经网络的数据集，开源代码和基准。最后，作者关于图神经网络的未来方向给出了建议。

  原文地址

Categorization and Frameworks

  图卷积网络在捕捉图结构依赖上扮演了一个中心角色。下面，简要介绍每一种分类。

fig 3

Table 1

Taxonomy of GNNs

  图卷积网络将传统数据上的卷积操作推广到图数据上。其关键是学得一个函数 $f$ 生成 节点 $v_i$ 的表示，通过聚合节点自己的特征和邻居的特征。

  图注意力网络同GCNs一样寻找一个整合函数来融合邻居节点，随机行走和候选模型来学得一个新的表示。关键的不同是，图注意力网络使用注意力机制，其对重要的节点，随机行走和模型赋予更大的权值。注意力参数和神经网络参数是在一个端到端框架中一起学得的。

  图自动编码器是一种无监督学习框架，其旨在学习低维节点向量，先通过一个编码器，然后使用解码器来重构图数据。图自动编码器不管是对有无属性的网络来说，都是学习图嵌入的流行方式。

  图生成网络旨在从数据中生成似是而非的结构。给定图经验分布生成图具有根本的挑战性，主要是因为图是复杂的数据结构。为了解决这个问题，研究者们将生成过程分解为交替生成点和边，并引入生成对抗训练。

  图时空网络旨在从时空图中学习看不见的模式，其在许多应用中越来越重要，如交通预测和人类活动预测。图时空网络的关键思想是同时考虑空间依赖和时间依赖。

Frameworks

  图神经网络，尤其是图卷积网络，试图在图数据上复制 CNN 的成功，通过以频谱理论或空间位置来定义图卷积。使用图结构和节点内容信息作为输入，GCN 的输出使用一下的机制之一聚焦于不同的图分析任务：

  • Node-level 输出是关于节点回归和分类任务。因为图卷积模块直接给出节点的隐表达，一个多层感知机或是一个softmax 层用来作为 GCN 的最有一层。
  • Edge-level 输出关于边分类和链路预测。为了预测边的标签或是连接强度，一个额外的函数使用来自于图卷积模块的两个节点的隐表示作为输出。
  • Graph-level 输出关于图分类任务。为了获得图级的紧凑表示，池化模块被用来将图粗粒化为子图或是求和/平均所有节点的表示。

  端到端训练框架。图卷积网络可以在端到端框架之内使用监督或半监督或无监督的方式训练，这取决于学习的任务和手中可用的标签信息。

  • Semi-supervised learning for node-level classification 给定一个图，其中仅部分节点有标签，图卷积网络可以学到一个鲁棒的模型，其可以有效识别未标注节点的类标签。为此，可以通过堆叠一些图卷积层，后跟 softmax 层来构建多类分类的端到端框架。
  • Supervised learning for graph-level classification 给定一个图数据集，图级的分类旨在为整个图预测类标签。对这个任务的端到端学习可以联合图卷积层和池化过程。特别的，通过使用图卷积层，我们可以在单个图上为每个节点获得固定数目的表示。然后，我们可以获得整个图的表示，通过池化操作。最后，使用线性层和 softmax 层，我们就可以构建一个用于图分类的端到端框架。
  • Unsupervised learning for graph embedding 当图中无可用的类标签信息时，我们可以纯无监督的方式学习图嵌入，在端到端框架中。这些算法在利用边级信息有两种方式。一种简单的方式是采用自动编码器框架。另一种方式是使用负采样方法，其中采样节点对的一部分作为负样本，而现有的具有连结的节点对作为正样本。然后，在卷积层后使用 logistic 回归层，用于端到端学习。

Graph Convolutional Networks

  GCNs 方法可以分为两类，基于频谱的方法和基于空间的方法。基于频谱的方法通过引入来自图信号处理的过滤器来定义图卷积，其中卷积操作被阐释为移除图信号的噪声。基于空间的方法将图卷积定义为整合来自邻居的特征信息。

fig 1

Spectral-based GNNs

  背景。在基于频谱的方法中，图被认为是无向的。无向图的一个鲁棒的数学表示是范数图拉普拉斯矩阵：$L = I_n - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$，其中D是节点度的对角矩阵，$D_{ii} = \sum_j{A_{ij}}$。范数图拉普拉斯矩阵具有真对称半正定性质。具有这个性质，其可以被分解为$L = U\Lambda U^T$，其中$U$是按照特征值排列的特征向量矩阵，$\Lambda$是特征值的对角矩阵，$\Lambda_{ii} = \lambda_i$ 。范数拉普拉斯矩阵的特征向量来自于一个正交空间，也就是$UU^T = I$ 。在图信号处理中，$x \in R^N$ 是图中一个节点的特征向量。对 $x$ 来说，图傅立叶变化被定义为 $\mathcal{G}(x) = U^Tx$，逆图傅立叶变化是$\mathcal{G}^{-1} = U\hat{x}$。为了理解图傅立叶变换，从它的定义我们看到它确实将输入图信号投影到正交空间，其中基由由范数图拉普拉斯算子的特征向量形成。变换信号$\hat{x}$的元素是新空间中图信号的坐标，这样输入信号就被表示为 $x = \sum_i{\hat{x}_iU_i}$，这恰恰就是逆傅里叶变换。现在，对于输入信号$x$，具有一个过滤器$g \in R^N$的图卷积定义如下：

equal 1

如果我们将过滤器记为$g_\theta = diag(U^Tg)$ ，图卷积可以简化为：

equal 2

（ps：Eq.1 等于 Eq.2）

基于频谱的图卷积网络都遵循这个定义。关键的不同在于对过滤器$g_\theta$的选择。

  基于频谱的 GCNs的方法：

  Spectral CNN:

假设过滤器 $g_\theta = \Theta_{i,j}^k$是一组可学习的参数，并认为图信号是多维的，其将图卷积层定义为：

equal 3

   Chebyshev Spectral CNN（ChebNet）：

将过滤器定义为特征值的对角矩阵的切比雪夫多项式，也就是

chebyshev

切比雪夫多项式由$T_k(x) = 2xT_{k-1}(x)-T_{k-2}{x}$，$T_0(x) = 1,T_1(x) = x$所递归的定义。

作为结果，图信号 $x$ 的带有过滤器$g_\theta$ 卷积被定义如下：

eq4

  First order of ChebNet （1stChebNet：

是对 ChebNet的一阶近似。假设 K = 1 和 $\lambda_{max} = 2$，Eq.4. 被简化为：

eq5

  为了抑制参数数目和避免过拟合，1stChebNet 进一步假设$\theta = \theta_0 = -\theta$，得到下面的土卷积的定义：

eq6

  为了处理多维的图输入信号，1stChebNet提出来Eq.6.修改版本：

eq7

  由1stChebNet提出的该图卷积是位于空间中的，它弥合了基于频谱方法和基于空间方法之间的裂隙。输出的每一行代表每个节点的潜在表示，该潜在表示是通过对来自节点本身及其相邻节点的聚合信息进行线性变换而获得的，其权重由$\widetilde{A}$的行指定。

  Adaptive Graph Convolution Network（AGCN):

为了利用图拉普拉斯矩阵上不明确的隐式的结构关系，该方法使用一个残差图增强了图，该残差图是计算节点对之间的距离而构建的。

  总结：

  1. 依赖对范数图拉普拉斯矩阵的特征分解
  2. 任何对图的排列变化会导致特征基的变化
  3. 学习的过滤器是域独立的，不能用于具有其他结构的图上
  4. 特征分解时间复杂度是$O(N^3)$，空间复杂度是$O(N^2)$
  5. 需要将整个图加载进内存中来执行卷积操作

Spatial-based GNNs

  基于空间的GCNs可以被分类两类：基于循环的方法和基于组合的方法。基于循环的方法使用同一个图卷积层来更新节点的隐表示，而基于组合的方法使用不同的图卷积层来更新隐表示。Fig. 7展示了这中不同。

fig 7

  Recurrent-based Spatial GCNs：

  Graph Neural Networks(GNNs)作为图神经网络早期工作之一，GNNs循环的更新节点隐表示直到收敛。GNNs的空间图卷积定义如下：

eq8

为了保证收敛，循环函数$f(\cdot)$必须是收缩映射，其收缩两个点在映射之后的距离。

  Gated Graph Neural Networks（GGNNs使用GRU作为循环函数，减少了循环的次数。

eq9

不同于GNNs，GGNNs使用时间后向传播来学习参数。优势是不在需要约束参数确保收敛。缺点是，时间和空间效率受影响。

  Stochastic Steady-state Embedding（SSE）是为了改善学习效率而提出来的，其以异步的方式来随机更新节点隐表示。如Algorithm 1所示，SSE通过采样批数据循环的估计节点隐表示和更新参数。为了确保收敛到稳定状态，SSE的循环函数被定义为历史状态和新状态的权重的和：

eq10

尽管求和邻居信息隐示的考虑到了节点度，但这种求和的规模是否会影响算法的稳定性依然是一个问题。

Algorithm 1

  Composition Based Spatial GCNs ：

  Message Passing Neural Networks（MPNNs）包含两个阶段，消息传递阶段和读出阶段。消息传递阶段实际上运行 T-step 的基于空间的图卷积。图空间卷积由消息函数$M_t(\cdot)$和更新函数$U_t(\cdot)$定义：

eq11

读出阶段实际上是一个池化操作，其基于每个节点的隐表示得到整个图的表示：

eq12

  GraphSage一引入聚合函数来定义图卷积。聚合函数可以集成节点邻居的信息，它必须对节点次序的排列具有不变性，如求和，均值和最大值。图卷积操作定义如下：

eq13

GraphSage 提出一种批训练算法。首先，它取样一个节点固定数目的局部的 k-hop 邻居。然后，它通过聚合邻居节点的特征信息得到中央节点最后的状态。最后，它使用中央节点最后的状态来做预测和后向传播错误。这个过程如Fig 8所示。

fig 8

  Miscellaneous Variants of Spatial GCNs：

  Diffusion Convolution Neural Networks(DCNN)提出了一种图形卷积网络，它封装了图扩散过程。一个隐藏的节点表示通过使用转移概率矩阵的指数系列独立卷积输出而获得。DCNN的扩散卷积运算定义如下：

eq14

  PATCHY-SAN使用CNN来解决图分类问题。它将图结构的数据转换为网格结构数据。

  Large-scale Graph Convolution Networks（LGCN）提出一种基于节点特征信息的排序算法。

  Mixture Model Network(MoNet)将标准CNN与非欧几里得域上的卷积结构统一起来。MoNet引入伪坐标和权重函数，以使节点邻居的权重由节点与其邻居之间的相对位置（伪坐标）确定。

Graph Pooling Modules

  图池化模块可以减少方差和计算复杂度，通过对原始特征数据下采样。

  图池化有如下几种方法：

  1. 均值/最大值/求和池化
  2. ChebNet：对图粗粒化
  3. DGCNN：对节点根据它们在图中的结构角色排序。
  4. DIFFPOOL:可以生成图的层次表示

Comparison Between Spectral and Spatial Models

  1. 效率上。基于频谱的方法的计算代价随图大小急剧增大，因为需要同时计算特征向量和处理整个图，令平行处理和应对大规模的图很难。
  2. 泛化性。
  3. 灵活性。基于频谱的方法只适用于无向图，因为对有向图的拉普拉斯矩阵还没有清晰的定义。

Beyond Graph Convolutional Networks

Graph Attention Neworks

  注意力机制的优点是它们能够集中于一个物体上最重要的部分。图神经网络在聚合，整合多个模型的输出和产生面向重要性的随机行走时使用注意力机制，并从中受益。

  Methods of Graph Attention NetWorks ：

  Graph Attention Newtork(GAT)在聚合邻居特征信息时使用注意力机制。

eq20&21

  Gated Attention Network（GAAN）提出multi-head注意力机制来更新节点的隐状态，并引入自注意机制来为每个 head 计算权重：

eq22

  Graph Attention Model(GAM)提出循环神经网络模型来解决图分类问题，其通过访问重要节点序列来处理图的信息部分。模型定义如下：

eq23

  Attention Walks通过随机行走学习节点嵌入。不像deepwalk使用固定的优先级，Attention Walk使用不同的注意力权重来分解共线矩阵：

eq25

Graph Auto-encoders

  图自动编码器是学习图嵌入的方法。

  Graph Auto-encoder(GAE）第一次将GCN整合进自动编码器框架。

  Adversarially Regularized Graph Autoencoder（ARGA）引入对抗学习。

  Network Representations with Adversarially Regularized Autoencoders(NetRA) 使用sequence-to-sequence 架构重构随机行走的节点序列。

  Deep Neural Networks for GraphRepresentations(DNGR)使用堆叠去噪自动编码器来重构PPMI矩阵。

  Structural Deep Network Embedding(SDNE)使用堆叠自动编码器保留节点的一阶近似和二阶近似。一阶近似被定义为节点节点和它邻居隐表示之间的距离。

Graph Generative Networks

  图生成网络的目标是给定一组观察到的图，然后生成图。许多图生成网络是特定于领域的。

  方法：

  1. Molecular Generative Adversarial Networks (MolGAN)

    使用GAN 和RL 来生成具有所期望性质的图

  2. Deep Generative Models of Graphs (DGMG)

    • 交替重复增加节点和边的步骤，直至评价标准被激活。

  3. GraphRNN

    • 通过两级的循环神经网络
    • graph-level 的RNN 每一时间将一个新节点加入一个节点序列，edge-level RNN 为新节点和之前的节点产生边

  4. NetGAN

    • 联合 LSTM 和 Wasserstein GAN，基于随机行走的方法来生成图。

Graph Spatial-Temporal Networks

  图形时空网络同时捕捉时空图的空间依赖和时间依赖。

  方法：

  1. Diffusion Convolutional Recurrent Neural Network
    (DCRNN)
    • 引入扩散卷积来捕捉空间依赖，具有GRU的sequence-to-sequence 架构来捕捉时间依赖。
  2. CNN-GCN
    • 交替使用GCN和1D-CNN来学习时空图数据
  3. Spatial Temporal GCN (ST-GCN)
    • 将时间流扩展为图的边，以便可以使用统一的GCN模型同时提取空间和时间信息。
  4. Structural-RNN
    • 旨在在每个时间步预测节点标签
    • 由两种 RNNs 组成，nodeRNN 和edgeRNN。每个节点的时间信息通过nodeRNN和edgeRNN传递
    • 为不同的节点和边假设不同的nodeRNN和edgeRNN

Applications

Datasets

Table 5

Benchmarks & Open-source Implementations

Table 6
Table 7

Practical Applicatons

  1. 计算机视觉
    • 场景图生成
    • 点云分类和分割
    • 动作识别
    • 人-物交互
    • few-shot image classification
    • 语义分割
    • 视觉推理和问答
  2. 推荐系统
    • 链路预测（预测用户和事项之间缺失的连结）
  3. 交通预测
    • 流量预测
    • 出租车需求预测
  4. 化学
    • 分子手印
    • 预测分子性质
    • 蛋白质界面推理
    • 合成化合物
  5. 其他
    • 程序确认
    • 程序推理
    • 社交影响预测
    • 对抗性攻击避免
    • 脑网络
    • 事件检测
    • 组合优化

Future Direction

  1. 变得更深。
    • 这是由于图卷积的影响，因为它本质上推动了相邻节点的表示彼此更接近，因此理论上，无限次卷积时，所有节点的表示将收敛到单个点。
    • 这引发了一个问题，对于学习图结构的数据，变得更深是否是一个更好的策略。
  2. 感受野。
    • 一些节点具有很多邻居，一些则仅有很少的邻居。
  3. 可扩展性。
    • 一个节点的最后状态设计大量它的邻居的隐藏状态，这令后向传播很复杂。
  4. 动态和异质图。