第17卷第3期 智能系统学报 Vol.17 No.3 2022年5月 CAAI Transactions on Intelligent Systems May 2022 D0:10.11992/tis.202107048 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20220324.1345.002.html 基于图卷积集成的网络表示学习 常新功，王金珏 (山西财经大学信息学院，山西太原030006) 摘要：针对现有网络表示学习方法泛化能力较弱等问题，提出了将stacking集成思想应用于网络表示学习的 方法，旨在提升网络表示性能。首先，将3个经典的浅层网络表示学习方法DeepWalk、Node2Vec、Line作为并 列的初级学习器，训练得到三部分的节点嵌入拼接后作为新数据集；然后，选择图卷积网络(graph convolutional network,GCN)作为次级学习器对新数据集和网络结构进行stacking集成得到最终的节点嵌入，GCN处理半监 督分类问题有很好的效果，因为网络表示学习具有无监督性，所以利用网络的一阶邻近性设计损失函数；最 后，设计评价指标分别评价初级学习器和集成后的节点嵌入。实验表明.选用GCN集成的效果良好，各评价指 标平均提升了1.47~2.97倍。 关键词：网络表示学习；集成学习；图卷积网络：社交网络：深度学习；特征学习；节点嵌入：信息网络嵌人 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2022)03-0547-09 中文引用格式：常新功，王金珏.基于图卷积集成的网络表示学习.智能系统学报，2022,17(3)：547-555. 英文引用格式：CHANG Xingong,WANGJinjue.Network representation learning using graph convolution ensemble.CAAI transactions on intelligent systems,2022,17(3):547-555. Network representation learning using graph convolution ensemble CHANG Xingong,WANG Jinjue (School of Information,Shanxi University of Finance and Economics,Taiyuan 030006,China) Abstract:Aimed at the weak generalization ability of the existing network representation learning methods,this paper proposes a stacking ensemble method that is applied to network representation learning to improve the performance of network representation.Three classical shallow network representation learning methods,namely,DeepWalk, Node2Vec,and Line,are used initially as parallel primary learners.After training,the embedded representation and three spliced node parts are obtained.Following this,the graph convolutional network(GCN)is selected as the second- ary learner to stack and integrate the network structure and the new data set.This is done to obtain the final node embed- ded representation.GCN efficiently deals with semisupervised classification problems.As network representation learn- ing is unsupervised,the first-order proximity of the network has been used to design the loss function.Finally,evalu- ation indices are designed to test the primary learner and integrated node eigenvector representation.The experimental results show that after the introduction of the integration method,each index improves by approximately 1.47-2.97 times. Keywords:Network represents learning;Ensemble learning;Graph convolution network;Social network;Deep learn- ing;Feature learning;Node embedding;Information network embedding 近年来，基于网络数据结构的深度学习十分络可视化1等下游任务时有着很好的效果，而且 流行，广泛应用于学术领域和工业领域。网络包在金融欺诈、推荐系统等场景下都有实际的应用 括节点和边，其中节点表示实体，边表示节点之 价值。例如，在社交网络中通过节点分类可以对 间的关系。现实世界中很多数据都可以表示为网 不同的用户推荐不同的物品：在生物网络中，可 络，例如社交网络凶、生物-蛋白网络)等。利用 以通过分析已知的疾病与基因关系预测潜在的致 网络分析挖掘有价值的信息备受关注，因为高效 病基因等。 的网络分析不仅处理节点分类四、链路预测回、网 由于网络数据的非欧几里得结构，大多数传 收稿日期：2021-07-23.网络出版日期：2022-03-25 统的网络分析方法不适合使用机器学习技术解 基金项目：国家自然科学基金项目(61906110)；山西财经大学 研究生创新项目(21cxxj088). 决。网络表示学习6很好地解决了上述问题，通 通信作者：常新功.E-mail:c_xg@126.com 过将节点映射到低维空间中，节点用学习生成的
DOI: 10.11992/tis.202107048 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20220324.1345.002.html 基于图卷积集成的网络表示学习 常新功，王金珏 （山西财经大学 信息学院，山西 太原 030006） 摘 要：针对现有网络表示学习方法泛化能力较弱等问题，提出了将 stacking 集成思想应用于网络表示学习的 方法，旨在提升网络表示性能。首先，将 3 个经典的浅层网络表示学习方法 DeepWalk、Node2Vec、Line 作为并 列的初级学习器，训练得到三部分的节点嵌入拼接后作为新数据集；然后，选择图卷积网络 (graph convolutional network, GCN) 作为次级学习器对新数据集和网络结构进行 stacking 集成得到最终的节点嵌入，GCN 处理半监 督分类问题有很好的效果，因为网络表示学习具有无监督性，所以利用网络的一阶邻近性设计损失函数；最 后，设计评价指标分别评价初级学习器和集成后的节点嵌入。实验表明，选用 GCN 集成的效果良好，各评价指 标平均提升了 1.47~2.97 倍。 关键词：网络表示学习；集成学习；图卷积网络；社交网络；深度学习；特征学习；节点嵌入；信息网络嵌入 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2022)03−0547−09 中文引用格式：常新功, 王金珏. 基于图卷积集成的网络表示学习 [J]. 智能系统学报, 2022, 17(3): 547–555. 英文引用格式：CHANG Xingong, WANG Jinjue. Network representation learning using graph convolution ensemble[J]. CAAI transactions on intelligent systems, 2022, 17(3): 547–555. Network representation learning using graph convolution ensemble CHANG Xingong，WANG Jinjue (School of Information, Shanxi University of Finance and Economics, Taiyuan 030006, China) Abstract: Aimed at the weak generalization ability of the existing network representation learning methods, this paper proposes a stacking ensemble method that is applied to network representation learning to improve the performance of network representation. Three classical shallow network representation learning methods, namely, DeepWalk, Node2Vec, and Line, are used initially as parallel primary learners. After training, the embedded representation and three spliced node parts are obtained. Following this, the graph convolutional network (GCN) is selected as the secondary learner to stack and integrate the network structure and the new data set. This is done to obtain the final node embedded representation. GCN efficiently deals with semisupervised classification problems. As network representation learning is unsupervised, the first-order proximity of the network has been used to design the loss function. Finally, evaluation indices are designed to test the primary learner and integrated node eigenvector representation. The experimental results show that after the introduction of the integration method, each index improves by approximately 1.47 –2.97 times. Keywords: Network represents learning; Ensemble learning; Graph convolution network; Social network; Deep learning; Feature learning; Node embedding; Information network embedding 近年来，基于网络数据结构的深度学习十分 流行，广泛应用于学术领域和工业领域。网络包 括节点和边，其中节点表示实体，边表示节点之 间的关系。现实世界中很多数据都可以表示为网 络，例如社交网络[1-2] 、生物–蛋白网络[3] 等。利用 网络分析挖掘有价值的信息备受关注，因为高效 的网络分析不仅处理节点分类[1] 、链路预测[2] 、网 络可视化[4-5] 等下游任务时有着很好的效果，而且 在金融欺诈、推荐系统等场景下都有实际的应用 价值。例如，在社交网络中通过节点分类可以对 不同的用户推荐不同的物品；在生物网络中，可 以通过分析已知的疾病与基因关系预测潜在的致 病基因等。 由于网络数据的非欧几里得结构，大多数传 统的网络分析方法不适合使用机器学习技术解 决。网络表示学习[6-8] 很好地解决了上述问题，通 过将节点映射到低维空间中，节点用学习生成的 收稿日期：2021−07−23. 网络出版日期：2022−03−25. 基金项目：国家自然科学基金项目（61906110）；山西财经大学 研究生创新项目（21cxxj088）. 通信作者：常新功. E-mail：c_x_g@126.com. 第 17 卷第 3 期 智 能 系 统 学 报 Vol.17 No.3 2022 年 5 月 CAAI Transactions on Intelligent Systems May 2022
第17卷 智能系统学报 ·548· 低维、稠密的向量重新表示，同时尽可能保留网 集成方法是对于同一网络并行训练多个较弱的个 络中包含的结构信息。因此，网络被映射到向量 体学习器，每个个体学习器的输出都是网络表示， 空间中就可以使用经典的机器学习技术处理很多 然后采用某种结合策略集成这些输出进而得到更 网络分析问题。现有的网络表示学习方法主要分 好的网络表示。stacking集成方法是集成方法的 为以下3类： 一种，结合策略是学习法，即选用次级学习器集 I)基于矩阵分解的网络表示学习。Roweis等9 成个体学习器的输出。次级学习器的选择是影响 提出的局部线性表示算法(locally linear embeding, 结果的重要因素，现有工作证明Kipf等o提出的 LLE)假设节点和它的邻居节点都处于同一流形 图卷积神经网络l(graph convolutional network, 区域，通过它的邻居节点表示的线性组合近似得 GCN)在提升网络分析性能上有着显著的效果， 到节点表示；He等1o提出的保留局部映射算法 GCN通过卷积层聚合网络中节点及邻居的信息， (locality preserving projections,LPP)通过对非线性 根据归一化拉普拉斯矩阵的性质向邻居分配权 的拉普拉斯特征映射方法进行线性的近似得到节 重，中心节点及邻居信息加权后更新中心节点的 点表示；Tu等川提出的图形分解算法(max mar- 特征表示。 gin deep walk,MMDW)通过对邻接矩阵分解得到 综上所述，本文的贡献有以下几点： 节点表示。Cao等提出的GraRep算法通过保 1)提出了基于stacking集成学习的网络表示 留节点的k阶邻近性保留全局网络结构。 学习，并行训练多个较弱的初级学习器，并将它 2)基于浅层神经网络的网络表示学习。Perozzi 们的网络表示拼接，选用GCN作为次级学习器， 等I]提出的DeepWalk算法通过随机游走遍历网 聚合中心节点及邻居信息得到最终的网络表示， 络中的节点得到有序的节点序列，然后利用Skip- 这样可得到更好的网络表示。 Gram模型预测节点的前后序列学习得到节点的 2)利用网络的一阶邻近性设计了损失函数； 向量表示：Grover等提出的Node2Vec改进了 3)设计了评价指标MRR、Hit@1、Hit@3、 DeepWalk的随机游走过程，通过引进两个参数 Ht@10,分别评价初级学习器和集成后的网络表 p和g控制深度优先搜索和广度优先搜索；Tang 示，验证了提出的算法具有较好的网络表示性 等Ils)提出的Line算法能够处理任意类型的大 能，各评价指标平均提升了1.47~2.97倍。 规模网络，包括有向和无向、有权重和无权重，该 1问题定义 算法保留了网络中节点的一阶邻近性和二阶邻 近性。 定义1给定网络G=<VE>,其中V表示节 3)基于深度学习的网络表示学习。Wang等 点集合，E表示节点之间的边集合，记y,∈V表示一 提出的SDNE算法利用深度神经网络对网络表示 个节点，e,=(,v)∈E表示一条边，由E构建邻接 学习进行建模，将输入节点映射到高度非线性空 矩阵A∈Rmm表示网络的拓扑结构，n=IVⅥ，若 间中获取网络结构信息。Hamilton等1刀提出的 e∈E,则Aj>0,若e生E,则A=0。 GraphSAGE是一种适用于大规模网络的归纳式 定义26给定网络G,每个节点的属性特征 学习方法，通过聚集采样到的邻居节点表示更新 是m维，G有n个节点，则网络G对应的节点特 当前节点的特征表示。Wang等18提出的Grapha- 征矩阵H∈Rm。网络表示学习的目标是根据网 GAN引入对抗生成网络进行网络表示学习。上 络中任意节点y,∈V学习得到低维向量Z∈Rx4,其 述研究方法大多是设计一种有效的模型分别应用 中d冬n。学习到的低维向量表示可客观反映节 不同的数据集学习得到高质量的网络表示，但是 点在原始网络中的结构特性。例如，相似的节点 单一模型的泛化能力较弱。为了解决此问题，目 应相互靠近，不相似的节点应相互远离。 前有学者提出使用集成思想学习网络表示，Zhang 定义3一阶邻近性1。网络中的一阶邻近 等9提出的基于集成学习的网络表示学习，其中 性是指两个节点之间存在边，若节点y,和y,之间 stacking集成分别将GCN和GAE作为初级模型， 存在边，这条边的权重"表示”，和y之间的一 得到两部分节点嵌入拼接后作为节点特征，其与 阶邻近性，若节点y,和y之间没有边，则，和y 原始图数据构成新数据集，最后将三层GCN作为 之间的一阶邻近性为0。 次级模型处理新数据集，使用部分节点标签进行 定义4二阶邻近性1。网络中一对节点 半监督训练。 ’,和y之间的二阶邻近性是指它们的邻域网络结 本文引入了stacking集成方法学习网络表示。 构之间的相似性，令4=(w1,w2,…,wm)表示节点
低维、稠密的向量重新表示，同时尽可能保留网 络中包含的结构信息。因此，网络被映射到向量 空间中就可以使用经典的机器学习技术处理很多 网络分析问题。现有的网络表示学习方法主要分 为以下 3 类： 1) 基于矩阵分解的网络表示学习。Roweis 等 [9] 提出的局部线性表示算法 (locally linear embeding, LLE) 假设节点和它的邻居节点都处于同一流形 区域，通过它的邻居节点表示的线性组合近似得 到节点表示；He 等 [10] 提出的保留局部映射算法 (locality preserving projections, LPP) 通过对非线性 的拉普拉斯特征映射方法进行线性的近似得到节 点表示；Tu 等 [11] 提出的图形分解算法 (max margin deep walk, MMDW) 通过对邻接矩阵分解得到 节点表示。Cao 等 [12] 提出的 GraRep 算法通过保 留节点的 k 阶邻近性保留全局网络结构。 2) 基于浅层神经网络的网络表示学习。Perozzi 等 [13] 提出的 DeepWalk 算法通过随机游走遍历网 络中的节点得到有序的节点序列，然后利用 SkipGram 模型预测节点的前后序列学习得到节点的 向量表示；Grover 等 [14] 提出的 Node2Vec 改进了 DeepWalk 的随机游走过程，通过引进两个参数 p 和 q 控制深度优先搜索和广度优先搜索；Tang 等 [ 1 5 ] 提出的 Line 算法能够处理任意类型的大 规模网络，包括有向和无向、有权重和无权重，该 算法保留了网络中节点的一阶邻近性和二阶邻 近性。 3) 基于深度学习的网络表示学习。Wang 等 [16] 提出的 SDNE 算法利用深度神经网络对网络表示 学习进行建模，将输入节点映射到高度非线性空 间中获取网络结构信息。Hamilton 等 [17] 提出的 GraphSAGE 是一种适用于大规模网络的归纳式 学习方法，通过聚集采样到的邻居节点表示更新 当前节点的特征表示。Wang 等 [18] 提出的 GraphGAN 引入对抗生成网络进行网络表示学习。上 述研究方法大多是设计一种有效的模型分别应用 不同的数据集学习得到高质量的网络表示，但是 单一模型的泛化能力较弱。为了解决此问题，目 前有学者提出使用集成思想学习网络表示，Zhang 等 [19] 提出的基于集成学习的网络表示学习，其中 stacking 集成分别将 GCN 和 GAE 作为初级模型， 得到两部分节点嵌入拼接后作为节点特征，其与 原始图数据构成新数据集，最后将三层 GCN 作为 次级模型处理新数据集，使用部分节点标签进行 半监督训练。 本文引入了 stacking 集成方法学习网络表示。 集成方法是对于同一网络并行训练多个较弱的个 体学习器，每个个体学习器的输出都是网络表示， 然后采用某种结合策略集成这些输出进而得到更 好的网络表示。stacking 集成方法是集成方法的 一种，结合策略是学习法，即选用次级学习器集 成个体学习器的输出。次级学习器的选择是影响 结果的重要因素，现有工作证明 Kipf 等 [20] 提出的 图卷积神经网络[21] (graph convolutional network, GCN) 在提升网络分析性能上有着显著的效果， GCN 通过卷积层聚合网络中节点及邻居的信息， 根据归一化拉普拉斯矩阵的性质向邻居分配权 重，中心节点及邻居信息加权后更新中心节点的 特征表示。 综上所述，本文的贡献有以下几点： 1) 提出了基于 stacking 集成学习的网络表示 学习，并行训练多个较弱的初级学习器，并将它 们的网络表示拼接，选用 GCN 作为次级学习器， 聚合中心节点及邻居信息得到最终的网络表示， 这样可得到更好的网络表示。 2) 利用网络的一阶邻近性设计了损失函数； 3) 设计了评价指标 MRR、Hit@1、Hit@3、 Hit@10，分别评价初级学习器和集成后的网络表 示，验证了提出的算法具有较好的网络表示性 能，各评价指标平均提升了 1.47~2.97 倍。 1 问题定义 G =< V,E > V E vi ∈ V ei, j = (vi , vj) ∈ E E A ∈ R n×n n = |V| ei, j ∈ E Ai, j > 0 ei, j < E Ai, j = 0 定义 1 给定网络 ，其中 表示节 点集合， 表示节点之间的边集合，记 表示一 个节点， 表示一条边，由 构建邻接 矩 阵 表示网络的拓扑结构， ， 若 ，则 ，若 ，则 。 H ∈ R n×m vi ∈ V Z ∈ R n×d d ≪ n 定义 2 [6] 给定网络 G，每个节点的属性特征 是 m 维，G 有 n 个节点，则网络 G 对应的节点特 征矩阵 。网络表示学习的目标是根据网 络中任意节点 学习得到低维向量 ，其 中 。学习到的低维向量表示可客观反映节 点在原始网络中的结构特性。例如，相似的节点 应相互靠近，不相似的节点应相互远离。 定义 3 一阶邻近性[15] 。网络中的一阶邻近 性是指两个节点之间存在边，若节点 vi 和 vj 之间 存在边，这条边的权重 wi,j 表示 vi 和 vj 之间的一 阶邻近性，若节点 vi 和 vj 之间没有边，则 vi 和 vj 之间的一阶邻近性为 0。 li = (wi,1,wi,2,··· ,wi,|V|) 定义 4 二阶邻近性[15] 。网络中一对节点 vi 和 vj 之间的二阶邻近性是指它们的邻域网络结 构之间的相似性，令 表示节点 第 17 卷 智 能 系 统 学 报 ·548·
·549· 常新功，等：基于图卷积集成的网络表示学习 第3期 ,与其他所有节点的一阶邻近性，，和y的二阶 行插值；Line是针对大规模的网络嵌入，可以保 邻近性由，和I的相似性决定。 持一阶和二阶邻近性。图3给出了一个说明示 定义5集成学习四。集成学习是构建多个 例，节点6和节点7之间边的权重较大，即节点 个体学习器(1,2，…，，再用某种结合策略将它 6和节点7有较高的一阶邻近性，它们在嵌入空 们的输出结合起来，结合策略有平均法、投票法 间的距离应很近：虽然节点5和节点6没有直接 和学习法。给定网络G,定义2中的网络表示学 相连的边，但是它们有很多共同的邻居，所以它 习方法可作为个体学习器，其结构如图1。若个体 们有较高的二阶邻近性，在嵌入空间中距离也应 学习器是同种则是同质集成，否则是异质集成。 很近。一阶邻近性和二阶邻近性都很重要，一阶 输出 邻近性可以用两个节点之间的联合概率分布度 量，”，和y的一阶邻近性如式(1)： 结合模块 P(v》= 1+e-对 (1) 评价 Loss 个体学习器 个体学习器2 个体学习器n 卷积层2 最终向量表示 图卷积（次 级学习器) 卷积层1 网络结构G 新特征向量z(N×3D) 图1集成学习结构 邻接矩阵 拼接下 Fig.1 Structure of ensemble learning 嵌入NxD)嵌入NxD)嵌入WxD) 定义6 stacking集成学习。stacking集成 学习的结合策略是学习法，对于同一网络通过 生成 生成 生成 k个初级学习器，2，…，（学习得到k部分节点 初级学习器1 初级学习器2初级学习器3 嵌入的特征向量o,z1,…,k-1,其嵌入维度均为 d维，然后按节点将z,i∈[0，k-1]对应拼接得到嵌 网络结构 入z,其嵌入维度是k×d维，最后使用次级学习器 图2基于GCN集成的网络表示学习结构 得到最终的嵌入z',为了方便对比设置其嵌入维 Fig.2 Network representation learning structure based on 度也是d维。 GCN ensemble method 2基于GCN集成的网络表示学习方法 本文将stacking集成思想引人网络表示学习， 对于同一网络数据基于3个初级学习器生成3部 分嵌入并将其拼接，然后选取GCN作为次级学习 器得到最终的嵌入，最后使用评价指标进行评 价，具体流程如图2所示。 2.1初级学习器 图3网络简单示例 初级学习器选择DeepWalk!)、Node2Vec Fig.3 Simple example of network 和Line。DeepWalk!1发现在短的随机游走中 二阶邻近性通过节点y,的上下文节点y的概 出现的节点分布类似于自然语言中的单词分布，于 率建模，即 是采用广泛使用的单词表示学习模型Skip-Gram e 模型学习节点表示；Node2Vec认为DeepWalk P2(v)= 的表达能力不足以捕捉网络中连接的多样性，所 以设计了一个灵活的网络邻域概念，并设计随机 条件分布意味着在上下文中具有相似分布的 游走策略对邻域节点采样，该策略能平滑地在广 节点彼此相似，通过最小化两种分布和经验分布 度优先采样(BFS)和深度优先采样(DFS)之间进 的KL散度，可以得到既保持一阶邻近性又保持
vi 与其他所有节点的一阶邻近性，vi 和 vj 的二阶 邻近性由 li 和 lj 的相似性决定。 ℓ1 ℓ2 ℓn 定义 5 集成学习[22] 。集成学习是构建多个 个体学习器 ， ，…， ，再用某种结合策略将它 们的输出结合起来，结合策略有平均法、投票法 和学习法。给定网络 G，定义 2 中的网络表示学 习方法可作为个体学习器，其结构如图 1。若个体 学习器是同种则是同质集成，否则是异质集成。 输出 结合模块 个体学习器 1 个体学习器 2 网络结构 G 个体学习器 n ... 图 1 集成学习结构 Fig. 1 Structure of ensemble learning ℓ1 ℓ2 ℓk zi，i ∈ [0, k−1] ℓ 定义 6 stacking 集成学习[22]。 stacking 集成 学习的结合策略是学习法，对于同一网络通过 k 个初级学习器 ， ，…， 学习得到 k 部分节点 嵌入的特征向量 z0，z1，…，zk−1，其嵌入维度均为 d 维，然后按节点将 对应拼接得到嵌 入 z，其嵌入维度是 k×d 维，最后使用次级学习器 得到最终的嵌入 z'，为了方便对比设置其嵌入维 度也是 d 维。 2 基于 GCN 集成的网络表示学习方法 本文将 stacking 集成思想引入网络表示学习， 对于同一网络数据基于 3 个初级学习器生成 3 部 分嵌入并将其拼接，然后选取 GCN 作为次级学习 器得到最终的嵌入，最后使用评价指标进行评 价，具体流程如图 2 所示。 2.1 初级学习器 初级学习器选择 DeepWalk[13] 、Node2Vec[14] 和 Line[15]。DeepWalk[13] 发现在短的随机游走中 出现的节点分布类似于自然语言中的单词分布，于 是采用广泛使用的单词表示学习模型 Skip-Gram 模型学习节点表示；Node2Vec[14] 认为 DeepWalk 的表达能力不足以捕捉网络中连接的多样性，所 以设计了一个灵活的网络邻域概念，并设计随机 游走策略对邻域节点采样，该策略能平滑地在广 度优先采样 (BFS) 和深度优先采样 (DFS) 之间进 行插值；Line[15] 是针对大规模的网络嵌入，可以保 持一阶和二阶邻近性。图 3 给出了一个说明示 例，节点 6 和节点 7 之间边的权重较大，即节点 6 和节点 7 有较高的一阶邻近性，它们在嵌入空 间的距离应很近；虽然节点 5 和节点 6 没有直接 相连的边，但是它们有很多共同的邻居，所以它 们有较高的二阶邻近性，在嵌入空间中距离也应 很近。一阶邻近性和二阶邻近性都很重要，一阶 邻近性可以用两个节点之间的联合概率分布度 量，vi 和 vj 的一阶邻近性如式 (1)： p1(vi , vj) = 1 1+e −z T i zj (1) 评价 卷积层 2 卷积层 1 新特征向量 z (N×3D) 邻接矩阵 图卷积 (次 级学习器) 拼接 生成 生成 初级学习器 1 初级学习器 2 初级学习器 3 网络结构 嵌入 (N×D) 嵌入 (N×D) 嵌入 (N×D) 生成 最终向量表示 Loss 图 2 基于 GCN 集成的网络表示学习结构 Fig. 2 Network representation learning structure based on GCN ensemble method 6 7 10 9 5 8 1 2 3 4 图 3 网络简单示例 Fig. 3 Simple example of network 二阶邻近性通过节点 vi 的上下文节点 vj 的概 率建模，即 p2(vj |vi) = e z T j zi ∑ k e z T k zi 条件分布意味着在上下文中具有相似分布的 节点彼此相似，通过最小化两种分布和经验分布 的 KL 散度，可以得到既保持一阶邻近性又保持 ·549· 常新功，等：基于图卷积集成的网络表示学习 第 3 期
第17卷 智能系统学报 ·550· 二阶邻近性的节点表示。 i的邻居数量，节点i的邻居j的邻居数量多，所以 2.2次级学习器 节点i对邻居j的影响小。 引入stacking集成方法学习网络表示，选择 然后，GCN的整体结构如图5所示，用式 DeepWalk!、Node2Vec和Line作为初级学习 (3)、(4)描述： 器。若初级学习器是同种的则为同质集成，否则 f(z',A)=ReLU(Az'W) (3) 为异质集成。3个初级学习器学习得到的嵌人分 z=f(fo,A)=tanh(Afow) (4) 别是z1、2、z,且维数均设为d,并将z1、2、z3拼接 式中：如式(3)所示计算，设计了两层卷积层，第 得到嵌入z,维数为3×d。这个过程中不使用节点 一层使用ReLU激活函数，第二层使用tanh激活 的铺助信息，仅利用网络的拓扑结构学习节点的 函数，W©，和W是需要训练的权重矩阵，最终 特征表示。选用GCN图卷积网络模型2作为 得到输出z。对于网络G=<VE>,这里的GCN是 stacking的次级学习器，学习得到最终的嵌入z, 基于空域的图卷积网络，其时间复杂度为O(EHTF), 维数是d。 H是输入特征维数384，T是中间层维数256，F是 GCN模型的输人有两部分，若网络G有N个 输出层维数128。 节点，则一部分是嵌入，每个节点有H维，其大 小为N×H,另一部分是网络G的邻接矩阵A,其 大小为N×N。首先，通过计算得到归一化矩阵 A∈Rxm,如式(2)： A=D生AD生 (2) G 式中：A=A+I,I∈Rm是单位矩阵；D是A的度矩 阵。拉普拉斯矩阵有良好的性质，下面针对对称 归一化拉普拉斯矩阵作详解。D-A即根据邻居 GCN 个数取平均，D-PA12是对称归一化拉普拉斯 矩阵，其与DA的对比示例如图4所示。 Loss 图5图卷积集成网络模型结构 Fig.5 Structure of GCN ensemble model 2.3 损失函数 利用网络的一阶邻近性设计损失函数，根据 噪声分布对边采样负边，任意边的损失函数为 2001 3001 :001 D=0 0 0 D-1=0 0 -logr(z·z,）+ E-wlog2·zl】 K (5) 001 002 100 式中：第一项是根据观测到的边即正例的Ioss;第 66 二项是为正例采样的负例的Ioss;K是负边的个 0 6 0 数；r(x)=1/1+exp(-x)是sigmoid函数；设置P.()c 0 d4,其在文献[23]中提出，d,是节点v的出度。 边采样根据边的权重选用alias table!方法 图4拉普拉斯矩阵示例 进行，从alias table中采样一条边的时间复杂度是 Fig.4 Example of Laplacian matrix O1),负采样的时间复杂度是O(d(K+1),d表示出 与DA相比，D-PADP是对称矩阵，改变的 度，K表示K条负边，所以每步的时间复杂度是 值含义如下：节点1有两个邻居节点2、3，但是节 O(dK),步数的多少取决于边的数量E卧，因此计算 点2、3分别只有一个邻居，所以节点1对节点2、 损失的时间复杂度为OdKE),与节点数量N无 3影响要大一点，对应矩阵中第一行第二列和第 关。此边采样策略在不影响准确性的情况下提高 三列，由/3变为16，其值变大了；节点3的邻居 了效率。 只有节点1，但是节点1有两个邻居，所以节点 2.4评价指标 3对节点1的影响要小一点，对应矩阵中第三行 通过2.3节损失函数影响模型的训练学习， 第一列，由/2变为16，其值变小了。相比节点 得到最终的网络嵌入表示z,对于网络表示学习
二阶邻近性的节点表示。 2.2 次级学习器 引入 stacking 集成方法学习网络表示，选择 DeepWalk[13] 、Node2Vec[14] 和 Line[15] 作为初级学习 器。若初级学习器是同种的则为同质集成，否则 为异质集成。3 个初级学习器学习得到的嵌入分 别是 z1、z2、z3，且维数均设为 d，并将 z1、z2、z3 拼接 得到嵌入 z'，维数为 3×d。这个过程中不使用节点 的辅助信息，仅利用网络的拓扑结构学习节点的 特征表示。选用 GCN 图卷积网络模型[21] 作为 stacking 的次级学习器，学习得到最终的嵌入 z， 维数是 d。 Aˆ ∈ R n×n GCN 模型的输入有两部分，若网络 G 有 N 个 节点，则一部分是嵌入 z'，每个节点有 H 维，其大 小为 N×H，另一部分是网络 G 的邻接矩阵 A，其 大小为 N×N。首先，通过计算得到归一化矩阵 ，如式 (2)： Aˆ = D − 1 2 AD˜ − 1 2 (2) A˜ = A+ I I ∈ R n×n A˜ Dˆ −1Aˆ Dˆ −1/2Aˆ Dˆ −1/2 Dˆ −1Aˆ 式中： ， 是单位矩阵；D 是 的度矩 阵。拉普拉斯矩阵有良好的性质，下面针对对称 归一化拉普拉斯矩阵作详解。 即根据邻居 个数取平均， 是对称归一化拉普拉斯 矩阵，其与 的对比示例如图 4 所示。 A= 0 1 1 1 0 0 1 0 , 0 A= 1 1 1 1 1 0 1 0 , 1 ^ D= 2 0 0 0 1 0 0 0 , 1 D= 3 0 0 0 2 0 0 0 , 2 ^ D−1= 0 0 0 0 0 0 ^ 2 1 3 1 2 1 D−1 A= 0 0 , ^ ^ 2 1 3 1 3 1 3 1 2 1 2 1 2 1 0 0 2 1 3 1 2 1 √￣6 1 √￣6 1 √￣6 1 √￣6 1 D AD = ^ ^ ^ 2 1 2 1 − − 1 2 3 [ ] [ ] [ ] [ ] [ ] [ ] [ ] 图 4 拉普拉斯矩阵示例 Fig. 4 Example of Laplacian matrix Dˆ −1Aˆ Dˆ −1/2Aˆ Dˆ −1/2 1/ 3 1 / √ 6 1/ 2 1 / √ 6 与 相比， 是对称矩阵，改变的 值含义如下：节点 1 有两个邻居节点 2、3，但是节 点 2、3 分别只有一个邻居，所以节点 1 对节点 2、 3 影响要大一点，对应矩阵中第一行第二列和第 三列，由 变为 ，其值变大了；节点 3 的邻居 只有节点 1，但是节点 1 有两个邻居，所以节点 3 对节点 1 的影响要小一点，对应矩阵中第三行 第一列，由 变为 ，其值变小了。相比节点 i 的邻居数量，节点 i 的邻居 j 的邻居数量多，所以 节点 i 对邻居 j 的影响小。 然后， GCN 的整体结构如图 5 所示，用式 (3)、(4) 描述： f (0)(z ′ , A) = ReLU(Azˆ ′W(0)) (3) z = f (1)(f (0) , A) = tanh(Aˆ f (0)W(1)) (4) G =< V,E > O(|E|HT F) 式中：Â如式 (3) 所示计算，设计了两层卷积层，第 一层使用 ReLU 激活函数，第二层使用 tanh 激活 函数，W (0) 和 W (1) 是需要训练的权重矩阵，最终 得到输出 z。对于网络 ，这里的 GCN 是 基于空域的图卷积网络，其时间复杂度为 ， H 是输入特征维数 384，T 是中间层维数 256，F 是 输出层维数 128。 G A z 拼接 W0 W1 GCN Loss f (1) f (0) G G z2 z1 z ′ z0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 图 5 图卷积集成网络模型结构 Fig. 5 Structure of GCN ensemble model 2.3 损失函数 利用网络的一阶邻近性设计损失函数，根据 噪声分布对边采样负边，任意边的损失函数为 −logσ(zT i · zj)+ 1 K ∑K i=1 Evn∼Pn (v)[logσ(z T i · zn)] (5) σ(x) = 1/(1+exp(−x)) Pn(v) ∝ d 3/4 v dv v 式中：第一项是根据观测到的边即正例的 loss；第 二项是为正例采样的负例的 loss；K 是负边的个 数； 是 sigmoid 函数；设置 ，其在文献 [23] 中提出， 是节点 的出度。 O(1) O(d(K +1)) O(dK) |E| O(dK|E|) 边采样根据边的权重选用 alias table[15] 方法 进行，从 alias table 中采样一条边的时间复杂度是 ，负采样的时间复杂度是 ，d 表示出 度，K 表示 K 条负边，所以每步的时间复杂度是 ，步数的多少取决于边的数量 ，因此计算 损失的时间复杂度为 ，与节点数量 N 无 关。此边采样策略在不影响准确性的情况下提高 了效率。 2.4 评价指标 通过 2.3 节损失函数影响模型的训练学习， 得到最终的网络嵌入表示 z，对于网络表示学习 第 17 卷 智 能 系 统 学 报 ·550·
·551· 常新功，等：基于图卷积集成的网络表示学习 第3期 的无监督性，设计评价指标2网评价网络表示学习 10)output tanh(X3) 的好坏。对于节点：和y之间的边即一个正例， 11)loss(output) 由一对节点(v。)表示，一个正例对应采样K条 12)Backpropagation(loss) 负边，即采样K个点(1,2，…，)，其中i,j(1,K), 13)更新output,.⊙ 构成负例集合{(y,n),(,2),…,(v,n}。 14)end for 衡量一对节点的相似度可计算它们网络表示 15)返▣output 的内积，正例(，)的相似度s=·z,负例的相似 训练阶段进行模型计算和损失计算，所以训 度5p=z2,p=(1,2,…,K),相似值越大越好，所 练阶段的时间复杂度是O(EHTF+dKED,测试阶 以将sp的值由大到小排序，记录s插入{sp}的索 段的时间复杂度是O(KED),其中H是特征输入维 引ranking,索引是从0开始的，衡量指标需要的 数384，T为中间层维数256，F为输出层维数128， 是排名位置，所以令ranking-=ranking+l,ranking越 数据边的数量是E,测试数据边的数量是E。综 小说明网络表示学习的嵌入越有效。 上所述，总体时间复杂度是O(EHTF+dKE)。 上文针对一个正例计算得到了一个ranking,. 3 实验和结果分析 对于整个网络设计指标如表1所示。 表1评价指标 在6个数据集上分别对比DeepWalk、Node Table 1 Evaluating indicator 2Vec、Line这3个经典的网络表示学习方法和 评价指标 含义 stacking集成后的实验效果，验证GCN作为stack-. ing集成次级学习器的有效性。实验环境为：Win- MRR 所有ranking的倒数的平均值 dows10操作系统，Intel i7-67002.6 GHz CPU,nvidia Hit@1/3/10 ranking在负例相似度排名的前1/3/10个 GeForce GTX950MGPU,8GB内存。编写Py- 评价数据边的数量为E1,时间复杂度为 thon和Pytorch实现。 OKED。 3.1 实验设定 2.5算法描述 1)数据集 基于图卷积集成的网络表示主要包括3个步骤 实验使用6个真实数据集，即Cora、Citeseer、 首先得到初级学习器的网络表示，然后用stack- Pubmed、Wiki-Vote、P2P.Gnutella05和Email-En- ing集成，其中次级学习器选用GCN。对于网络 ron,详细信息见表2。Cora是引文网络，由机器 表示学习的无监督性在GCN模型中设计了损失 学习论文组成，每个节点代表一篇论文，论文根 函数，也设计了其测试指标，相关算法如算法1 据论文的主题分为7类，边代表论文间的引用关 所示。 系。Citeseer也是引文网络，是从Citeseer数字论 算法1基于图卷积集成的网络表示 文图书馆中选取的一部分论文，该网络被分为 输入网络G=(V,E),窗口大小w,节点表示 6类，边代表论文间的引用关系。Pubmed数据集 向量维度d,每个节点随机游走次数y,随机游走 包括来自Pubmed数据库的关于糖尿病的科学出 序列长度t,节点个数size,邻近性阶数order,超参 版物，被分为3类。Wiki-Vote是社交网络，数据 集包含从Wikipedia创建到2008年1月的所有 数p控制节点随机游走回溯概率，超参数q控制 Wikipedia投票数据。网络中的节点表示Wikipe- BFS和DFS,数据集文件datafile,.训练轮数epoch,. dia用户，从节点i到节点j的定向边表示用户i给 GCN参数O; 用户j的投票。P2P-Gnutella05是因特网点对点网 输出网络表示output。. 络，数据集是从2002年8月开始的Gnutella点对 1)z=DeepWalk(G,w,y,t,d) 点文件共享网络的一系列快照，共收集了9个 2)z2=Node2Vec(G,w,y,t,d.p,q) Gnutella网络快照。节点表示Gnutella网络拓扑 3)z3=Line(size,d,order) 中的主机，边表示Gnutella主机之间的连接。 4)X=Concatenate(z1,Z2,Z3) Email-Enron是安然公司管理人员的电子邮件通 5)A=load date(datafile) 信网络，覆盖了大约50万封电子邮件数据集中的 6)for each epoch do: 所有电子邮件通信，这些数据最初是由联邦能源 7)XI GraphConvolution(X,A, 管理委员会在调查期间公布在网上的，网络的节 8)X2 ReLU(X) 点是电子邮件地址，边表示电子邮件地址之间的 9)X3 GraphConvolution(X2,A,) 通信
(n1,n2,··· ,nk) i, j < (1,K) {(vi ,n1),(vi ,n2),··· ,(vi ,nk)} 的无监督性，设计评价指标[24] 评价网络表示学习 的好坏。对于节点 vi 和 vj 之间的边即一个正例， 由一对节点 (vi , vj ) 表示，一个正例对应采样 K 条 负边，即采样 K 个点 ，其中 ， 构成负例集合 。 (vi , vj) s = zi · z T j sp = zi · z T np p = (1,2,··· ,K) 衡量一对节点的相似度可计算它们网络表示 的内积，正例 的相似度 ，负例的相似 度 ， ，相似值越大越好，所 以将 sp 的值由大到小排序，记录 s 插入{sp}的索 引 ranking，索引是从 0 开始的，衡量指标需要的 是排名位置，所以令 ranking=ranking+1，ranking 越 小说明网络表示学习的嵌入越有效。 上文针对一个正例计算得到了一个 ranking， 对于整个网络设计指标如表 1 所示。 表 1 评价指标 Table 1 Evaluating indicator 评价指标 含义 MRR 所有ranking的倒数的平均值 Hit@1/3/10 ranking在负例相似度排名的前1/3/10个 |E ’ | O(K|E ’ |) 评价数据边的数量为 ，时间复杂度为 。 2.5 算法描述 基于图卷积集成的网络表示主要包括 3 个步骤， 首先得到初级学习器的网络表示，然后用 stacking 集成，其中次级学习器选用 GCN。对于网络 表示学习的无监督性在 GCN 模型中设计了损失 函数，也设计了其测试指标，相关算法如算法 1 所示。 算法 1 基于图卷积集成的网络表示 γ Θ 输入 网络 G=(V,E)，窗口大小 w，节点表示 向量维度 d，每个节点随机游走次数 ，随机游走 序列长度 t，节点个数 size，邻近性阶数 order，超参 数 p 控制节点随机游走回溯概率，超参数 q 控制 BFS 和 DFS，数据集文件 datafile，训练轮数 epoch， GCN 参数 ； 输出 网络表示 output。 1) z1 = DeepWalk(G,w, γ,t,d) 2) z2 = Node2Vec(G,w, γ,t,d, p,q) 3) z3 = Line(size,d,order) 4) X = Concatenate(z1,z2,z3) 5) Aˆ = load_date(datafile) 6) for each epoch do: X1 = GraphConvolution1(X, Aˆ 7) ,Θ) 8) X2 = ReLU(X1) X3 = GraphConvolution2(X2, Aˆ 9) ,Θ) 10) output = tanh(X3) 11) loss(output) 12) Backpropagation(loss) 13) 更新 output,Θ 14) end for 15) 返回 output O(|E|HT F +dK|E|) O(K|E ′ |) |E| |E ′ | O(|E|HT F +dK|E|) 训练阶段进行模型计算和损失计算，所以训 练阶段的时间复杂度是 ，测试阶 段的时间复杂度是 ，其中 H 是特征输入维 数 384，T 为中间层维数 256，F 为输出层维数 128， 数据边的数量是 ，测试数据边的数量是 。综 上所述，总体时间复杂度是 。 3 实验和结果分析 在 6 个数据集上分别对比 DeepWalk、Node 2Vec、Line 这 3 个经典的网络表示学习方法和 stacking 集成后的实验效果，验证 GCN 作为 stacking 集成次级学习器的有效性。实验环境为：Windows10 操作系统，Intel i7-6700 2.6 GHz CPU，nvidia GeForce GTX 950M GPU，8 GB 内存。编写 Python 和 Pytorch 实现。 3.1 实验设定 1) 数据集 实验使用 6 个真实数据集，即 Cora、Citeseer、 Pubmed、Wiki-Vote、P2P-Gnutella05 和 Email-Enron，详细信息见表 2。Cora 是引文网络，由机器 学习论文组成，每个节点代表一篇论文，论文根 据论文的主题分为 7 类，边代表论文间的引用关 系。Citeseer 也是引文网络，是从 Citeseer 数字论 文图书馆中选取的一部分论文，该网络被分为 6 类，边代表论文间的引用关系。Pubmed 数据集 包括来自 Pubmed 数据库的关于糖尿病的科学出 版物，被分为 3 类。Wiki-Vote 是社交网络，数据 集包含从 Wikipedia 创建到 2008 年 1 月的所有 Wikipedia 投票数据。网络中的节点表示 Wikipedia 用户，从节点 i 到节点 j 的定向边表示用户 i 给 用户 j 的投票。P2P-Gnutella05 是因特网点对点网 络，数据集是从 2002 年 8 月开始的 Gnutella 点对 点文件共享网络的一系列快照，共收集了 9 个 Gnutella 网络快照。节点表示 Gnutella 网络拓扑 中的主机，边表示 Gnutella 主机之间的连接。 Email-Enron 是安然公司管理人员的电子邮件通 信网络，覆盖了大约 50 万封电子邮件数据集中的 所有电子邮件通信，这些数据最初是由联邦能源 管理委员会在调查期间公布在网上的，网络的节 点是电子邮件地址，边表示电子邮件地址之间的 通信。 ·551· 常新功，等：基于图卷积集成的网络表示学习 第 3 期