图神经网络综述论文笔记_图神经网络论文笔记

author：Jie Zhou∗, Ganqu Cui∗, Zhengyan Zhang∗, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, Maosong Sun
论文地址：paper

前言

近日在弄图神经网络，写下这篇论文笔记。笔记不会介绍很多背景知识，着重强调了自己有用的学习部分。

模型

图神经网络适用于非欧几里得结构的数据。第二节主要介绍图神经网路的基础模型和几个变体，第三节介绍的几个基本框架和应用。下图是本文的主要符号。

GNN

图神经网络是为处理图领域的数据，他的每个节点表示为他的特征以及相关节点。GNN的目标是学习一个包含每个节点邻域信息的状态嵌入$h_v\in R^s$,这是节点v的的s维度向量。$g(\cdot )$ 是输出函数$f(\cdot )$是转移函数。下列式子表示了输出是怎么产生的。
$$\begin{array}{c}{\mathbf{h}}_v=f\left({\mathbf{x}}_v,{\mathbf{x}}_{co[v]},{\mathbf{h}}_{ne[v]},{\mathbf{x}}_{ne[v]}\right)\\ {\mathbf{o}}_v=g\left({\mathbf{h}}_v,{\mathbf{x}}_v\right)\end{array}$$
其中$x_v$,$x_{co[v]}$,$h_{ne[v}$,$x_{ne[v]}$分别表示v的特征，边的特征，状态和节点v的邻居节点的特征。向量化后，我们就有了紧凑进行的变化。

状态的迭代计算方式为

这样$f$和$g$函数都能描述为前馈神经网络，损失函数定义如下。

其中$t_i$是用于监督的特定节点，$p$是监督节点的数量，该学习算法常用梯度下降法更新。

更新策略的方程1是本文的第一个方程，方程3是第三个方程。
局限性，首先，迭代地更新节点的隐藏状态对于固定点是低效的。其次，每次迭代使用了相同的参数，大多数神经网络在不同层中使用不同网络，作为一种分层特征提取方法。再者，边的也有丰富信息，没有被有效利用建模。最后，如果我们把重点放在节点的表示上，而不是图，则不适合使用固定点，因为在固定点中表示的分布在价值上会很平滑，对于区分每个节点来说信息更少。

GNN的变体

接下来分为两个小节，第一节主要是展示几个变体，拓展了原始模型的表示能力，第二节列举了几个修改 (convolution, gate mechanism, attention mechanism and skip connection)在信息传播以及可以学习更高质量的表示。

图类型

原始GNN模型是带标签信息的节点和无向图。下面是四个变体

1. 定向图
   定向图可以带来更多的信息，有学者使用两种权重矩阵来包含更精确的结构信息。传播规则如下，式中两个D分别为父母和子女的归一化零阶矩阵。
   

2. 异构图
   有几种不同的节点，处理异构图的最简单方法是将每个节点的类型转换为一个与原始特征连接的ont-hot特征向量。有学者将元路径引入到异构图上的传播上，在元路径上，我们可以通过节点类型和距离将邻居节点分组。对每个组，视作子图，进行传播，并将来自不同齐次图的传播结果连接起来，以进行集体节点表示。还有提出异构图注意网络（heterogeneous graph attention network (HAN)），利用节点的层次和语义层次的注意力。并且该模型具有同时考虑节点重要性和元路径的能力

3. 带边信息的图
   每个边缘都有额外的信息，如权重或边缘的类型。罗列两种方法来处理这种图。

4. 转化为二部图，将原始边变为节点，一个原始边缘被分割成两个新的边缘，这意味着边缘节点和开始/结束节点之间有两个新的边缘。采用下列聚合函数
   
   $W_r$和$b_r$是不同类型的边的传播参数。

5. 对不同的边采用不同的权重矩阵，当边的数量非常大的时候，r-GCN介绍了两种正则化手段，basis- and block-diagonal-decomposition。
   basis-decomposition:其中$W_r$是basis的变化$V_b\in R^{d_{in}\times d_{out}}$和系数$a_{r}b$的线性组合。
   
   block-diagonal-decomposion,每个$W_r$通过一组低维矩阵的直接和，它需要比第一个更多的参数。

6. 动态图
   有着静态图结构和动态输入信号，DCRNN和STGCN首次收集空间信息，然后将输出输入序列模型；Structural-RNN和ST-GCN同时收集时间和空间信息，这样就能采用传统的GNN。

传播方式

上图列出了主要的传播步骤，传播和输出是模型获取节点（边）隐藏层状态一个很重要的步骤，研究人员通常在输出步骤遵循简单的前馈神经网路设置。几种变体的利用不同的聚合方法和更新方法，比较如下表。

接着介绍四种传播方法的分类：

1. 卷积
spectral方法工作在图的光谱表示上。
7. spectral network
本方法是定义在傅里叶域上的卷积运算，通过计算图的拉普拉斯的特征值分解。本方法可以定义为信号$x\in R^N$(每个节点的标量）和一个过滤参数$g_{\theta }=diag(\theta ),\theta \in R^N$.

上式中U是归一化图拉普拉斯$\mathbf{L}={\mathbf{I}}_N-{\mathbf{D}}^{-\frac{1}{2}}\mathbf{A}{\mathbf{D}}^{-\frac{1}{2}}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^T$的特征向量矩阵，$D$是图的度矩阵，$A$是邻接矩阵，还有特征值Λ的对角矩阵。
本方法导致潜在的密集计算和非空间本地化过滤器
8. ChebNet
本方法认为$g_{\theta }(\Lambda )$可以用切比雪夫（Chebyshev）多项式$T_k(x)$的截断展开近似，直到$K^{th}$阶，所以操作如下。

式中，$\tilde{\mathbf{L}}=\frac{2}{\lambda }\mathbf{L}-{\mathbf{I}}_N$，${\lambda }_{max}$是$L$的最大特征值，$\theta \in R^k$是切比雪夫系数的向量，切比雪夫多项式定义为$T_{k}x=2x{T}_{k-1}(x)-T_{k-2}(x),T_0(x)=1,T_1(x)=x$.可以观察到，由于它是Laplacian中的K次多项式，所以操作是K局部化的。
ChebNet它使用这个K局部化卷积来定义一个卷积神经网络，它可以消除计算拉普拉斯特征向量的需要
9. GCN
有学者将分层卷积运算限制在K=1上，以缓解具有非常宽节点度分布的图在局部邻域结构上的过拟合问题

约束参数$\theta ={\theta }_0^{{}^{\prime }}=-{\theta }_1^{{}^{\prime }}$,得到下列式子

使用上式可能导致数值不稳定和梯度消失，为此提出了重整化技巧，$\mathbf{L}={\mathbf{I}}_N-{\mathbf{D}}^{-\frac{1}{2}}\mathbf{A}{\mathbf{D}}^{-\frac{1}{2}}={\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$,$\tilde{A}=A+I_N$,${\tilde{D}}_{ii}={\sum }_j={\tilde{A}}_{ij}$,最后定义了一个信号$X=R^{N\times C}$,C是输入通道数，和特征映射的F滤波器。

上述方法都使用了原始图的结构来表示节点之间的关系，但是可能也存在隐式关系，为此有提出自适应的图卷积网络来学习隐式关系，AGCN通过学习残差图拉普拉斯，并将他添加到原始的拉普拉斯矩阵中。
有学者提出了一种基于高斯过程的贝叶斯方法(G GP)来解决半监督学习问题。 它显示了模型与光谱滤波方法之间的相似之处，这可以从另一个角度给我们一些见解
但是上述方法有一个共同的缺陷，取决于训练的图结构，当结构不同时不能应用。
上述方法都是sepctral方法，非spectral方法如下
直接在图上定义卷积，在空间近邻上操作。非光谱方法的主要挑战是定义具有不同大小邻域的卷积运算，并保持CNN的局部不变性。

1. Neural FPs
   对于不同程度的节点使用不同的权重矩阵
   
   其中$W_t^{|N_v|}$是在$t$层的$|N_v|$度节点的权重矩阵，本方法的缺点是无法适用于大图。

2. DCNN
   提出扩散卷积神经网络，转移矩阵用来定义邻居节点，对于每个节点分类有
   
   其中，$X$是属兔特征$N\times F$的张量，$N$是节点数量，$F$是特征数量，$P^{\ast }$是$N\times K\times N$的张量，包括矩阵P的幂级数 $\left\{P,P^2,...,P^K\right\}$,而P是图邻接矩阵A的度归一化转移矩阵。每个实体被转换为扩散卷积表示，它是由F特征上的图扩散K跳定义的K×F矩阵。然后由K×F权重矩阵和非线性激活函数F定义。最后，H(即N×K×F)表示图中各节点的扩散表示。
   对于图的分类，DCNN只取节点表示的平均值。$1_N$是$N\times 1$的向量，DCNN也可以用于边的分类和增强邻接矩阵。
   

3. DGCN
   提出了双图卷积网络(DGCN)，共同考虑了图上的局部一致性和全局一致性。它使用两个卷积网络来捕获局部/全局一致性，并采用无监督损失来集成它们。第一层网络如下
   
   第二层网络如下:$X_P$是PPMI矩阵，$D_P$是$X_P$的对角度矩阵。
   

4. PATCHY-SAN
   为每个节点提取并规范精确的k个节点的邻域。 然后归一化邻域作为卷积运算的接收场

5. LGCN
   利用 CNN作为聚合器，最大池化节点的邻居节点矩阵来得到top-k特征向量，然后利用1-D CNN来计算隐藏层。

6. MoNet
   提出了一个关于非欧几里德域的空间域模型(MoNet)，它可以推广以前的几种技术。

7. GraphSAGE
   该框架通过从节点的本地邻域采样和聚合特征来生成嵌入
   
   本方法使用的是均匀采样邻居节点。其有三种聚合函数。分别是平均聚合，LSTM聚合，池化聚合。
   最近结构感知卷积神经网络（SACNNs)）被提出。单变量函数被用来作为过滤器执行，它们可以同时处理欧几里德和非欧几里德结构化数据
   2. Gate
   为减少前GNN的限制和改善信息图中的长期传播，很多模型利用了gate机制。

8. GGNN
   在传播阶段利用GRU单元，取消固定数量的步骤T的递归，并使用反向传播通过时间，以计算梯度。
   递归过程如下：
   
   节点v的第一次信息聚合来自他的邻居，$A_v$是邻居矩阵A的子矩阵，表示节点v和他的邻居的链接关系，GRU更新函数包含来自其他节点和以前的时间步骤的信息，以更新每个节点的隐藏状态。

9. 两种LSTM的拓展，其一Child-Sum Tree-LSTM，和N-ary Tree-LSTM,就像标准LSTM单元，每个Tree-LSTM单元，包含输入输出门$i_v$和$o_v$，一个记忆单元$c_v$和隐藏层$h_v$，不同于单个遗忘门（forget gate),Tree-LSTM单元对每个孩子k都有一个遗忘门$f_{vk}$，允许该单元选择性地包含来自每个孩子的信息。Child-Sum Tree-LSTM的转移方程如下。
   
   其中，$x_v^t$是在时间t的输入向量。
   如果树的分枝因子最多为K，并且节点的所有子节点都被排序，即他们可以从1-k索引，N-ary Tree-LSTM就可以使用，对于每个节点v,$h_{vk}^t$和$c_{vk}^t$表示在时间t的第k个孩子的隐藏层状态和记忆单元。转移方程如下。
   
   树和图的主要区别在于图的边有标签，有学者就利用权重矩阵来表示不同的标签
   
   其中$m(v,k)$表示节点v和k直接的边的标签。

10. Sentence LSTM,改善文本编码，他将文本转化到图中并利用graph LSTM来学习表示，它使用信任驱动方案自适应地选择起始节点并确定节点更新序列。
    3. Attention
    注意力机制在很多基于序列的任务中取得了很大的成功，有学者就提出图注意力网络（GAT），将注意力机制纳入传播步骤中，他计算每个节点的隐藏层状态，通过对其邻居进行处理，遵循自我关注策略。
    有学者提出定义单个图形注意层，并通过叠加该层构造任意图形注意网络。该层通过计算节点对$(i,j)$的注意机制中的系数.
    
    ${\alpha }_{ij}$是节点j到i的注意力系数，$N_i$表示节点i的邻居，该层的节点特征输入集为$h=h_1,h_2，...，h_N，h_i\in R_F$，其中N是节点数，F是每个节点的特征数。该层产生一组新的节点特性(潜在不同的基数$F^{{}^{\prime }}$)，$h^{{}^{\prime }}=\left\{h_1^{{}^{\prime }},h_2^{{}^{\prime }},...,h_N^{{}^{\prime }}\right\},h_i^{{}^{\prime }}\in R^F$作为输出。$W\in R^{F^{{}^{\prime }}\times F}$是适用于每个节点的共享线性变换的权重矩阵，$a\in R^{2F^{{}^{\prime }}}$是单层前馈神经网络的权重向量。。 用Softmax函数对其进行归一化，并应用LeakyReLU非线性(负输入斜率α=0.2。)
    最后每个节点的输出特征可以通过下式获得。
    
    此外，该层利用多头注意力，来稳定学习过程。 它应用K个独立的注意机制来计算隐藏状态，然后连接它们的特征（或计算平均值），从而产生以下两个输出表示：
    
    式中${\alpha }_{ij}^k$是由k-th注意机制计算的归一化注意系数。
    Gated Attention Network（GAAN）也采用了多头注意力，但是他是次啊用自注意力机制从不同的头来收集信息。
    4. Skip connetion
    许多应用展开或堆叠图形神经网络层，目的是获得更好的结果，因为更多的层(即k层)使每个节点聚集更多的信息从k跳的邻居。然而实验表明并不是越深的网络能取得更好的结果。这主要是因为更多的层也可以从指数增长的扩展邻域成员传播噪声信息。
    一种解决这个问题的直接方法就是残差网络。但是，即使有残差连接，具有更多层的GCN在许多数据集上的性能也不如2层GCN。
    有学者就提出一种Highway GCN利用分层门，一个层的输出用它的输入和门控权来求和。
    
    有学者提出提出了一种学习自适应结构感知表示的跳跃知识网络。 跳跃知识网络从最后一层的每个节点的所有中间表示（“跳转”到最后一层）中选择，这使得模型根据需要对每个节点的有效邻域大小进行调整。其提出三种方法，分别是连接(concatenation)，最大池化（max-pooling）和LSTM-attention
    5. Hierarchical Pooling
    复杂的大规模图通常具有丰富的层次结构，对于节点级和图级分类任务具有重要意义。

11. Edge-Conditioned Convolution (ECC)
    递归设计池化模块，下采样方法是基于拉普拉斯最大特征向量的符号将图分割成两个分量。

12. DIFFPOOL
    通过训练每个层中的赋值矩阵来学习层次聚类模块
    

训练方法

传统的训练方法有很多的缺点，比如每次更新都要计算整个图，还有L层的一个节点embedding是通过L-1层的所有邻居节点的embedding递归计算的。

1. 采样（Sampling）

• GraphSAGE使用可学习的聚合函数来替换全图的拉普拉斯，这是执行消息传递和泛化到未见节点的关键。GraphSAGE可以为未见节点生成嵌入。 此外，GraphSAGE使用邻居采样来减轻接收场的扩展。
• PinSage.提出基于重要性的采样方法，通过模拟从目标节点随机游走。这种方法选择具有最高归一化访问计数的顶部T节点。
• FatsGCN,直接通过每层的receptive field采样，也是采用重要性采样，重要因子如下。
  
  上述方法是固定采样，有学者引入一个参数化和可训练的采样器来执行基于前一层的分层采样。该自适应采样器可以同时找到最优采样重要性并减少方差。
  有学者提出随机定点梯度下降用于GNN训练，该方法将嵌入更新视为值函数，将参数更新视为值函数。在训练的同时，该算法将对节点进行采样更新嵌入，并对标记节点进行采样，交替更新参数
  2. Receptive Field Control
  提出了一种基于控制变量的GCN随机逼近算法，利用节点的历史激活作为控制变量，这种方法限制了1跳邻域中的接受场，但使用历史隐藏状态作为一个负担得起的近似。
  3. 数据增强（Data Augmentation）
  GCN需要许多额外的标记数据进行验证，并且还存在卷积滤波器的局部性，为此提出联合训练GCN和自我训练GCN以扩大训练数据集。 前一种方法找到训练数据的近邻，而后一种方法则采用类似增强的方法
  4. 无监督训练
  图自动编码器（auto-encoders）的目的是通过无监督的训练方式将节点表示成低维向量。
  首先使用GCNs来编码节点，然后使用一个简单的解码器重建邻接矩阵，并从原始邻接矩阵和重建矩阵之间的相似性计算损失。
  

通用框架

虽然有很多的变体，但是也提出了几种通用框架。
1. Message Passing Neural Networks
采用各种图神经网络和图卷积网络方法,该模型包括两个步骤，以恶个是信息传递，一个是读取阶段。
消息传递阶段（即传播步骤）运行于T时间步骤，用消息函数$M_t$和顶点更新函数$U_t$定义。

式中$e_{vw}$表示节点v到w的边的特征。
读出阶段根据读出函数R计算整个图的特征向量

式中T表示总的时间步骤。三个函数使用了不同的设置，因此，MPNN框架可以通过不同的功能设置来推广几种不同的模型。下面式子是GGNNs的设置例子

2. Non-local Neural Networks
它结合了几种“自我关注”式的方法。
其用于捕获深度神经网络的长距离依赖关系，非局部操作将位置上的响应计算为所有位置上特征的加权和。设置的位置可以在空间，时间或时空。
泛型非局部操作定义为：

其中i是输出位置的索引，j是枚举所有可能位置的索引，$f(h_i，h_j)$计算i和j之间的标量，表示它们之间的关系。$g(H_j)$表示输入$h_j$的转换,因子$\frac{1}{c(h)}$用来归一化结果。
有很多不同的$f(\cdot )$和$g(\cdot )$函数的实例。如$g(h_j)=W_g{h}_j$，接下来列举集中f函数。

• 高斯（Gaussian.）
  
• 嵌入高斯（Embedded Gaussian.）
  
• 点乘（Dot product）
  
• 连接（Concatenation）
• 

3. Graph Networks
统一MPNN和NLNN方法以及许多其他变体。

• Graph definition
  $G=(u,H,E)$,u是全局属性，H是节点集合，E是边的集合
• GN block
  包括更新函数$\varphi$，三个和函数$\rho$
  
  Computation steps
  
• 设计原则(Design Principles.)
  设计基于三个原则，分别是1） flexible representations,，2）configurable within-block structure，3）composable multi-block architectures.

应用

图神经网络的主要应用如下，就不在一一展开叙述。主要分为三大场景，1）是结构化的场景，可以很清晰的表述关系，例如物理系统，分子结构和知识图谱。2）非结构化场景，包括图片文本等。3）生成模型和组合优化问题等其他应用场景

主要问题

浅结构（Shallow Structure）

传统的深度神经网络可以堆叠上百层获得更好的性能，因为深度结构有更多的参数，可以提高表达力，然而，图神经网络一直存在浅层的问题，一般不超过三层。所以这是一个亟需解决的问题。

动态图（Dynamic Graphs）

静态图是稳定的，因此可以可行地建模，而动态图则引入了变化的结构。当边和顶点变化是，GNN无法自适应。

非结构化场景（Non-Structural Scenarios）

上文虽然提到了非结构化的应用场景，但是我们发现没有从原始数据生成图的最佳方法

可伸缩性（Scalability）

如何在社交网络或推荐系统等webscale条件下应用嵌入方法一直是几乎所有图嵌入算法的致命问题，GNN也不例外。扩展GNN是困难的，因为许多核心步骤在大数据环境中是计算消耗。