网络表示学习发展综述

(西华大学计算机与软件工程学院 四川 成都 610039)

引言

伴随着互联网的快速普及、在线社交网络迅猛发展，每天网络上都会产生量级极大的数据，在已经成为当前计算机科学重要研究领域的网络数据挖掘中，这些带挖掘的数据无疑具有极大的研究价值。

网络数据最鲜明的特点就体现在数据节点之间存在着链接关系，这也反映了网络中样本点并非完全独立。表示学习的目的是为网络中的每一个节点分配某个线性空间中的向量，使得这些向量能够保持原来网络的结构信息，这对于社会网络分析以及机器学习领域具有重大的意义[1]。

一、网络表示学习方法介绍

网络表示学习，又名网络嵌入、图嵌入，目的在于用低维紧凑的向量表示网络中的节点，为下一步的任务提供有效的特征表示。让映射出来的向量能够拥有表示和推理的功能，方便下游计算，从而能够使得到的向量表示使用于社交网络中广泛使用的应用场景里去。因此，网络表示学习具有相当重大的意义。

1.基于因子分解的方法

基于结构的因子分解方法，大都是用传统的方法进行因子分解[2]。

(1)Locally Linear Embedding (LLE)

局部线性嵌入(Locally Linear Embedding, LLE)是无监督的非线性降维算法，是流形学习经典算法。LLE假设高维空间的数据样本在局部依旧包含欧式空间的性质，即“邻域保持”思想：该节点可以通过其邻居节点点的线性组合重构出来。

假使有样本节点y1，用K-NN算法找到与它最接近的三个样本节点y2，y3，y4。使用这三个邻域节点表示该样本节点，即：

y1=w12y2+w13y3+w14y4

能够发现，在降维前后权重系数基本不发生改变的。利用这种局部相关性，LLE在局部建立降为映射关系，之后再将这种局部映射推广至整个网络。

(2)Laplacian Eigenmaps

拉普拉斯特征映射的思想比较简单。观察问题的角度与LLE类似，用子图的思想去构建数据之间的关系。

通过拉普拉斯特征映射可以体现出数据内在的流形结构。如果节点之间的边权重越大，就说明这两个节点的距离越近，那么在嵌入后节点对应的值就应越接近。 最优化目标如下：

=tr(YTLY)

其中L是对应网络的拉普拉斯矩阵。即 L=D-A。D 是度矩阵，A 是邻接矩阵。约束条件为1=YTDY, 移除了嵌入时的随意缩放因素。问题的标准解就是求标准化拉普拉斯矩阵最小的几个特征值所对应的特征向量。

2.基于随机游走的方法

基于随机游走的方法，主要有DeepWalk和Node2Vec[3]。

(1)DeepWalk

DeepWalk是最早提出的基于Word2Vec的节点向量化模型，是把语言模型的方法用在了社会网络之中，从而可以用深度学习的方法，除了表示节点以外，还可以反映节点间的拓扑关系，即表现出社会网络中的社会关系。

其大致思路，就是使用构造节点在网络上的随机游走路径，模拟文本生成的过程，给出节点序列，再将该序列向量化，然后用Skip-gram和Hierarchical Softmax模型对随机游走序列中每个局部序列内的节点对进行概率建模，将随机游走序列的似然概率最大化，利用随机梯度下降方法调整参数。

(2)Node2Vec

Node2Vec通过改进随机游走序列生成的方法对DeepWalk算法进行了拓展。在DeepWalk中，是完全随机地去选取随机游走序列中下一个节点的，而node2vec通过加入两个超参数p和q，将宽度优先搜索(BFS)和深度优先搜索(DFS)的思路加入到随机游走序列的生成进程中。BFS重视邻居节点，并描绘了相对邻域的表示，BFS中的节点通常会多次出现，使得核心节点邻域中节点的方差减少；DFS则注重高层次节点间同质性的刻画。即BFS能够体现图的结构性质，而DFS则能够反映邻居节点的相似性大小。

3.基于深度学习的方法

在网络表示学习中，还有基于深度学习的方法，比较具有代表性的方法就是Structural Deep Network Embedding (SDNE)[4]。

SDNE是第一个将深度学习应用于网络表示学习中的方法。它是一种半监督的学习模型。它属于在LINE模型的基础上做出了拓展，在使用深度学习的方法进行网络表示学习中结合了一阶估计和二阶估计的优点，以此来表示出网络中的局部以及全局结构属性，具有很强的适应性。SDNE利用了深度自动编码器分别优化1阶和2阶相似度，通过最小化节点表示之间的欧式距离来保留邻居节点之间的相似度。学习得到的向量表示能够包含网络高度非线性的局部和全局结构，而且对稀疏网络也有很高的适用性。

4.其他方法

LINE 的大概思路就是把一个大规模网络中的所有节点根据其关系的紧密程度映射到向量空间中，表征成为低维向量，联系紧密的节点会被映射到接近的位置，而在网络中衡量两个节点联系紧密程度的重要标准就是这两个节点之间边的权值。该模型既想到节点间的一阶相似性：两个节点之间边的权值较大就认为这两个节点比较相似，也兼顾到了二阶相似性：即两个节点也许没有直接相连的边，但假如它们的一阶公共节点相当多，那么也认为这两个节点是比较相似的。

LINE不仅保留了网络局部和全局的网络结构信息，还可以用于含有无权或有权边的大型网络，并且相当有效。

二、结论

本文总结了网络表示学习的节点表示学习的主要方法。上述网络表示学习方法，基本涵盖了网络表示学习的研究。