第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·