论文解读(DeepWalk)《DeepWalk: Online Learning of Social Representations》

2021年11月22日 阅读数:2
这篇文章主要向大家介绍论文解读(DeepWalk)《DeepWalk: Online Learning of Social Representations》,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

1、基本信息

论文题目:《DeepWalk: Online Learning of Social Representations》
发表时间:  KDD 2014
论文做者:  Bryan Perozzi、Rami Al-Rfou、Steven Skiena
论文地址:  https://dl.acm.org/citation.cfm?id=2623732算法


2、前言

  普通的邻接矩阵在存储的关系不少时,纬度将变得很高,而进行矩阵分解是一个至关费时复杂的过程,所以经过矩阵分解的方法进行网络的表示学习,目前并无应用到大尺度数据集的方案。express

  本文经过将已经成熟的天然语言处理模型word2vec应用到网络的表示上,作到了无需进行矩阵分解便可表示出网络中的节点的关系。网络

  DeepWalk把图中节点进行的一串随机游走类比于 word2vec 中单词的上下文,做为 word2vec 算法的输入,进而把节点表示成向量。输出的结果可以被多种分类算法做为输入应用。app


3、介绍

  Deepwalk:将一个网络中的每一个节点映射成一个低维的向量:用一个向量去表示网络中的每一个节点,而且但愿这些向量可以将网络中的节点中的关系表达出来,即但愿在原始网络中关系越紧密的结点对应的向量在其空间中距离越近。dom

    

  举例:输入是一个 Karate Graph,其中颜色相同的结点表示拓扑关系上更为相近的结点;输出是每一个节点的二维向量,每一个节点对应的向量关系如上图所示。从这个图看出,越是拓扑结构相近的点,其对应的二维向量在二维空间上距离与近。机器学习

  我的理解:可将这个过程理解为一个降维过程,但不一样于传统意义上的高纬度降到低纬度,而是将一个复杂的结构降到低纬度。或者能够理解为:将网络中的拓扑结构,嵌入到一个低维向量中,每一个节点的低维向量,从某种程度上反应了该节点在网络中的链接状况。异步

  网络数据不一样于传统的数据,它不只包含了节点的信息,还包含了节点间的关系,对于传统的机器学习算法,很难将其应用于网络中。例如网络中的社团发现算法,大多数状况下咱们都针对网络作大量的游走,不断改变网络的社团结构,以使网络得到最优的模块度,可是若是咱们能将拓扑信息嵌入到低维向量中,那么每一个节点咱们均可以看作是一个样本,每一个维度均可以看作一个 feature,那么只须要跑个聚类算法,就能够获得很好的结果。除了聚类,还有链路预测、推荐等一系列网络中的问题,均可以直接扔到机器学习的相关算法中跑出来。ide


4、Problem definition

     $G_{L}=(V, E, X, Y) $模块化

    $X \in \mathbb{R}^{|V| \times S} \quad S \  is\  the\  size\  of\  feature\  space $函数

    $E \subseteq(V \times V)$

    $Y \in \mathbb{R}^{|V| \times|\mathcal{Y}|} \quad \mathcal{Y} \  is\  the\  size\  of\  labels\  set  $

  输入:一个图的点集和边集

  输出:对于通常的机器学习问题,须要学习一个从 $X$ 映射到 $Y$ 的 hypothesis。而本文的任务就是学习获得$X$ 的低维表示。

  Goal:Our goal is to learn $X_{E} \in \mathbb{R}^{|V| \times d}$ , where d is small number of latent dimensions. These low-dimensional representations are distributed; meaning each social phenomena is expressed by a subset of the dimensions and each dimension contributes to a subset of the social concepts expressed by the space.

有意思的思考:

原文:
  We propose a different approach to capture the network topology information. Instead of mixing the label space as part of the feature space,
we propose an unsupervised method which learns features that capture the graph structure independent of the labels’ distribution.
  This separation between the structural representation and the labeling task avoids cascading errors, which can occur in iterative methods.

5、Learning social representations

  文中提到,在学习一个网络表示的时候须要注意的几个性质:

    • Adaptability:网络表示必须能适应网络的变化。网络是一个动态的图,不断地会有新的节点和边添加进来,网络表示须要适应网络的正常演化。
    • Community aware:属于同一个社区的节点有着相似的表示。网络中每每会出现一些特征类似的点构成的团状结构,这些节点表示成向量后必须类似。
    • Low dimensional:表明每一个顶点的向量维数不能太高,太高会有过拟合的风险,对网络中有缺失数据的状况处理能力较差。
    • Continuous:低维的向量应该是连续的。

6、Random Walks

  所谓随机游走(random walk),就是在网络上不断重复地随机选择游走路径,最终造成一条贯穿网络的路径。从某个特定的端点开始,游走的每一步都从与当前节点相连的边中随机选择一条,沿着选定的边移动到下一个顶点,不断重复这个过程。

  关于随机斿走的符号解释: 以  $v_{i}$  为根节点生成的一条随机游走路径为  $W_{v_{i}} $ ,其中路径上的点分别标记为  $W_{v_{i}}^{1}, W_{v_{i}}^{2}, W_{v_{i}}^{3} \ldots$。

  截断随机游走(truncated random walk)实际上就是长度固定的随机游走。

  随机游走的两个好处:

    • 并行化,随机游走是局部的,对于一个大的网络来讲,能够同时在不一样的顶点开始进行必定长度的随机游走,多个随机游走同时进行,能够减小采样的时间。
    • 适应性,能够适应网络局部的变化。网络的演化一般是局部的点和边的变化,这样的变化只会对部分随机游走路径产生影响,所以在网络的演化过程当中不须要每一次都从新计算整个网络的随机游走。

7、Connection: Power laws

  使用随机游走的顶点,附近顶点分布知足 power-low 分布

  文中提到网络中随机游走的分布规律与NLP中句子序列在语料库中出现的规律有着相似的幂律分布特征。那么既然网络的特性与天然语言处理中的特性十分相似,就能够将NLP中词向量的模型用在网络表示中,这正是本文所作的工做。

    


8、语言模型

  首先来看词向量模型:
    $w_{i}^{u}=\left(w_{0}, w_{1}, w_{2}, \ldots, w_{n}\right)$  是一个由若干单词组成的序列,其中 $w_{i} \in V( Vocabulary )$,$V$  是词汇表,也就是全部单词组成的集合。
  在整个训练集上须要优化的目标是:

    $\operatorname{Pr}\left(w_{n} \mid w_{0}, w_{1}, \ldots, w_{n}-1\right)$

  也就是给定 $w_0,w_1,.......,w_{i-1}$ 要求出下一个 $w_{i}$ 出现的几率

  将语言模型中的单词映射到图表示上去,单词即对应了图中的节点 $v_i$ ,句子序列对应了网络中的随机游走,那么对于一个随机游走$v_0,v_1,v_2,.......,v_{i-1}$须要优化的目标是:

  $\operatorname{Pr}\left(v_{i} \mid\left(v_{0}, v_{1}, \ldots, v_{i-1}\right)\right)$

  按照上面的理解就是,当知道  $\left(v_{0}, v_{1}, \ldots, v_{i-1}\right)$  游走路径后,游走的下一个节点是  $v_{i}$  的几率是多少? 但是这里的  $v_{i}$  是顶点自己无法计算,因而引入一个映射函数$\Phi$,它的功能是将顶点映射成向量,转化成向量后就能够对顶点  $v_{i}$  进行计算了。

    $\Phi: v \in V \mapsto \mathbb{R}^{|V| \times d}$

  因此怎么计算这个几率呢?一样借用词向量中使用的 skip-gram 模型 。

  Skip-gram模型有这样3个特色:

    • 不使用上下文 (context) 预测缺失词 (missing word),而使用缺失词预测上下文。由于 $\left(\left(v_{0}\right),\left(v_{1}\right), \ldots,\left(v_{i}-1\right)\right)$  这部分太难算了,可是若是只计算一个 $\left(v_{k}\right)$ 和左右 2 个窗口内的节点,其中 $v_{k}$  是缺失词,这就很好算。 
    • 不考虑顺序,只要是窗口中出现的词都算进来,而无论它具体出如今窗口的哪一个位置。

  应用 Skip-gram 模型后,优化目标变成了这样:

    $\underset{\Phi}{\operatorname{minimize}}  \quad-\log \operatorname{Pr}\left(\left\{v_{i-w}, \cdots, v_{i-1}, v_{i+1}, \cdots, v_{i+w}\right\} \mid \Phi\left(v_{i}\right)\right)$


9、Algorithm: DeepWalk

  整个 DeepWalk 算法包含两部分,一部分是随机游走的生成,另外一部分是参数的更新。

  随机游走的生成:随机游走生成器取一个图 $G$,并均匀地采样一个随机顶点 $v_i$ 做为随机游走$W_{v_i}$ 的根。从访问的最后一个顶点的邻居中均匀地采样,直到达到最大长度 $t$ 。

  算法:

  

  第 3 行表明整个过程迭代次,每次为每一个采样节点进行一次随机游走。第 4 行表明对节点进行随机排列,这不是必须的,可是能够加速随机梯度降低的收敛。对于每一个随机游走,使用第7行的 SkipGram 进行参数的更新。


10、SkipGram

  SkipGram是一种语言模型,它最大化句子中大小的窗口内出现的词的共现几率。算法2 展现了SkipGram在DeepWalk中的应用:

  算法2 迭代出如今窗口 $w$(第1-2行)内的随机游走中的全部可能的组合。对于每一个顶点,咱们将每一个顶点 $v_j$ 映射到它当前的表示向量$\Phi\left(v_{j}\right) \in \mathbb{R}^{d}$ (见图3b)。给定 $v_j$ 的表示,咱们但愿最大限度地提升其邻居在行走中的几率(第3行)。咱们可使用不一样的分类器来学习这种后验分布。例如,使用逻辑回归建模前面的问题将致使大量的标签(约 $|V|$ ),多是数百万或数十亿美圆。这样的模型须要大量的计算资源,能够跨越整个计算机集群。为了加快训练时间,可使用 Hierarchical Softmax 最大来近似几率分布。


11、Hierarchical Softmax

  考虑到 $u_{k} \in V$,在第3行中计算 $\operatorname{Pr}\left(u_{k} \mid \Phi\left(v_{j}\right)\right)$ 是不可行的。计算配分函数(归一化因子)成本昂贵。若是咱们将 顶点 分配给二进制树的叶子,预测问题就会变成树中特定路径的几率最大化(见 Figure 3c)。若是到顶点 $u_k$ 的路径是由一系列树节点识别的$\left(b_{0}, b_{1}, \ldots, b_{\lceil\log |V|\rceil}\right)$,$(b_0=root,b_{\lceil\log |V|\rceil}=u_{k})$,那么

    $\operatorname{Pr}\left(u_{k} \mid \Phi\left(v_{j}\right)\right)=\prod \limits _{l=1}^{\lceil\log |V|\rceil} \operatorname{Pr}\left(b_{l} \mid \Phi\left(v_{j}\right)\right)$

  如今,$\operatorname{Pr}\left(b_{l} \mid \Phi\left(v_{j}\right)\right)$ 能够经过分配给节点 $b_l$ 的父节点的二进制分类器来建模。这下降了计算 $\operatorname{Pr}\left(u_{k} \mid \Phi\left(v_{j}\right)\right)$ 的计算复杂度,从 $O(|V|)$ 下降到 $O(log|V|)$ 。咱们能够经过为随机行走中的频繁顶点分配更短的路径来进一步加快训练过程。霍夫曼编码用于减小树中频繁元素的访问时间。

    


12、Parallelizability

  如图2所示,社交网络随机游动中的顶点和一种语言中的单词的频率分布都遵循幂律。这致使了罕见顶点的长尾,所以,影响Φ的更新本质上是稀疏的。这容许咱们在多工做人员的状况下使用异步版本的随机梯度降低(ASGD)的方法。鉴于咱们的更新是稀疏的,而且咱们没有得到一个锁来访问模型共享参数,ASGD将实现一个最佳的收敛速度[36]。虽然咱们在一台机器上使用多个线程运行实验,但已经证实了这种技术具备高度的可伸缩性,而且能够用于很是大规模的机器学习[8]。图4显示了并行化“深度行走”的效果。它显示了随着工做目录的数量增长到8人,博客目录和Flickr网络的处理速度是一致的(图4a)。它还代表,相对于连续运行的DeepWalk,预测性能没有损失(图4b)

     

  上图显示了并行对DeepWalk的影响。图(a)当多个任务同时进行时,算法的速度变快。图(b)代表,并行运行下,DeepWalk的性能没有受到影响。


十3、实验效果展现

  数据集

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

     

  Baseline Methods
    • SpectralClustering:该方法从图 $G$ 的标准化拉普拉斯矩阵 $\widetilde{\mathcal{L}}$ 选择 d-smallest 个特征向量生成 $\mathbb{R}^d $ 的表示。利用$\widetilde{\mathcal{L}}$ 的特征向量隐式地假设图剪切将对分类有用。
    • Modularity:该方法从 $G$ 的  Modularity matrix B的  top-d 特征向量生成 $\mathbb{R}^d $ 的表示。B 的特征向量编码了 $G$ 的模图分区信息。使用它们做为特征能够假设模块化图分区对分类颇有用。
    • EdgeCluster:该方法使用 k-means 聚类对 $G$ 的邻接矩阵进行聚类,它的性能与模块化方法具备比较性,且扩展图太大,没法进行谱分解。
    • wvRN:加权投票关系邻居是一个关系分类器。给定顶点 $v_i$ 的邻域 $\mathcal{N}_{i}$,wvRN 用其邻域 ( 即 $\operatorname{Pr}\left(y_{i} \mid \mathcal{N}_{i}\right)=\frac{1}{Z} \sum \limits _{v_{j} \in \mathcal{N}_{i}} w_{i j} \operatorname{Pr}\left(y_{j} \mid \mathcal{N}_{j}\right)$ ) 估计 $\operatorname{Pr}\left(y_{i} \mid \mathcal{N}_{i}\right)$ 。它在真实网络中显示出惊人的良好性能,并被提倡做为一种合理的关系分类基线。
    • Majority:这种 naive 方法简单地选择训练集中最频繁的标签。

十4、实验

  为了便于咱们的方法与相关基线之间的比较,咱们使用了与[39,40]中彻底相同的数据集和实验程序。具体来讲,咱们随机抽取标记节点的一部分( $T_R$ ),并将它们做为训练数据。其他的节点被用做测试。咱们重复这个过程 10 次,并报告了 $Macro-F1$ 和 $Micro-F1$ 的平均性能。若是可能的话,咱们在这里直接报告原始结果[39,40]。对于全部的模型,咱们使用由 Lib Linear[10] 实现的  one-vs-rest 进行分类。咱们给出了使用( $γ=80,w=10,d=128$ )行走的结果。(光谱聚类、模块化、边缘聚类)的结果使用了 Tang 和 Liu 的首选维数,$d=500$ 。

BlogCatalog

  在本实验中,咱们将 BlogCatalog 网络上的训练比率( $T_R$ )从 10% 提升到 90% 。咱们的结果如 Table 2 所示。粗体中的数字表示每一列中的最高性能。DeepWalk的性能始终优于 EdgeCluster 、Modularity 和 wvRN。事实上,当只使用 20% 的节点进行训练时,DeepWalk 在得到 90% 的数据时比这些方法表现得更好。SpectralClustering 的性能被证实更具竞争力,但当在 $Macro-F_1$ ($ T_R≤20% $) 和 $Micro-F1$(T_R≤60% )上的标记数据稀疏时,DeepWalk的性能仍然优于后者。当图的一小部分被标记时,这种强大的性能是咱们方法的核心优点。在接下来的实验中,咱们研究了咱们的表示在更稀疏标记的图上的性能。

    

Flickr

  在本实验中,咱们将 Flickr 网络上的训练比率( $T_R$ )从 $1%$ 变化到 $10%$。这至关于在整个网络中有大约 800 到 8000 个节点被标记出来进行分类。Table 3 显示了咱们的结果,这与以前的实验结果一致。与Micro-F1相比,DeepWalk 的性能比全部基线高出至少 $3%$。此外,当只有 $3%$ 的图被标记时,它的 $Micro-F1$ 性能优于全部其余方法,即便它们获得了 $10%$ 的数据。换句话说,DeepWalk 能够比基线的训练数据少 60%。它在 $Macro-F_1$ 中也表现得很好,最初表现接近BlogCatalog,但距离本身提升了 1%。

    

YouTube

  YouTube 网络比咱们以前实验过的要大得多,它的大小阻止了咱们的两种基线方法(SpectralClustering 和 Modularity )在它上运行。它比咱们以前考虑过的更接近一个真实世界的图。训练比例( $T_R$ ) 从 1% 到 10% 的结果如 Table 4 所示。他们代表,DeepWalk 在建立图形表示方面显著优于可伸缩的基线,即边缘集群。当 1% 的标记节点用于测试时,$Micro-F1$ 提升了14%。$Macro-F1$ 显示出相应的 10% 的增加。随着训练数据的增长,这一领先优点逐渐缩小,但DeepWalk 以 $Micro-F1$ 领先 $3% $ 结束,$Macro-F1$ 提升了使人印象深入的5%。这个实验展现了性能的好处:能够经过使用社会表征学习进行多标签分类而发生。深度行走,能够缩放到大型图形,而且在这样一个稀疏标记的环境中表现得很是好。

    

Parameter Sensitivity

  为了评估 DeepWalk 参数化的变化如何影响其在分类任务上的性能,咱们在两个多标签分类任务( Flickr 和 BlogCatalog )上进行了实验。在这个测试中,咱们将窗口大小(Window size)和 行走长度(Walk Length) 固定为合理的值( $w=10,t=40$),这应该强调局部结构。而后,咱们改变潜在维度(d)的数量、每一个顶点开始行走的次数($γ$)和可用的训练数据量( $T_R$ ),以肯定它们对网络分类性能的影响。

Effect of Dimensionality

  Figure 5a显示了增长咱们的模型可用的潜在维度数的影响。

  Figure 5a1 和 Figure 5a3 检查了改变维数和训练率的影响。Flickr和博客目录之间的性能很是一致,并代表一个模型的最优维数取决于训练示例的数量。(请注意,1%的 Flickr 拥有的标记例子大约与10%的博客目录同样多)。

  Figure 5a2 和 Figure 5a3 检查了改变每一个顶点的维数和行走次数的影响。对于不一样的 $\gamma $ 值,维度之间的相对性能相对稳定。这些图表有两个有趣的观察结果。首先,大部分好处是经过在两个图中每一个节点启动 $\gamma =30$ 行走来实现的。第二,在这两个图中,不一样的 $\gamma =30$ 值之间的相对差别是至关一致的。Flickr 比 BlogCatalog  多有一个数量级的边,咱们发现这种行为颇有趣。

  这些实验代表,咱们的方法能够制做出不一样尺寸的有用模型。他们还代表,模型的性能取决于它所看到的随机游动的次数,而模型的适当维数取决于可用的训练示例。
Effect of sampling frequency 
  Figure 5a 显示了增长 $\gamma $ 的影响,即咱们从每一个顶点开始的随机游动的次数。在不一样尺寸条件下的结果很是一致。Figure 5b一、Figure 5b3 训练数据的数量(Figure  5b2,Figure  5b4)。最初,增长 $\gamma $  对结果有很大的影响,但这种影响很快减慢($\gamma  >10$ )。这些结果代表,咱们可以在通过少许的随机游走后学习顶点的有意义的潜在表示。

十5、结论

  咱们提出了 DeepWalk,一种学习顶点潜在社会表征的新方法。利用截断随机游动的局部信息做为输入,咱们的方法学习一种编码结构规律的表示。在各类不一样的图上进行的实验说明了咱们的方法在具备挑战性的多标签分类任务上的有效性。

  做为一种 online algorithm,DeepWalk也是可扩展的。咱们的结果代表,咱们能够为太大的没法运行光谱方法的图建立有意义的表示。在如此大的图上,咱们的方法显著优于其余设计来操做稀疏性的方法。咱们还展现了咱们的方法是可并行化的,容许工做人员同时更新模型的不一样部分。

  除了有效性和可扩展性外,咱们的方法也是语言建模的一个有吸引力的泛化方法。这种联系是互惠互利的。语言建模的进步可能会继续为网络产生改进的潜在表示。在咱们看来,语言建模其实是从一个不可观察到的语言图中采样的。咱们相信,从建模可观测图中得到的看法可能反过来会对建模不可观测图产生改进。

  咱们将来在该领域的工做将集中于进一步研究这种对偶性,利用咱们的研究结果来改进语言建模,并增强该方法的理论论证。 

『总结不易,加个关注呗!』