万物皆可Embedding之Deepwalk算法解读

需求论文的冤家可当前台私信小编。

前言

自从word representation中的神奇算法word2vec出现之后，无论是学术界还是工业界都有这样一个共识——万物皆可Embedding，基于句子、文档表达的word2vec、doc2vec算法，基于物品序列的item2vec算法，基于图结构的Graph Embedding技术，无论是在引荐、广告还是反欺诈范畴，各互联网公司基于本身业务与Embedding结合的论文相继问世，本篇讲述的Deepwalk就是Graph Embedding技术中的代表，下图是graph embeddings技术的普通流程。

DeepWalk论文发表于2014年的KDD会议上，将embedding从item序列推行至图序列，它是一种用于学习网络中顶点的潜在表示的新方法。这些潜在表示将社会关系编码到延续的向量空间中，编码到向量空间后的社会关系，很容易运用到统计模型中。DeepWalk将随机游走得到的节点序列当做句子，从截断的随机游走序列中得到网络的部分信息，再经过部分信息来学习节点的潜在表示。

算法思绪

DeepWalk将一个图作为输入，并产生一个潜在表示（将图中的每个节点表示为一个向量）作为输入，如下图示例所示：

对于图结构来说，算法设计需求满足以下几个要求：

1、顺应性：社交网络是不断变化的，当网络发生变化不能对整个网络重新停止计算。

2、社区看法：节点的潜在表示对应着维度空间中的间隔，应该表示网络中对应的成员的相似度，以此保证网络的同质性。

3、低维：当被标记的成员很少时，低维的模型普通表现的更好，并且收敛和推理速度更快。

4、延续性：需求经过图的潜在表示来对延续空间中的部分社区成员停止建模。除了提供对社区成员资历的纤细视图之外，延续表示还可以使社区之间的决策界限平滑，从而完成更弱小的分类。

Deepwalk算法流程

1、展现用户行为序列
2、基于这些用户行为序列构建了物品相关图，图中的边是由用户行为产生的，比如为用户M先后购买了物品A和物品B，会产生了一条有向边由A指向B。其他的有向边也是异样的道理，假如有多个有A指向B的有向边，那么该条边的权重被加强。经过这样的方法将一切用户行为序列都转换成物品相关图中的边后，就得到全局的物品相关图。

3、采用随机游走的方式随机选择起始点，产生部分物品序列。

4、将这些物品序列当初句子停止word2vec建模，生成最终的物品Embedding向量。

图中的节点表示item,边表示item之间的交互，上边步骤中最重要的是第三步，如何随机游走产生部分物品序列。deepwalk中的游走是完全随机的，这一点需求留意。经过改变Random Walk策略才有了后面的node2vec。

Random Walk

Random Walk从截断的随机游走序列中得到网络的部分信息，并以此来学习结点的向量表示。借助言语建模word2vec中的一个模型，skip-gram来学习结点的向量表示。将网络中的结点模拟为言语模型中的单词，而结点的序列（由随机游走得到）模拟为言语中的句子，作为skip-gram的输入。

当图中结点的度遵照幂律分布(度数大的节点比较少，度数小的节点比较多）时，短随机游走中顶点出现的频率也将遵照幂律分布(即出现频率低的结点多)，又由于自然言语中单词出现的频率遵照相似的分布，因此以上假设可行。如下图作者针对YouTube的社交网络与Wikipedia的文章停止了研讨，得出二者幂率分布基本上相似。

优点：

1.并行性：同时停止多个随机游走

2.顺应性：当图变化后，不需求全局重新计算，可以迭代地更新学习模型，合适online learning。

算法完成

Deepwalk算法架构

该算法由两部分组成：一个随机游走生成器和一个更新程序。

SkipGram

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

对序列中的每个顶点，计算条件概率，即该结点出现的状况下序列中其他结点出现的概率的log值并借助随机梯度下降算法更新该结点的向量表示。

注：Φ(vj)为当前结点的向量表示。

并行性

上图显示了并行对DeepWalk的影响。图(a)当多个义务同时停止时，算法的速度变快。图(b)表明，并行运转下，DeepWalk的功能没有遭到影响。

实验效果展现

数据集

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

对比算法

SpectralClusteringModularityEdgeClusterwvRNMajority

实验中经过多标签分类义务来评价算法的功能。从数据集中随机抽样标记节点的一部分(TR)，并将其用作训练数据。 其他的节点被用作测试。 我们反复这个过程10次，并报告Macro-F1和Micro-F1的平均功能。对于一切的模型，运用由LibLinear完成的one-vs-rest逻辑回归扩展来前往最能够的标签。将DeepWalk中的参数设置为：γ=80，w=10，d =128。在SpectralClustering，Modularity，EdgeCluster中，将维度设置为500。

实验结果及分析

(1) BlogCatalog

在实验中，将BlogCatalog网络上的训练比率(TR)从10％提高到90％，粗体数字表示每列中最高的功能。

结果分析：

1、DeepWalk的功能一直优于EdgeCluster，Modularity和wvRN。DeepWalk在只要20％的节点被标记时的功能，比这些方法在90％的数据时被标记的状况下执行得更好。

2、SpectralClustering的功能更具竞争力，但是当Macro-F1(TR≤20％)和Micro-F1(TR≤60％)上的标记数据稀疏时，DeepWalk照旧表现优秀。

经过以上两点可以看出，算法的优势在于，只要小部分图表被标记时，具有弱小的功能。

(2) Flickr

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

结果分析：

1、对于Micro-F1，DeepWalk的功能至少要比其他算法高出3％。DeepWalk可以比其他算法少60％的训练数据。

2、在Macro-F1中表现也相当不错，SpectralClustering最接近它。

（3）YouTube

YouTube网络规模大，更接近理想世界网络。SpectralClustering和Modularity不能用于这种规模的网络。在实验中，训练比率(TR)从1％变化到10％，粗体数字表示每列中最高的功能。

结果分析：

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

参数敏感度实验

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

图(a)显示了维度变化的影响。图(a1)和(a3)分析了维度和训练数据比例对功能的影响。图(a2)和(a4)展现了维数和随机游走长度对功能的影响。得到如下结论：

1、a1和a3显示模型的最佳维度取决于训练数据的数量。

2、经过a2和a4可以看出，在γ确定的状况下，不同维度下，算法的功能是相对波动的。当γ>=30时，算法的功能比较好。两个图在γ的不同值之间的相对差异是分歧的。

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

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

读了这篇文章给大家留几个成绩：

（1）你觉得Deepwalk中的随机游走方式合理吗？

（2）来了一个新的item，怎样求它的embedding，需求重新训练吗？

总结

最近在重温embedding相关的论文，每一次看论文都有不同的感受，graph embedding曾经广泛运用在引荐、广告、风控反欺诈等范畴，值得我们好好读一读，有什么成绩可以和我交流。

欢迎回复、分享、收藏、点赞，更多的内容可以关注同名公众号

分享了

embedding的本质是，应用低维子空间的稠密延续向量来逼近高维空间的稀疏团圆向量，它不应该比spectral clustering效果好，但是在计算效率上应该优越不少。随机游走是图论算法的数学基础，只需算法上运用合理，随机游走会发挥宏大的效果。前沿研讨中，应用随机游走改善spectral clustering是一个很重要的学术分支，国外著名大学的一票科研人员在努力于这方面的研讨。从文中的实验数据来看，好像某些算法的完成存在改进空间，算法完成没有表现出算法的优势。文章很值得好好研讨~~~

（1）不合理。（2）需求

先mark

分享了

分享了

分享了

分享了

分享了