DeepWalk：图表示的在线学习

2021-11-09 本文已影响0人酷酷的群

论文标题：DeepWalk: Online Learning of Social Representations
论文链接：https://arxiv.org/abs/1403.6652
论文来源：KDD 2014

一、概述

本文提出DeepWalk方法，来学习图节点的社会表示（social representation），学习到的表示处于较低维度的连续空间中。DeepWalk采用自然语言处理中的语言模型来建模一系列图上的随机游走节点序列，这些随机游走序列可以看做一种特殊的语言。模型的输入是一张图，输出是节点的隐表示，下图展示了一个例子，可以看到表示空间中线性可分的部分对应于原图根据模块最大化（modularity maximization）得到的划分：

example

二、社会表示的学习

问题陈述

考虑节点分类问题（单分类或者多分类问题）。使用 $G=(V,E)$ 表示图， $V$ 是节点集合， $E$ 是边的集合， $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}|}$ ， $\mathcal{ \\Y}$ 是标签集合。传统的机器学习分类算法是要学习一个假设 $H$ 来将 $X$ 的元素映射到标签集合 $\mathcal{ \\Y}$ 。

本文提出的方法用来捕获网络的拓扑信息。DeepWalk没有混合标签空间作为特征空间的一部分，而是采用无监督的方法来捕捉图的结构信息，忽略标签的分布。DeepWalk的目标是学习隐表示 $X_{E}\in \mathbb{R}^{|V|\times d}$ ， $d$ 是隐表示的维度，学习到的特征向量可以与任何分类算法相结合，即使是简单算法也可以得到好的性能。

我们希望算法学习到的节点表示能够具备以下特性：
①可适应性（adaptability）：真实的网络是一直在变化的，新的社会关系（social relation）的出现不应该要求重复算法的学习过程；
②社区感知（community aware）：隐表示之间的距离应该代表一种度量，用来评估网络相应成员节点之间的相似性，这允许在具有同质性（homophily）的网络中进行泛化；
③低维（low dimensional）：当标注数据稀缺时，低维模型泛化地更好（可能是因为高维具有维度灾难），并且能够加速收敛和推断；
④连续（continuous）：除了提供社区成员的细致入微的视图外，连续表示在社区之间有平滑的决策边界，这允许更具鲁棒性的分类。

随机游走

以节点 $v_i$ 为根节点的随机游走序列记作 $W_{v_{i}}$ ，这是一个依赖随机变量 $W_{v_{i}}^{1},W_{v_{i}}^{2},\cdots ,W_{v_{i}}^{k}$ 的随机过程， $W_{v_{i}}^{k+1}$ 是从节点 $v_k$ 的邻域里随机选择的节点。对于一些问题比如内容推荐（content recommendation）或者社区检测（community detection），随机游走被用来作为一种相似性度量，一些其他输出敏感算法也使用随机游走来计算局部社区结构信息。正是随机游走与局部结构的联系使我们产生了使用一系列随机游走作为基础的工具来捕获社区信息。并且，使用随机游走能够带来两个特性：
①可以并行化，不同的随机游走序列可以同时探索同一图的不同部分；
②算法依靠从短随机游走中获得信息，可以在不需要全局重新计算的情况下适应图结构中的微小变化。

幂律分布

如下图，节点在随机游走序列中出现的频率与自然语言中的词频同样满足幂律分布（power law）：

幂律分布

而语言建模技术解释了这种分布。我们的一个核心想法是应用于语言建模的技术（语言中的符合频率满足幂律分布，而随机游走序列中节点出现的频率也满足）也能够用来建模网络中的社区结构。

语言模型

语言建模的目的是估计特定的词序列出现在语料库中的似然。具体的，给定一个词序列：

$W_{1}^{n}=\left (w_{0},w_{1},\cdots ,w_{n}\right )$

这里 $w_{i}\in \mathcal {V}$ ， $\mathcal {V}$ 是词典，我们希望最大化所有训练语料上的概率 $Pr(w_{n}|w_{0},w_{1},\cdots ,w_{n-1})$ 。

近来，表示学习领域的研究使用神经网络来学习词的表示，这样的做法延伸了语言建模原来的目标（意思是现在不止要建模上面的概率，而且要学习词的表示）。

本文探索了一种语言建模技术的推广，来通过一系列随机游走序列学习网络中节点的表示。这些随机游走可以看做一种使用特殊语言的短句。直接的做法是在给定随机游走中之前节点的情况下估计观测节点 $v_i$ 的似然：

$Pr(v_{i}|(v_{1},v_{2},\cdots ,v_{i-1}))$

我们的目标不只是要学习节点共现的概率分布，同时也要学习一个节点的隐表示，所以我们引入一个映射函数 $\Phi :v\in V\mapsto \mathbb{R}^{|V|\times d}$ ，这个映射函数 $\Phi$ 代表了与图中每个节点 $v$ 所绑定的隐社会表示，实际中我们用一个 $|V|\times d$ 形状的自由参数矩阵来表示 $\Phi$ ，这个矩阵在后面被用作 $X_E$ 。现在，问题变成了估计下列似然：

$Pr(v_{i}|(\Phi (v_{1}),\Phi (v_{2}),\cdots ,\Phi (v_{i-1})))$

然而，随着随机游走序列长度的增加，该目标函数的计算变得不可行。语言模型对于这个问题的解决方案是将这个概率的预测反过来（其实就是指 SkipGram），其实是一种对原有问题的松弛。具体的做法是：
①使用一个词来预测其上下文；
②上下文既包含这个词左边的词也包含右边的词；
③移除了词的顺序限制，也就是说模型需要最大化任何在上下文中出现的词的似然，忽略这些词与该词的偏移。

将上述方法应用到节点表示学习上，要优化的问题就变成了：

$\underset{\Phi }{minimize}\; -log\: Pr\left ( \left \{v_{i-w},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+w}\right \}|\Phi (v_{i})\right )$

解决上述问题能够捕获图结构中节点之间的相似性，具有相似邻域的节点会获得相似的表示。通过结合截断的随机游走与语言模型，可以满足前面提到的需要满足的表示的特性。

三、方法

语言模型的输入只需要语料和词典 $\mathcal {V}$ ，DeepWalk将一系列短的截断随机游走序列作为语料，节点集合作为词典（ $\mathcal{V } =V$ ）。

DeepWalk

DeepWalk算法包括两部分：一个随机游走生成器和一个更新程序。随机游走生成器在图 $G$ 上均匀采样节点 $v_i$ 作为随机游走 $W_{v_{i}}$ 的根节点。一个随机游走每次均匀采样上一个节点的邻域节点，直至达到最大长度 $t$ ，在实验中随机游走的长度是固定的。一个随机游走可以使用restart，也就是一个转移回根节点的转移概率，但是实验表明restart并没有产生性能上的提升。在实验中，我们采用的方式是为每个节点产生 $\gamma$ 个长度为 $t$ 的随机游走。下面的算法展示了DeepWalk的大致过程：

DeepWalk

第3行代表整个过程迭代 $\gamma$ 次，每次为每个节点采样一个随机游走。第4行代表对节点进行随机排列，这不是必须的，但是可以加速随机梯度下降的收敛。对于每个随机游走，使用第7行的SkipGram进行参数的更新。

SkipGram

SkipGram是一种语言模型，它最大化句子中 $w$ 大小的窗口内出现的词的共现概率。下面的算法展示了SkipGram在DeepWalk中的应用：

SkipGram

第3行的概率可以有多种选择的分类器可供使用。如果使用逻辑回归来建模这个概率，那么将会有一个很大数量的标签（ $|V|$ ），可能达到百万级，这就会导致需要大量的计算资源。为了解决上述问题，可以应用Hierarchical Softmax。

Hierarchical Softmax

由于 $|V|$ 是庞大的，所以给定 $u_{k}\in V$ ，计算上面算法第3行的 $Pr(u_{k}|\Phi (v_{j}))$ 是不可行的，采用Hierarchical Softmax方法可以解决这个问题。

Hierarchical Softmax参考链接：Hierarchical Softmax（层次Softmax）

本文中的做法是将节点分配到一个二叉树（算法1里构建的二叉树 $T$ ）上，那么预测问题就变成了最大化二叉树里的一条特定的路径的概率，这样计算这个概率的复杂度将由 $O(|V|)$ 缩减成 $O(log|V|)$ （ $|V|$ 个节点作为叶子节点构建的二叉树深度为 $log|V|$ ）。如果二叉树中到节点 $u_{k}$ 的路径表示为 $b_{0},b_{1},\cdots ,b_{\left \lceil log|V|\right \rceil}$ ，其中 $b_{0}=root,b_{\left \lceil log|V|\right \rceil}=u_{k}$ ，那么有：