3.2 基于网络结构信息的网络表示方法

基于网络结构信息的网络表示方法只考虑网络节点之间的链接关系。给定网络图 G=(V, E)。其中V 表示网络中的节点集合；E 是网络中的边集合网络表示学习的目的在于从网络信息中学习得到各个节点的低维表示是向量的维度。

这部分分别介绍 DeepWalk、LINE 和 GraRep三种模型。其中 DeepWalk 是以 Skip-gram 模型为基础，本质上使用了二阶的网络上下文信息；LINE模型显示地提出了网络表示方法的目标函数，考虑了一阶和二阶的上下文信息；GraRep 对 LINE 模型进行了拓展，可以对节点的任意阶上下文信息建模。

DeepWalk 模型

DeepWalk 模型首先采用随机游走 (randomwalk) 的方法产生标准的输入序列，然后使用 Skip-gram 模型对序列建模得到网络节点表示（具体算法见表 1）。随机游走首先基于均匀分布得到序列的起始点，然后从当前点的邻居节点中随机选择一点作为后续节点，依次迭代直到产生特定长度的序列。
相比基准的模型方法 (Spectral Clustering [7] 、Modularity [8] 、EdgeCluster [22] 、wvRN [23] )，DeepWalk 模型有效地解决了训练数据稀疏的问题，在训练数据较少的情况下，F 1 值上有 10% 的提高。在一些标准数据集中，仅使用 60% 的训练数据 DeepWalk 模型就可以超过使用 100% 训练数据的所有基准方法。

LINE 模型

文献 [17] 提出了一种适用于不同类别网络图结构（有向图、无向图和加权图）的网络学习模型LINE。具体上，LINE 模型从一阶相似性 (first-orderproximity) 和二阶相似性 (second-order proximity)两方面设计目标函数。基于一阶或者二阶相似性，LINE 模型可以分别学习到一种网络表示。为了同时使用这两种相似性，LINE 模型将一阶节点向量和二阶节点向量拼接起来作为最终的节点表示。

一阶相似性表示网络中两个节点之间的点对相似性，具体为节点之间边的权重（如果点对不存在边，则其一阶相似性为 0）。为了建模一阶相似性，模型首先定义点对 υ i 和 υ j 联合概率为
其中 和 分别是节点υ i 和节点υ j 的向量表示。节点υ i 和υ j 的经验联合概率为表示边 (i, j) 上的权重， 。一阶相似性模型通过最小化概率分布 的KL距离来获得网络表示。

二阶相似性模型假设如果节点间共享相似的邻居节点，那么两者就趋于相似。具体上，点对之间的二阶相似性表示两个节点在整个网络上的一阶相似性的分布相似度（如果点对没有共同的相邻节点，则二阶相似性为 0）。在这种情况下，每个节点有目标节点和其他节点的上下文两个角色。形式上，用 和 分别指 υ i 作为目标节点的表示和 υ i 作为其他节点上下文的表示。二阶相似性模型首先定义节点 υ i 和 υ j 的条件概率为
节点 υ i 和 υ j 的经验条件概率，其中 d i是节点 υ i 的出度。通过最小化概率分布与之间的 KL 距离来获得二阶相似性模型的网络表示。

一阶相似性和二阶相似性模型都采用了基于边的负采样优化方法来得到网络节点表示。实验表明LINE 模型在语言网络、社交网络和论文引用网络的数据集上均超过了 DeepWalk 模型和基于随机梯度的矩阵分解方法[24] 。

GraRep 模型

文献 [18] 指出 LINE 模型中的一阶相似性和二阶相似性分别捕捉到节点间一阶和二阶的局部信息（如图 1（a）和（b）所示），并在此基础上提出更一般化的模型 GraRep。GraRep 模型可以捕捉更高阶的网络信息（如图 1（c）和（d）所示），并对每一阶的局部信息分别建模，最后串接各阶网络表示得到最终节点表示。
GraRep 模型基于概率转移矩阵来获得网络表示。首先定义一阶概率转移矩阵 A=D -1 S，其中 S 为邻接矩阵（S ij =wei ij ）、D 为度对角矩阵 (degreematrix)。所得到的A ij 是节点υ i 到υ j 的一阶转移概率。进一步，通过计算 可以得到 k 阶概率转移矩阵。GraRep 模型优化目标在于最大化 (c, w) 对的出现概率，同时最小化随机产生的 (c', w) 出现的概率，其中 w 为目标词、c 是 w 的上下文词、c' 是随机得到的上下文词。采用负采样的方法建模 k 阶信息，考虑 (c, w) 的出现概率，最大化的目标函数为
其中 表示从 w 到 c 的 k 步转移概率；σ（·）是 sigmoid 函数；λ 是负例的个数；上下文词c出现的概率为 根据文献[25]，优化上述式子本质上等价于将矩阵Y分解成W和C，其中 W 的每一行代表节点的表示，而 C 中的每一列表示节点作为上下文的表示。

GraRep 模型采用 SVD 矩阵分解的方法来得到网络节点的表示。相比 DeepWalk 和 LINE 模型，GraRep 模型考虑了更高阶的上下文信息，在网络结构数据上得到了更好的效果。值得一提的是，虽然在文献 [18] 中，GraRep 模型使用了复杂度较高的 SVD 矩阵分解的方法，但它也可以采用随机梯度下降的优化方法，因此该模型同样适用于大规模的网络结构。