Metapath2vec的前世今生

作者: Jarkata | 来源:发表于2021-08-11 17:49 被阅读0次

一、背景以及目的

最近看到的一些文章会提到Metapath2vec。于是乎抽了点时间整理了一下从word2vec方法发展到metapath2vec的路径。比较单纯的算是知识总结。本文尽量阐述思想，不过度使用公式表达。

本文中可能会涉及到的比较重要的知识，及其出处：

word2vec: Efficient Estimation of Word Representations in Vector Space

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

word2vec: word2vec Parameter Learning Explained

论文地址：https://arxiv.org/abs/1411.2738

Random walk：Random Walk: A Modern Introduction

书籍地址：http://www.math.uchicago.edu/~lawler/srwbook.pdf

Deepwalk：DeepWalk: Online Learning of Social Representations

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

node2vec：node2vec: Scalable Feature Learning for Networks

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

综述：LEARNING REPRESENTATIONS OF GRAPH DATA: A SURVEY

论文地址：https://arxiv.org/abs/1906.02989v2

二、embedding

在深度学习的应用过程中，Embedding 这样一种将离散变量转变为连续向量的方式为神经网络在各方面的应用带来了极大的扩展。该技术目前主要有两种应用，NLP 中常用的 word embedding 以及用于类别数据的 entity embedding。这一章节中，我们所有的探讨都围绕以下两个问题：

什么是 neural network embedding？
我们为什么需要使用 neural network embedding？

Embedding和One Hot编码

上面说了，Embedding 是一个将离散变量转为连续向量表示的一个方式。在神经网络中，embedding是非常有用的，因为它不光可以减少离散变量的空间维数，同时还可以有意义的表示该变量。

我们可以总结一下，embedding 有以下 3 个主要目的：

在embedding空间中查找最近邻，这可以用于推荐
作为监督性学习任务的输入
用于可视化不同离散变量之间的关系

要了解 embedding 的优点，我们可以对应 One-hot 编码来观察。One-hot 编码是一种最普通常见的表示离散数据的表示，首先我们计算出需要表示的离散或类别变量的总个数 N，然后对于每个变量，我们就可以用 N-1 个 0 和单个 1 组成的 vector 来表示每个类别。这样做有两个很明显的缺点：

对于具有非常多类型的类别变量，变换后的向量维数过于巨大，且过于稀疏。
映射之间完全独立，并不能表示出不同类别之间的关系。

因此，考虑到这两个问题，表示类别变量的理想解决方案则是我们是否可以通过较少的维度表示出每个类别，并且还可以一定的表现出不同类别变量之间的关系，这也就是embedding 出现的目的。而为了更好的表示类别实体，我们还可以是用一个 embedding neural network 和 supervised 任务来进行学习训练，以找到最适合的表示以及挖掘其内在联系。

三、word2vec初探

neural network embedding中最早的应用之一就是word2vec。

3.1 什么是word2vec

Word2Vec是从大量文本语料中以无监督的方式学习语义知识的一种模型，它被大量地用在自然语言处理（NLP）中。那么它是如何帮助我们做自然语言处理呢？Word2Vec其实就是通过学习文本来用词向量的方式表征词的语义信息，即通过一个嵌入空间使得语义上相似的单词在该空间内距离很近。Embedding其实就是一个映射，将单词从原先所属的空间映射到新的多维空间中，也就是把原先词所在空间嵌入到一个新的空间中去。

举个例子：
有四个词：man, woman, king, queen.我们通常是希望这四个词的embedding结果有相近的（距离）关系。man和woman的距离比man和queen的距离小，类似地，man和king的距离与woman和queen的距离相差无几，但比man和queen的距离以及woman和king的距离更小。

3.2 skip-gram和CBOW

Word2Vec模型中，主要有Skip-Gram和CBOW两种模型，从直观上理解，Skip-Gram是给定input word来预测上下文。而CBOW是给定上下文，来预测input word。如下图所示。

下图表达的是CBOW的网络结构，这里是输入是多个单词，一般是求和然后平均再进行计算，最终的损失函数保持不变。

下图表示skip-gram的网络结构，输入一个词，预测周边的词。

3.3 负采样(negative sampling)

正如我们所看到的，如果想要计算相关的模型，对于我们来说，计算代价是很大的。因此有了hierarchical softmax和negative sampling两个方法。这里稍微提一下hierarchical softmax这个方法，其本质是将一个N分类问题，通过建立树模型，变成一个log(N)次二分类问题。今天的重点在negative sampling。

负采样的思想更简单直接：in order to deal with the difficulty of having too many output vectors that need to be updated per iteration, we only update a sample of them.

这就是此思想最核心的部分，它的实现过程则是如下面的例子：

当训练样本 ( input word: "fox"，output word: "quick") 来训练我们的神经网络时，“ fox”和“quick”都是经过one-hot编码的。如果vocabulary大小为10000时，在输出层，我们期望对应“quick”单词的那个神经元结点输出1，其余9999个都应该输出0。这9999个我们期望输出为0的神经元结点所对应的单词我们称为“negative” word。使用负采样时，我们将随机选择一小部分的negative words（比如选5个negative words）来更新对应的权重。我们也会对我们的“positive” word进行权重更新（在我们上面的例子中，这个单词指的是”quick“）。

下面请出今天的一号主角，负采样目标函数表达式：

因此，这个目标函数可以理解为两方面的限制：

目标词为1
“负”词为0，但是负采样每次只考虑部分“负”词的，而非全量。

四、从word2vec到node2vec

word2vec是将词变成向量，顾名思义，node2vec其实就是将复杂网络中的节点变成向量。其核心思想为：生成随机游走，对随机游走采样得到（节点，上下文）的组合，然后用处理词向量的方法对这样的组合建模得到网络节点的表示。

Deepwalk和node2vec的思想是高度一致的。相比于deepwalk，node2vec在生成随机游走过程中做了一些创新。这里我们不对两者进行深入比较，但由此提出一个结论，也请出今天的二号主角，这一类编码方式的核心结构：我个人把它看做是“上、下”结构

上：想尽一切办法，在你的网络中进行游走，并采集成序，具体什么游走策略取决于你想采集到什么信息。

下：将采集好的序当作文本，后续与处理词向量的方法相似。

下面以node2vec为例，简单介绍一下这个过程。

4.1 采序

采序的目的很单纯：

同一个社区内的节点表示相似。
拥有类似结构特征的节点表示相似。

当然，你采序的思想反映了你希望获取到什么样的信息。论文原文中提到关于广度优先或者深度优先的采序方式在本质上就表达了对不同累心信息的重视。BFS倾向于在初始节点的周围游走，可以反映出一个节点的邻居的微观特性；而DFS一般会跑的离初始节点越来越远，可以反映出一个节点邻居的宏观特性。因此！因此！因此！采序策略是直接反应操作者对哪部分信息更加重视！（二号主角再度出现）

node2vec原文中提出的随机游走策略，实际上就是综合BFS与DFS的策略。下面我们细细品一哈。

上图表示我们刚刚从已经采集了t到v，那么下一个临幸的对象应该是谁？原文作者，给出了以下的转移概率：

释一下这个分布：

如果t与x相等，那么采样x的概率为1/p
如果t与x相连，那么采样x的概率为1；
如果t与x不相连，那么采样x的概率为1/q

参数p、q的意义分别如下：
返回概率p：

如果 p>max(q,1)，那么采样会尽量不往回走，对应上图的情况，就是下一个节点不太可能是上一个访问的节点t。
如果p<max(q,1)，那么采样会更倾向于返回上一个节点，这样就会一直在起始点周围某些节点来回转来转去。

出入参数q：

如果q>1，那么游走会倾向于在起始点周围的节点之间跑，可以反映出一个节点的BFS特性。
如果q<1，那么游走会倾向于往远处跑，反映出DFS特性。

当p=1，q=1时，游走方式就等同于DeepWalk中的随机游走。

再一次，采序策略是直接反应操作者对哪部分信息更加重视！（二号主角再度出现）！

4.2 训练

这部分我们只挑重点的说，原文作者通过扩展skipgram，定义了目标函数：

通过条件独立（假设观察邻域节点的可能性独立于观察给定顶点的任何其他邻域节点的特征表示，以此来分解这种条件概率）与特征空间对称（特征空间中，两个顶点之间的影响是对称的），将目标函数简化为：

其中，对于每一个顶点，有

由于计算代价高，由此引入负采样进行计算。

上图中是原文中对

N_S(u)

的解释。
再一次，采序策略是直接反应操作者对哪部分信息更加重视！（二号主角再度出现）！

五、metapath2vec来了

到此，我们已经基本了解到了embedding方法中，这一类方法的结构特点（所谓“上、下”）。但是之前接触的方法均是处理同质网络的方法，而metapath2vec恰恰是可以处理异质网络的一个方法。

Metapath2vec是Yuxiao Dong等于2017年提出的一种用于异构信息网络（Heterogeneous Information Network, HIN）的顶点嵌入方法。metapath2vec使用基于meta-path的random walks来构建每个顶点的异构邻域，然后用Skip-Gram模型来完成顶点的嵌入。在metapath2vec的基础上，作者还提出了metapath2vec++来同时实现异构网络中的结构和语义关联的建模。

这里说说metapath的贡献：