1.背景

DeepWalk是一种学习网络中节点的隐式表征的新颖方法。这些隐式表征把社会关系编码到统计模型易于使用的连续的向量空间中。DeepWalk使用从删减的随机游走获得的局部信息，通过游走等价句子学习出隐式表征。DeepWalk还是可扩张的，它是一个构建增量结果的在线学习算法，并且是并行的。这些特性使其广泛适用于实际应用，如网络分类或异常检测。

2.原理

2.1 问题定义

考虑将社会网络成员分成若干类，令 $G=(V,E)$ ，其中 $V$ 代表网络中的成员， $E$ 代表它们的连接， $E∈(V×V)$ 且 $G_L=(V,E,X,Y)$ 是部分标注的社会网络，满足 $X∈ℝ^{|V|×S}$ ， $S$ 是每个特征向量空间的大小， $Y∈ℝ^{|V|×|y|}$ ， $y$ 是标签集。
在传统机器学习分类环境中，目标是学习一个从 $X$ 的元素到标签集 $y$ 的假定映射 $H$ 。在这种情况下，可以利用有关嵌入到结构 $G$ 的实例依赖的重要信息来取得较好的效果。
本文提出一种捕获网络拓扑信息的方法，在不把标签空间作为特征空间的一部分的情况下，使用无监督方法学习独立于标签分布的图结构特征。这种将结构表征和标签任务的分离避免了发生在迭代方法上的级联错误。此外相同的表征还可以用于考虑网络的多分类问题。
本文目标是学习 $X_E∈ℝ^{|V|×d}$ ，其中 $d$ 是潜在的维数。这里 $d$ 就是我们学习到的低维的隐藏的表示。这里的意思就是说，这里 $d$ 维的向量中，包含了社区结构，我们可以通过这个向量进行进一步的训练和对整个社区的进一步的学习。

2.2 随机游走

Random Walk简单的说就是在图中选择一个顶点，然后由这个顶点开始选择一个随机的相连的顶点访问，然后再随机选择一个这个访问的顶点的一个相连顶点……以此循环周而复始可以得到一个长度为N的顶点序列，这个序列就是以此随机游走的结果。所以很明显的可以看到，这个随机游走的序列具有如下几个特点：

捕捉了图中的局部特点
容易的进行并行计算，同时选择N个节点开始遍历即可
在图的拓扑发生改变的时候，不需要重新计算整个图
定义：
把以节点 $v_i$ 为起点的随机游走记作 $W_{v_i}$ 。随机游走是一个由随机变量 $W_{v_i}^1、 W_{v_i}^2 、W_{v_i}^3 、W_{v_i}^4 、...、W_{v_i}^k$ 决定的随机过程，使得 $W_{v_k}^{k+1}$ 是从节点 $v_k$ 的相邻节点中随机选择的。

2.3 语言建模

语言建模的目的是估计特定词序列出现在语料库的可能性。常见的语言模型：N-gram、CBOW、SkipGram
给定一个词序列： $W^n_1=(w_0,w_1,…,w_n)$

其中 $w_i∈V$ （词表），要在语料库上最大化 $Pr(w_n∣w_0,w_1,…,w_{n−1})$ 。
本文中提出了一种通过短随机游走来探索图的语言模型。这些游走可以被认为是一种特殊语言的短句和短语；直接模拟是估计在随机游走中访问过观测点 $v_i$ 之前所有节点的可能性：
$Pr(v_i∣(v_1,v_2,…,v_{i−1}))$

目标是学习隐式表征，不只是节点共现的概率分布，因此我们引入映射函数 $Φ:v∈V↦ℝ|V|×d$ 。映射 $Φ$ 表示与图中每个节点 $v$ 相关的隐式社会表征。实际上用自由参数的矩阵 $|V|×d$ 来表示 $Φ$ 。于是问题变成了估计可能性：
$Pr(v_i∣(Φ(v_1),Φ(v_2),…,Φ(v_{i−1})))$

但是，随着随机游走路径长度的增加，上述概率的计算会非常复杂，计算概率会变得行不通。因此，论文借鉴了Mikolov的两篇关于语言模型的论文^[1][2]，进行了三种处理：首先，用一个词预测整篇文章，而不是用一篇文章预测一个词；其次，文章由给定单词的左右单词，即邻居词组成；最后，忽略单词顺序，不再受限于词与词之间的顺序关系。由此，优化目标表示为：
$minΦ−logPr({v_i−w,…,v_i+w}∖v_i∣Φ(v_i))$

2.4 DeepWalk

该算法由两个主要部分组成：随机游走生成器和更新过程。随机游走生成器在图 $G$ 上均匀采样一个随机节点 $v_i$ 作为随机游走 $W_i$ 的起点。每次游走都对上一个访问到的节点均匀随机采样一个邻节点，直到达到最大长度 $（t）$ 。尽管将实验中的随机游走的长度设为定值，但对于相同长度的随机游走来说没有任何限制。这些游走可能会重新开始（回到起点），但是初步结果没有显示重新开始的任何优势。在实践中对每个起始节点指定了一些长度为 $t$ 的随机游走 $γ$ 。

3.源码

├── deepwalk
│   ├── __init__.py
│   ├── __main__.py
│   ├── graph.py
│   ├── skipgram.py
│   └── walks.py

4.参考文献

论文地址：https://arxiv.org/pdf/1403.6652.pdf
代码地址：https://github.com/phanein/deepwalk
https://www.shintaku.cc/posts/deepwalk/
http://lipixun.me/2018/01/11/deepwalk

DeepWalk