DeepWalk: Online Learning of Social Representations
论文信息
- 作者：来源于纽约州立大学石溪分校，一个很有名的学校。
辅助资料
笔记
核心思想
- 使用RandomWalk提取节点共现信息
- 类比Word2Vec对提取的节点序列进行图嵌入
- 使用分层Softmax进行加速计算（并行化）
使用RandomWalk提取节点共现信息
生成随机游走序列
对于连通图 \(\mathcal{G=\{V,E\}}\)，确定一个起始节点 \(\mathcal{v_0 \in V}\)开始随机游走，每一次随机游走，从当前节点，随机走到该节点的一个邻节点（等概率），数学表示如下：
\[p\left(v^{(t+1)} \mid v^{(t)}\right)= \begin{cases}\frac{1}{d\left(v^{(t)}\right)}, & \text { if } v^{(t+1)} \in \mathcal{N}\left(v^{(t)}\right) \\ 0, & \text { otherwise }\end{cases} \]随机游走生成一系列节点序列 \(\mathcal{W}\)，使用RW()表示随机游走生成器，则 \(\mathcal{W}=\mathrm{RW}\left(\mathcal{G}, v^{(0)}, T\right)\)，其中 \(\mathcal{W}=\left(v^{(0)}, \ldots, v^{(T-1)}\right)\) 表示随机游走序列，\(\mathcal{v_0 \in V}\) 表示起始节点，\(T\) 表示随机游走的长度。
为了捕获整个图的信息，以图中每个节点作为起始节点进行随机游走，每个起始节点生成 \(\gamma\) 个随机游走序列，总共获取 \(|\mathcal{V}|\cdot \gamma\) 条随机游走序列。
生成共现列表 \(\mathcal{I}\)
注：这一部分是马耀老师《图深度学习》上的内容，原文献并没有直接写这一部分，而是将其放在了Skip-Gram算法中。
共现信息
共现信息一开始用于语言模型，字面上看，就是“一起出现”的意思，如果两个单词同时出现在一个句子中，就能构成共现。
在实际任务（比如完形填空）中，我们把句子中的一个词作为“中心词”，记作 \(v_{cen}\)，中心词前后 \(w\) 个词内的范围叫做上下文，中心词和上下文的每个词（记作 \(v_{con}\)）形成一个一个共现，使用二元组的形式表示 \((v_{con}, v_{cen})\)。
节点共现的提取（生成共现列表）
我们之前已经生成了 \(|\mathcal{V}|\cdot \gamma\) 条随机游走序列，每个随机游走序列可以看成一个句子，对所有序列中每一个节点 \(v^{(i)}\)，将其作为中心节点，其前后 \(w\) 个节点作为上下文节点，将二元组 \((v^{(i-j)},v^{(i)})\) 和 \((v^{(i+-j)},v^{(i)})\) 加入共现列表 \(\mathcal{I}\)。
使用Skip-Gram生成节点的嵌入表示
语言模型
疑问
- DeepWalk似乎只是提取了图结构（也就是节点之间的关系），而没有对节点本身的特征做处理，如果原来的节点就有特征，如何与DeepWalk结合？
知识树
- DeepWalk
- 节点共现信息
- 图嵌入
- 图信号处理
- 图
- 图信号处理
- 词共现
- 图嵌入
- RandomWalk生成随机游走序列
- 随机游走序列中包含的节点共现信息
- 使用Skip-Gram生成节点的嵌入表示
- 分层Softmax加速计算
- 节点共现信息
展示树
- 为什么需要图嵌入？（类比词嵌入，图结构让节点间不是相互独立的）
- DeepWalk的输入输出（也就是图嵌入的输入输出，图结构输入，嵌入表示输出）
- 什么是节点共现？（类比词共现）
- 如何使用RandomWalk提取节点共现信息？
- 生成随机游走序列
- 生成共现列表
- Skip-Gram算法生成