SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

Abstract

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

1、Introduction

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

这里，L0表示图标注部分的监督损失函数，f(.)是类似神经网络中的可微函数，λ是权重系数，X是一个有节点特征向量Xi组成的矩阵。△ = D - A表示无向图的非正则化图拉普拉斯行列式，包括N个节点，边缘，一个邻接矩阵（二进制或者权重）与次数矩阵。式(1)的公式依赖于图中连通节点可能共享同一标签的假设。然而，这种假设可能会限制建模能力，因为图边缘不一定要对节点相似性进行编码，但可能包含其他信息。

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

我们的贡献有两个方面。首先，我们针对直接作用于图上的神经网络模型，介绍了一种简单且表现良好的分层传播规则，并说明了该规则是如何由谱图卷积的一阶近似驱动（Hammond et al., 2011）。其次，我们演示了这种形式的基于图的神经网络模型如何被用于快速和可伸缩的半监督的节点分类。对大量数据集的实验表明，我们的模型在分类精度和效率(以时间衡量)方面都优于目前最先进的半监督学习方法。

2、Fast Approximate Convolutions On Graphs

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

这里是添加自连接的无向图G的邻接矩阵。IN是单位矩阵，与一个特定于层的可训练的权重矩阵。表示激活函数，例如ReLU(.)=max(0,.)。是lth层的激活矩阵；H(0)=X。在下面，我们证明了这种传播规则的形式可以通过图上局部谱滤波器的一阶近似来激发（Hammond et al., 2011; Defferrard et al., 2016）。

2.1 Spectral Graph Convolutions

我们考虑光谱卷曲图定义为信号的乘法（用于每个节点的系数）和一个过滤器由傅里叶域中的参数化，例如：

这里U是矩阵的特征向量归一化图像的拉普拉斯算子,一个对角矩阵的特征值Λ和是x的图像傅里叶变换。我们可以理解gθ是L的特征值函数，例如。评估式（3）是计算复杂度很高的，特征向量矩阵U的乘法复杂度是。此外，对于大型图，首先L的特征分解可能计算复杂度非常高。为了规避这个问题,Hammond et al. (2011)建议在gθ(Λ)可以被截断扩张的近似值为k阶切比雪夫多项式Tk (x)：

重新缩放。λmax表示L最大特征值。现在是切比雪夫系数的矢量。切比雪夫多项式被递归地定义为，这里且。读者可以参考Hammond et al.(2011)对这种近似的深入讨论。

回到我们的定义使用卷积过滤器的信号x ,我们现在有：

这里；这一点很容易得到证实。注意，这个表达式现在是K局部的，因为它是拉普拉斯多项式中的一个K阶多项式，也就是说，它只依赖于离中心节点(K阶邻域)最大K步的节点。计算公式5的复杂度是O(|E|)，即边的数量是线性的。 Defferrard et al.（2016）使用这个k局部卷积在图上定义卷积神经网络。

2.2Layer-Wise Linear Model

因此，通过将式(5)的多个卷积层叠加，可以建立基于图卷积的神经网络模型，每一层后面都是非线性的point-wise。现在，假设我们将逐层卷积运算限制为K = 1(参见公式5)，即一个线性的L的函数，因此是图拉普拉斯谱上的一个线性函数。

这样，我们仍然可以通过叠加多个这样的层来恢复一类丰富的卷积滤波函数，但是我们不局限于Chebyshev多项式等给出的显式参数化。我们直观地期望该模型能够缓解具有非常宽的节点度分布的图(如社交网络、引用网络、知识图和许多其他真实世界的图数据集)的局部邻域结构过拟合问题。此外，对于固定的计算资源，这种分层线性公式允许我们构建更深入的模型，这是一种已知的实践，可以提高在许多领域上的建模能力（He et al., 2016）。

在这之下我们进一步近似的线性公式λmax≈2,我们可以预期,神经网络参数将在规模在训练适应这种变化。在这些近似下，公式5简化为：

式中有两个自由变量与。过滤器参数可以在整个图中共享。这种形式的连续应用滤波器可以有效地对一个节点的k阶邻域进行卷积，其中k是神经网络模型中连续过滤操作或卷积层的个数。在实践中，进一步限制参数的数量来处理过拟合和最小化每层操作的数量(例如矩阵乘法)是有益的。这样就得到了下面的表达式：

式中只有一个参数。注意现在特征值在[0,2]范围内。因此，在深度神经网络模型中重复使用该算子会导致数值不稳定性和爆炸/消失梯度。为了解决这一问题，我们介绍以下重整化技巧：，这里且。我们可以将这个定义推广到一个具有C个输入通道的信号(即每个节点的C维特征向量)和F个滤波器或特征映射如下：

这里现在是矩阵滤波参数，是卷积信号矩阵。这个过滤操作复杂度, 可以有效地实现为一个稠密矩阵的稀疏矩阵的产物。

3、Semi-Supervised Node Classification

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

3.1Example

在下面，我们考虑一个两层的GCN用于半监督节点分类，其图上有一个对称邻接矩阵a(二进制或加权)。在预处理步骤时，我们首先计算。我们的前向模型采用简单形式：

其中，W(0)∈RC×H是H特征映射的隐含层的输入-隐藏权矩阵。W(1)∈RH×F是一个隐藏到输出的权矩阵。按行应用定义为，softmax激活函数。对于半监督的多类分类，我们然后评估所有标记的例子的交叉熵误差：

这里yL是一系列包含标签节点的索引。

神经网络的权重W(0)与W(1)是用梯度下降训练的。在这项工作中，我们在每次训练迭代中使用完整的数据集执行批量梯度下降，这是一个可行的选择，只要数据集适合在内存中。使用稀疏表示a，内存需求是O(|E|)，即边的数量是线性的。训练过程中的随机性是通过dropout引入的（Srivastava et al., 2014）。我们在以后的工作中使用小批量随机梯度下降法来扩展内存效率。

3.2Implementation

在实践中，我们利用TensorFlow（Abadi et al., 2015）实现了一个高效的基于gpu的Eq. 9实现，使用稀疏密集的矩阵乘法。计算公式9的计算复杂度为O(|E|CHF)，即图边数为线性。

4、Related Work

我们的模型从基于图的半监督学习领域和最近对基于图的神经网络的研究中获得灵感。在接下来的文章中，我们将简要介绍这两个领域的相关工作。

4.1Graph-Based Semi-Supervised Learning

近年来，人们提出了大量使用图表示的半监督学习方法，其中大多数可分为两大类:使用某种形式的显式图拉普拉斯正则化方法和基于图嵌入的方法。图拉普拉斯正则化的突出例子包括标签传播(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 & Leskovec, 2016)使用更复杂的随机步长或广度优先搜索方案扩展了DeepWalk。然而，所有这些方法都需要一个多步流水线，其中包括随机步长生成和半监督训练，每一步都需要分别优化。Planetoid (Yang et al.， 2016)通过在学习嵌入的过程中注入标签信息来缓解这一问题。

4.2Neural Networks On Graphs

操作在图上的神经网络在Gori et al.(2005)和Scarselli et al.(2009)中已经作为递归神经网络的一种形式被引入。他们的框架需要反复使用收缩映射作为传播函数，直到节点表示达到一个稳定的定点。后来Li等人(2016)通过在原始的图神经网络框架中引入循环神经网络训练的现代实践，缓解了这一限制。Duvenaud等人(2015)在图上引入了类似卷积的传播规则和图级分类方法。他们的方法需要学习节点度数特定的权重矩阵，这种矩阵不能缩放到具有广泛节点度数分布的大型图。我们的模型每层使用一个权值矩阵，通过适当的邻接矩阵标准化处理不同的节点度(见3.1节)。

最近在Atwood & Towsley(2016)中提出了一种基于图神经网络的节点分类方法。他们报告O(N2)复杂度，限制了可能的应用范围。在另一个相关的模型中，Niepert等人(2016)将图形局部转换成序列，然后将序列输入传统的一维卷积神经网络，这需要在预处理步骤中定义节点排序。

我们的方法基于谱图卷积神经网络，Bruna等人(2014)介绍了该方法，Defferrard等人(2016)对其进行了扩展，使用了快速定域卷积。与这些工作相比，我们在这里考虑的是在大得多的网络中转换节点分类的任务。我们表明，在这种情况下，可以对Bruna等人(2014)和Defferrard等人(2016)的原始框架进行一些简化(参见第2.2节)，从而提高大规模网络中的可伸缩性和分类性能。

5、Experiments

我们进行了大量的实验来测试我们的模型:引用网络中的半监督文档分类、从知识图中提取的二部图中的半监督实体分类、对各种图传播模型的评估以及对随机图的运行时分析。

5.1DataSets

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

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

NELL。 NELL是从(Carlson et al.，2010)中引入的知识图中提取的数据集。知识图是一组实体，它们通过有向标记的边(关系)连接在一起。我们遵循Yang et al.(2016)中描述的预处理方案。我们为每个实体对(e1, r, e2)分配单独的关系节点r1和r2，作为(e1, r1)和(e2, r2)。实体节点由稀疏特征向量描述。我们通过为每个关系节点分配一个唯一的热表示来扩展NELL中的特征数，有效地得到每个节点的61,278个稀疏特征向量。这里的半监督任务考虑的是训练集中每个类只有一个标记示例的极端情况。如果节点i和j之间存在一条或多条边，我们通过设置条目Aij = 1来从图中构造一个二元对称邻接矩阵。

Random graphs****。**** 我们模拟各种大小的随机图数据集，用于测量每个历元的训练时间的实验。对于有N个节点的数据集，我们创建一个随机图，随机分配2N条边。我们将单位矩阵作为输入特征矩阵X，从而隐式地采用一种无特征的方法，其中模型只被告知每个节点的身份，由一个唯一的热向量指定。我们为每个节点添加dummy标签Yi = 1。

5.2Experiment Set-up

除非另有说明，我们按照3.1节的描述训练一个双层GCN，并在一个包含1000个标记示例的测试集上评估预测精度。我们提供额外的实验中使用更深的模型与10层附录b .我们选择相同的数据集分割在Yang et al。(2016)与一个额外的验证组500标记示例超参优化(辍学率为所有层,L2正则化因子第一GCN层和隐藏的数量单位)。我们不使用验证集标签进行训练。

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

5.3 BaseLines

我们对比了Yang等人(2016)的基线方法，即标签传播(LP) (Zhu等人，2003)、半监督嵌入(SemiEmb) (Weston等人，2012)、流型则化(ManiReg) (Belkin等人，2006)和基于skip图嵌入(DeepWalk) (Perozzi等人，2014)。我们忽略了TSVM (Joachims, 1999)，因为它不能扩展到一个数据集中的大量类。

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

最后，我们将其与Planetoid (Yang et al.，2016)进行比较，在Planetoid中，我们总是选择表现最好的模型变体(转导型和诱导型)作为基线。

6、Results

6.1Semi-Supervised Node Classification

结果见表2。报告的数字表示分类精度的百分比。对于ICA，我们报告了100次随机节点排序的平均精度。所有其他基线方法的结果均取自Planetoid论文(Yang et al.，2016)。Planetoid*表示在他们的论文中给出的变量中针对各自数据集的最佳模型。

对于我们的方法(包括验证误差的评估)和Planetoid，我们进一步以秒为单位报告实际训练时间，直到收敛(在括号中)。对于后者，我们使用了由authors3提供的实现，并在与我们的GCN模型相同的硬件(使用GPU)上进行了训练。我们在与Yang等人(2016)相同的数据集分割上训练和测试了我们的模型，并报告了使用随机权重初始化的100次运行的平均准确性。我们使用一下组参数到Citeseer，Cora与Pubmed： 0.5 (dropout rate), 5 · 10×4(L2 regularization) and 16 (number of hidden units); and for NELL: 0.1 (dropout rate), 1 · 10×5(L2 regularization) and 64 (number of hidden units)。

此外，我们报告了我们的模型在10个随机绘制的数据集上的性能，这些数据集的大小与Yang等人(2016)的数据集大小相同，通过GCN 表示(rand，splits)。在这里，我们报告的平均和标准误差的预测精度的测试集差距的百分比。

6.2Evaluation Of Propagation Model

我们比较了我们提出的在引文网络数据集上的每层传播模型的不同变体。我们遵循前一节中描述的实验设置。结果见表3。我们原来的GCN模型的传播模型用重正化技巧表示(in bold)。在所有其他情况下，两个神经网络层的传播模型都替换为传播模型下指定的模型。报告的数字表示使用随机权重矩阵初始化的100次重复运行的平均分类精度。每层的多个变量Θi,我们L2正规化强加于第一层的权重矩阵。

6.3Training Time Per Epoch

在这里，我们报告了模拟随机图上100个epoch的平均训练时间(前向传递、交叉熵计算、后向传递)的结果，以秒为单位测量。这些实验中使用的随机图数据集的详细描述见5.1节。我们比较了在TensorFlow中GPU和仅cpu实现上的结果(Abadi et al.， 2015)。图2总结了结果。

7、Discussion

7.1Semi-Supervised Model

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

我们进一步证明该重整传播模型(Eq8)提供了提高效率(更少的参数和操作,如乘法或加法)和更好的预测性能的数据集相比,原始的1阶模型(Eq6)或高阶图利用切比雪夫多项式卷积模型(Eq5)。

7.2Limitations And Future Work

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

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

Directed edges and edge features****。**** 我们的框架目前自然不支持边缘特性，仅限于无向图(加权的或未加权的)。然而，在NELL上的结果表明，通过将原始有向图表示为带有附加节点的无向二部图来表示原始图中的边，可以同时处理有向边和边缘特征(详细信息参见5.1节)。

Limiting assumptions。 通过第2节中介绍的近似，我们隐式地假定了局部性(对于具有K层的GCN，依赖于K阶邻域)以及自连接与邻近节点的边的同等重要性。对于一些数据集,然而它可能是有益的引入权衡参数λ˜的定义:

该参数现在的作用与典型半监督设置下监督与非监督损失的权衡参数类似(见式1)，但在这里可以通过梯度下降来学习。

8、Conclusion

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