【PaperReading】metapath2vec: Scalable Representation Learning for Heterogeneous Networks
metapath2vec: Scalable Representation Learning for Heterogeneous Networks
-
算法速览
-
摘要泛读
-
问题定义
-
Metapath2vec
-
- 1. 异质skip-gram
- 2. 元路径randomwalk
- 3. metapath2vec++
-
实验
-
相关工作
-
结论
-
算法意义
-
基于Metapath2vec的节点表示学习
-
相关资料
算法速览
论文地址：https://dl.acm.org/doi/pdf/10.1145/3097983.3098036
会议： KDD 2017
论文结构：
Metapath2vec是一种用于学习节点嵌入 （node embedding）的图表示学习算法 ，旨在处理异构信息网络 （heterogeneous information networks）。该算法通过将异构信息网络中的节点序列转换为连续的向量表示，以捕捉节点之间的语义关系和相似性 。
Metapath2vec算法的核心思想是利用元路径 （metapath）来定义节点之间的路径。元路径是一种定义在异构信息网络上的路径模式，描述了节点之间的结构关系。例如，在一个包含用户、商品和标签的电子商务网络中，可以定义元路径"User-Item-User"来表示用户之间通过商品的交互行为进行连接。Metapath2vec算法通过遍历这些元路径生成的路径，并利用skip-gram模型进行训练，学习节点的向量表示。
下面是Metapath2vec算法的主要步骤：
定义元路径：根据具体的异构信息网络，选择合适的元路径来描述节点之间的结构关系。这些元路径需要能够捕捉到节点之间的语义关系。生成路径：根据选择的元路径，从网络中生成路径。可以使用随机游走（random walk）的方法，在网络中以一定的步长和路径长度进行遍历，生成大量的路径样本。构建词汇表：将生成的路径样本作为词汇表的候选项，对于频次低于某个阈值的路径，可以进行过滤以减少噪音。学习节点嵌入：使用skip-gram模型对路径样本进行训练，学习节点的向量表示。Skip-gram模型的目标是根据中心节点预测其周围节点的概率分布。得到节点嵌入：训练完成后，可以得到每个节点的向量表示，这些向量可以用于节点的相似性计算、聚类、分类等任务。
Metapath2vec算法的优点是能够处理异构信息网络，捕捉节点之间的语义关系。它可以应用于推荐系统、社交网络分析、生物信息学等领域，用于发现节点之间的关联和模式。然而，算法的性能受到元路径选择和路径生成策略的影响，需要根据具体的问题和网络特点进行调优和选择。
【metapath2vec】 Scalable Representation Learning for Heterogeneous Networks
摘要泛读
- 强调之前的模型研究的是同质网络，无法更好地表达点和边的多样性
- 基于异质图上的meta-path设计random walk算法
- 基于skip2gram框架和负采样算法完成异质图的学习
- 通过节点分类、聚类、相似性等任务在Aminer和DBIS两个数据集验证了模型的有效性。
问题定义
异质网络的定义：G=(V,E,T)，图中每个节点v和每条边e都有对应边的映射函数\phi(v):V\rightarrow T_V以及\phi(e):E\rightarrow T_E，T_V和T_E分别表示节点和边类型的集合，两个集合满足：|T_V|+|T_E|>2，也就是说节点类型数和边类型数之和大于2，即不止一种节点或者一种边。
可以将异质图表示学习定义为：给定一个异质图G，其任务是学习到所有节点的嵌入表示X\in R^{|V|\times d}，其中d<< |V|，嵌入表示X能够捕捉到不同类型节点的结构和语义关系。
值得注意的是，虽然异质图中存在不同类型的节点，但它们都会被映射到相同的空间，也就是说不同类型的节点的表示向量的维度都为
d。图嵌入前提是保持节点与其邻域(上下文)之间的邻近性，在异质环境中，异质图嵌入模型的核心是定义和建模“节点-邻居”的概念以及优化嵌入模型，以有效地维护多种类型节点和关系的结构和语义 。
Metapath2vec
1. 异质skip-gram
论文首先回忆了word2vec模型及其在同质图中的应用。前面提到的DeepWalk和node2vec模型都是基于skip-gram模型 ，具体来讲是先得到节点的游走序列，然后再将序列输入到skip-gram中以得到每个节点的嵌入表示 。
通常，给定一个网络G=(V,E)，其目标是使网络的局部结构概率最大化 ，即：arg\max_\theta \prod_{v\in V}\prod_{c\in N(v)} p(c|v;\theta)这里的N(v)指节点v的上下文节点 ，这种节点的定义方式有多种，比如DeepWalk中利用随机游走得到上下文节点。p(c|v;\theta)指已知节点v的情况下，上下文节点c存在的概率，这种概率通常用内积+softmax来实现。
为了将异质网络结构引入到skip-gram，metapath2vec提出了异质skip-gram的概念，即在给定节点v的情况下，最大化其异质上下文节点N_t(v)出现的概率：arg\max_{\theta}\sum_{v\in V}\sum_{t\in T_v}\sum_{c_t\in N_t(v)}\log{p(c_t|v;\theta)}这里N_t(v)表示节点v的第t种上下文节点，p(c_t|v;\theta)表示已知节点v的情况下，上下文节点c_t存在的概率，一般来讲，这种概率通常用内积+softmax来实现：
p(c_t|v;\theta)=\frac{e^{X_{c_t}\cdot X_v}}{\sum_{u\in V}e^{X_u\cdot X_v}}与skip-gram中一致，为了解决每次更新时都要对所有节点进行softmax计算的问题，metapath2vec也引入了负采样策略 。给定负样本数M，则优化目标可以表示为：
\log \sigma(X_{c_t}\cdot X_{v})+\sum_{m=1}^M\mathbb{E}_{u^m}\sim P(u)[\log \sigma (-X_{u^m}\cdot X_v)]其中p(u)是负采样中样本的预定义分布，这个更新公式与带负采样的skip-gram公式基本一致。
2. 元路径randomwalk
同DeepWalk和node2vec等类似，metapath2vec也需要得到节点的游走序列，然后使用1中的异质skip-gram模型进行优化。为了得到有效的游走序列，metapath2vec提出了Meta-Path-Based Random Walks ，即元路径随机游走。
最简单的一种想法是和DeepWalk一致，进行随机游走，这样也能得到包含不同类型节点的随机游走序列。然而，一些研究表明，异质随机游走偏向于高度可见的节点类型，即那些占据主导地位的路径数量的节点和集中的节点 。基于这种理念，本文提出了一种基于元路径的随机游走。
具体地，一个meta-path的schema被定义为：V_1\overset{R_1}{\rightarrow} V_2\overset{R_2}{\rightarrow}... V_t\overset{R_t}{\rightarrow} V_{t+1}...\overset{R_{l-1}}{\rightarrow} V_l需要注意的是，元路径中相邻节点的类型是不一样的 ，即V_i和V_{i+1}属于不同类型的节点，R_i表示两个节点间的关系。以下图为例：
上图中，A表示作者节点，P表示论文，O表示作者所属组织，V表示期刊会议。根据上述元路径的定义，可以有以下几种简单的元路径：
- APA：一篇论文中两个作者的合著关系。
0 APVPA：两个作者(A)在同一期刊会议(V)上发表了论文。
与node2vec一致，metapath2vec中也给出了每一步的转移概率 ：
假设当前节点为v_t^i，那么下一个节点v_{i+1}的选择策略为：
- 如果v_t^i与v^{i+1}间存在边，且v^{i+1}的类型与meta-path的schema的定义一致（比如APA中，如果当前为P那么下一节点的类型应该为A），那么v^{i+1}被选中的概率是均等的，也就是1/节点个数。
- 如果v_t^i与v^{i+1}间存在边，但v^{i+1}的类型与meta-path的schema的定义不一致，那么不会选择该节点
- 如果v_t^i与v^{i+1}间不存在边，那么不会选择该节点。
除了上述三点原则以外，元路径还需遵循对称原则，也就是路径中第一个节点V_1和最后一个节点V_l的类型应该一致，即：p(v^{i+1}|v_t^i)=p(v^{i+1}|v_1^i)\text{, if }t=l
基于元路径的随机游走策略确保了不同类型节点之间的语义关系能够被恰当地整合到skip-gram中 。 以下图为例：
在传统的随机游走过程中，从节点CMU过渡到节点a_4上的walker的下一步可以是它周围所有类型的节点，即a_2、a_3、a_5、p_2、p_3和CMU。然而，在meta-path scheme “OAPVPAO”下，下一步选择的节点会偏向于论文节点P。
3. metapath2vec++
metapath2vec中的优化目标为：arg\max_{\theta}\sum_{u\in V}\sum_{t\in T_V}\sum_{c_t\in N_t(v)}\log p(c_t|v;\theta)，其中：p(c_t|v;\theta)=\frac{e^{X_{c_t}\cdot X_v}}{\sum_{u\in V}e^{X_u \cdot X_v}}根据要求，我们需要构造节点的邻居函数N_t(v)(上下文邻居)。从元路径游走策略可知，metapath2vec中N_t(v)是根据meta-path scheme来确定的，然后进行softmax计算时会考虑所有类型的节点，这种方式忽略了softmax中节点的类型信息。换句话说，在进行负采样时，metapath2vec不会区分节点类型，所有类型的节点都有可能被采样到，即上面式子中的v\in V，作者认为这样是不合理的。
为此，作者提出了Heterogeneous negative sampling 的概念，也就是异质负采样，这不同于一般skip-gram中的负采样，这种采样会考虑节点的类型 。具体来说：p(c_t|v;\theta)=\frac{e^{X_{c_t}\cdot X_v}}{\sum_{u_t\in V_t}e^{X_{u_t}\cdot X_v}}即我们在计算节点向量间的内积并进行softmax时，会根据不同类型的节点的上下文c_t进行归一化。简单来讲，如果当前上下文节点类型为P，那么我们只需要将类型为P的节点向量与该上下文节点c_t放到一起来求softmax，而不是metapath2vec中的所有节点。
举个例子，假设序列为[A_1,P_1, V_1, P_2, A_2]，设中心节点为V_1，当前输入的节点为A_1，在metapath2vec中，我们会从所有类型的节点（可以为A，也可以为其他类型）中采样一部分与中心节点求内积再求softmax，而在metapath2vec++中，我们只会选择采样一部分作者类型节点(A)，然后去更新skip-gram中的参数。
因此，metapath2vec++的优化目标可以定义为：\mathcal{O}(X)=\log \sigma (X_{c_t}\cdot X_v)+\sum _{m=1}^M\mathbb{E}_{u_t^m\sim P_t(u_t)}[\log \sigma (-X_{u_t^m}\cdot X_v)]它与matapath2vec的优化目标\log \sigma (X_{c_t}\cdot X_v)+\sum _{m=1}^M\mathbb{E}_{u^m\sim P(u)}[\log \sigma (-X_{u^m}\cdot X_v)]相比，只是采样分布变化了一下，一个专注于所有类型节点 ，一个只考虑与当前节点同类型的节点 。从这里我们也可以看出metapath2vec++被提出的根本原因：之前所有方法都是基于同质图，同质图中所有节点类型都一致，因此进行负采样时不需要额外考虑节点类型，而异质图中节点类型不一致，因此自然而然地就会想到负采样时区分节点类型。
实验
Data ：the AMinter Computer Science(CS) dataset 和 the Database and Information Systems(DBIS) dataset
Baseline ：DeepWalk、LINE、PTE、Spectral Clustering
Patameters :
- The number of walks per node w：1000
- The walk length l：100
- The vector dimension d ： 128 (LINE: 128 for each order)；
- The neighborhood size k：7
- The size of negative samples：5
对于metapath2vec和metapath2vec++，我们还需要指定元路径schemes来引导随机游走 。 我们调查了大多数基于元路径的工作，发现异构学术网络中最常用、最有效使用的元路径方案是“APA”和“APVPA”[12, 25–27]。 请注意，“APA”表示共同作者语义，即传统（同质）协作链接/关系。 “APVPA”代表作者在同一地点发表论文的异构语义。 实证结果还表明，这种简单的元路径方案“APVPA”可以导致节点嵌入，可以推广到不同的异构学术挖掘任务，这表明它适用于学术搜索服务的潜在应用。
我们评估了三种经典异构网络挖掘任务中通过不同方法学习的潜在表示的质量，包括多类节点分类[13]、节点聚类[27]和相似性搜索[26]。 此外，我们还使用 TensorFlow [1] 中的嵌入projector来可视化从异构学术网络中学习到的节点嵌入。
相关工作
网络表示学习可以追溯到潜在因子模型（latent factor models）在网络分析和图挖掘任务中的使用，例如分解模型在推荐系统、节点分类、关系挖掘和角色发现中的应用。 这些丰富的研究重点是分解网络的矩阵/张量格式（例如邻接矩阵），为该网络中的节点或边生成潜在维度特征。 然而，分解大规模矩阵/张量的计算成本通常非常昂贵，并且还存在统计性能缺陷，使其对于解决大型网络中的任务既不实用也不有效。
随着深度学习技术的出现，人们投入了大量精力来设计基于神经网络的表示学习模型。 例如，米科洛夫等提出了 word2vec 框架（一个两层神经网络）来学习自然语言中单词的分布式表示。Perozzi 等人基于 word2vec 构建。 建议节点的“上下文”可以通过它们在随机游走路径中的共现来表示。 形式上，他们将随机游走器放在网络上来记录他们的步行路径，每个路径都由一系列节点组成，这些节点可以被视为文本语料库中单词的“句子”。
最近，为了使节点的邻域多样化，Grover 和 Leskovec 在网络上提出了有偏差的随机游走器（宽度优先和宽度优先搜索过程的混合）以生成节点路径。 生成节点路径后，这两项工作都利用了 word2vec 中的 Skip-gram 架构来对路径中节点之间的结构相关性进行建模。
此外，还提出了几种其他方法来学习网络中的表示。 特别是，为了学习网络嵌入，Tang 等将节点的上下文分解为一阶（朋友）和二阶（朋友的朋友）邻近度，并进一步发展为用于嵌入文本数据的半监督模型 PTE。
我们的工作进一步推动了这个研究方向，通过设计 metapath2vec 和 metapath2vec++ 模型，捕捉具有多种节点类型的大规模网络中展现的异构结构和语义相关性，这些相关性无法被之前的模型处理。我们将这些模型应用于各种网络挖掘任务。
结论
本文提出了异质图嵌入模型metapath2vec和metapath2vec++。具体来讲，首先定义了meta-path scheme及其对应的随机游走策略，该策略能够捕获不同类型节点及关系的结构和语义相关性 。然后，将随机游走序列输入到本文提出的异质skip-gram中以得到所有类型节点的嵌入表示 。
需要注意的是，metapath2vec中skip-gram的负采样策略与同质skip-gram一致，考虑了所有节点；而metapath2vec++中skip-gram在进行负采样时只考虑与上下文节点同类型的节点。
大量实验表明，metapath2vec和metapath2vec++学习的潜在特征表示能够改进各种异质网络挖掘任务，如相似性搜索、节点分类和聚类。
算法意义
- 将random walk + skip2gram的框架拓展到异质图，如何在多种类型的节点之间定义节点的上下文从而产生好的训练预料。
- 基于异质图的随机游走算法表达了不同类型节点之间的语义的结构关联
- 早期研究异质图学习的工作，拓展了关于更多类型的网络的图表示学习研究
基于Metapath2vec的节点表示学习
使用stellargraph和gensim库中的组件实现Metapath2Vec表示学习算法的示例: