我们来看下Bryan Perozzi的<DeepWalk: Online Learning of Social Representations>。
1.介绍
网络表示的稀疏性，即是它的强项，也是它的弱项。稀疏性允许设计一些很有效的分立算法，但使它很难泛化到统计学习（statistical learning）中。在网络机器学习应用中（比如：网络分类、内容推荐、异常检测、缺失环节预测missing link prediction等），必须能处理这种稀疏性。
本文引入了deep learning（非监督特征学习）技术来进行网络分析，DL已经在NLP上取得了成功。我们开发了一个算法（DeepWalk），它会通过建模一个关于短随机游走（short random walk）的流（stream），会学到一个关于图顶点(graph vertices)的社群表示（social representations）。社群表示是顶点的隐特征，它可以捕获相邻顶点间的相似度和社群关系。这些隐表示（latent representation）可以把社交关系使用相对少量的维度编码在连续特征空间中。DeepWalk可以看成是会将自然语言模型泛化来处理一个特殊的语言：它由一个随机生成的walk集合组成。这些自然语言模型被用于捕获人类语言中的语法和语义结构、以及逻辑类比。
图1
DeepWalk会将一个图作为输入，并生成一个隐表示作为它的输出。将我们的方法应用于Karate network上，结果如图1所示。图1a通过力导向（force-directed）的布局进行表示，图1b展示了我们使用2个隐维度的方法。除了显著的相似性外，我们注意到1b中线性可分的部分，对应于通过输入图1a的模块最大化（modularity maximization）的聚类（clusters）: 通过顶点颜色区分。
为了演示DeepWalk在真实世界场景中的潜力，我们在多标签网络分类问题上评估了它的效果。在关系分类（relational classification）问题上，特征向量间的连结（links）与传统的独立同分布（i.i.d）假设冲突。解决该问题的技术通常使用近似推断技术（approximate inference ）通过增加依赖信息来提升分类结果。我们通过增加图表示(representations of the graph)的标签独立性（label-independent）来解决。我们的表示（representation）质量不会因带label顶点（labeled vertices）的选择而受影响，因而它们可以在任务间共享。
DeepWalk比其它用于创建社交维度（social dimension）隐表示方法要好，尤其是当带label的节点（labeled nodes）很稀少时。我们的表示法的性能可能与最简单的分类器（LR）相当。我们的表示是可泛化的，可以结合任何分类方法（包含迭代型推断法）。DeepWalk可以完成上述所有，它是一个在线算法，可并行化。
本paper贡献：
- 引入深度学习作为一个工具来分析图，来构建健壮的表示，很适合于统计建模。DeepWalk会学到在短随机游走(short random walks)内表示的结构化规律。
- 我们对多个社交网络上使用我们的表示法，并在多标签分类上进行评估。我们发现可以极大提升存在标签稀疏性情况的分类效果，在Micro F1上可以提升5%-10%。在一些case中，即使只给了更少的60%的数据，DeepWalk的表示也可以胜出其它对手。
- 我们展示了我们的算法的可扩展性，使用一个并行实现去构建web-scale图（比如：Youtube）的表示。另外，我们描述了小的变种，来构建一个流版本（streaming version）。
本paper的其余部分如下安排。在第2-3节，描述了在数据网络中的分类问题，以及如何与我们的工作相结合。在第4节，我们描述了DeepWalk算法。第5､6节描述实验以及实验结果。等
2.问题定义
问题：对一个社交网络的成员进行分类，分成一或多个类(categories)。
更正式地表示：G=(V, E)，其中V是网络的成员，E是它们的边，\(E \subseteq (V \times V)\)。给定一个部分标记的社交网络\(G_L = (V,E,X,Y)\)，属性\(X \in R^{\mid V\mid \times S}\)， 其中S是每个属性向量的特征空间size，\(Y \in R^{\mid V \mid \times \mid \mathcal{Y} \mid}\)，其中\(\mathcal{Y}\)是labels的集合。
在传统的机器学习分类设定中，我们的目标是学习一个假设函数H，它会将元素X映射到标签集合\(\mathcal{Y}\)上。在我们的case中，我们可以利用关于样本依赖的显著信息，嵌入到G的结构中来完成更好的效果。
在学术上，这被称为是关系分类（relational classification)或者称为协作分类(collective classification）。关系分类的传统方法将该问题看成是在一个无向马尔可夫网络上做推断，接着使用迭代近似推断算法（比如：迭代型分类算法，Gibbs Sampling，或者 标记松弛法label relaxation）来计算给定网络结构下的标签后验分布。
我们提出了一个不同的方法来捕获网络拓朴信息。这种方法不再使用将标签空间进行混合作为特征空间的一部分，而是提出了一种无监督的方法，可以学到这样的特征：它能捕获与标签分布相独立的图结构。
结构化表示与标记任务间的分隔，可以避免重复错误，这常在迭代型方法中出现。另外，相同的表示可以被用于网络的多分类问题。
我们的目标是，学习\(X_E \in R^{\mid V \mid \times d}\)，其中，d是隐维度（latent dimensions）是最小数目。这些低维度表示是distributed式表示的; 这意味着每个社交现象（social phenomena）可以通过维度的某个子集进行表示，每个维度只会对通该空间表示的社交概率的某个子集做出贡献。
使用这些结构化特征，我们可以增大属性空间来帮助分类决策。这些特征是通用的，可以被用于任何分类算法（包括迭代型方法）。然而，我们相信，这些特征的最大作用是，它们很容易与简单的机器学习算法集成。它们可以很适合地在现实网络中扩展，在第6节会介绍。
3.学习社交表示
我们使用以下的特征来探索社交表示学习（learning social representations）：
- 适应性（Adaptability）：真实社交网络是不断演进的；新的社交关系不需要再次重复所有学习过程。
- 社群意识（Community aware）：隐维度间的距离可以作为评估网络成员的社交相似性的一个metric。这允许泛化到同质的网络中。
- 低维（Low dimensional）：当标记数据很少时，低维模型泛化更好，加速收敛和推断。
- 连续（Continuous）：我们需要隐表示来建模在连续空间中的部分社群成员关系（community membership）。除了提供一个关于社群关系的细微视图外，连续表示法具有在社群间的平滑决策边界，这可以允许更健壮的分类。
我们的方法满足这些需求，从一个短随机游走流中，使用语言建模上的优化技术来为顶点学到表示。这里，我们会复习下随机游走和语言建模，并描述两者如何结合来满足我们的需要。
3.1 随机游走
一个根顶点\(v_i\)的随机游走的定义为：\(W_{v_i}\)。它是一个随机过程，具有随机变量：\(W_{v_i}^1, W_{v_i}^2, ..., W_{v_i}^k\)，\(W_{v_i}^{k+1}\)是从顶点\(v_k\)的邻节点上随机选中的顶点。随机游走已经被用于在内容推荐和社群发现领域的多个问题上作为一个相似度衡量方法。他们也是输出敏感算法（output sensitive algorithms）大类的基础，使用它们来及时计算局部社群结构信息，与输入图的size成次线性关系（sublinear）。
这种局部结构的连接特性，启发我们来使用一个短随机游走作为我们的基础工具来从一个网络中抽取信息。除了捕获社群信息外，在我们的算法中使用随机游走作为基础，能给我们带来其它两个特性。
- 1.局部探索（local exploration）很容易并行化。多个随机游走者（random walkers）以不同线程、进程、机器可以并行探索同一个graph下的不同部分。
- 2.依靠从短随机游走上获取信息，可以使它更能适应在图结构上的小变动，无需进行全局重新计算。我们可以迭代式地更新学到的模型，从变动区域上使用新的随机游走，它对整个graph是在时间上是次线性的。
3.2 连接：二八法则（power law）
已经选择在线随机游走作为我们的基础来捕获图结构，我们现在需要一个更适合的方法来捕获这种信息。如果一个连接图的度分布（degree distribution）遵循一个power law（scale-free），我们会观察到，出现在短随机游走上的哪个顶点的频次也是遵循power-law分布的。
图2
在自然语言中，词频会遵循一个相似的分布，其中，语言建模领域的技术可以对该分布行为作出解释。为了强调该相似性，如图2所示，我们展示了两个不同的power-law分布。第1个图来自在一个scale-free的graph上进行一系列短随机游走，第2个图来自关于英文wikipedia的10w篇文章的文本。
我们的工作的一个核心贡献是，用于建模自然语言的技术（其中，符号频次遵循power-low分布）可以被用于建模在网络中的社群结构。该节剩余部分将讨论语言建模，并将它迁移到我们的case中来学习顶点表示。
3.3 语言建模
语言建模的目标是，在语料中出现的一个指定词序列的似然。更正式地，给定一个词序列：
\[W_1^n = (w_0, w_1, ..., w_n)\]其中，\(w_i \in V\)（V是词汇表），我们想最大化在所有训练语料上的\(Pr(w_n \mid w_0, w_1, ..., w_{n-1})\)。
在表征学习上的最近工作，主要使用概率神经网络来构建词的通用表示，可以扩展到语言建模范围之外。
在本paper中，我们使用一个语言建模的泛化版本、结合短随机游走的一个流(stream)来探索图。这些游走可以被认为是在一个特殊语言中的短句、短段落。直接类比是，给定在随机游走中所有访问过的前节点，估计观察顶点\(v_i\)的似然。
\[Pr(v_i | (v_1, v_2, ..., v_{i-1}))\]我们的目标是学习一个隐表示，它不仅仅是节点共现的一个概率分布，而且我们引入了一个映射函数 \(\Pi: v \in V \rightarrow R^{\mid V \mid} \times d}\)。该映射函数\(\Phi\)表示与在图中每个顶点v相关的隐社交表示。（实际上，我们通过一个\(\mid V \mid \times d\)的自由参数矩阵来表示\(\Phi\)，它可以在之后作为我们的\(X_E\)服务）。接着该问题是，估计以下似然：
\(Pr(v_i | (\Phi(v_1), \Phi(v_2), ..., \Phi(v_{i-1})))\) …(1)
然而，随机游走长度的增长，计算该目标函数会变得不可行。
在自然语言中的最近实验是，开始转变预测问题。首先，它不同使用上下文来预测一个缺失的词（word），而是使用一个词来预测它的上下文。第二，上下文由给定词的右侧和左侧组成。最后，它在该问题上会移除顺序限制。作为替代，该模型需要最大化出现在该上下文中的任何词的概率，无需知道与给定词间的偏移。
用顶点表示建模的优化问题，如下：
\(minimize_{\Phi} - log Pr({v_{i-w}, ..., v_{i-1}, v_{i+1}, ..., v_{i+w}} | \Phi(v_i))\) …(2)
我们发现这些条件放宽，特别适合于社交表征学习。首先，顺序无关性假设可以更好捕获由随机游走提供的“邻近度(nearness)”。另外，该relaxation通过一次只为一个顶点构建小模型对于加速训练时间相当有用。
对等式(2)的优化问题进行求解来构建表示，可以捕获在顶点间的局部图结构的共享相似度。具有相同邻节点的顶点可以获取相似的表征（encoding cocitation similarity），允许在机器学习任务上进行泛化。
通过组合截短的随机游走和自然语言建模，我们会对该方法公式化，它可以满足所有我们期待的特性。该方法可以生成社交网络的表征，具有低维、连续空间的特性。它的表示会对社群的隐形式进行编码，因为该方法会输出有用的中间表征，可以用来更改网络拓朴。
4.方法
在本节中，我们讨论算法的主要构成。
4.1 总览
在任何语言建模算法中，只需要一个语料和词汇表V。DeepWalk会考虑短截断的随机游走的一个集合作为它的语料，图顶点作为它的词汇表（\(v=V\)）。其中，它有利于知道在训练之前的随机游走上顶点的词频表V和频次分布。
4.2 算法：DeepWalk
该算法包含了两个主要部分：
- 1.随机游走生成器
- 2.一个更新过程
随机游走生成器会使用一个图G，并且均匀地抽样出一个随机顶点\(v_i\)作为随机游走\(W_{v_i}\)的根节点（root）。一个游走会均匀从最后访问的顶点的邻节点进行抽样，直到到达最大长度(t)。在我们的实验中，随机游走的长度设置是固定的，但是对于随机游走来说没有限制一定要用相同长度。这些游走会重启(restart)（例如：一个传送点（teleport）的概率会返回到它的root），但我们的初步结构不会展示使用重启(restarts)的任何优点。实际上，我们的实现指定了在每个顶点上进行随机游走的数目(\(\gamma\))和长度(t)。
算法一
在算法1中的3-9展示了我们算法的核心。外层的循环指定了次数，\(\gamma\)，即我们在每个顶点上启动随机游走的数目。我们认为每个迭代会生成一个对数据的”通路（pass）”，并在该pass期间为每个节点抽样一个walk。在每个pass的开头，我们生成了一个随机顺序来遍历这些顶点。这不是必需的，但可以加速随机梯度下降（SGD）的收敛。
在内层循环中，我们会迭代图的所有顶点。对于每个顶点\(v_i\)，我们会生成一个随机游走 \(\mid W_{v_i} \mid = t\)，接着使用它来更新我们的表征represntations（第7行）。我们使用SkipGram算法来更新这些表征，以适应在等式2中的目标函数。
4.2.1 SkipGram
SkipGram是一个语言模型，在一个句子中，它会最大化在同一窗口w中词之间的共现率。
图3: 补充
算法2会迭代在窗口w内出现的随机游走中的所有可能排列（collocations）（第1-2行）。for-each操作中，我们会将每个顶点\(v_j\)映射到它的当前表征向量\(\Phi(v_j) \in R^d\)中（见图3b）。给定\(v_j\)的表示，我们可以最大化在该walk中的邻节点的概率（第3行）。我们可以有多种分类器选择来学到在walk中这样的后验分布。例如，使用LR建模前面的问题，可以生成一个海量的标签（上百万或数十亿），它等于词汇表数\(\mid V \mid\)。这样的模型需要大量计算资源，可能会占用整个计算集群。为了加速训练时间，可以使用Hierarchical Softmax来近似概率分布。
算法2
4.2.2 Hierarchical Softmax
给定\(u_k \in V\)，计算第3行中\(Pr(v_k \mid \Phi(v_j))\)是不可行的。计算分区函数（正归化因子）很昂贵。如果我们将顶点设计成一棵二叉树的叶子节点，预测问题就转化成了最大化在树中一条指定路径上的概率（见图3c）。如果到顶点\(u_k\)的路径通过一个树节点序列\((b_0, b_1, ..., b_{[log \mid V \mid]})\)表示，其中：\(b_0 =root, b_{[log\mid V \mid]}=u_k\)，那么：
\[Pr(u_k | \Phi(v_j)) = \prod_{i=1}^{log|V|} Pr(b_l | \Phi(v_j))\]现在，\(Pr(b_l \mid \Phi(v_j))\)可以通过一个二分类器进行建模，该值被分配给节点\(b_l\)的父节点。这可以减少计算\(Pr(u_k \mid \Phi(v_j))\)的计算复杂度：从\(O(\mid V \mid)\)到\(O(log\mid V \mid)\)。
我们可以进一步加速训练过程，通过分配更短的路径给在随机游走中的频繁顶点。Huffman编码常用于减小在树中频繁顶点的访问次数。
4.2.3 最优化
模型参数集是\(\{ \Phi, T\}\)，其中每个的size都是\(O(d\mid V \mid)\)。随机梯度下降(SGD)被用于最优化这些参数（算法2第4行）。导数的估计使用BP算法。SGD的learning rate \(\alpha\)在训练开始处初始化设置为2.5%，接着随着见过的顶点数进行线性递减。
4.3 并行化(Parallelizability)
如图2所示，在社交网络上的随机游走中，顶点的频率分布与语言中的字分布遵循power law。这会产生一个关于不频繁顶点的长尾，因此，对\(\Phi\)有影响的更新在本质上很稀疏。这允许我们使用并行版本的ASGD(asynchronous version of stochastic gradient descent)，在多个worker上。假定：我们的更新是稀疏的，我们不需要一个锁来访问模型的共享参数，那么ASGD将会达到一个收敛的最优rate。其中我们在单机上使用多线程进行实验，它可以演示这种技术是高度可扩展的，可以用于大规模机器学习上。图4展示了并行的DeepWalk。它展示了处理BLOGCATELOG和Flickr网络的加速与我们增加workers数是一致的（图4a）。也展示了相对于顺序版本的DeepWalk，预测效果并没有损失（图4b）。
图4
4.4 算法变种
我们提出的方法还有一些变种。可能是你感兴趣的。
4.4.1 Streaming
其中一个有意思的变种是streaming方法，它没需知道整个graph就可以实现。在该变种中，从一个图出发的小游走，直接传到表示学习编码上，模型是直接更新的。该学习过程的一些修改是必须的。首先，使用一个衰减的learning rate不再可能。相反地，我们会初始化learning rate \(\alpha\)，我们不必构建一个参数树。如果V的基数是已经的（可以限定），我们可以构建Hierachical Softmax tree来最大化值。当顶点被首先看到时，它们会被被分配给余下叶子之一。如果我们能估计顶点频率的一个先验，我们也可以仍使用Huffman编码来减小频繁节点的访问次数。
4.4.2 非随机游走
一些图是作为一系列元素行为的一个副产品被创建的。（例如：用户在一个网站上的导航）。当一个图通过这样的非随机游走方式创起家时，我们可以使用该过程来直接feed该建模阶段。以这种方式抽样的图不仅能捕获与网络结构相关的信息，也能捕获在该路径进行反向的频率。
我们认为，该变种也包括语言建模问题。句子可以看成是通过一个合理设计的语言网络上的一些特定游走，像SkipGram的语言模型可以被设计用来捕获这种行为。
该方法可以结合streaming变种来在连续演化网络上训练特征，无需显式构建整个网络。使用该技术维护表示，可以允许web-scale分类，无需处理一个web-scale规模的graph。
5.实验设计
略.
YouTube是一个社交网络，用户共享流行的视频。这里的labels表示viewers的群组，它们喜欢相同的视频类目（比如：动作 和 摔跤）
6.实验
6.1.3 YouTube
详见paper.