论文 | 图网络理论之Deeper Insights into GCN

新学期！VTS三只小猪继续冲鸭！

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

AAAI2018

*文章总体思路：1. 证明GCN实际上是一种拉普拉斯平滑 ——> 所以深层GCN会造成过度平滑的问题，使结点特征变得不可区分 ——> 但浅层GCN也有问题，在半监督学习中标签很少的情况下无法将标签传播到整个图中 ——> 2. 提出协同训练和自训练

摘要

本文对GCN模型进行了深入的研究，并解决了它的基本局限性：

1. 证明了GCN模型的图卷积实际上是拉普拉斯平滑（Laplacian smoothing）的一种特殊形式，这是GCN工作的关键原因，但它也带来了由过多卷积层导致的过度平滑（over-smoothing）的潜在问题。

2. 为了克服浅层结构的GCN模型的局限性，本文提出了协同训练（co-training）和自训练（self-training）两种方法来训练GCN。

本文的方法在学习中显著提高了GCN，只使用很少的标签，并且免除了它们需要额外的标签来进行验证。实验做的不错！

1. 文章简介

GCN模型过深存在的问题 本文证明了GCN模型的图卷积只是拉普拉斯平滑的一种特殊形式，它混合了节点及其邻近点的特征。平滑操作使同一簇中的结点特征相似，从而大大简化了分类任务，这是GCN工作如此出色的关键原因。然而，它也带来了过度平滑的潜在担忧。如果一个GCN有很多卷积层，输出特征可能会过度平滑，不同簇的结点可能变得不可区分。在只有几个卷积层的小数据集上，特征混合发生得很快，如图2所示。此外，向GCN添加更多的层将使其更难训练。

图2 空手道俱乐部网络的结点嵌入（1、2、3、4、5层GCN）

GCN模型过浅存在的问题 浅层GCN模型（如Kipf和Welling 2017中使用的两层GCN）有其自身的局限性。除了需要许多额外的标签来进行验证外，它还受到卷积核的局部特性的影响。当只给出很少的标签时，一个较浅的GCN就不能有效地将标签传播到整个数据图中。如图1所示，随着训练规模（*有标签样本占比）的缩小，GCN的性能会迅速下降，即使是有500个附加标签进行验证的GCN。

图1 四种模型在Cora数据集上的性能比较

为了克服这一局限，充分发挥GCN模型的潜能，本文提出了一种协同训练（co-training）方法和一种自训练（self-training）方法来训练GCN。通过将一个GCN与一个随机游走模型（random walk）进行联合训练，后者可以在探索全局图拓扑中补充前者。通过对GCN的自训练，可以利用其特征提取能力来克服其局限性。将协同训练和自训练方法结合起来，可以大大改进具有极少标签的半监督学习的GCN模型，并且免除了它需要额外的标签数据进行验证的要求。如图1所示，本文方法大幅度完胜GCN。

简而言之，本文的主要创新点是：1）对半监督学习的GCN模型提出了新的见解和分析；2）提出了改进半监督学习的GCN模型的解决方案。

3. 分析

尽管GCN模型具有良好的学习性能，但其半监督学习的机制尚不明确。本节将更详细地介绍GCN模型，分析其工作的原因，并指出其局限性。

3.1 GCN为何有效

*本节证明图卷积是一种特殊形式的拉普拉斯平滑。

拉普拉斯平滑 考虑一层GCN，包括两步：

1）对X进行图卷积生成新的特征矩阵Y：

$Y=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X$ (8)

2）将新的特征矩阵Y输入全卷积层。显然，图卷积是关键。

那就让我们好好看看图卷积。假设每个结点都加上自循环，则新图的邻接矩阵为 $\tilde{A} =A+I$ .输入特征每个通道上的拉普拉斯平滑定义为：

$\hat{\textbf{y}} _i=(1-\gamma)\textbf{x}_i+\gamma\sum_j\frac{\tilde{a}_{ij} }{d_i}\textbf{x}_j$ , (for $1\leq i\leq n$ ). (9)

其中 $0<\gamma\leq1$ 是控制当前结点特征与其相邻特征之间权重的参数。将拉普拉斯平滑写成矩阵形式：

$\hat{Y} =X-\gamma\tilde{D}^{-1}\tilde{L} X=(I-\gamma\tilde{D}^{-1}\tilde{L} )X$ (10)

其中， $\tilde{L}= \tilde{D}-\tilde{A}$ . 令 $\gamma=1$ ，则有 $\hat{Y} =\tilde{D}^{-1}\tilde{A} X$ ，这是拉普拉斯平滑的标准形式。

若将归一化拉普拉斯 $\tilde{D}^{-1}\tilde{L}$ 替换为对称归一化拉普拉斯 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ ，令 $\gamma=1$ ，则 $Y=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X$ ，也就是式8中的图卷积。因此，我们称图卷积是拉普拉斯平滑的一种特殊形式——对称拉普拉斯平滑。注意，这里的平滑仍然包括当前结点特征，因为每个结点都加上了自循环，是自己的邻居结点。

拉普拉斯平滑将结点的新特征计算为其自身及其相邻结点的加权平均值。由于同一簇中的结点往往是密集连接的，平滑处理使它们的特征相似，这使得后续的分类任务更加容易。如表1所示，仅应用一次平滑就可以获得巨大的性能增益。

多层结构 从表1也可以看出，2层FCN仅比1层FCN略有改善，但2层GCN比1层GCN有较大幅度的改善。这是因为在第一层的激活上再次应用平滑，使得同一簇中结点的输出特征更加相似，从而进一步简化了分类任务。

表1 FCN和GCN比较

3.2 GCN何时失效

*本节证明深层图卷积即过度平滑，会使结点特征收敛到相同的值。

一个GCN中应该包括多少个卷积层？当然不是越多越好。一方面，多层GCN很难训练。另一方面，重复应用拉普拉斯平滑可能会混合来自不同簇的结点特征，使它们无法区分，如图2所示。

下面将证明通过多次重复应用拉普拉斯平滑，图中每个连通分支内的结点特征将收敛到相同的值。对于对称拉普拉斯平滑，它们将收敛到与结点度的平方根成比例。

基于上述定理，过度平滑会使特征难以区分，影响分类精度，并且深层GCN会使得网络难以训练。然而由于图卷积是一个局部滤波器——相邻特征向量的线性组合，浅层GCN不能充分地将标签信息传播到只有几个标签的整个图中。如图1所示，随着训练规模的缩小，GCN的性能（有或无验证）会迅速下降。事实上，GCN的准确度下降速度远远快于label propagation的准确度。由于label propagation只使用图信息，而GCN同时使用结构和结点特性，因此它反映了GCN模型在探索全局图结构方面的不足。

在（kipf和welling 2017）中，GCN模型的另一个问题是，它需要一个额外的验证集，用于提前终止训练，这是使用验证集的预测精度进行模型选择。如果我们在不使用验证集的情况下对训练数据进行GCN优化，则性能将显著下降。如图1所示，未经验证的GCN的性能比经验证的GCN明显下降。在（kipf和welling 2017）中，作者使用了另外一组500个标记数据进行验证，这远远超过了训练数据的总数。这当然是不可取的，因为它破坏了半监督学习的目的。此外，它使得将GCN与其他方法进行比较变得不公平，因为label propagation等其他方法可能根本不需要验证数据。

4. 方法

总结GCN模型的优缺点。优点：1）图卷积-拉普拉斯平滑有助于简化分类问题；2）多层神经网络是一个强大的特征提取工具。缺点：1）图卷积是一种局域滤波器，在标签数据较少的情况下性能不理想；2）神经网络需要大量的标签数据进行验证和模型选择。

*本节提出的方法旨在解决浅层GCN在半监督学习中标签很少的情况下无法将标签传播到整个图中的问题，不依靠加深网络的方法，而是依靠扩大标记数据的方法。

4.1 用随机游走模型协同训练GCN

本文提出将随机游走模型与GCN协同训练，因为随机游走可以探索全局图结构，这是对GCN模型的补充。首先使用随机游走模型来找到最有信心的结点——每个类的有标签结点的最近邻点，然后将它们添加到标签集以训练GCN。与（kipf和welling 2017）不同，我们直接优化了训练集中GCN的参数，无需额外的标记数据进行验证。

我们选择使用部分吸收（partially absorbing）随机游走（Parwalks）作为我们的随机游走模型。部分吸收随机游走是一个二阶马尔可夫链，在每个状态下都有部分吸收。通过适当的吸收设定，吸收概率可以很好地捕捉到全局图结构。重要的是，通过求解一个简单的线性系统，可以闭式计算吸收概率，并且可以通过随机游走采样或在结点中心图的顶部放大来快速近似（？）。

扩展训练集的算法由算法1所示。首先计算归一化吸收概率矩阵 $P=(L+\alpha\Lambda)^{-1}$ ( $\Lambda$ 的选择可能取决于数据). $P_{i,j}$ 表示从结点i被结点j吸收的随机游走概率，也就是i和j属于同一种类的可能性。其次，计算结点属于k类的置信度。将标记的结点划分为S1，S2，…，其中Sk表示k类的标记数据集。对于每个种类k，计算置信度向量 $\textbf{p}=\sum_{j\in S_k}P_{:,j}$ . 最后，找到t个最有信心的结点，并将它们添加到带有标签k的训练集中，以训练GCN。

4.2 自训练GCN

另一种让GCN看到更多训练样本的方法是自训练GCN。具体来说，首先用给定的标签训练一个GCN，然后通过比较SoftMax分数，选出每个类中最有信心的预测，并将它们添加到标签集。然后，继续使用扩展标签集对GCN进行训练，使用预训练的GCN作为初始化。如算法2所示。

协同训练和自训练相结合 为了提高标签的多样性并训练一个更强大的分类器，建议将协同训练和自训练相结合。具体来说，使用随机游走和GCN本身发现的最有信心的预测来扩展标签集，然后使用扩展的标签集继续训练GCN，这种方法称为“Union”。为了找到更准确的标签添加到标签集，建议添加随机游走和GCN都发现的最有信心的预测，这种方法称为“Intersection”。

注意，我们在扩展标签集上优化所有方法，而不需要任何额外的验证数据。只要扩展的标签集包含足够的正确标签，我们的方法就可以训练出一个良好的GCN分类器。但训练一个GCN需要多少标记数据呢？建设GCN层数为 $\tau$ ，基础图的平均度为 $\hat{d}$ ,通过求解 $\hat{d} ^{\tau}*\eta \approx n$ 来估计标记数量 $\eta=|V_l|$ .这背后的基本原理是估计一个具有τ层的GCN需要多少标签来传播它们以覆盖整个图。

5. 实验

本文在三个常用的引文网络上进行实验：citeseer、cora和pubmed。在每个数据集中，文档都由一袋字特征向量来描述，也就是说，一个0/1值的向量表示某个字的缺失/存在。文档之间的引用链接由0/1值邻接矩阵描述。用于测试的数据集由（Yang、Cohen和Salakhuttdinov，2016）和（Kipf和Welling，2017）的作者提供。

对于ParWalks，设定 $\Lambda=I,\alpha=10^{-6}$ ，对于GCN，设定和(Kipf and Welling 2017)相同：a learning rate of 0.01, 200 maximum epochs, 0.5 dropout rate, 5 × 10^{−4} L2 regularization weight, 2 convolutional layers, and 16 hidden units, which are validated on Cora by Kipf and Welling.

6. 总结

了解深层神经网络对于实现其在实际应用中的全部潜能至关重要。本文有助于理解GCN模型及其在半监督分类中的应用。我们的分析不仅揭示了GCN模型的机制和局限性，而且提出了克服其局限性的新解决方案。在未来的工作中，我们计划开发新的卷积滤波器，它与深层结构兼容，并利用先进的深层学习技术来提高GCN在更多基于图的应用中的性能。

文章标*处为全世界最乖巧的小猪注.