图神经网络-DeepWalk

本文主要是介绍图神经网络-DeepWalk，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

论文地址：https://arxiv.org/pdf/1403.6652.pdf
发表会议：KDD2014

这篇论文是基于embedding的同质图网络节点表示学习的开山之作。

文章目录

- - 目的
  - 动机
  - 方法
  - 实验
  - 不足

目的

给定一个图，返回节点的embedding表示，节点的embedding表示嵌入了图的结构信息。

动机

图通常是很大的，直接对全图进行表示学习是不现实的。所以作者借鉴了random walk的思想。random walk是一种在图上进行随机游走的算法，即从一个节点走到它的任意邻居节点的概率是相同的。通过若干随机游走序列，就可以表示出整张图的结构信息。作者采用random walk的思想有两点原因：（1）random walk可以并行工作，即可以同时从图中不同节点进行游走，这样就可以在很快的时间内游走完整张图。（2）随机游走只需要图的局部结构，这样当图的一部分变化时，可以很快地去学习新的表示，即对动态图具有很好的适应性。

那么如何利用random walk来学习节点的表示呢？在自然语言处理中，学习单词的嵌入表示时采用的方法是基于上下文预测中间词（CBOW)，或基于中间词预测上下文（skip-gram）。无论哪种方法，都是基于一种概率模型的方法来学习单词的表示。而random walk得到的节点也是一个序列，所以作者就想把自然语言处理中的单词表示方法引用到图的节点表示上。为了更具有说服性，作者对比了文本中的单词出现频数和在图中随机游走节点的出现频数，发现它们都遵循幂率(power law)。

幂率（power law）：
所谓幂律，是说节点具有的连线数(度）和这样的节点数目乘积是一个定值，或者说，出现连接数为k的概率 p(k)，反比于k的n次方。其中，n称为幂数，它是很接近于2的一个常数。比如有10000个连线的大节点有10个，有1000个连线的中节点有100个，100个连线的小节点有1000个……，即度越大的节点越少，在对数坐标上画出来会得到一条斜向下的直线。一个现实的例子是：在绝大多数网站的连接数很少的情况下，却有极少数网站拥有高于普通网站百倍、千倍甚至万倍的连接数。统计物理学家习惯于把服从幂次分布的现象称为无尺度现象(scale-free)。
此外，论文中也提到了Zipf’s law，它和幂律的性质很像。

作者发现，和图中节点度和节点数的关系一样，在图中随机游走节点出现的频数也遵循幂律，即随机游走访问到某个节点的频数和具有这样频数的节点数目乘积是一个定值，换句话说，频数越大，这样的节点越少。这和文本中单词的出现频数一样，在文本中出现频数越高的单词数量越少，即大部分单词出现的频数很小，而出现频数较高的单词也仅有一些副词等。

上述思想可以用下图表示：
在这里插入图片描述
左图是random walk中节点出现频数（横坐标）和出现此频数的节点的数量（纵坐标）图。右图是文本中单词出现频数（横坐标）和出现此频数的单词的数量（纵坐标）。两者的相似性提供了更加具有说服力的理由，使得deepwalk可以借鉴自然语言处理中用概率建模节点表示的方法。

方法

首先模仿skip-gram，通过给定的上下文预测中间词，使得中间词的条件概率最大。那么在deepwalk中，首先根据random walk得到节点序列，然后最大化序列中某节点周围节点出现的概率（最小化负对数损失）：
在这里插入图片描述
而skip-gram是对窗口内的每一对单词最大化条件概率的，它去掉了单词序列顺序的限制，即不考虑单词排列的顺序。所以deepwalk也采用最大化random序列中每一对节点的条件概率： $Pr(u_k|\Phi(v_j))$ 。这会产生一个问题，即如果利用softmax，需要计算的标签概率数大小等于|V|,即图中节点的个数，时间复杂度太高。于是再根据skip-gram的改进算法，利用Hierarchical Softmax来计算概率，把图中节点做为二叉树中的叶子结点，这样计算 $Pr(u_k|\Phi(v_j))$ 就转化为计算从根节点到目标叶子结点路径的概率：
在这里插入图片描述
这里每一个 $Pr(b_l|\Phi(v_j))$ 都只需一个二分类器来计算。于是最终的时间复杂度从O(|V|)降到了O(log|V|)。Hierarchical Softmax如下图所示：

整个算法流程如下所示：
在这里插入图片描述
模型的输入是窗口大小 $w$ ，embedding维度 $d$ ，在每个顶点进行随机游走的次数 $\gamma$ ，随机游走的步长 $t$ 。输出是每个节点的表示 $\Phi$ 。

首先从均匀分布中采样每个节点的初始表示 $\Phi$ 。
对图中节点构造一个二叉树 $T$ 。
开始外层循环，即共进行 $\gamma$ 次随机游走。
$\qquad$ 每次循环首先打乱所有节点的顺序（便于模型更快收敛）
$\qquad$ 对于图中每个节点 $v_i$
$\qquad \qquad$ 从 $v_i$ 出发进行随机游走得到节点序列 $W_{v_i}$
$\qquad \qquad$ 根据 $W_{v_i}$ ， $w$ ， $\Phi$ 来进行skip-gram算法，来更新节点表示 $\Phi$ 。

其中skip-gram算法如下：
在这里插入图片描述
输入是窗口大小 $w$ ，从 $v_i$ 出发进行随机游走得到节点序列 $W_{v_i}$ ，当前节点表示 $\Phi$ 。目的是更新节点的表示。

对于节点序列 $W_{v_i}$ 中的每个节点 $v_j$
$\qquad$ 对于 $v_j$ 上下文窗口大小w内的每个节点 $u_k$
$\qquad$ $\qquad$ 根据Hierarchical Softmax来计算损失函数： $J(\Phi)=-logPr(u_k|\Phi(v_j))$
$\qquad$ $\qquad$ 梯度下降更新节点表示 $\Phi=\Phi-\alpha*\frac{\partial J}{\partial \Phi}$