四、Semi-Supervised GCN

1. 图的半监督学习方法大致分为两大类：

   • 基于图的拉普拉斯矩阵正则化的方法， 包括标签传播算法label propagation、流行正则化算法manifold regularization 。

   • 基于图嵌入的方法，包括 DeepWalk、LINE 等。

     但是基于图嵌入的方法需要一个pipeline，其中包括生成随机游走序列、执行半监督训练等多个步骤，而每个步骤都需要分别进行优化。

   论文《 SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS》 提出了一种可扩展的、基于Graph 的半监督学习方法，该方法基于一个有效的、能直接对Graph 进行操作的卷积神经网络变种。

   该模型基于频域卷积的局部一阶近似来选择卷积网络结构，其计算复杂度为 ，其中 为边的数量。

   该模型学到的隐层representation 既能够编码图的局部结构，又能够编码顶点的特征。

2. 考虑图中顶点的分类问题，其中仅有一小部分顶点具有标签信息。如：对引文网络的文章进行分类，只有一小部分文中具有类别标签。

   该问题是一个图的半监督学习问题，其中标签信息通过显式的正则化而被平滑。例如，考虑在损失函数中使用图的拉普拉斯正则项：

   

   其中：

   • 表示图中有标签部分的监督损失； 为正则化项； 为罚项系数。其中：

     

     为顶点 的输入特征， 为顶点 的标签； 是一个类似神经网络的可微函数，它将输入 映射到类别空间； 为带标签顶点的集合。

   • 为邻接矩阵， 为顶点数量； 为度矩阵，其中 ； 为无向图 的未归一化的拉普拉斯算子 ； 为顶点的特征向量拼接的矩阵

   正则化项的物理意义为：

   • 如果两个顶点距离较近（即 较大），则它们的 representation 应该比较相似（即 和 距离相近）。
   • 如果两个顶点距离较远(即 较小)，则它们的 representation 可以相似也可以不相似。

   因此该模型假设：Graph 中直接相连的顶点很可能共享相同的标签。这种假设会限制模型的表达能力，因为图中的边不一定代表相似性，边也可能代表其它信息。

   在论文Semi-Supervised GCN 中，作者直接使用神经网络模型 对图结构进行编码，并对所有带标签的顶点进行监督目标 的训练，从而避免在损失函数中进行显式的、基于图的正则化。 依赖于图的邻接矩阵 ，这允许模型从监督损失 中分配梯度信息，并使得模型能够学习带标签顶点的representation 和不带标签顶点的 representation。

4.1 模型

1. 考虑一个多层GCN 网络，其中每层的传播规则为：

   

   其中：

   • 是带自环的无向图的邻接矩阵， 为单位矩阵， 为顶点数量； 为带自环的度矩阵。
   • 为第 层的激活矩阵， ， 为特征向量维度； 为第 层的权重矩阵； 为激活函数。

   其基本物理意义：

   • 我们认为在第 层，每个顶点的representation 由其邻域内顶点（包含它自身）在第 层的representation 的加权和得到，加权的权重为边的权重：

     

   • 考虑到不同顶点的度不同，这将使得顶点的度越大（即邻域内顶点越多），则representation 越大。因此这里对顶点的度进行归一化：

     

   • 考虑到非线性映射，则得到最终的结果 ：

     

2. 可以证明，上述形式的传播规则等价于localized 局部化的频域图卷积的一阶近似。

   给定输入 ，其频域卷积为 ，其中：

   

   为卷积核， 各列为拉普拉斯矩阵 的特征向量。这里我们采用归一化的拉普拉斯矩阵：

   

   以及 。

   这种卷积的参数数量为 ，计算复杂度为 。因此 Fast Graph CNN 采用切比雪夫多项式来构造多项式卷积核，因此有：

   

   其中 为 阶切比雪夫多项式， 为其系数， 。

   令 ，则有：

   

   该卷积满足 阶局部性，其计算复杂度为 。

   现在我们选择 ，则有 。因此有：

   

   该卷积为 的线性函数。

   • 我们仍然可以堆叠多个这样的层来实现图卷积神经网络，但是现在我们不再局限于切比雪夫多项式这类的参数化方式。
   • 由于 为归一化的拉普拉斯矩阵，因此我们预期该模型能够缓解顶点的degree 分布范围很大的图的局部邻域结构的过拟合问题，这些图包括社交网络、引文网络、知识图谱等等。
   • 当计算资源有限时，这种线性卷积核使得我们可以构建更深的模型，从而提高模型的能力。

   进一步的，我们令 ，因为我们预期模型可以在训练过程中适应这种变化。另外我们减少参数数量，令 ，则有：

   

   注意到 的特征值在 [0,2]之间，在深层网络种应用这种卷积操作会导致数值不稳定核梯度爆炸、消失的现象。为缓解该问题，我们应用了正则化技巧：

   

   其中 ， 为由 定义的度矩阵： 。

   我们可以将这个定义推广到 个输入通道、 个输出通道的卷积上，其中输入 ，则卷积输出为：

   

   其中 为输出 featue map， 为卷积核的参数矩阵。

   卷积操作的计算复杂度为 ，因为 可以实现为一个稀疏矩阵和一个稠密矩阵的乘积。

3. 介绍完这个简单灵活的、可以在图上传播信息的模型 之后，我们回到图的半监督顶点分类问题上。由于 包含了一些 中为包含的图的结构信息，如引文网络中的文档引用关系、知识图谱的实体之间的关系等等，我们预期模型比传统的半监督学习模型表现更好。

   整个半监督学习模型是一个多层GCN模型，结构如下图所示。

   • 左图：一个多层卷积神经网络模型，其中包含 个输入通道、 个输出通道，图中 。

     黑色的线条为图的边，彩色线条为信息流动的方向（注意：颜色有重叠）； 为监督的标签信息。图结构在不同卷积层之间共享。

   • 右图：在Cora 数据集上的一个双层GCN 网络（两个隐层 + 一个输出层）的最后一个隐层的隐向量（经过激活函数），在使用 t-SNE 可视化的结果，颜色代表不同类别。其中数据集仅仅使用 5% 的顶点标签。

   

4. 考虑一个双层 GCN 模型，其邻接矩阵 是对称的。

   • 我们首先在预处理中计算

   • 然后计算前向传播：

     

     其中：

     • 为输入到隐层的权重矩阵，有 个输出 feature map

     • 为隐层到输出的权重矩阵

     • 激活函数定义为：

       

       按行进行归一化。

     前向传播的计算复杂度为 。

   • 对于半监督多标签分类，我们使用交叉熵来衡量所有标记样本的误差：

     

     其中 为有标签的顶点的下标集合。顶点标签 经过 one-hot 为： ，其中 为类别数量。

   • 神经网络权重 使用梯度下降来训练。

     • 只要数据集能够全部放到内存中，训练过程中我们就使用全部数据集来执行梯度下降。由于邻接矩阵 是稀疏的，因此内存占用为 。

       在未来工作中，我们考虑使用 mini-batch 随机梯度下降。

     • 训练过程中使用 dropout 增加随机性。

4.2 WL-1 算法

1. 理想情况下图神经网络模型应该能够学到图中顶点的representation，该representation 必须能够同时考虑图的结构和顶点的特征。

   一维 Weisfeiler-Lehman:WL-1 算法提供了一个研究框架。给定图以及初始顶点标签，该框架可以对顶点标签进行分配。

2. WL-1 算法：令 为顶点 在第 轮分配的标签， 为顶点 的邻居顶点集合。

   • 输入：初始顶点标签

   • 输出：最终顶点标签

   • 算法步骤：

     • 初始化

     • 迭代直到 或者顶点的标签到达稳定状态。迭代步骤为：

       • 循环遍历 ，执行：

         

       • 

     • 返回每个顶点的标签

3. 如果我们采用一个神经网络来代替 hash 函数，同时假设 为向量，则有：

   

   其中：

   • 为第 层神经网络顶点 的激活向量 vector of activations 。
   • 为第 层的权重矩阵。
   • 为非线性激活函数。
   • 为针对边 的正则化常数。

   我们定义 ，其中 为顶点 的度degree，则上式等价于我们的 GCN 模型。因此我们可以将 GCN 模型解释为图上 WL-1 算法的微分化和参数化的扩展。

4. 通过与 WL-1 算法的类比，我们可以认为：即使是未经训练的、具有随机权重的 GCN 模型也可以充当图中顶点的一个强大的特征提取器。如：考虑下面的一个三层GCN 模型：

   

   其中权重矩阵是通过 Glorot & Bengio (2010) 初始化的： 。

5. 我们将这个三层 GCN 模型应用于 Zachary 的 karate club network ，该网络包含34个顶点、154 条边。每个顶点都属于一个类别，一共四种类别。顶点的类别是通过 modularity-based 聚类算法进行标注的。如下图所示，颜色表示顶点类别。

   

   我们令 ，即每个顶点除了顶点ID 之外不包含任何其它特征。另外顶点的ID 是随机分配的，也不包含任何信息。我们选择隐层的维度为4、输出层的维度为2 ，因此输出层的输出 能够直接视为二维数据点来可视化。

   下图给出了未经训练的 GCN 模型获得的顶点embedding，这些结果与从DeepWalk 获得的顶点embedding 效果相当，而DeepWalk 使用了代价更高的无监督训练过程。

   

6. 在karate club network数据集上，我们观察半监督分类任务期间，embedding 如何变化。这种可视化效果提供了关于 GCN 模型如何利用图结构从而学到对于分类任务有益的顶点embedding 。

   训练配置：

   • 在上述三层GCN 之后添加一个 softmax 输出层，输出顶点属于各类别的概率
   • 每个类别仅使用一个带标签的顶点进行训练，一共有四个带标签的顶点
   • 使用Adam 优化器来训练，初始化学习率为 0.01
   • 采用交叉熵损失函数
   • 迭代 300 个 step

   下图给出多轮迭代中，顶点embedding 的演变。图中的灰色直线表示图的边，高亮顶点（灰色轮廓）表示标记顶点。可以看到：模型最终基于图结构以及最少的监督信息，成功线性分离出了簇团。

   

4.3 局限性

1. 我们的 Semi-GCN 模型存在一些局限，我们计划在将来克服这些局限性。

2. 内存需求局限性：在full-batch 梯度下降算法中，内存需求随着数据集的大小线性增长。

   • 一种解决方式是：采用 CPU 训练来代替 GPU 训练。这种方式我们在实验中得到验证。

   • 另一种解决方式是：采用 mini-batch 梯度下降算法。

     但是mini-batch 梯度下降算法必须考虑 GCN 模型的层数。因为对于一个 层的 GCN 模型，其 阶邻居必须全部存储在内存中。对于顶点数量庞大、顶点链接很密集的图，这可能需要进一步的优化。

3. 边类型的局限性：目前我们的模型不支持边的特征，也不支持有向图。

   通过NELL 数据集的实验结果表明：可以通过将原始的有向图转化为无向二部图来处理有向图以及边的特征。这通过额外的顶点来实现，这些顶点代表原始Graph 中的边。

4. 假设局限性：我们的模型有两个基本假设：

   • 假设 层GCN 依赖于 阶邻居，即模型的局部性。

   • 假设自链接和邻居链接同样重要。

     在某些数据集中，我们可以引入一个折衷参数： 。其中参数

     平衡了自链接和邻居链接的重要性，它可以通过梯度下降来学习。

4.4 实验

1. 我们在多个任务中验证模型性能：在引文网络中进行半监督文档分类、在从知识图谱抽取的二部图中进行半监督实体分类。然后我们评估图的各种传播模型，并对随机图的运行时进行分析。

2. 数据集：

   • 引文网络数据集：我们考虑 Citeseer,Cora,Pubmed 三个引文网络数据集，每个数据集包含以文档的稀疏 BOW 特征向量作为顶点，文档之间的引文链接作为边。我们将引文链接视为无向边，并构造一个二元的对称邻接矩阵 。

     每个文档都有一个类别标签，每个类别仅包含 20个标记顶点作为训练样本。

   • NELL 数据集：该数据集是从Carlson et al.2010 引入的知识图谱中抽取的数据集。知识图谱是一组采用有向的、带标记的边链接的实体。我们为每个实体对 分配顶点 ，以及边 和 。其中， 是知识图谱链接 得到的两个“拷贝”的关系顶点relation node，它们之间不存在边。最终我们得到 55864 个关系顶点和 9891 个实体顶点。

     实体顶点entity node 通过稀疏的特征向量来描述。我们为每个关系顶点分配唯一的 one-hot 向量从而扩展 NELL 的实体特征向量，从而使得每个顶点的特征向量为 61278 维稀疏向量。

     对于顶点 和 ，如果它们之间存在一条边或者多条边，则设置 从而构建一个二元对称邻接矩阵。

     在顶点的半监督分类任务中，我们为每个类别标记一个顶点作为训练集，因此属于非常极端的情况。

   • 随机图：我们生成各种规模的随机Graph 数据集，从而评估每个epoch 的训练时间。

     对于具有 个顶点的图，我们创建一个随机图：

     • 随机均匀分配 条边
     • 令 ，即每个顶点除了其id 之外没有任何特征，且顶点id 是随机分配的
     • 每个顶点标签为

   各数据集的整体统计如下表所示。标记率：表示监督的标记顶点数量占总的顶点数量的比例。

   

3. 模型设置：除非另有说明，否则我们的GCN 模型就是前面描述的两层GCN 模型。

   • 我们将数据集拆分为labled 数据、unlabled 数据、测试数据。其中我们在labled 数据和 unlabled 数据上学习，在测试数据上测试。我们选择测试数据包含 1000 个顶点。

     另外我们还使用额外的 500 个带标签的顶点作为验证集，用于超参数优化。这些超参数包括：所有层的 dropout 比例、第一层的 正则化系数、隐层的维度。

     注意：验证集不用于训练。

   • 对于引文网络数据集，我们仅在Cora 数据集上优化超参数，并对Citeseer 和 Pubmed 数据集采用相同的超参数。

   • 所有模型都使用 Adam 优化器，初始化学习率为 0.01 。

   • 所有模型都使用早停策略，早停的 epoch 窗口为 10。即：如果连续 10 个 epoch 的验证损失没有下降，则停止继续训练。

   • 所有模型最多训练 200 个 epoch 。

   • 我们使用 Glorot & Bengio (2010) 初始化策略： 。

   • 我们对输入的特征向量进行按行的归一化 row-normalize，这类似于 Batch-Normalization，使得每个维度的取值都在相近的取值范围。

   • 在随机图数据集上，我们选择隐层维度为 32，并省略正则化：即不进行dropout，也不进行 正则化。

4. Baseline 模型：我们比较了 Yang et al.(2016) 相同的 baseline 方法，即：即：标签传播算法label propagation:LP、半监督embedding 算法 semi-supervised embedding:SemiEmb 、流形正则化算法manifold regularization:MainReg 、基于skip-gram 的图嵌入算法DeepWalk 。

   • 我们忽略了 TSVM 算法，因为它无法扩展到类别数很大的数据集。
   • 我们还还比较了Planetoid(2016) 算法， 以及 Lu&Getoor(2003) 提出的迭代式分类算法iterative classification algorithm:ICA 。

5. 模型比较结果如下表所示。

   • 对于ICA ，我们随机运行 100 次、每次以随机的顶点顺序训练得到的平均准确率； 所有其它基准模型的结果均来自于 Planetoid 论文，Planetoid* 表示论文中提出的针对每个数据集的最佳变体。

   • 我们的GCN 执行100次、每次都是随机权重初始化的平均分类准确率，括号中为平均训练时间。

   • 我们为 Citeseer,Cora,Pubmed 使用的超参数为：dropout = 0.5、 正则化系数为 、隐层的维度为64 。

   • 最后我们报告了10 次随机拆分数据集，每次拆分的labled 数据、unlabled 数据、测试数据比例与之前相同，然后给出GCN 的平均准确率和标准差（以百分比表示），记作 GCN(rand. splits) 。

     前面七行是针对同一个数据集拆分，最后一行是不同的数据集拆分。

   实验表明：我们的半监督顶点分类方法明显优于其它方法。

   • 基于图的拉普拉斯正则化方法（LP, maniReg 方法）最有可能受到限制，因为它们假设图的边仅仅编码了顶点的相似性。
   • 基于 SkipGram 的方法也受到限制，因为它们难以优化一个多步骤的 pipeline 。

   我们的模型可以克服这些局限性，同时在计算效率上和有关方法相比仍然是有利的。

   

6. 我们在引文网络数据集上比较了我们提出的逐层传播模型的不同变体，实验配置和之前相同，结果如下表所示。

   我们原始的 GCN 模型应用了 renormalization 技巧（粗体），即：

   

   其它的GCN 变体采用Propagation model 对应的传播模型。

   • 对于每一种变体模型，我们给出执行100次、每次都是随机权重初始化的平均分类准确率。
   • 对于每层有多个权重 的情况下（如 Chebyshev filter, 1st-order model），我们对第一层的所有权重执行 正则化。

   实验表明：和单纯的一阶切比雪夫多项式卷积模型，以及更高阶的切比雪夫多项式卷积模型相比，renormalization 模型在很多数据集上都能够效率更高（更少的参数和更少的计算量）、预测能力更强。

   

7. 我们在随机图上报告了 100 个 epoch 的每个 epoch 平均训练时间。我们在 Tensorflow 上比较了 CPU 和 GPU 实现的结果，其中 * 表示内存溢出错误Out Of Memory Error 。

   

8. 最后我们考虑模型的深度对于性能的影响。这里我们报告对 Cora,Citeseer,Pubmed 数据集进行5 折交叉验证的结果。

   除了标准的 GCN 模型之外，我们还报告了模型的一种变体：隐层之间使用了残差连接：

   

   在5 折交叉验证的每个拆分中，我们训练400 个 epoch 并且不使用早停策略。我们使用Adam 优化器，初始学习率为 0.01。我们对第一层和最后一层使用dropout = 0.5 ，第一层权重执行正则化系数为 的 正则化。GCN 的隐层维度选择为 16 。

   结果如下图所示，其中标记点表示5 折交叉验证的平均准确率，阴影部分表示方差。

   可以看到：

   • 当使用两层或三层模型时，GCN 可以获得最佳效果。
   • 当模型的深度超过七层时，如果不使用残差连接则训练会变得非常困难，表现为训练准确率骤降。
   • 当模型深度增加时，模型的参数数量也会增加，此时模型的过拟合可能会成为问题。