DeepWalk: Online Learning of Social Representation

1. 简介

1.1 摘要

We presentDeepWalk, a novel approach for learning la-tent representations of vertices in a network. These latentrepresentations encode social relations in a continuous vectorspace, which is easily exploited by statistical models.Deep-Walkgeneralizes recent advancements in language mod-eling and unsupervised feature learning (ordeep learning)from sequences of words to graphs.DeepWalkuses local information obtained from trun-cated random walks tolearnlatent representations by treat-ing walks as the equivalent of sentences. We demonstrateDeepWalk’s latent representations on several multi-labelnetwork classification tasks for social networks such as Blog-Catalog, Flickr, and YouTube. Our results show thatDeep-Walkoutperforms challenging baselines which are alloweda global view of the network, especially in the presence ofmissing information.DeepWalk’s representations can pro-videF1scores up to 10% higher than competing methodswhen labeled data is sparse. In some experiments,Deep-Walk’s representations are able to outperform all baselinemethods while using 60% less training data.DeepWalkis also scalable. It is an online learning algo-rithm which builds useful incremental results, and is triviallyparallelizable. These qualities make it suitable for a broadclass of real world applications such as network classifica-tion, and anomaly detection.

我们展示了DEEPWALK——一种用于学习网络中节点的潜在表示的原生方法。这些潜在的表示在一个连续的向量空间中编码了社会关系，可以轻松应用到统计学习模型中去。DEEPWALK整合了从单词序列到图形的语言模型和无监督特征学习的最新进展。DEEPWALK把游走序列看做句子，利用从截断随机游走获得的局部信息来学习节点的潜在表示。我们在一些社交网络例如BlogCatlog、Flickr和Youtubu数据集上，通过多标签网络分类任务验证了DeepWalk学习到的潜在表示。我们的结果表明DeepWalk优于很多有挑战性的baseline，尤其在信息缺失的情况下。在有标签数据稀疏的情况下，DeepWalk的F1得分要比对比方法高10%。在一些实验中，尽管训练数据少60%，DeepWalk的效果仍然要优于所有的baseline。DeepWalk也是可扩展的，它是一种在线学习算法，可以建立有用的增量结果，并且可以并行化。这些性质使其适合很多现实世界中的应用，如网络分类，异常检测等。

1.2 简介

这篇文章中，作者将自然语言处理中的模型推广到网络表示学习中，将随机游走序列看做句子，将顶点看做单词，通过对游走序列进行建模来学习图中顶点的潜在特征。

DeepWalk的输入时一张图，输出的是潜在表示。算法在Karate网络中的效果如下图所示，我们发现除了输入和输出之间结构上的惊人相似外，算法输出的潜在表示还是线性可分的。

DeepWalk具有以下优点：

• DeppWalk效果比其他方法要好，尤其在有标签节点数量很少的时候。
• DeepWalk得到的潜在表示泛化能力更好，适用于非常简单的线性分类器，并且可以和任何分类方法结合。
• DeepWalk是一个在线算法，并行程度高

这篇文章作者的主要贡献有：

2. 方法

2.1 问题定义

图$G=(V,E)$，V表示网络中的节点，$E\subseteq(V\times V)$表示边。给定部分节点有标签的社交网络$G_L=(V,E,X,Y)$，属性$X\in\mathbb R^{|V|\times S}$，S表示特征空间的大小，$Y\in\mathbb R^{|V|\times|\mathcal Y|}$是标签集合。

2.2 算法

DeepWalk算法包含两部分：随机游走序列生成器和参数更新程序。

• **Random Walk Generator：**输入图G，从$v_i$节点开始，生成指定长度t的游走序列$W_{v_i}$

• **Update Procedure：**使用SkipGram算法更新节点表示（SkipGram模型可参考https://zhuanlan.zhihu.com/p/27234078）

  

层次Softmax：https://zhuanlan.zhihu.com/p/56139075

未完待续... ...