第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201905045 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190902.1139.006html 基于多粒度结构的网络表示学习 张蕾2，钱峰2，赵姝'，陈洁，张燕平，刘峰 (1.安徽大学计算机科学与技术学院，安徽合肥230601：2.铜陵学院数学与计算机学院，安徽铜陵244061) 摘要：图卷积网络(GCN)能够适应不同结构的图，但多数基于GCN的方法难以有效地捕获网络的高阶相 似性。简单添加卷积层将导致输出特征过度平滑并使它们难以区分，而且深层神经网络更难训练。本文选择 将网络的多粒度结构和图卷积网络结合起来用于学习网络的节点特征表示，提出基于多粒度结构的网络表示 学习方法Mt-GS。首先，基于模块度聚类和粒计算思想，用分层递阶的多粒度空间替代原始的单层网络拓扑 空间：然后，利用GCN模型学习不同粗细粒度空间中粒的表示；最后，由粗到细将不同粒的表示组合为原始空 间中节点的表示。实验结果表明：Mt-GS能够捕获多种结构信息，包括一阶和二阶相似性、社团内相似性（高 阶结构)和社团间相似性（全局结构）。在绝大多数情况下，使用多粒度的结构可改善节点分类任务的分类 效果。 关键词：网络表示学习；网络拓扑；模块度增量；网络粒化；多粒度结构：图卷积网络：节点分类：链接预测 中图分类号：TN929.12文献标志码：A文章编号：1673-4785(2019)06-1233-10 中文引用格式：张蕾，钱峰，赵姝，等.基于多粒度结构的网络表示学习智能系统学报，2019,14(6)：1233-1242. 英文引用格式：ZHANG Lei,QIAN Feng,ZHAO Shu,etal.Network representation learning based on multi-granularity structure[J.CAAI transactions on intelligent systems,2019,14(6):1233-1242. Network representation learning based on multi-granularity structure ZHANG Lei2,QIAN Feng2,ZHAO Shu',CHEN Jie',ZHANG Yanping',LIU Feng' (1.School of Computer Science and Technology,Anhui University,Hefei 230601,China;2.School of Mathematics and Computer Science,Tongling University,Tongling 244061,China) Abstract:The Graph Convolution Network(GCN)can adapt to graphs with different structures.However,most GCN- based models have difficulty effectively capturing the high-order similarity of the network.Simply adding a convolu- tion layer will cause the output features to be too smooth and difficult to distinguish.Moreover,the deep neural network is more difficult to train.In this paper,multi-granularity structure and a GCN are combined to represent the node charac- teristics of the learning network.A multi-granularity structure-based network representation learning method,Multi-GS, is proposed.First,based on the idea of modularity clustering and granular computing,hierarchical multi-granularity space was used to replace the original single-layer network topology space.The GCN model was then used to learn the representation of granules in different coarse-and fine-granularity spaces.Finally,representations of the different grains were combined into representations of nodes in the original space from coarse to fine.Experimental results showed that multi-GS can capture a variety of structural information,including first-order and second-order similarity,intra-com- munity similarity (high-order structure),and inter-community similarity (global structure).In most cases,using multi- granularity structure can improve the classification performance of node classification tasks. Keywords:network represent learning;network topology;modularity increment;network coarsening;multi-granularity structure;Graph Convolution Network;node classification;link prediction 研究人员常用网络（图）描述不同学科领域中 收稿日期：2019-05-23.网络出版日期：2019-09-02 基金项目：国家自然科学基金项目(61876001,61602003， 实体间的交互关系，例如生物学领域中的蛋白质 61673020):中国国防科技创新区规划项目(2017： 0001-863015-0009):国家重点研究与发展项目 互联网络，社会学领域中的社交网络，语言学领 (2017YFB1401903):安徽省自然科学基金项目 域中的词共现网络。结合不同的分析任务对网络 (1508085MF113.1708085QF156). 通信作者：赵蛛.E-mail:zhaoshuzs2002@hotmail.com 进行研究、探索，进而挖掘出隐藏在网络数据中
DOI: 10.11992/tis.201905045 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190902.1139.006.html 基于多粒度结构的网络表示学习 张蕾1,2，钱峰1,2，赵姝1 ，陈洁1 ，张燕平1 ，刘峰1 （1. 安徽大学 计算机科学与技术学院，安徽 合肥 230601; 2. 铜陵学院 数学与计算机学院，安徽 铜陵 244061） 摘 要：图卷积网络 (GCN) 能够适应不同结构的图，但多数基于 GCN 的方法难以有效地捕获网络的高阶相 似性。简单添加卷积层将导致输出特征过度平滑并使它们难以区分，而且深层神经网络更难训练。本文选择 将网络的多粒度结构和图卷积网络结合起来用于学习网络的节点特征表示，提出基于多粒度结构的网络表示 学习方法 Multi-GS。首先，基于模块度聚类和粒计算思想，用分层递阶的多粒度空间替代原始的单层网络拓扑 空间；然后，利用 GCN 模型学习不同粗细粒度空间中粒的表示；最后，由粗到细将不同粒的表示组合为原始空 间中节点的表示。实验结果表明：Multi-GS 能够捕获多种结构信息，包括一阶和二阶相似性、社团内相似性 (高 阶结构) 和社团间相似性 (全局结构)。在绝大多数情况下，使用多粒度的结构可改善节点分类任务的分类 效果。 关键词：网络表示学习；网络拓扑；模块度增量；网络粒化；多粒度结构；图卷积网络；节点分类；链接预测 中图分类号：TN929.12 文献标志码：A 文章编号：1673−4785(2019)06−1233−10 中文引用格式：张蕾, 钱峰, 赵姝, 等. 基于多粒度结构的网络表示学习 [J]. 智能系统学报, 2019, 14(6): 1233–1242. 英文引用格式：ZHANG Lei, QIAN Feng, ZHAO Shu, et al. Network representation learning based on multi-granularity structure[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1233–1242. Network representation learning based on multi-granularity structure ZHANG Lei1,2 ，QIAN Feng1,2 ，ZHAO Shu1 ，CHEN Jie1 ，ZHANG Yanping1 ，LIU Feng1 (1. School of Computer Science and Technology, Anhui University, Hefei 230601, China; 2. School of Mathematics and Computer Science, Tongling University, Tongling 244061, China) Abstract: The Graph Convolution Network (GCN) can adapt to graphs with different structures. However, most GCNbased models have difficulty effectively capturing the high-order similarity of the network. Simply adding a convolution layer will cause the output features to be too smooth and difficult to distinguish. Moreover, the deep neural network is more difficult to train. In this paper, multi-granularity structure and a GCN are combined to represent the node characteristics of the learning network. A multi-granularity structure-based network representation learning method, Multi-GS, is proposed. First, based on the idea of modularity clustering and granular computing, hierarchical multi-granularity space was used to replace the original single-layer network topology space. The GCN model was then used to learn the representation of granules in different coarse- and fine-granularity spaces. Finally, representations of the different grains were combined into representations of nodes in the original space from coarse to fine. Experimental results showed that multi-GS can capture a variety of structural information, including first-order and second-order similarity, intra-community similarity (high-order structure), and inter-community similarity (global structure). In most cases, using multigranularity structure can improve the classification performance of node classification tasks. Keywords: network represent learning; network topology; modularity increment; network coarsening; multi-granularity structure; Graph Convolution Network; node classification; link prediction 研究人员常用网络 (图) 描述不同学科领域中 实体间的交互关系，例如生物学领域中的蛋白质 互联网络，社会学领域中的社交网络，语言学领 域中的词共现网络。结合不同的分析任务对网络 进行研究、探索，进而挖掘出隐藏在网络数据中 收稿日期：2019−05−23. 网络出版日期：2019−09−02. 基金项目：国家自然科学基金项 目 (61876001， 61602003， 61673020)；中国国防科技创新区规划项目 (2017- 0001-863015-0009)；国家重点研究与发展项 目 (2017YFB1401903)；安徽省自然科学基金项 目 (1508085MF113，1708085QF156). 通信作者：赵姝. E-mail：zhaoshuzs2002@hotmail.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019
·1234· 智能系统学报 第14卷 的信息，使之服务于人类。不过，真实场景中的 当前方法依然是浅层结构。例如，GCN阁实际上 网络数据通常具有稀疏、高维等特质，直接利用 只使用两层结构，更多的卷积层甚至可能会损害 这样的数据进行分析通常有较高的计算复杂度， 方法的性能。而且随着模型层数的增加，学习 使得许多先进的研究成果无法直接应用到现实的 到的节点特征可能过度平滑，使得不同簇的节点 网络环境中。 变得无法区分。这样的限制违背使用深层模型的 网络表示学习四(network representation learn- 目的，导致利用GCN模型进行网络表示学习不利 ing,NRL)是解决上述问题的有效方法，旨在保留 于捕获节点的高阶和全局特征。 结构信息的前提下，为网络中的每个节点学习一 为克服这种限制，受商空间四中的分层递阶2四 个低维、稠密的向量表示。如此，网络被映射到 思想的启发，提出一种基于多粒度结构的网络表 一个向量空间中，并可通过许多经典的基于向量 示学习方法(network representation learning based 的机器学习技术处理许多网络分析任务，如节点 on multi-granularity structure,Multi-GS).Multi- 分类回、链接预测、节点聚类、可视化刊、推荐等。 GS首先基于模块度22和粒计算21的思想，利用 网络表示学习不仅要解决网络数据的高维和 网络自身的层次结构，即社团结构，通过使用局 稀疏的问题，还需使学习到的节点特征表示能够 部模块度增量迭代地移动和合并网络中的节点， 保留丰富的网络结构信息。网络中的节点结构大 构造网络的粗粒度结构。利用粗粒度的结构生成 致分为三类：1)微观结构，即局部相似性，例如： 更粗粒度的结构，反复多次，最终获得分层递阶 一阶相似性（相邻）、二阶相似性（有共同的邻 的多粒度网络结构。在多粒度结构中，不同粗细 居)。2)中观结构，例如：角色相似性（承担相同的 的粒能够反映节点在不同粒度空间上的社团内邻 功能)、社团相似性（属于同一社团）。3)宏观结 近关系。然后，Multi-GS使用无监督的GCN模型 构，即全局网络特性，例如：无标度（度分布符合 分别学习不同粒度空间中粒的特征表示向量，学 幂律分布)特性、小世界（高聚类系数）特性。 习到的特征能够反映不同粒度下粒间的邻近关 为获取有效的节点表示，结合最先进的机器 系，不同粗细粒度中的粒间关系能够表示不同阶 学习、深度学习等技术，已提出各种各样的网络 的节点关系，粒度越粗阶数越高。最后，Multi- 表示学习方法。DeepWalk!和Node2VecI通过 GS将不同粒度空间中学习到的粒特征表示按照 随机游走获取节点的局部相似性。GraRep和 由粗到细的顺序进行逐层细化拼接，输出最细粒 Walklets通过将邻接矩阵提升到k次幂获取节 度空间中拼接后的粒特征表示作为初始网络的节 点的k阶相似性。DNGR通过随机冲浪策略获 点特征表示。实验结果表明，结合多粒度结构能 取节点高阶相似性。Struc:2 Vecl21通过构造层次 使GCN有效地捕获网络的高阶特征，学习的节点 加权图，并利用层次加权图上的随机游走获取节 表示可提升诸如节点分类任务的性能。 点的结构相似性。M-NMF1通过融合模块度4 (modularity)的非负矩阵分解(nonnegative matrix 1问题定义 factor,NMF)方法，将社团结构信息纳入网络表示 定义1设网络G=(WE,A,其中，V代表节 学习中。Graph Wavels通过谱图小波的扩散获取 点集合，E代表边集合，A代表邻接矩阵。记 节点的角色结构相似性。HARP通过随机合并 ∈V代表一个节点，e=(,v)eE代表一条边， 网络中相邻节点，迭代地将网络粗化为一系列简 邻接矩阵A∈R表示网络的拓扑结构，n=VⅥ， 化的网络，然后基于这些简化的网络递归地构建 若e∈E,则A=w>0;若eE,则A=0。记 节点向量，从而捕获网络的全局特征。 最近，图卷积网络m(graph convolutional net- d)=∑A代表节点的度，T)=veeE代 表节点的邻居节点集合。 works,.GCN)越来越受到关注，已经显示GCN对 定义2网络的模块度Q定义为 网络分析任务性能的改进有着显著的效果。 GCN通过卷积层聚合网络中每个节点及其邻居 0=2m (1)】 节点的特征，输出聚合结果的加权均值用于该节 式中：m表示网络中的边的总数：l表示社团c中 点新的特征表示。通过卷积层的不断叠加，节点 能够整合k阶邻居信息，从而获取更高阶的节点 所有内部边的总数，∑A;D.表示社团c中所有 特征表示。尽管GCN的设计目标是利用深层模 节点的度的总和；C表示所有社团构成的集合。 型更好地学习网络中节点的特征表示，但大多数 在社团挖掘任务中，通常使用模块度评价社团划
的信息，使之服务于人类。不过，真实场景中的 网络数据通常具有稀疏、高维等特质，直接利用 这样的数据进行分析通常有较高的计算复杂度， 使得许多先进的研究成果无法直接应用到现实的 网络环境中。 网络表示学习[1] (network representation learning，NRL) 是解决上述问题的有效方法，旨在保留 结构信息的前提下，为网络中的每个节点学习一 个低维、稠密的向量表示。如此，网络被映射到 一个向量空间中，并可通过许多经典的基于向量 的机器学习技术处理许多网络分析任务，如节点 分类[2] 、链接预测[3] 、节点聚类[4] 、可视化[5] 、推荐[6] 等。 网络表示学习不仅要解决网络数据的高维和 稀疏的问题，还需使学习到的节点特征表示能够 保留丰富的网络结构信息。网络中的节点结构大 致分为三类：1) 微观结构，即局部相似性，例如： 一阶相似性 (相邻)、二阶相似性 (有共同的邻 居)。2) 中观结构，例如：角色相似性 (承担相同的 功能)、社团相似性 (属于同一社团)。3) 宏观结 构，即全局网络特性，例如：无标度 (度分布符合 幂律分布) 特性、小世界 (高聚类系数) 特性。 k k 为获取有效的节点表示，结合最先进的机器 学习、深度学习等技术，已提出各种各样的网络 表示学习方法。DeepWalk[7] 和 Node2Vec[8] 通过 随机游走获取节点的局部相似性。GraRep[9] 和 Walklets[10] 通过将邻接矩阵提升到 次幂获取节 点的 阶相似性。DNGR[11] 通过随机冲浪策略获 取节点高阶相似性。Struc2Vec[12] 通过构造层次 加权图，并利用层次加权图上的随机游走获取节 点的结构相似性。M-NMF[13] 通过融合模块度[14] (modularity) 的非负矩阵分解 (nonnegative matrix factor，NMF) 方法，将社团结构信息纳入网络表示 学习中。GraphWave[15] 通过谱图小波的扩散获取 节点的角色结构相似性。HARP[16] 通过随机合并 网络中相邻节点，迭代地将网络粗化为一系列简 化的网络，然后基于这些简化的网络递归地构建 节点向量，从而捕获网络的全局特征。 k 最近，图卷积网络[17] (graph convolutional networks，GCN) 越来越受到关注，已经显示 GCN 对 网络分析任务性能的改进有着显著的效果。 GCN 通过卷积层聚合网络中每个节点及其邻居 节点的特征，输出聚合结果的加权均值用于该节 点新的特征表示。通过卷积层的不断叠加，节点 能够整合 阶邻居信息，从而获取更高阶的节点 特征表示。尽管 GCN 的设计目标是利用深层模 型更好地学习网络中节点的特征表示，但大多数 当前方法依然是浅层结构。例如，GCN[18] 实际上 只使用两层结构，更多的卷积层甚至可能会损害 方法的性能[19]。而且随着模型层数的增加，学习 到的节点特征可能过度平滑，使得不同簇的节点 变得无法区分。这样的限制违背使用深层模型的 目的，导致利用 GCN 模型进行网络表示学习不利 于捕获节点的高阶和全局特征。 为克服这种限制，受商空间[20] 中的分层递阶[21] 思想的启发，提出一种基于多粒度结构的网络表 示学习方法 (network representation learning based on multi-granularity structure，Multi-GS)。MultiGS 首先基于模块度[22] 和粒计算[23] 的思想，利用 网络自身的层次结构，即社团结构，通过使用局 部模块度增量迭代地移动和合并网络中的节点， 构造网络的粗粒度结构。利用粗粒度的结构生成 更粗粒度的结构，反复多次，最终获得分层递阶 的多粒度网络结构。在多粒度结构中，不同粗细 的粒能够反映节点在不同粒度空间上的社团内邻 近关系。然后，Multi-GS 使用无监督的 GCN 模型 分别学习不同粒度空间中粒的特征表示向量，学 习到的特征能够反映不同粒度下粒间的邻近关 系，不同粗细粒度中的粒间关系能够表示不同阶 的节点关系，粒度越粗阶数越高。最后，MultiGS 将不同粒度空间中学习到的粒特征表示按照 由粗到细的顺序进行逐层细化拼接，输出最细粒 度空间中拼接后的粒特征表示作为初始网络的节 点特征表示。实验结果表明，结合多粒度结构能 使 GCN 有效地捕获网络的高阶特征，学习的节点 表示可提升诸如节点分类任务的性能。 1 问题定义 G = (V,E, A) V E A vi ∈ V ei j = (vi , vj) ∈ E A ∈ R n×n n = |V| ei j ∈ E Ai j = wi j > 0 ei j < E Ai j = 0 d(vi) = ∑ Ai vi Γ(vi) = {vj |ei j ∈ E} vi 定义 1 设网络 ，其中， 代表节 点集合， 代表边集合， 代表邻接矩阵。记 代表一个节点， 代表一条边， 邻接矩阵 表示网络的拓扑结构， ， 若 ，则 ；若 ，则 。记 代表节点 的度， 代 表节点 的邻居节点集合。 定义 2 网络的模块度 Q [22] 定义为 Q = 1 2m ∑ c∈C ( lc 2m − ( Dc 2m )2 ) (1) m lc c ∑ vi∈c Aii Dc c C 式中： 表示网络中的边的总数； 表示社团 中 所有内部边的总数， ； 表示社团 中所有 节点的度的总和； 表示所有社团构成的集合。 在社团挖掘任务中，通常使用模块度评价社团划 ·1234· 智 能 系 统 学 报 第 14 卷
第6期 张蕾，等：基于多粒度结构的网络表示学习 ·1235· 分的效果，模块度Q值越高，表明社团划分的效 中所有粒的特征向量；然后自底向上逐层对粒的 果越佳。 特征向量进行映射、拼接；最后输出最终的结果 基于式(1)，可以推导出两个社团合并后的局 作为初始网络中节点的特征表示，如图2所示。 部模块度增量△Q。设当前划分中的任意两个社 团p和q,合并p和q后的社团为k,产生的局部 模块度增量△Qg的计算方法如下： GCN △Qm=Qk-Qp-Qg= (0p+lg)2 D+Dg2 上+ 粒化 2m 2m 2m2m/ =+四+ 2m 2m m 2m 2m (2) GCN 拼接 D.Da -+-+ 12 2m2 2m 2m 2m/ 2m 2m D,Da 粒化 其中，n∑ m 2m Aijo GCN 定义3给定初始网络G。在粒度世界中， 网络中的每个节点可视为一个基本粒。同样用边 图2 Multi-.GS方法的框架 描述粒间的关系。通过粒度衡量粒的大小（粗 Fig.2 Framework of Multi-GS approach 细)。基本粒是指最细粒度的粒。粒化是指将多 2.1基于模块度的网络粒化分层 个粒合并为一个更粗粒度的粒的操作。 本小节介绍Muti-GS的粒化分层操作。主要 将初始网络结构视为由基本粒构成的最细粒 包含两个步骤：1)粒的移动与合并：移动和合并 度的粒层结构。粒化分层是通过聚合和粒化操 的决定取决于局部模块度增量计算结果。2)粒 作，迭代地形成粒度由细到粗的多粒层结构。具 化：生成更粗粒度的粒层结构。相关细节见算法1。 体地说，通过不断聚合不同粒层中的粒和边，G 算法1网络粒化分层(Graphgranular) 被递归压缩成一系列粒度由细到粗的粒层 输入网络G=(VE),最大粒化层数k: Grm,Gr",…,Gr,如图1所示。 输出由细到粗的粒层Gro,GrD,…,Gr。 粒 粒层影 1level =0; 粒化 2)granuleGraph=copy_Graph(G):/*复制图结 粒 粒层 构 3)Qaew=modularity();/*按式(1)计算模块度*/ 粒化 粒化 4)repeat 粒层 5)Grkveaddgraph(granuleGraph): 6)C←{Cy,∈granuleGraph; 7)repeat 图1网络拓扑的粒化分层示例 8)Ocu=Onew; Fig.1 An example of hierarchical view of network topology 9)for each v:in granuleGraph do 定义4给定网络G,网络表示学习的目标是 10)将粒从自身所在的集合中移出： 将网络中的节点，∈V映射到低维向量z∈R,其 11)for v;in Tv)do 中，d表示向量的维度，d≤n。学习到的向量表 12)按式(2)计算粒，移入集合C,后的模块 示可客观反映节点在原始网络中的结构特性。例 度增量△Q; 如，具有相似结构的节点在特征向量的欧式距离 13)end for 空间中彼此靠近，不相似的节点彼此远离。 14)将粒M并入max(△Q)>0的粒集合； 2网络表示学习方法Multi-GS 15)end for 16)Onew=modularity(); Mult-GS首先基于模块度构建多粒度的网络 17)untill (Oeur=Onew) 分层结构：接着使用GCN模型依次学习不同粒层 18)V-[vileach C:in granuleGraph);
分的效果，模块度 Q 值越高，表明社团划分的效 果越佳。 ∆Q p q p q k ∆Qpq 基于式 (1)，可以推导出两个社团合并后的局 部模块度增量 。设当前划分中的任意两个社 团 和 ，合并 和 后的社团为 ，产生的局部 模块度增量 的计算方法如下： ∆Qpq = Qk − Qp − Qq = ( lp +lq )2 2m − ( Dp + Dq 2m )2 − lp 2m + ( Dp 2m )2 − lq 2m + ( Dq 2m )2 = lp 2m + lpq m + lq 2m − ( Dp 2m )2 − DpDq 2m2 − ( Dq 2m )2 − lp 2m + ( Dp 2m )2 − lq 2m + ( Dq 2m )2 = lpq m − DpDq 2m2 (2) lpq = ∑ vi∈p,vj∈q 其中， Ai j。 G 定义 (0) 3 给定初始网络 。在粒度世界中， 网络中的每个节点可视为一个基本粒。同样用边 描述粒间的关系。通过粒度衡量粒的大小 (粗 细)。基本粒是指最细粒度的粒。粒化是指将多 个粒合并为一个更粗粒度的粒的操作。 G (0) Gr(0) ,Gr (1) ,··· ,Gr(k) 将初始网络结构视为由基本粒构成的最细粒 度的粒层结构。粒化分层是通过聚合和粒化操 作，迭代地形成粒度由细到粗的多粒层结构。具 体地说，通过不断聚合不同粒层中的粒和边， 被递归压缩成一系列粒度由细到粗的粒层 ，如图 1 所示。 粒 粒 粒 粒层 粒层 粒层 粒化 粒化 粒化 图 1 网络拓扑的粒化分层示例 Fig. 1 An example of hierarchical view of network topology G vi ∈ V zi ∈ R d d d ≪ n 定义 4 给定网络 ，网络表示学习的目标是 将网络中的节点 映射到低维向量 ，其 中， 表示向量的维度， 。学习到的向量表 示可客观反映节点在原始网络中的结构特性。例 如，具有相似结构的节点在特征向量的欧式距离 空间中彼此靠近，不相似的节点彼此远离。 2 网络表示学习方法 Multi-GS Multi-GS 首先基于模块度构建多粒度的网络 分层结构；接着使用 GCN 模型依次学习不同粒层 中所有粒的特征向量；然后自底向上逐层对粒的 特征向量进行映射、拼接；最后输出最终的结果 作为初始网络中节点的特征表示，如图 2 所示。 粒化 G(0) Z (0) Z G(1) Z (1) G(k) Z 粒化 (k) 逐层 拼接 GCN··· ··· ··· GCN GCN 图 2 Multi-GS 方法的框架 Fig. 2 Framework of Multi-GS approach 2.1 基于模块度的网络粒化分层 本小节介绍 Multi-GS 的粒化分层操作。主要 包含两个步骤：1) 粒的移动与合并：移动和合并 的决定取决于局部模块度增量计算结果。2) 粒 化：生成更粗粒度的粒层结构。相关细节见算法 1。 算法 1 网络粒化分层 (Graphgranular) 输入 网络 G = (V,E) ，最大粒化层数 k； Gr(0) ,Gr(1) ,··· ,Gr 输出 由细到粗的粒层 (k)。 1)level = 0； 2)granuleGraph = copy_Graph(G)；/*复制图结 构*/ 3)Qnew=modularity()；/*按式 (1) 计算模块度*/ 4)repeat Gr 5) (level) ← addGraph(granuleGraph) ； C ← { Ci |vi ∈ granuleGraph} 6) ； 7)repeat 8)Qcur= Qnew； 9)for each vi in granuleGraph do 10) 将粒 vi 从自身所在的集合中移出； 11)for in do vj Γ(vi) vi Cj ∆Q 12) 按式 (2) 计算粒 移入集合 后的模块 度增量 ； 13)end for 14) 将粒 vi 并入 max(∆Q)>0 的粒集合； 15)end for 16)Qnew=modularity()； 17)untill (Qcur = Qnew) V ∗ ← { v ∗ i |each Ci in granuleGraph} 18) ； 第 6 期 张蕾，等：基于多粒度结构的网络表示学习 ·1235·
·1236· 智能系统学报 第14卷 19)E←{ele,∈C,v;ECj and C,≠C: 的对角矩阵，Dj=∑，Aj。GCN模型的整体结构 20)w←{w∑ifvEC,andy,eC: 用式(4(7描述： 21)granuleGraph -Graph(V,E',W*); μ=f(Af(AW)w） (4) 22)level=level +1; o=f(af(Aw）w9)） (5) 23)untill (level>) Z~N(μ，exp(c) (6) 24)return Gr),Gr,…,Gr A'=sigmoid(Z*Z） (7) 算法1的主要步骤如下： 其中，f(·)表示线性激活函数，第一层使用RELU 粒的移动与合并：首先将当前粒层中的每个 函数，第二层使用sigmoid函数；u和c分别表示 粒放人不同的集合中（第6行）。其中，子集合的 向量矩阵Z的均值向量矩阵和标准差向量矩阵； 数量等于当前粒层中粒的数量。遍历所有的粒 W四、W、W9、W四是需要训练的权重矩阵；可通 (第9行)，将当前粒移出自身所在的集合（第10 过对u和σ进行采样得到特征矩阵Z,Z=μ+E*exp 行)，依次移入一个相邻粒的集合中，并依据式(2) (σ)，E~N(0,);“*”符号表示两个向量的内积。 计算移入后的局部模块度增量△Q(第11~13行)。 基于变分推断的编码器，其变分下界的优化 待与所有相邻粒集合的△Q计算完成后，选择与 目标函数如下： 最大（正值）模块度增量相关联的相邻粒集合，并 将粒并入该集合中（第14行）。遍历结束后，重新 计算模块度Q(第16行)。当未达到模块度的局 部极大值时，重复上述步骤（第8~16行）。 解码器使用式(7)重构关系矩阵A,对于重构 在第2个步骤中，新粒间的边权由两个对应 损失，考虑到A的稀疏性，使用加权交叉熵损失 集合中的粒间的边权和确定。同一集合中粒间的 函数Loss构建最终的目标函数，具体公式如下： 内部边视为新粒的自边。 Loss=A.-log(sigmoid(A"))*W()+ (9) 2.2基于图卷积网络的粒特征表示学习 (1-A).-log(1-sigmoid(A)) 本小节介绍Multi--GS的GCN模型结构，包括 (10) 两个部分，编码器和解码器，如图3所示。GCN mw-立424 模型借鉴VGAE2的设计，Multi-.GS不使用节点 的辅助信息，仅利用网络的拓扑结构学习节点的 w=NN小N-2A (11) 特征表示，因此，最终的GCN模型在设计上与 Ccom=wmean(Loss(A.A",Wu) (12) VGAE有所区别。 结合式（⑧）和式(12)，GCN模型最终的目标函 数如下： e C=Clatent +Lreconst (13) exp(a) 2.3算法描述 本小节介绍基于多粒度结构的网络表示学习 解码器 方法Multi-GS,主要包括3个步骤：利用局部模块 度增量△Q,由细到粗地构造多粒度的网络分层 结构（已在2.1小节详细介绍）：使用GCN模型（已 o) 在2.2小节详细介绍)学习不同粒层中粒的特征 图3图卷积神经网络模型结构 表示；将不同粒层的粒特征表示由粗到细地进行 Fig.3 The structure of GCN model 逐层拼接，最终得到最细粒度粒层中粒的特征表 GCN模型的输入是不同分层中的粒关系矩 示；输出此结果作为初始网络的节点特征表示。 阵A,A∈RW表示同一粒层中粒间的连接关系， 相关细节见算法2。 其中，N表示粒的数量。给定粒i和粒j,则 算法2基于多粒度结构的网络表示学习 A=w,w表示粒i和粒j间的连接权重。首先， (Multi-GS) 利用式(3)计算得到归一化的矩阵A∈Rw。 输入网络G,粒化层数k,节点表示向量维 A=DiAD月 (3) 度d,GCN参数O; 其中，A=A+I,I∈RNxN是单位矩阵，D是矩阵A 输出网络表示Z
E ∗ ← { e ∗ i j|ei j, vi ∈ Ci , vj ∈ Cj and Ci , Cj } 19) ； W∗ ← { W∗ i j| ∑ wi j , if vi ∈ Ci and vj ∈ Cj } 20) ； granuleGraph ← Graph(V ∗ ,E ∗ ,W∗ 21) ) ； 22)level = level +1； 23)untill (level> k) Gr(0) ,Gr(1) ,··· ,Gr(k) 24)return 算法 1 的主要步骤如下： ∆Q ∆Q Q 粒的移动与合并：首先将当前粒层中的每个 粒放入不同的集合中 (第 6 行)。其中，子集合的 数量等于当前粒层中粒的数量。遍历所有的粒 (第 9 行)，将当前粒移出自身所在的集合 (第 10 行)，依次移入一个相邻粒的集合中，并依据式 (2) 计算移入后的局部模块度增量 (第 11~13 行)。 待与所有相邻粒集合的 计算完成后，选择与 最大 (正值) 模块度增量相关联的相邻粒集合，并 将粒并入该集合中 (第 14 行)。遍历结束后，重新 计算模块度 (第 16 行)。当未达到模块度的局 部极大值时，重复上述步骤 (第 8~16 行)。 在第 2 个步骤中，新粒间的边权由两个对应 集合中的粒间的边权和确定。同一集合中粒间的 内部边视为新粒的自边。 2.2 基于图卷积网络的粒特征表示学习 本小节介绍 Multi-GS 的 GCN 模型结构，包括 两个部分，编码器和解码器，如图 3 所示。GCN 模型借鉴 VGAE[24] 的设计，Multi-GS 不使用节点 的辅助信息，仅利用网络的拓扑结构学习节点的 特征表示，因此，最终的 GCN 模型在设计上与 VGAE 有所区别。 Z A * exp(σ) W(1) W σ (0) σ W(0) μ W(1) μ μ Â ··· ··· ······ ReLU ReLU 解码器 图 3 图卷积神经网络模型结构 Fig. 3 The structure of GCN model A A ∈ R N×N N i j Ai j = wi j wi j i j Ab∈ R N×N GCN 模型的输入是不同分层中的粒关系矩 阵 ， 表示同一粒层中粒间的连接关系， 其中， 表示粒的数量。给定粒 和 粒 ， 则 ， 表示粒 和粒 间的连接权重。首先， 利用式 (3) 计算得到归一化的矩阵 。 Ab= D − 1 2 ADe − 1 2 (3) Ae= A+ I I ∈ R N×N 其中， ， 是单位矩阵， D 是矩阵 Ae Di j = ∑ j Ae 的对角矩阵， 。i j GCN 模型的整体结构 用式 (4)~(7) 描述： µ = f ( Abf ( AWb (0) µ ) W(1) µ ) (4) σ = f ( Abf ( AWb (0) σ ) W(1) σ ) (5) Z ∼ N ( µ, exp(σ) ) (6) A ∗ = sigmoid( Z ∗ Z T ) (7) f (•) µ σ Z W(0) µ W(1) µ W(0) σ W(1) σ µ σ Z Z = µ+ε ∗ exp (σ),ε ∼ N(0,I) 其中， 表示线性激活函数，第一层使用 RELU 函数，第二层使用 sigmoid 函数； 和 分别表示 向量矩阵 的均值向量矩阵和标准差向量矩阵； 、 、 、 是需要训练的权重矩阵；可通 过对 和 进行采样得到特征矩阵 ， ；“*”符号表示两个向量的内积。 基于变分推断的编码器，其变分下界的优化 目标函数如下： Llatent = − ( 0.5 N ) ·mean ∑d i=1 ( 1+2log(σ)−µ 2 −σ 2 ) (8) A A 解码器使用式 (7) 重构关系矩阵 ，对于重构 损失，考虑到 的稀疏性，使用加权交叉熵损失 函数 Loss 构建最终的目标函数，具体公式如下： Loss = A· [ −log( sigmoid(A ∗ ) ) ∗W(1)] + (1− A)· [ −log( 1−sigmoid(A ∗ ) )] (9) W(1) = N ·N − ∑N i=1 Ai /∑N i=1 Ai (10) W(2) = N ·N / N ·N − ∑N i=1 Ai (11) Lreconst = W(2)mean( Loss( A, A ∗ ,W(1))) (12) 结合式 (8) 和式 (12)，GCN 模型最终的目标函 数如下： L = Llatent +Lreconst (13) 2.3 算法描述 ∆Q 本小节介绍基于多粒度结构的网络表示学习 方法 Multi-GS，主要包括 3 个步骤：利用局部模块 度增量 ，由细到粗地构造多粒度的网络分层 结构 (已在 2.1 小节详细介绍)；使用 GCN 模型 (已 在 2.2 小节详细介绍) 学习不同粒层中粒的特征 表示；将不同粒层的粒特征表示由粗到细地进行 逐层拼接，最终得到最细粒度粒层中粒的特征表 示；输出此结果作为初始网络的节点特征表示。 相关细节见算法 2。 算法 2 基于多粒度结构的网络表示学习 (Multi-GS) Θ 输入 网络 G，粒化层数 k，节点表示向量维 度 d，GCN 参数 ； 输出 网络表示 Z。 ·1236· 智 能 系 统 学 报 第 14 卷
第6期 张蕾，等：基于多粒度结构的网络表示学习 ·1237· l)Gro,Gr,…,Grw←Graphgranular(G): Citeseer21同样是引文网络。该网络包含6类的 2)for m=0 to k do 3312种出版物。边代表不同出版物间的引用关 3)Zm←-GCN(Grm.A,⊙)： 系，共有4660条边。PPI2是生物网络。该网络 4)end for 包含3890个节点和38739条边。其中，节点代 5)for n=k to 1 do 表蛋白质，根据不同的生物状态分为50类，边代 6)Z()projection(Z(m); 表蛋白质间的相互作用。WiK2)是维基百科数 7)Za-l)←concatenate(Za,Za-l)片 据库中单词的共现网络。该网络包含4777个节 8)end for 点，92517条边，以及40种不同的词性标签。Blog 9z-t°； Catalog2s是来自BlogCatalog网站的社交网络。 10)return Z 节点代表博主，并根据博主的个人兴趣划分为39 首先，Multi--GS算法的输入包括3个部分：网 类，边代表博主间的友谊关系。该网络包含10312 络G;粒化层数k;GCN模型的参数⊙，包括，节点 个节点和333983条边。 表示向量维度d、训练次数和学习率。算法2的 2)对比算法。 第1行，使用算法1构建多粒度的网络分层结构， 实验选择4种具有代表性的网络表示学习算 其复杂度为O(M什N),其中M为每轮迭代中粒的 法作为对比算法，包括DeepWalk、Node2Vec 数量，N是粒层中的边的数量。第2~第4行，依 GraRep、DNGR。关于这些方法的简要描述如下： 次将不同粒层的粒关系矩阵A作为输入，利用 DeepWalk!7:使用随机游走获取节点序列，通 GCN模型学习粒的特征表示。GCN模型的复杂 过SkipGram方法学习节点表示。 度与网络的边数呈线性关系，其复杂度为 Node2Vec⑧：类似于DeepWalk,但是使用有偏 Omdh),其中m是矩阵A中非零元素的数量，d是 向的随机游走获取节点序列。 特征维数，h是权重矩阵的特征映射数量。另外， GraRep:通过构造k步概率转移矩阵学习节 方法还需重建原始拓扑结构，因此总体复杂度为 点表示，能够保留节点的高阶相似性。 O(mdH+W),其中H是不同层上所有特征映射的 DNGR山：使用随机冲浪方法获取节点的高 总和。第5~第8行，将学习到的粒特征向量由粗 阶相似性，利用深度神经网络学习节点表示。 到细地进行拼接。其中，projection函数是粒化过 3)参数设定。 程的反向操作。在此过程中，上层的粒特征向量 对于Multi-GS方法中的GCN模型，使用 被映射到一个或多个较细粒度粒特征向量，投影 Adam优化器更新训练中的参数，学习率设为 结束后，拼接相同粒的两个不同的粒特征表示。 0.O5。对于DeepWalk和Node2Vec,节点游走次数 循环结束后，得到基本粒的拼接后的特征表示， 设为10，窗口大小设为10，随机游走的长度设为 其复杂度为O(M0。第9行，以基本粒的特征表示 80。Node2Vec的参数p=0.25、qF4。对于GraRep, 作为对应节点的特征表示进行输出。 kp=4。对于DNGR的随机冲浪方法，迭代次数设 为4，重启概率α=0.98，自编码器的层数设为2， 3实验和结果分析 使用RMSProp优化器，训练次数设为400，学习率 本节通过节点分类和链接预测任务，在真实 设为0.002。为进行公平比较，所以方法学习的节 数据集上与4个具有代表性的网络表示学习方法 点表示维度均设为128。 进行对比，验证Multi--GS的有效性。实验环境 表1数据集信息 为：Windows10操作系统，Intel i7-47903.6GHz Table 1 Datasets information CPU,8GB内存。通过Python语言和Tensor- 数据集 节点数 边数 类别数 平均度 Flow实现Multi-GS。 Cora 2708 5278 > 3.898 3.1实验设定 Citeseer 3312 4660 6 2.814 1)数据集。 PPI 3890 38739 50 19.917 实验使用5个真实数据集，包括引文网络、生 WiKi 4777 92517 40 38.734 物网络、词共现网和社交网络，详细信息见表1。 BlogCatalog 10312 333983 39 64.776 Cora21是引文网络。其中，节点代表论文，根据 论文的不同主题分为7类。边代表论文间的引 3.2节点分类 用关系。该网络包含2708个节点和5278条边。 利用节点分类任务比较Multi-.GS和对比算
Gr(0) ,Gr(1) ,··· ,Gr 1) (k) ← Graphgranular(G) ； 2)for m = 0 to k do Z (m) ← GCN( Gr(m) .A,Θ ) 3) ； 4)end for 5)for n = k to 1 do Z (n) ← projection( Z (n) ) 6) ； Z (n−1) ← concatenate( Z (n) , Z (n−1) ) 7) ； 8)end for 9)Z←Z (0) ； 10)return Z G k Θ d A A 首先，Multi-GS 算法的输入包括 3 个部分：网 络 ；粒化层数 ；GCN 模型的参数 ，包括，节点 表示向量维度 、训练次数和学习率。算法 2 的 第 1 行，使用算法 1 构建多粒度的网络分层结构， 其复杂度为 O(M+N)，其中 M 为每轮迭代中粒的 数量，N 是粒层中的边的数量。第 2~第 4 行，依 次将不同粒层的粒关系矩阵 作为输入，利用 GCN 模型学习粒的特征表示。GCN 模型的复杂 度与网络的边数呈线性关系，其复杂度 为 O(mdh)，其中 m 是矩阵 中非零元素的数量，d 是 特征维数，h 是权重矩阵的特征映射数量。另外， 方法还需重建原始拓扑结构，因此总体复杂度为 O(mdH+N 2 )，其中 H 是不同层上所有特征映射的 总和。第 5~第 8 行，将学习到的粒特征向量由粗 到细地进行拼接。其中，projection 函数是粒化过 程的反向操作。在此过程中，上层的粒特征向量 被映射到一个或多个较细粒度粒特征向量，投影 结束后，拼接相同粒的两个不同的粒特征表示。 循环结束后，得到基本粒的拼接后的特征表示， 其复杂度为 O(M)。第 9 行，以基本粒的特征表示 作为对应节点的特征表示进行输出。 3 实验和结果分析 本节通过节点分类和链接预测任务，在真实 数据集上与 4 个具有代表性的网络表示学习方法 进行对比，验证 Multi-GS 的有效性。实验环境 为：Windows10 操作系统，Intel i7-4790 3.6 GHz CPU，8 GB 内存。通过 Python 语言和 TensorFlow 实现 Multi-GS。 3.1 实验设定 1) 数据集。 实验使用 5 个真实数据集，包括引文网络、生 物网络、词共现网络和社交网络，详细信息见表 1。 Cora[25] 是引文网络。其中，节点代表论文，根据 论文的不同主题分为 7 类。边代表论文间的引 用关系。该网络包含 2 708 个节点和 5 278 条边。 Citeseer[25] 同样是引文网络。该网络包含 6 类的 3 312 种出版物。边代表不同出版物间的引用关 系，共有 4 660 条边。PPI[26] 是生物网络。该网络 包含 3 890 个节点和 38 739 条边。其中，节点代 表蛋白质，根据不同的生物状态分为 50 类，边代 表蛋白质间的相互作用。WiKi[27] 是维基百科数 据库中单词的共现网络。该网络包含 4 777 个节 点，92 517 条边，以及 40 种不同的词性标签。BlogCatalog[28] 是来自 BlogCatalog 网站的社交网络。 节点代表博主，并根据博主的个人兴趣划分为 39 类，边代表博主间的友谊关系。该网络包含 10 312 个节点和 333 983 条边。 2) 对比算法。 实验选择 4 种具有代表性的网络表示学习算 法作为对比算法，包括 DeepWalk、Node2Vec、 GraRep、DNGR。关于这些方法的简要描述如下： DeepWalk[7] ：使用随机游走获取节点序列，通 过 SkipGram 方法学习节点表示。 Node2Vec[8] ：类似于 DeepWalk，但是使用有偏 向的随机游走获取节点序列。 GraRep k [9] ：通过构造 步概率转移矩阵学习节 点表示，能够保留节点的高阶相似性。 DNGR[11] ：使用随机冲浪方法获取节点的高 阶相似性，利用深度神经网络学习节点表示。 3) 参数设定。 α = 0.98 对于 Multi-GS 方法中的 GCN 模型，使用 Adam 优化器更新训练中的参数，学习率设为 0.05。对于 DeepWalk 和 Node2Vec，节点游走次数 设为 10，窗口大小设为 10，随机游走的长度设为 80。Node2Vec 的参数 p=0.25、q=4。对于 GraRep， kstep=4。对于 DNGR 的随机冲浪方法，迭代次数设 为 4，重启概率 ，自编码器的层数设为 2， 使用 RMSProp 优化器，训练次数设为 400，学习率 设为 0.002。为进行公平比较，所以方法学习的节 点表示维度均设为 128。 表 1 数据集信息 Table 1 Datasets information 数据集 节点数 边数 类别数 平均度 Cora 2 708 5 278 7 3.898 Citeseer 3 312 4 660 6 2.814 PPI 3 890 38 739 50 19.917 WiKi 4 777 92 517 40 38.734 BlogCatalog 10 312 333 983 39 64.776 3.2 节点分类 利用节点分类任务比较 Multi-GS 和对比算 第 6 期 张蕾，等：基于多粒度结构的网络表示学习 ·1237·
·1238· 智能系统学报 第14卷 法的性能差异。实验挑选4种不同领域数据集， 表4WiKi数据集上的Micro-E和Macro-F,结果 包括Citeseer、PPI、WiKi和BlogCatalog。首先各 Table 4 Micro-F and Macro-F results on WiKi dataset 自使用网络中所有节点学习节点的特征表示，对 Micro-F Macro-F 于Multi-GS,为比较不同的粒化层次对方法性能 对比算法 10%50%90%10%50%90% 的影响，针对不同的数据集，分别设置5组实验， DeepWalk 0.4160.4730.4920.0700.0890.093 在每组实验中，将粒化层次从0设到4(k为 Node2Vec 0.4220.4860.5090.0780.0990.106 0~4)。=0表示Multi--GS不使用多粒度结构进行 联合学习表示，仅利用原始网络通过GCN模型学 GraRep 0.4750.5230.5270.0940.1170.123 习节点的表示。针对节点分类，使用Logistic回 DNGR 0.3410.4200.4340.0660.0830.083 归分类器，随机从不同数据集中分别选择{10%， Multi-.GS(=0)0.4720.4740.4720.0780.0730.070 50%,90%}节点训练分类器，在其余节点上评估 Multi-GS(k=1)0.4690.5020.5130.0710.0780.084 分类器的性能。为衡量分类性能，实验采用M- cro-F21和Macro-F作为评价指标。两个指标 Multi--GS(k=2)0.4760.5040.5220.0810.0870.101 越大，分类性能越好。所有的分类实验重复10 Multi--GS(k=3)0.4830.5240.5890.0980.1180.123 次，报告平均结果。表2~5分别展示在Citeseer、 Multi-GS(=4)0.4160.4730.4920.0700.0890.093 PPI、WiKi和BlogCatalog数据集上的节点分类 Micro-F,和Macro-F,的均值，其中，粗体表示性能 表5 BlogCatalog数据集上的MicroFj和Macro-F结果 最好的结果，下划线表示对比算法中性能最优的 Table 5 Micro-F and Macro-F results on BlogCatalog dataset 结果。 表2 Citeseer数据集上的Micro-F和Macro-F结果 Micro-F Macro-F 对比算法 Table 2 Micro-F and Macro-F results on Citeseer dataset 10%50%90%10%50%90% Micro-F Macro-F DeepWalk 0.3390.3970.4080.1910.2530.263 对比算法 10%50%90%10%50%90% Node2Vec 0.3410.3990.4150.2000.2630.281 DeepWalk 0.5110.5910.5960.4690.5400.538 GraRep 0.3670.4000.4050.1980.2350.235 Node2Vec 0.5310.5940.6120.4800.5420.561 DNGR 0.2660.3270.3420.1560.1840.190 GraRep 0.5200.5460.5630.4650.4860.498 DNGR 0.4540.5350.5450.4180.4900.492 Multi-GS(k=0)0.3140.3650.3630.1200.1260.120 Multi-GS(=0) 0.3800.4520.4890.3380.4080.433 Multi--GS(k=1)0.3550.3800.3940.1370.1580.173 Multi--GS(=1)0.4650.5360.5730.4220.4950.534 Multi-GS(k=2)0.3850.4050.4310.2020.2690.283 Multi-.GS(k=2)0.5280.6180.6580.4870.5810.627 Multi--GS(k=3)0.3680.3990.4170.1480.1630.179 Multi-.GS(=3)0.5410.6340.6660.4990.5990.632 Multi--GS(k=4)0.5420.6590.6990.5010.6260.661 Multi--GS(k=4)0.3230.3640.3800.1430.1600.172 表3PPI数据集上的Micro--F,和Macro-F结果 实验结果显示，在对比算法中，GreRap表现 Table 3 Micro-F and Macro-F results on PPI dataset 出强有力的竞争力，Node2Vec也表现不俗。因无 Micro-F 法获取节点的一阶相似性，故DNGR表现较差。 对比算法 Macro-F 10%50%90%10%50%90% 针对Multi-GS,可以发现，相对于不使用联合学 DeepWalk 0.1600.2090.2320.1310.1810.190 习(=O)的情形，使用多粒度结构在多数情况下 可提升方法的性能，说明保留节点的高阶相似性 Node2Vec 0.1550.2040.2280.1250.1770.189 可提升节点分类任务的性能。对于相同的数据 GraRep 0.1920.239025401480.1950201 集，Multi--GS在不同的粒化层次下存在差异。具 DNGR 0.1450.1880.2230.1260.1640.186 体来说，在Citeseer数据集上，随着粒化层数的增 Multi--GS(=0)0.1730.1970.2090.1280.1530.159 加，Multi-.GS的Micro-F1和Macro-F1值逐渐增 Multi--GS(k=1)0.1810.2180.2320.1350.1690.173 大。在PPI和WiK数据集上，最佳的结果出现 Multi--GS(k=2)0.1880.2310.2580.1430.1900.189 在k=3时。在BlogCatalog数据集上，当k=2时方 Multi--GS(=3)0.1940.2410.2660.1570.1990.201 法性能最好。依据表1中不同数据集平均度的统 计结果，可以看出，Citeseer数据集的平均度是 Multi-.GS(=4)0.1770.2150.2190.1390.1760.174 3.8981,说明该网络是一个弱关系网络，BlogCata
法的性能差异。实验挑选 4 种不同领域数据集， 包括 Citeseer、PPI、WiKi 和 BlogCatalog。首先各 自使用网络中所有节点学习节点的特征表示，对 于 Multi-GS，为比较不同的粒化层次对方法性能 的影响，针对不同的数据集，分别设置 5 组实验， 在每组实验中，将粒化层次 从 0 设 到 4 ( k 为 0~4)。k=0 表示 Multi-GS 不使用多粒度结构进行 联合学习表示，仅利用原始网络通过 GCN 模型学 习节点的表示。针对节点分类，使用 Logistic 回 归分类器，随机从不同数据集中分别选择{10%， 50%，90%}节点训练分类器，在其余节点上评估 分类器的性能。为衡量分类性能，实验采用 Micro-F1 [29] 和 Macro-F1 [29] 作为评价指标。两个指标 越大，分类性能越好。所有的分类实验重复 10 次，报告平均结果。表 2~5 分别展示在 Citeseer、 PPI、WiKi 和 BlogCatalog 数据集上的节点分类 Micro-F1 和 Macro-F1 的均值，其中，粗体表示性能 最好的结果，下划线表示对比算法中性能最优的 结果。 表 2 Citeseer 数据集上的 Micro-F1 和 Macro-F1 结果 Table 2 Micro-F1 and Macro-F1 results on Citeseer dataset 对比算法 Micro-F1 Macro-F1 10% 50% 90% 10% 50% 90% DeepWalk 0.511 0.591 0.596 0.469 0.540 0.538 Node2Vec 0.531 0.594 0.612 0.480 0.542 0.561 GraRep 0.520 0.546 0.563 0.465 0.486 0.498 DNGR 0.454 0.535 0.545 0.418 0.490 0.492 Multi-GS(k=0) 0.380 0.452 0.489 0.338 0.408 0.433 Multi-GS(k=1) 0.465 0.536 0.573 0.422 0.495 0.534 Multi-GS(k=2) 0.528 0.618 0.658 0.487 0.581 0.627 Multi-GS(k=3) 0.541 0.634 0.666 0.499 0.599 0.632 Multi-GS(k=4) 0.542 0.659 0.699 0.501 0.626 0.661 表 3 PPI 数据集上的 Micro-F1 和 Macro-F1 结果 Table 3 Micro-F1 and Macro-F1 results on PPI dataset 对比算法 Micro-F1 Macro-F1 10% 50% 90% 10% 50% 90% DeepWalk 0.160 0.209 0.232 0.131 0.181 0.190 Node2Vec 0.155 0.204 0.228 0.125 0.177 0.189 GraRep 0.192 0.239 0.254 0.148 0.195 0.201 DNGR 0.145 0.188 0.223 0.126 0.164 0.186 Multi-GS(k=0) 0.173 0.197 0.209 0.128 0.153 0.159 Multi-GS(k=1) 0.181 0.218 0.232 0.135 0.169 0.173 Multi-GS(k=2) 0.188 0.231 0.258 0.143 0.190 0.189 Multi-GS(k=3) 0.194 0.241 0.266 0.157 0.199 0.201 Multi-GS(k=4) 0.177 0.215 0.219 0.139 0.176 0.174 表 4 WiKi 数据集上的 Micro-F1 和 Macro-F1 结果 Table 4 Micro-F1 and Macro-F1 results on WiKi dataset 对比算法 Micro-F1 Macro-F1 10% 50% 90% 10% 50% 90% DeepWalk 0.416 0.473 0.492 0.070 0.089 0.093 Node2Vec 0.422 0.486 0.509 0.078 0.099 0.106 GraRep 0.475 0.523 0.527 0.094 0.117 0.123 DNGR 0.341 0.420 0.434 0.066 0.083 0.083 Multi-GS(k=0) 0.472 0.474 0.472 0.078 0.073 0.070 Multi-GS(k=1) 0.469 0.502 0.513 0.071 0.078 0.084 Multi-GS(k=2) 0.476 0.504 0.522 0.081 0.087 0.101 Multi-GS(k=3) 0.483 0.524 0.589 0.098 0.118 0.123 Multi-GS(k=4) 0.416 0.473 0.492 0.070 0.089 0.093 表 5 BlogCatalog 数据集上的 Micro-F1 和 Macro-F1 结果 Table 5 Micro-F1 and Macro-F1 results on BlogCatalog dataset 对比算法 Micro-F1 Macro-F1 10% 50% 90% 10% 50% 90% DeepWalk 0.339 0.397 0.408 0.191 0.253 0.263 Node2Vec 0.341 0.399 0.415 0.200 0.263 0.281 GraRep 0.367 0.400 0.405 0.198 0.235 0.235 DNGR 0.266 0.327 0.342 0.156 0.184 0.190 Multi-GS(k=0) 0.314 0.365 0.363 0.120 0.126 0.120 Multi-GS(k=1) 0.355 0.380 0.394 0.137 0.158 0.173 Multi-GS(k=2) 0.385 0.405 0.431 0.202 0.269 0.283 Multi-GS(k=3) 0.368 0.399 0.417 0.148 0.163 0.179 Multi-GS(k=4) 0.323 0.364 0.380 0.143 0.160 0.172 实验结果显示，在对比算法中，GreRap 表现 出强有力的竞争力，Node2Vec 也表现不俗。因无 法获取节点的一阶相似性，故 DNGR 表现较差。 针对 Multi-GS，可以发现，相对于不使用联合学 习 (k=0) 的情形，使用多粒度结构在多数情况下 可提升方法的性能，说明保留节点的高阶相似性 可提升节点分类任务的性能。对于相同的数据 集，Multi-GS 在不同的粒化层次下存在差异。具 体来说，在 Citeseer 数据集上，随着粒化层数的增 加，Multi-GS 的 Micro-F1 和 Macro-F1 值逐渐增 大。在 PPI 和 WiKi 数据集上，最佳的结果出现 在 k=3 时。在 BlogCatalog 数据集上，当 k=2 时方 法性能最好。依据表 1 中不同数据集平均度的统 计结果，可以看出，Citeseer 数据集的平均度是 3.898 1，说明该网络是一个弱关系网络，BlogCata- ·1238· 智 能 系 统 学 报 第 14 卷
第6期 张蕾，等：基于多粒度结构的网络表示学习 ·1239· 10g数据集的平均度高达64.7756，是一个强关系 框架时，方法的性能是最优的。以AUC为评价标 网络。在弱关系网络中，由于不同社团间的联系 准，相对于对比算法中的最优结果，在Citeseer数 较弱，使得不同粒层中粒的粒度差异较小，而对 据集上相对提高45.24%，在WiKi数据集上相对 于强关系网络，由于社团内部边的密度与不同社 提高15.4%，在PPI数据集上相对提高39.14%，在 团间的边密度差异较小，使得小社团快速合并成 BlogCatalog数据集上相对提高20.66%。但是，随 大社团，导致不同粒层间的粒度差异会非常大。 着粒化层数的增加，对于链接预测任务，方法的 在强关系网络中，随着粒化层数的增加，各粒层 性能会越来越差，下降速度会随着网络的密度成 中相应粒的特征趋于雷同，若拼接过多类似的特 正比。综合来看，在链接预测任务中，利用多粒 征将导致节点自身的特征被弱化，导致Multi- 度结构联合学习到的节点表示无法提升链接预测 GS的性能会有先提升再降低的情况。因此，针对 能力，说明该类任务需要更多节点自身的特征， 不同的数据集，如何设置一个合理的粒化层数是 节点低阶相似性比高阶相似性更重要。虽然融合 Multi-GS需要考虑的问题。 多粒度结构中节点的高阶特征会导致Multi- 3.3链接预测 GS性能下降，但可以看出，在较低的k值下，仅利 链接预测任务是预测网络中给定节点间是否 用节点的拓扑结构信息，Multi-GS的链接预测结 存在边。通过链接预测可以显示不同网络表示方 果十分理想，说明Multi-GS中GCN模型能有效 法的链接预测能力。对于链接预测任务，仍然选 地捕获节点的低阶相似性。 择Citeseer、PPI、WiKi和BlogCatalog作为验证数 3.4可视化 据集，分别从不同数据集中随机移除现有链接的 在本小节中，对Multi-.GS和对比算法学习的 50%。使用剩余网络，利用不同的方法学习节点 节点表示利用可视化进行比较。由于空间限制， 表示。另外，将被移除边中的节点对作为正样 实验选择节点数较少的Cora作为可视化数据 本，同时随机采样相同数量未连接的节点对作为 集。其中，每个节点代表一篇机器学习论文，所 负样本，使正样本和负样本构成平衡数据集。实 有节点按照论文的主题分为7类。实验通过t: 验中，首先基于给定样本中的节点对，通过表示 SNE2m工具，将所有方法的节点表示投影到二维 向量计算其余弦相似度得分，然后使用Logist- 空间中，不同类别的节点用不同的颜色显示。可 ic回归分类器进行分类，并通过曲线下面积2 视化结果如图4所示。 (area under curve,.AUC)评估标签间的一致性和样 本的相似性得分。对于Muti-GS,k为0-4。表6 显示链接预测任务中，不同算法在Citeseer、PPI、 WiKi和BlogCatalog数据集上的AUC值，其中， 粗体表示性能最好的结果，下划线表示对比算法 (a)DeepWalk (b)Node2Vec (c)GraRep 中性能最优的结果。 表6链接预测任务中不同数据集上的AUC结果 Table 6 AUC score on all datasets 对比算法 Citeseer WiKi PPI BlogCatalog (d)DNGR =0 =1 DeepWalk 0.63540.7577 0.7244 (e)Multi-GS (f)Multi-GS Node2Vec 0.61210.74200.6001 0.7126 GraRep 0.6162 DNGR 0.65150.75640.5165 0.7177 Multi--GS=0)0.99650.92570.8724 0.9036 =2 =3 =4 Multi-GS(k=1)0.99150.87750.8285 0.7369 (g)Multi-GS (h)Multi-GS (i)Multi-GS Multi-GS(-=2) 0.97360.80780.7477 0.6641 图4Cora数据集的可视化结果 Fig.4 The visualization of Cora dataset Multi-GS(K=3) 0.93500.78410.6076 0.6498 在图4中，DeepWalk、Node2Vec的表示结果 Multi-GS(=4)0.91120.78010.6026 0.6272 较差，节点散布在整个空间中，不同类别的节点 表6的结果显示，在对比算法中，GraRep表 相互混在一起，无法观察到分组结构，意味着算 现依然最好。对于Multi-GS,当不使用联合学习 法无法将相似节点组合在一起。通过GreRap的
log 数据集的平均度高达 64.775 6，是一个强关系 网络。在弱关系网络中，由于不同社团间的联系 较弱，使得不同粒层中粒的粒度差异较小，而对 于强关系网络，由于社团内部边的密度与不同社 团间的边密度差异较小，使得小社团快速合并成 大社团，导致不同粒层间的粒度差异会非常大。 在强关系网络中，随着粒化层数的增加，各粒层 中相应粒的特征趋于雷同，若拼接过多类似的特 征将导致节点自身的特征被弱化，导致 MultiGS 的性能会有先提升再降低的情况。因此，针对 不同的数据集，如何设置一个合理的粒化层数是 Multi-GS 需要考虑的问题。 3.3 链接预测 链接预测任务是预测网络中给定节点间是否 存在边。通过链接预测可以显示不同网络表示方 法的链接预测能力。对于链接预测任务，仍然选 择 Citeseer、PPI、WiKi 和 BlogCatalog 作为验证数 据集，分别从不同数据集中随机移除现有链接的 50%。使用剩余网络，利用不同的方法学习节点 表示。另外，将被移除边中的节点对作为正样 本，同时随机采样相同数量未连接的节点对作为 负样本，使正样本和负样本构成平衡数据集。实 验中，首先基于给定样本中的节点对，通过表示 向量计算其余弦相似度得分，然后使用 Logistic 回归分类器进行分类，并通过曲线下面积[ 2 9 ] (area under curve，AUC) 评估标签间的一致性和样 本的相似性得分。对于 Multi-GS，k 为 0~4。表 6 显示链接预测任务中，不同算法在 Citeseer、PPI、 WiKi 和 BlogCatalog 数据集上的 AUC 值，其中， 粗体表示性能最好的结果，下划线表示对比算法 中性能最优的结果。 表 6 链接预测任务中不同数据集上的 AUC 结果 Table 6 AUC score on all datasets 对比算法 Citeseer WiKi PPI BlogCatalog DeepWalk 0.635 4 0.757 7 0.724 4 Node2Vec 0.612 1 0.742 0 0.600 1 0.712 6 GraRep 0.616 2 DNGR 0.651 5 0.756 4 0.516 5 0.717 7 Multi-GS(k=0) 0.996 5 0.925 7 0.872 4 0.903 6 Multi-GS(k=1) 0.991 5 0.877 5 0.828 5 0.736 9 Multi-GS(k=2) 0.973 6 0.807 8 0.747 7 0.664 1 Multi-GS(k=3) 0.935 0 0.784 1 0.607 6 0.649 8 Multi-GS(k=4) 0.911 2 0.780 1 0.602 6 0.627 2 表 6 的结果显示，在对比算法中，GraRep 表 现依然最好。对于 Multi-GS，当不使用联合学习 框架时，方法的性能是最优的。以 AUC 为评价标 准，相对于对比算法中的最优结果，在 Citeseer 数 据集上相对提高 45.24%，在 WiKi 数据集上相对 提高 15.4%，在 PPI 数据集上相对提高 39.14%，在 BlogCatalog 数据集上相对提高 20.66%。但是，随 着粒化层数的增加，对于链接预测任务，方法的 性能会越来越差，下降速度会随着网络的密度成 正比。综合来看，在链接预测任务中，利用多粒 度结构联合学习到的节点表示无法提升链接预测 能力，说明该类任务需要更多节点自身的特征， 节点低阶相似性比高阶相似性更重要。虽然融合 多粒度结构中节点的高阶特征会导致 MultiGS 性能下降，但可以看出，在较低的 k 值下，仅利 用节点的拓扑结构信息，Multi-GS 的链接预测结 果十分理想，说明 Multi-GS 中 GCN 模型能有效 地捕获节点的低阶相似性。 3.4 可视化 在本小节中，对 Multi-GS 和对比算法学习的 节点表示利用可视化进行比较。由于空间限制， 实验选择节点数较少的 Cora 作为可视化数据 集。其中，每个节点代表一篇机器学习论文，所 有节点按照论文的主题分为 7 类。实验通过 tSNE[27] 工具，将所有方法的节点表示投影到二维 空间中，不同类别的节点用不同的颜色显示。可 视化结果如图 4 所示。 (a) DeepWalk (b) Node2Vec (c) GraRep (d) DNGR (e) Multi-GS k=0 (f) Multi-GS k=1 (g) Multi-GS k=2 (h) Multi-GS k=3 (i) Multi-GS k=4 图 4 Cora 数据集的可视化结果 Fig. 4 The visualization of Cora dataset 在图 4 中，DeepWalk、Node2Vec 的表示结果 较差，节点散布在整个空间中，不同类别的节点 相互混在一起，无法观察到分组结构，意味着算 法无法将相似节点组合在一起。通过 GreRap 的 第 6 期 张蕾，等：基于多粒度结构的网络表示学习 ·1239·
·1240· 智能系统学报 第14卷 可视化结果，能够看出节点间的分组结构。对于 1.00 3500. Multi--GS,在图4(e)中，不同分类的节点相互混 0.95 岁3000 合，这种现象在图的中心尤其明显。意味着仅保 0.90 2500 留低阶相似性的节点表示无法区分不同分类的节 2000 0.80 点。图4（①显示结果与图4(）相似。在图4(g) 1500 0.75 图4①)中，可以看到节点逐渐开始呈现紧凑的分 1000 0.70 组结构，而且不同组之间的距离越来越大，随着 8163264128 01234 节点向量维度 粒化层数 层数的增加，Muti-GS可以将相似结构的节点进 (e链接预测AUC值 ()不同粒层中粒的数量 行分组并推到一起。因此，在节点分类任务中， 图5参数敏感性分析 利用多粒度结构使Muti-GS获得更好的结果。 Fig.5 Parametric sensitivity analysis 3.5参数敏感性分析 图5的结果表明，对于节点分类任务，Micro- 本节进行参数敏感性实验，主要分析不同的 F1和Macro-F1指标随着特征维度的上升而上 特征维度和粒化层数对Multi-.GS性能的影响。 升。因为一个更大的特征维度可以保留网络中更 实验针对Citeseer数据集，利用Multi-.GS在不同 粒化层数下学习到的不同维度的节点表示，通过 多的信息。随着粒化层数的增加，Micro-F1和 节点分类、节点聚类和链接预测任务对Multi- Macro-F1指标也逐渐提升，但是可以看出，这样 GS进行评估，并报告相关的实验结果。对于节点 的提升效果会随着粒化层数的增加而越变越小 分类任务，随机选择50%节点训练分类器。采用 甚至退化。对于节点聚类任务，NMI和ARI的最 Micro-F1和Macro-F1作为评价指标。对于节点 优结果都出现在=3时，继续增加层数，结果会下 聚类任务，采用NM0和ARIB0作为评价指标。 降。对于链接预测任务，AUC指标随着特征维度 对于链接预测任务，移除50%的链接，采用 的上升而上升，这是合理的情形。但是当仁4时， AUC作为评价指标。参数k表示最终节点的特 AUC指标发生波动，说明叠加更多的层次会导致 征表示融合的粒化层数，若=0，表示仅选取最细 学习的特征表示发生信息变化，这是需要避免的 粒度的粒特征表示作为最终的节点特征表示， 情况。通过图5()中显示的各层中粒的数量的变 =1,表示用第0层和第1层的粒学习到的特征表 化曲线，可以看出，不同层间的粒度差异会随着 示进行拼接后的向量作为最终的节点特征表示， 层数的增加而减少。在第3层和第4层间，这种 以此类推。其中，0表示最细粒度，k值越大，表 粒度差异几乎很小，意味着节点在第3层和第 示粒度越粗。对于所有任务，重复实验10次并报 4层中的特征极为相似，若拼接过多类似的高阶 告平均结果，实验结果如图5所示。 特征向量，导致节点自身的特征被弱化，使得最 -k=0平-k=1一=2-=3 终Multi--GS的输出表示不能在网络分析任务中 0.7 0.7 发挥出方法优势。 0.6 0.6 0.5 年0.5 4结束语 0.4 在网络表示学习中，如何让学习到的节点特 0.3 0.3 征表示能够保留网络结构的局部和全局特征，仍 0.2 0.2 8163264128 8163264128 是一个开放和重要的研究课题。本文结合分层递 节点向量维度 节点向量维度 阶的思想，提出一种无监督网络表示学习方法 (a)节点分类Micro-F值 (b)节点分类Macro-F,值 Multi-GS,通过构建网络的深度结构解决GCN无 0.30 0.30 法有效捕获节点高阶相似性特征的问题。该方法 0.25 0.25 首先利用模块度增量逐步构建网络的多粒度分层 0.20 0.20 结构，然后利用GCN模型学习不同粒度空间中粒 0.15 0.15 的特征表示，最后将已学习的粒特征向量逐层映 0.10 0.10 0.05 0.05 射拼接为原始网络的节点表示。利用Multi- 0 GS可捕获多种网络结构信息，包括一阶和二阶相 8163264128 8163264128 节点向量维度 节点向量维度 似性、社团内相似性（高阶结构）和社团间相似性 (c)节点聚类NMI值 (d)节点聚类ARI值 (全局结构)
可视化结果，能够看出节点间的分组结构。对于 Multi-GS，在图 4(e) 中，不同分类的节点相互混 合，这种现象在图的中心尤其明显。意味着仅保 留低阶相似性的节点表示无法区分不同分类的节 点。图 4(f) 显示结果与图 4(e) 相似。在图 4(g)~ 图 4(i) 中，可以看到节点逐渐开始呈现紧凑的分 组结构，而且不同组之间的距离越来越大，随着 层数的增加，Multi-GS 可以将相似结构的节点进 行分组并推到一起。因此，在节点分类任务中， 利用多粒度结构使 Multi-GS 获得更好的结果。 3.5 参数敏感性分析 本节进行参数敏感性实验，主要分析不同的 特征维度和粒化层数对 Multi-GS 性能的影响。 实验针对 Citeseer 数据集，利用 Multi-GS 在不同 粒化层数下学习到的不同维度的节点表示，通过 节点分类、节点聚类和链接预测任务对 MultiGS 进行评估，并报告相关的实验结果。对于节点 分类任务，随机选择 50% 节点训练分类器。采用 Micro-F1 和 Macro-F1 作为评价指标。对于节点 聚类任务，采用 NMI[30] 和 ARI[30] 作为评价指标。 对于链接预测任务，移 除 5 0 % 的链接，采 用 AUC 作为评价指标。参数 k 表示最终节点的特 征表示融合的粒化层数，若 k=0，表示仅选取最细 粒度的粒特征表示作为最终的节点特征表示， k=1，表示用第 0 层和第 1 层的粒学习到的特征表 示进行拼接后的向量作为最终的节点特征表示， 以此类推。其中，0 表示最细粒度，k 值越大，表 示粒度越粗。对于所有任务，重复实验 10 次并报 告平均结果，实验结果如图 5 所示。 图 5 的结果表明，对于节点分类任务，MicroF1 和 Macro-F1 指标随着特征维度的上升而上 升。因为一个更大的特征维度可以保留网络中更 多的信息。随着粒化层数的增加，Micro-F1 和 Macro-F1 指标也逐渐提升，但是可以看出，这样 的提升效果会随着粒化层数的增加而越变越小， 甚至退化。对于节点聚类任务，NMI 和 ARI 的最 优结果都出现在 k=3 时，继续增加层数，结果会下 降。对于链接预测任务，AUC 指标随着特征维度 的上升而上升，这是合理的情形。但是当 k=4 时， AUC 指标发生波动，说明叠加更多的层次会导致 学习的特征表示发生信息变化，这是需要避免的 情况。通过图 5(f) 中显示的各层中粒的数量的变 化曲线，可以看出，不同层间的粒度差异会随着 层数的增加而减少。在第 3 层和第 4 层间，这种 粒度差异几乎很小，意味着节点在第 3 层和第 4 层中的特征极为相似，若拼接过多类似的高阶 特征向量，导致节点自身的特征被弱化，使得最 终 Multi-GS 的输出表示不能在网络分析任务中 发挥出方法优势。 4 结束语 在网络表示学习中，如何让学习到的节点特 征表示能够保留网络结构的局部和全局特征，仍 是一个开放和重要的研究课题。本文结合分层递 阶的思想，提出一种无监督网络表示学习方法 Multi-GS，通过构建网络的深度结构解决 GCN 无 法有效捕获节点高阶相似性特征的问题。该方法 首先利用模块度增量逐步构建网络的多粒度分层 结构，然后利用 GCN 模型学习不同粒度空间中粒 的特征表示，最后将已学习的粒特征向量逐层映 射拼接为原始网络的节点表示。利用 MultiGS 可捕获多种网络结构信息，包括一阶和二阶相 似性、社团内相似性 (高阶结构) 和社团间相似性 (全局结构)。 1 000 1 500 2 000 2 500 3 000 3 500 0 1 2 3 4 粒化层数 (f) 不同粒层中粒的数量 粒层中粒的数量 1.00 0.95 0.90 0.85 0.80 0.75 0.70 8 AUC 16 32 64 128 节点向量维度 (e) 链接预测AUC值 图 5 参数敏感性分析 Fig. 5 Parametric sensitivity analysis k=0 k=1 k=2 k=3 k=4 0.7 0.6 0.5 0.4 0.3 0.2 8 Micro-F1 16 32 64 128 节点向量维度 (a) 节点分类Micro-F1值 0.7 0.6 0.5 0.4 0.3 0.2 8 Macro-F1 16 32 64 128 节点向量维度 (b) 节点分类Macro-F1值 0.30 0.25 0.20 0.15 0.10 0.05 0 8 NMI 16 32 64 128 节点向量维度 (c) 节点聚类NMI值 0.30 0.25 0.20 0.15 0.10 0.05 0 8 ARI 16 32 64 128 节点向量维度 (d) 节点聚类ARI值 ·1240· 智 能 系 统 学 报 第 14 卷
第6期 张蕾，等：基于多粒度结构的网络表示学习 ·1241· 为验证Multi-GS方法的性能，通过在4个真 learning of social representations[C]//Proceedings of the 实数据集上进行节点分类任务和链接预测任务， 20th ACM SIGKDD International Conference on Know- 并与几个经典的网络表示学习方法进行比较。从 ledge Discovery and Data Mining.New York,USA,2014: 实验结果上看，针对节点分类任务，使用多粒度 701-710. 结构的Multi-GS能够改进节点的特征表示，提升 [8]GROVER A,LESKOVEC J.node2vec:Scalable feature GCN模型的节点分类性能。但是由于网络结构 learning for networks[Cl//Proceedings of the 22th ACM 的多样性和复杂性，Muti-GS的粒化层数无法固 SIGKDD International Conference on Knowledge Discov- 定，必须根据不同结构的网络进行调整。针对链 ery and Data Mining.San Francisco,California,USA, 2016:855-864. 接预测任务，使用多粒度结构Multi-GS对 [9]CAO Shaosheng,LU Wei,XU Qiongkai.GraRep:learn- GCN模型的性能造成损害。说明节点间的低阶 ing graph representations with global structural informa- 邻近关系对链接预测任务是至关重要的。尽管如 tion[C]//Proceedings of the 24th ACM International on 此，在不使用多粒度结构的情况下，以AUC为评 Conference on Information and Knowledge Management. 价指标，相对于对比算法，Multi-GS的性能优势非 Melbourne,Australia,2015:891-900. 常明显。针对Multi--GS超参数敏感性的实验结 [10]PEROZZI B.KULKARNI V.CHEN Haochen,et al. 果可以看出，面对不同的网络分析任务，融合不 Don't walk,Skip!:Online learning of multi-scale network 同粒度的粒特征对Multi--GS的性能有着不同程 embeddings[C]//Proceedings of the 2017 IEEE/ACM In- 度的影响。 ternational Conference on Advances in Social Networks 未来工作方向包括探索其他网络粒化分层技 Analysis and Mining 2017.Sydney,Australia,2017: 术和继续深人研究不同的层和不同粗细的粒以及 258-265. 不同类型的网络结构对Muti-GS的影响。 [11]CAO Shaosheng,LU Wei,XU Qiongkai.Deep neural networks for learning graph representations[C]//Proceed- 参考文献： ings of the 30th AAAI Conference on Artificial Intelli- [1]涂存超，杨成，刘知远，等.网络表示学习综述).中国科 gence.Phoenix,USA,2016:1145-1152 学：信息科学，2017,47(8)：980-996. [12]RIBEIRO L F R,SAVERESE P H P,FIGUEIREDO D R. TU Cunchao,YANG Cheng,LIU Zhiyuan,et al.Network struc2vec:Learning node representations from structural representation learning:an overview[J].Scientia sinica in- identity[C]//Proceedings of the 23rd ACM SIGKDD In- formationis,2017,47(8):980-996. ternational Conference on Knowledge Discovery and [2]SHEIKH N,KEFATO Z T,MONTRESOR M.Semi-su- Data Mining.Halifax,Canada,2017:385-394. pervised heterogeneous information network embedding [13]WANG Xiao,CUI Peng,WANG Jing,et al.Community for node classification using 1D-CNN[C]//Proceedings of preserving network embedding[C]//Proceedings of the the Fifth International Conference on Social Networks 31th AAAI Conference on Artificial Intelligence.San Analysis,Management and Security.Valencia,Spain, Francisco,California,USA,2017:203-209 2018:177-181 [14]方莲娣，张燕平，陈洁，等.基于三支决策的非重叠社团 [3]XU Guangluan,WANG Xiaoke,WANG Yang,et al 划分).智能系统学报，2017,12(3)293-300， Edge-nodes representation neural machine for link predic- FANG Liandi,ZHANG Yanping,CHEN Jie,et al.Three- tion[J].Algorithms,2019,12(1):12. way decision based on non-overlapping community divi- [4]HU Xuegang,HE Wei,LI Lei,et al.An efficient and fast sion[J].CAAl transactions on intelligent systems,2017, algorithm for community detection based on node role ana- 12(3:293-300 lysis[J].International journal of machine learning and cy- [15]DONNAT C,ZITNIK M,HALLAC D,et al.Learning bernetics,.2019,10(4):641-654 structural node embeddings via diffusion wavelets[C]// [5]PEREDA M,ESTRADA E.Visualization and machine Proceedings of the 24th ACM SIGKDD International learning analysis of complex networks in hyperspherical Conference on Knowledge Discovery Data Mining space[J].Pattern recognition,2019,86:320-331. London.UK,2018:1320-1329. [6]SHI Chuan,HU Binbin,ZHAO WX,et al.Heterogeneous [16]CHEN Haochen,PEROZZI B,HU Hifan,et al.HARP: information network embedding for recommendation[]. hierarchical representation learning for networks[C]//Pro- IEEE transactions on knowledge and data engineering, ceedings of the 32th AAAl Conference on Artificial Intel- 2019,31(2):357-370. ligence.New Orleans,Louisiana.USA.2018:2127-2134. [7]PEROZZI B.AL-RFOU R,SKIENA S.DeepWalk:online [17]ZHANG Si,TONG Hanghang,XU Jiejun,et al.Graph
为验证 Multi-GS 方法的性能，通过在 4 个真 实数据集上进行节点分类任务和链接预测任务， 并与几个经典的网络表示学习方法进行比较。从 实验结果上看，针对节点分类任务，使用多粒度 结构的 Multi-GS 能够改进节点的特征表示，提升 GCN 模型的节点分类性能。但是由于网络结构 的多样性和复杂性，Multi-GS 的粒化层数无法固 定，必须根据不同结构的网络进行调整。针对链 接预测任务，使用多粒度结 构 Multi-G S 对 GCN 模型的性能造成损害。说明节点间的低阶 邻近关系对链接预测任务是至关重要的。尽管如 此，在不使用多粒度结构的情况下，以 AUC 为评 价指标，相对于对比算法，Multi-GS 的性能优势非 常明显。针对 Multi-GS 超参数敏感性的实验结 果可以看出，面对不同的网络分析任务，融合不 同粒度的粒特征对 Multi-GS 的性能有着不同程 度的影响。 未来工作方向包括探索其他网络粒化分层技 术和继续深入研究不同的层和不同粗细的粒以及 不同类型的网络结构对 Multi-GS 的影响。 参考文献： 涂存超, 杨成, 刘知远, 等. 网络表示学习综述 [J]. 中国科 学: 信息科学, 2017, 47(8): 980–996. TU Cunchao, YANG Cheng, LIU Zhiyuan, et al. Network representation learning: an overview[J]. Scientia sinica informationis, 2017, 47(8): 980–996. [1] SHEIKH N, KEFATO Z T, MONTRESOR M. Semi-supervised heterogeneous information network embedding for node classification using 1D-CNN[C]//Proceedings of the Fifth International Conference on Social Networks Analysis, Management and Security. Valencia, Spain, 2018: 177–181. [2] XU Guangluan, WANG Xiaoke, WANG Yang, et al. Edge-nodes representation neural machine for link prediction[J]. Algorithms, 2019, 12(1): 12. [3] HU Xuegang, HE Wei, LI Lei, et al. An efficient and fast algorithm for community detection based on node role analysis[J]. International journal of machine learning and cybernetics, 2019, 10(4): 641–654. [4] PEREDA M, ESTRADA E. Visualization and machine learning analysis of complex networks in hyperspherical space[J]. Pattern recognition, 2019, 86: 320–331. [5] SHI Chuan, HU Binbin, ZHAO W X, et al. Heterogeneous information network embedding for recommendation[J]. IEEE transactions on knowledge and data engineering, 2019, 31(2): 357–370. [6] [7] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2014: 701–710. GROVER A, LESKOVEC J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, California, USA, 2016: 855–864. [8] CAO Shaosheng, LU Wei, XU Qiongkai. GraRep: learning graph representations with global structural information[C]// Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. Melbourne, Australia, 2015: 891–900. [9] PEROZZI B, KULKARNI V, CHEN Haochen, et al. Don't walk, Skip!: Online learning of multi-scale network embeddings[C]//Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017. Sydney, Australia, 2017: 258–265. [10] CAO Shaosheng, LU Wei, XU Qiongkai. Deep neural networks for learning graph representations[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence. Phoenix, USA, 2016: 1145–1152. [11] RIBEIRO L F R, SAVERESE P H P, FIGUEIREDO D R. struc2vec: Learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax, Canada, 2017: 385–394. [12] WANG Xiao, CUI Peng, WANG Jing, et al. Community preserving network embedding[C]//Proceedings of the 31th AAAI Conference on Artificial Intelligence. San Francisco, California, USA, 2017: 203–209. [13] 方莲娣, 张燕平, 陈洁, 等. 基于三支决策的非重叠社团 划分 [J]. 智能系统学报, 2017, 12(3): 293–300. FANG Liandi, ZHANG Yanping, CHEN Jie, et al. Threeway decision based on non-overlapping community division[J]. CAAI transactions on intelligent systems, 2017, 12(3): 293–300. [14] DONNAT C, ZITNIK M, HALLAC D, et al. Learning structural node embeddings via diffusion wavelets[C]// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London, UK, 2018: 1320–1329. [15] CHEN Haochen, PEROZZI B, HU Hifan, et al. HARP: hierarchical representation learning for networks[C]// Proceedings of the 32th AAAI Conference on Artificial Intelligence. New Orleans, Louisiana, USA, 2018: 2127–2134. [16] [17] ZHANG Si, TONG Hanghang, XU Jiejun, et al. Graph 第 6 期 张蕾，等：基于多粒度结构的网络表示学习 ·1241·
·1242· 智能系统学报 第14卷 convolutional networks:algorithms,applications and BioGRID interaction database:2008 update[J].Nucleic open challenges[C]//Proceedings of the 7th International acids research,2008,36:D637-D640. Conference on Computational Data and Social Networks. [27]GAO Hongchang,HUANG Heng.Self-paced network Shanghai,China,2018:79-91. embedding[C]//Proceedings of the 24th ACM SIGKDD [18]KIPF T N,WELLING M.Semi-supervised classification International Conference on Knowledge Discovery with graph convolutional networks[C/OL].[2019-01-28]. Data Mining.London,UK,2018:1406-1415. https://arxiv.org/pdf/1609.02907.pdf. [28]TANG Lei,LIU Huan.Relational learning via latent so- [19]LI Qimai,HAN Zhichao,WU Xiaoming.Deeper insights cial dimensions[C]//Proceedings of the 15th ACM SIGK- into graph convolutional networks for semi-supervised DD International Conference on Knowledge Discovery learning[C]//Proceedings of the 32th AAAI Conference and Data Mining.Paris,France,2009:817-826. on Artificial Intelligence.New Orleans,Louisiana,USA. [29]FAWCETT T.An introduction to ROC analysis[J].Pat- 2018:3538-3545. tern recognition letters,2006,27(8):861-874. [20]张燕平，张铃，吴涛.不同粒度世界的描述法一商空 [30]FAHAD A,ALSHATRI N,TARI Z,et al.A survey of 间法J.计算机学报，2004,27(3)：328-333 clustering algorithms for big data:Taxonomy and empir- ZHANG Yanping,ZHANG Ling,WU Tao.The repres- ical analysis[J].IEEE transactions on emerging topics in entation of different granular worlds:a quotient space[J] computing,.2014,2(3):267-279 Chinese journal of computers,2004,27(3):328-333. [21]赵姝，柯望，陈洁，等.基于聚类粒化的社团发现算 作者简介： 法U.计算机应用，2014,3410)：2812-2815 张蕾，女，1980年生，讲师，主 ZHAO Shu,KE Wang,CHEN Jie,et al.Community de- 要研究方向为数据挖掘、网络表示 tection algorithm based on clustering granulation[J]. 学习。 Journal of computer applications,2014,34(10): 2812-2815. [22]NEWMAN M E J.Fast algorithm for detecting com- munity structure in networks[J].Physical review E,2003. 69(6:066133 钱峰，男，1978年生，讲师，主要 [23]赵姝，赵晖，陈洁，等.基于社团结构的多粒度结构洞占 研究方向为数据挖掘、网络表示 据者发现及分析[J】.智能系统学报，2016,11(3)： 学习。 343-351. ZHAO Shu,ZHAO Hui,CHEN Jie,et al.Recognition and analysis of structural hole spanner in multi-granular- ity based on community structure[J].CAAI transactions on intelligent systems,2016,11(3):343-351. 赵蛛，女，1979年生，教授，博士 [24]KIPF T N,WELLING M.Variational graph auto-en- 生导师，博士，安徽省人工智能学会常 务理事，安徽省计算机学会理事，中国 coders[C/OL].[2019-01-28].https://arxiv.org/pdf/1611. 人工智能学会粒计算与知识发现专委 07308.pdf. 会委员，CIPS社会媒体处理专委会委 [25]MCCALLUM A K,NIGAM K,RENNIE J,et al.Auto- 员，主要研究方向为机器学习、粒计算 mating the construction of internet portals with machine 以及社交网络分析和科技大数据挖掘 learning[J].Information retrieval,2000,3(2):127-163. 应用研究。获得发明专利和软件著作权多项，发表学术论 [26]BREITKREUTZ B J,STARK C,REGULY T,et al.The 文60余篇
convolutional networks: algorithms, applications and open challenges[C]//Proceedings of the 7th International Conference on Computational Data and Social Networks. Shanghai, China, 2018: 79–91. KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C/OL]. [2019-01-28]. https://arxiv.org/pdf/1609.02907.pdf. [18] LI Qimai, HAN Zhichao, WU Xiaoming. Deeper insights into graph convolutional networks for semi-supervised learning[C]//Proceedings of the 32th AAAI Conference on Artificial Intelligence. New Orleans, Louisiana, USA, 2018: 3538–3545. [19] 张燕平, 张铃, 吴涛. 不同粒度世界的描述法——商空 间法 [J]. 计算机学报, 2004, 27(3): 328–333. ZHANG Yanping, ZHANG Ling, WU Tao. The representation of different granular worlds: a quotient space[J]. Chinese journal of computers, 2004, 27(3): 328–333. [20] 赵姝, 柯望, 陈洁, 等. 基于聚类粒化的社团发现算 法 [J]. 计算机应用, 2014, 34(10): 2812–2815. ZHAO Shu, KE Wang, CHEN Jie, et al. Community detection algorithm based on clustering granulation[J]. Journal of computer applications, 2014, 34(10): 2812–2815. [21] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2003, 69(6): 066133. [22] 赵姝, 赵晖, 陈洁, 等. 基于社团结构的多粒度结构洞占 据者发现及分析 [J]. 智能系统学报, 2016, 11(3): 343–351. ZHAO Shu, ZHAO Hui, CHEN Jie, et al. Recognition and analysis of structural hole spanner in multi-granularity based on community structure[J]. CAAI transactions on intelligent systems, 2016, 11(3): 343–351. [23] KIPF T N, WELLING M. Variational graph auto-encoders[C/OL]. [2019-01-28]. https://arxiv.org/pdf/1611. 07308.pdf. [24] MCCALLUM A K, NIGAM K, RENNIE J, et al. Automating the construction of internet portals with machine learning[J]. Information retrieval, 2000, 3(2): 127–163. [25] [26] BREITKREUTZ B J, STARK C, REGULY T, et al. The BioGRID interaction database: 2008 update[J]. Nucleic acids research, 2008, 36: D637–D640. GAO Hongchang, HUANG Heng. Self-paced network embedding[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London, UK, 2018: 1406–1415. [27] TANG Lei, LIU Huan. Relational learning via latent social dimensions[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 817–826. [28] FAWCETT T. An introduction to ROC analysis[J]. Pattern recognition letters, 2006, 27(8): 861–874. [29] FAHAD A, ALSHATRI N, TARI Z, et al. A survey of clustering algorithms for big data: Taxonomy and empirical analysis[J]. IEEE transactions on emerging topics in computing, 2014, 2(3): 267–279. [30] 作者简介： 张蕾，女，1980 年生，讲师，主 要研究方向为数据挖掘、网络表示 学习。 钱峰，男，1978 年生，讲师，主要 研究方向为数据挖掘、网络表示 学习。 赵姝，女，1979 年生，教授，博士 生导师，博士，安徽省人工智能学会常 务理事，安徽省计算机学会理事，中国 人工智能学会粒计算与知识发现专委 会委员，CIPS 社会媒体处理专委会委 员，主要研究方向为机器学习、粒计算 以及社交网络分析和科技大数据挖掘 应用研究。获得发明专利和软件著作权多项，发表学术论 文 60 余篇。 ·1242· 智 能 系 统 学 报 第 14 卷