ABSTRACT

我们提出了一种新的学习网络顶点内容表示的方法DeepWalk。这些最新的表现形式将社会关系编码在一个连续的向量空间中，这很容易被统计模型利用。Deep Walk概括了语言建模和无监督特征学习（或从单词序列到图形的深度学习）的最新进展。DeepWalk使用从trun-cated随机游动中获得的局部信息，通过将游动视为句子的等价物来学习潜在的表示。我们演示了DeepWalk-s在多个社交网络分类任务（如Blog Catalog、Flickr和YouTube）上的潜在表示。我们的结果表明，深度行走优于具有挑战性的基线，后者允许对网络进行全局查看，特别是在缺少信息的情况下。当标记数据稀疏时，DeepWalk-s表示可以提供比竞争方法高10%的F1分数。在一些实验中，Deep Walk-s表示能够在使用60%较少训练数据的情况下优于所有baselin方法。DeepWalk也是可伸缩的。它是一种在线学习算法，能够建立有用的增量结果，并且具有很小的可并行性。这些特性使其适合于广泛的实际应用，如网络分类和异常检测。

  1. INTRODUCTION

网络表示的稀疏性既是优点也是缺点。稀疏性使得设计出高效的离散算法成为可能，但在统计学习中更难推广。网络表示的稀疏性既是优点也是缺点。稀疏性使设计出科学的离散算法成为可能，但也使统计学习更难推广。机器学习在网络中的应用（如网络分类、异常检测[5]和丢失链路预测[22]）必须能够处理这种稀疏性才能生存。本文首次将深度学习（无监督特征学习）技术引入到网络分析中，并在自然语言处理领域取得了成功。我们开发了一种算法（DeepWalk），通过对短随机游动流建模，学习图s顶点的社会表示。社会表征是获取邻域相似性和社区成员身份的顶点的潜在特征。这些潜在的表现形式将社会关系编码在一个相对较少维度的连续向量空间中。DeepWalk将神经语言模型推广到处理由一组随机生成的walks组成的特殊语言。这些神经语言模型已经被用来捕捉人类语言的语义和句法结构[6]，甚至是逻辑类比[28]。

DeepWalk以图作为输入，并生成一个潜在表示作为输出。将我们的方法应用于研究良好的空手道网络的结果如图1所示。图1a显示了通常由力定向布局显示的图形。图1b显示了我们方法的两个潜在维度的输出。除了惊人的相似性之外，我们注意到（1b）的线性可分离部分对应于通过输入图（1a）中的模块化最大化发现的聚类（如顶点颜色）。

为了展示DeepWalk-s在现实世界中的潜力我们评估了它在挑战大型异构图中的多标签网络分类问题上的性能。在关系分类问题中，特征向量之间的联系违反了传统的i.i.d.假设。解决这个问题的技术通常使用近似推理技术[ 31, 35 ]来利用依赖信息来改进分类结果。我们通过学习图的labelindependent表示来与这些方法保持距离。我们的表示质量不受标记顶点选择的影响，因此它们可以在任务之间共享。DeepWalk在创建社会维度方面优于其他潜在的表示方法[39，41]，特别是在标记节点稀少的情况下。在非常简单的线性分类（如logistic回归）下，我们的表现可能很强。我们的表示是通用的，可以与任何分类方法（包括迭代推理方法）结合使用。DeepWalk实现了所有这些，同时也是一个简单可并行化的在线算法。我们的贡献如下：

我们引入深度学习作为分析图形的工具，以构建适合统计建模的健壮表示。DeepWalk学习短随机游动中存在的结构规则。我们广泛评估了我们在多个社交网络上的多标签分类任务中的表现。

我们在标记稀疏度的存在下，显示出显著的分类性能，在我们所考虑的最稀疏的问题中，改进了微F1的5%～10%。在某些情况下，即使训练数据减少60%，DeepWalk-s的表现也能胜过竞争对手。

我们通过使用一个并行实现来构建web比例图（如YouTube）的表示来演示我们算法的可伸缩性。此外，我们还描述了构建流式版本的方法所需的最小更改。

论文的其余部分安排如下。在第2节和第3节中，我们讨论了数据网络中分类的问题公式，以及它与我们的工作的关系。在第4节中，我们介绍了DeepWalk，我们的社会表征学习方法。我们在第5节概述了我们的实验，并在第6节介绍了它们的结果。最后，我们将在第7节中讨论相关工作，并得出结论。

  1. PROBLEM DEFINITION

我们考虑将社交网络的成员划分为一个或多个类别的问题。更正式地说，设G=（V；E），其中V是网络的成员，E是网络的边缘，E （V  V）。给定一个部分标记的社交网络GL=（V；E；X；Y），其中S是每个属性向量的特征空间大小，Y 2 RjV j  jYj，Y是一组标签。在传统的机器学习分类环境中，我们的目标是学习一个假设H，它将X的元素映射到标签集Y。在我们的例子中，我们可以利用G的结构中嵌入的示例依赖性的显著信息来获得更好的性能。