第1部分——基于GatedGCN的Graph Neural Networks简介
图表示学习(Graph Representation Learning)
图表示学习是在低维嵌入中有效总结图形结构的任务。随着深度学习的兴起，研究人员提出了各种涉及使用神经网络进行图表示学习的架构。我们把这样的架构称为图神经网络。
在这个 Google Colab 笔记本中实验图神经网络 →
为什么我们需要图神经网络（GNN）？
在谈论 GNN 细节之前，我们首先要了解这样做的背后动机。有人可能会问，我们在图表示学习中能不能不使用我们目前的深度学习架构（CNN和RNN）。然而，可以看到的是，CNN 专门用于网格型结构，而 RNN 则专门用于顺序数据。相反，图像的结构并不明朗，可以在这种环境下学习的特殊方法会更合适。
图像无处不在！
各种数据存储都有一个固有的图像结构，利用这些数据可以产生很多影响。以下是 GNN 可能产生影响的各个域：
- 社交网络
- 经济网络
- 生物医学网络
- 互联网
- 神经元网络
这些网络可以被用于完善推荐系统，了解各种元素的经济影响、药物发现，了解大脑中的神经元如何发挥作用，以及许多其他应用。
问题陈述
节点分类
基于其他已知节点对未知节点进行分类。例如，将社交媒体账号分为机器人或人类。
图像分类
它涉及将整个图像分类为预定义的类别。例如，根据分子的原子结构预测分子是否可溶于水。
链接预测
确定图中的特定节点是否与一些其它节点链接。例如，它可在社交网络中使用，用于预测一个人是否认识另一个人并进行朋友推荐。
图像回归
图像回归任务类似于逻辑回归和逻辑分类。它有一个不同的损失函数和性能度量，重点是根据可用的图形结构而不是分类来回归特定变量。
生成节点嵌入
从图像结构中学习表示的任务包括为图像的节点创建低维嵌入。目标是在低维欧几里得空间中缩短相似节点之间的距离。此任务如下图所示。
我们将讨论两种基本的节点嵌入方法。（1）经典的“浅层”方法，和（2）基于神经网络的方法。
浅层嵌入法
浅层嵌入法的典型特征是编码器的大小随图中节点的数量呈线性增长。节点嵌入的检索的本质就是查表。故名为“浅层”。
就最简单的浅层编码方案而言，如下图所示：
学习浅层节点嵌入任务通常涉及三个步骤：
1. 定义一个将节点映射到嵌入的编码器。
其中 ZϵRd×∣ν∣,∣ν∣Z \epsilon R^{d \times |\nu|}, |\nu|, 是图像中的节点数，vv 是图中任意节点的独热编码矢量。
**2. 定义一个衡量两个节点的相似性的函数，即相似性 similarity(u,v)similarity(u, v)。
3. Optimize the parameters of the encoder such that similarity(u,v)≈zvT.zusimilarity(u, v) \approx z_v^T.z_u
还有其他基于浅层编码的方式，如Node2Vec、DeepWalk与 LINE。但是，这些方法存在一些固有的问题：
-
编码器大小是 O(∣V∣)\Omicron (|V|)，这会影响拥有许多节点的大型图像的可扩展性。
-
很难定义基于其优化编码器参数的相似性度量。如果我们基于相邻节点计算相似性度量，则度量的范围将限制嵌入到简单地聚集最近的邻居，且增加覆盖范围将导致计算复杂性增加。
-
这种浅层嵌入方法只能对训练期间图像中存在的节点起作用。因此，图像更新时将不能使用这种方法。
-
这些方法结合了对某些任务有用的节点特征。
图神经网络
如上所述，浅层嵌入方法具有某些限制会影响其在现实生活场景中的执行能力。为了重新调解这些问题，我们来看看GNN。基于神经网络的节点嵌入方法大致有两种类型：
1. .基于消息传递的GCN
2. 基于 WL 测试的 Weisfeiler-Lehman GNN[1]
在本报告中，我们将仅讨论基于消息传递的GCN，因为当前基于WLGNN的方法是不可扩展的。它们的复杂性相对于图像大小在空间和时间上呈多项式地增加，这通常增加了在大型数据集中使用WLGNN的难度。
基于消息传递的图卷积神经网络（GCN）
基于消息传递的GCN依赖于称为邻域聚合的概念。基本上，每个节点的嵌入将是其所有通过神经网络的邻居的平均值。如果您的操作正确，您可能会对它只是聚合邻居而感到奇怪。然而，这是一个迭代过程，因此可以想象，几次迭代之后的聚合将被复合，从而覆盖整个图像。这一过程可视化图如下。
从形式上讲，这个过程可以概括为以下步骤：
1. .定义邻域聚合函数
最简单的情况是每个节点平等地考虑其所有邻居，即所有邻居的权重相等，对生成的节点嵌入具有相等的影响。这样的结构也被称为各向同性。如GCN[2]与GraphSage[3].下方的各向同性程序显示了各向同性体系结构的节点更新操作。
hil+1=σ(W1lhil+ΣjϵNiW2lhjl),hl,hl+1ϵRn×d,W1,2lϵRd×dh^{l+1}_i = \sigma(W_1^l h_i^l + \Sigma_{j\epsilon N_i} W_2^l h_j^l ), \quad h^l, h^{l+1}\epsilon \R^{n\times d}, W^l_{1,2}\epsilon \R^{d\times d}
σ\sigma 是类似ReLU的激活函数
更高级的架构是各向异性的，也就是说，每个邻居对生成的节点嵌入的影响不同。如MoNet[4]、GAT[5]、GatedGCN[6].以下方程显示了各向异性体系结构的节点更新操作。
hil+1=σ(W1lhil+ΣjϵNiηijW2lhjl),hl,hl+1ϵRn×d,W1,2lϵRd×dh^{l+1}_i = \sigma(W_1^l h_i^l + \Sigma_{j\epsilon N_i} \eta_{ij} W_2^l h_j^l ), \quad h^l, h^{l+1}\epsilon \R^{n\times d}, W^l_{1,2}\epsilon \R^{d\times d}
其中 \eta{ij} = f^l(h^l_i, h^l_j)$ 以及 flf^l 是训练期间权重被学习的参数化函数。
观察这里作为注意机制的 $\eta{ij}$ 。
2. 定义损失函数
损失函数基于要进行预测的任务定义。例如，对于节点分类任务，损失函数将是预测标签的BCE损失。因此，学习的节点嵌入将有效地提取有助于确定节点类别的特征。
3. 训练
基于定义的损失函数，我们应用梯度下降来更新整个网络共享的参数的权重。由于每个更新步骤仅依赖于本地邻居，因此该操作具有高度可扩展性，并允许批处理操作。
现在我们已经了解了基于消息传递的GCN，我们将在下文中研究这种类型的最佳性能体系结构之一——图卷积神经网络。
图卷积神经网络
GatedGCN架构是一种基于各向异性消息传递的GNN，它采用了剩余连接、批处理规范化和边缘门。给出的图像总结了GatedGCN网络的每一层。
一层 GatedGCN[7]
hil+1=hil+ReLU(BN(Ulhil+ΣjϵNieijl⊙Vlhjl)),h^{l+1}_i = h^l_i + ReLU(BN(U^l h_i^l + \Sigma_{j\epsilon N_i} e^l_{ij}\odot V^l h^l_j )), ,hil+1=hil+ReLU(BN(Ulhil+ΣjϵNieijl⊙Vlhjl)), 其中 Ul,V^l \epsilon \R^{d\times d},意味着对位相乘，, 意味着对位相乘，Ni$ 是节点 ii 的邻居， $e^l{ij}$ 是定义如下的边缘门：
eijl=σ(e^ijl)÷(Σj′ϵNiσ(e^ij′l)+ε)e^l_{ij} = \sigma(\hat{e}^{l}_{ij})\div (\Sigma_{j'\epsilon N_i} \sigma(\hat{e}^{l}_{ij'}) + \varepsilon)
e^ijl=e^ijl−1+ReLU(BN(Alhil−1+Blhjl−1+Cle^ijl−1))\hat{e}^{l}_{ij} = \hat{e}^{l-1}_{ij} + ReLU(BN(A^l h^{l-1}_i + B^l h^{l-1}_j + C^l \hat{e}^{l-1}_{ij}))
其中 σ\sigma 是 signmoid 函数， ε\varepsilon 是数值稳定性的小固定常量， Al,Bl,ClϵRd×dA^l, B^l, C^l \epsilon \R^{d \times d}
现在有很多方程，让我们看看这些方程所表现出的显著特征。
特色
- 其中的 hil+1=hil+ReLU(...)h^{l+1}_i = h^l_i + ReLU(...)表示神经网络中的剩余链接。这些“跳过连接”降低了更深层次网络的训练的难度。
- eijle^l_{ij} 充当注意机制，因为它确定给予每个邻居的权重。
- BNBN 表示有助于稳定学习过程的批标准化。
现在我们已经了解了GatedGCN的特性，我们将在下文中实际对其进行实验。
实验
我们在Dwivedi等人提出的用于二元节点分类的模式数据集上训练我们的网络。它是使用随机块模型（SBM）生成的人工数据集。已知SBM可控制地对社交网络中的社区进行建模。我们的训练/验证/测试拆分是10K/2K/2k图像平均有117个节点和4749条边。
实验在PyTorch中进行。可在此链接中取得Colab笔记。我们使用Adam优化器和ReduceLROnPlateau调度器。初始学习率为10-3，降低因子为0.5。Colab在实验时分配的GPU是Nvidia T4。该模型在约50个epoch中收敛，每个epoch耗时约280s。
从验证精度与epoch图中可以看出，该模型以84.37%的验证精度收敛。
最后，在测试分裂上的分类准确率为84.5%。
完整代码 →
结论
在这份报告中，我们了解了图表示学习背后的动机和对GNN的需求。我们还广泛地研究了当前正在研究的基于GNN的方法，对这些方法有了直观的认识。最后，我们了解了性能最好的GNN架构之一——GatedGCN的内部活动。
虽然这份报告概述了图表示学习中使用的方法，但就目前可用的文献的深度而言，我们只触及了表面。我想推荐读者阅读 Dwivedi 等人的论文Benchmarking Graph Neural Networks（图神经网络基准）。此论文深入研究了当前GNN体系结构的更多细节，并对所有方法进行了标准化比较。他们还在Github上发布了他们的代码。这个实验中使用的代码是他们的代码的简化版本。作为练习，读者可以使用权重和偏差报告来训练和比较所有的体系结构。
请查看本文的第2部分，我在其中比较了基于消息传递的GNN体系结构。
参考文献
