基于文献信息网络语义特征的相似性搜索

邱庆羽，李 婧，全 兵，童 超，张利君，张海仙*

(1．四川大学 计算机学院，成都610065; 2．中移(苏州)软件技术有限公司，江苏 苏州215000;3．成都瑞贝英特信息技术有限公司，成都610041)

(*通信作者电子邮箱zhanghaixian@scu．edu．cn)

0 引言

信息网络由一系列的节点以及连接节点的关系组成，现实世界中大多数对象都可以抽象为一个庞大的网络，例如:文献信息网络［1］、生物信息网络［2］、电影网络［3］等。根据节点和关系的类型，信息网络可以具体划分为同构信息网络和异构信息网络。由于现实信息网络中节点类型多样，而且不同节点间的关系包含丰富的语义信息，所以目前研究的工作主要围绕异构信息网络展开。

随着异构网络的信息量呈指数级增长，用户往往难以从大量的数据中筛选出感兴趣的信息。相似性搜索作为异构信息网络的重要研究分支，可以从大量的数据集中发现与查询对象最为相关的信息，现已广泛应用于诸多领域。例如，在文献网络中，用户希望找到与给定作者最为相似的作者信息［4］;在医学领域中，人们希望利用异构网络识别出潜在的microRNA与疾病之间的关联，从而解释人类多源性疾病的发病机理［5］;在电商领域中，商家可能感兴趣于推荐与指定产品最为相似的其他产品，辅助用户作购买决策［6］。因此，基于异构信息网络寻找与查询对象最为相似的对等实体具有重要的研究价值和应用场景。

近年来，众多学者探索设计不同的相似性度量方法，涌现了大量优秀的工作。目前的研究工作大致可以分为以下3类:

1)基于节点特征的相似性度量［7－8］。借助计算特征相似性从而得到网络节点间的相似性，然而该方法并不适用于不同类型节点间的相似性计算。

2)基于图论的相似性度量［9－10］。通过图拓扑概念将节点间的相似性转化为与节点有关的图结构的相似性进行计算。

3)基于元路径的相似性度量［11－13］。借助领域知识定义几种包含节点、关系操作的序列来计算节点在全局中的相似性。

本文提出了基于文献网络语义特征的相似性搜索算法(Similarity computation based on Vectorand meta Path，VPSim)，其主要贡献包括:

1)从节点特征出发，提出了一种基于向量的文献网络特征提取的方法。该方法可用于衡量同类型节点间的语义关系，通过分析语义得到向量间相关概率作为节点间路径权重。

2)结合元路径设计了一种基于语义特征的节点相似性度量算法。在传统的元路径基础上，增加了节点的语义信息，从而对节点的相似性分数进行加权组合。

3)基于文献网络数据的特点，设计了剪枝策略用以提高相似性搜索算法的执行效率。通过在真实数据集上的实验验证了提出算法的有效性、执行效率和可扩展性。

1 相关工作

1．1 语义特征提取

语义特征提取工作的前提是为文本寻求一种恰当的表示方式。目前研究工作处理的文本表示模型共有三种:布尔模型(Boolean Model)、向量空间模型(Vector Space Model)［14］和概率模型(Probabilistic Model)［15］。其中，向量空间模型因其操作性强、易于计算分析的优点得到了广泛的应用。然而，随着对文本语义研究的深入，向量空间模型的不足日益显现，如:实际的文本难以满足特征项间相互独立;只关注特征项的频率信息从而丢失了文本上下文的语义及潜在的概念结构等信息。

因此，目前文本特征提取问题的研究工作，逐渐从传统方法向深度学习方法转移。深度学习的方法可以更好地提高模型的泛化能力，结合词向量Word2Vec［16］技术，以及神经网络的层次化设计机制，更好地解决文档表达的多元性和层次性问题。然而像传统方法一样，Word2Vec只是基于词的维度进行语义分析，忽视了上下文的语义。由 Quoc等提出Doc2Vec［17］模型，在 Word2Vec模型的基础上作了改进，通过在训练文档过程中增添一个共享段落向量，保留了文本上下文的语义信息。

1．2 信息网络相似性搜索

相似性搜索作为众多数据挖掘任务如聚类、推荐等的基础受到广泛关注也诞生了很多优秀的工作。基于同构信息网络的工作有 Jeh等［18］提出的个性化 PageRank算法和SimRank算法［11］等;Kusumoto等［19］提出了 SimRank 的线性递归表达式便于并行计算，使得大规模图计算成为可能。然而这些算法并不直接适用于异构信息网络的相似性搜索。

考虑到由不同类型对象组成的元路径包含丰富的语义信息，Sun等［4］提出了PathSim算法用于计算基于单个对称元路径同类型节点的相似性，但该方法不适用于不同类型的节点。进而Shi等［20］提出了HeteSim算法用于计算不同类型实体间的相似性。以上方法均需用户具备相关领域知识，具有一定局限性。Huang等［21］在元路径的基础上提出了基于 Meta Structure在大规模文献异构网络中的相似性搜索算法。此外，通过引入用户导向，预测与用户搜索相关元路径的方法可以缩小元路径指定范围，目前也有一些研究工作，如MineRank算法［22］等。这些方法都是基于异构网络的结构进行相似性搜索，虽然也取得了较好的效果，但它们均忽略了节点包含的语义信息，从而使得挖掘结果不准确。而语义信息作为节点的重要属性，对相似性搜索具有重要的作用。

本文从信息网络的语义出发，结合元路径提出了一个面向文献信息网络，基于语义特征的相似性搜索算法。该算法考虑了公认的领域知识，不需要用户指定，同时利用了节点自身携带的语义信息，使得相似性搜索的结果更为准确。同时结合文献数据的特点，设计了剪枝策略，降低了计算候选路径的规模，为文献网络计算相似性提供了一种新的解决思路。

2 问题定义

2．1 信息网络

信息网络是结构化文本表示知识的一种方式，它由一系列的节点和连接节点的边组成。

定义1 信息网络［4］。信息网络可以用一个有向图G=(V，E)来表示，其中V表示对象，E表示连接对象的边。且对象V和边E均有相应的类型映射函数，s:V→T，表示对于每个对象v∈V均属于对象类型集合T:s(v)∈T以及关系映射函数t:E→R，对于任意一条边e∈E都属于一种特定类型边的集合R:t(e)∈R。

文献信息网络是典型的异构信息网络，它包含了三种不同对象类型:作者(A)、论文(P)、会议(C)，同时包含两种类型的边:作者撰写文章，文章发表在会议上。值得注意的是，在其他的应用场景中，可能涵盖类型为术语(V)的对象以及文章涉及到某个术语的边，但本文工作主要针对会议上文章的相关性，所以在图1中并未展示术语类型的对象。具体的文献信息网络如图1所示。

图1 文献信息网络Fig．1 Bibliographic information network

定义2 元路径［4］。元路径P是定义在网络G上的一种基础路径，如:，表示了从类型T1到类型Tl+1的复合关系R，即R=R1。R2。…。Rl，其中。表示定义在关系上的复合操作。

图2中列出了文献信息网络中典型的元路径，具体地，元路径实例则如表1所示。值得注意，本文只用到了“APCPA”元路径进行计算。

表1 文献信息网络中的元路径实例Tab．1 Instances of meta paths in bibliographic information network

图2 元路径Fig．2 Meta paths

2．2 语义特征向量

定义3 语义特征向量，是指利用神经网络语言模型对文本信息进行特征提取，从而将任意文本映射成特征向量(feature vector)的形式。具体地可以表示为:

v= ［v1，v2，…，v(k－1)，vk］

其中k代表向量的维度。在本文中使用Doc2Vec［17］神经网络语言模型对文本信息进行特征提取。

定义4 语义特征相似度。在文献信息网络中，语义特征相似度采用余弦相似度对发表在同一个会议上的论文标题集合特征向量进行计算。具体如式(1)所示:

N最大值，cos()表示余弦相似度，×代表笛卡尔积。由于余弦相似度的取值范围在［－1，1］内，不便于后续的计算，因此本文对式(1)进行归一化，具体如式(2)所示:

具体的算法描述见算法2。

2．3 相似性

定义5 相似性。给定对象a1和对象a2，利用文献信息网络语义特征可以定义二者之间的相似性，具体如式(3):

其中:|C|表示会议的数量，pa1～a2表示从对象a1出发在满足元路径的前提下到对象a2的路径实例，Pc为定义在会议c上元路径代表作者a发表在会议c上所有论文标题的特征向量集合。

3 文献信息网络语义特征提取

本文提出的基于文献信息网络语义特征的相关性搜索主要分为两个步骤:1)文献信息网络语义特征提取;2)使用步骤1)中得到的文献信息网络的语义特征进行相似性搜索。接下来详细阐述如何从大规模的文献信息网络中提取语义特征。

本文采用的数据集是目前公认的 DBLP“4-area dataset”［23］，该数据集提供了数据库、数据挖掘、机器学习和信息检索4个领域顶级会议上所有文章的相关信息。而通常文章标题是对文章主要内容的精简概括，涵盖文章大部分的语义信息，因此标题信息可以作为信息网络的重要特征。我们工作的重点则是对标题进行语义特征提取，从而利用该特征衡量文章间的相关性。

在语义特征提取过程中，本文采用目前较为成熟的Doc2Vec算法。该算法的核心是PV-DM(Distributed Memory of Paragraph Vectors)模型［17］，其结构如图3所示。对于每一个标题，它均可以通过PV-DM模型被映射成一个可以唯一表示的特征向量。PV-DM模型采用交叉训练的方式，具体步骤可分为以下两个阶段:1)训练阶段，训练模型得到词向量矩阵W，Softmax权重矩阵U，偏置向量b和标题向量矩阵D。2)推理阶段，如果发现新的标题文本，则在D中添加相应的列，在保持W、U、b不变的情况下，对D采用梯度下降法训练。

图3 PV-DM模型Fig．3 PV-DM model

算法1给出了使用Doc2Vec算法在文献信息网络中语义特征提取的详细过程。它的主要思想是根据输入的文献标题信息，生成特征向量集合并输出。

算法1 文献信息网络语义特征提取。

输入 文献信息网络G;

输出 文献信息网络语义特征向量集合V，Doc2Vec模型M。

2) P←all papers in G;

3) M←train Doc2Vec model with P;

4) for each p∈P do

5) v←M(p); //transform paper using model into vector

6) V← V∪{v}; //update V with element v

7) end for

8) return V，M

算法1的流程具体可以分为3个步骤:1)遍历文献信息网络，得到文章标题集合;2)将得到的文章标题输入到Doc2Vec算法中进行训练，得到最终模型M;3)利用模型M对属于文章标题集合中的每一个标题进行特征提取，生成特征向量并输出。

算法1将文献信息网络中的文章标题转换为特征向量集合，方便后续的语义特征相似性计算。算法1是本文进行文献网络语义特征相关性搜索的基础。

4 基于文献信息网络语义特征的相似性搜索

4．1 VPSim算法框架

基于算法1得到的文章特征向量，本文设计了基于文献信息网络语义特征的相似性搜索算法VPSim算法。该算法在考虑了元路径“APCPA”的基础上，同时也考虑了文章标题携带的语义信息对挖掘结果的影响。设想，有些作者在同一个会议上发表了文章，但是文章的研究方向可能存在很大的区别，如图挖掘、序列模式挖掘等。以往的工作仅仅考虑了元路径对作者相似性的影响，但忽略了文章本身内容也会对搜索相似的作者产生一定的影响。

同时，不同的作者在同一会议上发表文章的数目可能不统一，如何更为准确地计算两个作者间文章的相关性需要定义统一的规范。为此，本文设计了算法2来解决此问题。

算法2 作者在会议c上发表所有文章的语义相似度计算 VSim(Vp1，Vp2)。

输入 作者a1在会议c上发表的论文集合p1对应的向量集合Vp1，作者a2在会议c上发表的论文集合p2对应的向量集合Vp2;

输出 作者a1、a2在会议c上的语义相似度s。

10)return s

算法2主要是计算任意两名作者在同一会议c上发表的所有文章集合的语义相似度。步骤7)提到的sort函数采用降序排列，步骤8)的表示取p1和p2集合元素个数的最小值，步骤9)表示对前 k 个元素求和。

通过算法2计算出作者在会议上发表文章的语义相似度，根据式(2)可知，语义相似度的值表示两位作者在会议上发表的文章越相似，基于算法2并结合式(3)本文设计了VPSim算法对文献信息网络进行相似性搜索。

算法3 VPSim算法框架。

输入 文献信息网络G，参数k，网络语义特征向量集合V，查询作者a;

输出 top-k相似作者R。

17) sum2←sum2+pNuma*pNuma+pNuma'*pNuma';

18) end for

19) update simList with(sum1/sum2);

20)end for

21)sort(simList);

22)R ← simList．topK(k);

23)return R;

算法3给出了VPSim算法的基本框架。算法3主要是从大量的文献信息网络对给定的查询作者进行相似性搜索，并按照相似度对全部候选作者集合进行降序排序，最后输出top-k相似作者集合，完成相似性搜索。由于算法3处理对象为文献信息网络中所有作者，因此进行相似性搜索速度较慢，不利于实际应用，在4．2节中给出了带剪枝策略的VPSim算法。

4．2 VPSim 算法

分析算法3可知，VPSim算法在查找文章对应的特征向量以及计算候选作者与查询作者之间相似度时会耗费大量计算开销，尤其当候选作者的规模增加时，执行效率会极大降低。主要原因在于文献信息网络规模通常较大，即存在大量的候选作者。因此，本文基于如下观察设计了针对候选作者集合的剪枝策略。

定理1 在文献信息网络中，对任意作者a，C(a)表示所有与a通过“作者－文章－会议”路径连通的会议的集合，简写为“APC”即C(a)={c∈C|-APC路径连通c和a}，如果P(a)∩P(a')=，那么作者a与作者a'必定不相似。

证明 用反证法证明。若作者a与作者a'相似，那么他们之间必然存在一条满足APC的路径实例通过会议节点C使得作者a与作者a'连通。反之，若C(a)∩C(a')=，即不存在任意一个满足APC路径的会议使得作者a与作者a'关联，那么两个作者必定不相似。

根据定理1，本文设计了剪枝策略。算法4给出了带剪枝策略的VPSim算法。

算法4 VPSim算法

输入 文献信息网络G，参数k，网络语义特征向量集合V，查询作者a。

输出 top-k相似作者R。

算法4在算法3的基础上增加了对候选作者集合元素的剪枝策略，主要思想是在计算查询作者与候选作者相似度之前判断当前候选作者与查询作者所发表文章的会议是否有交集，如果没有交集则直接将当前候选作者剪掉，如果有交集则继续计算当前候选作者与查询作者之间的相似度。

5 实验

5．1 实验环境

本文设计VPSim算法使用Python语言实现，Python版本为 3．5，所有实验均在配置为 AMD FX-8300，3．30 GHz CPU，8 GB内存，120 GB+1 TB硬盘，Windows 10操作系统的PC上完成。

5．2 数据集与相关参数

实验数据采用真实世界中 DBLP的“4-area dataset”(http://web．cs．ucla．edu/～ yzsun/data/)。该数据集包括来自于4个不同研究领域的20个会议，5 000位作者和28 569篇论文。实验数据集具体特征如表2所示。需要说明的是，同一位作者可能会同时在不同领域发表论文，所以不同领域的作者数量总和会大于作者总数5000。

表2 实验数据集Tab．2 Experimental data set

在实验中涉及的Doc2Vec算法采用gensim机器学习库中的接口实现，训练Doc2Vec模型使用到的具体参数如表3所示，在没有特殊说明时，VPSim算法执行参数默认值为:k=10，即在文献信息网络中搜索出与查询作者相似度最高的10个作者。

表3 Doc2Vec训练参数Tab．3 Training parameters of Doc2Vec

5．3 语义特征向量搜索有效性验证

利用“4-area dataset”中28 569篇学术论文的标题使用Doc2Vec模型进行训练，并使用该模型将每一篇学术论文的标题转换成特征向量。然后，利用算法2对某一篇学术论文标题进行搜索，输出与之语义最为相似的top-10学术论文标题，并对实验结果进行分析，验证算法2的有效性。

由表4可以看出，与文章编号为“13624”相似的top-10的文章标题中都包含有“XML”字样，另外单词“query”也是频繁出现。从字面含义来看，10个标题表示的内容也大体相同，由此可以证明，提出的算法2是有效的，它能够通过特征向量搜索到与查询文章最为近似的文章集合，而且，文章间的相似值对以后的研究也具有一定的参考价值。

5．4 VPSim算法有效性验证

我们在APCPA路径下分别使用PathSim算法和VPSim算法对给定的查询作者进行搜索，计算出与其最为相似的top-10作者，并对实验结果进行比较分析，从而验证VPSim算法的有效性。

表4 与编号为“13624”文章相似的top-10文章Tab．4 Top-10 most similar articles to the number“13624”

观察表5可以看出，PathSim和 VPSim算法在搜索与“Jiawei Han”作者最为相似的top-10的作者在结果比较接近，在执行VPSim算法搜索出的结果中只有一名作者(Jian Per)没有出现在PathSim算法搜索的结果列表中;VPSim计算前八名的结果与PathSim计算的结果完全一致，其余作者总体排序相近，然而在计算出的相似度有细微差别。原因在于PathSim算法只是简单基于元路径“APCPA”计算得出的相似度，只是考虑了在同一个会议上发表了文章的作者是相似的，并未考虑作者发表的文章之间是否相似，即作者的研究领域是否相似。由于同一个会议中可能会收录从事不同研究方向作者的文章，因此传统的PathSim算法存在着不足。而本文提出的VPSim算法在考虑“APCPA”元路径的同时也将文章间的语义相似度考虑了进来，因此计算出的结果更接近作者真实的情况。通过表5可以得出结论，VPSim算法是有效的。

表5 APCPA路径下PathSim与VPSim计算的和“Jiawei Han”相似的top-10作者Tab．5 Top-10 most similar authors to“Jiawei Han”under meta path APCPA between PathSim and VPSim

在PathSim搜索到与“Jiawei Han”最为相似的top-10的作者中有“Nick Koudas”，而在VPSim算法搜索的结果列表中不包含“Nick Koudas”却增加了“Jian Pei”。通过对比分析“Jiawei Han”“Nick Koudas”和“Jian Pei”三位作者在会议上发表的文章，可以发现:1)三位作者的文章均都属于数据库、数据挖掘领域;2)“Nick Koudas”共发表了79篇文章，在这79篇文章的标题中共有11篇文章提到了“XML”技术;3)“Jian Pei”共发表了70篇文章，其中只有1篇文章提到了“XML”技术;4)“Jiawei Han”共发表了168篇文章，其中没有文章涉及到“XML”技术。因此可以得出结论，虽然三位作者都属于数据库、数据挖掘领域，但是他们研究方向略有区别，经过对他们发表的文章进行比较，本文认为“Jian Pei”与“Jiawei Han”更加相似。

5．5 执行效率

本节实验主要验证了VPSim算法的执行效率。本文对提出的两种算法不包含剪枝策略的VPSim-baseline算法和包含剪枝策略的VPSim-pruning算法的查询时间进行了对比。

图4给出了不带剪枝策略的VPSim算法，记为VPSimbaseline与带剪枝策略的VPSim算法，记为VPSim-pruning的效率对比，本文随机抽取了10%的数据集，即500个作者进行查询，图中横、纵坐标分别表示 VPSim-baseline算法和VPSim-pruning算法执行500次查询的执行时间。图中的直线则为使用一次函数得到的拟合曲线。由图4可以看出本文设计的剪枝策略是有效的，使得执行效率提高了约15．5%。

图4 VPSim-baseline与VPSim-pruning效率对比Fig．4 VPSim-baseline vs．VPSim-pruning execution time

表6展示了VPSim-pruning算法与PathSim算法执行效率的对比情况。该实验列出了两种算法分别执行500次随机查询所需执行时间的统计特征。观察表6可以看出，VPSimpruning算法的执行效率略低于PathSim算法，原因在于VPSim-pruning算法考虑了文献信息网络中标题的语义相似度，然而标题语义的特征向量文件较大，在执行和计算过程中会花费时间消耗，因此VPSim-pruning算法进行相似性搜索所花费的时间较长。同时，表6给出了两种算法执行查询所需时间的最大值，可以发现相差较大。分析原因如下，当作者发表的论文数量过多时，算法查找和计算所需要的时间也会相应地增加。然而VPSim-pruning算法执行时间的最小值要远低于PathSim算法，主要是由于本文设计的剪枝策略起到了作用。综合表6的结果可以看出，虽然VPSim-pruning算法的执行效率略有降低，但时间开销在可控的范围内，而且由于其考虑了文献信息网络中语义的相似性，从而极大地提高了相似性搜索的结果的准确性。

表6 VPSim-pruning算法与PathSim算法执行效率对比Tab．6 Execution time of VPSim-pruning and PathSim

图5则展示了在500次查询中，通过剪枝策略剪掉的候选作者的数量，其中横坐标表示剪枝作者的数量区间，纵坐标则表示符合该数量区间内的查询个数。分析图5可知，在500次查询实验中，VPSim-pruning算法最多可以剪掉4716个候选作者，最少也可以剪掉283个候选作者，平均可以剪枝掉2685个作者，而且大部分的剪枝数量在(2 500，3 200］区间内。虽然VPSim-pruning可以用来降低候选作者的规模，提高查询速度，但由于VPSim-pruning先需要从28 569篇论文生成的特征向量集合中计算文章的相似度，所以也花费了一定资源，导致虽然剪枝掉大量的无关作者，但执行效率提升幅度略小。

图5 VPSim-pruning算法剪枝效果统计Fig．5 Pruning results of VPSim-pruning

图6展示了VPSim算法在维度不同的特征向量中查询500次的平均执行时间折线图。由图6中的结果可以看出VPSim的执行时间随着向量维度的变大而增加。但是当特征向量的维度过低时，特征向量不能将文章标题的特征完全提取出来，从而导致搜索结果不准确，而当特征向量维度过大时，向量中会包含大量的冗余信息，从而降低搜索的效率。经过实验可知，当特征向量维度取值为128时，既能将文章标题特征准确地提取出来，同时不会降低算法的搜索效率。

图6 VPSim算法在不同特征向量维度下查询时间折线图Fig．6 Execution time of VPSim under different feature vector dimensions

5．6 可扩展性实验

为了验证VPSim算法的可扩展性，本文设计了随节点数目变化对VPSim算法执行效率影响的实验。在图7的实验中，以作者节点数目为变量，可以看出随着节点数目的增加两个算法的执行时间大致呈现相同规律变化，即线性增长，而且VPSim-pruning算法的执行时间始终要低于VPSim-baseline算法，由此可以看出带剪枝策略的VPSim-pruning算法可以高效地处理大规模文献信息网络的搜索查询。

6 结语

随着研究学者对异构信息网络的认识不断加深，如何基于其有效地开展数据挖掘工作成为研究的热点。目前，在异构信息网络进行节点相似性搜索的工作，为我们提供了一种新的研究方向。如何从大量的文献信息网络中抽取特征以及如何基于语义特征设计高效的相似性搜索算法辅助完成聚类、推荐等特定任务具有重要意义。然而目前工作仅考虑了元路径的组合，并未考虑节点本身的语义特征，降低了搜索结果的准确性。此外，候选节点的规模也会影响相似性搜索算法的执行效率，也会耗费大量的计算代价。针对这些问题，本文提出了VPSim算法，同时设计了高效的剪枝策略。最后在真实数据集上验证了VPSim算法的有效性、执行效率和可扩展性。

图7 节点数目对VPSim算法的影响Fig．7 Execution time of VPSim under different numbers of nodes

下一步，将考虑进一步提取文献信息网络中更多具有代表性的语义特征，如摘要、文章内容等，从而更全面、更真实地评价作者之间的相似性;同时，还将根据需要，考虑结合不同的元路径，进而从不同角度分析作者间关系;此外，还考虑将VPSim算法与其他应用场景结合，如影视、医学等，以便在实际的应用中进一步验证VPSim的有效性。