HIN-基于元路径的相似度计算

转载 2019-11-21 22:29  阅读 24 次 评论 0 条

前面我们介绍了HIN的几个基本概念,其中最重要的是对meta path的理解,我们说meta path是HIN体系的核心构成,是后续各类数据挖掘任务的基础,所以这一节就来讲解meta path是具体怎样发挥作用的。

基于meta path的相似度计算

相似度计算是数据挖掘领域的首要任务之一,它有益于后续最邻近搜索、聚类、分类等相关任务。对于网络数据挖掘而言,很多相似度的计算都局限在同构的对象之间,并不好套用到HIN体系里来。然而,前面我们也介绍到了基于不同的元路径,数据之间会展现出丰富的语义关联关系。所以,如何基于meta path,发展出一套适合HIN的相似度计算方法,是非常重要的基础工作。相似度的性质两个物体的相似度本质上就是反映了在某种度量空间下两者的距离远近,基于这样的理解,相似度需要满足下面两个基本性质:

其中xi表示网络中的第 i 个对象,\(s(x_i,x_j)\)表示第 i 个对象与第 j 个对象之间的相似度。两条性质都不难理解,我们下面要讲的几类相似度的定义方法都会满足这两点基本性质。PathSim作为比较早期HIN中的相似度方法,PathSim定义了对称元路径这个特定情况下的相似度计算问题。为什么是对称元路径呢? 因为在对称的元路径的条件下,定义出一个符合上述性质的相似度是很简单的,从下面的定义公式中,我们也可以清晰的看到这一点:
由于讨论的是对称元路径(上式中的P),所以这里的对象 x、y 是同类型的。\( p(x→y)\)表示HIN中的一条从x到y的路径。这个式子说明,给定某一个对称元路径P,PathSim和两部分有关:

  1. 符合P的路径模式下,对象x 到对象y的总路径数,很自然地,总路径数越多,相似度越高。
  2. 符合P的路径模式下,对象x,y到各自的总路径数,这是一个归一项,刻画了对象x与对象y在P模式下自身的可达路径总数,这个值越大,说明x,y自身在图里面沿着P路径的链接越发散,在考虑相似度的时候,需要这一项来做归一约束。

下面我们还是以论文引用网络为例,为了方便,我们只考虑作者与会议之间的网络:

我们来看看在 AVA 路径下作者之间的相似度具体是怎么算的。上图中Mike在SIGMOD上发表了2篇论文,也就是说Mike有两条路径到达SIGMOD这个对象节点,SIGMOD接受了50篇Jim的论文,也即SIGMOD到Jim的路径有50条。以此法理解,Mike和Jim 在AVA路径下的相似度为:

下面我们来看看怎么用矩阵的方式来计算PathSim值,在这之前,我们需要给一个很重要的定义:

Commuting matrix:

给定一个HIN,我们定义在元路径\( P(a_1,a_2...a_i)\)下的Commuting matrix\(M=W_{A_1A_2} W_{A_2A_3} ...W_{A_{i-1}A_i} \),\(W_{A_iA_j} \)表示Ai类节点与Aj类节点之间的邻接矩阵,比如上面作者和会议之间的邻接矩阵\(W_{AV} \),\(M_{i,j} \)代表着在元路径P下,\(A_1[\)类型里的第i个对象到\(A_l \)类型里的第j个对象之间的总路径数。同样地,在上面的例子中,AVA路径下的Commuting matrix:

有了Commuting matrix的定义,PathSim的计算就相当方便了:

特别地,如果P的长度为2,如AVA这种,PathSim衡量的就是两对象邻居节点之间的相似度。HeteSim下面我们来看看在非对称路径下,如何定义相似度。沿着PathSim的思路,首先在任意给定的路径P下,两个对象的之间的总路径数是一样计算的,这里是没有问题的,但是在归一化那一项就出现了问题,我们无法定义在一个非对称路径下对象自身的发散程度,于是相似度的第二条性质就很难满足了。在这种情况下,需要一种新的视角来审视这个问题。HeteSim以pairwise random walk的方式来考虑这个问题。假设在路径P的两端有两个漫步者向路径中点相向运动,那么就将两端对象的相似度定义为二者在中点某个节点相遇的概率。下面我们来看,作者是怎么具体定义的:Transition probability matrix对于一个关系\( A\stackrel{R}{\longrightarrow}B\),其邻接矩阵为\( W_{AB}\),\(U_{AB} \)是\( W_{AB}\)沿着行向量归一化的矩阵,我们将\(U_{AB} \)定义为\( A\stackrel{\longrightarrow}B\)在R关系下的转移概率矩阵。相反地,\(V_{AB} \)是\( W_{AB}\)沿着列向量归一化的矩阵,它定义了\( A\stackrel{\longrightarrow}B\)在\( R^{-1}\)关系下的转移概率矩阵。很明显的,二者满足下列关系:

其中\(V^{'}_{BA} \)表示\(V_{BA} \)矩阵的转置。

Reachable probability matrix

给定一个HIN,沿着元路径\(P=A_1A_2...A_{L+1) \)下的可达概率矩阵 PM 被定义为:

\( PM_{i,j}\)表示第 i 个A1类型对象沿着路径P到达 第j个\(A_{l+1} \)类型对象的概率。有了上面的定义铺垫,设想中的两者在中点类型M下相遇的概率为:

有了上面这个式子,两个对象a,b的相似度就可以计算:

\( (a,:)\)表示矩阵的第a行。

我们看到上面的这个式子,HeteSim就是以中点类型M为界,左右两边的可达概率矩阵的乘积。当路径是诸于APV或APAPA这类偶数长路径时,是存在中间节点的,但是如APVP这类奇数长路径时,并不好界定中间节点。这个时候怎么办呢?HeteSim的解决方法也很简单,在中间插入一个原子关系E,比如将AB路径变成AEB,具体就是将每一个AB路径的实列上增加一个新的E类型节点,这样的处理方式并不会改变AB路径下的拓扑结构,不会影响到相似度的计算。第二个问题是上面HeteSim的定义公式并没有考虑归一化,两组概率向量的乘积出来的值一般会更小,因此我们可以加上归一化项:

上面就是一个归一化之后的相似度定义公式。

上面这个例子展示了HeteSim是如何计算的,很简单,这里不赘述过程了。AvgSim第三种定义相似度的方法比较简单,这里我们也提一下。将元路径P的下面的可达概率矩阵与反路径\(P^{-1} \)下的可达概率矩阵取一个算术平均就行了,也即两端对象的单向可达概率的均值。

总结

上面介绍了HIN中相似度的几种定义方式,同时也介绍了各自怎么用矩阵进行计算。在工程上,我们可以根据事先拟定的几条最常用,最有意义的元路径,线下计算好各类对象之间的相似度,如果数据量太大,导致矩阵的维度过高,可以考虑稀疏矩阵相关的工程优化工作。当然这种计算方式是计算的全量数据之间的相似度矩阵。如果只需要知道两个特定对象之间相似度,可以采用蒙特卡洛的方法进行近似计算,比如模拟N个漫步者沿着元路径P从a达到b的概率,就可以代替a、b之间的相似度。最后,需要强调一点的是,相似度背后的概率意义只是用来强化理解的,只要符合上述两条性质,都可以作为HIN中相似度的一种定义,真正的桎梏还是在于工程实现上所面临的数据体量问题,所以应用中的着力点也应于此。

参考链接:

PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks

http://vldb.org/pvldb/vol4/p992-sun.pdf

HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks

https://arxiv.org/pdf/1309.7393.pdf

Avgsim: Relevance Measurement on Massive Data in Heterogeneous Networks

http://www.jatit.org/volumes/Vol84No1/12Vol84No1.pdf

本文地址:http://51blog.com/?p=6155
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 刘忠雨 ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情