论文信息

发表:
2014年的KDD会议上
作者：
Bryan Perozzi, Stony Brook University, Stony Brook, NY, USA
Rami Al-Rfou, Stony Brook University, Stony Brook, NY, USA
Steven Skiena, Stony Brook University, Stony Brook, NY, USA
摘要：
  我们提出DeepWalk，一种用于学习网络中顶点的潜在表示的新方法。这些潜在表示将社会关系编码到连续的向量空间中，编码到向量空间后的社会关系，很容易应用到统计模型中。 DeepWalk将语言建模和无监督特征学习（或深度学习）的最新进展，从单词序列推广到图中。
  DeepWalk将随机游走得到的节点序列当做句子，从截断的随机游走序列中得到网络的局部信息，再通过局部信息来学习节点的潜在表示。为了展示DeepWalk得到的节点的潜在表示，我们对几个社交网络（BlogCatalog，Flickr和YouTube）进行了多标签分类任务。我们的研究结果显示，DeepWalk能够对网络进行全局的观察，特别是在存在缺失信息的情况下。当已标记数据很少时，DeepWalk的表示得到的F1分数比对比方法高出10％。在一些实验中，当训练数据少于60%时，DeepWalk的表现能够胜过所有对比算法。
  DeepWalk也是可扩展的。DeepWalk是可以建立有用的增量结果的在线学习算法，并且是平行的。这些特性使其适用于广泛的实际应用，如网络分类和异常检测。
代码：
http://bit.ly/deepwalk

背景

  使用机器学习的算法解决问题需要有大量的信息，但是现实世界中的网络中的信息往往比较少，这就导致机器学习算法不能在网络中广泛使用。为了将机器学习广泛应用到网络中，必须要先对信息比较少的网络进行处理，如稀疏性网络。

问题定义

  社交网络中节点之间的连接比较稀疏，是比较典型的信息比较少的网络，文章通过对社交网络中的节点进行分类这一问题，说明了问题定义。

1. 图的表示：令G =(V,E)，其中V表示网络的节点，E是网络中的连接，E⊆ (V×V)。
   G_L=(V,E,X,Y)是部分标记的社交网络。X是各个节点的属性空间，X∈R^|V|×S，其中S是每个节点的属性向量的特征空间的大小；Y∈R^|V|×|Y|，Y是标签的集合。
2. 传统机器学习分类问题中，目标是学习一个假设H，能够将X中的向量映射到Y中的标签（不考虑图的结构，根据每个节点的属性向量，将节点分类）。因为网络中的信息比较少，所以该方法不适用与网络。
3. 在本文中，采用的方法是：先得到图的结构，然后利用图的结构实现分类，这种分类方式被称为关系分类,也叫做集体分类。
4. 本文提出了新的、无监督的、独立于标签分布的（捕获结构信息时不考虑标签）、捕获图结构信息的算法。算法目标是学习图的结构特征X_E∈R^{| V |×d}，其中d是节点的潜在表示（向量形式）的维数。图结构特征可以用于任何分类算法。

  将X_E∈R^{| V |×d}与简单的机器学习算法集成，还可以用来实现很多其他问题。

算法思路

输入输出：

  DeepWalk将一个图作为输入，并产生一个潜在表示（将图中的每个节点表示为一个向量）作为输出。图1是将算法应用到空手道网络的结果： 图1 DeepWalk在空手道网络上的应用，顶点颜色表示输入的图的聚类。

图1(a)是空手道网络的力导向图，图1(b)是算法在二维空间的输出。

对算法的要求：

• 适应性：社交网络是不断变化的，当网络发生变化时，不能对整个网络重新进行计算。
• 社区意识：节点在潜在表示的维度空间中的距离，应该表示网络中对应的成员的相似度，以此保证网络的同质性。
• 低维：当被标记的成员很少时，低维的模型一般表现的更好，并且收敛和推理速度更快。
• 连续性：需要通过图的潜在表示来对连续空间中的部分社区成员进行建模。除了提供对社区成员资格的细微视图之外，连续表示还可以使社区之间的决策界限平滑，从而实现更强大的分类。

  为了满足这些要求，算法利用最初为了语言建模设计的优化技术(word2vec)，从短的随机游走序列中学习节点的表示，

随机游走

过程：
  将从顶点v_i开始的随机游走序列表示为W_vi。W_vi^j表示序列W_vi中的第j个点。其中，W_vi¹为v_i，W_vi^k+1是从W_vi^k的邻居中随机选择的节点。

特点：
  随机游走得到的序列中包含了网络的局部结构信息。（文章中是通过随机游走的应用说明的）
  当图中节点的度遵循幂律分布（y=cx^-r，y是度数为r的节点的出现的频率；直观上说，就是度数大的节点比较少，度数小的节点比较多）时，短随机游走中顶点出现的频率也将遵循幂律分布。
  因为自然语言中单词出现的频率遵循类似的分布，所以用于建模自然语言分布的技术，可以用于对随机游走得到的序列进行建模。

图2 短随机游走和自然语言中的幂律分布

优点：
1.容易实现并行性。几个随机游走者（不同的线程，进程或机器）可以同时探索同一网络的不同部分。
2.适应性。当图变化后，不需要全局重新计算，可以迭代地更新学习模型。

语言建模

1. 语言建模的目标是估计出现在语料库中的特定序列的可能性。即，给定Wⁿ =（w₀，w₁，...，w_n）的序列，其中w_i∈V（V是词汇表），我们想最大化Pr（w_n | w₀，w₁， ...，w_n-1）。在最近的工作中，语言建模扩展到使用概率神经网络来构建词语的一般表示。
   随机游走得到的序列可以被认为是一种特殊语言的短句，类比语言建模可以得到：在随机游走中给定迄今为止访问的所有先前顶点的情况下，下一个顶点是vi的可能性可以表示为：
              Pr(v_i| (v₁,v₂,··· ,v_i-1))  (1)
2. 为了得到节点的潜在表示，引入映射函数Φ：v ∈ V → R^|V|×d，|V|×d的矩阵Φ表示图中每个顶点的在d维空间中的潜在表示。这样公式(1)可以表示为：
             Pr(v_i|Φ(v₁),Φ(v₂),··· ,Φ(v_i-1))  (2)
   然而，随着步数的增长，不可能进行计算。
3. 对语言建模进行下面的relaxation：
   1)不是通过上下文预测单词，而是使用单词来预测上下文。
   2)上下文由给定的单词左右两边的单词组成（原本只考虑左边的）。
   3)不考虑句子中上下文出现的顺序，最大化出现在上下文中的所有单词的概率。
   对于顶点表示建模，就产生了下面的优化问题：
          minimize −logPr({v_i−w,··· ,v_i+w}\v_i | Φ(v_i))  (3)

  通过解决优化问题(3)就可以得到图中节点的向量表示形式。具有相同的上下文的节点的表示相似（使用LINE中的定义，即算法使用的是二阶相似度）。

算法实现

DeepWalk算法框架

DeepWalk

  该算法由两个主要组件组成：一个随机游走生成器和一个更新程序。 算法1 DeepWalk

  算法1中的3-9行显示了算法的核心。将每次迭代看作是对数据进行“传递”，迭代次数由输入数据 γ 指定。每次循环中，先生成一个随机排序来遍历顶点；再得到从每个顶点开始的长度为 t 的随机游走W_vi；最后，根据W_vi，利用SkipGram算法实现表示更新。

SkipGram：
  SkipGram是一个语言模型，用于最大化句子中出现在窗口w内的单词之间的共现概率。它使用独立性假设，将等式3中的条件概率近似为：

(4) 算法2 SkipGram

  对随机游走序列中的每个顶点，先把它映射到它的当前表示向量Φ(v_j)（参见图3(b)）；然后通过随机梯度下降算法，最大化出现在上下文中的所有单词的概率，以此更新向量表示。

Hierarchical Softmax：
  给定u_k∈V，直接计算第3行的Pr(u_k|Φ(v_j))是不可行的，我们将使用Hierarchical Softmax来分解条件概率。
  我们将网络中的顶点分配为二叉树的叶子节点，将问题转化为最大化层级中特定路径的概率（参见图3(c)）。如果顶点u_k的路径由一系列树节点(b₀，b₁，...，b_{[log |V|]})来标识，其中，b₀=v_j，b_{[log |V|]}= u_k，那么

(5) Pr(b_l|Φ(v_j))可以通过对b_l的父节点建模一个二元分类器实现，计算公式为： (6) 其中，Ψ(b_l) ∈R^d是b_l的父节点的向量表示。
  可以通过给随机游走中的频繁顶点分配更短的路径来加速训练过程。使用Huffman编码的二叉树可以减少树中频繁元素的访问时间。

优化：
  模型参数集是θ= {Φ,Ψ}，Φ和Ψ的大小是O(d | V |)。使用随机梯度下降(SGD)来优化这些参数(算法2，第4行)。导数使用反向传播算法估算。SGD的学习率α在训练开始时初始设定为2.5％，然后随着到目前为止所看到的顶点数目线性减少。

并行性

图4 并行对DeepWalk的影响

  因为社交网络中的顶点的频率分布和语言中的词都遵循幂律，出现频率低的顶点很多。因此，Φ的更新本质上是稀疏的，因此，参数更新过程中发生冲突的概率很低。且即使出现了冲突，算法还是有效的。这使我们能够在多任务的情况下使用异步随机梯度下降（ASGD）进行优化。
  图4显示了并行对DeepWalk的影响。图4(a)当多个任务同时进行时，算法的速度变快。图4(b)表明，并行运行下，DeepWalk的性能没有受到影响。

算法变体

Streaming

  Streaming可以在不知道整个图形的情况下实现。在这个变体中，图形中的游走直接传递给表示学习代码，并且模型被直接更新。算法中的其他调整包括：

1. 学习率α初始化为一个小的常数值。
2. 如果节点V的数目是已知的(或者可以是有界的)，我们可以为该最大值构建分层Softmax树。当某个顶点第一次被观察到，可以被分配到叶子节点上。如果我们有先验估计顶点频率的能力，还可以使用Huffman编码来减少频繁的节点访问时间。如果不知道节点的数目，则不能构建参数数。

非随机游走

  一些图形是作为代理与元素序列交互的副产品（例如用户在网站上的页面导航）创建的。当一个图形由这种非随机游走的流创建时，我们可以使用这个过程直接得到节点序列。 以这种方式采样的图不仅可以捕获与网络结构有关的信息，而且还可以捕获遍历路径的频率。
  这种方法可以与Streaming结合使用，在不断发展的网络上训练特征，而不必明确地构造整个图形。

实验：

数据集：

• BlogCatalog是博客作者的社交关系网络。标签代表作者提供的主题类别。
• Flickr是照片分享网站用户之间的联系网络。标签代表用户的兴趣组，如“黑白照片”。
• YouTube是流行的视频分享网站用户之间的社交网络。 这里的标签代表喜欢不同类型视频（例如动漫和摔跤）的观众群体。

表1 实验数据集概况

对比算法

• SpectralClustering
• Modularity
• EdgeCluster
• wvRN
• Majority

实验设计

  实验中通过多标签分类任务来评估算法的性能。
  从数据集中随机抽样标记节点的一部分(T_R)，并将其用作训练数据。 其余的节点被用作测试。 我们重复这个过程10次，并报告Macro-F1和Micro-F1的平均性能。
  对于所有的模型，使用由LibLinear [11]实现的one-vs-rest逻辑回归扩展来返回最可能的标签。
  将DeepWalk中的参数设置为：γ=80，w=10，d =128。在SpectralClustering，Modularity，EdgeCluster中，将维度设置为500。

实验结果及分析

BlogCatalog

实验结果：

表2 BlogCatalog数据集上多分类问题结果   在实验中，将BlogCatalog网络上的训练比率(T_R)从10％提高到90％，粗体数字表示每列中最高的性能。

结果分析：

1. DeepWalk的性能始终优于EdgeCluster，Modularity和wvRN。DeepWalk在只有20％的节点被标记时的性能，比这些方法在90％的数据时被标记的情况下执行得更好。
2. SpectralClustering的性能更具竞争力，但是当Macro-F1(TR≤20％)和Micro-F1(TR≤60％)上的标记数据稀疏时，DeepWalk仍然表现优异。

通过以上两点可以看出，算法的优势在于，只有小部分图表被标记时，具有强大的性能。

Flickr

实验结果：

表3 Flickr数据集上多分类问题结果   在实验中，将Flickr网络上的训练比率(T_R)从1％变为10％。 这相当于在整个网络中有大约800到8000个节点标记用于分类。 表3给出了实验结果，粗体数字表示每列中最高的性能。

结果分析：

1. 对于Micro-F1，DeepWalk的性能至少要比其他算法高出3％。DeepWalk可以比其他算法少60％的培训数据。
2. 在Macro-F1中表现也相当不错，最初接近SpectralClustering。

YouTube

实验结果：

表4 YouTube数据集上多分类问题结果   YouTube网络规模大，更接近现实世界网络。SpectralClustering和Modularity不能用于这种规模的网络。
  在实验中，训练比率(T_R)从1％变化到10％，粗体数字表示每列中最高的性能。

结果分析：
  从实验中可以看出，DeepWalk明显优于其他算法：DeepWalk可以扩展到大图，并且在这样一个稀疏标记的环境中执行得非常好。

参数灵敏度

  为了评估DeepWalk的参数变化如何影响其在分类任务上的性能，我们对两个多标签分类任务(Flickr和BlogCatalog)进行了实验。实验中固定窗口大小和步长(w = 10，t = 40)，然后，改变潜在维度(d)，每个游走的长度(γ)，以及可用的训练数据量(T_R)，以确定它们对网络分类性能的影响。

图5 参数灵敏度研究

维度(d)

  图5(a)显示了维度变化的影响。图5(a1)和5(a3)分析了维度和训练比例对性能的影响。图5(a2)和5(a4)展示了维数和随机游走数量对性能的影响。

1. a1和a3显示模型的最佳维度取决于训练示例的数量。
2. 通过a2和a4可以看出，在γ确定的情况下，不同维度下，算法的性能是相对稳定的。当γ>=30时，算法的性能比较好。两个图在γ的不同值之间的相对差异是一致的。

  这些实验表明，算法可以生成各种大小的有用模型。模型的性能取决于随机游走的数量，而模型的最优维度取决于可用的训练样例。

采样率(γ)

  图5(b)显示了改变γ对性能的影响。结果对于不同的维度(图5b1，图5b3)和不同训练数据量(图5b2，图5b4)非常一致。 最初，增加γ对结果有很大的影响，但是当γ>10时，这种影响迅速减慢。
  这些结果表明，当随机游走的数量足够多时，我们才能够学习顶点的有意义的潜在表示。

总结

  本文提出DeepWalk，一种学习顶点潜在表示的新方法，是对语言建模算法的一般化。文中通过实验说明了算法的有效性。作为在线算法，DeepWalk是可扩展的，可以为大规模、稀疏的图创建有意义的表示。DeepWalk还是可并行的，允许工作人员同时更新模型的不同部分。