英语原文共 14 页

图卷积网络的半监督分类

摘要

我们提出了一种可扩展的图表结构的方法用于半监督学习，它是基于一种直接作用于图像的卷积神经网络的高效变体。我们通过谱图卷积的一阶局部逼近来刺激我们的卷积架构的选择。我们的模型按照图像边界的数量线性衡量，并学习编码节点的局部图结构和特征的隐藏层表示。在许多实验中，通过引文网络和知识图谱数据集我们证明了我们的方法以显著的优势胜过其他相关的方法。

1 引言

我们考虑了在一个图（比如引文网络）中对节点（比如文档）进行分类的问题，其中标签只对一小部分节点可用。这个问题可以被构建成基于图的半监督学习，其中标签信息通过某种形式的基于图的显式正则比平滑到图像上（Zhuetal.,2003；Zhouetal.,2004；Belkinetal.,2006；Westonetal.,2012），例如通过在损失函数中使用一个图的拉普拉斯正则化项：

其中，表示关于图中标记的部分的监督损失，f(·)可以是一个类神经网络的可微函数，lambda;是一个加权因子，X是一个由节点特征向量X_i构成的矩阵。表示无向图 G = (V, E) 的拉普拉斯的非规范化图像，其中N个v_iisin;V的节点、边界（v_i,v_j）isin;E，一个邻接矩阵A isin; R^Ntimes;N（二进制或加权）以及一个度矩阵。Eq.1的公式依赖于图中所连接的节点可能是共享相同的标签这一假设。然而，这种假设可能会限制建模能力，因为图边不一定要编码节点相似度，但可能会包含额外的信息。

本文我们直接使用神经网络模型f(X,A)对图的结构进行编码，并对所有带有标签的节点在监督目标L₀进行训练，从而避免在损失函数中的基于图的显示正则化。在基于图像的邻接矩阵上对f(·)进行条件设置，可以使得模型从监督损失L₀中分布梯度信息以及使其能够学习有标签和无标签节点的表示形式。

我们的贡献是双重的。首先，我们介绍了一种直接作用于图的神经网络模型的简单且多种机体通用的分层传播规则，并展示了如何从谱图卷积的一阶近似中激发它(Hammond et al., 2011)。其次，我们演示了这种基于图的神经网络模型如何用于图上快速和可扩展的节点的半监督分类。大量数据集中的实验表明，与最先进的半监督学习方法相比，我们的模型在分类精度和效率(以挂钟时间衡量)方面都具有优势。

2 图上的快速近似卷积

在本节中，我们将为一个特定的基于图的神经网络模型f(X, A)提供理论动机，该模型我们会在这篇论文的后面用到。我们考虑一个多层图形卷积网络(GCN)，其传播规则为:

其中，是有着额外的自我连接的无向图的邻接矩阵G。I_N是单位矩阵,和W^(l)是一个分层的可训练的权重矩阵。sigma;(·)表示一个激活函数,如ReLU(·)= max(0·)。H^(l)isin;R^Ntimes;D为第l层的活化矩阵；H (0) = X。在下面，我们证明了可以通过局部光谱滤波器在图中的一阶近似来激发这种传播规则的形式。

2.1谱图卷积

我们考虑将光谱卷积曲线定义为信号xisin;R^N(每个节点的标量)与一个在傅里叶域中参数为theta;isin;R的过滤器g_theta;=diag(theta;)的乘法，也就是说：

其中U是由归一化曲线拉普拉斯算子组成的特征向量所构成的矩阵，其中Lambda;是一个存在特征值的对角矩阵，U^Tx是关于x的傅里叶变换。我们可以将g_theta;理解为一个L也就是g_theta;(Lambda;)的特征值的函数。从计算方面来说计算公式Eq.3是很麻烦的，因为与特征向量矩阵U相乘的结果是O(N²)。此外，对于复杂曲线，首先处理L的特征分解问题可能是代价非常高的。为了规避这个问题，在Hammond等人的研究中建议g_theta;(Lambda;)可以通过一个切比雪夫多项式Tk(x)直到k阶的截断展开来取近似值：

其中。表示L最大的特征值，切比雪夫系数是一个矢量。切比雪夫多项式的递归定义式为，其中、。读者可以参考Hammond等人(2011)对这一近似的深入讨论。

回到我们对于含有信号x的卷积滤波器的定义,我们应有:

其中；很容易发现可以验证。注意，此时这个表达式是K定域的，因为它是拉普拉斯中的一个第K阶的多项式，也就是说，它只取决于距离中心节点(K阶邻域)最大为K阶的节点。计算式（5）的复杂度为，即其边数为线性。Defferrard等人(2016)利用这种K定域卷积去定义图上的卷积神经网络。

2.2 分层线性模型

因此，基于图卷积的神经网络模型可以通过将多个如式5所示的卷积层叠加，每层叠加一个点向非线性来构建。现在，假设我们将分层卷积运算限制为K = 1(参见计算式5)，即一个关于L的线性函数，因此它是拉普拉斯谱图上的一个线性函数。

这样，我们仍可以通过叠加多个这样的层来弥补多阶的卷积滤波函数，但是我们并不局限于例如切比雪夫多项式给出的显式参数化。

对于节点度分布非常广的图(如社交网络、引文网络、知识图和许多其他真实世界的图数据集)所存在的局部邻域结构过拟合问题，我们直观地期望这样的模型可以缓和它。此外，对于确定的计算预算，这种分层线性规划允许我们构建更深入的模型，这种实践可以提高许多领域的建模能力 (He et al.,2016)。

在这种图卷积网络的线性规划下在我们可以进一步地近似lambda;_maxasymp;2,我们可以预期神经网络参数将在练习中依比例适应这种改变。在这些近似下，式5可以简化为:

其中和是两个自由参数。滤波器参数可以在整个图中共享。这种形式滤波器的连续应用有效地卷积了节点的第k阶邻域，其中k是神经网络模型中连续滤波操作或卷积层的个数。

在实践中，进一步限制参数的数量有利于解决过拟合问题，并能够尽可能地减少每层的操作数量(如矩阵乘法)。这样我们就得到了下列的表达式:

其中单参数。注意,在区间[0,2]上有特征值。因此在深度神经网络模型中，重复使用该算子会导致数值不稳定和梯度爆炸/消失。为了减轻这个问题,我们引入以下重正化技巧: ，其中，。

我们可以概括这个定义为一个有着C输入通道(即对于每个节点存在一个C维特征向量)的信号Xisin;R^Ntimes;C和如下的F滤波器或特征图:

其中Theta;isin;R^Ctimes;F是一个矩阵滤波器参数，Zisin;R^Ntimes;F是卷积信号矩阵。这种过滤操作复杂度为,和稠密矩阵一样也可以有效地执行作为稀疏矩阵的结果。

3半监督节点分类

为了在图上进行有效地信息传播，我们引入了一个简单但灵活的模型f(X,A)，现可以回到半监督节点分类的问题。如引言所述，

我们通过对数据X和基础图结构的邻接矩阵A所构成的模型f(X, A)进行调整，可以放宽在基于图的半监督学习中作出的某些典型假设。

当邻接矩阵包含数据X中不存在的信息，例如引文网络中文档之间的引文链接或知识图中的关系时，我们期望这种设置特别有效。整个用于半监督学习的多层图卷积网络模型，其原理如图1所示。

3.1 例子

下面，我们考虑一个两层的图卷积网络，用于对具有对称的邻接矩阵A（二进制或加权）的图进行半监督节点分类。我们首先进行预处理步骤计算。对我们的正向模型采用简单的形式:

图1:左侧:在输出层有C个输入通道和F个特征映射的用于半监督学习的多层图卷积网络(GCN)原理示意图。图的结构(边用黑线表示)在层上共享，标签用表示。右侧:t-分布领域嵌入算法(Maaten amp; Hinton, 2008)在Cora数据集(Sen et al.，2008)上使用5%的标签对一个双层图卷积网络的隐层激活进行可视化。颜色表示文档类别。

这里,W⁽⁰⁾isin;R^Ctimes;H是一个H特征图隐藏层的input-to-hidden权重矩阵。W⁽¹⁾isin;R^Htimes;F是一个hidden-to-output权重矩阵。softmax激活函数按行应用，定义为,其中。对于多种类别的半监督分类，我们这样评估所有有标签的例子的交叉熵误差:

其中是具有标签的节点索引的集合。

使用梯度下降法对神经网络权值W⁽⁰⁾和W⁽¹⁾进行训练。在这项工作中，我们对每个训练迭代使用完整的数据集来批处理梯度下降，只要数据集内存适合这是一个可行的选择。对于A使用稀疏表示，其内存需求为，即边数为线性。通过dropout引入训练过程中的随机性(Srivastava et al.，2014)。我们将小批随机梯度下降的高效存储扩展留到以后的工作中。

3.2 实现

在实践中，我们利用TensorFlow(Abadi et al.，2015)使用稀疏-密集矩阵的乘法高效执行基于GPU的公式（9）。公式（9）的计算复杂度为，即图边数为线性。

4 相关工作

我们的模型灵感来自于基于图形的半监督学习领域，以及最近对图形起作用的神经网络方面的工作。下面，我们将对这两个领域的相关工作进行简要概述。

4.1 基于图形的半监督学习

近年来，提出了大量使用图像表示半监督学习的方法，其中大部分可分为两大类:一类是使用某种形式的显式图拉普拉斯正则化的方法，另一类是图以嵌入为基础的方法。图拉普拉斯正则化的显著例子包括标签传播(Zhu et al.，2003)、流形正则化(Belkin et al.，2006)和深度半监督嵌入(Weston et al.，2012)。

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

4.2图上的神经网络

在Gori等人(2005)的研究中已经引入了对图形进行操作的神经网络;Scarselli等人(2009)则将其作为一种递归神经网络。其框架要求对压缩映射重复应用作为传递函数，直到节点表示达到了一个稳定的不动点。在原有的图神经网络框架中，Li 等人(2016)引入了现代的递归神经网络训练方法，减轻了这一限制。Duvenaud等人(2015)则引入了一种关于图的卷积式传播规则和图级分类方法。他们的方法需要学习节点度特定的权重矩阵，这些矩阵不能缩放到具有宽节点度分布的大型图。而我们的模型则每层使用一个单独的权重矩阵，并通过一个适当的标准化邻接矩阵来处理不同的节点度(参见3.1节)。

最近Atwoodamp;Towsley(2016)提出了一种基于图的神经网络的节点分类相关方法。他们报告复杂度为，对可能的应用范围进行了限制。但是在另一个相关的模型中，Niepert等人(2016)将局部图转换为序列，并将其输入到一个传统的1D卷积神经网络，这需要在预处理步骤中先定义节点的排序。

我们的模型是基于谱图卷积神经网络，该方法在Bruna et al.(2014)中引入，且随后由Defferrard et al.(2016)用快速的局部卷积对其进行了扩展。与这些工作相比，我们在这里考虑的任务是在更大规模的网络中进行传感器节点分类。我们展示了在这种设置下，可以对最初的Bruna et al.(2014)和Defferrard et al.(2016)提出的框架进行一些简化(参见2.2节)，以提高大规模网络中的延展性和分类性能。

5实验

我们通过一系列实验来测试我们的模型:引文网络中的半监督文档分类、知识图中提取的二分图中的半监督实体分类、各种图传播模型的评估以及随机图的运行时间分析。

5.1数据集

我们密切关注Yang et al.(2016)的实验设置。在表1中总结了数据集的统计信息。

在引文网络数据集—— Citeseer、Cora和Pubmed (Sen et al.，2008)中，节点为文献，边缘为引文链接。标签率表示为用于训练的标签节点的数量除以每个数据集中节点的总数。NELL (Carlson et al.，2010;Yang et al.，2016)是从一个包含55864个关系节点和9891个实体节点的知识图中所提取出的二分图数据集。

引文网络 我们考虑三个引文网络数据集:Citeseer、Cora和Pubmed (Sen et al.，2008)。数据集包含每个文档稀疏的bag-of-words特征向量和文档之间的引用链接列表。我们将引文链接视为(无向)边，并构造二元对称邻接矩阵A。每个文档都有一个类别标签。对于训练，所有的特征向量我们每个类别只使用20个标签。

NELL NELL是从(Carlson et al.，2010)里引入的知识图中提取的数据集。知识图是一组实体，它

资料编号：[3606]