使用子图推理实现知识图谱关系预测

doi:10.3778/j.issn.1673-9418.2104084

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (8): 1800-1808.DOI: 10.3778/j.issn.1673-9418.2104084

使用子图推理实现知识图谱关系预测

于慧琳, 陈炜, 王琪, 高建伟, 万怀宇

北京交通大学计算机与信息技术学院，北京 100044

收稿日期:2021-03-26 修回日期:2021-05-31 出版日期:2022-08-01 发布日期:2021-06-03
作者简介:于慧琳（1997—），女，黑龙江佳木斯人，硕士研究生，主要研究方向为知识图谱推理、信息抽取。
陈炜（1994—），男，广西合浦人，博士研究生，主要研究方向为知识图谱推理与应用。
王琪（1997—），女，河北衡水人，硕士研究生，主要研究方向为知识图谱问答与推荐。
高建伟（1995—），男，山西定襄人，硕士研究生，主要研究方向为知识图谱、信息抽取。
万怀宇（1981—），男，湖北宣恩人，博士，副教授，CCF会员，主要研究方向为社交网络挖掘、文本信息抽取、用户行为分析、时空数据挖掘。
基金资助:
国家重点研发计划(2018YFC0830200)

Knowledge Graph Link Prediction Based on Subgraph Reasoning

YU Huilin, CHEN Wei, WANG Qi, GAO Jianwei, WAN Huaiyu

School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China

Received:2021-03-26 Revised:2021-05-31 Online:2022-08-01 Published:2021-06-03
About author:YU Huilin, born in 1997, M.S. candidate. Her research interests include knowledge graph reasoning and information extraction.
CHEN Wei, born in 1994, Ph.D. candidate. His research interests include knowledge graph reasoning and application.
GAO Jianwei, born in 1995, M.S. candidate. His research interests include knowledge graph and information extraction.
WAN Huaiyu, born in 1981, Ph.D., associate professor, member of CCF. His research interests include social network mining, text information extraction, user behavior analysis and spatial-temporal data mining.
Supported by:
the National Key Research and Development Program of China(2018YFC0830200)

摘要/Abstract

摘要：

知识图谱中的关系推理旨在从现有数据中识别和推断出新的关系，为许多下游任务提供知识服务。当前的许多研究工作主要将实体与关系映射到向量空间中或对实体之间的路径进行搜索来解决关系推理问题。这些方法都只考虑了单一路径或一阶信息对关系推理的影响，忽视了广泛存在于实体之间的更复杂的关系信息。提出了一种新颖的基于子图的知识图谱关系推理方法，结合表示学习与路径推理的优势，使用具有丰富信息的子图结构获取实体对的邻域结构信息，实现实体之间的关系预测。首先将实体对之间的路径扩展为子图，分别从实体层面和关系层面出发，构建节点子图和关系子图;再结合图嵌入表示与图神经网络计算子图的高阶特征，从而获得更丰富的实体关系特征;最后从子图高阶特征中获取实体对的邻域结构信息，实现实体之间的关系预测。实验结果表明，在两个基准数据集上，该方法优于现有的其他基于推理的关系预测方法。

关键词: 知识图谱, 连接预测, 子图构建, 图神经网络

Abstract:

Relationship prediction in knowledge graph aims to identify and infer new relationships from existing data, and provides knowledge services for many downstream tasks. At present, many researches solve the link prediction problem between entities by mapping entities and relations into a vector space or searching the paths between entities. These methods only consider the influence of single path or first-order information but ignore more complex relation information between entities. Therefore, this paper proposes a novel link prediction method based on subgraph reasoning in knowledge graph, uses the subgraph structure to obtain the entity pair neighborhood structure information, combines the advantages of representation learning and path reasoning, and realizes the relationship prediction between entities. This paper first extends the paths between entities to subgraphs, constructs node subgraph and relationship subgraph from entity level and relationship level respectively, then combines the graph embedding representation with the graph neural network to calculate the subgraph features, to get richer entity characteristics and relationship characteristics. Finally, this paper calculates the neighborhood structure information of entity pairs from the subgraph structure to conduct link prediction between entities. Experimental results demons-trate that the proposed approach outperforms other reasoning-based link prediction methods on two benchmark datasets.

Key words: knowledge graph, link prediction, subgraph construction, graph neural network

中图分类号:

TP391

于慧琳, 陈炜, 王琪, 高建伟, 万怀宇. 使用子图推理实现知识图谱关系预测[J]. 计算机科学与探索, 2022, 16(8): 1800-1808.

YU Huilin, CHEN Wei, WANG Qi, GAO Jianwei, WAN Huaiyu. Knowledge Graph Link Prediction Based on Subgraph Reasoning[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(8): 1800-1808.

图/表 7

参考文献 24

[1]	CHEN X, JIA S, XIANG Y. A review: knowledge reasoning over knowledge graph[J]. Expert Systems with Applications, 2020, 141: 112948.
[2]	HU S, ZOU L, YU J X, et al. Answering natural language questions by subgraph matching over knowledge graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30: 824-837.
[3]	PALUMBO E, RIZZO G, TRONCY R.Entity2rec: learning user-item relatedness from knowledge graphs for Top-N item recommendation[C]// Proceedings of the 11th ACM Conference on Recommender Systems, Como, Aug 27-31, 2017. New York: ACM, 2017: 32-36.
[4]	CORCOGLIONITI F, DRAGONI M, ROSPOCHER M, et al. Knowledge extraction for information retrieval[C]// Procee-dings of the 2016 European Semantic Web Conference, Crete, May 29-Jun 2, 2016. Cham:Springer, 2016: 317-333.
[5]	BORDES A, USUNIER N, GARCIA-DURAN A, et al. Tran-slating embeddings for modeling multi-relational data[C]// Proceedings of the 2013 Neural Information Processing Sys-tems, Lake Tahoe, Dec 5-8, 2013. Piscataway: IEEE, 2013: 2787-2795.
[6]	LIN Y K, LIU Z Y, SUN M S, et al. Learning entity and relation embeddings for knowledge graph completion[C]// Proceedings of the 29th AAAI Conference on Artificial In-telligence, Austin, Jan 25-30, 2015. Menlo Park: AAAI, 2015: 2181-2187.
[7]	DAS R, NEELAKANTAN A, BELANGER D, et al. Chains of reasoning over entities, relations, and text using recurrent neural networks[C]// Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, Valencia, Apr 3- 7, 2017. Stroudsburg: ACL, 2017: 132-141.
[8]	NEELAKANTAN A, ROTH B, MCCALLUM A. Composi-tional vector space models for knowledge base completion[C]// Proceedings of the 53rd Annual Meeting of the Asso-ciation for Computational Linguistics and the 7th Interna-tional Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, Jul 26-31, 2015. Stroudsburg: ACL, 2015: 156-166.
[9]	XIONG W, HOANG T, WANG W Y. DeepPath: a reinfor-cement learning method for knowledge graph reasoning[C]// Proceedings of the 2017 Conference on Empirical Me-thods in Natural Language Processing, Copenhagen, Sep 9-11, 2017. Stroudsburg: ACL, 2017: 564-573.
[10]	DAS R, DHULIAWALA S, ZAHEER M, et al. Go for a walk and arrive at the answer: reasoning over paths in knowledge bases using reinforcement learning[J].
[11]	MORRIS C, RITZERT M, FEY M, et al. Weisfeiler and Leman go neural: higher-order graph neural networks[C]// Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, the 9th AAAI Symposium on Edu-cational Advances in Artificial Intelligence, Honolulu, Jan 27 - Feb 1, 2019. Menlo Park: AAAI, 2019: 4602-4609.
[12]	SCHOENMACKERS S, DAVIS J, ETZIONI O, et al. Lear-ning first-order horn clauses from Web text[C]// Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, Oct 9-11, 2010. Stroudsburg: ACL, 2010: 1088-1098.
[13]	SCHULTE O, QIAN Z, KIRKPATRICK A E, et al. Fast learning of relational kernels[J]. Machine Learning, 2010, 78(3): 305-342.
[14]	WANG Z, ZHANG J W, FENG J L, et al. Knowledge graph embedding by translating on hyperplanes[C]// Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, Jul 27-31, 2014. Menlo Park: AAAI, 2014: 1112-1119.
[15]	JI G, HE S, XU L, et al. Knowledge graph embedding via dynamic mapping matrix[C]// Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Lan-guage Processing, Beijing, Jul 26-31, 2015. Stroudsburg: ACL, 2015: 687-696.
[16]	HOCHREITER S, SCHMIDHUBER J. Long short-term memory[J]. Neural Computation, 1997, 9(8): 1735-1780.
[17]	LI Z, JIN X, GUAN S, et al. Path reasoning over knowledge graph: a multi-agent and reinforcement learning based me-thod[C]// Proceedings of the 2018 IEEE International Confer-ence on Data Mining, Singapore, Nov 17-20, 2018. Piscata-way: IEEE, 2018: 929-936.
[18]	SHEN Y L, CHEN J S, HUANG P, et al. M-walk: learning to walk over graphs using Monte Carlo tree search[C]// Advances in Neural Information Processing Systems 31, Montréal, Dec 3-8, 2018: 6787-6798.
[19]	WAN G J, PAN S R, GONG C, et al. Reasoning like human: hierarchical reinforcement learning for knowledge graph reasoning[C]// Proceedings of the 29th International Joint Conference on Artificial Intelligence, Yokohama, 2021: 1926-1932.
[20]	ZHOU J, CUI G, ZHANG Z, et al. Graph neural networks: a review of methods and applications[J]. AI Open, 2020, 1: 57-81.
[21]	DOUGLAS B L. The Weisfeiler-Lehman method and graph isomorphism testing[J].
[22]	GAO H Y, JI S W. Graph U-Nets[C]// Proceedings of the 36th International Conference on Machine Learning, Long Beach, Jun 9-15, 2019: 2083-2092.
[23]	SRIVASTAVA N, HINTON G, KRIZHEVSKY A, et al. Drop-out: a simple way to prevent neural networks from over-fitting[J]. Journal of Machine Learning Research, 2014, 15(1): 1929-1958.
[24]	POWLEY E. Monte Carlo tree search[M]. Berlin, Heidelberg: Springer, 2012.

数据集	#实体数	#关系数	#三元组	#任务
FB15K-237	14 505	237	310 116	10
NELL-995	75 492	200	154 213	10

数据集	#实体数	#关系数	#三元组	#任务
FB15K-237	14 505	237	310 116	10
NELL-995	75 492	200	154 213	10

FB15K-237	TransE	TransR	DeepPath	MINERVA	M-Walk	RLH	SubGLP
personNationality	0.641	0.720	0.823	0.746	0.793	0.821	0.855
filmLanguage	0.642	0.641	0.670	0.603	0.623	0.682	0.716
birthPlace	0.403	0.417	0.531	0.641	—	—	0.710
filmDirector	0.386	0.399	0.441	0.589	0.618	0.683	0.654
filmWrittenBy	0.563	0.605	0.457	0.675	0.672	0.725	0.793
musicianOrigin	0.361	0.378	0.514	0.534	0.583	0.568	0.605
tvLanguage	0.804	0.906	0.969	0.860	—	—	0.988
capitalOf	0.554	0.493	0.783	0.729	0.743	0.737	0.803
organizationFounded	0.390	0.339	0.309	0.475	—	—	0.600
teamSports	0.896	0.784	0.955	0.960	—	—	0.906
Average	0.564	0.568	0.645	0.681	0.672	0.703	0.763

FB15K-237	TransE	TransR	DeepPath	MINERVA	M-Walk	RLH	SubGLP
personNationality	0.641	0.720	0.823	0.746	0.793	0.821	0.855
filmLanguage	0.642	0.641	0.670	0.603	0.623	0.682	0.716
birthPlace	0.403	0.417	0.531	0.641	—	—	0.710
filmDirector	0.386	0.399	0.441	0.589	0.618	0.683	0.654
filmWrittenBy	0.563	0.605	0.457	0.675	0.672	0.725	0.793
musicianOrigin	0.361	0.378	0.514	0.534	0.583	0.568	0.605
tvLanguage	0.804	0.906	0.969	0.860	—	—	0.988
capitalOf	0.554	0.493	0.783	0.729	0.743	0.737	0.803
organizationFounded	0.390	0.339	0.309	0.475	—	—	0.600
teamSports	0.896	0.784	0.955	0.960	—	—	0.906
Average	0.564	0.568	0.645	0.681	0.672	0.703	0.763

NELL-995	TransE	TransR	DeepPath	MINERVA	M-Walk	RLH	SubGLP
athleteHomeStadium	0.718	0.722	0.846	0.928	0.919	0.934	0.962
bornLocation	0.712	0.812	0.755	0.782	0.842	0.873	0.929
athletePlaysSport	0.876	0.963	0.917	0.986	0.983	0.974	0.906
teamPlaySports	0.761	0.814	0.696	0.875	0.884	0.891	0.876
orgHeadquaterCity	0.620	0.657	0.790	0.945	0.950	0.936	0.915
worksFor	0.677	0.692	0.699	0.827	0.827	0.826	0.836
athletePlaysForTeam	0.627	0.673	0.721	0.826	0.847	0.869	0.949
athletePlaysInLeague	0.773	0.912	0.960	0.952	0.978	0.946	0.958
personLeadsOrg	0.751	0.772	0.790	0.830	0.812	0.814	0.936
orgHiredPerson	0.719	0.737	0.738	0.870	0.888	0.895	0.866
Average	0.723	0.775	0.791	0.882	0.893	0.896	0.913

使用子图推理实现知识图谱关系预测

Knowledge Graph Link Prediction Based on Subgraph Reasoning

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 24

相关文章 15

编辑推荐

Metrics

FB15K-237	SubGLP-nod	SubGLP-edg	SubGLP	NELL-995	SubGLP-nod	SubGLP-edg	SubGLP
birthPlace	0.708	0.679	0.710	athletePlaysInLeague	0.941	0.939	0.958
personNationality	0.842	0.836	0.855	athleteHomeStadium	0.952	0.953	0.962
filmDirector	0.639	0.627	0.654	athletePlaysSport	0.957	0.936	0.906
filmWrittenBy	0.803	0.801	0.793	teamPlaySports	0.862	0.870	0.876
filmLanguage	0.706	0.702	0.716	orgHeadquaterCity	0.913	0.906	0.915
tvLanguage	0.978	0.975	0.988	worksFor	0.835	0.830	0.836
teamSports	0.896	0.897	0.906	athletePlaysForTeam	0.957	0.882	0.949
capitalOf	0.773	0.759	0.803	bornLocation	0.898	0.920	0.929
organizationFounded	0.524	0.523	0.600	personLeadsOrg	0.934	0.931	0.936
musicianOrigin	0.575	0.554	0.605	orgHiredPerson	0.860	0.825	0.866
Average	0.744	0.735	0.763	Average	0.911	0.899	0.913

[1]	萨日娜, 李艳玲, 林民. 知识图谱推理问答研究综述[J]. 计算机科学与探索, 2022, 16(8): 1727-1741.
[2]	田萱, 陈杭雪. 推荐任务中知识图谱嵌入应用研究综述[J]. 计算机科学与探索, 2022, 16(8): 1681-1705.
[3]	韩毅, 乔林波, 李东升, 廖湘科. 知识增强型预训练语言模型综述[J]. 计算机科学与探索, 2022, 16(7): 1439-1461.
[4]	郭晓旺, 夏鸿斌, 刘渊. 融合知识图谱与图卷积网络的混合推荐模型[J]. 计算机科学与探索, 2022, 16(6): 1343-1353.
[5]	董文波, 孙仕亮, 殷敏智. 医学知识推理研究现状与发展[J]. 计算机科学与探索, 2022, 16(6): 1193-1213.
[6]	王宝亮, 潘文采. 基于知识图谱的双端邻居信息融合推荐算法[J]. 计算机科学与探索, 2022, 16(6): 1354-1361.
[7]	张雁操, 赵宇海, 史岚. 融合图注意力的多特征链接预测算法[J]. 计算机科学与探索, 2022, 16(5): 1096-1106.
[8]	张子辰, 岳昆, 祁志卫, 段亮. 时序知识图谱的增量构建[J]. 计算机科学与探索, 2022, 16(3): 598-607.
[9]	蒋光峰, 胡鹏程, 叶桦, 仰燕兰. 基于重构误差的同构图分类模型[J]. 计算机科学与探索, 2022, 16(1): 185-193.
[10]	李想, 杨兴耀, 于炯, 钱育蓉, 郑捷. 基于知识图谱卷积网络的双端推荐算法[J]. 计算机科学与探索, 2022, 16(1): 176-184.
[11]	袁立宁, 李欣, 王晓冬, 刘钊. 图嵌入模型综述[J]. 计算机科学与探索, 2022, 16(1): 59-87.
[12]	吴正洋, 汤庸, 刘海. 个性化学习推荐研究综述[J]. 计算机科学与探索, 2022, 16(1): 21-40.
[13]	武家伟, 孙艳春. 融合知识图谱和深度学习方法的问诊推荐系统[J]. 计算机科学与探索, 2021, 15(8): 1432-1440.
[14]	高仰, 刘渊. 融合知识图谱和短期偏好的推荐算法[J]. 计算机科学与探索, 2021, 15(6): 1133-1144.
[15]	王晓东, 赵一宁, 肖海力, 王小宁, 迟学斌. 使用GNN与RNN实现用户行为分析[J]. 计算机科学与探索, 2021, 15(5): 838-847.