【Embedding】Metapath2vec：异构网络表征

今天学习的是微软的一篇论文《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》，发表于 KDD 2017，目前引用次数超 500 次。

很多网络表征学习主要是针对同构网络的，而本文提出的一种专门用于异构网络表征学习的方法——Metapath2Vec，其能够同时捕捉不同类型节点之间的「结构关系」和「语义关系」。

Metapath2Vec 使用基于元路径的随机游走方法来捕捉节点的异构邻居，然后使用异构 Skip-Gram 模型进行训练，同时建模结构上和语义上相近的节点。

此外，作者还提出了 Metapath2Vec++ 方法，针对每种类型的节点进行单独归一化，即把异构网络分解成不同的同构网络。

最终实验表明，这两种 Metapath2Vec 方法不仅在异构网络挖掘任务中取得了 SOTA 的成绩，而且还能够识别不同网络对象之间的结构和语义关系。

1.Introduction

目前大部分的工作都集中在同构网络中，但真实场景下异构网络才是最常见的。针对同构网络设计的模型很多都没法应用于异构网络，比如说，对于一个学术网络而言：如何高效根据上下文信息表征不同类型的节点？能否用 Deepwalk 或者 Node2Vec 来学习网络中的节点？能否直接将应用于同构网络的 Embedding 模型直接应用于异构网络？

解决诸如此类的挑战，有利于更好的在异构网络中应用多种网络挖掘任务：

传统的方法都是基于结构特征（如元路径 meta-path）来求相似性，类似的方法有 PathSim、PathSelClus、RankClass 等：

但这种方式挖掘出来的元路径（如 “APCPA”）经常会出现相似度为 0 的情况。如果我们能够将 Embedding 的思想应用于异构网络，则不会再出现这种情况。

基于这种观察，作者提出了两个可以应用于异构网络的 Graph Embedding 的算法模型——metapath2vec 以及 metapath2vec++。

2.Metapath2Vec

为了对异构网络节点中的邻居进行建模，metapath2vec 引入了异构 skip-gram 模型。此外，为了捕获异构网络的结构，作者还提出了基于元路径的随机游走策略。

先给出流程图：

2.1 Meta-Path-Based Random Walks

Metapath2vec 同构 metapath 来指导随机游走的节点跳转。给出元路径模式 ：

其中，节点类型间的关系表示：

“APA” 关系表示两位作者（A）在一篇论文（P）上的合著关系；“APVPA” 表示两位作者(A)在同一会议（V）发表过论文(P)。这种元路径有利于异构网络的数据挖掘。

基于元路径模式 ，我们给出转移概率：

其中 ， 表示节点 的邻居中属于 类型的节点集合。

也就是说，游走是在预先设定的 meta-path 的条件上。通常 meta-path 一般用在对称的路径上，第一个节点类型与最后一个节点类型相同，例如 OAPVPAO。

2.2 Heterogeneous skip-gram

对于每个节点 v，根据其不同类型的上下文最大化其上下文：

其中，V 表示网络的节点集合； 表示节点类型的集合； 表示节点 v 的类型为 t 的邻居集合。 表示节点 v 的 Embedding 向量。

考虑负采样的目标函数：

其中， 是负采样中样本的预定义分布；metapath2vec 通过均匀地观察不同类型的节点并绘制(负)节点来维护一个节点频率分布。

相比于考虑负采样的 Skip-gram 的目标函数而言并无本质区别，唯一的区别在于采样的策略上发生了变换。

##2.3 Metapath2Vec++

Metapath2Vec 在计算 Softmax 时不考虑节点的类型。Metapath2Vec++ 在采集负样本时，考虑样本与正样本属于同一个节点类型。也就是「异构负采样 (Heterogeneous negative sampling)」。

考虑条件概率 p 在特定的节点类型 t 上做标准化：

此时，目标函数为：

与 Skip-gram 没有本质区别，但异构网络的「异构」信息不仅仅在采样中体现出来，也在目标函数中被体现出来。

来看下伪代码：

3.Experiment

简单看一下实验。

以 Aminer 数据集为例，“会议”节点节点分类的结果：（百分号为训练的数据集的占比）

“作者”节点分类的结果：

参数敏感性实验：

节点分类结果：

metapath2vec++ 聚类结果的可视化：

4.Conclusion

总结：本文定义了异构网络中表征学习问题，其存在不同类型的节点和边。为了应对异构网络所带来的挑战，作者提出了 Metapath2Vec 和 Metapath2Vec++ 两种算法。Metapath2Vec 首先「基于元路径的引导进行随机游走」并采集到相关序列，该能够捕捉到不同类型节点的关系结构和语义相关性。虽然，作者利用异构 Skip-gram 和异构负采样技术来学习节点的表征。Metapath2Vec++ 算法则是在计算 Softmax 时不考虑节点的类型。最终实验表明，这两种算法在异构网络中取得了不错的成绩。

5.Reference

1. Dong Y, Chawla N V, Swami A. metapath2vec: Scalable representation learning for heterogeneous networks[C]//Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017: 135-144.
2. 《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》