DeepWalk: Online Learning of Social Representations-2

Language Modeling

语言建模的目标是估计语料库中出现特定单词序列的可能性。更正式的是，给定一个单词序列。

在训练语料库里最大化 DeepWalk: Online Learning of Social Representations-2

在这项工作中，我们提出了一种通用的语言模化方法，通过一系列的随机短游动来研究图形。这些行走可以用一种特殊的语言来思考短句和短语。直接的模拟是估计在目前的随机游走之后发现顶点vi的可能性。 DeepWalk: Online Learning of Social Representations-2

我们的目标是学习一个潜在的表示，而不仅仅是节点共现的概率分布，所以引入映射函数 DeepWalk: Online Learning of Social Representations-2

这个映射表示了在图中与每个顶点v相关的潜在的社会表示。这个问题就成了估计可能性 DeepWalk: Online Learning of Social Representations-2

然而，随着行走长度的增加，计算这个目标函数变得不可行。

它不是使用上下文来预测一个丢失的单词，而是使用一个单词来预测上下文。上下文由出现在给定单词的右侧和左侧的单词组成。它消除了对问题的排序约束。相反，该模型需要在不知道与给定单词的偏移量的情况下，最大限度地提高单词在上下文中出现的概率。在顶点表示建模方面，这就产生了优化问题 DeepWalk: Online Learning of Social Representations-2

该方法在连续向量空间中生成低维的社会网络的表示。它的表示形式对社区成员的潜在形式进行编码，并且由于该方法输出有用的中间表示形式，因此它能够适应不断变化的网络拓扑结构。

Method

与任何语言建模算法一样，惟一需要的输入是语料库和词汇表V。Deepwalk把一组短的截断的随机游走作为它的语料库，图顶点作为它自己的词汇表。

Algorithm: DeepWalk

该算法由两个主要部分组成;首先是随机游走生成器，然后是一个更新过程。

随机游动发生器取一个图G，并均匀采样一个随机顶点vi作为随机游走Wvi的根。一直均匀随机采样直到最大长度到达t。尽管实验中我们的随机游走设置长度固定，但没有限制

随机游走长度要相同。

算法核心如下：

DeepWalk: Online Learning of Social Representations-2

外层循环确定我们应该在每个顶点开始随机游走的次数。我们将每次迭代视为对数据进行一次“传递”，并在此传递期间对每个节点进行一次遍历。在每次传递的开始，我们生成一个随机顺序来遍历顶点。这不是严格要求的，但众所周知，它可以加快随机梯度下降的收敛速度。

DeepWalk: Online Learning of Social Representations-2

在内部循环中，我们遍历图中的所有顶点。对于每个顶点v i，我们生成一个随机游走

|Wvi| = t，然后用它来更新我们的表示。我们使用SkipGram算法根据Eq. 2中的目标函数更新这些表示。

SkipGram

SkipGram是一个语言模型最大化出现在窗口中的单词w在句子中的出现概率。算法2遍历窗口w出现的所有可能随机游走搭配。对于每一个，我们映射每个顶点Vj到他现在的表示向量 DeepWalk: Online Learning of Social Representations-2

考虑到vj的表示形式，我们想要最大化它的邻居在walk中的概率(第3行)。我们可以使用多种分类器来学习这种后验分布。例如，使用逻辑回归对前面的问题进行建模将导致大量的标签，这些标签等于|V |，单位可能是数百万或数十亿。这种模型需要大量的计算资源，这些资源可以跨整个计算机集群。为了加快训练时间，分级Softmax可以用来近似概率分布。

Hierarchical Softmax

考虑到 DeepWalk: Online Learning of Social Representations-2 所以在第三行计算是不可行的。计算配分函数(正态化因子)是很昂贵的。如果我们给二叉树的叶子分配顶点，预测问题就变成了最大化树中特定路径的概率。如果顶点uk的路径是由树节点序列标识的