论文笔记-Deep Learning on Graphs: A Survey（上）

论文链接：https://arxiv.org/pdf/1812.04202.pdf

深度学习在许多领域都取得了成功，在图上也有许多研究工作。在这篇文章中，作者根据模型架构和训练策略将现有方法分为五类：图循环神经网络、图卷积网络、图自动编码器、图强化学习和图对抗方法，并以系统的方式全面概述这些方法。最后，作者简要概述了它们的应用，并讨论了未来潜在的研究方向。

1. 介绍

传统的深度学习架构应用于图存在一些挑战：

  • 图的不规则结构，例如卷积和池化，在图上的定义并不容易，这个问题通常被称为几何深度学习问题。
  • 图的异质性和多样性，图可以是异质的或同质的、加权的或未加权的、有符号的或无符号的。图的任务也千差万别，从节点分类和链接预测等以节点为中心的问题到图分类和图生成等以图为中心的问题。这些不同的类型、属性和任务需要不同的模型架构来解决特定的问题。
  • 大规模的图，真实的图很容易有数百万甚至数十亿的节点和边，例如社交网络和电子商务网络 。因此，如何设计可扩展的模型，最好是相对于图大小具有线性时间复杂度的模型，是一个关键问题。
  • 结合跨学科知识，图通常与其他学科相关，例如生物学、化学和社会科学。可以利用领域知识来解决特定问题，但整合领域知识会使模型设计复杂化。

根据模型架构和训练策略，可以将将现有基于图的深度学习方法分为五类：

  • 图循环神经网络 (graph recurrent neural networks，Graph RNN)，Graph RNN 通过在节点级别或图级别的状态进行建模，来获得图的递归和序列特征。
  • 图卷积网络 (graph convolutional networks，GCN)，GCN 定义了对不规则图结构的卷积和读出操作（readout operation），以获得常见的局部和全局结构特征。
  • 图自动编码器 (graph autoencoder，GAE），GAE 假设低秩图结构，并采用无监督方法进行节点表示学习。
  • 图强化学习（graph reinforcement learning，Graph RL），图 RL 定义了基于图的动作和奖励，以在遵循约束的同时获得有关图任务的反馈。
  • 图对抗方法（graph adversarial methods），图对抗方法采用对抗训练技术来增强基于图的模型的泛化能力，并通过对抗性攻击测试其鲁棒性。

2. 一些符号和定义

G: 图, G=(V,E)
V: 节点, V={v_1, v_2, \cdot, v_N}N: 节点数量, N=|V|
E：边，E \subseteq V\times V, 边集是节点间互相连接的集合的子集
M：边的数量，M=|E|
A：邻接矩阵，A \in \mathbb{R}^{N \times N} , A(i,j) 代表第 i 行第 j 列的元素，本文中的图主要是无符号图，因此A(i,j) \geq 0
F^V, F^E：节点上的特征，边上的特征

L：无向图的拉普拉斯矩阵，定义为L=D−A
D：是A的对角矩阵， D \in \mathbb{R} ^{N×N} 是 D(i,i) =∑_jA(i,j) 的对角矩阵。其特征分解记为L=QΛQ^T
Λ：Λ \in \mathbb{R}^{N×N}，是特征值升序排列的对角矩阵
Q：Q \in \mathbb{R}^{N×N}，是特征值对应的特征向量
P：转移矩阵，P=D^{−1}A，其中 P(i,j) 表示从节点v_i 开始,随机游走到v_j的概率。
N_k(i)：N_k(i) =\{ j|D(i,j)≤k \}，其中D(i,j)是到节点v_i到v_j的最短距离，即Nk(i)是v_i在k步可达到的节点集合。N(i)=N_1{i}
H^l：第 l 层中的隐藏表示
f_l：H^l的维度
\rho(\cdot)：非线性激活函数
X_1 \odot X_2：逐元素乘法
\Theta：可学习参数
s：样本大小

在图上学习深度模型的任务可以大致分为两类：

  • 以节点为中心的任务：这些任务与图中的各个节点相关联。包括节点分类、链接预测和节点推荐。
  • 以图形为中心的任务：这些任务与整个图形相关联。包括图分类、估计各种图属性和生成图。

3. 图循环神经网络

循环神经网络 (RNN)，例如GRU或LSTM是对序列数据建模。在本节中，Graph RNNs 可以捕获图的递归和序列特征。图 RNN 可以大致分为两类：

  • 节点级 RNNs ，特征位于节点级并以节点状态建模
  • 图级 RNNs，特征位于图级并以整个图状态建模
图循环神经网络的主要特征

3.1 节点级 RNNs

图的节点级 RNN，也称为图神经网络 (GNN)。 GNN 背后的想法很简单：对图结构信息进行编码，每个节点 v_i 由一个低维状态向量 s_i 表示。受递归神经网络的启发，采用了状态的递归定义：
s_i = \sum_{j \in N(i)} F(si, sj, F_i^V, F_j^V,F^E_{i,j}) \tag{1}

最终的输出为\hat{y_i} = O(s_i, F_i^V)\tag{2}

对于以图为中心的任务，建议添加一个具有唯一属性的特殊节点来表示整个图。为了学习模型参数，采用以下半监督方法：

  • 使用 Jacobi 方法，迭代求解s_i 到稳定点，
  • 使用 Almeida-Pineda 算法，执行一个梯度下降步骤，以最小化特定任务的目标函数；
  • 然后重复这个过程直到收敛

上面两个简单方程式在中GNN扮演着两个重要的角色。实际上，GNN 统一了一些早期用于处理图数据的方法，例如递归神经网络和马尔可夫链。GNNs 背后的总体思路有着深刻的启示，许多最先进的 GCNs 实际上都有类似于公式(1) ，遵循在直接连接的节点邻域内交换信息的相同框架。实际上，GNNs 和 GCNs 可以统一成一些通用的框架，一个 GNN 就相当于一个使用相同的层达到稳定状态的GCN。这一点会在GCN的篇章中讨论。

GNNs 的缺点：

  • 公式（1）中的F(\cdot) 必须是一个“收缩图”，这严格限制了建模的能力
  • 需要多次迭代梯度下降才能达到稳定状态，所以 GNNs 的计算成本很高

由于这些缺点以及可能缺乏计算能力（GPU 在当时并未广泛用于深度学习）以及缺乏研究兴趣，因此 GNN 并未成为一般研究的重点。

对 GNNs 的一个显著改进是门控图序列神经网络（gated graph sequence neural networks，GGS NNs），作者使用GRU替换了公式（1）中的递归定义 ，从而消除“收缩图”要求，并支持现代优化技术。具体而言，公式（1）被修改如下：
s_i^{(t)} = (1-z_i^{(t)}) \odot s_i^{(t-1)} + z_i^{(t)} \odot \tilde{s}_i^{(t)} \tag{4}

其中 z 由更新门计算，\tlide{s} 是更新的候选者， t 是伪时间。其次，作者提议使用几个这样的网络按顺序运行来产生序列输出，并表明他们的方法可以应用于基于序列的任务，例如程序验证。

SSE 采取了与公式（4）类似的方法。然而，SSE 在计算中没有使用 GRU，而是采用随机定点梯度下降来加速训练过程。该方案基本上在使用局部邻域计算稳定节点状态和优化模型参数之间交替进行，两种计算均在随机小批量中进行。

3.2 图级 RNNs

图级 RNN，不是将一个 RNN 应用于每个节点来学习节点状态，而是将一个 RNN 应用于整个图以对图状态进行编码。

You et al.将图 RNN 应用于图生成问题。他们采用了两个 RNN：一个生成新节点，另一个以自回归的方式为新添加的节点生成边。他们表明，这种分层 RNN 架构比传统的基于规则的图生成模型更有效地从输入图中学习，同时具有合理的时间复杂度。

为了捕获动态图的时间信息，有人提出了动态图神经网络 (dy-namic graph neural network，DGNN) ，它使用时间感知 LSTM 来学习节点表示。当一条新边建立时，DGNN 使用 LSTM 更新两个交互节点及其直接邻居的表示，即考虑一步传播效应。作者表明，时间感知 LSTM 可以很好地模拟边形成的建立顺序和时间间隔。

图 RNN 还可以与其他架构相结合，例如 GCN 或 GAE。例如，为了解决图稀疏性问题，RMGCNN 将 LSTM 应用于 GCN 的结果以逐步重建图。通过使用 LSTM，来自图不同部分的信息可以在不需要多个 GCN 层的情况下扩散很长的距离。Dynamic GCN 应用 LSTM 从动态网络中的不同时间片收集 GCN 的结果，以获得空间和时间的图信息。

4. 图卷积网络

GCN 仿照 CNN，，通过设计卷积和读出函数，学习图的局部和全局结构特征。因为大多数 GCN 可以通过反向传播使用特定于任务的损失进行训练，这里重点介绍采用的架构。

4.1 卷积操作

图卷积可以分为两组：

  • 谱卷积，它通过使用图傅立叶变换或其扩展将节点表示转换到谱域来执行卷积
  • 空间卷积，它通过考虑节点邻域来执行卷积

这两个组可以重叠使用。

4.1.1 谱方法

用于图像或文本的标准卷积运算不能直接应用于图，因为图缺乏网格结构 。Bruna等人首先使用图 拉普拉斯矩阵 L, 从谱域中引入图数据的卷积，它在信号处理中起着与傅立叶基相似的作用。图卷积运算 ∗_G定义如下:
u_1 *_G u_2 = Q((Q^Tu_1) \odot (Q^T u_2)) \tag{5}

其中u_1, u_2 是定义在节点上的两个信号，Q 是 L 的特征向量。

乘以 Q^T 将图信号 u_1、u_2 转换到谱域（即图傅立叶变换），而乘以 Q 执行逆变换。该定义的有效性是基于卷积定理，即卷积运算的傅立叶变换是他们的傅立叶变换的元素乘积。一个信号 u 经过滤波器后变为
u' = Q \Theta Q^T u \tag{6}

(这里的 \Theta 是乘在 u 左边的)

一个卷积层是通过对不同的输入-输出信号对应用不同的滤波器来定义的，如下所示：
u_j^{l+1} = \rho(\sum_{i=1}^{f_l} Q \Theta_{i,j}^l Q^T u_i^l) \quad j=1,\cdots,f_{l+1} \tag{7}

公式（7）背后的思想类似于传统的卷积：它将输入信号通过一组可学习的滤波器来聚合信息，然后进行一些非线性转换。通过使用节点特征F^V作为输入层，叠加多个卷积层，整体架构类似于CNN。理论分析表明，这种图卷积运算的定义可以模拟CNN的几何特性。

然而，直接使用公式 (7) 需要学习 O(N) 的参数，这在实践中可能不可行。此外，频谱域中的滤波器可能不会定位在空间域中，也就是说，每个节点可能会受到所有其他节点的影响，而不仅仅是小区域内的节点。为了缓解这些问题，Brunaet al.建议使用以下平滑过滤器：
diag(\Theta_{i,j}^l) = K \a_{i,i,j} \tag{8}

其中K是一个固定的插值核，α_{l,i,j}是可学习的插值系数。作者还将这一思想推广到图不是给定的，而是使用有监督或无监督方法从原始特征构造的设置。

然而，两个基本问题仍未解决。

  • 首先，因为每次计算都需要拉普拉斯矩阵的完整特征向量，所以每次前向和后向传递的时间复杂度至少为O(N^2)，计算特征分解需要O(N^3)复杂度，这意味着这种方法不是可扩展到大规模图。
  • 其次，由于过滤器依赖于图的 特征基Q，参数不能在具有不同大小和结构的多个图之间共享。

接下来，我们回顾试图解决这些限制的两行工作，然后使用一些通用框架将它们统一起来。

4.1.2 效率方面

为了解决效率问题，ChebNet 提出使用多项式滤波器，如下：Θ(Λ) =∑^K_{k=0}θ_kΛ^k,\tag{9}
其中θ_0,...,θ_K 是可学习参数，K 是多项式阶数。然后，作者没有进行特征分解，而是使用切比雪夫展开式重写了公式 (9) ：
Θ(Λ) =∑^K_{k=0}θ_k T_k( \tilde{Λ}),\tag{10}

其中 \tilde{\Lambda} = 2 \Lambda/\lambda_{max}-I，是rescale后的特征值，\lambda_{max} 是特征值的最大值，I 是单位矩阵，T_k(x) 是k阶的切比雪夫多项式。由于 Chebyshev 多项式的正交基，重新缩放是必要的。利用拉普拉斯矩阵的多项式作为其特征值的多项式，即 L^k = Q\Lambda^k Q^T，公式（6）可以重写为
\begin{split} u' = Q \Theta( \Lambda) Q^T u &= ∑^K_{k=0}θ_k QT_k( \tilde{Λ})Q^Tu\\ &= ∑^K_{k=0}θ_k T_k( \tilde{L})u \\ &= ∑^K_{k=0}θ_k \tilde{u}_k \end{split} \tag{11}

其中 \tilde{u}_k = T_k(\tilde{L})u, \tilde{L}=2L/\lambda_{max}-I.

使用切比雪夫多项式的递归关系 T_k(x) = 2xT_{k-1}(x)-T_{k-2}(x)，T_0{x}=1，T_1(x) =x，也可以得到
\tilde{u}_k = 2\tilde{L} \tilde{u}_{k-1}-\tilde{u}_{k-2} \tag{12}

现在，因为只需要计算稀疏矩阵 \tilde{L} 的矩阵乘法，还有一些向量需要计算，所以使用稀疏矩阵乘法时的时间复杂度变为 O(KM)，其中 M 是边数，K 是多项式阶数，即时间复杂度是线性的边缘。也很容易看出，这样的多项式滤波器是严格 K 局部化的：在一次卷积之后，v_i 的表示将仅受其 K 步邻域 N_K(i) 的影响。有趣的是，这个想法在网络嵌入中被独立使用，以保留高阶近似，为了简洁起见省略了细节。
Kipf和Welling通过仅使用一阶邻域进一步简化了滤波：
h_i^{l+1} = \rho(\sum_{j \in N(i)} \frac{1}{\sqrt{\tilde{D}(i,i) \tilde{D}(j,j)}} h_j^l \Theta^l) \tag{13}
矩阵形式：
H^{l+1}=\rho(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}H^l \Theta^l) \tag{14}
其中， \tilde{A} = A+I, \tilde{D} = D+I，也就是，添加了自连接。作者通过设置k=1和一些细微的变化，证明了式（14）是式（9）的特例。然后，作者认为堆叠足够数量的层具有类似于ChebNet 的建模能力，但会产生更好的结果。

ChebNet及其扩展的一个重要见解是，它们将谱图卷积与空间结构联系起来。具体而言，它们表明，当谱卷积函数为多项式或一阶时，谱图卷积等价于空间卷积。此外，式（13）中的卷积与式（1）中GNN中的状态定义非常相似，只是卷积定义取代了递归定义。

从这一方面来看，GNN可以被视为具有大量相同层以达到稳定状态的GCN，即GNN使用具有固定参数的固定函数迭代更新节点隐藏状态，直到达到非平衡状态，而GCN具有预设层数，并且每层包含不同的参数。

还提出了一些谱方法来解决效率问题。例如，CayleyNet 没有使用公式（10）中的切比雪夫展开，而是采用Cayley多项式来定义图卷积。除了证明 CayleyNet 与 ChebNet 一样有效之外，作者还证明了 Cayley 多项式可以检测“重要的窄频带”，以获得更好的结果。于是进一步提出了图小波神经网络（GWNN），通过重写方程来用图小波变换代替谱滤波器中的傅立叶变换。 GWNN 的计算复杂度也是 O(KM)，即与边数成线性关系。

4.1.3 多个图

一系列并行的工作侧重于将图卷积推广到任意大小的多个图。Neural FPs 提出了一种空间方法，该方法也使用一阶邻居：
h_i^{l+1} = \sigma (\sum_{j \in N(i)} h_j^l \Theta ^l) \tag{17}

由于参数Θ可以在不同的图之间共享，并且与图的大小无关，因此 Neural FPs可以处理任意大小的多个图。等式（17）与等式（13）非常相似，然而，Neural FPs 没有通过添加一个归一化项来考虑节点度的影响，而是建议为不同度的节点学习不同的参数。该策略对于小图（如分子图）表现良好（即原子作为节点，键作为边），但可能不适用于较大的图。

（跳过了一些）

4.1.4 Frameworks

基于上述工作，MPNNs 被提出，作为使用消息传递函数在空间域中进行图卷积运算的统一框架：

m_i^{l+1} = \sum_{j \in N(i)} F^l(h_i^l, h_j^l, F^E_{i,j}) \\ h_i^{l+1} = G^l(h_i^l, m_i^{l+1}) \tag{21}

其中F^l(·)和G^l(·)分别是要学习的消息函数和顶点更新函数，m^l表示节点之间传递的“消息”。从概念上讲，MPNN 是一个框架，其中每个节点根据其状态发送消息，并根据从直接邻居收到的消息更新其状态。作者表明，上述框架已经包括了许多现有的方法，如 GGS-NNs 、Brunaet al.、Henaffet al.、Neural FPs 、Kipf 和 Welling 和 Kearnes et al.。 此外，作者提出增加一个连接所有节点的“主”节点以加速长距离的消息传递，并将隐藏的表示拆分为不同的“塔”以提高泛化能力。作者表明，MPNN 的特定变体可以在预测分子特性方面达到 state-of-the-art。

同时，GraphSAGE 采用了与等式（21）类似的思想，使用了多个聚合函数，如下所示：

m_i^{i+1} = AGGREGATE^l ({h_j^l, \forall j \in N(i)}) \\ h_i^{l+1} = \rho(\Theta[h_i^l, m_i^{l+1}]) \tag{22}

其中 [·,·] 是连接操作，AGGREGATE(·) 表示聚合函数。作者提出了三个聚合函数：元素均值、LSTM 和最大池化，如下所示：
AGGREGATE^l = max{\rho(\Theta_{pool}h_j^l + b_{pool})}, \forall j \in N(i) \tag{23}

其中 Θ_{pool} 和 b_{pool}是要学习的参数，max{·}是元素最大值。对于 LSTM 聚合函数，因为需要一个邻居顺序，作者采用了一个简单的随机顺序。

混合模型网络（MoNet）还尝试使用“模板匹配”将现有的 GCN 模型以及流形的 CNN 统一为一个通用框架。

图网络 (GNs) 为 GCNs 和 GNNs 提出了一个更通用的框架，它学习了三组表示：h^l_i、e^l_{i,j} 和 z^l 分别是节点、边和整个图的表示。这些表示是使用三个聚合和三个更新函数学习的：

消息传递函数都以集合作为输入，因此它们的参数长度是可变的，并且这些函数应该对输入排列保持不变；一些示例包括逐元素求和、均值和最大值。与 MPNN 相比，GNs 引入了边表示和整个图的表示，从而使框架更加通用。

总之，卷积运算已经从频谱域发展到空间域，从多步邻居发展到直接邻居。目前，从近邻收集信息（如等式（14））并遵循等式(21)(22)(27) 的框架是图卷积运算最常见的选择。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,547评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,399评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,428评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,599评论 1赞 274
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,612评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,577评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,941评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,603评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,852评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,605评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,693评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,375评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,955评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,936评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,172评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,970评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,414评论 2赞 342

推荐阅读更多精彩内容