网络顶点表示学习方法

周晓旭 刘迎风 付英男 朱仁煜 高明

摘要：网络是一种常用的数据结构，在社交、通信和生物等领域广泛存在，如何对网络顶点进行表示是学术界和工业界广泛关注的难点问题之一，网络顶点表示学习旨在将顶点映射到一个低维的向量空间，并且能够保留网络中顶点问的拓扑结构，本文在分析网络顶点表示学习的动机与挑战的基础上，对目前网络顶点表示学习的主流方法进行了详细分析与比较，主要包括基于矩阵分解、基于随机游走和基于深度学习的方法，最后介绍了衡量网络顶点表示性能的方法。

关键词：网络嵌入：随机游走：矩阵分解：深度神经网络

中图分类号：TP391 文献标志码：A DOI：10.3969/j，issn，1000-5641.202091007

0引言

现实世界中普遍存在类型丰富多样的网络数据结构，如社交网络、通信网络、生物网络等，这些网络表示实体之间的关系，规模从数百个顶点到数百万个甚至数十亿个顶点，分析网络在许多应用中都发挥着至关重要的作用，因此也得到学术界和工业界越来越多的关注，对网络进行有效分析首先要对网络顶点进行表示，邻接矩阵、拉普拉斯矩阵等传统表示方法展示了顶点间的显式关系，更复杂的、高阶的拓扑结构很难被有效地表示出来，而且这类传统方法通常复杂度较高，难以应用在大规模网络上，为了突破传统方法的“瓶颈”，顶点嵌入技术旨在尽可能保留网络拓扑结构、顶点语义信息和顶点属性的前提下，将顶点映射到低维向量空间中，该空间也被称之为顶点嵌入空间，嵌入空间不仅能够重构原始网络，而且保留了网络的拓扑特征，如果两个顶点在网络拓扑结构上是相似的，那么这两个顶点在嵌入空间中也要尽量靠近。

在顶点嵌入后，可以利用机器学习或者深度学习方法在嵌入空间中高效地进行网络分析，如链接预测、顶点分类和网络可视化，链接预测指预测缺失的链接或将来可能产生的链接，顶点分类指基于有标记的顶点和网络拓扑关系进一步确定其他顶点的标签，网络可视化将原始网络降维到二维空间中展示，有助于直观理解网络中顶点间的相互关系。

1问题与挑战

由于网络数据结构存在一些独特的特征，致使网络顶点表示学习面临众多问题和挑战，其中三个最关键挑战分别是：

（1）稀疏性真实世界中的網络顶点的度通常服从长尾分布，能够观察到的边仅占很小的比例，许多顶点间的边存在缺失，实际上大多数顶点仅有很少的连接，少数顶点拥有更多的连接，由于稀疏的网络链接给顶点表示造成了困难，因此网络中普遍存在的稀疏特征给顶点表示学习带来了很大的挑战，

（2）保留结构和属性顶点表示学习需要保留原始网络中的局部结构和全局结构，网络中彼此相近的顶点在嵌入空间中也应该尽量靠近，顶点间的相对位置也要保持不变，此外，网络顶点的属性信息也是网络的重要组成部分，但如何将这些信息与网络拓扑结构综合在一起？因此，同时保留顶点的结构和属性信息是网络顶点嵌入学习的重要挑战。

（3）可扩展性现实世界中的信息网络其规模越来越庞大，从数百个顶点到数百万个顶点甚至数十亿个顶点，分析大规模信息网络的需求越来越迫切，但也要避免耗费昂贵的计算代价，因此，网络表示学习方法要具备可扩展性，能够针对大规模网络进行顶点表示学习，并进一步支持针对大规模网络的其他分析与应用。

2问题定义

定义1（网络）

网络G（V，E）由顶点集合V={V1…，Vn）和边集合E={eij）构成的二元组，其中ei表示Vi与Vi之间的连接，无权网络G的邻接矩阵记为A，其中当Vi与Vj存在连接时，aij=1.否则aj=0.对于无向网络G，A具有对称性，即aij=aji，带权网络G的权重矩阵记为S其中sij表示Vi与vj连接上的权重，权重能够表示顶点间联系的强弱。

网络顶点在嵌入低维向量空间的过程中，需要利用顶点间的局部相似性，在LINE中提出了顶点间的局部结构相似性。

定义2（一阶相似性）一阶相似性表示网络中两个顶点间的局部相似性，如果顶点%和%间有边连接，则边上的权重sij即为顶点vi和vj的一阶相似度;若没有边连接，sij=0.则一阶相似性也为0.

在现实网络中，能够观察到的边仅占很小的比例，而许多顶点间的边都缺失了，这种顶点对的一阶相似性为0.一阶相似性忽略了顶点间的隐式关系，因此为了保留更丰富的网络结构，进一步定义顶点之间的高阶相似性。

定义3（二阶相似性）二阶相似性表示网络中两个顶点之间的邻居相似性，用pi=（wi，1.…，wi V ）表示顶点vi与其他顶点的一阶接近度，wij表示顶点vi和顶点vj的一阶相似性，二阶相似性可以，通过pi和pj的相似性确定，若顶点vi与vj间不存在一样的邻居顶点，则二阶相似性为

二阶相似性考虑两个顶点邻域间的相似性，如果它们具有相似的邻居，则认为它们是相似的，在社交网络中，有相同朋友的人往往具有相似的兴趣，很可能也会成为朋友，在单词共现网络中，经常与同一组单词同时出现的单词往往具有相似的含义。

如图1所示，顶点6和顶点7之间存在边，且权重较大，则认为两者一阶相似性较高，而顶点5和顶点6之间不存在边，则两者间的一阶相似性为0.但是由于它们的邻居重合度较高，则认为两者的二阶相似性较高。

学习到的顶点表示空间需要保留网络结构并可以重构原始的网络，如果两个顶点之间存在链接，为了保留网络关系，这两个顶点在嵌入空间中的距离也应相对较小。

3网络顶点表示学习方法的分类

长久以来，针对网络顶点表示学习已经提出了许多方法，本文根据它们在图的顶点表示方法上的差异，将这些模型分成三大类别：基于矩阵分解的方法、基于随机游走的方法和基于深度神经网络的方法，接下来介绍每一类里的代表性方法。

3.1基于矩阵分解的方法

对于有礼个顶点的网络G，用n×n的邻接矩阵A来表示网络的拓扑结构，每一行每一列的值代表顶点和其余顶点的连接关系，值为0表示顶点之间不存在边，邻接矩阵的行向量或列向量构成了顶点的一种n维表示，这种表示的维度通常都很高，而网络嵌入想要得到的是低维顶点向量表示，通过矩阵分解、维度约减，可以将高维的原始矩阵分解获得低维表示，例如，对邻接矩阵、拉普拉斯矩阵、转移概率矩阵等进行特征值分解、奇异值分解、非负矩阵分解，从而获得顶点的低维表示。

3.1.1Locall，y Linear Embedding

局部線性嵌入（Locally Linear Embedding，LLE）假设顶点可以由它的邻居向量线性表示，降维之后仍能保持同样的线性关系，即权重系数基本保持不变。

LLE首先利用K一最近邻算法或其他方法确定降维前顶点vi的k个邻居顶点，然后使用最小化均方误差找到线性表示的归一化权重系数wij，wij表示顶点vj对于重构顶点vi的重要性，即对于所有顶点：

3.3基于深度学习的方法

网络节点嵌入的学习目标是找到能将原始网络空间转换为低维向量空间的映射函数，网络的结构复杂，而且是非线性结构，因此之前通过线性模型寻找节点嵌入的方法不足以保留信息网络的非线性特征，而深度神经网络能够对数据中的非线性结构进行建模，在许多领域都得到了应用且获得了成功，因此许多工作用端到端的深度网络学习网络顶点表示。

3.3.1SDNE

与使用浅层模型的嵌入方法相比，真实网络结构较为复杂，浅层模型找到的顶点表示向量不能保存网络高阶的非线性特征，而深度学习擅长捕捉非线性特征，Structural Deep Network Embedding，简称SDNE，率先将深度学习应用在网络表示学习中，与之前使用神经网络对图进行表示的已有工作不同，SDNE学习的是可以在任务之间利用的低维表示，而且考虑了顶点之间的一阶和二阶相似性，如图6所示，模型使用半监督学习能够同时保留一阶和二阶网络相似性，SDNE首先利用无监督学习，根据顶点的邻居结构，通过多个非线性函数构成自动编码器获取顶点的潜在表示，yi（k）=σ（w（k）yi（k-1）+6（k）），以此保留网络的二阶相似性，然后为了保留一阶相似性，借助拉普拉斯特征映射方法，有监督地根据邻接矩阵代表的先验知识调整节点的嵌入表示，SDNE遵循的思路是当相似的顶点在嵌入空间中被映射得较远时，就让模型的损失变大，模型的损失函数为：

3.3.2SiNE

符号网络是指具有正边和负边的信息网络，正边可以表示朋友、信任、喜欢、支持等积极关系，负

4应用

学习到的网络顶点嵌入可以应用到后续任务中，如链接预测、顶点分类和可视化，通常可以根据这些任务上的评价指标来衡量学习到的网络顶点嵌入的优劣。

4.1链接预测

链接预测是指预测顶点对之间是否存在边，这些边可能是缺失的，也可能会在将来网络的不断演化中形成，在社交网络中，链接预测技术可以预测两个人是否为朋友关系，以此推荐可能的好友，在生物网络中，链接预测用来判断蛋白质之间是否存在未知的相互作用，这可以提高在真实世界中实验的目标性，减少昂贵的实验测试。

4.2顶点分类

顶点分类是利用已知标签顶点来推测其他顶点的标签，在网络中，顶点会带有标签，表示实体的属性，例如，社交网络中的标签可以表示人的兴趣、喜恶等，在引用网络中，标签可以表示文章的关键词或研究领域，生物网络中顶点的标签可以表示实体的功能，由于标记成本高或者其他原因，只有少数顶点被打上了标签，网络中大部分顶点的标签是未知的。

4.3网络可视化

网络可视化是将原始网络降维到二维空间中以方便展示，应用主成分分析或者t-sNE，可以将学习的顶点嵌入进行可视化，以观察网络的空间结构，如图9所示，a-2）为使用Deepwalk学习到的空手道俱乐部网络a-1）的可视化结果，b）为使用LINE学习到的DBLP网络的可视化结果，通过将网络表示进行可视化可以证明模型的有效性。

5总结

本文回顾了近年来网络顶点表示学习的模型和算法，将现有的模型按照基于矩阵分解、基于随机游走和基于深度学习分为3类，并且介绍了每一类中具有代表性的算法，算法的目标是能够保留网络的结构和属性特征，基于矩阵分解的模型适合于小型网络，模型复杂度较高;基于随机游走的模型借鉴了自然语言处理领域的思想，将随机序列视为语句，顶点视为单词，再进行后续的分析处理;新兴的深度学习将自编码器、图卷积技术应用到顶点表示学习中，适合处理大型的网络，网络顶点表示学习的未来研究方向是利用非线性模型，如基于深度学习的算法，研究不同属性的图，如符号图、异构图和二分图，网络嵌入方法还可以应用到知识图谱、生物学网络和社交网络等领域以方便研究。