GCN

摘要

我们提出了一种可扩展的图结构数据半监督学习方法，该方法基于直接在图上运行的卷积神经网络的有效变体。 我们通过谱图卷积的局部一阶近似来选择我们的卷积架构。 我们的模型在图边的数量上线性缩放，并学习对局部图结构和节点特征进行编码的隐藏层表示。 在引文网络和知识图数据集上的大量实验中，我们证明我们的方法明显优于相关方法。

1、介绍

为什么称为“半监督节点分类”：在一个图中，标签只是部分可知。

前人的提出的方法，在损失函数中加入拉普拉斯正则项：

$$\Iota = \Iota_0+\lambda*\Iota_{reg} \\其中\ \Iota_{reg}=\sum_{i,j}A_{i,j}||f(X_i)-f(X_j)||^2=f(X)^T\Delta f(X)$$

代表监督损失，可以是一个神经网络，X是特征矩阵，是权重因子，表示非归一化的拉普拉斯矩阵。

上述式子依赖于一个假设：图中的连接节点可能有相同的标签。 然而，这种假设可能会限制建模能力，因为图的边不一定需要对节点相似性进行编码，可能包含附加信息。

本文的贡献：1、为神经网络模型引入了一种简单且表现良好的分层传播规则，该规则 直接在图上运行，并展示了如何从谱图卷积的一阶近似中激发。

​ 2、实现1。

2、图上的快速近似卷积

层级映射传播规则:

$$H^{(l+1)}=\sigma(\tilde{D}^{-\frac{1}{2}}\widetilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$$

，是由的度矩阵，, 是权值矩阵

2.1、谱域图卷积

谱域上的滤波器,

$$g_\theta*x=U g_\theta U^Tx$$

是归一化的图拉普拉斯矩阵的特征向量，,对于大型图来说，由于拉普拉斯的谱分解计算量巨大，所以采用“K阶切比雪夫多项式”来近似,如下：

$$g_{\theta^{'}}(\Lambda)\thickapprox\sum_{k=0}^{K}\theta_k^{'}T_k(\tilde\Lambda)$$

其中. 是切比雪夫系数的向量，切比雪夫多项式递归形式为.

整合上式，得到：

$$g\theta^{'}*x\thickapprox\sum_{k=0}^{K}\theta_k^{'}T_k(\tilde L)x,$$

其中，,该表达式现在是 K 局部化的，因为它是拉普拉斯算子中的 K 阶多项式，即它仅取决于距离中心节点（K 阶邻域）最大 K 步的节点。

2.2 分层线性模型

通过这种方式，我们仍然可以通过堆叠多个此类层来恢复丰富的卷积滤波器函数类别，但我们不限于由切比雪夫多项式等给出的显式参数化。

在GCN的线性公式里，,以上式子再次简化为：

$$g_{\theta'}\star x\approx\theta'_0x+\theta'_1\left(L-I_N\right)x=\theta'_0x-\theta'_1D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x,$$

是自由参数，过滤器参数可以在整个图共享。

在实践中，进一步限制参数的数量以解决过度拟合并最大限度地减少每层的操作（例如矩阵乘法）数量可能是有益的。 这给我们留下了以下表达式：

$$g_\theta\star x\approx\theta\left(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\right)x,$$

其中,而的特征值值范围是[0,2],因此，当在深度神经网络模型中使用时，重复应用该算子可能会导致数值不稳定和梯度爆炸/消失。

为了缓解这个问题，我们引入了以下重整化技巧:

得到以下公式：

$$Z=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}X\Theta,$$

其中,现在是滤波器参数矩阵,Z是经过滤波后的矩阵。

3、 半监督节点分类

正如引言中所述，我们可以通过在数据 X 和底层图结构的邻接矩阵 A 上调节模型 f (X, A) 来放宽基于图的半监督学习中通常做出的某些假设。 我们期望此设置在邻接矩阵包含数据 X 中不存在的信息的场景中特别强大，例如引文网络中文档之间的引文链接或知识图中的关系。 整个模型是一个用于半监督学习的多层 GCN，如图 所示。

3.1、 例子

下面，我们考虑在具有对称邻接矩阵 A（二进制或加权）的图上进行半监督节点分类的两层 GCN。 我们首先在预处理步骤中计算 。 我们的前向模型采用简单的形式：

$$Z=f(X,A)=\text{softmax}\Big(\hat{A}\text{ReLU}\Big(\hat{A}XW^{(0)}\Big)W^{(1)}\Big).$$

使用交叉熵损失函数：

$$\mathcal{L}=-\sum_{l\in\mathcal{Y}_L}\sum_{f=1}^FY_{lf}\ln Z_{lf},$$

代表节点标签,表示预测结果。

4、相关工作

我们的模型从基于图的半监督学习领域和最近在图上运行的神经网络的工作中汲取了灵感。 接下来，我们将简要概述这两个领域的相关工作。

4.1、基于图的半监督学习

近年来，人们提出了大量使用图表示的半监督学习方法，其中大多数分为两大类：使用某种形式的显式图拉普拉斯正则化的方法和基于图嵌入的方法。 图拉普拉斯正则化的突出例子包括标签传播（Zhu et al., 2003）、流形正则化（Belkin et al., 2006）和深度半监督嵌入（Weston et al., 2012）。

4.2、图上的神经网络

5、实验

我们在许多实验中测试我们的模型：引文网络中的半监督文档分类、从知识图提取的二分图中的半监督实体分类、各种图传播模型的评估以及随机图的运行时分析 。

5.1、数据集

Dataset	Type	Nodes	Edges	Classes	Features	Label rate
Citeseer	Citation network	3,327	4,732	6	3703	0.036
Cora	…	270.	5429	7	1433	0.052
Pubmed	…	19717	44338	3	500	0.003
NELL	Knowledge graph	65755	266144	210	5414	0.001

5.2、实验设置

1、两层GCN，500个验证集，1000个测试集。

2、L2正则化。

3、学习率0.01，早停机制，dropout，32个隐藏层神经元。

5.3、BaseLines

我们与 Yang 等人的相同基线方法进行比较。 （2016），即标签传播（LP）（Zhu et al., 2003）、半监督嵌入（SemiEmb）（Weston et al., 2012）、流形正则化（ManiReg）（Belkin et al., 2006）和跳过 基于-gram 的图嵌入（DeepWalk）（Perozzi 等人，2014）。 我们省略了 TSVM（Joachims，1999），因为它无法扩展到我们的数据集中的大量类。

我们进一步将 Lu & Getoor (2003) 中提出的迭代分类算法 (ICA) 与两个逻辑回归分类器相结合进行比较，一个用于单独的局部节点特征，另一个用于使用局部特征和聚合算子的关系分类，如 Sen 等人中所述。 等人。 （2008）。 我们首先使用所有标记的训练集节点训练局部分类器，并使用它来引导未标记节点的类标签以进行关系分类器训练。 我们使用随机节点排序运行迭代分类（关系分类器），在所有未标记节点上进行 10 次迭代（使用本地分类器引导）。 L2 正则化参数和聚合运算符（count 与 prop，参见 Sen 等人 (2008)）是根据每个数据集的验证集性能分别选择的。

6、结果

6.1、节点分类

6.2、传播模型的评估

我们在引文网络数据集上比较了我们提出的每层传播模型的不同变体。 我们遵循上一节中描述的实验设置。 结果总结在表 3 中。我们原始 GCN 模型的传播模型由重整化技巧（粗体）表示。 在所有其他情况下，两个神经网络层的传播模型都替换为传播模型下指定的模型。 报告的数字表示随机权重矩阵初始化的 100 次重复运行的平均分类精度。 如果每层有多个变量 θi，我们对第一层的所有权重矩阵进行 L2 正则化。

6.3、每轮训练时间

7、讨论

7.1、半监督模型

在这里演示的实验中，我们的半监督节点分类方法明显优于最近的相关方法。 基于图拉普拉斯正则化的方法（Zhu et al., 2003; Belkin et al., 2006; Weston et al., 2012）很可能受到限制，因为它们假设边缘仅编码节点的相似性。 另一方面，基于 Skip-gram 的方法受到以下事实的限制：它们基于难以优化的多步骤管道。 我们提出的模型可以克服这两个限制，同时在效率（以挂钟时间衡量）方面仍然优于相关方法。 与仅聚合标签信息的 ICA (Lu & Getoor, 2003) 等方法相比，每层中相邻节点的特征信息传播提高了分类性能。

我们进一步证明，与原始一阶模型相比，所提出的重整化传播模型（方程 8）不仅提高了效率（更少的参数和运算，例如乘法或加法），而且在许多数据集上提供了更好的预测性能（ 方程 6）或使用切比雪夫多项式的高阶图卷积模型（方程 5）。

7.2、局限性和未来的工作、

内存需求。在当前的全批量梯度下降设置中，内存需求随着数据集的大小线性增长。 我们已经证明，对于 GPU 内存无法容纳的大型图，在 CPU 上进行训练仍然是一个可行的选择。 小批量随机梯度下降可以缓解这个问题。 然而，生成小批量的过程应该考虑 GCN 模型中的层数，因为具有 K 层的 GCN 的 K 阶邻域必须存储在内存中才能实现精确的过程。 对于非常大且紧密连接的图形数据集，可能需要进一步的近似。

有向边和边特征。我们的框架目前并不自然支持边特征，并且仅限于无向图（加权或未加权）。 然而，NELL 上的结果表明，通过将原始有向图表示为无向二部图，并使用表示原始图中边的附加节点，可以处理有向边和边特征（详细信息请参见第 5.1 节）。

限制性假设。通过第 2 节中介绍的近似，我们隐含地假设局部性（依赖于具有 K 层的 GCN 的 K 阶邻域）以及自连接与相邻节点的边的同等重要性。 然而，对于某些数据集，在的定义中引入权衡参数 λ 可能会有所帮助：

$$\tilde A=A+\lambda I_N$$

该参数现在起着与典型半监督设置中监督和无监督损失之间的权衡参数类似的作用（参见方程 1）。 然而，在这里，它可以通过梯度下降来学习。

8、结论

我们引入了一种对图结构数据进行半监督分类的新方法。 我们的 GCN 模型使用高效的分层传播规则，该规则基于图上谱卷积的一阶近似。 对多个网络数据集的实验表明，所提出的 GCN 模型能够以对半监督分类有用的方式编码图结构和节点特征。 在这种情况下，我们的模型在计算效率上明显优于最近提出的几种方法。

附录

A.1具有随机权重的节点嵌入

通过与 Weisfeiler-Lehman 算法的类比，我们可以理解，即使是未经训练的具有随机权重的 GCN 模型也可以作为图中节点的强大特征提取器。

A.2半监督节点嵌入

略

B.模型深度实验

在这些实验中，我们研究了模型深度（层数）对分类性能的影响。 除了标准 GCN 模型（方程 2）之外，我们还报告了模型变体的结果，其中我们在隐藏层之间使用残差连接（He et al., 2016），通过使模型能够携带信息来促进更深层次模型的训练 来自上一层的输入：

$$H^{(l+1)}=\sigma\Big(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}\Big)+H^{(l)}.$$

对于此处考虑的数据集，通过 2 层或 3 层模型获得最佳结果。 我们观察到，对于深度超过 7 层的模型，不使用残差连接的训练可能会变得困难，因为每个节点的有效上下文大小都会随着其 K 阶邻域的大小而增加（对于具有 K 层的模型）。 层。 此外，随着参数数量随着模型深度的增加而增加，过度拟合可能成为一个问题。