文献地址：https://ieeexplore.ieee.org/document/9046288

摘要

深度学习处理的机器学习任务
- 图像分类
- 视频处理
- 语音识别
- 自然语言处理
上述四大任务数据的特点
目前处理的对象的数据通常是在 欧式空间 中表示
存在的问题
很多数据其实是以图这种 非欧式空间 表示
- 数据之间存在 复杂的关系 【比如警察推断的嫌疑人之间存在某种不可描述的联系】
- 对象之间存在 相互依赖性 【嫌疑人之间的相关性】
本文的概述领域
- 数据挖掘
- 机器学习
本文的意义
- 提出了一种新的分类
  - 递归图神经网络 (recurrent graph neural networks, RecGNNs)
  - 卷积图神经网络 (convolutional graph neural networks, ConvGNN)
  - 图自编码器 (graph autoencoders, GAE)
  - 考虑时间因素的图神经网络 (spatial-temporal graph neural networks, ST-GNN)
- 讨论图神经网络在各个领域的应用
- 总结了 GNN 的开源代码、基准数据集和模型评估
- 潜在的研究方向

介绍

机器学习解决的任务【严重依赖于工人数据标注】
- 目标检测
- 机器翻译
- 语音识别
目前解决上述任务的方法【端到端的深度学习方法】
- 卷积神经网络（convolutional neural network, CNNs）
  - 平移不变性【目标无论平移到哪，其标签不变】
  - 局部连通性
  - 合成性
- 递归神经网络 (recurrent neural network, RNNs)
- 自编码器 (autoencoders, AE)
深度学习取得成功的两点原因
- 强大的计算资源
- 大量可用的数据
- 从欧式空间【图片、文字、视频】中提取潜表示的有效性
  - 可以有效从欧式数据中得到潜模式
目前存在的问题：
- 目前许多应用中的数据使用的是图形形式
- 图形数据复杂性高【图不规则｛具有可变大小的无序节点｝】
- 图形中的数据不再相互独立
二维卷积 VS 图卷积

二维卷积 VS 图卷积
- 左图：将图片中的每一个像素作为节点，其邻居由 Filter 决定；
  图中橙色节点的更新方式是 其与邻居节点的加权平均值；
  节点是有序的并且具有固定的大小【1 + 8 】
- 右图：类同于二维卷积，橙色节点的更新方式是 取其与邻居节点的节点特征的平均值；
  节点是无序的并且大小可变【不同节点有不同数目的邻居】
本文的贡献：
- 新的分类方法：循环图神经网络、卷积图神经网络、图自编码器、考虑时间因素的图神经网络
- 全面的综述：对现有的深度学习技术进行详细的说明以及比较，最后总结了相应的算法
- 丰富的资源：收集了大量的资源【最新模型、基准数据集、开源代码以及实际应用】
- 未来方向：讨论了图神经网络的理论方面，分析现有方法的局限性；
- 在模型深度、可伸缩性折中、异质性与动态性四方面提出了可能的方向

背景以及定义

背景

图神经网络 VS 网络嵌入
- 网络嵌入：目的是将网络节点表示为低维向量，同时保留网络的拓扑结构和节点内容信息
- 图神经网络：目的是以端到端的方式解决与图相关的任务，其提取高级表示
- 两者的本质区别：
  - GNN 是一组用来为各种任务而设计的神经网络模型
    - 通过AE框架解决网络嵌入问题
  - 网络嵌入主要是针对同一任务的各种方法
    - 网络嵌入中包含非深度学习方法【SVD 和 Random Walk】
图神经网络 VS 图核方法
- 图核方法：用于解决图分类的方法，这些方法通过核函数来计算图对之间的相似度【用于图的监督学习】；
  其可以通过映射函数将图或者节点嵌入向量空间
- 两者的区别：
  - 图核方法的映射方法是确定的而不是学习得到的
  - 图核方法计算图对之间的相似度计算力太大
  - GNN 直接基于提取的图形表示执行图形分类

定义

符号表示

本文用到的符号表示
图：图的表示为 $G = (V, E)$ ，其中 $V$ 是图中节点的集合， $E$ 是边的集合，使用 $v_i \in V$ 表示一个节点， $e_{ij} = (v_i, v_j) \in E$ 表示从节点 $v_j$ 到节点 $v_i$ 的边，节点 $v$ 的邻居节点定义为 $N(v) = \{{u \in V|(u, v) \in E}\}$ ，邻接矩阵 $A$ 是 $n \times n$ 的矩阵，并且 $\left\{\begin{aligned}A_{ij} &=1，如果e_{ij} \in E\\A_{ij}&=0，如果e_{ij} \notin E\end{aligned}\right.$ ，图的节点属性使用 $X$ 进行表示，其中 $X \in R^{n \times d}$ 是一个节点特征矩阵， $x_v \in R^d$ 表示节点 $v$ 的特征向量，图的边属性使用 $X^e$ 进行表示，其中 $X^e \in R^{m \times c}$ 是一条边的特征矩阵， $x_{u, v}^e \in R^c$ 表示边 $(u, v)$ 的特征向量。
有向图：边是带有箭头的边
考虑时间因素的图：节点属性随时间的变化而变化的图，表示为 $G^{(t)} = (V, E, X^{(t)}), 其中X^{(t)} \in R^{n \times d}$

类别与框架

类别梗概

图形表示

类别图
递归图神经网络 (RecGNNs)
- 目的是通过 递归神经网络架构 学习节点表示【假设图中的节点不断与其邻居进行信息交互】
卷积图神经网络 (ConvGNNs)
- 主要思想是通过 聚合节点 $v$ 的特征 $x_v$ 及其邻居节点的特征 $x_u$ 得到节点 $v$ 的特征
- 与RecGNNs的不同：ConvGNNs通过堆叠多个卷积层提取高级节点的表示
用于进行节点分类的ConvGNN

具有多个图卷积层的ConvGNN
图解【用于节点分类】
- 图卷积层通过聚合来自其邻居的特征信息来封装每个节点的隐表示
- 特征聚合之后，将非线性变换应用与结果
- 通过堆叠多层，每个节点的最终隐表示得到一个更远邻居的消息
用于图分类的ConvGNN

带有池化与readout的ConvGNN
- 图解
  - 在图卷积之后进行池化，将图粗化为子图
  - 经过Readout层，其通过获取子图的隐表示的和/平均值来得到最终的图表示

图自编码器 (GAEs)
- 思想：一种无监督的学习框架，可以将节点/图形编码为潜向量空间，然后从编码信息中重建图形数据。
- 目的：学习网络嵌入与图形生成分布
  - 网络嵌入：通过重建图结构信息 (比如：图邻接矩阵) 来学习潜节点表示
  - 图生成：有的方法逐步生成节点与边，有的方法直接生成整个图
    
    网络嵌入的图自编码器
    - 图解
      - 编码器使用图卷积层得到每一个节点的网络嵌入。
      - 解码器计算给定网络嵌入的成对距离。
    - 说明：
      - 在经过非线性激活函数之后，解码器重建图邻接矩阵
      - 训练网络的方式：最小化 真实邻接矩阵 与 重建邻接矩阵 之间的差异

考虑时间因素的图神经网络 (STGNNs)
- 思想：从考虑时间因素的图中学习隐模式【同时考虑了时间依赖性与空间依赖性】
- 目前的方法：聚合图卷积与RNNs/CNNs进而得到空间依赖性，然后对时间依赖性进行建模
  
  用于图预测的STGNNs
- 图解
  - 图卷积层后面使用的是一维CNN
  - 图卷积层作用在 $A$ 和 $X^{(t)}$ 上用于得到空间依赖性
  - 一维CNN沿时间轴在 $X$ 上滑动用于得到时间依赖性
  - 最后的输出是线性变换层，为每一个节点生成预测(比如下一个时间戳的值)

框架

整体框架
- 输入：图结构与节点内容信息
- 输出有以下的三种机制
  - 节点级：其输出与节点回归/节点分类任务相关。RecGNNs和ConvGNNs能够通过 信息传播/图卷积 提取到高级别的节点表示。输出层使用 MLP 或者 softmax层，GNN能够以端到端方式执行节点级任务。
  - 边级：其输出与边分类和链接预测任务相关。以来自GNN的两个节点的隐表示为输入，之后利用 相似性函数或者神经网络来预测边的标签/连接强度【分别对应与边分类任务和链接预测任务】。
  - 图级：其输出与图分类任务相关。GNN通常结合 pooling 和 readout 操作来得到图级的表示。
训练框架
- 三种学习任务对应的框架
  - 用于节点级分类的半监督学习：给定一个 部分有标记节点与其他无标记节点 的单个网络，ConvGNNs可以学习到一个健壮的模型，这个模型能够确定无标签节点的标签。最后，端到端框架的构造方式是堆叠几个图卷积层和用于多分呢类的softmax层。
  - 用于图级分类的有监督学习：图级分类的目的是预测整个图的类标签。实现此任务的端到端学习的方式是组合图卷积层、图池化层、<Readout层>。其中图卷积层负责提取高级节点表示；图池化层负责充当下采样的角色，用于将图粗化为子图；Readout层将每个图的节点表示折叠为图表示【readout：将所有节点特征集合起来代表整张图】。最后通过MLP和softmax层应用于图表示，进而构建用于图分类的端到端框架。（案例见用于 图分类的ConvGNNs）
  - 用于图嵌入的无监督学习：图中没有可用的标签，使用端到端框架以无监督的方式学习图嵌入。有两种方式应用了边级信息：1）采取 自编码器框架 ，其中编码器使用图卷积层将图嵌入到潜表示中，然后解码器对此潜变量进行解码重构图结构。2）利用 负样本 ，其对一部分节点对采样为负对，而图中具有链接的现有节点对为正对，最后使用 逻辑回归层 来区分正对和负对。
- RecGNNs 与 ConvGNNs 的总结
  
  时间复杂度比较
  - 说明：带有 “-” 的说明此实验只进行了节点级/边级任务。

循环图卷积网络

RecGNNs是GNN的先驱工作，主要用于提取高级节点表示形式，当时主要用于有向无环图【计算力较小】
GNN*扩展了图的类型，比如非循环图，循环图，有向图和无向图。基于信息扩散机制，其通过周期性地交换邻居信息来更新节点的状态，直到稳定，更新方式如下
- $f(*)$ 为参数化函数
- $h_v^{(0)}$ 是随机初始化得到的
- $\sum$ 操作使得GNN*可以用于所有的节点【无视邻居数与邻居顺序的不同】
- $f$ 是 contraction mapping【投影后缩小两点之间的距离】，进而确保其收敛
门控GNN(GGNN)：采用门控循环单元（GRU）作为循环函数，将循环数减少并固定；优点是不再需要约束参数确保收敛，节点隐状态的更新依赖于先前的隐状态机器相邻的隐状态更新，公式为
- $h_v^{(0)} = x_v$
- 通过时间反向传播（BPTT）算法
- 对于大图存在问题，需要将节点的中间状态存储在内存中
随机稳态嵌入（SSE）：是一种对大型图具有可扩展性的学习算法。其以随机和异步的方式周期性更新节点的隐状态，它随机采样一批节点用于状态更新，随机采样一批节点用于梯度计算。为了确保稳定性，SSE的递归函数定义为历史状态和新状态的加权平均
- $\alpha$ 是一个超参数
- $h_v^{(0)}$ 是随机初始化的
- SSE在理论上不能说明节点状态会收敛到固定点

卷积图神经网络

卷积图神经网络分成两类：基于空间的和基于频谱的
基于频谱的方法从图信号处理的角度引入 Filter，可以解释为从图信号中去除了噪音；
基于空间的方法通过信息传播的方式来定义图卷积

基于频谱的方法：

背景：
- 假设图是无向的
- 无向图的规范化拉普拉斯矩阵的数学表示 $L = I_n - D^{-(\frac 12)}AD^{-(\frac 12)}$ ，其中D是节点度数的对角矩阵，即 $D_i{i} = \sum_j (A_{i, j})$
- 由于 $L$ 具有半正定的特性，因此 $L$ 可以表示为 $L = U \Lambda U^T$ ，其中 $U = [u_0, u_1, ..., u_{n-1}] \in R^{n \times n}$ 是由特征向量组成的特征向量矩阵
- $\Lambda$ 是由特征值对应的对角矩阵，即 $\Lambda_{ii} = \lambda_i$
- 归一化之后的特征向量是正交化的，即 $U^TU = I$
- 在图信号处理中，图信号 $x \in R^n$ 表示一个图所有节点的特征向量，其中 $x_i$ 指的是第 $i$ 个节点的值
- 信号 $x$ 的傅里叶变换为 $F(x) = U^Tx$ ，逆傅里叶变换为 $F^{-1}(\widehat{x}) = U \widehat{x}$ ，其中 $\widehat{x}$ 表示经过图傅里叶变换的结果信号
- 最终含义就是图傅里叶变换将输入的图信号投影到正交空间，正交空间上的基是由归一化图拉普拉斯算子的特征向量组成，变换后的信号 $\widehat{x}$ 是在新空间中对应的坐标，所以输入的信号 $x$ 可以表示为 $x = \sum_i \widehat{x}_iu_i$ ，这个计算过程正好是逆傅里叶变换。
- 带有 Filter 的输入信号的图卷积表示为
  - $⊙$ 表示逐元素相乘
  - 如果 filter 表示为 $g_\theta = diag(U^Tg)$ ，那么谱图卷积可以表示为 $x*_Gg_\theta = Ug_\theta U^Tx$
- 最终说明：所有的谱图卷积都遵循上述的定义，唯一的不同就是 filter 的选取
谱卷积神经网络
- 假设 filter $g_\theta = \Theta_{i, j}^{(k)}$ 是一系列可学习的参数
- 使用多通道考虑图信号
- 谱卷积神经网络的图卷积层定义为
  - $k$ 表示层的下标
  - $H^{(k-1)} \in R^{n \times f_{k-1}}$ 是输入的图信号，并且 $H^{(0)} = X$
  - $f_{k-1}$ 是输入的通道数， $f_{k}$ 是输出的通道数
  - $\Theta_{i, j}^{(k)}$ 是由可学习参数组成的对角矩阵
谱卷积神经网络的限制：
- 对图的变化会对特征值造成变化
- 学习到的 Filter 是域相关的，即一个 Filter 不能应用于具有不同结构的图
- 特征分解的复杂度大： $O(n^3)$
解决上述限制的方法：将复杂度降低为 $O(m)$
- ChebNet：通过特征值对角矩阵的切比雪夫多项式近似 Filter $g$
  - $g_\theta = \sum_{i=0}^K \theta_iT_i(\widetilde{\Lambda})$
  - $\widetilde{\Lambda} = 2 \frac{\Lambda}{\lambda_{max}} - I_n$
  - $\widetilde{\Lambda} \in [-1, 1]$
  - 切比雪夫多项式的递归定义 $T_i(x) = 2xT_{i-1}(x) - T_{i-2}(x)$
  - $T_0(x) = 1$ ，并且 $T_1(x) = x$
  - 带有 filter $g_\theta$ 的图信号的卷积为 $x*_G g_\theta = U(\sum_{i-0}^K\theta_i T_i (\widetilde{\Lambda}))U^Tx$
  - $\widetilde{L} = \frac{2L}{\lambda_{max}} - I_n$ ， $T_i(\widetilde{L}) = UT_i(\widetilde{\Lambda})U^T$
  - 切比雪夫的最终形式： $x *_G g_\theta = \sum_{i=0}^{K} \theta_i T_i(\widetilde{L})x$
- CayleyNet：使用凯利多样式
  - Cayley 的频谱图卷积
    - $Re(*)$ 返回复数的实数部分， $c_0$ 是实数， $c_j$ 是复数， $i$ 是虚数
      ， $h$ 是控制 filter 的一个参数
    - ChebNet是CayleyNet的特例
- GCN：引入了ChebNet的一阶逼近
  - 假设 $K = 1$ ，并且 $\lambda_{max} = 2$
  - 公式 $x *_G g_\theta = \sum_{i=0}^{K} \theta_i T_i(\widetilde{L})x$ 可以变成 $x *_G g_\theta = \theta_0 x - \theta_1D^{-\frac 12}AD^{-\frac 12}x$
  - 防止过拟合，假设 $\theta = \theta_0 = -\theta_1$
  - 最后得到的表达式为 $x *_G g_\theta = \theta(I_n + D^{-\frac 12}AD^{-\frac 12})x$
  - 为了允许输入和输出的可以是多通道，组合层定义为 $H = x *_G g_\Theta = f(\overline{A}X\Theta)$
    - $\overline{A} = I_n + D^{-\frac 12}AD^{-\frac 12}$
    - $f(*)$ 是激活函数
    - 使用 $I_n + D^{-\frac 12}AD^{-\frac 12}$ 从经验上来说会造成数值不稳定
    - 使用 $\overline{A} = D^{-\frac 12}AD^{-\frac 12}$ 代替 $\overline{A} = I_n + \widetilde{D}^{-\frac 12} \widetilde{A}\widetilde{D}^{-\frac 12}$ ,其中 $\widetilde{A} = A + I_n$ , $\widetilde{D}_{ii} = \sum_j\widetilde{A}_{ij}$
  - GCN可以解释为基于空间的方法，即将GCN认为是聚合节点邻居的特征信息，那么公式 $H = x *_G g_\Theta = f(\overline{A}X\Theta)$ 可以表示为 $H_v = f(\Theta^T(\sum_{u \in{\{N(v) \bigcup v}\}}\overline{A}_{v,u}x_u)) \ \ \ \forall v \in V$
  - 自适应卷积图神经网络(AGCN)：学习未被图邻接矩阵指定的隐结构关系
    - 通过一个可学习的距离函数构造一个残差图邻接矩阵
    - 该距离函数将两个节点的特征作为输入
  - 双卷积图神经网络（DGCN）：引入双图卷积体系结构
    - 两层共享参数
    - 共同使用归一化的邻接矩阵和逐点正互信息(PPMI)矩阵，该矩阵通过从图中进行随机游走获取节点共现信息，其表示为
      - $v_1, v_2 \in V$
      - $|D| = \sum_{v_1, v_2}count(v_1, v_2)$
      - $count(•)$ 函数返回在样本随机游走中节点 $v$ 和/或节点 $u$ 共同发生/发生的概率
      - 通过集成双图卷积层的输出，DGCN没有必要对多个图卷积层进行堆叠就可以对局部和全局结构信息进行编码

基于空间的ConvGNNs

基于空间的ConvGNNs与RecGNNs共享相同的信息传播/消息传递思想。

NN4G (neurla network for graph)
- 思想：通过在每一层具有独立参数的综合神经架构学习图的互依赖
- 方式：直接汇总节点的邻域信息来执行卷积，同时还会应用残差连接和跳过连接用来存储每层的信息
- 节点状态更新过程：
  - $f(•)$ 是一个激活函数
  - $h_v^{(0)} = 0$
- 上述过程可以使用矩阵进行表示： $H^{(k)} = f(XW^{(K)} + \sum_{i=1}^{(k-1)}\Theta^{(k)})$
- 与GCN传统形式的不同点：NN4G是使用非归一化的邻接矩阵
- 存在的问题：没有归一化会导致隐节点状态存在不同的范围
CGMM (Contextual Graph Markov model)
- 特点：在保持空间局部性的同时，还具有概率可解释性的优势
DCNN (Diffusion CNN)
- 思想：将图卷积视为一种扩散过程
- 前提：假设信息是以一定的转移概率从一个节点传递到邻域的节点之一【使得信息可以在几轮传递之后能够达到平衡】
- 图卷积定义
  - $f(•)$ 是一个激活函数
  - $P \in R^{n \times n}$ 是概率迁移矩阵，表示方式为 $P = D^{-1}A$
  - 隐表示矩阵 $H^{(k)}$ 保持与输入特征矩阵 $X$ 相同的维度，与 $H^{(k-1)}$ 无关
  - 输出结果：串联 $H^{(1)}, H^{(2)},... H^{(K)}$
DGC
- 思想：与DCNN基本类似，最终的处理方式不同
- 图卷积定义
  - $W^{(k)} \in R^{D \times F}$
  - $f(•)$ 是一个激活函数
  - 使用迁移概率矩阵的平方表示远处的邻居对中心节点的贡献很小
  - 输出结果：累加 $H^{(1)}, H^{(2)},... H^{(K)}$
PGG-DGGNN
- 思想：使用最短路径增加远处的节点的贡献度
- 最短距离邻接矩阵 $\left\{\begin{aligned}S_{v, u}^{(j)} &=1，如果节点u到节点v的最短距离为j \\S_{v, u}^{(j)}&=0，其他情况 \end{aligned}\right.$
- 图卷积操作
  - $\widetilde{D}_{ii}^{(j)} = \sum_l S_{i, l}^{(j)}$
  - $H^{(0)} = X$
  - $||$ 操作表示向量的串联
  - $\gamma$ 是控制感受野大小的超参数
- 缺点：计算最短路径邻接矩阵的时间复杂度 $O(n^{3})$
PGC (Partition graph convolution)
- 思想：根据不限于最短距离的一定标准将节点的邻居分为 $Q$ 组
- 方式：根据每个组定义的邻域构造 $Q$ 个邻接矩阵
- 图卷积方式：
  - $H^{(0) } = X$
  - $\overline{A}^{(j)} = (\widetilde{D}^{(j)})^{-\frac 12}\widetilde{A}^{(j)} （\widetilde{D}^{(j)})^{-\frac 12}$
  - $\widetilde{A}^{(j)} = A^{(j)} + I$
MPNN (message-passing neural network)
- 思想：将图卷积视为一种消息传递的过程，信息可以沿着边直接从一个节点传递到另一个节点
- 方式：使用K步消息传递迭代确保信息能够传递更远
- 图卷积方式：
  - $h_v^{(0)} = x_v$
  - $U_k(·)$ 和 $M_k(·)$ 是可学习的参数的函数
  - 得到的结果可以用于执行节点级预测任务，或者将结果传递到 Readout 函数用于执行图级的预测任务
  - Readout 函数基于节点隐表示生成整张图
  - Readout 函数生成图的表示
    - $R(·)$ 表示可学习参数的Readout函数
    - 选择不同的 $U_k(·)$ 、 $M_k(·)$ 和 $R(·)$ 可以覆盖很多的 GNNs
GIN ( Graph isomorphism network)
- 思想：通过可学习的参数调节中心节点的权值
- 图卷积方式：
  - $MLP(·)$ 表示多层感知
GraphSage
- 思想：为每个节点固定数量的邻居
- 图卷积方式：
  - $h_v^{(0)} = x_v$
  - $f_k(·)$ 是聚合函数
  - $S_{N{(v)}}$ 是对于节点 $v$ 的邻居的随机取样
  - 聚合函数不随节点顺序的变化而变化
GAT (Grapg Attention Network)
- 思想：采用注意力机制来得到相连节点之间的相对权值
- 图卷积方式：
  - $h_v^{(0)} = x_v$
  - $\alpha_{vu}^{(k)}$ 是注意力权值，用来测量节点 $v$ 与其邻居节点 $u$ 之间的连接强度
  - - $g(·)$ 表示 LeakyReLu 激活函数
    - $\alpha$ 是一个可学习参数的向量
    - softmax 函数确保该节点与其邻居节点的权值和为1
    - GAT 执行多头注意力增强了模型的表达能力
- 缺点：GAT假设注意头的贡献是相同的
- 与GCN的不同
  
  GAT与GCN的不同
  - GCN 为节点与其相邻的节点之间赋予相同的权值
  - GAT 为节点与其相邻的节点之间赋予不同的权值，贡献度大的权值高

GAAN (Gated attention network)
- 思想：引入自注意力机制
- 特点：该机制为每个注意力头分配不同的注意分数
GeniePath
- 思想：提出了在空间施加注意力之外，还进一步提出了一种类似于LSTM的门控机制
- 特点：这种门控机制可以控制跨图卷积的信息流
MoNet (Mixture model network)
- 思想：使用节点伪坐标确定节点与其邻居之间的相对位置
- 方式：确定位置之后，权值函数会将相对位置映射到这两个节点之间的相对权值
- 特点：Filter 的参数可以在不同的位置之间进行共享
- 流行的方法：
  - geodesic CNN (GCNN)
  - anisotropic CNN (ACNN)
  - spline CNN
- 提出了一个具有可学习参数的高斯核，能够自适应学习权值函数
PATCHY-SAN
- 思想：根据节点邻居的图标签对节点进行排序，选择前q个邻居
- 图标签本质是节点分数，节点分数的获取：
  - node degree
  - centrality
  - Weisfeiler–Lehman (WL) color
- 特点：由于每个节点都有固定数量的有序邻居，因此可以将图结构化数据转换为网格结构化数据
- 应用标准的一维卷积 Filter 来汇总邻域特征信息
- Filter 的权值与节点邻居的顺序相对应
- 缺点：需要对节点进行排序，因此需要大量的计算才能进行数据处理
LGCN (Large-scale GCN)
- 思想：根据节点特征信息对节点的邻居进行排名
- 方式：对于每个节点，LGCN都会集成一个由其邻域组成的特征矩阵，然后沿着每一列对该特征矩阵进行排序，然后将前q行作为输入

训练效率方面的提升：
- 一般的GNN需要将整个图数据和所有节点的中间状态存储在内存中，可能造成内存溢出
- GraphSage 提出批量训练算法节省了内存，其以固定样本大小的K步递归扩展根节点的邻域来对每个节点构造树，对于每棵采样树，GraphSage通过从下到上分层汇总隐藏节点表示形式来计算根节点的隐藏表示形式。【对每个节点采样固定数量的邻居】
- FastGCN (Fast Learning with GCN)为每个卷积层采样固定数量的节点，其将图卷积解释为概率度量下节点嵌入函数的积分变换，使用Monte Carlo近似和方差减小技术来简化训练过程，但是层间连接可能稀疏
- 自适应的分层采样方法，其较低层的节点采样以上一层为条件，相比于FastGCN，其实现了更高的精度，但是采样方案更加复杂
- StoGCN (stochastic GCNs)使用历史节点表示作为控制变量将图卷积的感受野大小减小到任意小的比例，即使每个节点有两个邻居，其也能够达到可比较的性能。但是，其必须保存所有节点的中间状态，对于大型图不好解决。
- Cluster-GCN 使用图聚类算法对子图进行采样，并对采样的子图中的节点执行图卷积，由于邻域搜索受子图的限制，因此其能够以更小的代价（更少时间，更小内存，更深网络）处理更大的图，其提供了时间复杂度和内存复杂度的直接比较。
  
  不同方法的时间与内存复杂度
  - GCN 是进行批量训练的 baseline
  - GraphSage 是牺牲时间效率来节省内存
  - Sto-GCN 的时间复杂度最高，处于瓶颈
  - Cluster-GCN 实现了最低的内存复杂度

频谱模型与空间模型之间的比较
- 频谱模型：
  - 在图信号处理中具有理论依据
  - 可以通过设计不同的 Filter 得到不同的 GCNs
- 空间模型：
  - 在每个节点上本地执行图卷积
  - 可以在不同的位置和结构之间轻松共享权值
- 比较
  - 频谱模型在效率、通用性、灵活性上不如空间模型
  - 频谱模型仅限用于无向图，空间模型可以用于多源图

图池化模块

通过GNN生成节点特征之后，直接应用于最终任务会导致计算量大的问题，此时需要进行下采样

两个下采样的操作
- 池化操作i
  - 目的：降低参数的大小
  - 方式：通过对节点进行下采样以生成较小的表示
  - 意义：防止过拟合、避免置换不变性与计算复杂性的问题
- Readout 操作
  - 用途：主要用于基于节点表示生成图级表示
池化方法
- 最原始以及最有效的池化方法：均值、最大值、求和
- 表示 $h_G = mean/max/sum(h_1^{(K)}, h_2^{(K)} ,...h_n^{(K)})$ ，其中 $K$ 是最后一个卷基层的下标
- 优点：可以降低图域的维度以及降低计算费用
- 存在的问题：使用以上池化方式，甚至使用了注意力机制的方式对于任意大小的图形都会生成固定大小的嵌入
  - Set2Set：使用LSTM在应用减少操作的之前将与顺序相关的信息整合到内存嵌入中，否则将此信息进行破坏。
  - ChebNet：使用Graclus算法将输入图粗化多个级别，然后将输入图的节点与粗化版本重新排列成平衡二叉树。自底而上任意聚合平衡二叉树将相似的节点排列在一起。
  - DGCNN：其使用的池化策略类似于 SortPooling，将节点重新排列为有意义的序列，然后再执行池化操作。DGCNN根据节点在图中结构角色进行排序【对节点特征进行排序】，另外还通过截断/扩展节点特征矩阵将图形大小统一为q $\left\{\begin{aligned}删除最后的n-q行，如果n \geq q \\添加 q-n 行零行，其他情况 \end{aligned}\right.$
  - DiffPool (differentiable pooling)：不仅将图上的节点聚类，同时学习了在k层的聚类分配矩阵 $S$ , $S^{(k)} \in R^{n_k \times n_{k+1}}$ ，其中 $n_k$ 表示第k层的节点数， $S^{(k)}$ 中的概率值基于节点特征与拓扑结构生成的， $S^{(k)} = softmax(ConvGNN_k(A^{(k)}， H^{(k)}))$ 。如此设计的核心思想是同时考虑图拓扑和特征信息，进而学习到一个全面的节点分配，但是DiffPool会在池化之后生成密集图，导致时间复杂度为 $O(n^2)$
  - SAGPool：在考虑了拓扑与节点特征的同时，还通过自注意力方法学习池化。
- 池化总体来说就是减小图形大小，需要研究的是如何提高池化的有效性与计算复杂性

理论方面的讨论【可以努力的方面】

感受野的形状
- 定义：节点的感受野是节点的集合
- 目的：有助于确定最后的节点表示
- 变化过程：每当合成一个多个图卷积层时，节点的感受野每次都会向其远处的邻居向前增长一步
- 一个ConvGNN能够通过堆叠局部图卷积层来提取出全局信息
VC 维度
- 定义：VC 维度是模型复杂度的度量
图同构
- 定义：如果两个图的拓扑是相同的，那么它们是同构的
等变性和不变性
- 执行节点级任务，GNN一定是等变函数
- 执行图级任务，GNN一定是不变函数
通用逼近
- 具有一个隐层的MLP可以近似任意函数，
- 级联相关可以逼近结构化输出的函数
- RecGNNs可以近似保留任何展开精度的任何函数

图自编码器

说明：GAEs是深度数据架构，能够将节点映射到潜特征空间，然后解码器能够根据潜表示解码出图信息

选择的GAEs的主要特性

网络嵌入：

定义：网络嵌入是节点的低维度向量表示，可以保留节点的拓扑信息
过程：
- 使用编码器提取网络嵌入
- 使用解码器执行网络嵌入【保存图拓扑结构（比如PPMI矩阵和邻接矩阵）】
- 最后学习网络嵌入
SDNE (structural deep network embedding)
- 方式：使用堆叠式自动编码器共同保存节点的一阶近似度和二阶近似度
- 缺点：仅仅考虑了结构信息，但是没有考虑节点本身信息
- 两个损失函数
  - 第一个损失函数
    - $x_v = A_v$
    - $enc(·)$ 是由一个MLP组成的编码器
- 第二个损失函数
  - $\left\{\begin{aligned}b_{v, u} &= 1，如果A_{v, u} =0 \\b_{v, u} &= \beta > 1，如果A_{v, u} =0 \end{aligned}\right.$
  - $dec(·)$ 是由一个MLP组成的解码器
GAE*
- 特点：使用GCN同时编码节点结构信息和节点特征信息
- 编码器公式表示： $Z = enc(X, A) = Gconv(f(Gconv(A, X;\Theta_1));\Theta_2)$
  - $Z$ 代表图的网络嵌入矩阵
  - $f(·)$ 是一个ReLu激活函数
  - $Gconv(·)$ 是由公式 $H = x *_G g_\Theta = f(\overline{A}X\Theta)$ 定义的图卷积层
- 解码器通过重建图邻接矩阵，从节点的嵌入中解码出节点关系信息
- 解码器公式表示： $\widehat{A}_{v, u} = dec(z_v, z_u) = \sigma(z_v^Tz_u)$
  - $z_v$ 是节点 $v$ 的嵌入表示
- 训练GAE*的方式是根据真实邻接矩阵 $A$ 和重构邻接矩阵 $\widehat{A}$ ，最小化负交叉熵
VGAE (Variational GAE)
- 由于GAE的简单重建图邻接矩阵可能会导致过拟合，因此使用VGAE用于学习数据分布
- 变分下边界的优化方式：
  - $KL(·)$ 指的是两个分布之间距离度量的KL散度
  - $p(Z)$ 是高斯先验，表示为 $p(Z) = \prod_{i=1}^np(z_i) = \prod_{i=1}^nN(z_i|0, I)$
  - $p(A_{i, j} = 1|z_i, z_j) = dec(z_i, z_j) = \sigma(z_i^Tz_j)$
  - $q(Z|X, A) = \prod_{i=1}^nq(z_i|X, A)$ ，其中 $q(z_i|X, A) = N(z_i|\mu, diag(\sigma_i^2))$
  - $\mu_i$ 是由公式 $Z = enc(X, A) = Gconv(f(Gconv(A, X;\Theta_1));\Theta_2)$ 定义的编码器输出的第 $i$ 行
  - $\log \sigma_i$ 与另一个编码器的 $\mu_i$ 相似
  - 由公式 $L = E_{q(Z|X, A)}[\log p(A|Z)] - KL[q(Z|X, A)||p(Z)]$ 可以知道，VGAE假设经验分布 $q(Z|X, A)$ 与先验分布 $p(Z)$
ARVGA (adversarially regularized VGAE)
- 思想：学习得到一个编码器，这个编码器能够得到经验分布 $q(Z|X,A)$ ，这个分布与先验分布 $p(Z)$ 无法分开，即这两个分布之间存在一定的关系

GraphSage
- 思想：使用两个卷积层编码节点特征
- 特点：没有优化重建误差，只是显示了两个节点之间的关系信息【负采样】
- 损失计算：
  - 节点 $u$ 是节点 $v$ 的邻居
  - 节点 $v_n$ 是一个到节点 $v$ 的远处节点，该节点是从负采样分布 $P_{n}(v)$ 中采样的
  - $Q$ 为负样本的数量
  - 损失函数的本质：与该节点相近的节点有近似的表示，远处的节点与该节点有不同的表示
DGI
- 通过最大化本地互信息来驱动本地网络嵌入以得到全局结构信息
以上的方法是通过解决链路预测问题来学习网络嵌入的
DRDE (Deep recursive network embedding)
- 假定节点的网络嵌入近似与其邻域网络嵌入的聚合
- 采取LSTM聚合一个节点的邻居
- 重建损失：
  - $z_v$ 表示通过字典查找得到的节点 $v$ 的网络嵌入
  - LSTM将节点 $v$ 的邻居的随机序列作为输入【按照节点度数排序】
  - DRDE 通过 LSTM 隐式学习 网络嵌入，而不是使用 LSTM 网络生成网络嵌入
  - 如此做可以避免 LSTM 对于节点序列的排列不是不变的问题
NetRAs (Network representations with adversarially regularized autoencoders)
- 提出了一种具有一般损失函数的图自编码框架
- 损失函数表示
  - $dist(·)$ 表示节点嵌入 $z$ 与重建的 $z$ 之间的距离度量
  - NetRAs 的编码器和解码器是 LSTM 网络， LSTM的输入是节点的随机游走得到的序列

图生成

有多个图，GAEs能够学习到图的生成分布，方式是将图编码成隐表示，然后解码器根据给定的隐表示解码出图结构
目前用于图生成的 GAEs 大多数都用于分子生成图问题
两种方法：
- 顺序方式：逐步得到图的节点与边
  - DeepGMG (Deep generative model of graphs)
    - 假设图的概率是所有可能节点置换的排列组合
    - 公式表达：
      - $\pi$ 表示节点顺序，用于得到图中所有节点和边的复杂联合概率
    - 通过决策来确定是否需要添加节点，要添加哪个节点，是否添加边以及连接到新节点的节点
    - 生成节点和边的决策过程取决于RecGNN更新的增长图的节点状态和图状态
  - GraphRNN
    - 使用图级RNN与边级RNN用来给节点和边的生成建模
    - 图级RNN每次添加一个节点到节点序列
    - 边级RNN产生二进制序列，说明新节点与该序列中先前生成节点之间的连接
- 全局方式：一次性输出整张图
  - GraphVAE (Graph variational autoencoder)
    - 将存在的节点和边建模为独立随机变量
    - 假设有编码器定义的后验分布 $q_\phi(z|G)$ 和由解码器定义的生成分布 $p_\theta(G|z)$
    - 变分下界的定义：
      - $p(z)$ 服从高斯先验
      - $\phi$ 和 $\theta$ 是可学习的参数
  - 使用ConvGNN作为编码器
  - 使用简单的MLP作为解码器
  - 输出结果：带有邻接矩阵、节点属性和边属性的图
RGVAE (Regularized GraphVAE)
- 增强GraphVAE的约束，对GraphVAE的解码器正则化
MolGAN (Molecular GAN)
- 整合convGNNs, GANs, 强化学习目标生成具有所需特性的图
- MolGAN由生成器和判别器组成，相互竞争以提高生成器的真实性
- 生成器尝试生成一个伪图及其特征矩阵
- 判别器将伪样本与真实样本进行区分
- 对判别器引入奖励机制，根据外部评估者鼓励所生成的图具有一定的属性
NetGAN
- 结合LSTM 与 WGAN 结合在一起
- 基于随机游走的方法生成图形
- 训练生成器通过 LSTM 网络生成合理的随机游走
- 强制执行判别器从真实的随机游走中识别出生成器生成的随机游走
- 通过标准化生成器生成的随机游走计算出节点的共现矩阵，从而得到新的图

总结

顺序方法将图线性化为序列，但是由于循环，可能丢失结构信息
全局方法可以一次性生成一张图，但是无法应用于大图【GAE的输出空间最多为 $O(n^2)$ 】

带有时间因素的图神经网络

实际情况下，图在图结构和图输入方面都是动态的，因此出现了 STGNN

大体思想：给动态节点输入建模，同时假设已连接节点之间的互依赖性【根据节点状态建模】
案例：交通网络中存在许多速度传感器，不同距离的传感器之间的权值不同
STGNN 可以同时获取到图的空间和时间依赖性
STGNNs的任务是预测未来的节点值/标签或者预测带有时间因素的图标签
STGNN遵循的两个方向：基于RNN的方法和基于CNN的方法

基于RNN的方法

大多数基于RNN的方法是通过使用图卷积过滤传递给递归单元的输入和隐状态来获取时空依赖性

上述语句的说明：假设有一个简单的RNN任务 $H^{(t)} = \sigma(WX^{(T) } + UH^{(T-1)} + b)$
- $W^{(t)} \in R^{b \times d}$ 表示在时间步为 $t$ 时的节点特征矩阵
对上述表达插入图卷积 $H^{(t)} = \sigma(Gconv(X^{(t)}, A; W) + Gconv(H^{(t-1), A; U}) + b)$
- $Gconv(·)$ 是图卷积层
GCRN (Graph convolutional recurrent network)
- 集合了LSTM和ChebNet
DCRNN (Diffusion convolutional RNN)
- 将提出的扩散图卷积层合并到GRU网络中
- 采用编码器-解码器框架来预测节点值的未来的K步

使用节点级和边级RNNs解决时间信息的不同方面

Structureal-RNN
- 提出一种递归框架来预测每个时间步的节点标签
- 存在两个RNN：节点RNN和边RNN
- 每个节点和每条边的时间信息分别通过节点RNN和边RNN
- 为了合并空间信息，节点RNN将边RNN的输出作为输入
- 将节点和边分成语义组，并且同一语义组中的节点或者边共享相同的RNN模型，因此节省了成本
基于RNN的方法存在耗时的迭代传播与梯度爆炸/消失问题

基于CNN的方法

以非递归的方式处理时空图
相比于基于RNN的方法的优点：
- 并行计算
- 稳定的梯度
- 低内存需求
基于CNN的方法将一维CNN层与图卷积层进行交错，从而学习到时间和空间依赖性
案例讲解：
- 假设STGNN的输入是一个张量 $X \in R^{T \times n \times d}$
- 一维卷积层沿着时间轴在 $X_{[:, i, :]}$ 上滑动，从而对每个节点的时间信息进行汇总
- 图卷积层在 $X_{[i, :, :]}$ 用于聚合空间信息
CGCN
- 将一维卷积层与ChebNet/GCN层整合在一起
- 时空块的构成：按顺序堆叠的一个门控的一维卷积层，一个图卷积层和另一个门控的一维卷积层
ST-GCN
- 使用一维卷基层和PGC层组成时空块

先前的方法都是使用预定义的图结构，假设预定义的图结构反映了节点之间的真实依赖关系，实际上时空设置下的图有许多的快照【图形模糊】

Graph WaveNet
- 提出使用自适应邻接矩阵来执行图卷积，进而从数据中自动学习到潜在的静态图形结构
- 自适应邻接矩阵
  - SoftMax是沿行维度进行计算的
  - $E_!$ 表示源节点嵌入
  - $E_2$ 表示带有可学习参数的目标节点嵌入
  - $E_1$ 与 $E_2$ 的相乘，可以得到源节点和目标节点之间的依赖权值
  - 借助FNN的复杂时空神经网络，Graph WaveNet不需要提供邻接矩阵就可以表现良好

学习潜静态空间相关性可以发现网络中不同实体之间的可解释且稳定的相关性，但是有的时候，学习潜动态空间的相关性可以进一步提高模型的精度

案例：
- 在交通网络中，车辆在两条道路上行驶的时间可能取决于道路的当前状况
GaAN
- 利用注意力机制通过基于RNN的方法学习动态空间依赖性
- 注意函数用于根据给定的两个连接节点的当前节点输入来更新它们之间的边权值
ASTGCN
- 进一步包括空间注意函数和时间注意函数
- 通过基于CNN的方法学习潜动态空间相关性和时间相关性

学习潜空间相关性存在的缺点是需要计算没对节点之间的空间相关性权值，时间复杂度为 $O(n^2)$

应用

图结构化数据无处不在

基准图数据集

引文网络
生化图
社交网络
其他

基准数据集

评估方法

节点分类和图分类是评估RecGNN和C哦女GNN性能的常见任务

节点分类：
- 大多数方法遵循基准数据集的训练/验证/测试的标准划分
  - Cora
  - Citeseer
  - Pubmed
  - PPI
  - Reddit
- 评估性能存在的陷进：
  - 在所有实验中使用相同的训练/验证/测试划分会低估泛化误差
  - 不同的方法采用了不同的训练技术【超参数调参，参数初始化，学习率衰减和提前停止】
图分类
- 一般采用10倍交叉验证对模型进行评估
- 存在的问题：在每一折的外部测试集都用于模型选择和风险评估

开源实现

看文献

实际应用

计算机视觉
- 场景图生成
- 点云分类
- 动作识别
自然语言处理
- 文本分类

交通
- 预测交通速度
- 预测交通量
- 预测道路密度

推荐系统
- 将商品与用户作为节点
化学
- 研究分子/化合物的图结构
其他
- 程序验证
- 程序推理
- 社会影响预测
- 对抗攻击的预防
- 电气健康记录建模
- 脑网络
- 事件检测
- 组合优化

未来的方向

模型深度
可扩展性权衡
异质性
动态性

结论

在本文中，我们对GNN进行了全面概述。我们提供的分类法将GNN分为四类：RecGNN，ConvGNN，GAE和STGNN。
我们对类别内或类别间的方法进行了全面的回顾，比较和总结。然后，我们介绍了GNN的广泛应用。总结了GNN的数据集，开源代码和模型评估。
最后，我们提出了GNN的四个未来发展方向。

《A Comprehensive Survey on Graph Neural Networks》阅读