基于用户导向的异构网络语义预测算法研究

王少峰，郭俊霞，卢 罡

北京化工大学 信息学院，北京 100029

1 引言

随着信息网络的快速发展，对信息网络的分析已成为一个重要的研究方向，包括信息检索、数据挖掘、社交网络、关系预测等等。信息网络是一种将有向图作为基本数据结构的网络，它对结点类型和关系类型进行了明确的区分。如果它只包含一种类型的结点和一种类型的关系，则称为同构网络；如果包含多种类型的结点和多种类型的关系，则被称为异构网络。现实的信息网络往往很复杂，包含很多种类型的结点和关系，所以对异构网络的研究十分重要。

随着异构网络的信息量与日俱增，用户在搜索感兴趣的信息时耗费大量时间与精力。相似性搜索作为异构网络数据挖掘的一种基本方法，能够帮助用户快速准确地搜索所需要的信息。为此，有许多相似性度量方法被提出，大致可以分为以下三类：（1）基于结点特征的相似性度量[1-2]：网络中的结点包含一系列特征，结点间的相似性可以通过特征相似性来进行计算。这些方法适用于特征丰富的相同类型结点，不能用于计算不同类型结点间的相似性。（2）基于图特性的相似性度量[3-4]：通过特征子图、分类图等图拓扑概念计算相似性，将结点间的相似性转化为与结点有关的图结构相似性计算得到。（3）基于元路径的相似性度量[5-7]：通过递归地计算结点邻居间相似性，最终得到全局相似性。如文献[5]基于“如果两个结点和被其相似的结点所引用，那么这两个结点也相似”的思想，提出SimRank算法。这类算法是基于结点结构的上下文，从全局路径出发计算相似性，需要计算的路径数非常多，带来计算量大的问题，无法扩展到大规模数据集中。

在相似性搜索中，基于用户导向去预测与用户搜索相关的路径，是减少路径选择数的重要参考依据。文献[8]中对于需要聚类的目标，用户只需要提供小部分与目标相关的特征集，便可根据该特征集找到相似的结点。文献[9]通过考虑用户对不同搜索结果的满意程度，建立修改度量系数的目标函数，从而实现微博中体现用户兴趣的主题时序相似性计算，为用户提供更好的搜索结果。针对基于元路径的相似性搜索算法普遍存在计算量大的问题，基于利用用户导向预测与用户搜索相关的路径，以减少路径数的考虑，本文拟进行基于用户导向的语义预测算法研究。本文的主要贡献为：

（1）从图拓扑结构的角度出发，提出一种基于用户导向进行语义预测的算法。该算法可用于同类型和不同类型结点间的语义预测，并通过语义预测减少了元路径选择数，缓解了计算量大的问题。并且不需要用户具备相关专业知识，对用户是友好的。

（2）为在多语义路径上计算相似性提供一种实现方法。本文根据预测过程所得到的概率作为多语义路径的权重，对多语义路径上的相似性分数进行加权组合。

（3）本文实验表明，通过与实际情况进行比较，本文算法在对称与非对称路径上均能够对结点间的语义进行准确预测，并且在多语义环境下的排名结果质量明显好于对应算法。

2 相关研究

针对基于元路径的相似性度量方法存在路径选择数多的问题，已有一些研究成果，包括针对SimRank的算法改进[10-11]，路径依赖随机行走[12]法等。文献[10]通过理论上界分析，将每次迭代计算后不可能进入Top-k候选集的节点对锁定，从而在精确度损失不大的情况下大幅提升计算时间。文献[11]提出SimRank的线性递归表达式，结合蒙特卡洛模拟方法、距离的衰减特性、适应性选样技术使得搜索的时间复杂度独立于图的规模，方便进行并行计算，使得计算大规模的图成为可能。但这些算法只能应用于同构图中，无法应用于异构网络计算不同类型结点间的相似性。文献[12]提出一个路径依赖随机游走（PCRW）算法，用于度量一个由文献库中元数据组成的有向图中的结点相似性。其相似度被定义为一个已知的约束随机行走的组合，每个约束只遵循远离搜索结点的边标签的一个特定序列。该算法具有非对称属性，可用于计算不同类型结点间的相似性。也因为其非对称属性，不能用于计算同类型结点相似性。

还有一些文献提出根据用户的专业知识来选择与搜索相关的某一条具体的路径，即单路径。文献[6，13]提出PathSim算法用于计算相同类型结点间的相似性。该算法基于单个对称元路径，双向随机游走，通过可交换矩阵，计算相同类型结点间的相似性。用户需要根据自己掌握的相关领域知识来选择单个路径。该算法只能用于计算同类型结点，不能用于不同类型结点。文献[7]提出HeteSim算法用于计算不同类型结点间的相似性。该算法基于单个对称元路径，双向随机行走，计算异构网络中不同类型实体间的相似性。同样的，用户需要根据自己掌握的相关领域知识来选择单个路径。文献[14]提出在HeteSim基础上的矩阵分解方法，可以得到结点的软聚类或硬聚类结果，以此进一步缩小路径的选择范围。在这些方法中，用户可以根据自己的专业知识来选择相应的单路径，减少了路径选择的数量，减小了计算量，但要求用户对相关领域专业知识的理解较高，具有一定局限性。

通过引入用户导向，预测与用户搜索相关元路径的方法[15-20]也可以用来改善路径选择数大的问题，而且在用户满意度方面表现更好。其中包括几类算法：利用种子的半监督算法[15-16]、关系预测算法[17-18]，和监督与半监督组合算法[19-20]。利用种子的半监督算法是在半监督的基础上，将用户提供的标签样例和未提供标签的样例结合起来，进一步提高检索效率。关系预测算法是在用户输入搜索和导向的情况下，根据输入之间的关系，利用建好的预测算法去预测搜索与路径之间的相似概率。监督与半监督组合算法分别克服了监督学习需要大量标注语料以及半监督学习标注语料受限于一定应用环境的缺点，可以在少量标注语料的情况下方便快捷地移植到其他标注语料受限的应用环境中。但这些算法主要适用于同构网络或异构网络中的同类型结点。在异构网络不同类型结点上的语义预测仍有待进一步研究。

文献[4]利用最大公共子图和最小公共超图等图结构信息的方法与PathSim的结果集合有相当数量是重合的，表明了该文所提方法确实能有效度量各节点的相似程度。在文献[3]中进一步表明，利用类图信息所得到的结点相似性的准确性相较基于元路径所得实体相似性的准确性要好很多。由于利用图的结构信息不需要用户的专业知识，并且图中可以包含有不同类型的结点，再基于以上文献的实验结果，可以得出以下结论：利用图的结构信息来对不同类型和相同类型结点间的语义进行预测是可行的。

本文从用户导向的角度出发，提出一个面向异构网络、基于用户导向的语义预测算法。该算法不仅考虑同类型结点，同时也考虑不同类型结点。该算法不需要用户具备一定的专业知识，而是利用图的结构信息，计算用户搜索匹配各相关路径的概率，通过选择概率最大的路径，可以减少候选路径数，从而减小计算量。同时，可预测得到各相关路径的概率，为多语义环境下计算相似性提供一种具体实现方法。

3 用户导向-语义预测算法

由于异构网络中语义的多样性，用户搜索往往含有歧义性，所以需要更好地理解用户搜索意向，以减少路径选择数。例如，在图1所示的网络中，作者和会议之间可以通过“Author-Paper-Venue-Conf”（APVC），“Author-Paper-Venue-Subj-Paper-Venue-Conf”（APSPVC）等路径来连接。其中，APVC路径表示作者写的文献发表在会议上，着重于作者参加的会议；而APSPVC路径表示在会议中发表的文献，这些文献与作者发表的文献有相同主题，着重于与作者文献有相同主题的其他会议文献。所以，在度量结点相似性之前，先进行语义预测，降低语义歧义性，可减少候选路径数。

图1 ACM数据集网络模式

3.1 异构网络的相关定义

Han和Yu等人在文献[21]和文献[22]中正式提出和倡导信息网络这一概念，并探索信息网络的元结构，即网络模式，同时提出元路径的概念。利用元路径所包含的语义来查找用户搜索的信息，是相似性搜索领域一个主要的研究方向。本文在前人提出的信息网络、网络模式、元路径和基于用户导向的相似性搜索定义基础上，提出以下两个定义。

定义1路径回溯

在一个数据集中，对于一个搜索q，在某个语义下，可以得到一系列相关或不相关结果集，则训练集可以形式化为：D=(qii=1,2,…,N ，其中是正相关结果集，q-i是不相关结果集。直观上，可以知道：有相似结果的搜索应该有相似的语义，而有不相似结果的搜索应该有不同的语义。对于D中的一个候选结果r（用户导向），正相关搜索可以收集并定义为不相关搜索为。则该候选结果r和正相关搜索所对应的语义，就是用户搜索隐含的候选路径。

定义2正则路径数

本文定义正则路径数来表示网络中两个结点的整体连通性，表示如下：

其中P(qi,ui)表示在候选路径下搜索qi到用户导向ui的路径实例数，P(qi,)表示在候选路径下从结点qi开始的路径实例数，P(, ui)表示在候选路径下到达结点ui的路径实例数，l表示路径长度。

3.2 语义预测过程

在进行语义预测前，首先准备一个数据集，数据集是以搜索的格式准备的。然后对这个数据集使用路径回溯方法，得到与用户搜索相关的所有候选路径。在此基础上，统计搜索和导向在各候选路径上的路径实例数。然后将各路径上的路径实例数代入公式（1），得到对应路径上的正则路径数。

由于语义之间的含义不同，可以把语义预测看作一个多分类问题。Softmax模型是logistic回归模型在多分类问题上的推广，可以用来对语义预测问题进行概率建模。在多分类问题中，类标签可以取两个以上的值。本文中，自变量是语义路径的正则路径数，因变量是搜索匹配该语义路径的概率。具体形式如公式（2）所示：

p(S=j|qi,ui,θ)表示基于用户导向ui和搜索qi属于语义 j的概率，k是对应语义数，其中xji是路径 j的正则路径数对概率分布进行归一化，使得所有概率之和为 1。

为了得到搜索匹配各候选路径的最优概率θj，本文训练模型参数θ，使其能够最小化代价函数 ：

1{值为真的表达式}=1，1{值为假的表达式}=0。

对于J(θ)的最小化问题，由于J(θ)不是严格非凸的，回归中对参数的最优化求解不只一个。为了求出唯一解，使得J(θ)成为一个严格凸函数，通过添加一个权重衰减项来修改代价函数。有了这个权重衰减项以后(λ＞0)，代价函数就变成了严格的凸函数，这样就可以保证得到唯一的解。并且因为J()θ是凸函数，利用梯度下降法等优化算法可以保证收敛到全局最优解。现在代价函数变为：

为了使用优化算法，需要求得这个新函数J()θ的导数，如下：

有了上面的偏导数公式以后，就可以将它代入到优化算法中。本文使用梯度下降法来实现最优概率θj。在梯度下降法的标准实现中，每一次迭代需要进行如下更新：

当迭代一定次数后，得到最优的θj，进而得到最优θ。其中α表示沿梯度下降方向的步长。在得到最优的θ后，选择最大的分量θj，利用相似性算法公式对相应的路径进行计算，给出最终结果。

3.3 算法描述

首先基于用户搜索q和导向u，得到各候选路径的正则路径数，然后利用softmax函数得到搜索q匹配各候选路径的初始概率。再利用优化算法求出搜索q匹配各候选路径的最优概率，最后代入softmax函数得到最终概率。具体过程如算法1所示。

算法1语义预测算法

输入：用户搜索q，用户导向u，图S=( )A,R

输出：搜索q匹配相关语义的概率列表result

1. for eachq，u do

2. 路径回溯（q，u）->Pl(q , u)；

3. Pl(q ,u)->xl(q , u)；

4. end for

5.for allxl(q ,u ) do

6. p(S=j|q,u,θ)；

7.end for

8.for each xl(q ,u ) do

9. J(θ)；

10. repeat

11. ∇θjJ(θ)；

12. θj=θj-α∇θjJ(θ)；

13. until迭代次数>107

14. end

15. end for

16.for allθjdo

17. p(S=j|q,u,θ)；

18.return result{θopt}其中，Pl( )

q,u是在路径 j上的路径实例数。p(S=j|q,u,θ)表示基于用户导向u，搜索q属于语义 j的概率。∇θjJ()θ是利用梯度下降法来求最优概率θopt。

4 实验

4.1 实验数据集

本文使用DBLP数据集作为实验对象，其中包含1 928 000个文献，109 000个作者，1 000个会议和193 000个关键字，以及总共4 244 000个关系。它的网络模式如图2所示。

图2 DBLP网络模式

4.2 实验设计

考虑到实验环境对路径步长的影响，为了能得到有效的正则路径数，本实验的路径步长控制在4步之内，路径语义如表1所示。

为了验证本文提出算法的有效性，设计如下三个实验问题：

（1）基于用户导向的语义预测算法能否准确预测用户搜索意向

表1 DBLP数据集4步长路径语义表

预测算法通过所给的搜索和导向，得到搜索属于各候选路径的最终概率。当选择概率最大的路径时，与实际选择情况进行比较，验证是否能准确预测。

（2）多语义路径下的排名是否比单语义路径的排名更准确

为了得到更为准确的结果，文献[7]和文献[13]都曾提出在多语义环境下计算相似性，但没有给出解决方法。本文利用用户搜索与导向在各语义路径下的概率作为该路径下的权重，然后将相似性算法在各相关路径上的相似性分数进行加权组合，得到多语义路径上的相似性分数，再与原相似性算法的相似性分数进行比较。

（3）本文算法与对应相似性算法的效率对比

本文实验中将对本文算法与对应算法的效率进行实验比较与分析。

4.3 实验结果分析

4.3.1 算法时间复杂度分析

本文算法主要分为路径回溯、语义预测两部分。在路径回溯部分，由于是对搜索和用户导向结点双向回溯，算法的时间复杂度为O()n2。在语义预测部分，用到的是调整的softmax函数，时间复杂度为O()n。在对该算法的参数θ进行优化时使用了梯度下降法，梯度下降法的时间复杂度为O(tn)，t表示迭代次数。所以本算法的时间复杂度为O(n2+(t +1) n)，而HeteSim算法的时间复杂度为O(k dn2T4)，其中k表示迭代次数，d表示结点出度和入度乘积的平均值，T表示结点类型数；PathSim算法的时间复杂度为O(n2)。

4.3.2 实验参数的选择

迭代步长只影响速度，不影响收敛性。在梯度下降法中，往往需要设置一个合适的步长。步长设置太大，使得要估计的系数在迭代过程中不断增大，最后趋于无穷大，程序陷入死循环或溢出；太小可能永远到不了最优点。由相关证明文件（http://research.cs.buct.edu.cn/WDBLab/Appendix.pdf）可知，当假定正则项系数λ=1时，步长α在（0，2）范围内对所有预定义路径来说是比较合适的。并且迭代达到1 000万次时，迭代停止。本实验中，设定迭代步长的初始值为0.1（因为各路径的初始概率值就比较低，步数设置太大时最优解会出现负数，也就意味着步数太大导致越过了最优解），每次迭代步长的值由下面公式确定：

α=α*0.8

4.3.3 与其他算法的比较

PathSim[13]和HeteSim[7]是异构网络中两个经典的相似性搜索算法。它们都是基于单个元路径，计算异构网络中实体间的相似性。对于一个对称元路径P=(Pl)，算法PathSim和HeteSim都可以应用在该元路径上，而对于非对称元路径，HeteSim可以应用。本实验中，分别在对称与非对称元路径上与上述算法进行比较。

在对称路径上，给出一个用户搜索Christos Faloutsos和导向Spiros Papadimitriou，结果如表2和表3所示。

表2 路径APA上，用PathSim得到的Top-10与Christos Faloutsos最相似的作者

表3 路径APA上，用HeteSim得到的Top-10与Christos Faloutsos最相似的作者

现实中，Spiros Papadimitriou是Christos Faloutsos的共作者，所以用户搜索隐含的语义是找到Christos Faloutsos的其他共作者。所以PathSim和HeteSim算法所走路径都是APA。而在用预测算法进行预测时，在定义路径APA、APVPA和APTPA上的归一化概率如表4所示。其中概率最大的路径为APA，概率为0.433 8。选择概率最大路径为APA，与PathSim和HeteSim相符；而当选择组合路径时，各路径权重即为上述概率。

表4 基于不同导向，作者Christos Faloutsos在对称元路径上的匹配概率

而对于同一个搜索Christos Faloutsos，此时给出的导向是Philip S.Yu，结果如表5和表6所示。

现实中，Philip S.Yu是在数据挖掘领域与Christos Faloutsos名声相当的作者，所以用户搜索隐含的语义是找到与Christos Faloutsos在数据挖掘领域名声相当的其他作者。所以HeteSim算法所走路径是APVPA。而在用预测算法进行预测时，在定义路径APA、APVPA和APTPA上的归一化概率如表4所示。其中概率最大的路径为APVPA，其概率为0.581 5。选择概率最大路径为APVPA，与PathSim和HeteSim相符；而当选择组合路径时，各路径权重即为上述概率。

表5 路径APCPA上，用PathSim得到的Top-10与Christos Faloutsos最相似的作者

表6 路径APVPA上，用HeteSim得到的Top-10与Christos Faloutsos最相似的作者

在非对称路径上，给出一个用户搜索Christos Faloutsos和导向KDD，结果如表7所示。

表7 路径APC上，Top-10与作者相关的会议

现实中，KDD是Christos Faloutsos主要参加的会议，所以HeteSim可以根据用户的专业知识去选择特定的元路径APC。而在用预测算法进行预测时，在定义路径APC，和APTPC上的归一化概率如表8所示。其中概率最大的路径为APC，其概率为0.600 3。概率最大路径为APC，与HeteSim相符；而当选择组合路径时，各路径权重即为上述概率。

表8 基于用户搜索Christos Faloutsos和导向KDD的各路径概率

根据以上实验，可以得出下面两个结论：

（1）基于用户导向，由语义预测算法得到概率最高的路径与实际选择的路径是相同的，说明预测算法能够准确地对用户搜索意向进行预测。

（2）本实验利用用户搜索与导向在各语义路径下的概率作为该路径下的权重，然后将PathSim和HeteSim在各相关路径的相似性分数进行加权组合，分别与PathSim和HeteSim进行比较。由表2和表3可以看到，当给出用户搜索Christos Faloutsos和导向Spiros Papadimitriou时，多语义路径下的得分比PathSim和HeteSim高。但在给出用户搜索Christos Faloutsos和导向Philip S.Yu时，得分比PathSim和HeteSim低。这是由于多语义路径下对语义的区分度不高，势必会将相关语义的得分拉低，同时将不太相关语义的得分拉高，造成了多语义路径得分并不一定总是比单语义路得分高。同时也说明了相似性得分只是评价相似性度量的一个方面，还需要对实际的排名质量进行比较。

4.3.4 排名的质量比较

为了比较排名结果的质量，本文使用DCG指标[23]来评价本文方法和其他算法分别在对称路径APA、APTPA、APCPA和非对称路径APC，APTPC上搜索Christos Faloutsos的表现。

在本文实验中，将实验结果按1～10进行打分。10分表示排名最好的结果，1分表示排名最差的结果。

在APA路径上，PathSim和HeteSim与本文方法的DCG分数如图3所示。

图3 APA路径上，本文方法与PathSim、HeteSim的DCG分数

在APCPA路径上，PathSim和HeteSim与本文方法的DCG分数如图4所示。

图4 APCPA路径上，本文方法与PathSim、HeteSim的DCG

在APC路径上，HeteSim和本文方法的DCG分数如图5所示。

图5 APC路径上，HeteSim和本文方法的DCG分数

可以看到，在对称路径和非对称路径上，本文方法在原有相似性算法的基础上，利用多语义环境下的相似性分别与PathSim和HeteSim进行了比较，都表现出了较好的性能。说明虽然多语义路径下的得分不一定比单语义路径得分高，但排名质量是好于单语义路径的。

4.3.5 算法效率对比

为了比较本文算法和对应算法的效率，本文将在对称路径和非对称路径上搜索Christos Faloutsos的运行时间进行比较。

在APA路径上，基于用户导向Spiros Papadimitriou，PathSim和HeteSim与本文方法的运行时间如图6所示。

图6 APA路径上，本文方法与PathSim、HeteSim的运行时间

在APCPA路径上，基于用户导向Philip S.Yu，PathSim和HeteSim与本文方法的运行时间如图7所示。

在APC路径上，基于用户导向KDD，HeteSim和本文方法的运行时间如图8所示。

图7 APCPA路径上，本文方法与PathSim、HeteSim的运行时间

图8 APC路径上，本文方法与PathSim、HeteSim的运行时间

由以上实验可以看到，本文算法的运行时间高于对应算法。这是由于本文首先基于用户导向对搜索在各语义路径下的匹配概率进行预测，并将概率作为对应路径上的权重，然后利用相似性算法在各对应路径上计算得到的相似性分数进行加权组合，即本文方法的运行时间包括语义预测和相似性计算两部分。而且本文算法在预测部分为了得到准确的预测结果，需要进行迭代更新，当迭代次数逐渐增加时，本文算法与对应算法之间的运行时间差距会逐步增大。因此需要在运行时间和结果准确性之间进行权衡。

5 结束语

本文提出的用户搜索导向-语义预测算法，可用于同类型和不同类型结点间的语义预测，能够较好地预测用户搜索的语义，且不需要用户具备相关专业知识。并且本算法减少了元路径选择数，以一种新的方法缓解了计算量大的问题。本文根据预测过程所得到的概率作为多语义路径的权重，为多语义环境下的相似性计算提供了具体的实现方法。实验表明，本文提出的算法能够准确对同类型和不同类型结点间语义的预测，在排名质量上好于对应的相似性算法。