目录四、相关工作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启发的图嵌入方法。DeepWalkPerozzi et al., 2014通过预测图中随机游走采样节点的局部邻域来学习嵌入。LINETang et al., 2015和node2vecGrover Leskovec, 2016改进了DeepWalk采用更复杂的随机游走或广度优先搜索策略。然而这些方法均需多步骤流程如随机游走生成和半监督训练且每一步需单独优化。PlanetoidYang 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、PubmedSen等人2008年提出节点代表文献边代表引用关系。标注率指训练使用的已标注节点数占数据集总节点数的比例。NELL数据集Carlson等人2010年Yang等人2016年引用从知识图谱提取的二部图包含55,864个关系节点和9,891个实体节点。引文网络研究涉及三个引文网络数据集Citeseer、Cora和PubmedSen等2008。这些数据集包含每篇文档的稀疏词袋特征向量及文档间的引用链接列表。引用链接被视为无向边并构建二元对称邻接矩阵A。每篇文档带有类别标签训练阶段仅使用每类20个标签但使用全部特征向量。NELL知识图谱NELL数据集源自Carlson等2010提出的知识图谱。知识图谱由通过定向标记边关系连接的实体集合构成。采用Yang等2016的预处理方案为每对实体关系(e1,r,e2)分配独立关系节点r1和r2形成(e1,r1)和(e2,r2)结构。实体节点通过稀疏特征向量描述通过为每个关系节点分配独热编码扩展特征维度最终生成61,278维稀疏特征向量。半监督任务设定为每类仅含一个标注样本的极端情况通过节点间存在边时设置Aij1构建二元对称邻接矩阵。随机图为测量每轮训练时间模拟不同规模的随机图数据集。对于含N个节点的数据集通过均匀随机分配2N条边构建随机图。输入特征矩阵X采用单位矩阵IN即通过独热向量标识节点身份的特征无关方法所有节点设置虚拟标签Yi1。5.2 实验设置除非另有说明实验采用3.1节描述的两层GCN结构并在包含1,000个标注样本的测试集上评估预测准确率。附录B提供了更深层模型最多10层的补充实验。数据集划分与Yang等人2016保持一致并额外使用500个标注样本的验证集进行超参数优化包括所有层的丢弃率、第一GCN层的L2正则化系数及隐藏单元数量。验证集标签不参与训练。针对引文网络数据集超参数仅在Cora数据集上优化并在Citeseer和Pubmed中复用相同配置。所有模型最多训练200个周期迭代采用Adam优化器学习率0.01并启用早停机制窗口大小为10即验证损失连续10轮未下降时终止训练。权重初始化采用Glorot Bengio2010的方法输入特征向量按行归一化。在随机图数据集中隐藏层设置为32个单元且不进行正则化即不使用丢弃或L2正则化。5.3 基线方法比较的基线方法与Yang等人2016的研究一致包括标签传播LPZhu等人2003、半监督嵌入SemiEmbWeston等人2012、流形正则化ManiRegBelkin等人2006以及基于Skip-gram的图嵌入方法DeepWalkPerozzi等人2014。由于TSVMJoachims1999无法扩展到数据集中大量类别的场景因此未纳入比较。进一步对比了Lu Getoor2003提出的迭代分类算法ICA该算法结合了两个逻辑回归分类器一个仅使用局部节点特征另一个通过局部特征和聚合算子Sen等人2008所述进行关系分类。具体实现中先利用所有带标签的训练集节点训练局部分类器并基于其预测结果引导未标注节点的伪标签用于关系分类器的训练。在未标注节点上通过局部分类器引导以随机节点顺序运行10次迭代分类关系分类器。L2正则化参数和聚合算子计数或比例见Sen等人2008根据各数据集的验证集表现单独选择。最后与PlanetoidYang等人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.5L2正则化系数5×10⁻⁴隐藏单元数16NELL数据集丢弃率0.1L2正则化系数1×10⁻⁵隐藏单元数64随机划分验证额外汇报了模型在10次随机数据集划分划分规模与Yang等人相同下的性能表现标记为GCN随机划分。测试集预测准确率以百分比形式呈现同时标注平均值和标准误差。6.2 传播模型评估在引文网络数据集上对所提出的逐层传播模型的不同变体进行比较。实验设置遵循前一章节的描述结果汇总于表3。原始GCN模型采用的传播模型标记为重归一化技巧加粗显示。其余情况下神经网络各层的传播模型均替换为“传播模型”栏下指定的模型。报告数值为100次随机权重矩阵初始化的重复实验分类准确率均值。若单层存在多个变量Θi对第一层所有权重矩阵施加L2正则化。6.3 每轮训练时间本节报告在模拟随机图上进行100轮训练前向传播、交叉熵计算、反向传播的每轮平均训练时间结果以秒为单位的实际耗时呈现。实验所用随机图数据集的详细描述见第5.1节。对比了基于GPU和仅使用CPU的TensorFlowAbadi等2015实现的性能差异结果汇总于图2。硬件配置16核英特尔®至强®处理器 E5-2640 v3 2.60GHz 英伟达® GeForce® GTX TITAN X 显卡 七 讨论7.1 半监督模型实验结果表明本文提出的半监督节点分类方法显著优于近期相关方法。基于图拉普拉斯正则化的方法如Zhu等2003Belkin等2006Weston等2012受限于其假设——边仅编码节点相似性而基于Skip-gram的方法因多步骤流水线难以优化存在局限性。本文模型能克服这两类限制同时在运行效率以实际时间为衡量标准上优于对比方法。通过每层聚合相邻节点的特征信息分类性能优于仅聚合标签信息的ICA方法Lu Getoor2003。实验进一步证明与朴素一阶模型公式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)(三)