图表示学习-图嵌入 DeepWalk

1 图嵌入

目标：将节点 (node) 映射为 d 维的实向量

为什么要将节点映射为 d 维的实向量（嵌入到 d 维的空间）？

为了将节点进行数学表示，以度量节点间的相似度，有了节点对应的向量，才可以进行节点分类、连接预测等任务（为下游各种任务做准备）

2 随机游走-Random walks

算法的目标：将节点编码为向量，使得节点所表示的 d 维向量间尽可能的相似

• 编码器 ENC(v)：将节点映射为向量（本文中为 DeepWalk）

• 相似度函数：$similarity(v_1,v_2)$

• 解码器 DEC：根据两个节点向量计算其相似度

3 DeepWalk

论文地址：https://arxiv.org/pdf/1403.6652.pdf

由于图的节点往往非常的多，经过 one-hot 编码之后得到的节点向量往往非常地大，且向量每个元素的值为 0 和 1。通过神经网络训练得到的节点向量是低维的、元素值是实数（连续值），且可进行相似度的度量，可以反应节点间的关系

随机得到游走序列，将随机游走序列视为句子（中心词+上下文），使用 Skip-gram 来训练节点向量!

使用 Hierarchical Softmax 计算输出的每个节点的概率

3.1 Hierarchical Softmax

3.1.1 哈夫曼树

• 带权路径长度最短的二叉树

• 可以使用哈夫曼编码

  • 频率相关：节点出现频率越高，其越靠近根节点

  • 唯一编码、且编码长度减小（压缩编码）

3.1.2 Logistic Regression

$$y=Sigmoid(wx+b)$$

LR 是传统线性回归 $y=wx+b$ 与 $Sigmoid$ 变换结合，将连续值转化为0到1之间的类概率值，并设定分类阈值如 0.5，来完成二分类任务

3.1.3 Softmax 回归

神经网络的多分类，最基本的是使用Softmax回归

但是 Softmax 回归需要构建一个每个词的全连接层，即需要对词表中的每个词均计算一遍输出值并归一化，再找到输出概率最大的词。当词表非常大的时候，Softmax 回归将会非常耗时

传统 ML 中的多分类：用二分类解决多分类问题，这种方法要训练多个模型，对于神经网络这种庞大参数的模型来说无疑是行不通的

用二分类解决多分类问题：OvR (one versus rest)、OvO (one versus one)

OvO一对一：将 n 个类别两两配对，产生$\frac{n\ast (n-1)}{2}$个二分类任务进行训练，最终把预测出来次数最多的类别作为最终的分类类别

OvR一对其他：每次将一个类作为正例，别的类作为反例，共训练 n 个分类器。预测时，用 n 个分类器预测，若只得到一个预测值是正例，则取此为最终预测类别；若多个分类器得到正例，则对比它们的置信度（如 LR 中得到的类概率值，来比较它们谁最大）

3.1.4 Hierarchical Softmax

分层 Softmax 如图，构建一颗二叉树，其中每个叶子节点对应一个词，非叶子结点是一个 LR 分类器，LR 在这里的应用就是判断在当前节点要走左子树还是右子树，其输出的值在当前节点往左走或右走的概率。

)]

由于此树从根节点的分类器到叶子节点的编码是唯一的（路径是唯一的），路径上每个 LR 预测概率之积，就可以视为在当前输入词的词向量下，得到的输出周围词（skip-gram根据中心词预测上下文的词）的词向量条件概率

分层 Softmax 比 Softmax 牛的地方：设窗口为2，训练的每轮迭代，Softmax 都得把词表遍历一遍，找到预测概率最大的俩词，而分层 Softmax 运行的次数是路径长度之和（从根节点到叶子节点经过的节点数之和），分层Softmax 运行的时间复杂度会大大减小。

3.2 模型训练

更新两套权重

• n 个节点的 v 维节点向量

• n-1 个 LR，每个 LR 的输入特征向量的维度是 v

为什么是 n-1 个 LR，因为二叉树性质 $n_0=n_2-1$，n 个节点对应其叶子节点，所以飞叶子节点的个数即 LR 的个数是 n-1