Press "Enter" to skip to content

【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

 

 

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》

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。