论文笔记DeeperInsightsintoGraphConvolutionalNetworksforSemiSupervisedLearning

论文题目&＃xff1a;Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning(AAAI 2018)
论文链接&＃xff1a;arxiv

GCN在卷积层中很好地聚合了局部结点特征和图拓扑结构信息&＃xff0c;但它的机制并不清楚&＃xff08;类似一个黑匣子&＃xff09;&＃xff0c;它仍然需要大量的标记数据来验证和选择模型。

在本文中&＃xff0c;我们对GCN模型进行了深入的研究&＃xff0c;并指出了它的基本的局限性。首先&＃xff0c;我们 ** 证明了GCN模型的图卷积实际上是拉普拉斯平滑的一种特殊形式&＃xff0c;这是GCN为什么能工作的关键原因&＃xff0c;但它也带来了多层卷积层的过平滑问题。**其次&＃xff0c;为了克服浅层结构GCN模型的局限性&＃xff0c;我们提出了训练生成GCN的联合训练和自训练&＃xff08;co-training and self-training&＃xff09;两种方法。我们的方法极大地提高了GCN的学习能力&＃xff0c;并且使它们不需要额外的标签进行验证。

许多研究表明&＃xff0c;** 如果使用得当&＃xff0c;在训练中利用未标记数据可以显著提高学习&＃xff08;此处应该指的是半监督学习&＃xff0c;尤其是带标签样本较少的情况&＃xff09;的准确性&＃xff08;Zhu和Goldberg&＃xff0c;2009&＃xff09;**。其关键问题是最大限度地有效利用未标记数据的结构和特征信息。由于深度神经网络强大的特征提取能力和最近所取得的成功&＃xff0c;已经有一些基于神经网络模型的半监督学习的成功尝试。

2016年提出的图卷积神经网络&＃xff08;GCNNs&＃xff09;是将处理欧氏数据的强大卷积神经网络&＃xff08;CNNs&＃xff09;推广到处理非欧氏数据图结构数据的成功尝试。2017年Kipf和Welling提出了一种简化的GCNN&＃xff0c;称为图卷积网络&＃xff08;GCN&＃xff09;&＃xff0c;并将其应用于半监督分类。GCN模型可自然地聚合了图结构数据的图拓扑结构信息和结点特征属性&＃xff0c;在某些基准上明显优于许多最新的方法。然而&＃xff0c;它也面临着其他基于神经网络的模型所面临的类似问题&＃xff1a;半监督学习的GCN模型的工作机制尚不清楚&＃xff0c;训练GCN仍然需要大量的标记数据进行参数整定和模型选择&＃xff0c;从而影响了半监督学习的效果。

在本文中&＃xff0c;我们揭开了用于半监督学习的GCN模型的神秘面纱。特别地&＃xff0c;我们** 证明了GCN模型中的图卷积只是拉普拉斯平滑的一种特殊形式&＃xff08;Laplacian smoothing&＃xff09;&＃xff0c;它聚合了顶点及其几阶邻居&＃xff08;几跳范围之内的邻居结点&＃xff09;的特征**。平滑操作使同一簇中顶点的特征相似&＃xff0c;大大简化了分类任务&＃xff0c;这是GCNs能够取得良好效果的关键原因。然而它也带来了过度平滑的潜在问题 。** 在有许多卷积层的深层GCN模型中&＃xff0c;输出特征可能会过度平滑&＃xff0c;不同簇的顶点可能无法区分** 。 如图2所示&＃xff0c;即使只有少量卷积层的GCN模型在小数据集上&＃xff0c;这种混合&＃xff08;过平滑&＃xff09;仍然发生得很快。此外&＃xff0c;深层GCN相对于浅层模型更难训练。

然而&＃xff0c;** 一个较浅的GCN模型&＃xff0c;如(Kipf and Welling 2017)中使用的双层GCN有其自身的局限性。除了需要许多额外的标签来进行验证之外&＃xff0c;它还受到了卷积滤波器的局部化特性的影响&＃xff08;即两层GCN模型只能聚合两阶邻居的特性&＃xff09;**。当只给出少量的标签时&＃xff0c;浅层GCN不能有效地将标签传播到整个数据图中。如图1所示&＃xff0c;GCNs的性能随着训练规模的缩小而迅速下降&＃xff0c;即使对于有500个额外标签的验证也是如此。

为了克服GCN模型&＃xff08;指浅层的GCN&＃xff09;的局限性&＃xff0c;充分发挥GCN模型的潜力&＃xff0c;本文提出了一种联合训练和自训练的GCN训练方法&＃xff08;在半监督学习中常用的两种方法&＃xff09;。通过与随机游走模型共同训练GCN&＃xff0c;随机游走可以补充GCN对全局图拓扑结构的探索。通过对GCN的自训练方法&＃xff0c;我们可以利用GCN的特征提取能力来克服其局部性。将联合训练和自训练方法相结合&＃xff0c;可以大大改进GCN半监督学习模型&＃xff0c;使其不需要额外的标记数据进行验证&＃xff08;因为某些场景下标签数据很难获得&＃xff09;。如图1所示&＃xff0c;我们的方法大大优于GCNs。

简而言之&＃xff0c;本文的主要创新之处在于&＃xff1a;
1&＃xff09;为用于半监督学习的GCN模型提供新见解和分析&＃xff1b;
2&＃xff09;提出改进半监督学习的GCN模型的解决方案。

基于图的半监督学习是近二十年来的一个热门研究领域。通过利用数据的图结构或流形结构&＃xff0c;可以用很少的标签来学习。许多基于图的半监督学习方法采用聚类假设&＃xff08;Chapelleand Zien 2005&＃xff09;&＃xff1a;假设图上的相邻顶点倾向于共享同一标签&＃xff08;聚类假设是指处在相同聚类&＃xff08;cluster&＃xff09;中的示例有较大的可能拥有相同的标记。根据该假设&＃xff0c;决策边界就应该尽量通过数据较为稀疏的地方&＃xff0c;从而避免把稠密的聚类中的数据点分到决策边界两侧。在这一假设下&＃xff0c;大量未标记示例的作用就是帮助探明示例空间中数据分布的稠密和稀疏区域&＃xff0c;从而指导学习算法对利用有标记示例学习到的决策边界进行调整&＃xff0c;使其尽量通过数据分布的稀疏区域。&＃xff09;。

GCN模型自然地结合了卷积中的图结构和顶点特征&＃xff0c;其中未标记顶点的特征与附近标记顶点的特征混合&＃xff0c;并通过多层网络在图上传播。

尽管GCN模型具有良好的性能&＃xff0c;但其用于半监督学习的机制尚不清楚。在本节中&＃xff0c;我们将更仔细地研究GCN模型&＃xff0c;分析其工作原理&＃xff0c;并指出其局限性

GCN能工作的原因

为了理解为什么GCNs工作得这么好&＃xff0c;我们将它们与最简单的全连接网络(FCNs)进行比较&＃xff0c;后者的分层传播规则是

两者的区别仅有GCN在的迭代公式为AHΘ&＃xff0c;而全连接网络的为HΘ&＃xff0c;邻接矩阵A可为其他归一化矩阵。为了观察图卷积的作用&＃xff0c;我们在每个类别只有有20个标签的Cora分类网络上测试了GCN和FCN的半监督分类性能。结果见表1。令人惊讶的是&＃xff0c;即使是一层GCN其精度也要高于FCN。

拉普拉斯平滑&＃xff1a;为了方便分析&＃xff0c;我们先只考虑一层图卷积网络。它实际上包含两个步骤。1&＃xff09; 通过应用图卷积将结点特征X生成新的特征矩阵Y&＃xff1a;

将新特征矩阵传递到全连接层。显然&＃xff0c;图卷积是性能提升的关键。

接下来对图卷积进行更进一步的分析。假设在图中每个顶点上都加自环&＃xff0c;则结点加上自环的图的邻接矩阵为̃A&＃61;A&＃43;I。而输入特征的每个通道上的拉普拉斯平滑&＃xff08;Taubin 1995&＃xff09;定义为

其中0<γ≤1是一个参数&＃xff0c;用于控制当前顶点的特征与其相邻特征之间的权重。我们可以把拉普拉斯平滑写成矩阵形式


现在&＃xff0c;如果我们用对称正规化的拉普拉斯函数D−1/2LhatD−1/2D^{−1/2}L^{hat}D^{−1/2}D−1/2LhatD−1/2替换正规化的拉普拉斯函数D−1LhatD^{−1}L^{hat}D−1Lhat&＃xff0c;让$\gamma \&＃61;1$&＃xff0c;我们就得到了yhat&＃61;D−1/2LhatD−1/2Xy^{hat} &＃61; D^{−1/2}L^{hat}D^{−1/2}Xyhat&＃61;D−1/2LhatD−1/2X&＃xff0c;这正是等式&＃xff08;8&＃xff09;中的图卷积。因此&＃xff0c;我们把图的卷积称为拉普拉斯平滑的一种特殊形式——对称拉普拉斯平滑。请注意&＃xff0c;这里的平滑仍然包括当前顶点的特征&＃xff0c;因为每个顶点都有一个自环&＃xff0c;并且是自己的邻居。

拉普拉斯平滑算法将一个顶点的新特征Y计算为其自身及其邻域的加权平均值&＃xff0c;由于同一簇中的顶点往往是密集连接的&＃xff0c;平滑使得它们的特征相似&＃xff0c;这使得后续的分类任务变得更加容易。如表1所示&＃xff0c;仅应用一次平滑已经带来了巨大的性能提升。

多层结构: 我们从表1还可以看出&＃xff0c;比较于2层FCN仅比1层FCN略有改善&＃xff0c;而2层GCN比1层GCN有很大幅度的改善。这是因为在第一层的激活函数上再次应用平滑操作&＃xff0c;使得同一簇中顶点的输出特征更加相似&＃xff0c;进一步简化了分类。

When GCNs Fail

我们已经证明了图卷积是一种特殊拉普拉斯平滑。自然的&＃xff0c;我们想知道一个问题是一个GCN模型应该包含多少个卷积层&＃xff1f;当然不是越多越好。一方面&＃xff0c;具有多个层次的GCN很难训练。另一方面&＃xff0c;重复应用拉普拉斯平滑可能会混合来自不同簇的顶点的特征&＃xff0c;使它们无法区分&＃xff08;即过平滑&＃xff09;。下面&＃xff0c;我们使用一个流行的数据集来说明这一点

我们在Zachary的空手道俱乐部数据集上应用不同层数的GCN&＃xff0c;该数据集有两个类别共计34个顶点和78个边。GCN未经训练&＃xff08;未经预训练&＃xff09;&＃xff0c;权重参数随机初始化&＃xff0c;正如&＃xff08;Glorot和Bengio 2010&＃xff09;论文中的实验。隐藏层的维数是16&＃xff0c;输出层的维数是2。隐藏层的维数是16&＃xff0c;输出层的维数是2。每个顶点的特征向量是one-hot向量。每个GCN的输出在图2中以二维空间中的点进行绘制。我们可以观察图卷积&＃xff08;拉普拉斯平滑&＃xff09;对这个小数据集的影响。使用一次平滑&＃xff08;一层图卷积网络&＃xff09;处理后&＃xff0c;不能很好的区分不同类别的点&＃xff08;如图2a所示&＃xff09;。使用两次平滑&＃xff08;两层图卷积&＃xff09;&＃xff0c;不同类别的点分离得比较好。三层至五层的图卷积网络&＃xff0c;结点又变得不可区分&＃xff08;如图2c&＃xff0c;2d&＃xff0c;2e&＃xff09;&＃xff08;即出现了过平滑&＃xff09;。由于这是一个非常小的数据集&＃xff0c;且两个类别之间的顶点有较多的边&＃xff0c;故混合&＃xff08;过平滑&＃xff09;发生得很快。

在下面&＃xff0c;我们将证明**通过多次重复应用拉普拉斯平滑&＃xff08;即堆叠多层图卷积网络&＃xff09;&＃xff0c;图的每个连通分量内的顶点特征将收敛到相同的值。**对于对称拉普拉斯平滑的情况&＃xff0c;它们将收敛到与顶点度的平方根成正比的值。

注意&＃xff0c;由于每个顶点都有一个额外的自环&＃xff0c;在图中没有二部分量。根据上述定理&＃xff0c;过平滑会使不同结点特征变得无法区分&＃xff0c;从而影响分类精度。

上述分析指出了在GCN中堆叠过多卷积层的潜在问题&＃xff08;即可能存在过平滑问题&＃xff09;&＃xff0c;并且一个深层GCN更难训练。故Kipf和Welling使用的GCN仅为2层。然而&＃xff0c;由于图卷积是一个局部滤波器&＃xff0c;是相邻邻域特征&＃xff08;包含结点自身的特征&＃xff09;向量的线性组合&＃xff0c;一个较浅的图卷积网络不能将只有较少标签样本的标签信息充分传播到整个图。如图1所示&＃xff0c;GCN的性能&＃xff08;无论有还是没有验证样本&＃xff09;随着训练规模&＃xff08;带标签样本数量&＃xff09;的缩小而急剧下降。事实上&＃xff0c;GCN的准确度比标签传播的准确度下降得快得多。由于标签传播只使用图信息&＃xff0c;而GCN同时利用结构和顶点特征&＃xff0c;这反映了GCN模型在探索全局图结构方面的不足。

**Kipf和Welling的GCN模型的另一个问题是&＃xff0c;它需要一个额外的验证集来提前停止训练&＃xff0c;这本质上是使用验证集上的预测精度来进行模型选择。**如果我们不使用验证集而是在训练数据上优化GCN&＃xff0c;它的性能将会显著下降。如图1所示&＃xff0c;没有验证的GCN的性能比有验证的GCN下降得更厉害。Kipf和Welling使用了额外的一组500个标记数据进行验证&＃xff0c;这远远超过了训练数据的总数&＃xff0c;这违背了半监督学习的目的。此外&＃xff0c;这使得GCNs与其他方法进行不公平的比较&＃xff0c;因为标签传播算法等其可能根本不需要验证数据。

我们总结了gcn模型的优缺点&＃xff0c;其优点是&＃xff1a;1&＃xff09;图卷积-拉普拉斯平滑有助于使分类问题更容易&＃xff1b;2&＃xff09;多层神经网络是一个强大的特征提取工具。缺点是&＃xff1a;1)图卷积是一种局部滤波器&＃xff0c;在标记数据较少的情况下性能不理想;&＃xff1b;2&＃xff09;神经网络需要大量的标记数据进行验证和模型选择

我们希望充分利用GCN模型的优点&＃xff0c;同时克服它的局限性。这自然导致了协同训练(Blum和Mitchell 1998年)的想法

Co-Train a GCN with a Random Walk Model

我们建议将GCN与随机游走模型共同训练&＃xff0c;因为后者可以探索全局图结构&＃xff0c;这是对GCN模型的补充。 具体的做法是&＃xff1a;我们首先使用随机游走模型寻找最可靠的顶点-每个类别中标记顶点的最近邻居&＃xff0c;然后将它们添加到标签集中以训练GCN。 与&＃xff08;Kipfand Welling 2017&＃xff09;不同&＃xff0c;我们直接在训练集上优化GCN模型参数&＃xff0c;而无需其他标记数据进行验证。

我们选择使用部分吸收随机游动&＃xff08;ParWalks&＃xff09;&＃xff08;Wu et al.2012&＃xff09;作为我们的随机游动模型。部分吸收随机游动是一个二阶马尔可夫链&＃xff0c;在每个状态下都有部分吸收。在&＃xff08;Wu&＃xff0c;Li&＃xff0c;and Chang 2013&＃xff09;中发现&＃xff0c;在适当的吸收设置下&＃xff0c;吸收概率可以很好地捕获全局图结构。重要的是&＃xff0c;吸收概率可以通过求解简单的线性系统以封闭形式计算&＃xff0c;并且可以通过随机游走采样或在顶点中心图引擎上放大来快速近似&＃xff08;Guo等人&＃xff09;。2017).

GCN Self-Training

另一种使GCN“看到”更多训练示例的方法是对GCN进行自我培训&＃xff08;self-train&＃xff09;。具体地说&＃xff0c;我们首先用给定的标签训练一个GCN&＃xff0c;然后通过比较softmax分数来选择每个类最有信心的预测&＃xff0c;并将它们添加到标签集中。然后&＃xff0c;我们继续使用扩展标签集训练GCN&＃xff0c;使用预先训练的GCN作为初始化。算法2对此进行了描述。

GCN发现的最有信心的实例支持与标记数据共享相似&＃xff08;但不相同&＃xff09;的特征。将它们添加到标记集将有助于训练更健壮和准确的分类器。此外&＃xff0c;在图中有许多孤立的小成分&＃xff0c;并且不可能用随机游动来传播标签的情况下&＃xff0c;它补充了联合训练方法。

Combine Co-Training and Self-Training.

到为了提高标签的多样性&＃xff0c;训练出更具鲁棒性的分类器&＃xff0c;我们提出了联合训练和自学习相结合的方法。具体地说&＃xff0c;我们用随机游走和GCN本身找到的可信程度最高的预测来扩展标签集&＃xff0c;然后用扩展的标签集继续训练GCN。我们称这种方法为“联合”。为了找到更准确的标签添加到标签集&＃xff0c;我们还建议添加由random walk和GCN发现的可信程度最高的预测。我们称这种方法为“交集”。

请注意&＃xff0c;我们在扩展的标签集上优化了所有方法&＃xff0c;而不需要任何额外的验证数据。只要扩展的标签集包含足够多的正确标签&＃xff0c;我们的方法就有望训练出一个好的GCN分类器。但是训练GCN需要多少标记数据呢&＃xff1f;假设GCN的层数为$\tau$&＃xff0c;底层图的平均度数为dhatd^{hat}dhat&＃xff0c;我们提出通过求解(dhat)τ∗η≈n(d^{hat})^τ*η≈n(dhat)τ∗η≈n来估计标签数η&＃61;∣Vl∣η&＃61;| V_l |η&＃61;∣Vl​∣的下界&＃xff0c;其基本原理是估计一个具有τ层的GCN需要多少标签才能传播到整个图。