图神经网络分享系列-GCN(SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS)(二)
目录
四、相关工作
4.1 基于图的半监督学习
4.2 图神经网络
五、实验部分
5.1 数据集
引文网络
NELL知识图谱
随机图
5.2 实验设置
5.3 基线方法
六、结果
6.1 半监督节点分类结果
编辑
实验方法与结果详述
随机划分验证
6.2 传播模型评估
6.3 每轮训练时间
编辑
七 讨论
7.1 半监督模型
7.2 局限性与未来工作
参数作用
八、结论
图神经网络概览：图神经网络分享系列-概览
上一篇文章：图神经网络分享系列-GCN(SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS)(一)
四、相关工作
该模型的设计灵感来源于基于图的半监督学习领域以及近期关于图神经网络的研究。以下简要概述这两个领域的相关工作。
4.1 基于图的半监督学习
近年来，大量基于图表示的半监督学习方法被提出，主要分为两类：显式图拉普拉斯正则化方法和图嵌入方法。图拉普拉斯正则化的典型代表包括标签传播（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.2 图神经网络
Gori et al. (2005) 和 Scarselli et al. (2009) 最早将图神经网络引入为一种循环神经网络框架，其要求重复应用收缩映射作为传播函数，直至节点表示达到稳定固定点。Li et al. (2016) 通过将现代循环神经网络训练技术引入原框架，缓解了这一限制。Duvenaud et al. (2015) 提出了图上的类卷积传播规则及图级分类方法，但需学习节点度数特定的权重矩阵，难以扩展至节点度数分布广泛的大规模图。该模型则采用每层单一权重矩阵，并通过邻接矩阵的适当归一化处理可变节点度数（见第3.1节）。
Atwood & Towsley (2016) 近期提出了一种基于图神经网络的节点分类方法，但其计算复杂度为O(N²)，限制了应用范围。Niepert et al. (2016) 将图局部转换为序列后输入传统一维卷积神经网络，但需预处理阶段定义节点排序。
该模型基于Bruna et al. (2014) 提出的谱图卷积神经网络，并经Defferrard et al. (2016) 扩展为快速局部化卷积。与这些工作不同，本研究聚焦于更大规模网络中的转导式节点分类任务，并证明在此场景下，可对原框架进行简化（见第2.2节），从而提升大规模网络中的可扩展性和分类性能。
五、实验部分
我们通过多项实验测试模型性能：引用网络中的半监督文档分类、从知识图谱提取的二部图中的半监督实体分类、多种图传播模型的评估以及随机图上的运行时分析。
5.1 数据集
实验设置严格遵循Yang等人（2016）的方案，数据集统计信息见表1。
引用网络数据集（Citeseer、Cora、Pubmed，Sen等人2008年提出）：节点代表文献，边代表引用关系。"标注率"指训练使用的已标注节点数占数据集总节点数的比例。
NELL数据集（Carlson等人2010年，Yang等人2016年引用）：从知识图谱提取的二部图，包含55,864个关系节点和9,891个实体节点。
引文网络
研究涉及三个引文网络数据集：Citeseer、Cora和Pubmed（Sen等，2008）。这些数据集包含每篇文档的稀疏词袋特征向量及文档间的引用链接列表。引用链接被视为（无向）边，并构建二元对称邻接矩阵A。每篇文档带有类别标签，训练阶段仅使用每类20个标签，但使用全部特征向量。
NELL知识图谱
NELL数据集源自Carlson等（2010）提出的知识图谱。知识图谱由通过定向标记边（关系）连接的实体集合构成。采用Yang等（2016）的预处理方案：为每对实体关系(e1,r,e2)分配独立关系节点r1和r2，形成(e1,r1)和(e2,r2)结构。实体节点通过稀疏特征向量描述，通过为每个关系节点分配独热编码扩展特征维度，最终生成61,278维稀疏特征向量。半监督任务设定为每类仅含一个标注样本的极端情况，通过节点间存在边时设置Aij=1构建二元对称邻接矩阵。
随机图
为测量每轮训练时间，模拟不同规模的随机图数据集。对于含N个节点的数据集，通过均匀随机分配2N条边构建随机图。输入特征矩阵X采用单位矩阵IN，即通过独热向量标识节点身份的特征无关方法，所有节点设置虚拟标签Yi=1。
5.2 实验设置
除非另有说明，实验采用3.1节描述的两层GCN结构，并在包含1,000个标注样本的测试集上评估预测准确率。附录B提供了更深层模型（最多10层）的补充实验。数据集划分与Yang等人（2016）保持一致，并额外使用500个标注样本的验证集进行超参数优化（包括所有层的丢弃率、第一GCN层的L2正则化系数及隐藏单元数量）。验证集标签不参与训练。
针对引文网络数据集，超参数仅在Cora数据集上优化，并在Citeseer和Pubmed中复用相同配置。所有模型最多训练200个周期（迭代），采用Adam优化器（学习率0.01）并启用早停机制（窗口大小为10，即验证损失连续10轮未下降时终止训练）。权重初始化采用Glorot & Bengio（2010）的方法，输入特征向量按行归一化。
在随机图数据集中，隐藏层设置为32个单元，且不进行正则化（即不使用丢弃或L2正则化）。
5.3 基线方法
比较的基线方法与Yang等人（2016）的研究一致，包括标签传播（LP）（Zhu等人，2003）、半监督嵌入（SemiEmb）（Weston等人，2012）、流形正则化（ManiReg）（Belkin等人，2006）以及基于Skip-gram的图嵌入方法（DeepWalk）（Perozzi等人，2014）。由于TSVM（Joachims，1999）无法扩展到数据集中大量类别的场景，因此未纳入比较。
进一步对比了Lu & Getoor（2003）提出的迭代分类算法（ICA），该算法结合了两个逻辑回归分类器：一个仅使用局部节点特征，另一个通过局部特征和聚合算子（Sen等人，2008所述）进行关系分类。具体实现中，先利用所有带标签的训练集节点训练局部分类器，并基于其预测结果引导未标注节点的伪标签，用于关系分类器的训练。在未标注节点上（通过局部分类器引导）以随机节点顺序运行10次迭代分类（关系分类器）。L2正则化参数和聚合算子（计数或比例，见Sen等人，2008）根据各数据集的验证集表现单独选择。
最后与Planetoid（Yang等人，2016）进行对比，始终选择其表现最佳的模型变体（直推式或归纳式）作为基线。
六、结果
6.1 半监督节点分类结果
结果总结于表2。报告的数字表示分类准确率（百分比）。对于ICA方法，报告了100次随机节点排序运行的平均准确率。所有其他基线方法的结果均引自Planetoid论文（Yang等人，2016年）。Planetoid*表示该论文中针对各数据集的最佳模型变体。
关键术语说明
- 半监督节点分类：结合有标签和无标签数据的图节点分类任务。
- 分类准确率：模型预测正确的样本比例，以百分比形式呈现。
- ICA（迭代分类算法）：通过迭代更新节点特征的分类方法，需考虑随机性影响。
- Planetoid：一种基于图的半监督学习框架，包含多种变体模型。
实验方法与结果详述
我们进一步记录了从训练开始至收敛的实时训练时间（单位为秒，括号内数值），涵盖本方法（含验证误差评估过程）及Planetoid方法的对比数据（https://github.com/kimiyoung/planetoid）。针对Planetoid，采用作者提供的官方实现代码，并在与GCN模型相同的GPU硬件环境下进行训练。
模型训练与测试均基于Yang等人（2016）论文中相同的数据集划分方式，最终汇报的是100次随机权重初始化的平均准确率。不同数据集的超参数配置如下：
- Citeseer、Cora、Pubmed数据集：丢弃率0.5，L2正则化系数5×10⁻⁴，隐藏单元数16
- NELL数据集：丢弃率0.1，L2正则化系数1×10⁻⁵，隐藏单元数64
随机划分验证
额外汇报了模型在10次随机数据集划分（划分规模与Yang等人相同）下的性能表现，标记为GCN（随机划分）。测试集预测准确率以百分比形式呈现，同时标注平均值和标准误差。
6.2 传播模型评估
在引文网络数据集上，对所提出的逐层传播模型的不同变体进行比较。实验设置遵循前一章节的描述，结果汇总于表3。原始GCN模型采用的传播模型标记为重归一化技巧（加粗显示）。其余情况下，神经网络各层的传播模型均替换为“传播模型”栏下指定的模型。报告数值为100次随机权重矩阵初始化的重复实验分类准确率均值。若单层存在多个变量Θi，对第一层所有权重矩阵施加L2正则化。
6.3 每轮训练时间
本节报告在模拟随机图上进行100轮训练（前向传播、交叉熵计算、反向传播）的每轮平均训练时间，结果以秒为单位的实际耗时呈现。实验所用随机图数据集的详细描述见第5.1节。对比了基于GPU和仅使用CPU的TensorFlow（Abadi等，2015）实现的性能差异，结果汇总于图2。
（硬件配置：16核英特尔®至强®处理器 E5-2640 v3 @ 2.60GHz 英伟达® GeForce® GTX TITAN X 显卡 ）
七 讨论
7.1 半监督模型
实验结果表明，本文提出的半监督节点分类方法显著优于近期相关方法。基于图拉普拉斯正则化的方法（如Zhu等，2003；Belkin等，2006；Weston等，2012）受限于其假设——边仅编码节点相似性；而基于Skip-gram的方法因多步骤流水线难以优化存在局限性。本文模型能克服这两类限制，同时在运行效率（以实际时间为衡量标准）上优于对比方法。通过每层聚合相邻节点的特征信息，分类性能优于仅聚合标签信息的ICA方法（Lu & Getoor，2003）。
实验进一步证明，与朴素一阶模型（公式6）或基于切比雪夫多项式的高阶图卷积模型（公式5）相比，提出的重归一化传播模型（公式8）在多个数据集上实现了更高的预测性能，同时具备更优的计算效率（参数量和运算量更少）。
7.2 局限性与未来工作
当前模型存在以下局限性，未来工作可针对性改进：
内存需求
全批量梯度下降下，内存需求随数据集规模线性增长。实验表明，对于超出GPU内存的大规模图，CPU训练仍可行。采用小批量随机梯度下降可缓解此问题，但需注意：生成小批量时应考虑GCN层数，因为K层GCN需存储K阶邻域信息以实现精确计算。对于超大稠密图数据集，可能需要进一步近似处理。
有向边与边特征
当前框架默认不支持边特征，且仅适用于无向图（加权或未加权）。但在NELL数据集上的结果表明，通过将原始有向图转化为无向二分图（附加节点表示原图的边），可间接处理有向边和边特征（详见5.1节）。
假设限制
第2节的近似隐含了两项假设：局部性（K层GCN仅依赖K阶邻域）以及自连接与邻边权重相等。某些场景下，需在的定义中引入权衡参数
以调整重要性比例。
参数作用
该参数的作用类似于典型半监督设置中监督损失和无监督损失之间的权衡参数（参见公式1）。不同之处在于，此处可通过梯度下降自动学习该参数。
八、结论
提出了一种针对图结构数据的半监督分类新方法。基于图频谱卷积的一阶近似，所设计的图卷积网络（GCN）模型采用高效的层间传播规则。在多个网络数据集上的实验表明，该模型能够有效编码图结构和节点特征，从而提升半监督分类性能。在此设定下，模型显著优于近期提出的多种方法，同时具备较高的计算效率。
关于gcn的实验部分，就已经描述完成，后续会针对附录部分，做个描述。
下一篇文章：图神经网络分享系列-GCN(SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS)(三)