DeepWalk原理理解：DeepWalk: online learning of social representations

文献：DeepWalk: online learning of social representations

对比阅读了几篇关于网络表示学习的文献，其中一篇包括DeepWalk的提出，下面将自己对于论文的理解和论文的笔记组织好记录下来。

---

deep walk 的提出是针对网络表示学习的稀疏性提出来的，网络表示学习的稀疏性问题对于统计学习任务有一定难度。

deep walk 学习的是图中顶点的社会特征（the social representation of graph's vertices）,它对随机游走进行了改进：一种缩短了的流式随机游走的方法（ a stream of short random walk）.

下图引自论文中：

---

利用流式的短的随机游，提出了一个通用的语言模型探究图结构

 根据随机游走中包含的顶点来估计下一个顶点出现的概率：

 

需要一个映射函数：

这个映射函数表示了顶点之间隐藏的社会特征(social representation)，其中这个映射函数是一个|V| x d的矩阵

由此一来，eq.1式转化为：

 

关于随机游走值得关注的问题：随机游走的长度会越来越大（walk length grows）,这样以来我们在计算eq.1或者eq. 2式条件概率的时候会出现困难。

针对上面这个问题对随机游走进行了改进：

• 通过单词来预测上下文而不是通过上下文来预测单词
• 上下文的组成有单词左右两边的信息组成
• 去掉顺序的约束

 

对随机游走进行了改进后，eq.2 的问题转化

---

deep walk 的算法描述

deep walk包括两个部分，一个是随机游走生成器，一个是更新程序

 

 

---

在本文中涉及到的一个streaming 方法,是为了在不知道整个图的情况下，也可以采用本算法。

streaming approach could 被implemented without knowledge of the entire graph.

---