异质网络组合元路径节点重要性分析方法

刘政君，梁 英，张 伟

1(中国科学院计算技术研究所，北京100190)

2(中国科学院大学，北京100190)

1 引 言

异质信息网络包含多种类型的对象或关系，与同质信息网络相比，异质信息网络可以包含更加丰富的语义信息.在异质信息网络中挖掘重要的节点具有很高的实用价值，可应用于学术评审评议、优化搜索引擎、推荐［1］、网络可视化和链路预测等.

在异质信息网络中，对象间的关系主要包括内部关系和相关关系.其中，内部关系指的是相同类型的对象之间的关系;相关关系指的是不同类型的对象之间的关系.元路径是定义在异质信息网络中链接两类对象的一条路径，不同的元路径表达了不同的语义信息.图1 表示了学术网络的网络模式.这个实例中包含了三种类型对象:论文、学者和会议，可以看出，学者之间的合作关系和论文之间的引用关系对应的是内部关系，学者和论文之间的发表关系、会议与论文之间的收录关系对应的是相关关系.同时，图中还包含了“学者-论文-学者”、“学者-论文-会议-论文-学者”等元路径信息.

图1 学术异质信息网络的网络模式Fig.1 Academic heterogeneous information network schema

在信息网络的研究中，关键节点对整个网络起着至关重要的作用，因而发掘其中的重要节点具有重要的理论意义与应用价值.目前节点重要性分析方法主要分为同质网络的节点重要性分析和异质网络的节点重要性分析.其中，同质网络的节点重要性分析主要是基于节点之间的连接权重进行重要性分析，而与同质信息网络相比，异质信息网络具有更全面的结构信息和更丰富的语义信息，虽然同质网络的节点重要性分析方法取得了很好的效果，但迁移到异质网络时会造成语义信息的丢失，因此无法直接应用于异质网络上，这导致异质网络的节点重要性分析成为研究难点.

异质网络中的节点重要性分析主要通过元路径寻找不同类型节点之间的关系，目前的异质信息网络中分析节点重要性的方法大多使用不同对象之间的可达性对异质信息网络进行分析，没有更大范围地捕捉存在于网络中的语义信息，导致排名缺少可信度.

针对上述问题，本文提出了一种异质信息网络中基于组合元路径的节点重要性排名方法(Combination-Path Rank)，通过组合多个包含特定语义的元路径，捕捉异质信息网络丰富的语义信息，使得重要性排名结果更加精准.该方法使用指数加权平均数法(EWA)［2］确定对象内部关系与相关关系的组合参数寻优步长，以最大化排名向量的信息熵为贪心目标，寻找组合参数的局部最优值，最终得到一个稳定可信的重要性排名.

本文的贡献包括:

1)提出了一种基于组合元路径的重要性排名方法.组合了多种含有特定语义的元路径，可以兼顾更丰富的信息，使重要性排名更精准.

2)以信息熵为标准对随机游走的比重进行优化.确保组合元路径的组合参数收敛于某个数值范围内，使重要性排名更可信.

2 相关工作

目前，有许多方法用于解决节点重要性分析问题，主要分为同质信息网络的重要性分析方法、二分图的重要性分析方法和基于元路径的重要性排名方法.

许多学者在同质信息网络节点的重要性进行分析进行了深入的研究.Page［3］等人提出了类似投票机制的 PageRank 算法，通过随机游走分析同质信息网络中节点的重要性.Kleinberg［4］提出了 HITS 算法，使用 authority 和 hub 分数来对节点进行重要性排名.Jeh［5］提出了SimRank 算法，基于向量空间模型的相似性高效的对节点进行重要性排名，并用于对节点的评分.这三种方法针对单一类型节点的同质信息网络进行重要性排名，并不适用于包含多种节点和关系的异质信息网络.

二分图的节点重要性排名方法将节点分为两类，用以构建两个子图来对节点进行重要性分析.Zhou［6］通过两个随机游走来对二分图的学者和出版物进行重要性排名，出版物和学者的重要性排名在迭代计算中相互增强，从而利用了异质信息网络中隐含的语义信息.Deng［7］提出了co-HITS 算法，将二分图的内容信息和约束结合起来进行重要性排名，并提出了一个代价函数来考虑两个实体集之间的直接关系.Soulier［8］提出了一种通过组合不同特征的重要性排名算法.但是二分图的重要性分析方法只能处理含有两类对象的信息网络，不适用于多关系网络的重要性分析.

现实中真实的网络数据组织形式多为异质信息网络，包含不同类型的对象和关系，元路径作为一种有效的语义捕获方法，通过不同的元路径进行重要性分析可以获得不同的排名结果.Sun［9］提出了 PathSelClus 算法，通过学习元路径的权重，元路径权重在迭代过程中不断更新用以提高聚类质量，但是该方法挑选的元路径之间相互独立，不具备信息共享的特性.Meng［10］等提出了一种自动发现元路径的方法，通过高接近度的节点对来贪心的寻找可以解释节点对之间关系的元路径，并整合对象之间的关系用以捕捉重要的元路径，但是该方法没有考虑元路径之间信息互补，使得元路径包含的语义只是局部最优.Shi［11］等提出了SemRec 集成异构信息并获得表示用户对路径的偏好优先级和个性化权重，实现了更好的推荐性能，但是该方法没有考虑元路径之间组合关系，重要性分析缺乏一定的网络信息.Cao［12］提出了 LiPaP 算法，设计了一个元路径生成的算法，按照相关性顺序提取元路径，并学习被提取的元路径的权重，由于该方法提取的元路径有较高的相似性，在用于节点重要性分析时会忽略掉其他元路径包含的网络信息.Wang［13］提出了一种无监督的元路径选择方法，自动在异质信息网络上寻找有用的元路径，并提出了一种新的相似性度量方法KnowSim 应用于文本聚类和分类问题改进聚类和分类结果，但是该方法没有考虑元路径之间信息互补，使得在进行重要性分析时缺乏需要的语义.Li［14］提出了HRank，利用约束元路径来捕获网络中的丰富语义.HRank 应用张量分析同时评估多种类型的对象和元路径的重要性，但该方法只考虑到了对象之间的可达性或简单的组合元路径，无法针对元路径上的不同对象选取不同的元路径进行语义补充，重要性分析缺乏针对性.

本文提出基于组合元路径的重要性排名方法，通过组合元路径有针对性地捕捉与重要性排名相关的语义信息，避免了使用单一的语义信息分析节点的重要性的局限，从而使重要性排名更加可信.

3 基本定义

在介绍重要性排名算法之前，先给出符号解释和定义.

定义1.异质信息网络G.给定一个有向图G=(V，E，τ，φ，A，R).V 代表节点集，E 代表边集.τ 表示对象类型映射函数，φ表示关系类型映射函数.τ(v)∈A 表示每个节点v∈V都属于一个节点类.φ(e)∈R 表示每个边e∈E 都属于一类关系.当对象类型数量∣A ∣＞1 或关系类型数量∣R ∣＞1时，网络被称为异质信息网络.当对象类型数量 ∣A ∣=1且关系类型数量∣R ∣=1 为同质信息网络.

令Vi表示Ai对象对应的V 中节点的集合，满足:对于Av∈Vi，Vi≤V，都有 τ(v)=Ai，并且对于Av∈V－Vi，都有τ(v)≠Ai.其中，Ai表示 G 中的对象类型，Ai∈A.

定义2.元路径 P.给定异质信息网络 G=(V，E，τ，φ，A，R)，长度为m 的元路径P 定义为链接两类对象的一条路径.即.其中:Ai表示G 中的对象类型，Ai∈A;Ri表示 G 中的关系类型，Ri∈R.元路径P 的长度用Plen(P)表示，代表元路径中对象的个数，即m=Plen(P).

为了方便，规定元路径P 的表示缩写为A1A2…Ai…Am，Ai∈A.A1称为元路径 P 的源对象，Am称为元路径 P 的目标对象.

元路径P 包含的对象对应一个对象序列(A1A2…Ai…Am)，假定有一条元路径tp=Astart…Aend，如果tp 对应的对象序列(Astart…Aend)是(A1A2…Ai…Am)的连续子序列，则称元路径tp 为P 的子路径.

元路径刻画了节点之间的语义信息，以学术网络为例，假设A，P，C 分别表示学者、论文和会议，则元路径APCPA 表示的语义是不同学者在同一个会议上发表论文.元路径APA 表示的语义是不同的学者合作发表同一篇论文.

定义3.组合元路径CP.在异质信息网络G=(V，E，τ，φ，A，R)中，定义组合元路径为 CP=(FP，LP，λ).其中:

FP 是一条以被排名对象为目标对象的元路径，称FP 为主元路径(Main meta-path)，FP 的长度为m.

LP 是由m 个辅助元路径(Auxiliary meta-path)组成的元路径集合，即 LP={LPA1，LPA2，…，LPAi，…，LPAm}，称 LP 为辅助元路径集合.LPAi为辅助元路径，0＜i＜m，是一条链接在主元路径的Ai对象上用于补充Ai对象语义信息的元路径，Ai∈A.

λ={λA1，λA2，…，λAi，…，λAm}表示辅助元路径集合 LP与主元路径FP 的组合参数集合，λAi为主元路径FP 与辅助元路径 LPAi的组合参数，0＜i＜m.

组合元路径通过多个辅助元路径对主元路径的语义进行补充，使得组合元路径可以适应异质信息网络中复杂的网络结构和多种对象关系.

定义4.相关关系转移邻接矩阵WAlAk.相关关系转移邻接矩阵WAlAk是表示Al对象与Ak对象之间关系的邻接矩阵，Al∈A，Ak∈A.将 Al对象对应的节点类 Vl中的第 i 个节点表示为 vl，i，Ak对象对应的节点类 Vk中的第 j 个节点表示为vk，j，则 WAlAk={wi，j}的计算公式见式(1).

相关关系转移邻接矩阵Wpaper，author表示的是论文对象与学者对象之间的发表关系.

定义5.内部关系转移邻接矩阵MAlAl.内部关系转移邻接矩阵MAlAl是表示Al对象内部关系的邻接矩阵，Al∈A.MAlAl={mi，j}的计算见式(2).

其中relation_num 表示节点之间的路径数，以学术网络为例，两个学者之间的relation_num 可以代表合作次数.内部关系转移邻接矩阵Mpaper，paper表示的是论文对象的互相引用关系.

4 基于组合元路径的节点重要性排名方法

基于组合元路径的节点重要性排名方法首先选取主元路径和辅助元路径集合构建组合元路径，沿主元路径进行重要性排名的循环迭代计算，并对组合参数进行更新，最大化排名向量的信息熵，使排名向量更加可信.

步骤1.确定主元路径，根据主元路径选取辅助元路径，构建组合元路径.

步骤2.计算相关关系排名和内部关系排名，通过参数线性组合得到重要性排名.

步骤3.沿主元路径循环迭代计算直至重要性排名稳定，迭代同时进行组合参数更新.

图2 基于组合元路径的节点重要性排名方法Fig.2 Node importance ranking method based on combine meta-path

图2 展示了该方法的基本思想，①通过主元路径FP 可以确定不同对象之间的相关关系，计算相关关系排名;②通过Ai对象的辅助元路径LPAi确定Ai对象的内部关系，计算内部关系排名;③线性组合相关关系排名和内部关系排名得到该对象的重要性排名，并沿主元路径进行下一个对象的重要性排名计算.并将主元路径的目标对象连入源对象，构建可循环迭代的计算结构，计算不同迭代次数的重要性排名.

4.1 组合元路径的选取

选取主元路径和辅助元路径集合构建组合元路径用以捕捉语义信息.主元路径可以按照如下规则选取:首先根据异质信息网络的网络结构得到元路径集合MP，当对Ai对象进行重要性排名时，在MP 中筛选出以Ai为目标对象的元路径，当筛选结果中包含多条元路径时，为了更大范围地捕捉语义信息，从中选取包含对象类型数目最多的元路径作为主元路径FP.

针对主元路径 FP=A1A2…Ai…Am上的每类对象 Ai，Ai∈A，在元路径集合MP 中选取一条辅助元路径LPAi用于补充Ai对象的语义信息，辅助元路径的选取遵循3 个规则:

规则1.类型相同规则.辅助元路径的源对象与目标对象类型相同，即辅助元路径As…Ae满足As=Ae.

规则2.语义不重复规则.辅助元路径与主元路径中包含的语义不能重复，即主元路径与辅助元路径不可互为子路径.

规则3.长度最短规则.当对Ai对象的辅助元路径LPAi进行选取时，若满足规则1 和规则2 的元路径有r 条(r＞1)，符合规则的元路径记为 candp1，candp2，…，candpr，选取长度最短、包含对象类型最少的元路径作为辅助元路径LPAi.即LPAi=min(Plen(candpt)).

辅助元路径的设计原则遵循进一步补充语义信息，同时避免语义重复，使补充的语义信息更具有针对性.因此，选择长度最短、包含对象类型最少的元路径作为辅助元路径，既能更大范围的捕捉语义信息，又能避免语义重复.辅助元路径的确定过程如算法1 所示.

算法1 的算法时间复杂度为O(mk)，第4 ～9 行是遍历元路径集合MP，寻找符合规则1 和规则2 的元路径candpt，将符合选取规则的元路径 candpt放入集合 candp 中.第11 ～13行表示当candpt不为空集时，从集合中挑选出长度最短、包含对象类型最少的元路径作为Ai对象的辅助元路径LPAi加入到辅助元路径集合LP 中.

4.2 组合排名的计算

根据辅助元路径集合LP 可以得到A1，A2…Ai…Am对象的内部关系转移邻接矩阵 MA1A1，MA2A2，…，MAiAi，…，MAmAm.Ai对象的内部关系转移邻接矩阵为 MAiAi，Ai∈A，第 j－1(j＞1)次迭代计算得到的 Ai对象的重要性排名为 RankAi，j－1，通过 MAiAi和 RankAi，j－1可以得到 Ai对象在第 j 次沿主元路径 FP循环迭代计算得到的内部关系排名 R1Ai，j，i=1，2，…，m.计算方法见式(3).

根据主元路径FP 上相邻对象的相关关系，得到m－1 个相关关系转移邻接矩阵 WA1A2，WA2A3，…，WAi－1Ai，…，WAm－1Am.Ai对象与Ai－1对象之间的相关关系转移邻接矩阵为 WAi－1Ai，第j－1 次沿主元路径FP 循环迭代时Ai对象的重要性排名为RankAi，j－1，通过 WAi－1Ai和 RankAi，j－1可以计算得到 Ai对象在第j 次迭代时的相关关系排名R2Ai，j，计算方法见式(4).

使用组合参数 λAi(0＜λAi＜1)对 R1Ai，j和 R2Ai，j进行线性组合，得到Ai对象在第j 次沿主元路径FP 迭代计算得的重要性排名 RankAi，j，组合方法见式(5).

4.3 组合参数寻优

组合参数决定了相关关系排名和内部关系排名在重要性排名中的占比，本节通过组合参数寻优最大化重要性排名向量的信息熵，最大化排名向量的信息熵可以使排名更具有区分度.计算第j 次迭代时Ai对象的排名向量RankAi，j的信息熵及其与第j－1次迭代的排名向量 RankAi，j－1的信息增益 ΔH.信息熵的计算方法见式(6).

其中，X 为排名向量，p(xi)表示X 分布中离散值xi的出现概率，一般H(X)＞0.X 变量的不确定性越大，熵就越大.

信息增益ΔH 的计算公式见式(7).

这里，RankAi，j是第 j 次迭代时 Ai对象的重要性排名向量，RankAi，j－1是第j－1次迭代时 Ai对象的重要性排名向量.

利用指数加权平均法计算出Ai对象在第j 次迭代计算时组合参数λAi的寻优步长PAAi，j，计算方法见式(8).

其中，μ 是指数加权平均法的超参数.

把主元路径FP 上的目标对象连入源对象，构建循环迭代的计算结构，在循环迭代计算的过程中，以最大化重要性排名的信息熵为目标，使用指数加权平均法计算组合参数的寻优步长对组合参数进行更新，直到组合参数和重要性排名向量趋于稳定.

通过以上步骤可以将主元路径与多个辅助元路径进行组合并循环迭代的进行重要性排名计算，如算法2 所示.

当每类对象对应的节点类包含x 个节点时，算法2 的时间复杂度为O(mx3)，第1 ～3 行为主元路径FP 上的每类对象初始化重要性排名.

算法的第7 行计算第j 次迭代计算时Ai对象的内部关系排名.

第8 行计算第j 次迭代计算时Ai对象的相关关系排名.

第9 行线性组合相关关系排名和内部关系排名得到第j次迭代计算时Ai对象的重要性排名.

第10 行对计算得到的排名向量进行归一化.

第11 行通过指数加权平均法计算参数的寻优步长，并对参数进行更新，最大化重要性排名的信息熵.

第15 行确定迭代结束条件.

5 实验与效果评估

本节在AMiner［15］数据集上测试了基于组合元路径的重要性排名方法，并使用匹配准确率和收敛速度对实验结果进行分析评估.

5.1 实验数据

使用AMiner 数据集作为实验数据集，AMiner 数据集包括了1702575 个学者数据、1932381 篇论文数据、255407 个会议数据、5181440 个学者与论文的发表数据、8008836 个论文之间的引用数据和4249520 个作者之间的合作数据.

选取包含学术领域信息的学术文本，对该学术文本进行LDA［16］主题提取，得到主题集合 RZ 和 RZ 中各主题元素的比重得分SZ.

选取AMiner 数据集中数据挖掘领域的会议，将每个会议对应的学术文本进行拼接，并同样进行LDA 主题提取得到第j 个会议的主题集合RCj和主题集合RCj对应的各主题比重得分SCj.计算每个会议的主题集合与学术文本的主题集合RZ 的加权相似度得分.

根据相似度得分选定 SIGKDD、SIGMOD、VLDB、ICDE、CIKM、DASFAA 这六个会议用以缩小信息网络的分析范围，增强重要性分析的针对性.表1 统计了AMiner 数据集中这六个会议收录的论文数以及与会议存在发表关系的学者数.

表1 会议的数据统计Table 1 Conference statistics

5.2 评价指标

选取实验结果的匹配准确率以及排名向量的收敛速度作为对重要性排名方法的评价指标.

1)匹配准确率accuracy

匹配准确率可以说明算法的可信程度，计算公式见式(9).

式(9)中Calset(Top_num)表示排名方法结果中前Top_num 个元素构成的集合，Baseset 表示用于计算匹配准确率的匹配集合.

2)收敛速度

随着迭代次数的增加，重要性排名向量趋于稳定，收敛速度快的方法可以在较少的迭代次数中得到稳定的重要性排名.

计算相邻两次迭代结果的重要性排名向量之间的欧几里得距离dis，并使用dis 作为判断迭代是否结束的依据，当Ai对象相邻两次迭代计算得到的排名向量之间的dis 值小于某一给定的阈值σ 时，方法停止迭代，欧几里得距离dis 的计算公式见式(10).

式(10)中，RankAi，r表示的是 Ai对象第 r 次迭代计算时得到的重要性排名向量，RankAi，r－1表示的是 Ai对象第r－1次迭代计算时得到的重要性排名向量.

5.3 实验内容

以AMiner 数据集构建学术异质信息网络，使用基于组合元路径的节点重要性分析方法对Author 节点进行重要性分析，选取包含对象类型数目最多的元路径CPA 作为主元路径FP，主元路径长度m=3.由于Conference 对象对应的节点之间没有相互影响的关系，选取表示论文之间互相引用的关系的元路径PP 作为LPpaper来补充Paper 对象语义信息，选取表示学者之间相互合作的关系的元路径APA 作为LPauthor补充Author 对象的语义信息.

将主元路径FP 的目标对象Author 连接入源对象Conference，构建循环迭代的计算结构，得到不同迭代次数下的重要性排名，直至重要性排名稳定.

表2给出了基于组合元路径的重要性排名方法在AMiner 数据集上运行结果的前5 名学者的信息，同时也给出在AMiner 数据集中按照引用数和H 指数(h-index)排序的前5名的学者信息进行学者之间的比对.这里，H 指数是一个量化学者个体科研成果的评价指标，学者的H 指数是指至多有H篇论文分别被引用了至少H 次.

基于组合元路径的重要性排名方法的实验结果都可以在引用数或H 指数的排名结果中找到对应，说明了实验结果的合理性.并且可以看出基于组合元路径的重要性排名方法更具有针对性，在一定程度上排除在其他学术领域有较多成果的学者，提高排名的精准性，体现了基于组合元路径的重要性排名方法相对于统计方法的优势.

清洗数据使PageRank 和HITS 算法可以进行重要性分析，PageRank、HITS 和基于组合元路径的节点重要性排名方法的实验结果与AMiner1https://www.aminer.cn/于2019 年4 月公布的知名学者之间进行匹配.将学者按H 指数、A 指数(A-index)排名得到H指数排名和A 指数排名，并计算出H 指数排名和A 指数排名的匹配结果，得到的匹配准确率如图3 所示.

图3 匹配准确率Fig.3 Matching accuracy

图3 的横轴表示的是算法结果的匹配范围，即对算法结果中前top 个结果求匹配准确率.纵轴表示的是对应的匹配范围内的匹配准确率.

从图3 可以看到，随着匹配范围的不断扩大，基于组合元路径的节点重要性分析方法的匹配准确率较高，使用单一语义进行重要性分析的PageRank 和HITS 算法，由于忽略了语义信息，匹配准确率稍低.

由于HITS 算法易受“垃圾链接”的影响，当不同对象之间存在一对多的关系时会引起HITS 的重要性分数的不正常增加，从而影响匹配准确率偏低;而直接使用学术指标进行重要性排名只是对学者发表的学术成果进行了简单的统计，无法针对某个学术范围进行学者的重要性分析，匹配准确率较低.

PageRank、HITS 和基于组合元路径的节点重要性排名方法的实验结果都与AMiner 公布的知名学者有差别，部分学者跨多个研究领域，导致对学者重要性的分析出现偏差;部分学者的成果发表时间较短，未被AMiner 收录，导致重要性分析缺乏时效性;还有一些学者的信息没有包含在AMiner 数据集中，导致无法对此类学者进行重要性分析.

在循环迭代计算的过程中，各学者的重要性得分会收敛于一个稳定值，即重要性排名向量会趋于稳定.图4 显示了PageRank 算法、HITS 算法、基于组合元路径的节点重要性分析方法的排名向量的收敛速度.图4 的横坐标表示算法迭代计算的次数，纵坐标代表的是相邻两次计算得到排名之间的距离.

通过图4 可以发现基于组合元路径的重要性分析方法可以使排名向量更快速地收敛，而PageRank 算法和HITS 算法的收敛速度较慢，需要更多次的迭代计算才可以使排名收敛.

图4 迭代计算时排名的收敛Fig.4 Convergence of rankings in iterative calculations

基于组合元路径的重要性分析方法使用组合参数对相关关系排名和内部关系排名进行线性组合，并在迭代计算中不断的对组合参数进行更新.

图5 参数 λpaper和 λauthor的收敛Fig.5 Convergence of parameters λpaper and λauthor

Paper 节点的组合参数λpaper和Author 节点的组合参数λauthor的收敛情况如图5(a)和图5(b)所示.从图5 中可以看到，通过指数加权平均法确定步长并对组合参数进行更新之后，组合参数最终会收敛于某一个较小的范围内.

6 总 结

本文研究了异质信息网络中的节点重要性分析问题.提出了一种基于组合元路径的节点重要性排名方法，根据异质信息网络的结构确定组合元路径，进行循环迭代计算，同时更新组合参数使排名向量的信息熵最大化，直至重要性排名稳定.通过实验验证了所提方法有效，并可以快速收敛.后续工作中，我们将考虑沿元路径进行多循环迭代运算时不同组合参数收敛速度的差异性，开展进一步的研究.