《Meta-Path Guided Embedding for Similarity Search in Large-Scale Heterogeneous Information Networks》—论文笔记

这篇论文是韩家炜实验室投稿在2016年KDD的一篇文章,虽然被拒稿了,但是大佬的论文还是非常值得一读的。论文提出了一种在异质信息网络中,基于元路径的同类型节点间的相似性搜索方法ESim,模型接受用户定义(user-defined)的元路径,以此为指导学习节点的隐含表示,然后使用向量的cos相似性度量节点间的相似性。

论文的主要亮点在于其提出了一种有效的基于采样的优化算法,同时论文考虑融合多条不同元路径以求得到更好的实验效果。

1、Introduction

论文简介部分主要是PathSim[1]等相似性搜索算法进行了分析总结,同时指出了一些网络嵌入方法的不足。PathSim算法同样是在异质信息网络中,基于元路径进行相似性搜索,但是它没有深入考虑异质信息网络结构的相似性嵌入。例如,在学术合作网络中,PathSim只能搜索在同一会议上发表了论文的作者的相似性,但是不能搜索不同会议间的相似性。

对于一些网络嵌入方法(LINE、PTE等)基本上是先将异质网络映射到二部或同质网络,然后在进行节点的表示学习,这种做法的计算代价是很高的,同时丢失了一些隐含的语义信息。

论文还指出对于同样的需求,不同人的在网络搜索中会使用不同的语义表述,所以基于用户偏好作为指导的元路径学习节点的特征表示是能够捕获异质网络中更强的语义信息。

2、ESim Framwork

2.1、Preliminaries

论文首先对一些定义给出了详细的说明,包括异质网络、元路径、路径实例和元路径知道的相似性搜索。

元路径

元路径定义为$M=$,表示长度为L的边类型序列,在这里,论文特别指明了边$r_i$的出节点类型应该和$r_{i+1}$的入节点类型一致

子元路径定义为$M_{s,t}=$,其中$1\le{s}\le{t}\le{L}$。

路径实例(path instance)

论文中使用边序列描述路径实例,原因是同一节点对之间的可能有多条边。给定一个HIN图和一条元路径$M=$,任意连接节点$u_1$和$u_{L+1}$的路径$P_{e_1\to{e_L}}=$就是一个服从$M$的路径实例,同时定义$\forall{1\le{i}\le{L},v_i=u_{i+1}}$。

需要注意的是,这里的路径长度$L$和随机游走中的walk length不同,因为相似性搜索只需要度量两两节点之间的相似性,比如$M=$,$L=4$,一个路径实例可以是$a_1p_2v_3p_4a_5$。

2.2、Probabilistic Embedding Model Incorporating Meta-Paths

论文在已有的概率嵌入模型中加入了元路径,并认为共同出现在很多路径实例中的节点应该有相似的embeddings

对于给定元路径$M$和节点$u$,节点$u$的邻接点$v$的条件概率定义为:

其中,$f(u,v,M)=\mu_M+p_m^Tx_u+q_M^Tx_v+x_u^Tx_v=(\mu_M-p_M^Tq_M^T)+(x_u+q_M)^T(x_v+p_M)$

$f$公式中的参数全部通过学习得到,感觉这里写成$f(u,v|M)$更合适。

对于给定的路径实例$P_{e_1\to{e_L}}=,e_2=,…,e_L=>$,可以计算其近似概率为:

这里值得注意的是,在给定路径实例中,其实$v_1=u_2$,即“首尾连接”。

$C(u,i|M)$表示第$i$个节点是$u$的路径实例个数

从公式(2)可以看出,在可以预计算$C(u,i|M)$的前提下,只有$Pr(P_{e_1\to{e_L}}|u_1,M)$是未知的。论文针对该条件概率,给出了两种计算方法:

  • Sequential:假设路径中某一个节点只和其左边或右边的邻居节点有关,因此可以定义:

    需要注意的是,在路径实例的定义中,已经给出了$v_k=u_{k+1}$,子元路径$M_{k,k}$其实就是一条边$r_k$。

  • Pairwise:假设路径中所有节点都是相互关联的,因此可以定义:

实验证明,第二种方法的效果更好一些,因为它考虑了路径实例中当前节点后面的所有节点。

论文采样NCE方法优化计算公式(1)(2),公式推导不再赘述,根据两种不同的计算方法,可以得到两个损失函数:

2.3、Optimization Algorithm

优化算法的整体框架比较简单,其中的一个比较好的优化方式是,不是在每次迭代的时候都遍历每一条路径实例,而是根据路径实例的分布概率抽样一个路径实例的子集合,然后进行梯度下降优化参数。

由前面的假设得知,采样一条路径实例的概率只和$C(u,i|M)$有关,正比于$C(u,i|M)$,算法2采用采用动态规划法递归计算$C(u,i|M)$的值。对于边界情况,如果节点$u$是边$r_L$的下一节点,那么$C(u,L+1|M)=1$。然后对于从L到1的节点,递从后往前递归计算。

在采样一条路径实例时,先是以正比于$C(u_1,1|M)$的概率随机采样开始节点$u_1$,然后以正比于$C(u_i,i|M)$的概率,从$u_i$的邻接点集合$V_i$中,依次采样其它节点,最后返回一条路径实例。

需要注意的是,负采样时,因为负样本路径实例和正样本路径实例是相关的,所以首节点是固定的,但是剩下的其它节点是相互独立的,所以负采样时候,从网络的所有节点$V$中,以正比于$C(u_i,i|M)^\gamma, \forall{i}>1$的概率采样节点。

3、Summary

这篇论文提出了一种针对异质信息网络中同类型节点的相似性搜索框架,比较有创新的地方有三处:首先,论文融合元路径到概率模型中,考虑了两种不同的生成路径实例的概率模型,尤其是第二种,考虑元路径上的所有节点之间的相互作用;其次,论文提供了一种高效的采样算法,基于假设节点的采样概率正比于$C$,通过预计算节点$u_i$在元路径$M$的第$i$位置的路径实例个数$C(u_i,i|M)$,能够高效快速采样得到路径实例;最后,论文提供了一种融合多条元路径学习网络embedding的新思路,可以对不同元路径赋不同的权重,融合多条元路径以达到更好的效果。

整体来说,这篇论文的想法思路还是比较新颖的,但很遗憾被KDD‘16拒稿了,个人感觉是论文的叙述还是有些难理解的,比如对于路径实例的长度L没有给出明确的说明,很容易和随机游走中的walk length产生混淆(也可能是个人理解能力有限……),还有论文也没有详细解释采样概率正比于C的原因,还是会引起疑惑。

写的还不错?那就来个红包吧!
0%