一、基本信息

论文题目：《DeepWalk: Online Learning of Social Representations》

发表时间：KDD 2014

论文作者及单位：

论文地址：https://dl.acm.org/citation.cfm?id=2623732

 

二、摘要

        网络表示的稀疏性既是优点也是缺点。稀疏性使得设计有效的离散算法成为可能，但也使得在统计学习中更难推广。网络中的机器学习应用程序（如网络分类[16，37]、内容建议[12]、异常检测[6]和丢失链接预测[23]）必须能够处理这种稀疏性才能生存。本文首次在网络分析中引入了在自然语言处理中获得成功的深度学习（无监督特征学习）技术，提出了一种新的方法(DeepWalk)来学习网络中顶点的潜在表示。这些潜在的表征将社会关系编码在一个连续的向量空间中，这很容易被统计模型利用。DeepWalk概括了语言建模和无监督特征学习（或深度学习）的最新进展，从单词序列到图表。
       DeepWalk中使用截断随机游走获得的局部信息，通过将游走视为句子的等价物来学习潜在的表示。我们展示了Deep Walk对社交网络（如BlogCatalog、Flickr和YouTube）的多标签网络分类任务的潜在表现。我们的结果表明，DeepWalk优于具有挑战性的baseline，这些baseline允许对网络进行全局查看，尤其是在信息缺失的情况下。当标记数据稀疏时，Deepwalk的表示可以提供比竞争方法高10%的F1分数。在一些实验中，DeepWalk的表现可以超越所有的基线方法，并且是在使用少于60%的训练数据的情况下。
        DeepWalk也具有可扩展性。它是一种在线学习算法，可以生成有用的增量结果，并且非常容易并行。这些特性使其适用于广泛的现实应用，如网络分类和异常检测。

 

三、主要内容与工作

1、本文的贡献有如下三点：

• 我们引入深度学习作为分析图表、构建适合统计建模的强大表示的工具。DeepWalk研究短随机游动中存在的结构规律。
• 我们广泛评估了我们在多个社交网络上的多标签分类任务的表现。我们发现在标签稀疏的情况下，分类性能显著提高，在我们考虑的最稀疏问题上，Micro F1的改进率为5%-10%。在某些情况下，即使在培训数据减少60%的情况下，DeepWalk的表现也可以超越竞争对手。
• 我们通过使用并行实现构建Web比例图（如YouTube）的表示来演示算法的可伸缩性。此外，我们描述了构建我们方法的流式版本所需的最小更改。

2、DeepWalk的功能简单来说就是在一幅图中建立坐标系，然后给出每个点的坐标。如下图所示：

3、算法

 

四、总结

        我们提出了一种学习顶点潜在社会表征的新方法——DeepWalk。该方法利用截断随机游动的局部信息作为输入，学习一种对结构规律进行编码的表示法。对各种不同图表的实验说明了我们的方法在挑战多标签分类任务方面的效果。
        作为一种在线算法，DeepWalk也具有可扩展性。我们的结果表明，对于标准光谱方法来说，我们可以为太大的图创建有意义的表示。在如此大的图上，我们的方法明显优于其他为稀疏性而设计的方法。我们还表明，我们的方法是可并行的，允许工人同时更新模型的不同部分。

        除了有效和可扩展之外，我们的方法也是语言建模的一个吸引人的概括。这种联系是互惠互利的。语言建模的进步可能会继续为网络生成改进的潜在表示。在我们看来，语言建模实际上是从一个不可观察的语言图中取样。我们相信，从对可观测图建模中获得的见解，反过来可能会提高对不可观测图的建模。

       我们在该领域的未来工作将集中在进一步研究这种二元性，利用我们的结果改进语言建模，并加强方法的理论合理性。