Open Access
Issue
JNWPU
Volume 39, Number 5, October 2021
Page(s) 1070 - 1076
DOI https://doi.org/10.1051/jnwpu/20213951070
Published online 14 December 2021

© 2021 Journal of Northwestern Polytechnical University. All rights reserved.

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

传统的推荐系统方法有基于协同过滤, 通过分析用户的历史交互数据, 猜测他们可能的共同爱好1。但是该方法有着冷启动和稀疏矩阵的问题。研究人员提出了许多解决方法, 譬如结合知识图谱、社会网络2, 通过融合侧面信息到矩阵中填补一定的数据空缺, 但还是有较大的局限性。

在推荐系统中, 基于知识图谱的推荐方法有基于嵌入的方法和基于路径的方法。2016年Zhang等人提出了协同知识库嵌入(CKE)方法, 他将协同过滤模型与嵌入结合3。2018年Wang等人提出的深度知识感知网络(DKN), 他将实体嵌入和词嵌入分为2个不同的频道, 设计1个CNN模型将其结合4。2014年Yu等人提出了异构信息网络方法5, 2017年Zhao等人提出了基于元图的推荐方法6。两者都是通过创建异构信息网络, 基于网络的潜在特征, 从中抽取元路径或者元图, 来代表用户和项目之间的关系。Wang等人同时结合基于嵌入和路径的方法提出了RippleNet7。Wang模拟水波纹传播方式, 对用户偏好进行模拟, 得到了非常好的效果。但RippleNet没有考虑到限定域知识图谱中的实体权重, 导致该模型无法得到不同权重实体的推荐结果, 没有将推荐重点放在重要程度较高的实体上, 从而降低了推荐准确度。

在复杂网络科学中, 国内外学者对节点传播能力的评估进行了大量研究, 目前常用的方法有度中心性8、介数中心性9、紧密度中心性10等。为了解决这个问题, 本文将运用复杂网络科学的方法, 把知识图谱中三元组的实体抽象为节点, 关系抽象为连边, 计算出复杂网络中实体的节点影响力, 并将其作为实体权重再放入RippleNet网络中进行计算。

1 联合复杂网络的Cn-RippleNet算法

1.1 构建基于知识图谱的复杂网络

本文使用RippleNet中的电影和书籍知识图谱7, 这个图谱数据文件是一个纯文本文件, 构成该文件的数据是实体——关系——实体的三元组。以电影知识图谱为例, 构建电影图谱复杂网络时, 将所有实体抽象为为网络的节点, 实体之间的关系作为连边, 表示节点之间的关联。建立的电影图谱复杂网络是一种无向非加权网络, 具有如下特征:

1) 网络规模巨大, 包含169 366个节点和333 543条边, 因此建立非加权网络以减少计算复杂度, 便于特征分析。

2) 只描述实体与实体之间的关联及关联间的距离, 忽略关系的方向。

因为以知识图谱构建的网络不一定是全连通网络, 导致某些节点无法参与计算其节点影响力, 所以需要消除冗余, 计算出电影知识图谱的最大连通子网。这里本文使用丁连红老师的基于集合运算的子网抽取算法(SNESO)11。该方法将电影知识图谱文件Graph作为输入, 经过子网抽取算法得到其输出最大连通子网的节点集合MaxSubNet。

算法过程如下:

1) 从电影知识图谱Graph中抽取1条拥有最大度值节点的三元组信息, 将三元组中的2个实体作为中心节点, 也就是作为最大连通子网的中心层SubNeti(这时i=1), 将此中心层加入MaxSubNet。

2) 寻找SubNeti集合的相邻节点, 即遍历Graph中的三元组(head, relation, tail), 判断其中的head, tail是否存在于SubNeti集合中。如果存在, 则表示对应head或者tail是集合SubNeti的相邻节点, 将这些相邻节点加进相邻节点集NeighborsSeti中。

3) 对比NeighborsSeti集和MaxSubNet集, 查看NeighborsSeti中是否有新的节点并不存在于MaxSubNet集中, 如果存在这样的节点, 则将NeighborsSeti并入MaxSubNet。并将SubNeti用NeighborsSeti与MaxSubNet的差集替换掉, 作为新的SubNeti, i=i+1。跳转到步骤2)。如果不存在新的节点, 则进行步骤4)。

4) 返回MaxSubNet。

此算法的关键步骤是对Graph三元组的遍历。从中心层出发, 每一次的遍历Graph, 都会得到当前层节点的所有相邻节点。由于度值较大的节点存在于最大连通子网的概率更高, 因此从度值最大的节点入手, 找到最大连通子网的概率更高。

找到最大连通子网的所有实体, 即MaxSubNet之后, 再根据MaxSubNet从电影知识图谱文件Graph中提取出最大子网的边的集合, 并且存储在GraphLink中, 最后由MaxSubNet和GraphLink生成如图 1所示结构的最大连通子网, 存储格式依然是三元组形式。可以看见, 中心层是由2个点构成, 层层扩散, 2个点的相邻实体作为第二层, 第二层的相邻实体作为第三层, 层层递归得到整个子网, 直到没有新的相邻实体为止。

thumbnail 图1

最大连通子网的模型结构

1.2 节点影响力计算

节点影响力是指在复杂网络中对所有节点进行建模分析, 对网络中具有影响力或重要的节点进行排序。一个复杂网络通常包含有重要节点, 并且少部分重要节点一般都能影响网络中的大部分节点。在不同网络中, 研究人员都会从不同尺度、方向和实验条件下建立节点影响力的测量指标, 并尽量用最精确和快速的方式找到最有影响力的节点, 并对其进行排序12

本文用已构建的最大连通子网作为一个复杂网络, 对所有三元组的节点进行影响力计算。本文分别使用使用度中心性方法8介数中心性9、紧密度中心性10对电影知识图谱网络的节点影响力进行计算, 寻找电影知识图谱中相对影响力较大的节点, 并从实验结果中分析哪种方法更加有效。

在度中心性中, 节点的度值是指连接某节点的其他节点的数量。度中心性则是根据单个节点度值大小和节点的总数来计算, 节点度值越大, 则度中心性也越大。在限定域知识图谱中, 大多数网络的度分布为幂律分布, 所以少数节点的度值较大, 而大量的节点度值较小。因此, 使用度中心性进行节点影响力计算, 能够准确区分不同度值的节点, 并赋予差异较大的权重。

由于以电影知识图谱构成的网络为无向网络, 因此具体计算公式如下

在总数g为的节点所构成的无向网络中, 单个节点i的度中心性使用CD(Ni)表示。最终得到的结果是一个比例, 范围在0.0~1.0之间。0.0表示其与任何一个节点都没有关系, 1.0表示与每一个节点都有直接关系。计算出知识图谱网络中所有节点的度中心性后, 将其对应在图谱中的实体上, 采用字典存取方式保存, 记为C。介数中心性和紧密度中心性的保存方法同上。

1.3 联合复杂网络Cn-RippleNet模型

RippleNet是模拟水波纹的传播方式, 以用户点击历史为种子, 并在限定域知识图谱上使用种子为初始点向外一圈一圈地扩散开来, 这个过程称为用户的偏好传播。该模型认为种子外圈的项目依然属于用户的潜在偏好, 因此在刻画时也要将其考虑。以下是对RippleNet模型进行改进的地方:

Cn-RippleNet的整体框架如图 2所示, 通过上部分实验得到当前Hop的Ripple set三元组中头部head的度中心性, 且作为对应head的权值。然后在对Ripple set进行embedding时, 将Ripple set的嵌入矩阵与head对应的权值矩阵中对应元素各自相乘, 得到带有权重的Ripple set embedding。之后按照RippleNet模型进行用户embedding和项目embedding计算, 根据Hop次数进行偏好传播的迭代, 最终得到带有实体权重的最终结果。

Cn-RippleNet是模拟水波纹的传播方式, 以用户点击历史为种子, 模拟偏好传播, 对用户偏好节点添加影响力, 再将其作为用户embedding与项目embedding进行计算。在整个Cn-RippleNet模型中, 把用户u和项目v分别作为模型的输入, 把用户u可能会点击项目v的预测概率作为最终输出。每一个用户u, 都会根据其点击历史vu构建属于他的Ripple set, 其点击历史作为偏好传播的种子。然后沿知识图谱的关系向外扩充形成对应Hop的Ripple set Suk(k=1, 2, …, H)。Ripple set Suk是用户点击历史vu进行偏好传播后的三元组。Ripple set与项目embedding交互, 将用户u与项目v的信息相融合, 然后将这些信息组合起来形成最终的用户embedding。最后, 使用用户u和项目v的embedding来计算最终的预测概率ŷuv

首先, 在知识图谱中表示用户历史点击数据vu, 由此来表示基于用户历史vu的偏好相关实体, 在RippleNet中, 通过循环递归的方法, 为用户u创建了偏好相关实体集, 如下所示

这些实体可被视为用户在知识图谱中依据历史点击vu的偏好扩展。在给出相关实体的定义后, 本文定义用户u所有的K-hop Ripple set如下

在每一次Hop中, 都会将Ripple set中头实体的度中心性Ci作为权值与Ripple set的嵌入矩阵ei进行矩阵对应项乘积运算, 得到带有权重的hi。如下所示

之后将项目v的项目embedding和用户u的Ripple set Su1进行计算。项目v分别与Su1中的头部hi和关系ri计算每个三元组(hi, ri, ti)的相关概率pi

相关概率可以看做项目v和头实体hi在关系空间中Ri的测度。因为不同种类的关系类型肯定会计算出不同相似性, 所以关系数据Ri也参与了相关概率的计算。获得相关概率后, 将Su1中的所有尾实体ti乘以相应的相关概率, 并且返回向量ou1ou1可以看作是用户u对项目历史点击记录的第一次响应, 用来组成用户u的embedding。

最后, 结合用户embedding和项目embedding, 输出预测的点击概率

thumbnail 图2

联合复杂网络Cn-RippleNet模型

2 实验设置及结果分析

2.1 数据集

在本文的实验中, 利用以下2个数据集进行实验: MovieLens-1M和Book-Crossing分别是在电影推荐和图书推荐中经常用到的数据集。其中电影数据集MovieLens-1M包含网站上真实用户的上百万个评分。Book-Crossing同样也包含百万本图书, 并且所有图书都在图书交流社区中获得用户的评分。本文采用RippleNet模型中为每个数据集所构造的知识图谱。

表1

2个数据集的基本统计

2.2 实验环境

表 2中给出了Cn-RippleNet模型完整的参数设置, 其中d表示项目和知识图的嵌入维数, H表示Hop的次数,l表示学习率。

本文将分别对每个数据集进行处理, 将整个数据集分为训练集、评估集和测试集3个部分。数据占比为6∶2∶2。每个数据集进行5次实验, 并以其平均值作为最终结果。

表2

Cn-RippleNet模型的超参数

2.3 评价指标

本文使用ACC(Accuracy)和AUC(Area Under Curve)作为实验的评价指标。AUC来源于ROC, 也就是ROC曲线图下半部分的面积。其值小于1。ROC曲线图用来判断二值分类器的优劣, 得到的曲线图横坐标为FPR(false positive rate), 纵坐标为TPR(true positive rate), 将这些坐标对连接起来就形成了ROC曲线图。最后计算AUC面积得到一个0.5~1的值, AUC越大分类效果就越好。

2.4 实验结果

本文构建了电影和书籍的知识图谱, 使用基于集合运算的子网抽取算法构建了复杂网络。下图是最大联通子网的部分三元组数据。head表示头, rel表示关系, tail表示尾。为方便使用和统计, 实体和关系都使用序号来表示。

通过对节点影响力的计算, 得到了子网中每一个实体的度中心性。部分电影知识图谱实体的度中心性结果如下:

本文测试了不同参数时得到的结果, Cn-RippleNet模型在参数d=16, l=0.02, λ2=0.02的时候表现最佳, 得到的AUC和ACC都取得令人满意的结果。如表 5所示, 相比其他主流基于知识图谱的推荐模型, Cn-RippleNet在2个数据集上都取得了最好的性能。其原因在于Cn-RippleNet是将基于路径和基于嵌入的方法相结合, 利用知识图谱的侧面信息和节点影响力, 且对网络中的实体赋予了权重, 能够给予推荐系统更好的推荐, 得到更加准确的推荐结果。

通过表 5的结果可以发现, 对比CKE的表现来看, Cn-RippleNet在AUC和ACC的评价指标下分别高出了13个百分点和12个百分点, 这是因为CKE是将知识图谱同协同过滤方法融合, 只是利用了图谱的结构知识特征, 没有考虑图谱的路径。DKN在电影和图书推荐方面表现不尽人意, 被Cn-RippleNet模型分别高出28个百分点和26个百分点。这是因为DKN更注重文本内容, 需要有多个实体才能保证预测的准确率。对DKN来说数据集的实体名字不够长, 就无法提供有用的信息, 得到的结果也更加不准确。Cn-RippleNet通过结合基于路径的方法, 得到了节点影响力克服了这个问题, 因此Cn-RippleNet也能在数据长度不够的情况下达到高性能。由于用户定义的元路径很难是最佳的, 所以PER在电影和书籍改编上的表现并不令人满意, 而Cn-RippleNet融合知识图谱实体的路径, 达到了更高的性能。在这2个数据集中, Cn-RippleNet的性能最好。对比RippleNet, 在MovieLens-1M数据集中, 改进后的Cn-RippleNet在AUC和ACC的评价指标下都高出了1个百分点, 而在Book-Crossing数据集中, 指标高出了2个百分点。这表明考虑节点影响力后的RippleNet的推荐效果更加准确。因此本文认为Cn-RippleNet在依据路径融合节点影响力的方法后效果更好。

在实验时, 考虑到RippleNet和Cn-RippleNet可能由于模型超参数的不同导致实验结果不严谨, 因此本文将添加1组对照试验, 将2个模型的超参数按照表 2设置, 并将RippleNet的实验结果记为SSP-RippleNet。通过表 5的结果, 发现在相同超参数下, Cn-RippleNet对比SSP-RippleNet的结果依然更优。在MovieLens-1M数据集中, AUC和ACC的指标分别高数3个百分点和4个百分点, 而Book-Crossing数据集中, AUC和ACC分别高出4个百分点和5个百分点。对比相同超参数的RippleNet模型, Cn-RippleNet依然能够取得更好的结果。

同时由图 3可以看出, Hop的值在2或者3时, 效果最佳, 说明Hop数对与性能的影响并不是越高越好。从图 4可以看出, 同样Dim也不是值越高效果越好, Dim在16时模型性能最优。表 6可以看出在这2个数据集下, 在度中心性、介数中心性、接近中心性的实验对比中, 度中心性的各项结果都优于其他。这表明在确定权重的方法中, 度中心性是最能体现2个数据集中网络节点的重要程度。因此对节点影响力的评价选择, 需要根据具体网络具体分析, 并且要通过实验来确定。

表3

最大连通子网的部分数据

表4

最大连通子网的部分度中心性

表5

不同模型的AUC和ACC的结果

thumbnail 图3

不同Hop的AUC值

thumbnail 图4

不同Dim下的AUC值

表6

不同中心性的AUC和ACC的结果

3 结论

本文提出了一种融合复杂网络节点影响力的Cn-RippleNet推荐模型。对领域知识图谱进行了网络化, 计算了知识图谱中实体的影响力, 并将其融入知识图谱的网络中, 使得推荐结果更加符合人们的偏好, 解决了RippleNet没考虑关键节点对推荐结果的影响的问题, 从而增加了推荐精度。实验表明, 通过节点影响力改进的Cn-RippleNet算法能够提高推荐算法的结果。下一步可以考虑将知识图谱的最大联通子网的关系细化, 对不同的关系赋予不同的权重。也可以考虑更加新颖的节点影响力算法。

References

  1. Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8) : 30–37. [Article] [Google Scholar]
  2. Jamali M, Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C]//Proceedings of the fourth ACM conference on Recommender systems, 2010: 135–142 [Google Scholar]
  3. Zhang Fuzheng, Jing Nicholas, Lian Defu. Collaborative knowledge base embedding for recommender systems[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016: 353–362 [Google Scholar]
  4. Wang Hongwei, Zhang Fuzheng. DKN: deep knowledge-aware network for news recommendation[C]//Proceedings of the 2018 World Wide Web Conference, 2018: 1835–1844 [Google Scholar]
  5. Yu Xiao, Ren Xiang, Sun Yizhou. Personalized entity recommendation: a heterogeneous information network approach[C]//Proceedings of the 7th ACM International Conference on Web Search and Data Mining, 2014: 283–292 [Google Scholar]
  6. Zhao Huan, Yao Quanming, Li Jianda. Metagraph based recommendation fusion over heterogeneous information networks[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017: 635–644 [Google Scholar]
  7. Wang Hongwei, Zhang Fuzheng, Wang Jialin. Exploring high-order user preference on the knowledge graph for recommender systems[J]. ACM Transactions on Information Systems, 2019, 37(3) : 1–26 [Google Scholar]
  8. Freeman L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3) : 215–239. [Article] [Google Scholar]
  9. Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1) : 35–41. [Article] [Google Scholar]
  10. Sabidussi G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4) : 581–603. [Article] [Google Scholar]
  11. Ding Lianhong, Sun Bin, Shi Peng. Empirical study of knowledge network based on complex network theory[J]. Journal of Physics, 2019, 68(12) : 324–338 [Article] (in Chinese) [Google Scholar]
  12. Fan Yanni, Liu Sanyang, Bai Yiguang. Identifying critical nodes in complex networks based on multi-scale centrality algorithm[J]. The Practice and Understanding of Mathematics, 2020, 50(10) : 159–167 [Article] (in Chinese) [Google Scholar]

All Tables

表1

2个数据集的基本统计

表2

Cn-RippleNet模型的超参数

表3

最大连通子网的部分数据

表4

最大连通子网的部分度中心性

表5

不同模型的AUC和ACC的结果

表6

不同中心性的AUC和ACC的结果

All Figures

thumbnail 图1

最大连通子网的模型结构

In the text
thumbnail 图2

联合复杂网络Cn-RippleNet模型

In the text
thumbnail 图3

不同Hop的AUC值

In the text
thumbnail 图4

不同Dim下的AUC值

In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.