PathSim：异质信息图中基于元路径的top-k相似搜索

PathSim：异质信息图中基于元路径的top-k相似搜索

标签（空格分隔）： 图模型

---

本文研究异质信息网络同一类型的顶点上的相似搜索。此外，考虑网络中不同链接路径，可以推导出不同的语义相似度。这里介绍一种基于元路径的相似度。元路径是定义在不同类型顶点之间的一系列关系序列组成的一条路径。

PathSim：  在元路径形式下，定义了一个新颖的相似搜索方法，它能找到网络中同类型的顶点。（如，在相似的领域找到拥有相似声誉的作者）在很多情况下，与基于随机游走的相似性度量方法相比较，pathsim更有意义。

异质信息网络

异质信息图（Heterogeneous information networks）是一个涉及多个类型的顶点对象，多个类型边（链接）的逻辑网络，例如，文献网络、社交网络。

信息网络（Information Network）:一个信息网络定义为一个有向图 G=(V,E)  ，包含节点类型映射函数φ： V→A  和链接类型映射函数 φ:E→R  ，其中对象 v∈V  属于一个特定的对象类型 ϕ(v)∈A  ，并且每个链接 e∈E  ，属于一个特定的关系 ψ(e)∈R 

不同于传统网络的定义，明确的区分表示对象的顶点的类型和表示链接关系的边的类型。注意，如果类型 A  到类型 B  存在联系，用 ARB  表示，反过来 R −1   表示 BR −1 A  ，在大多数情况下， R  和它的逆 R −1   并不相等。除非A和B属性相同，并且R是对称的。当顶点对象的属性 |A|>1  或者表示链接的边的属性个数 |R|>1  时，这个网络是异质信息网络，否则，是同质信息网络。

给定一个复杂的异质信息图，需要找到它的元层次描述以便于更好的理解。因此，提出 networkschema  的概念来描述网络的元结构。 networkschema  与 ERmodel  类似，但是只抓住实体的类型和他们之间的二元关系，而不考虑每个实体类型的属性。 networkschema  好像是网络的模板，它告诉我们有多少个顶点对象的类型，哪里存在可能的链接。

元路径相似度量框架

在一个异质信息图中，两个顶点对象可能通过不同的路径被连接。例如，两个作者之间的链接可能通过“作者-报纸-作者”的路径，“作者-报纸-发表场合-报纸-作者”的路径等等。不同的元路径代表不同的语义。

metapath：元路径是一个定义在图的网络模式 T G =(A,R)  上的路径。它的表示结构为 A 1 → R 1  A 2 → R 2  ...→ R l  A l+1   ，他定义了 A 1   到 A l   之间的一组复合关系 R=R 1 ∘R 2 ∘R 3 ∘...∘R l   。

如果关系 R  是定义在一个对称的顶点对象上（路径的起点和终点是同一个顶点类型），我们说元路径 P  对称。如果两种顶点类型之间没有多种不同类型的表，我们通常也使用顶点的类型名称来表示元路径： P=(A 1 A 2 …A l )  。在图书馆数目索引的例子中，两个作者之间的联合关系可以表示为一个长度为2的元路径， A→P→A  或者缩写为 APA  ， P ′   表示元路径 P  的逆元路径。也写作 P −1   ， P −1 =(A ′ 1 A ′ 2 …A ′ l )=(A l …A 2 A 1 )  。此处输入代码

通常定义一个元路径相似度框架，顶点对象 x  和顶点对象 y  有： s(x,y)=∑ p∈P f(p)  ，其中 f(p)  是一些定义在 x  和 y  之间的路径实例 p  度量方法。

元路径的语义

以电影推荐系统为例，其中包含了用户(U)、小组、电影、导演、演员、类型6种顶点类型。其中用户可以通过元路径“用户-电影-用户(UMU)”相连，也可以通过元路径“用户-电影-导演-电影-用户(UMDMU)”相连。不同的元路径代表了不同的语义，元路径UMU代表用户观看了相同的电影，而元路径UMDMU代表观看了同一个导演执导的电影。基于元路径UMU观看了想通电影的用户更相似，基于元路径UMDMU观看了相同导演执导的电影的用户更相似。

PathSim  相似度量方法

往返元路径形式 P=(P l P −1 l )  通常是对称的。在此基础上定义 PathSim  相似度量。

PathSim：  一个元路径相似度量方法，给定一个对称的元路径 P  ，两个相同类型的顶点对象x和y的Pathsim是：

s(x,y)=2×|{p x⇝y :p x⇝y ∈P}||{p x⇝x :p x⇝x ∈P}|+|{p x→x :p x⇝x ∈P}|  

其中， p x⇝y   是 x  与 y  之间的路径实例， p x⇝x   是 x  与 x  之间的路径实例， p y⇝y   是 y  与 y  之间的路径实例。

给定一个元路径 P  ， s(x,y)  通过两个方面来定义，一是：两个顶点对象之间的定义在元路径上的联系；二是，它们与自身的路径实例个数。

下表展示了一个简单的网络中的作者和发表场合之间的邻接矩阵 W AC   ，网络表示作者在每个场合，发表报纸的数量。查询和“ Mike  ”同类的作者。

-	SIGMOD	VLDB	ICDE	KDD
Mike	2	1	0	0
Jim	50	20	0	0
Mary	2	0	1	0
Bob	2	1	0	0
Ann	0	0	1	1

计算Mike与其他作者的 PathSim  值：

s(Mike,Jim)=2×(2×50+1×20)(2 2 +1 2 )+(50 2 +20 2 ) =0.08 

s(Mike,Mary)=2×(2×2+1×0+0×1)(2 2 +1 2 )+(2 2 +1 2 ) =0.8 

s(Mike,Bob)=2×(2×2+1×1+0×1)(2 2 +1 2 )+(2 2 +1 2 ) =1.0 

s(Mike,Ann)=2×(2×0+1×0+0×1+0×1)(2 2 +1 2 )+(1 2 +1 2 ) =0.0 

对以上 PathSim  值排序得出与 Mike  最相似的作者 Bob 

baseline python3实现

# -*- encoding: utf-8 -*-
import pandas as pd
import numpy as np


class DBLPnetwork_PathSim:
    def __init__(self, author, paper, venue, edge1, edge2):
        # self.__file_to_dataframe(author, paper, venue)
        self._read_edge1(edge1)
        self._read_edge2(edge2)
        self._build_path_APV()
        self._build_AA_diagonal_APVPA()

    def _read_edge1(self, edge1):
        self.edge1 = pd.read_csv(edge1, header=0, index_col=0)

    def _read_edge2(self, edge2):
        self.edge2 = pd.read_csv(edge2, header=0, index_col=0)

    def _build_path_APV(self):
        m1 = self.edge1
        m2 = self.edge2.sort_index(ascending=False)
        m2_rowname = [x for x in m2.index]
        m1 = m1.ix[:, m2_rowname]
        mp = pd.DataFrame(np.dot(m1.values, m2.values), index=m1.index, columns=m2.columns)
        self.mp = mp

    # def __file_to_dataframe(self, author, paper, venue):
    # self.author_vertices = self._read_author(author)
    # self.paper_vertices = self._read_paper(paper)
    # self.venue_vertices = self._read_venue(venue)
    #
    # def _read_author(self, author):
    # self.author_vertices = pd.read_csv(author)
    #
    # def _read_paper(self, paper):
    # self.paper_vertices = pd.read_csv(paper)
    #
    # def _read_venue(self, venue):
    # self.venue_vertices = pd.read_csv(venue)

    def _find_candidate_set_A(self, an_author):
        ''' 找到与目标向量不正交的的向量，作为候选集，这是baseline算法的优化核心 '''
        yk = [y for y in self.mp.columns if self.mp.loc[an_author, y] != 0]
        candidate_set_A = []
        for y in yk:
            for x in self.mp.index:
                if self.mp.T.loc[y, x] != 0:
                    candidate_set_A.append(x)
                else:
                    pass
        candidate_set_A = list(set(candidate_set_A))
        candidate_set_A.remove(an_author)
        return candidate_set_A

    def _build_AA_diagonal_APVPA(self):
        authors = [x for x in self.mp.index]
        diagals = np.diagonal(np.dot(self.mp.values, self.mp.values.T))
        self.AA_dict_APVPA = dict(zip(authors, diagals))
        return self.AA_dict_APVPA

    def calcu_pathsim_value(self, an_author, other_author):
        fenzi = 2 * np.dot(self.mp.loc[an_author, :], self.mp.T.loc[:, other_author])
        fenmu = self.AA_dict_APVPA[an_author] + self.AA_dict_APVPA[other_author]
        val = fenzi/fenmu
        return round(val, 2)

    def find_top_10_similar_authors_APVPA(self, an_author):
        candidate_set_A = self._find_candidate_set_A(an_author)
        similar_authors = [(x, self.calcu_pathsim_value(an_author, x)) for x in candidate_set_A]
        sorted_list = sorted(similar_authors, key=lambda x: x[1], reverse=True)[:10]
        print(sorted_list)
        return sorted_list


def main():
    dblp = DBLPnetwork_PathSim("author.csv", "paper.csv", "venue.csv", "edge1.csv", "edge2.csv")

    print("============Top 10 using APVPA for Mike=================")
    ADlist_APVPA = dblp.find_top_10_similar_authors_APVPA("Mike")

    for author, val in ADlist_APVPA:
        print(author)