面向不同网络结构和应用任务的网络表示学习研究进展

赵卫绩 孙晓霞 刘井莲 佟 良

（绥化学院信息工程学院 黑龙江绥化 152061)

随着Facebook，Twitter 微信，微博等在线社会媒体网络的蓬勃发展，产生了海量的网络大数据[1]。传统的网络分析技术是将网络表示成邻接矩阵，存在着数据稀疏性和高时间空间复杂度[2]。网络表示学习，即网络嵌入，就是将网络中的节点或者边投影到低维向量空间中，再用于后续的机器学习或者数据挖掘任务[3]，这对于对于复杂网络来说是一个比较新的尝试。近几年，国内外的相关研究工作及成果展示了网络表示学习技术的广阔发展前景。目前已经成功应用于节点分类、连接预测，社区发现等任务中。北京大学陈伟政等人和清华大学涂存超等人对近几年的网络表示学习技术与应用成果进行了全面的综述分析[1，3]，为网络表示学习技术研究者指引了方向。但这些综述性文献主要是针对的同构网络，基于此，在对网络表示学习技术的相关文献深入研究的基础上，本文分别对同构网络和异质网络上的著名的表示学习技术与应用成果进行阐述和分析，试图为网络表示学习初学者提供一个很好的指引方向。

一、问题定义

网络结构是信息系统的一种重要组织形式，传统网络的存储采用的是邻接矩阵，但由于网络中大部分节点间没有连接，所以邻接矩阵非常稀疏，不利于存储计算。因此，近年来，兴起了网络表示学习（Network Representation Learning，NRL），也称为网络嵌入（NetworkEmbedding，NE），采用低维、稠密、实值的向量表示网络中的节点，解决了传统网络存储数据稀疏问题。首先，参考文献[4]中的信息网络和元路径定义并进行扩展，给出与网络表示学习相关的定义1和定义2，具体如下。

定义1 信息网络[4]，信息网络可以表示为一个图G=(V，E，A，R)，其中 V 是节点集合；E 是节点间边的集合；A 是节点类型；R 是边类型。从 V 到A 存在映射 φ：V→A；从 E到R 存在映射：Ψ：E→R。当节点类型|A|=1，边类型|R|=1，|A|+|R|=2，表示是一种同构网络；当|A|+|R|＞2，表示的是一种异质网络，其中|A|=2，|R|=1，表示的是一种最简单的异质网络，即二分网络。异质网络中一般存在多种关系或多种类型节点。Rk=＜Ai，Aj＞两个类型的节点间通过一种类型边连接，这里的i 和j 可以相同，也可以不同，因为同类型节点可能存在边的情况，此外Rk中k 也可能值为多个，因为两个类型节点可以存在多种关系，比如学生跟老师可以是师生关系，可能还同时是父子关系。例如，DBLP 学术信息网络，作者（Writer，简写W），论文（Paper，简写P），发表处（Conference or Journal，简写V），在这里节点类型A={W，P，V}，关系类型 R={R1，R2，R3，R4，R5，R6}，其中 R1，R2分别表示的是作者和文章之间的写与被写关系，R3，R4分别表示期刊或会议和文章之间的发表与被发表关系，R5，R6分别表示文章和文章之间的引用与被引用关系，这六种关系可以形成一个数目信息网络模式。一般为了方便，作者，论文和发表处仅用三种关系来表达，分别是作者与论文是发表关系，论文与期刊或会议是出版关系，论文与论文是引用关系。

定义2 元路径[4]，元路径描述的是网络中节点类型之间是如何关联的，一条元路径是节点类型与边类型形成的交替序列，元路径可以看成是网络模式图中的子图。例如，在DBLP学术信息网络中，WPW是一条元路径，表示的是两个作者共同发表一篇论文，WPVPW是一条元路径，表示的是两个作者在同一处发表论文。

参考文献[1]中对网络表示学习的定义并进行扩展，给出定义3，如下。

定义3 网络表示学习[1]，是将网络中的节点学习低维稠密的向量表示，网络表示学习的任务是对每个节点v 学习一个低纬的实数向量，Rv∈Rd，其中，d＜＜|V|，|V|是网络中的节点总个数。网络中的节点V，映射函数f：V→R(|V|*d。对于异质网络表示学习，由于节点相似度与异质网络中元路径相关，因此除了学习节点的低纬实数向量，同时还要学习关系的低纬实数向量。在大规模网络数据中，节点之间的链接关系可能会非常复杂，通过在低维向量空间中进行分析，可以很直观地观察节点之间的关系。

二、基于不同网络结构的表示学习

近年来，网络表示学习，成为了复杂网络分析中的一个新兴研究热点，网络表示学习是衔接网络原始结构和网络应用任务的桥梁，网络表示学习算法是将网络信息转化为低维稠密实数向量，用作机器学习算法的输入[3]。

（一）同构网络表示学习。随着著名的网络表示学习算法word2vec在图像处理、自然语言处理上的成功应用，掀起了基于表示学习的研究热潮[5]。出现了著名的网络表示学习典型算法 DeepWalk 算法，Line 算法，Node2vec 算法。2014年，Perozzi等人提出了著名的基于深度学习技术的Deepwalk算法[6]，实现了从词序列到图上的一个扩展，通过在图上进行随机游走获取网络的局部结构，采用SkipGram 的方法进行网络中节点的表示学习，使用随机梯度下降的方法来优化参数。Deepwalk算法的随机游走是随机游走随机均匀地选取网络节点，并生成固定长度的随机游走序列，将此序列类比为自然语言中的句子，然后应用skip-gram 模型学习节点的分布式表示。2015年，清华大学唐建等人提出一种适用于大规模的有向带权图的LINE算法[7]，通过节点对的一级接近度和二级接近度进行概率建模，来刻画节点间关系，参数学习同样由梯度下降算法决定。在LINE算法里，一阶接近度是指如果网络中两个节点之间存在边，那么它们之间的一阶接近度是这条边的权重，没有边相连则接近度等于0。二阶接近度是指如果网络中两个节点有邻居节点，那么它们之间的二阶接近度是它们邻居集合的相似度，没有共同好友则接近度等于0，文献[7]在实验中证明了LINE算法在节点标签预测任务上要优于Deepwalk 算法。2016年，Grover 等人对Deepwalk 算法进行改进，提出了著名的Node2Vec[8]，主要的创新点在于改进了随机游走的策略，定义了两个参数p和q，在BFS和DFS中达到一个平衡，同时考虑到局部和宏观的信息，并且具有很高的适应性。也是采用SkipGram 的方法进行网络中节点的表示学习。

Deepwalk算法，相当于Node2vec算法的一种特例，就是最平凡情况下的让其随机游走。LINE算法本质上相当于一个限制的BFS，只不过它只找一阶和二阶邻居节点，不探寻到更远的节点。Node2Vec采用BFS能够探究图中的结构性质，而DFS则能够探究出内容上的相似性（相邻节点之间的相似性）。其中结构相似性不一定要相连接，甚至可能相距很远。

（二）异质网络表示学习。当前已经的网络表示学习技术大多是针对同构网络，已有的几篇网络表示学习综述性论文主要探讨的也都是同构网络表示学习。不同于以往网络表示学习综述文献，本文对异质网络表示学习研究进展也进行了探讨。2016年，著名数据挖掘大师韩家炜课题组Shang等人提出一篇用于相似搜索的异质网络表示学习的Esim算法[9]，ESim 模型考虑了节点间的不同关系，但是该模型缺点是过于依赖人为定义的元路径以及每条元路径人为设置的权重。2017年，Fu等人提出著名的HIN2Vec算法[10]，这是在国际会议CIKM2017上的一项重要工作，HIN2Vec 模型通过研究节点之间不同关系类型和网络结构，学习异质信息网络中丰富的信息。相比之前的一些模型，HIN2Vec模型保留了更多的上下文信息，不仅假设存在关系的两个节点是相关的，而且还区分节点之间的不同关系。主要贡献是：判断节点对间关系，将一个多分类问题转化为二分类。HIN2Vec模型分为两部分：基于随机游走的数据生成部分和表示学习部分。数据生成部分，基于随机游走和负采样生成符合目标关系的数据，以用于表示学习。表示学习部分是一个神经网络模型，通过最大化预测节点之间关系的可能性，同时学习节点和关系的表示向量。这种多任务学习方法能够把不同关系的丰富信息和整体网络结构联合嵌入到节点向量中。该文论文考虑到了节点和关系的语义是不同的，对关系向量运用了一个正则函数，对于随机游走过程中可能会出现循环节点的问题，论文也给出了解决方法并进行了实验分析，同时阐述了负采样时候节点及节点类型的选择，该论文有一定的创新。论文的不足之处在于随机游走过程中如何消除循环，没有给出较为详细的解释说明。2017年，Swami等人提出了对异质网络的表示学习算法 metapath2vec 和metapath2vec++[11]，这是Swami 等人的国际重要会议KDD2017 的一项重要工作。Swami 等人是通过元路径来指导随机游走的邻居节点的选择，本质上是一种带偏置的随机游走，由元路径来指导随机游走的跳转，如果下一节点的类型满足元路径中的类型，那么跳转的概率就是该类型节点数分之一（等概率跳转），否则，全部为0，然后基于异质的skipgram 模型进行节点表示学习。其中metapath 算法和DeepWalk、node2vec 算法基本类似，只是处理的网络不同，分别对应同质网络和异质网络，但是其本质似乎都是通过随机游走选择邻居节点，然后用skip-garm 模型学习节点的表示，不同的是随机游走的过程中，邻居节点的跳转选择策略是不同的，metapath2vec++用不同类型节点的特征表示进行归一化，对每种类型节点指定不同的一组多项式分布，相当于在输出层根据节点类型，把异质网络分解成不同的同质网络。

三、面向应用任务的网络表示学习

文献[3]对面向链接预测和节点分类的应用任务给予详尽的介绍。在这里不再重复，社区结构是复杂网络中一个重要特征，社区发现问题是一种对网络中的节点进行无监督的聚类。近几年，国内外学者对社区发现问题进行深入研究，但基于网络表示学习技术的社区发现具有较少的研究。2013年，Yang 等人给出一种基于非负矩阵分解方法重叠社区发现算法BIGCLAM[12]，BIGCLAM 是为每个网络中的节点学习了一个上述的k维非负向量表示，最大化目标是整个网络结构的最大似然概率。最优化求解参数的过程也是由随机梯度下降算法实现。2016年，天津大学何东晓等人把基于深度学习技术的网络表示学习应用到社区发现研究中[13]，实验结果表明，相比较一些经典的社区发现算法，具有较好的效果。以上网络表示学习算法中随机游走仅仅是基于节点的邻居节点，没有考虑到网络中社区信息。2018年，Keikha等人提出一种新颖的CARE 算法[14]，首先利用getphi 识别出网络中的全局社区结构，然后在起始节点的邻居或所在社区内进行随机游走。采用SkipGram的方法进行网络中节点的表示学习。该算法应用在多标签分类和链接预测中具有较好的性能。

四、结语

近几年，国内外学者在网络表示学习研究上做了大量工作，斯坦福大学Jure Leskovec，新加坡大学的hongyan cai，清华大学唐建、涂存超课题组等人，涂，存超等人分别在同构异质网络表示做了大量工作，取得了很大进展，并对之前的网络表示学习工作进行过系统的前面的介绍和总结，https：//github.com/thunlp/NRLPapers。清华大学刘知远课题组就知识表示学习研究进展也进行全面的介绍和系统的总结。在深入研究网络表示学习算法和综述性文献的基础上，本文对近几年的网络表示学习技术和面向社区发现任务的表示学习研究进行了全面介绍和分析，对以往表示学习综述文献是一个很好的补充，为网络表示学习初学者起到一定的指导作用。未来研究方向：融合异质网络表示学习与社区发现的研究，动态网络的社区发现研究。