原文：DeepWalk: Online Learning of Social Representations
源码：phanein/deepwalk
摘要
DeepWalk是一种学习网络中节点的隐式表征的新颖方法。这些隐式表征把社会关系编码到统计模型易于使用的连续的向量空间中。DeepWalk使用从删减的随机游走获得的局部信息，通过游走等价句子学习出隐式表征。DeepWalk还是可扩张的，它是一个构建增量结果的在线学习算法，并且是并行的。这些特性使其广泛适用于实际应用，如网络分类或异常检测。
问题定义
考虑将社会网络成员分成若干类，令\(G=(V, E)\)，其中\(V\)代表网络中的成员，\(E\)代表它们的连接，\(E\in(V\times V)\)且\(G_L=(V, E, X, Y)\)是部分标注的社会网络，满足\(X\in\mathbb{R}^{|V|\times S}\)，\(S\)是每个特征向量空间的大小，\(Y\in\mathbb{R}^{|V|\times |\mathcal{Y}|}\)，\(\mathcal{Y}\)是标签集。
在传统机器学习分类环境中，目标是学习一个从\(X\)的元素到标签集\(\mathcal{Y}\)的假定映射\(H\)。在这种情况下，可以利用有关嵌入到结构\(G\)的实例依赖的重要信息来取得较好的效果。
本文提出一种捕获网络拓扑信息的方法，在不把标签空间作为特征空间的一部分的情况下，使用无监督方法学习独立于标签分布的图结构特征。这种将结构表征和标签任务的分离避免了发生在迭代方法上的级联错误。此外相同的表征还可以用于考虑网络的多分类问题。
本文目标是学习\(X_E\in\mathbb{R}^{|V|\times d}\)，其中\(d\)是潜在的维数。这些低维表示是分散的，表示每个社会现象在维度子集的压缩，并且每个维度贡献一个在空间上压缩的社会概念的子集。使用这些结构特征将增加属性空间来帮助确定分类。这些特征是普遍的，并可以用于任何分类算法（包括迭代法）。
学习社会表征
尝试根据以下特点学习社会表征：
- 普适性：真实社会网络是不断进化的，新的社会关系不需要再次重复学习过程。
- 团体性：隐式维度间的距离应当表示网络中相关成员的社会相似性。这样可以在网络中实现普遍化。
- 低维性：当标记数据很少时用低维模型能更好地概括、加快收敛和推断。
- 连续性：需要隐式表征在连续空间上建模部分社团关系。为了发现社团关系的细微差别，连续表征有健壮的社团间的平滑边界。
随机游走
把以节点\(vi\)为起点的随机游走记作\(\mathcal{W}{vi}\)。随机游走是一个由随机变量\(\mathcal{W}{vi}^1,\mathcal{W}{vi}^2,\ldots,\mathcal{W}{vi}^k\)决定的随机过程，使得\(\mathcal{W}{v_i}^{k+1}\)是从节点\(v_k\)的相邻节点中随机选择的。随机游走在内容推荐和社团发现中被用于衡量相似度。它们也是在输入图的大小的次线性时间内计算局部社团结构信息的一类输出敏感算法的基础。
由于这种与局部结构的联系，于是使用一个随机游走流（stream）作为从网络中提取信息的基本工具。除了捕获社团信息，使用随机游走作为算法的基础也提供了两个不错的属性：首先，局部探索容易并行化。许多随机游走（在不同的线程、处理器或机器上）可以同时探索一个图的不同部分。其次，依靠从短随机游走获得的信息，可以适应图形结构的小变化而不需要全局重新计算。可以用次线性时间在变化的区域进行新的随机游走来迭代更新学习的模型。
连接：幂定律
之前用在线随机游走作为捕获图结构的雏形，现在需要一种合适的方法来捕获这些信息。如果连通图的度分布遵循幂定律（即无尺度），观测到在节点出现在短随机游走中的频率也将遵循幂定律分布。
自然语言中的词频遵循类似的分布，语言建模技术可以解释这种分布行为。本文核心贡献在于可以重新设计用于建模自然语言的技术来建模网络中的社团结构。
语言建模
语言建模的目的是估计特定词序列出现在语料库的可能性。给定一个词序列：
其中\(wi\in\mathcal{V}\)（词表），要在语料库上最大化\({\rm Pr} (w_n\mid w_0,w_1,\ldots,w{n-1})\)。最近在表征学习中的工作集中在使用概率神经网络来构建超过原始目标的语言模型一般表征。
本文中提出了一种通过短随机游走来探索图的语言模型。这些游走可以被认为是一种特殊语言的短句和短语；直接模拟是估计在随机游走中访问过观测点\(v_i\)之前所有节点的可能性：
目标是学习隐式表征，不只是节点共现的概率分布，因此我们引入映射函数\(\Phi:v\in V\mapsto\mathbb{R}^{|V|\times d}\)。映射\(\Phi\)表示与图中每个节点\(v\)相关的隐式社会表征。实际上用自由参数的矩阵\(|V|\times d\)来表示\(\Phi\)。于是问题变成了估计可能性：
然而随着游走距离的增长，计算这种条件概率变得不可行。于是在节点表征建模上产生了优化问题：
用这个目标函数构建捕获节点间在局部图结构中共享相似性的表征。具有相似邻居的顶点将获得相似的表征，可以在机器学习任务上进行一般化。
结合缩短的随机游走和语言模型，制定了一种满足所有期望属性的方法。该方法生成存在于连续向量空间中的低维社会网络表征。它的表征编码了社团成员的隐含形式，并且由于该方法输出有用的中间表征，它可以适应变化的网络拓扑。
方法
概述
在任何语言建模算法中，唯一需要的输入是语料库和词表\(\mathcal{V}\)。DeepWalk考虑一组在自身语料库中减短的随机游走，且图节点作为自己的词表（\(\mathcal{V} = V\)）。尽管在训练前已知\(V\)和随机游走节点的频率分布是有益的，但对于算法而言并不是必要的。
算法：DeepWalk
该算法由两个主要部分组成：随机游走生成器和更新过程。随机游走生成器在图\(G\)上均匀采样一个随机节点\(v_i\)作为随机游走\(\mathcal{W}_i\)的起点。每次游走都对上一个访问到的节点均匀随机采样一个邻节点，直到达到最大长度（\(t\)）。尽管将实验中的随机游走的长度设为定值，但对于相同长度的随机游走来说没有任何限制。这些游走可能会重新开始（回到起点），但是初步结果没有显示重新开始的任何优势。在实践中对每个起始节点指定了一些长度为\(t\)的随机游走\(\gamma\)。
算法1中的3～9行是方法的核心。外层循环指定循环次数\(\gamma\)，从每个顶点开始随机游走。每次迭代都会在数据中形成一个pass，并且对pass上的每个节点采样一个游走。在每次pass开始时先生成一个随机排序来遍历节点。虽不是严格要求的，但能加速随机梯度下降的收敛。
在内层循环迭代图上的所有节点。对每个节点\(vi\)生成一个随机游走\(|\mathcal{W}{v_i}|=t\)，然后使用mikolov2013efficient中提出的SkipGram算法按照上面的目标函数更新表征。
SkipGram
SkipGram是一种可以使句子中出现在窗口\(w\)中的单词之间共现率最大化的语言模型。它使用独立假设近似目标函数的条件概率：
算法2迭代窗口\(w\)（1～2行）内随机游走中的所有可能组合。映射每个顶点\(v_j\)到其当前表征向量\(\Phi(v_j)\in\mathbb{R}^d\)。
给定\(v_j\)的表征，要最大化游走中邻节点的概率（第3行），可以使用几种选择分类器来学习这种后验分布。例如使用逻辑回归建模前面的问题将导致大量的标签。这种模型需要跨集群的庞大的计算资源。为了避免这种必要性并加快训练时间，用Hierarchical Softmax来逼近概率分布。
Hierarchical Softmax
给定\(u_k\in V\)，计算第3行的\({\rm Pr}\big(u_k\mid \Phi(v_j)\big)\)是不可行的。计算配分函数（归一化因子）代价很高，所以使用Hierarchical Softmax分解条件概率。将节点分配到二叉树的叶子，把预测问题转化为最大化层次结构中特定路径的概率。
如果把到节点\(uk\)的路径看作树节点序列\((b_0,b_1,\ldots,b{\lceil\log|V|\rceil})\)，\((b0=root,b{\lceil\log|V|\rceil}=u_k)\)，那么：
现在\({\rm Pr}\big(b_l\mid\Phi(v_j)\big)\)可用分配给节点\(b_l\)的父节点二项分类器建模：
其中\(\Psi(b_l)\in\mathbb{R}^d\)是分配给\(b_l\)父节点的表征。这样就把计算\({\rm Pr}\big(u_k\mid\Phi(v_j)\big)\)的复杂度从\(O(|V|)\)降到了\(O(\log|V|)\)。
可以通过在随机游走中为高频节点分配较短的路径来加快训练过程。霍夫曼编码就用于减少树中高频元素的访问时间。
优化
模型参数集是\(\theta={\Phi,\Psi}\)，其中每个大小都是\(O(d|V|)\)。用随机梯度下降法（SGD）来优化这些参数（算法2第4行）。使用反向传播算法估计导数。SGD的学习率\(\alpha\)在训练开始时初始设置为\(2.5％\)，然后根据节点数线性下降。
并行性
社会网络随机游走的节点和语言中的词汇频率分布都遵循幂定律，导致低频节点距离较长，因此影响\(\Phi\)的更新在本质上是稀疏的。于是在多协作的情况下使用异步随机梯度下降（ASGD）。鉴于更新是稀疏的，且没有加访问模型共享参数的锁，ASGD将达到最佳收敛率。尽管实验是在一台机器上用多线程进行，但已经证明这种技术具有高度可扩展性，并可用于超大规模的机器学习。
算法变型
流
该方法的一个有趣的变型是流式（streaming）方法，可以在不了解整个图的情况下实现。在这种变型中图中的小游走直接传递到表征学习代码并且直接更新模型。还需要对学习过程进行一些修改。首先，使用衰减学习率可能不再可行，因为假设了对总语料库大小的认知。相反可以将学习率\(\alpha\)初始化为一个小常量。这将需要更长时间去学习，但在某些应用中可能更有价值。其次，不一定要再建立一个参数树。如果\(V\)的基数已知（或有界），可以为其最大值构建Hierarchical Softmax树。首次看到节点可以为其分配一个叶。如果能够先验估计节点频率，还可以使用霍夫曼编码来降低高频元素的访问时间。
非随机游走
一些图被作为与一系列元素交互的代理而创建（如页面导航）。当通过这种非随机游走的流建图时，可以使用此过程直接提供建模。以这种方式采样的图不仅捕获与网络结构相关的信息，还有遍历路径的频率。
这种变型还包括语言模型。句子可被看作在经过适当设计的语言网络进行有目的地游走，并且像SkipGram这样的语言模型是为捕获这种行为而设计的。
这种方法可以与流式方法结合，在不断进化的网络上无需构建全图而训练特征。用这种技术维护表征可以无需处理网络规模图而实现网络规模分类。
