【Graph Embedding】DeepWalk
关于Graph Embedding系列的论文翻译解读文章：
参考资料
paper: http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
code: https://github.com/phanein/deepwalk
1. 介绍
DeepWalk将图作为输入，将生成的潜在表示(embedding 向量)作为输出。应用DeepWalk的结果深入研究空手道网络的方法如图1。该图的布局表示（1a）。图1b显示了用DeepWalk后在两个潜在维度的输出。可以看到(1b)的线性可分部分对应原图中发现的集群(以顶点颜色显示)。另外文章在多标签预测上评估了其性能。
在创造社交维度方面，DeepWalk的表现优于其他潜在的表现方法[39，41]，尤其是当标记的节点很少。 使用非常简单的线性分类器的表现非常出色（如LR）。文章中提到主要的贡献如下：
我们引入深度学习作为分析图形的工具，以构建适合于统计建模的健壮表示。DeepWalk学习短随机游走中出现的结构规律。
我们广泛地评估了我们在几个社交网络上的多标签分类任务的表现。我们发现，在标签稀疏性存在的情况下，分类性能显著提高，Micro-F1指标提高5%-10%，我们考虑的最稀疏的问题。在某些情况下，即使训练数据减少60%，DeepWalk的表现也能超越竞争对手。
我们通过构建web级图的表示来演示我们的算法的可伸缩性和并行实现。
2. 问题定义
考虑将社交网络成员划分为一个或多个类别的分类问题。定义$G=(V,E)$，$V$是网络节点的集合，$E$是节点之间的边的集合。$E \subseteq (V \times V)$。给定一个有标签的社交网络$G_L=(V,E,X,Y)$,它有属性$X \in \Bbb R^{|V| \times S}$，其中$S$是每个属性的特征空间大小，$Y \in \Bbb R^{|V| \times \cal Y}$是标签的集合。
在传统的机器学习分类任务中，需要学习一个假设$H$（根据特征训练一个分类器），使它可以把$X$映射到$Y$集合中。现在，可以利用图$G$结构的embedding获得有意义的信息，进而获得更好的表现(其实就是根据图结构对每个顶点得到一个embedding向量，后续以此作为特征训练一个分类器)。
在文献中，这被称为关系分类。传统的方法把这个问题看作无向马尔可夫网络的推理问题，并且在给定网络结构的情况下，运用迭代近似推理算法计算标签的后验分布。
DeepWalk提出一种不同的方法去获取网络的拓扑信息。而不是混合标签空间作为特征空间的一部分，我们提出一种无监督的方法可以得到具有捕捉网络结构能力的特征，并且它们与标签的分布是相关独立的。
目标是学习$X_E \in \Bbb R^{|V| \times d}$，这里的$d$是潜在维数。使用这些结构化的属性，我们就可以扩充特征空间，帮助进行分类决策。这些特征是通用的，可以用作任何分类算法（包括迭代算法）。因此，这些特征的最大好处就是易与简单的机器学习算法整合起来。
3. 学习社交表示
文章试图学习具有以下特征的社会表征:
- 适应性 — 真实的社交网络是不断进化的;新的社会关系不应该要求重新学习过程。
- 社区感知 — 潜在维度之间的距离应该代表一个度量标准，用于评估网络中相应成员之间的社会相似性。这使得具有同质性的网络可以泛化。
- 低维 — 当标记数据不足时，低维模型能更好地推广，并加速收敛和推理。
- 连续 — 我们需要潜在的表现来在连续空间中模拟部分社区成员。除了提供社区成员的细致视图外，一个连续的表示在社区之间有平滑的决策边界，这允许更健壮的分类。
根据短随机游走学习到顶点的表示，使用最初为语言建模设计的优化技术来满足这些要求。在这里，需要回顾下随机游走和语言建模的基础知识。
3.1 随机游走
定义随机游走的根节点$v_i$为$\cal W_{v_i}$。它是一个由$\cal W^1_{v_i},\cal W^2_{v_i},…,\cal W^k_{v_i}$组成的随机过程，$\cal W^{k+1}_{v_i}$是被随机选出的节点$v_k$的邻居。随机游走作为一种相似度度量的方式应用于内容推荐和社区发现。正是这种与本地结构的连接促使我们使用短随机游动流作为从网络中提取信息的基本工具。使用随机游走不仅可以获取社区信息，还有两个理想特性。首先，局部探索很容易并行化。可以同时探索同一图的不同部分。其次，依靠短随机游走获得的信息，可以适应图结构的微小变化，而不需要全局重新计算。我们可以用新的随机游走来迭代地更新所学习的模型，这对比更新整个图来说是次线性的。
3.2 连接：幂律
在选择在线随机游走作为我们主要捕捉图结构的方法之后，我们现在需要一个合适的方法去捕捉这些信息。如果一个连接图的度分布服从幂律定律，我们观测得到节点在短随机游走出现的频率也会服从幂律分布。过去用于自然语言建模的方法（符号频率服从幂律分布）也可以用于网络的社区结构建模。
3.3 语言建模
语言建模的目标是估计一串特殊的词出现在全集的可能性。正式地说，给定一串词$W^n_1=(w_0,w_1,…,w_n)$，其中$w_i \in \cal V$($\cal V$是词汇表)，我们要在所有训练的集合中求出$Pr(w_n|w_0,w_1,…,w_{n-1})$的最大值（条件概率）。
在DeepWalk中，通过短随机游走探索图，这展示了一种语言建模的一般化。这种直接的类比是在给定随机游走之前访问过的节点情况下，估计下一次要访问节点$v_i$的可能性。
目标是学习顶点的一种潜在表示，而不是一个节点再现的概率分布，引入一个映射函数$\Phi:v \in V \to \Bbb R^{|V| \times d}$。这个映射函数$\Phi$表示图中每个节点$V$之间的潜在表示。然后这个问题就变成估计以下可能性：
然而，随着游走的距离增大，计算这个目标函数变得不是那么容易。
最近的一些工作[27,28]提出，可以不用上下文去预测缺失的单词，而是用单词去预测它的上下文。其次，这里的上下文同时包括该单词的右边的词汇和左边的词汇。最后，它去除了这个问题的顺序约束。取而代之的是，这个模型需要最大化上下文出现的各个单词的概率，而无需知道其偏离给定单词的知识。在节点表示建模方面，这产生了如下优化问题：
这在社交表示学习上尤其可取。首先，顺序独立假设很好地获取了随机游走所提供的“接近”。另外，可以在某个时间给出一个节点的情况下，通过构建更小的模型加速训练时间。
通过结合缩短的随机游走和神经语言模型。可以生成社交网络的低维表示，并且在向量空间连续。它表示了社区成员的潜在形式，并且由于这种方法输出有用的中间表示，它可以适应变化的网络拓扑。
4. 方法
4.1 概况
在其他所有语言建模算法中，需要的输入仅为一个全集和一个词汇表$\cal V$。DeepWalk把随机游走作为自己的全集，图的节点作为自己的词汇表$(\cal V$ = $V)$。最好在训练之前知道随机游走的$V$和节点的频率分布，不过这不是必须要的。
4.2 算法： DeepWalk
算法主要包括两个主要成分；第一是随机游走生成器，第二是更新程序。随机游走生成器把图$G$作为输入，随机挑选一个节点$v_i$作为随机游走$\cal W_{v_i}$的根节点。每一步需要从上一个节点的邻居节点中随机挑选一个作为当前节点，直到达到最大长度$t$。在实验中我们把这个长度固定，但是并没有规定$t$必须取某个相同的值。这些游走可能重新回到起点，但是我们之前的结果并没有显示重新开始的任何优势。在实践过程中，我们在每个节点进行了$\gamma$次长度为$t$的随机游走。
算法1中的3-9行显示了我们方法的核心。外循环指定次数$\gamma$，我们应该在哪个点开始随机游走。 我们认为每次迭代都是对数据进行一次“传递”，并在此传递过程中对每个节点进行一次抽样。在每次遍历的开始，我们都会生成一个随机的遍历顶点的顺序。这不是严格要求，但对随机梯度下降可以加快收敛。
在内部循环中，遍历图上的所有顶点。对于每个顶点$v_i$，我们生成一个随机游走$|\cal W_{v_i}| = t$，然后用它来更新表示。我们根据目标函数，使用Skip-Gram算法进行表示的更新。
4.2.1 SkipGram
SkipGram是一种语言模型，它使出现在窗口$w$中的单词在句子中的共现概率最大化。它使用如下独立假设近似方程3中的条件概率
算法2 遍历出现在窗口$w$中的所有可能的随机游走（第1-2行）。对于每一个顶点，将每个顶点$v_j$映射到其当前表示向量$\Phi(v_j) \in \Bbb R^d$（见图3b）。给定$v_j$的表示，我们想要最大化它的邻居在这条线上的概率(第3行)。例如用分类器LR对问题进行建模，将产生大量的标签(即$|V|$)，其数量可能是数百万甚至数十亿。这些模型需要大量的计算资源，这些资源可以跨越整个计算机集群[4]。为了避免这种必要性，加快训练时间，我们使用层次结构来近似概率分布。
4.2.2 分层SoftMax
给定$u_k \in V$,计算$Pr(u_k|\Phi(v_j))$不是可取的。计算归一化因子代价很高。如果把顶点分配给二叉树的叶节点，将预测问题转化为最大化层次结构中特定路径的概率(参见图3c)。如果到顶点$u_k$的路径由一系列树节点$(b_0, b_1, …, b_{[log|V|]})$，$(b_0=root, b_{[log|V|]}=u_k)$，那么：
现在，$Pr(b_l | \Phi(v_j))$可由分配给节点$b_l$父节点的二进制分类器建模，如式6所示，
其中$\Psi(b_l) \in \Bbb R^d$是分配给树节点$b_l$的父节点的表示形式。这减少了计算$Pr(u_k | \Phi(v_j)) $的复杂性，复杂度从$O(|V|)$降低到$O(log|V|)$。
通过为随机游走中频繁出现的顶点分配较短的路径，可以进一步加快训练过程。人工编码是为了减少树中频繁元素的访问时间。
4.2.3 最优化
这个模型的参数集合是$\theta = \lbrace \Phi,T \rbrace$，其大小都为$O(d|V|)$。随机梯度下降被用来优化这些参数，利用反向传播算法对导数进行估计。学习率$\alpha$初始化为2.5%，然后随着目前发现的节点的增加线性减小。
4.3 并行性
如图2，社交网络中随机游走的顶点的频率分布和语言中的单词都遵循幂律分布。这就导致了一条罕见顶点的长尾，因此，影响$\Phi$的更新在本质上是稀疏的。在有多个worker的情况下允许使用异步版本的随机梯度下降（ASGD）。由于更新是稀疏的，因此ASGD将实现最佳收敛速度[36]。当我们在一台使用多线程的机器上运行实验时，已证明该技术具有高度的可扩展性，并且可以用于超大规模的机器学习[9]。图4展示了并行化DeepWalk的效果。它表明，随着我们将worker数量增加到8个，处理BlogCatalog和Flickr网络的速度是一致的（图4a）。它还表明，相对于串行运行DeepWalk而言，不会降低预测性能（图4b）。
4.4 算法变体
4.4.1 Streaming
这种方法的一个有趣的变体是流式处理处理，哪些可以在不了解整个图的情况下实现。在这种变体中，图的小遍历被直接传递给表示学习代码，并直接更新模型。 对学习过程进行一些修改也是必要的。 首先，使用衰减的学习率可能不再是可取的，因为它假定了总语料库大小的知识。反而，我们可以将学习率$\alpha$初始化为一个小的常数值。这将需要更长的学习时间，但在某些应用程序中值得。其次，我们不一定要建立任何参数树。 如果$V$的基数已知（或可以有界），我们可以为该最大值构建分层 Softmax树。 可以将顶点分配给其余叶子之一。当他们第一次见到。 如果我们有能力预先估计顶点频率，我们还可以使用人工编码(Huffman coding)来减少频繁的元素访问时间。
4.4.2 非随机游走
有些图是并非是随机游走的(例如，用户在网站上的页面导航)。当这样一个非随机游走流创建一个图时，我们可以使用这个过程来直接支持建模阶段。以这种方式采样的图不仅可以捕获与网络结构相关的信息，还可以捕获路径遍历的频率。
在我们看来，这种变体还包括语言建模。句子可以被看作是经过适当设计的语言网络的有目的的游走，而像Skip-Gram这样的语言模型就是为了捕捉这种行为而设计的。
【Graph Embedding】DeepWalk