DeepWalk: Online Learning of Social Representations

本文是我参加Datawhale的CS224W图机器学习时的笔记，第一次学习图机器学习，对DeepWalk这篇开山之作的理解。

论文的三位作者均来自纽约州立大学石溪分校，杨振宁和丘成桐也曾在此教学。

摘要

论文的三位作者均来自纽约州立大学石溪分校，杨振宁和丘成桐也曾在此教学。

我们提出了DeepWalk，一种新颖的用于学习图中节点的潜在知识表示的方法。这些潜在的知识表示将图中节点之间的连接编码到一个连续的低维向量空间中，这使得知识很容易被统计模型所使用。DeepWalk将自然语言模型和无监督学习或深度学习在单词序列中的最新进展推广到图。
DeepWalk通过将随机游走序列类比做句子，从而利用截断的随机游走序列去学习潜在的图结点间的连接。我们在几个多标签图分类任务BlogCatalog, Flickr, and YouTube中论证DeepWalk的潜在知识的表示能力。结果显示在全图层面，DeepWalk的表现优于具有挑战性的基线方法，尤其是在有缺失信息的情况下。DeepWalk在有标签的数据稀疏的情况下比同类方法的F1成绩提高10%。DeepWalk优于所有的基线方法同时，少用了60%的数据。DeepWalk也是可扩展的，它是一个在线学习算法，可以不断生成新的结果，并且可以并行计算。这些优秀特性使它适合于多类型的真实应用场景，图分类和异常检测。

Introduction

在图结构的数据集中，很多时候表示图的邻接矩阵都是稀疏的，即很多位置都是0。稀疏矩阵是一把双刃剑，虽然可以被离散类的算法所利用[pass]，但却不利用机器学习算法。所以作者将自然语言处理上大放异彩的无监督学习—Word2Vec的思想应用到图结构上。

图中的不同节点之间可能有相似性，不同节点也可以属于同一个社群，这些都是节点的潜在特征。DeepWalk正是利用节点的随机游走序列将节点的潜在特征编码到低维空间中。

为了验证模型在真实数据集上的表现，我们在具有多标签的大规模异质图上进行分类任务，图节点间的连接不满足传统的数据集样本之间独立同分布的假设，为了解决这个问题，一般使用近似推理。Deep Walk则跳出这些传统的方法，直接学习与标签无关的知识表示，这样模型不被样本标签所影响，进而生成的模型就能用于下游的诸多不同任务。

PROBLEM DEFINITION

首先，我们将问题定义为对一个社交网络图数据进行分类任务，定义变量如下。

$G = (V,E): V是图的结点，E是结点之间的边，也就是图的邻接矩阵的元素 $
$E \subseteq (E,E): E也就是图的邻接矩阵的元素 $
$G_L=(V,E,X,Y): 这是一个标注好的网络$
- $\in \mathbb{R}^{|V| \times S}即一个V行，S列的实数矩阵，每行表示某个结点的特征$
- $\in \mathbb{R}^{|V| \times |y|}，y是某个节点的标签$

传统的方法总是试图找到一个在 $X$ 和 $Y$ 之间的映射，Deep Walk则是利用节点的嵌入向量去分析。

事实上，该问题不是一个新的问题，对于将图中节点的信息表示出来并进行分析。在过去的文献中，这被称为关系分类或集体分类。有用无向马尔科夫链进行推理、迭代近似推理算法（迭代分类算法—吉布斯采样、label relaxation）计算标签给定网络结构的后验概率分布。

我们提出的Deep Walk是一种无监督方法，不考虑节点标签的影响。这种将结构表示和标签相关的任务分离可以带来一些显而易见的好处：

尽可能减少在迭代计算中的级联错误的发送
可以被用于下游的诸多任务

我们的目标：学习获得 $X_E \in \mathbb{R}^{|V| \times d}$ ，其中 $d$ 是嵌入向量的维度。这个低维的嵌入向量是分布式的，意味着向量的各个维度都是不为0的

LEARNING SOCIAL REPRESENTATIONS

我们希望模型可以具有如下特征：

适应性：真实世界中的图结构是不断变化，新的变化不应该再重复全图的训练，只需要局部训练即可
反应社群的聚类信息：原图中相近的节点，在嵌入后其向量依然相近
嵌入向量低维度：当图中有标签的数据节点是稀疏时，低维度的模型总体表现更好，在收敛和推理上更快。低维度嵌入有助于防止过拟合
连续：向量每个维度都是一个连续的实数，这样可以在分类任务中提供一个平滑的决策边界。

Random Walks

随机游走序列：一个醉汉从图中的任意一个点向其他相邻节点前进，走过的节点序列即为随机游走序列。
在这里插入图片描述

定义从节点 $V_i$ 出发的随机游走序列 $W_{v_i}$ ，其节点为 $W_{v_i}^1,W_{v_i}^2,...,W_{v_i}^k$ 。 $W_{v_i}^{k+1}$ 是节点 $v_k$ 周围的一个随机邻居。

随机游走已被应用于内容推荐和社区检测领域中的各种相似性度量问题。通过该方法将离得近且容易走动（或连通）的节点聚集。随机游走也是输出敏感类算法（至少要遍历一遍全图）的基础，但却可以以输入图大小相匹配的时间计算局部社群结构信息。

两个优点：

随机游走是局部游走，并不是全局采样，即有一个最大长度。局部采样是容易并行计算，利用多个线程、进程或是计算机可以同时在不同节点开始随机游走。
随机游走序列可以反映图中一些细微的变化，这使得图结构变化时不需要全局重新计算，可以用新的随机游走序列迭代更新模型

Connection: Power laws

如果连通图中节点的度的分布遵循幂律分布（二八定律），例如无标度网络：网络中少数称之为Hub点的节点拥有极其多的连接，而大多数节点只有很少量的连接。

我们发现在随机游走序列中出现的节点也遵循幂律分布，少数节点占据了整个网络中的大部分连边，而多数节点的连边数量很少，可以认为这些节点是非常重要的。

在自然语言场景中，单词的分布也是遵循幂律分布，自然语言中的知识很好解释了这一现象。
在这里插入图片描述

上图利用真实世界的两个数据集进一步展示了这一现象，左图是YouTube的图数据集，纵轴是不同的节点数，横轴是同一节点在不同的随机游走序列中出现的次数，可以看出只有10数量级的节点出现了 $10^3$ 次以上。有图则是维基百科的文章名称的单词情况。

再次发现，本文的核心贡献之一是将自然语言处理的思想运用到了图分析上。

Language Modeling

语言模型是自然语言处理领域中一个非常重要的研究方向。简单地说，语言模型就是用来计算一个句子的概率的模型，也就是判断一句话是否是人话的概率？

例如： $\\ 学习爱我$ ，则是第一句话更通顺，语言模型也叫做通顺度模型。

正式的话说就是去估计一串特定的单词序列出现在语料库（corpus）中的似然概率（likelihood）。在图中，将单词类别节点即可。我们求解的目标如下：

$Pr(v_i|(v_1,v_2,...,v_{i-1}))$

但是我们希望利用随机游走生成的Embedding。则设置一个节点到其对应的Embedding的函数。其输入是全部节点，输出是全部节点的Embedding。

$\phi: v \in V \mapsto \mathbb{R}^{|V| \times d}$

问题转换为：

$Pr(v_i|(\phi(v_1),\phi(v_2),...,\phi(v_{i-1})))$

按这个公式求解是不可行的，这样的方法存在两个致命的缺陷：

參数空间过大：条件概率P(wn|w1,w2,…,wn-1)的可能性太多，无法估算，不可能有用；
数据稀疏严重：对于非常多词对的组合，在语料库中都没有出现，依据最大似然估计得到的概率将会是0。

近期语言模型的研究中，从相反的方向看待预测问题：

CBOW：模型假设句子中每个词的选取都由相邻的词决定，即用上下文去预测中心词。
Skip—Gram：假设句子中的每个词都决定了相邻词的选取，即用中心词去预测周围词。对于Skip—gram，周围词可以是中心词的左边或右边，顺序无关的

求解公式转换如下：

$\ v i ∣ Φ ( v i ) ) \underset{\Phi}{\operatorname{minimize}} \quad-\log \operatorname{Pr}\left(\left\{v_{i-w}, \cdots, v_{i+w}\right\} \backslash v_{i} \mid \Phi\left(v_{i}\right)\right)$

用第i个节点的Embedding去预测上下个 $w$ 个节点（公式中的**\**是除去的意思）。想要预测结果更精确，概率最大，即概率的负数最小。
在这里插入图片描述

最初初始化一个 $\phi: v \in V \mapsto \mathbb{R}^{|V| \times d}$ ，朝着目标不断迭代优化 $\phi$ 。

这里省略了一些模型的实现细节，即怎样求解这个最优化问题，模型的结构具体是什么？不要着急，这在下一部分method里面介绍

总结：DeepWalk 能将每个节点编码为一个低维、连续、稠密的向量，其包含着节点在原图的结构、连接、社群特征。虽然不包含类别信息，但可用于预测类别信息。

METHOD

这节主要介绍Deep Walk算法的核心组件实现和几个变种或技巧

正如语言模型输入需要有语料库和词语，DeepWalk将随机游走序列作为语料库，将图中节点作为词汇

Algorithm: DeepWalk

算法整体上分为两个模块：

随机游走序列生成器
参数迭代更新器

随机游走序列生成器：从图 $G$ 中随机选择一个节点 $v_i$ 作为游走序列 $W_{v_i}$ 的起始节点**。每次随机选择当前节点的相邻节点作为下一个**。随机游走序列也可以传送回起始节点，但初步试验发现这样做并没有显著提升。下图是原文的伪代码。
在这里插入图片描述

# function to generate random walk sequences of nodes
def get_randomwalk(node, path_length):'''node：起始节点path_length：游走序列长度'''random_walk = [node]for i in range(path_length-1):temp = list(G.neighbors(node))temp = list(set(temp) - set(random_walk))    if len(temp) == 0:break# 随机返回temp中的一个结点random_node = random.choice(temp)random_walk.append(random_node)node = random_nodereturn random_walk

SkipGram

在这里插入图片描述
SkipGram是一种语言模型，旨在利用中心词去预测上下文单词，它能反映词和词的共现关系，即两个词同时出现的概率。即使句子中出现在窗口w中的单词共现概率最大化。

它利用独立假设来近似方程中的条件概率，即将各个节点看做是独立的，将左侧的方程通过独立假设变为右侧的连乘形式，对于单个Pr的计算如下：

将 $v_i$ 的Embedding和 $v_j$ 的Embedding做向量的数量积。

$\ v i ∣ Φ ( v i ) ) = ∏ j = i − w j ≠ i i + w Pr ⁡ ( v j ∣ Φ ( v i ) ) \operatorname{Pr}\left(\left\{v_{i-w}, \cdots, v_{i+w}\right\} \backslash v_{i} \mid \Phi\left(v_{i}\right)\right)=\prod_{\substack{j=i-w \\ j \neq i}}^{i+w} \operatorname{Pr}\left(v_{j} \mid \Phi\left(v_{i}\right)\right)$

这里的Skip-Gram具体实现的细节是借助Word2vec论文提出的方法。Word2Vec作为一个自然语言处理的模型，其训练样本来自语料库。

我们从语料库中抽取一个句子，选取一个长度为 2c+1（目标词前后各选 c 个词）的滑动窗口，将滑动窗口由左至右滑动，每移动一次，窗口中的词组就形成了一个训练样本。根据 Skip-gram 模型的理念，中心词决定了它的相邻词，我们就可以根据这个训练样本定义出 Word2vec 模型的输入和输出，输入是样本的中心词，输出是所有的相邻词。

这里我们选取了“Embedding 技术对深度学习推荐系统的重要性”作为句子样本。首先，我们对它进行分词、去除停用词的过程，生成词序列，再选取大小为 3 的滑动窗口从头到尾依次滑动生成训练样本，然后我们把中心词当输入，边缘词做输出，就得到了训练 Word2vec 模型可用的训练样本。

在这里插入图片描述
Word2Vec的结构本质上是一个三层的神经网络

它的输入层和输出层的维度都是 V，这个 V 其实就是语料库词典的大小。假设语料库一共使用了 10000 个词，那么 V 就等于 10000。根据图 4 生成的训练样本，这里的输入向量自然就是由输入词转换而来的 One-hot 编码向量，输出向量则是由多个输出词转换而来的 Multi-hot 编码向量，显然，基于 Skip-gram 框架的 Word2vec 模型解决的是一个多分类问题。

隐层的维度是 N，N 的选择就需要一定的调参能力了，我们需要对模型的效果和模型的复杂度进行权衡，来决定最后 N 的取值，并且最终每个词的 Embedding 向量维度也由 N 来决定。

需要注意的是，隐层神经元是没有激活函数的，或者说采用了输入即输出的恒等函数作为激活函数，而输出层神经元采用了 softmax 作为激活函数。
$\operatorname{Softmax}\left(z_{i}\right)=\frac{e^{z_{i}}}{\sum_{c=1}^{C} e^{z_{c}}}$

Hierarchical Softmax

给定节点 $v_j$ ，我们想最大化其窗口范围内出现的节点的概率。在Softmax计算分母partition function时，对于图的节点数数量级的指数运算 $\sum_{c=1}^{C} e^{z_{c}}$ ，需要消耗极大的算力，所以采用了分层（Hierarchical）Softmax。

这样计算在得到在 $v_i$ 条件下，需要找出其周围窗口范围内出现概率最大的节点的概率就变为

$\operatorname{Pr}\left(u_{k} \mid \Phi\left(v_{j}\right)\right)=\prod_{l=1}^{\lceil\log |V|\rceil} \operatorname{Pr}\left(b_{l} \mid \Phi\left(v_{j}\right)\right)$

计算 $\operatorname{Pr}\left(b_{l} \mid \Phi\left(v_{j}\right)\right)$ 则需要以 $b_l$ 的父节点构建一个二分类器，以Logistic为例，其参数维度与Embedding一致。这里用 $\Phi(v_{j})$ 表示节点Embedding，以 $\Psi(b_{l})$ 表示分类器的参数。所以整个算法一共是两套参数，最后将分类器的结果输入Sigmoid函数

$\operatorname{Pr}\left(b_{l} \mid \Phi\left(v_{j}\right)=1 /\left(1+e^{-\Phi\left(v_{j}\right) \cdot \Psi\left(b_{l}\right)}\right)\right.$

在这里插入图片描述

更好的方法是以节点出现的频率构造哈夫曼树。

ReadPaper十问

论文试图解决什么问题？

图结构类型的数据中，结点在图中的连接关系很难被表示出来，更难以被传统的统计机器学习算法所利用。该论文主要将节点在图中的连接关系用一种容易被机器学习算法所使用的方法表示出来

是否是一个新的问题？

该问题不是一个新的问题，对于将图中节点的信息表示出来并进行分析。在过去的文献中，这被称为关系分类或集体分类。有用无向马尔科夫链进行推理、迭代近似推理算法（迭代分类算法—吉布斯采样、label relaxation）计算标签给定网络结构的后验概率分布。但将深度学习（无监督学习）的思想引入到图结点的分析中是首次