使用

图卷积网络进行半监督分类

摘要

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

1简介

我们考虑对图中（例如引文网络）中的节点（例如文档）进行分类的问题，其中标签仅适用于一小部分节点。 这个问题可以被描述为基于图的半监督学习，其中标签信息通过某种形式的显式基于图的正则化在图上进行平滑（Zhu 等人，2003；Zhou 等人，2004；Belkin 等人, 2006; Weston 等人, 2012), 例如通过在损失函数中使用图拉普拉斯正则化项：

$$ℒ={ℒ}_0+\lambda {ℒ}_{\text{reg}},\text{with}{ℒ}_{\text{reg}}=\sum _{i,j}{A}_{ij}{\Vert f(X_i)-f(X_j)\Vert }^2=f{(X)}^{\top }\mathrm{\Delta }f(X).$$ (1)

这里，${ℒ}_0$表示监督损失。 $f(\cdot )$可以是类似神经网络的可微分函数，$\lambda$是权重系数，$X$是节点特征向量矩阵$X_i$。 $\mathrm{\Delta }=D-A$表示无向图 $𝒢=(𝒱,ℰ)$ with $N$ nodes $v_i\in 𝒱$,edges $(v_i,v_j)\in ℰ$,邻接矩阵 $A\in {ℝ}^{N\times N}$（二值或加权）和度矩阵$D_{ii}={\sum }_j{A}_{ij}$. 方程式的制定1 依赖于图中的连接节点可能共享相同标签的假设。 然而，这种假设可能会限制建模能力，因为图边不一定需要对节点相似性进行编码，但可能包含附加信息。

在这项工作中，我们直接使用神经网络模型$f(X,A)$ 并在受监督目标上训练 ${ℒ}_0$ 调节$f(\cdot )$ 在图的邻接矩阵上将允许模型从监督损失中分配梯度信息 ${ℒ}_0$ 并将启用它学习带标签和不带标签的节点的表示。

我们的贡献是双重的。 首先，我们为神经网络模型引入了一种简单且表现良好的分层传播规则，该规则直接在图上运行，并展示了如何从谱图卷积的一阶近似中激发它（Hammond等人，2011） ）。 其次，我们演示了这种形式的基于图的神经网络模型如何用于对图中节点进行快速且可扩展的半监督分类。 对多个数据集的实验表明，我们的模型在分类准确性和效率（以挂钟时间测量）方面与最先进的半监督学习方法相比都具有优势。

2 图上的快速近似卷积

在本节中，我们为特定的基于图的神经网络模型提供理论动机 $f(X,A)$ 我们将在本文的其余部分使用它。 我们考虑具有以下逐层传播规则的多层图卷积网络（GCN）：

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

这里，$\tilde{A}=A+I_N$是无向图的邻接矩阵$𝒢$ $I_N$为单位矩阵，${\tilde{D}}_{ii}={\sum }_j{\tilde{A}}_{ij}$和$W^{(l)}$ $\sigma (\cdot )$ 表示激活函数，例如 $\mathrm{ReLU}(\cdot )=\max (0,\cdot )$。 $H^{(l)}\in {ℝ}^{N\times D}$。是 $l^{\text{th}}$ 层的激活矩阵；$H^{(0)}=X$. 下面，我们证明这个传播规则的形式可以被激发 通过图 上局部光谱滤波器的一阶近似（Hammond 等人，2011；Defferrard 等人，2016）。

2.1 谱图卷积

我们考虑图上的谱卷积，定义为信号 $x\in {ℝ}^N$ （每个节点的标量），带有过滤器 $g_{\theta }=\text{diag}(\theta )$ 由 $\theta \in {ℝ}^N$

$$g_{\theta }\star x=U{g}_{\theta }{U}^{\top }x,$$ (3)

其中，$U$ 是归一化图形拉普拉奇的特征向量矩阵$L=I_N-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}=U\mathrm{\Lambda }{U}^{\top }$,其特征值的对角矩阵 $\mathrm{\Lambda }$ 和 $U^{\top }x$ 是 $x$ 的图傅里叶变换。 我们可以将$g_{\theta }$理解为$L$特征值的函数，即$g_{\theta }(\mathrm{\Lambda })$。 评估方程3 的计算量很大，因为与特征向量矩阵 $U$ 相乘是 $𝒪(N^2)$。 此外，对于大型图来说，首先计算 $L$ 的特征分解可能会非常昂贵。 To circumvent this problem, it was suggested in Hammond et al. (2011) that $g_{\theta }(\mathrm{\Lambda })$ can be well-approximated by a truncated expansion in terms of Chebyshev polynomials $T_k(x)$ up to $K^{\text{th}}$ order:

$$g_{{\theta }^{\prime }}(\mathrm{\Lambda })\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{\mathrm{\Lambda }}),$$ (4)

重新调整后的 $\tilde{\mathrm{\Lambda }}=\frac{2}{{\lambda }_{\text{max}}}\mathrm{\Lambda }-I_N$。 ${\lambda }_{\text{max}}$表示$L$的最大特征值。 ${\theta }^{\prime }\in {ℝ}^K$ 现在是切比雪夫系数的向量。 切比雪夫多项式的递归定义为$T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$,with $T_0(x)=1$and $T_1(x)=x$. 读者可以参考Hammond等人(2011)来深入讨论这种近似。

回到我们对信号 $x$ 与滤波器 $g_{{\theta }^{\prime }}$，我们现在有：

$$g_{{\theta }^{\prime }}\star x\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x,$$ (5)

与 $\tilde{L}=\frac{2}{{\lambda }_{\text{max}}}L-I_N$；通过注意 ${(U\mathrm{\Lambda }{U}^{\top })}^k=U{\mathrm{\Lambda }}^k{U}^{\top }$ 请注意，此表达式现在是 $K$ 局部化的，因为它是拉普拉斯算子中的 $K^{\text{th}}$ 阶多项式，即它仅取决于距中心节点最大 $K$ 步的节点($K^{\text{th}}$ 评估方程的复杂性。 5 是 $𝒪(|ℰ|)$，即边数呈线性。 Defferrard 等人 (2016) 使用这个 $K$ 局部卷积来定义图上的卷积神经网络。

2.2逐层线性模型

因此，可以通过堆叠式（1）形式的多个卷积层来构建基于图卷积的神经网络模型。 5，每一层后面都有一个逐点非线性。 现在，假设我们将逐层卷积运算限制为 $K=1$ （参见等式 5)，即与线性关系的函数。 $L$ 因此是图拉普拉斯谱上的线性函数。

通过这种方式，我们仍然可以通过堆叠多个此类层来恢复丰富的卷积滤波器函数类别，但我们不限于由切比雪夫多项式等给出的显式参数化。 我们直观地期望这样的模型可以缓解节点度分布非常宽的图（例如社交网络、引用网络、知识图和许多其他现实世界图数据集）的局部邻域结构过度拟合的问题。 此外，对于固定的计算预算，这种逐层线性公式允许我们构建更深的模型，这种做法众所周知可以提高多个领域的建模能力（He等人，2016）。

在 GCN 的线性公式中，我们进一步近似 ${\lambda }_{\text{max}}\approx 2$，因为我们可以预期神经网络参数将在训练期间适应这种规模变化。 在这些近似下5 简化为：

$$g_{{\theta }^{\prime }}\star x\approx {\theta }_0^{\prime }x+{\theta }_1^{\prime }\left(L-I_N\right)x={\theta }_0^{\prime }x-{\theta }_1^{\prime }{D}^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}x,$$ (6)

有两个自由参数 ${\theta }_0^{\prime }$ 和 ${\theta }_1^{\prime }$。 过滤器参数可以在整个图表上共享。 连续应用这种形式的过滤器可以有效地对节点的 $k^{\text{th}}$ 阶邻域进行卷积，其中 $k$是神经网络模型中连续过滤操作或卷积层的数量。

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

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

具有单个参数 $\theta ={\theta }_0^{\prime }=-{\theta }_1^{\prime }$。 请注意 $I_N+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$ 现在的特征值在 $[0,2]$ 因此，当在深度神经网络模型中使用时，重复应用该算子可能会导致数值不稳定和梯度爆炸/消失。 为了缓解这一问题，我们引入了以下重正化技巧：$I_N+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\to {\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$,with $\tilde{A}=A+I_N$ and${\tilde{D}}_{ii}={\sum }_j{\tilde{A}}_{ij}$.

We can generalize this definition to a signal $X\in {ℝ}^{N\times C}$ with $C$ input channels (i.e. a $C$-dimensional feature vector for every node) and $F$ filters or feature maps as follows:

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

其中$\mathrm{\Theta }\in {ℝ}^{C\times F}$ 现在是滤波器参数矩阵，$Z\in {ℝ}^{N\times F}$ 此过滤操作具有复杂性 $𝒪(|ℰ|FC)$，如$\tilde{A}X$

3 半监督节点分类

引入了一个简单而灵活的模型 $f(X,A)$为了图上的高效信息传播，我们可以回到半监督节点分类问题。 正如导言中所述，我们可以通过对模型 $f(X,A)$ 的数据 $X$ 和底层图结构的邻接矩阵 $A$ 进行调节，从而放宽基于图的半监督学习中的某些典型假设。 我们希望此设置在邻接矩阵包含数据 $X$ 中不存在的信息的情况下特别强大，例如引文网络中文档之间的引文链接或知识图中的关系。 整个模型是一个用于半监督学习的多层 GCN，如图 1 所示。

(a) 图卷积网络

(b) 隐藏层激活

图1： 左：用于半监督学习的多层图卷积网络 (GCN) 的示意图，其中具有 $C$ 输入通道和 $F$ 特征图输出层。 图结构（边缘显示为黑线）在各层之间共享，标签由 $Y_i$ 表示。 右：t-SNE （Maaten & Hinton，2008） 在 Cora 数据集上训练的两层 GCN 的隐藏层激活可视化（Sen 等人， 2008） 使用 $5\%$ 标签。 颜色表示文档类别。

3.1示例

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

$$Z=f(X,A)=\mathrm{softmax}\left(\widehat{A}\mathrm{ReLU}\left(\widehat{A}X{W}^{(0)}\right)W^{(1)}\right).$$ (9)

这里，$W^{(0)}\in {ℝ}^{C\times H}$ 是具有 $H$ $W^{(1)}\in {ℝ}^{H\times F}$ 是隐藏到输出的权重矩阵。 softmax激活函数，定义为 $\mathrm{softmax}(x_i)=\frac{1}{𝒵}\exp (x_i)$ 与 $𝒵={\sum }_i\exp (x_i)$ 对于半监督多类分类，我们评估所有标记示例的交叉熵误差：

$$ℒ=-\sum _{l\in {𝒴}_L}\sum _{f=1}^F{Y}_{lf}\ln Z_{lf},$$ (10)

其中 ${𝒴}_L$ 是具有标签的节点索引集。

神经网络权重$W^{(0)}$和 $W^{(1)}$ 使用以下方法进行训练梯度下降。 在这项工作中，我们在每次训练迭代中使用完整数据集执行批量梯度下降，只要数据集适合内存，这就是一个可行的选择。 使用 $A$ 的稀疏表示，内存需求为 $𝒪(|ℰ|)$，即与数量呈线性关系边缘。 训练过程中的随机性是通过 dropout (Srivastava 等人, 2014) 引入的。 我们将小批量随机梯度下降的内存高效扩展留给未来的工作。

3.2实施

在实践中，我们利用 TensorFlow (Abadi 等人, 2015) 进行基于 GPU 的高效实现 方程的9 使用稀疏密集矩阵乘法。 评估方程的计算复杂度。 9 则为 $𝒪(|ℰ|CHF)$0>，即图边数呈线性。

4相关工作

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

4.1基于图的半监督学习

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

最近，人们的注意力已经转移到使用受skip-gram模型启发的方法来学习图嵌入的模型（Mikolov等人，2013）。 DeepWalk (Perozzi 等人, 2014) 通过预测节点的局部邻域来学习嵌入，这些节点是从图上的随机游走中采样的。 LINE (Tang 等人, 2015) 和 node2vec (Grover & Leskovec, 2016) 使用更复杂的随机游走或广度优先搜索方案扩展 DeepWalk。 然而，对于所有这些方法，都需要包括随机游走生成和半监督训练的多步骤管道，其中每个步骤都必须单独优化。 Planetoid (Yang 等人, 2016) 通过在学习嵌入的过程中注入标签信息来缓解这一问题。

4.2 图上的神经网络

之前在 Gori 等人 (2005) 中介绍过在图上运行的神经网络； Scarselli 等人 (2009) 作为循环神经网络的一种形式。 他们的框架需要重复应用收缩图作为传播函数，直到节点表示达到稳定的固定点。 后来，Li 等人 (2016) 通过将循环神经网络训练的现代实践引入到原始图神经网络框架中，缓解了这一限制。 Duvenaud 等人 (2015) 引入了图上的类卷积传播规则和图级分类方法。 他们的方法需要学习特定于节点度的权重矩阵，该矩阵不能扩展到具有宽节点度分布的大图。 相反，我们的模型每层使用一个权重矩阵，并通过邻接矩阵的适当归一化来处理不同的节点度（请参见第 3.1 节）。

Atwood & Towsley (2016) 最近介绍了一种使用基于图的神经网络进行节点分类的相关方法。 他们报告 $𝒪(N^2)$复杂性，限制了可能的应用范围。 在另一个相关模型中，Niepert 等人 (2016) 将图本地转换为序列，然后输入传统的一维卷积神经网络，这需要在预处理步骤中定义节点排序。

我们的方法基于谱图卷积神经网络，在 Bruna 等人 (2014) 中引入，后来由 Defferrard 等人 (2016) 扩展为快速局部卷积。 与这些工作相反，我们在这里考虑在规模明显更大的网络中进行传导节点分类的任务。 我们表明，在这种情况下，可以将许多简化（参见第 2.2 节）引入到 Bruna 等人 (2014) 和 Defferrard 等的原始框架中。人 (2016) 提高大规模网络的可扩展性和分类性能。

5实验

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

5.1数据集

我们密切关注Yang等人(2016)中的实验设置。 数据集统计信息总结在表1中。 在引文网络数据集中——Citeseer、Cora 和 Pubmed （Sen 等人，2008）——节点是文档，边是引文链接。 标签率表示用于训练的标记节点数除以每个数据集中的节点总数。 NELL (Carlson 等人, 2010; Yang 等人, 2016) 是从知识图谱中提取的二分图数据集，有 55,864 个关系节点和 9,891 个实体节点。

表格1： 数据集统计，参见Yang等人(2016)。

Dataset	Type	Nodes	Edges	Classes	Features	Label rate
Citeseer	Citation network	3,327	4,732	$6$	3,703	$0.036$
Cora	Citation network	2,708	5,429	$7$	1,433	$0.052$
Pubmed	Citation network	19,717	44,338	$3$	500	$0.003$
NELL	Knowledge graph	65,755	266,144	$210$	5,414	$0.001$

引文网络

我们考虑三个引文网络数据集：Citeseer、Cora 和 Pubmed (Sen 等人，2008)。 数据集包含每个文档的稀疏词袋特征向量以及文档之间的引用链接列表。 我们将引用链接视为（无向）边并构造一个二元对称邻接矩阵 $A$。 每个文档都有一个类标签。 对于训练，我们每个类仅使用 20 个标签，但全部是特征向量。

内尔

NELL是从（Carlson等人，2010）中介绍的知识图谱中提取的数据集。 知识图是一组通过有向、标记的边（关系）连接的实体。 我们遵循Yang等人(2016)中描述的预处理方案。 We assign separate relation nodes $r_1$ and $r_2$ for each entity pair $(e_1,r,e_2)$ as $(e_1,r_1)$ and $(e_2,r_2)$. 实体节点由稀疏特征向量描述。 我们通过为每个关系节点分配唯一的 one-hot 表示来扩展 NELL 中的特征数量，从而有效地为每个节点生成 61,278 维的稀疏特征向量。 这里的半监督任务考虑了训练集中每个类只有一个标记示例的极端情况。 如果节点 $i$ 和 $j$ 之间存在一条或多条边，我们将设置条目 $A_{ij}=1$ 从该图中构建二进制对称邻接矩阵。

随机图

我们模拟各种大小的随机图数据集进行实验，测量每个时期的训练时间。 对于具有 $N$ 个节点的数据集，我们创建一个分配 $2N$ 个边的随机图均匀随机。 我们将单位矩阵 $I_N$ 作为输入特征矩阵 $X$，从而隐式地采用无特征方法，其中模型仅获知每个节点的身份，由唯一的 one-hot 向量指定。 我们添加虚拟标签 $Y_i=1$对于每个节点。

5.2实验设置

除非另有说明，我们按照 3.1 节中的描述训练一个两层 GCN，并在 1,000 个标记示例的测试集上评估预测准确性。 我们在附录 B 中提供了使用最多 10 层的更深模型的额外实验。 我们选择与 Yang 等人 (2016) 中相同的数据集分割，并附加 500 个标记示例的验证集用于超参数优化（所有层的丢弃率、第一个 GCN 层的 L2 正则化因子和数量）隐藏单元）。 我们不使用训练的验证集标签。

对于引文网络数据集，我们仅在 Cora 上优化超参数，并为 Citeseer 和 Pubmed 使用相同的参数集。 我们使用 Adam (Kingma & Ba, 2015) 对所有模型进行最多 200 轮训练（训练迭代），学习率为 $0.01$ 并提前停止窗口大小$10$，即如果验证损失在连续 10 个时期内没有减少，我们就停止训练。 我们使用 Glorot & Bengio (2010) 中描述的初始化来初始化权重，并相应地对输入特征向量进行（行）归一化。 在随机图数据集上，我们使用 32 个单位的隐藏层大小并省略正则化（即既不丢失也不进行 L2 正则化）。

5.3基线

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

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

最后，我们与 Planetoid (Yang 等人，2016) 进行比较，我们总是选择他们表现最好的模型变体（传导与感应）作为基线。

6结果

6.1 半监督节点分类

结果总结于表2中。 报告的数字表示分类准确性的百分比。 对于 ICA，我们报告了 100 次随机节点排序运行的平均准确度。 所有其他基线方法的结果均取自 Planetoid 论文（Yang 等人，2016）。 Planetoid* 表示论文中提出的变体中各个数据集的最佳模型。

表2： 分类准确度结果摘要（百分比）。

Method	Citeseer	Cora	Pubmed	NELL
ManiReg [3]	$60.1$	$59.5$	$70.7$	$21.8$
SemiEmb [28]	$59.6$	$59.0$	$71.1$	$26.7$
LP [32]	$45.3$	$68.0$	$63.0$	$26.5$
DeepWalk [22]	$43.2$	$67.2$	$65.3$	$58.1$
ICA [18]	$69.1$	$75.1$	$73.9$	$23.1$
Planetoid* [29]	$64.7$ (26s)	$75.7$ (13s)	$77.2$ (25s)	$61.9$ (185s)
GCN (this paper)	$\mathbf{70.3}$ (7s)	$\mathbf{81.5}$ (4s)	$\mathbf{79.0}$ (38s)	$\mathbf{66.0}$ (48s)
GCN (rand. splits)	$67.9\pm 0.5$	$80.1\pm 0.5$	$78.9\pm 0.7$	$58.4\pm 1.7$

我们进一步报告了我们的方法（包括）收敛（在括号中）之前的挂钟训练时间（以秒为单位）。 验证误差的评估）和小行星。 对于后者，我们使用了作者提供的实现 并在与我们的 GCN 模型相同的硬件（带有 GPU）上进行训练。 我们在与 Yang 等人 (2016) 中相同的数据集分割上训练和测试我们的模型，并报告随机权重初始化的 100 次运行的平均准确度。 对于 Citeseer、Cora 和 Pubmed，我们使用了以下超参数集：0.5（辍学率）、$5\cdot {10}^{-4}$（L2 正则化）和$16$（隐藏单元数）；对于 NELL，我们使用了 0.1（辍学率）、$1\cdot {10}^{-5}$（L2 正则化）和$64$（隐藏单元数）。

此外，我们报告了我们的模型在 10 个随机抽取的数据集分割上的性能，这些分割的大小与 Yang 等人 (2016) 中的大小相同，用 GCN (rand. 分裂）。 在这里，我们以百分比报告测试集预测准确性的平均值和标准误差。

6.2传播模型的评估

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

表3： 传播模型的比较。

Description		Propagation model	Citeseer	Cora	Pubmed
Chebyshev filter (Eq. 5)	$K=3$		$69.8$	$79.5$	$74.4$
	$K=2$		$69.6$	$81.2$	$73.8$
$1^{\text{st}}$-order model (Eq. 6)		$X{\mathrm{\Theta }}_0+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}X{\mathrm{\Theta }}_1$	$68.3$	$80.0$	$77.5$
Single parameter (Eq. 7)		$(I_N+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}})X\mathrm{\Theta }$	$69.3$	$79.2$	$77.4$
Renormalization trick (Eq. 8)		${\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}X\mathrm{\Theta }$	$\mathbf{70.3}$	$\mathbf{81.5}$	$\mathbf{79.0}$
$1^{\text{st}}$-order term only		$D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}X\mathrm{\Theta }$	$68.7$	$80.5$	$77.8$
Multi-layer perceptron		$X\mathrm{\Theta }$	$46.5$	$55.1$	$71.4$

6.3 每个 Epoch 的训练时间

图2： 随机图每个时期的挂钟时间。 (*) 表示内存不足错误。

在这里，我们报告了模拟随机图上 100 个 epoch 的每个 epoch 的平均训练时间（前向传递、交叉熵计算、后向传递）的结果，以秒挂钟时间为单位。 有关这些实验中使用的随机图数据集的详细说明，请参阅第 5.1 节。 我们比较 GPU 和仅 CPU 实现上的结果 在 TensorFlow (Abadi 等人, 2015) 中。 图2总结了结果。

7讨论

7.1半监督模型

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

我们进一步证明，与传统的模型相比，所提出的重整化传播模型（方程8)不仅提高了效率（更少的参数和操作，例如乘法或加法），而且在许多数据集上提供了更好的预测性能。 naïve $1^{\text{st}}$阶模型（方程6)或使用切比雪夫多项式的高阶图卷积模型（等式5)。

7.2 局限性和未来的工作

在这里，我们描述了当前模型的一些局限性，并概述了如何在未来的工作中克服这些局限性。

内存要求

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

有向边和边特征

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

限制性假设

通过2节中介绍的近似，我们隐式地假设局部性（依赖于$K^{\text{th}}$阶邻域具有 $K$ 层的 GCN），并且自连接与相邻节点的边具有同等重要性。 不过，对于某些数据集来说，在 $\tilde{A}$ 的定义中引入一个权衡参数 $\lambda$ 可能是有益的：

$$\tilde{A}=A+\lambda I_N.$$ (11)

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

8结论

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

致谢

我们要感谢 Christos Louizos、Taco Cohen、Joan Bruna、Zhilin Yang、Dave Herman、Pramod Sinha 和 Abdul-Saboor Sheikh 进行的有益讨论。 这项研究由 SAP 资助。

附录A与Weisfeiler-Lehman算法的关系

理想情况下，图结构数据的神经网络模型应该能够学习图中节点的表示，同时考虑节点的图结构和特征描述。 1-dim Weisfeiler-Lehman (WL-1) 算法 （Weisfeiler & Lehmann，1968）：

输入： 初始节点着色 $(h_1^{(0)},h_2^{(0)},\mathrm{\dots },h_N^{(0)})$

输出： 最终节点着色 $(h_1^{(T)},h_2^{(T)},\mathrm{\dots },h_N^{(T)})$

t $\leftarrow$ 0;

重复

对于 $v_i\mathrm{\in }𝒱$ 做0>

$h_i^{(t+1)}\leftarrow \mathrm{hash}\left({\sum }_{j\in {𝒩}_i}{h}_j^{(t)}\right)$；

$t\leftarrow t+1$;

直到 达到稳定的节点着色；

算法1 WL-1 算法（Weisfeiler & Lehmann，1968）

Here, $h_i^{(t)}$ denotes the coloring (label assignment) of node $v_i$ (at iteration $t$) and ${𝒩}_i$ is its set of neighboring node indices (irrespective of whether the graph includes self-connections for every node or not). $\mathrm{hash}(\cdot )$ 是一个哈希函数。 有关 WL-1 算法的深入数学讨论，请参阅 Douglas (2011)。

我们可以将算法 1 中的哈希函数替换为具有可训练参数的神经网络层状可微函数，如下所示：

$$h_i^{(l+1)}=\sigma \left(\sum _{j\in {𝒩}_i}\frac{1}{c_{ij}}{h}_j^{(l)}{W}^{(l)}\right),$$ (12)

其中 $c_{ij}$ 是适当选择的边缘归一化常数 $(v_i,v_j)$。 Further, we can take $h_i^{(l)}$ now to be a vector of activations of node $i$ in the $l^{\text{th}}$ neural network layer. $W^{(l)}$ 是一个层 -具体权重矩阵和 $\sigma (\cdot )$ 表示可微的非线性激活函数。

选择 $c_{ij}=\sqrt{d_i{d}_j}$、其中 $d_i=|{𝒩}_i|$ 表示节点 $v_i$ 的度数、我们以向量形式恢复图卷积网络 (GCN) 模型的传播规则（见公式2).

宽松地说，这使我们能够将 GCN 模型解释为图上 1 维 Weisfeiler-Lehman 算法的可微分和参数化泛化。

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

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

$$Z=\tanh \left(\widehat{A}\tanh \left(\widehat{A}\tanh \left(\widehat{A}X{W}^{(0)}\right)W^{(1)}\right)W^{(2)}\right),$$ (13)

权重矩阵 $W^{(l)}$ 已初始化随机使用 Glorot & Bengio (2010) 中描述的初始化。 $\widehat{A}$、$X$ 和 $Z$ 的定义如 3.1

我们将此模型应用于 Zachary 的空手道俱乐部网络（Zachary，1977）。 该图包含 34 个节点，由 154 条（无向且未加权）边连接。 每个节点都由四个类别之一进行标记，这些类别是通过基于模块化的聚类（Brandes等人，2008）获得的。 有关说明，请参见图2(a)。

(a) 空手道俱乐部网络

(b) 随机权重嵌入

图3： 左：Zachary 的空手道俱乐部网络（Zachary，1977），颜色表示通过基于模块化的聚类获得的社区（Brandes 等人，2008）。 右：从未经训练的 3 层 GCN 模型（方程 13)获得的嵌入，并将随机权重应用于空手道俱乐部网络。 在电脑屏幕上观看效果最佳。

我们采用无特征方法，设置 $X=I_N$ ，其中 $I_N$ 是 $N$ 乘 $N$ 的特征矩阵。 $N$ 是图中的节点数。 请注意，节点是随机排序的（即排序不包含信息）。 此外，我们选择隐藏层维度 $4$ 和二维输出（以便输出可以立即在二维图中可视化）。

图2(b)显示了从应用于空手道俱乐部网络的未经训练的GCN模型获得的节点嵌入（输出$Z$)的代表性示例。 这些结果与 DeepWalk (Perozzi 等人, 2014) 获得的嵌入相当，后者使用更昂贵的无监督训练程序。

A.2 半监督节点嵌入

在这个将 GCN 应用于空手道俱乐部网络的简单示例中，观察嵌入在半监督分类任务训练期间的反应非常有趣。 这样的可视化（见图4)提供了关于 GCN 模型如何利用图结构（以及从后面层的图结构中提取的特征）来学习对分类任务。

我们考虑以下半监督学习设置：我们在模型顶部添加一个 softmax 层（等式 13)，并且每个类仅使用一个标记示例（即总共 4 个标记示例）进行训练节点）。 我们使用 Adam (Kingma & Ba, 2015) 进行 300 次训练迭代，交叉熵损失的学习率为 $0.01$。

图4显示了节点嵌入在多次训练迭代中的演变。 该模型成功地基于最少的监督和图结构来线性分离社区。 完整训练过程的视频可以在我们的网站。

(a)迭代 25

(b)迭代 50

(c) 迭代 75

(d) 迭代 100

(e) 迭代 200

(f)迭代 300

图4： 经过多次半监督训练迭代后，从 GCN 模型获得的空手道俱乐部网络节点嵌入的演变。 颜色表示等级。 训练期间提供标签的节点（每类一个）会突出显示（灰色轮廓）。 节点之间的灰色链接表示图的边。 在电脑屏幕上观看效果最佳。

附录B模型深度实验

在这些实验中，我们研究了模型深度（层数）对分类性能的影响。 我们报告了使用所有标签对 Cora、Citeseer 和 Pubmed 数据集 （Sen 等人，2008） 进行 5 倍交叉验证实验的结果。 除了标准 GCN 模型（等式2)之外，我们还报告了模型变体的结果，其中我们使用隐藏层之间的残差连接（He等人，2016）通过使模型能够继承前一层输入的信息，促进更深层次模型的训练：

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

在每个交叉验证分割中，我们使用 Adam 优化器 (Kingma & Ba, 2015) 训练 400 个 epoch（没有提前停止），学习率为 $0.01$。 其他超参数选择如下：0.5（丢弃率，第一层和最后一层），$5\cdot {10}^{-4}$（L2 正则化，第一层）、16（每个隐藏层的单元数）和 0.01（学习率）。 结果总结在图5中。

图5： 模型深度（层数）对分类性能的影响。 标记表示 5 倍交叉验证的平均分类精度（训练与测试）。 阴影区域表示标准误差。 我们展示了标准 GCN 模型（虚线）和隐藏层之间添加残差连接 （He 等人，2016） 的模型（实线）的结果。

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