今天学习的是微软的一篇论文《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
- 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.
- 《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》
