基于图卷积网络的半监督分类（Semi-Supervised Cl

作者: 心上那朵云 | 来源:发表于2019-12-21 20:50 被阅读0次

注：内容非原创，仅作翻译
原论文地址：https://arxiv.org/abs/1609.02907

摘要：我们提出一个直接操作图本身并且基于图卷积网络的半监督学习的方法，该方法使用图结构数据，它是一种卷积神经网络的变体。我们通过谱图卷积的局部一阶近似来激励卷积结构的选择。我们的模型在图形边的数量上是线性扩展的，并且学习了隐藏层对局部图结构和节点特征进行编码的表示。在“论文的引用网络”（ citation networks and on a knowledge graph dataset）数据集上进行了大量实验我们证明我们的方法比相关的方法有显著的优势。

1. 引言

我们考虑一个在图上的（例如引用网络）节点分类问题（例如文档），这里的标签只能对很小的一部分子集可用。这种问题可以表示为基于图的半监督学习，可以通过某种形式的显式的基于图的正则化来平滑图上的标签信息（Zhu等人2003; Zhou等人2004; Belkin 等人2006; Weston等人2012），例如，使用一个图拉普拉斯正则化在损失函数中：
$L=L_0+λL_{reg}, with\; L_{reg}=\displaystyle\sum_{i,j}A_{ij}||f(X_i)-f(X_j)||^2=f(X)^T\Delta f(X).\quad eq.1$ 这里的 $L_0$ 可以表示为在有标签的部分图中的监督损失， $f(.)$ 是一个类似于可微分函数的神经网络， $λ$ 是一个权重因子， $X$ 是由每一个节点 $X_i$ 的特征向量组成的矩阵。 $∆= D−A$ 表示无向图 $G = (V, E)$ 的未归一化图拉普拉斯行列式， $N$ 个节点表示为 $v_i\in V$ ，边表示为 $(v_i, v_j)\in ε$ ，邻接矩阵表示为 $A\in R^{N\times N}$ （二进制或者加权值），次数矩阵 $D_{ii}=\sum_jA_{ij}$ ，公式1中的推导依赖于图中连通节点共享同一个标签这一个假设。然而，这种假设可能会限制建模能力，因为图的边不一定要对节点相似性进行编码，但可能包含其他信息。
在该论文中，我们直接使用一个神经网络模型 $f(X,A)$ 对一个图进行编码，并且有监督地使用所有有标签的节点对 $L_0$ 进行训练，从而避免显式地对基于图的损失函数进行正则化计算。在图的邻接矩阵上调节函数 $f(·)$ 将允许模型从监督损失 $L_0$ 中分开梯度信息，并使其能够学习有标签和无标签节点的表示。
我们的进展是双重的。首先，我们为直接作用于图的神经网络模型引入了一个简单并且表现良好的分层传播规则，并且展示了它们是如何通过谱图卷积的一阶近似来激励神经网络模型。其次，我们证明并演示了这种基于图的神经网络模型如何被用于快速和可扩展的半监督式节点分类。大量的实验表明，我们的模型在时间效率上都优于现有最先进的半监督学习方法。

2. 图上快速近似卷积

在这节，我们提供一个特定的基于图的神经网络模型 $f(X, A)$ ，该模型将会在本文的剩余部分进行使用。我们考虑一个使用了如下所示传播函数的的多层GCN：
$H^{(l+1)}=\sigma(\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}).\quad eq.2$ 这里的 $\widetilde{A}=A+I_N$ 是一个添加了自连接的无向图 $G$ 的邻接矩阵表示，其中 $I_N$ 是一个单位矩阵， $\widetilde{D}_{ii}=\sum_j\widetilde{A}_{ij}$ ， $W^{(l)}$ 是一个可训练的分层权重矩阵。 $\sigma(.)$ 是一个激活函数，例如 $ReLU(.)=max(0,.)$ ， $H^{(l)}\in R^{N \times D}$ 是一个第 $l$ 层的激励矩阵， $H^{(0)}=X$ ，也就是说第一层的激励矩阵是每一个节点的特征向量构成的特征矩阵。在下文中，我们证明了这种传播规则的形式可以通过图上局部谱滤波器的一阶近似来进行激励（Hammond等人 2011; Defferrard等人 2016）。

2.1 卷积谱图

我们将图上的谱卷积定义为一个信号 $x\in R^N$ （一个节点对应一个标量）和一个过滤器 $g_\theta = diag(\theta)$ 的乘积，其中的参数 $\theta$ 为在傅里叶域上的向量，满足 $\theta\in R^N$ 。例如：
$g_\theta*x=Ug_\theta U^Tx\quad eq.3$ 这里的 $U$ 是一个标准化图拉普拉斯变换 $L=I_N-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\land U^T$ ，其中的 $\land$ 为对角矩阵特征值，运算 $U^Tx$ 是 $x$ 的图傅里叶变换结果。我们可以将 $g_\theta$ 理解为一个关于 $L$ 特征值的函数，例如： $g_\theta(\land)$ 。验证和计算公式3是一个费时费力的活儿，因为和特征向量矩阵 $U$ 相乘的复杂度为 $O(N^2)$ 。此外，对于大型图，首先计算 $L$ 的特征分解可能非常昂贵（时间和设备上）。为了缓解这个问题（之所以称为缓解，是因为并没有得到彻底解决），我们可以使用近似表达式，下式中的多项式 $T_k(x)$ 直到 $K$ 阶：
$g_{\theta'}(\land)=\sum_{k=0}^{K}\theta'_kT_k(\widetilde\land)\quad eq.4$ 这里的 $\widetilde\land=\frac{2}{\lambda_{max}}\land-I_N$ ，其中的 $\lambda_{max}$ 指的是 $L$ 的最大特征值， $\theta'\in R^K$ 是一个切比雪夫系数向量，切比雪夫多项式递归定义为 $T_k(x)=2xT_{k-1}(x)-T_{k-2}(x)$ ，并且满足初始条件 $T_0(x)=1$ 和 $T_1(x)=x$ 。回到先前的定义，我们可以更新公式为：
$g_{\theta'}*x\approx\sum_{k=0}^{K}\theta'_kT_k(\widetilde{L})x\quad eq.5$ 其中的 $\widetilde{L}=\frac{2}{\lambda_{max}}L-I_N$ ，并且可以得证 $(U\land U^T)^k=U\land^k U^T$ ，需要注意的是这个表达式是 $k$ 局部的，因为它是 $K$ 阶拉普拉斯多项式，也就是说，它只依赖于离中心节点（K阶领域）最大 $K$ 步的节点（什么意思？），原文如下：

该段原文，没看明白所以然

计算公式5所用到的时间复杂度为 $O(|\epsilon|)$ ，也就是说和边的数量是线性关系。

2.2 Layer-Wise 线性模型

基于图卷积的神经网络模型可由公式5的多层卷积层叠加而成，每层跟随一个逐点非线性（point-wise non-linearity）。现在，假设我们将逐层卷积运算限制为 $K = 1$ （参见公式5），即一个线性的 $w.r.t.\; L$ 的函数，因此是图拉普拉斯谱上的一个线性函数。
通过这种方法，我们可以保持一种丰富的卷积滤波函数，但是并不局限于给出的显式参数化，例如切比雪夫多项式等。我们期待这样一个模型能够解决具有非常宽节点度分布的图（例如社交网络、引用网络、知识图和许多其他真实世界的图数据集）的局部领域结构过拟合问题。此外，这种分层线性模型允许我们构建更深入的模型，这是一种可以提高多个领域建模能力的实践。
在这种情况下，我们将GCN网络进一步近似 $\lambda_{max}\approx 2$ ，神经网络参数将会在大规模的训练之后达到这样预期的估计。因此，公式5可以简化为：
$g_{\theta'}*x\approx \theta'_0x+\theta'_1(L-I_N)x=\theta'_0x-\theta_1'D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x\quad eq.6$ 这里有两个自定义的参数 $\theta'_0$ 和 $\theta'_1$ 。这个滤波器可以在整个图中共享，这种形式的连续滤波操作可以对一个节点的 $k$ 阶邻（k-th）域进行卷积操作，其中 $k$ 指的是神经网络模型中连续滤波操作或者卷积层的数量。
在实践中，得益于进一步限制了参数的数量来处理过拟合并且最小化每层操作的数量（例如使用矩阵乘法），得到了下面的表达式：
$g_\theta*x\approx\theta(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\quad eq.7$ 这里将上述的双参数合并为一个单参数 $\theta=\theta'_0=-\theta_1'$ ，需要注意的是 $I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 现在的特征值在[0, 2]范围内。因此，在深度神经网络模型中重复使用该算子会导致该数值不稳定和梯度消失，为了解决这一问题，我们引入了再归一化技巧：
$I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\to\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}$ ，其中参数满足 $\widetilde{A}=A+I_N\;and\;\widetilde{D}_{ii}=\sum_j\widetilde{A}_{ij}$ 。我们可以将这个定义泛化到信号 $X\in R^{N\times C}$ 这里的 $C$ 输入通道（每个节点有 $C$ 维的特征向量）和 $F$ 维滤波器的特征映射如下：
$Z=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}X\Theta\quad eq.8$ 这里的 $\Theta\in R^{C\times F}$ 是滤波器参数矩阵， $Z\in R^{N\times F}$ 是信号卷积矩阵。这个滤波计算的复杂度是 $O(|\epsilon|FC)$ ，这样可以有效实现 $\widetilde{A}X$ 稠密矩阵和稀疏矩阵的乘积操作。

3. 半监督节点分类器

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

图1. a. 图卷积网络结构

图表解释：输入通道 $C$ 和特征映射输出 $F$ 进行半监督学习的多层图卷积网络(GCN)的示意图。图的结构(以黑线表示的边)在层之间共享，标签用 $Y_i$ 表示。

图1. b. 隐藏层活动状态

图表解释：隐藏层的可视化展示，在Cora数据集上使用5%的标签训练的两层GCN，其中的颜色表示文档类别。

3.1 栗子（例子）

下文中，我们考虑一个两层的GCN用于半监督节点分类，其图上有一个对称的邻接矩阵 $A$ （二进制或者加权矩阵）。在每一步进行处理的时候我们首先计算 $\widetilde{A}=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}$ 作为预处理步骤。我们的前向模型采用以下简形式：
$Z=f(X, A)=softmax(\widetilde{A}ReLU(\widetilde{A}XW^{(0)})W^{(1)})\quad eq.9$ 该处的 $W^{(0)}\in R^{C\times H}$ 是一个输入层到隐藏层（input-to-hidden）的权重矩阵，输出的是维度为 $H$ 的特征映射。 $W^{(1)}\in R^{H\times F}$ 是一个隐藏层到输出层（hidden-to-output）的权重矩阵。该softmax激活函数，定义为 $softmax(x_i)=\frac{1}{Z}exp(x_i)\;with\;Z=\sum_i{exp(x_i)}$ ，该函数应用于每一行。对于半监督多类分类器，我们评估所有训练标签的交叉熵误差：
$L=-\sum_{l\in y_L}\sum_{f=1}^{F}Y_{lf}lnZ_{lf}\quad eq.10$ 该处的 $y_L$ 是一组有标签的节点索引目录。
$W^{(0)}$ 和 $W^{(1)}$ 是使用梯度下降法训练的神经网络权值矩阵。在该任务中，我们每次训练迭代中使用完整的数据集进行批量梯度下降，只要数据集能够在（计算机）内存中存储，这就是一个可行的选择。矩阵 $A$ 使用稀疏表示法，内存的需求是 $O(|\epsilon|)$ ，即和边的数量是线性相关的。训练过程中的随机性是通过dropout（Srivastava等人 2014）。在之后的工作中使用小批量随机梯度下降法来增加内存效率。

3.2 实现

在实践中，我们使用了稀疏矩阵乘法和基于GPU版本的TensorFlow对公式9进行了高效的实现。可以证明，公式9的计算复杂度为 $O(|\epsilon|CHF)$ ，即和图中的边数有线性关系。

4. 相关工作（也称他山之石、前人工作）

（不翻）

5. 实验

我们在数个实验中检验该模型：使用引用网络数据的半监督文档分类器，从知识图中提取的二分图的半监督实体分类器，各种图传播模型的评估和随机图的运行时分析。

5.1 数据集

我们按照Yang等人(2016)设置的实验条件，数据集的统计数据如下表所示：

数据集统计

在引用网络数据集中——Citeseer、Cora和Pubmed中，节点是“文档”，边是“引用网络”。标签比率（Label rate）指的是用来训练的节点所占每一个数据集整体的比重。NELL是一个从含有55864个关系节点以及9891个实体节点中提取出来的二分图。

Citation networks：我们使用三个引用网络数据集（Citeseer、Cora和Pubmed）。这些数据集包含每一个文档的稀疏词库模型特征向量，以及每个文档之间的引用关系列表。我们将引用关系表示为无向图的边并且将其构建为一个二分的，对称的邻接矩阵 $A$ 。每一个文档有一个对应的标签。训练时，我们仅仅用每一个类的20个标签，但是用到了所有的特征向量。
NELL：在程序中并未见到该数据集，不翻。
Random graph：在程序中并未见到该数据集，不翻。

5.2 实验设置

除非特别声明，我们均训练在第3.1节中所述的两层的GCN网络，并且在1000个样本标签中计算预测分数来评估样本。我们提供了一个额外的实验，使用了更深层次的模型（有10层），详细内容在附录B中。我们使用了和Yang等人(2016)中相同的数据集切片。并增加了500个带标记的超参数优化示例验证集（所有层的信号丢失率（dropout rate）、第一个GCN层的 $L_2$ 正则化因子和隐藏单元的数量）。在训练数据过程中不使用验证集。
对于引用网络数据集，我们只在Cora数据集上优化超参数，并且使用相同的参数集在Citeseer和Pubmed上。对所有模型进行200次迭代（epoch），并使用设置为0.01学习速率的Adam优化算法来对模型进行训练。当训练窗口为10的时候提前停止训练（即验证损失值连续10个迭代（epoch）都没有减少的话，我们就停止训练）。对于初始值，我们使用Glorot和Bengio（2010）中提到的初始化方法进行初始化，并相应地对输入特征向量进行归一化（行方向上），在随机图数据集上，我们使用了32个单位地隐层大小，并且省略了正则化（即既没有dropout也没有进行 $L_2$ 正则化的项）。

5.3 基准

我们与Yang等人(2016)相同的基线方法进行了比较，即标签传播
(LP) (Zhu等人2003)，半监督嵌入(SemiEmb) (Weston等人2012)，manifold正则化(ManiReg) (Belkin等人2006)和基于跳跃图嵌入(DeepWalk)(Perozzi等人2014)。我们省略了TSVM (Joachims, 1999)，因为它不能扩展到一个含有大量类别的数据集中。
我们进一步对比了Lu和Getoor(2003)提出的迭代分类算法(ICA)，并结合两个逻辑回归分类器，一个用于单独的局部节点特征，另一个用于使用局部特征和Sen等人(2008)描述的聚合操作符进行关系分类。我们首先使用所有标记的训练集节点训练本地分类器，并使用它引导未标记节点的类标签进行关系分类器训练。我们在所有未标记的节点上（使用本地分类器引导）以随机节点顺序运行迭代分类（关系分类器），进行10次迭代。 $L_2$ 正则化参数和聚合操作符（count vs. prop，参见Sen等人（2008））分别根据每个数据集的验证集性能进行选择。
最后，我们比较了Planetoid（Yang等人2016）的结果，我们总是选择表现最好的模型变体(转导型和诱导型)作为基准。

6. 结果

6.1 半监督节点分类

结果汇总在下表中，表中的数字代表了分类得分比值，对于ICA，我们选择展示其100次随机节点排序运行结果的平均值。对于其他结果而言，基准方法是取自Planetoid（Yang等人2016）论文。Planetoid*表示在他们的论文中给出的变量针对各数据集有最佳模型。

表2：分类得分汇总（百分比）
在我们的方法(包括验证误差的评估)和Planetoid的方法中，我们以秒为单位控制训练时间，直到收敛。对于后者，我们使用了由第三位作者https://github.com/kimiyoung/planetoid提供的实现，并在与我们的GCN模型相同的硬件（使用GPU）上进行了训练。我们在与Yang等人（2016）相同的数据集切片上训练和测试了我们的模型，并报告了使用随机权重初始化的100次运行的平均准确性。我们对Citeseer、Cora和Pubmed使用了以下超参数集:0.5（dropout rate）、（正则化）和16（隐藏单元数目）;对于NELL而言: 0.1（dropout rate），（正则化）和64（隐藏单元数目）。
此外，我们报告了我们的模型在10个随机产生的数据集上的性能，这些数据集的大小与Yang等人(2016)的数据集大小相同，用GCN 表示。在这里，我们报告的平均和标准误差的预测精度的测试集的百分比。

6.2 传播模型评价

（不翻）

6.3 每批次的训练时间

（不属于研究内容，不翻）

7. 讨论（不翻）

7.1 半监督模型

7.2 局限性和展望

8. 结论

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