Knowledge Graph Inference Method Combined with Decision Implication

doi:10.3778/j.issn.1673-9418.2207085

Abstract

Abstract: Decision implication is a tool of decision knowledge representation and reasoning in formal concept analysis. This paper proposes a relationship completion method for knowledge graph based on decision implication. Firstly, this paper constructs the corresponding decision context for a knowledge graph and proves that decision implications are able to equivalently represent the rules in knowledge graph inference. In order to efficiently extract decision implications, this paper reduces the complicated decision contexts many times and proves that the reduced decision contexts also contain the rules in knowledge graph inference. This paper also designs an algorithm to extract decision implications from the reduced decision contexts and provides steps to perform relationship completion by applying decision implications. Finally, experiments verify the effectiveness of the proposed method. This paper provides a new idea for completing knowledge graph relationship, as well as a new choice for fusion inference.

Key words: formal concept analysis, decision implication, object reduction, knowledge graph, relationship completion

摘要： 决策蕴涵是形式概念分析中的决策知识表示和推理工具。提出了一种基于决策蕴涵的知识图谱关系补全方法。基于知识图谱构建对应的决策背景，证明决策蕴涵可以等价表示知识图谱推理中的规则；为了快速挖掘决策蕴涵，对复杂的决策背景进行多次约简，证明约简后的决策背景也可以获取知识图谱推理中的规则；设计了从简化后的决策背景中获取决策蕴涵的算法，给出了使用决策蕴涵进行关系补全的步骤；最后通过实验验证了上述方法的有效性。该研究为完成知识图谱关系补全任务提供了新的思路，也为融合推理提供了一个新的选择。

关键词: 形式概念分析, 决策蕴涵, 对象约简, 知识图谱, 关系补全

ZHAI Yanhui, HE Xu, LI Deyu, ZHANG Chao. Knowledge Graph Inference Method Combined with Decision Implication[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(11): 2743-2754.

翟岩慧, 何煦, 李德玉, 张超. 融合决策蕴涵的知识图谱推理方法[J]. 计算机科学与探索, 2023, 17(11): 2743-2754.

References

[1] GANTER B, WILLE R. Formal concept analysis, mathematical foundations[M]. Berlin, Heidelberg: Springer, 1999.
[2] WILLE R. Restructuring lattice theory, an approach based on hierarchies of concepts[C]//LNCS 5548: Proceedings of the 2009 International Conference on Formal Concept Analysis, Darmstadt, May 21-24, 2009. Berlin, Heidelberg: Springer, 2009: 314-339.
[3] QU K S, ZHAI Y H, LIANG J Y, et al. Study of decision implications based on formal concept analysis[J]. International Journal of General Systems, 2007, 36(2): 147-156.
[4] ZHAI Y H, LI D Y, QU K S. Decision implications, a logical point of view[J]. International Journal of Machine Learning and Cybernetics, 2014, 5(4): 509-516.
[5] ZHAI Y H, LI D Y, QU K S. Decision implication canonical basis, a logical perspective[J]. Journal of Computer and System Sciences, 2015, 81(1): 208-218.
[6] ZHAI Y H, JIA N, ZHANG S X, et al. Study on deduction process and inference methods of decision implications[J]. International Journal of Machine Learning and Cybernetics, 2022, 13(7): 1959-1979.
[7] WU W Z, LEUNG Y, MI J S. Granular computing and know-ledge reduction in formal contexts[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21: 1461-1474.
[8] ZHANG S X, LI D Y, ZHAI Y H, et al. A comparative study of decision implication, concept rule and granular rule[J]. Information Sciences, 2020, 508: 33-49.
[9] TU X D, WANG Y L, ZHANG M L, et al. Using formal concept analysis to identify negative correlations in gene expression data[J]. IEEE/ACM Transactions on Computational Biology & Bioinformatics, 2016, 13(2): 380-391.
[10] ZHI H L, QI J J, QIAN T, et al. Con?ict analysis under one-vote veto based on approximate three-way concept lattice[J]. Information Sciences, 2020, 516: 316-330.
[11] ZOU C F, ZHANG D Q, WAN J F, et al. Using concept lattice for personalized recommendation system design[J]. IEEE Systems Journal, 2017, 11(1): 305-314.
[12] QIN K Y, LI B, ZHENG P. Attribute reduction and rule acquisition of formal decision context based on object (property) oriented concept lattices[J]. International Journal of Machine Learning and Cybernetics, 2019, 10(10): 2837-2850.
[13] CORNEJO M E, MEDINA J, RAMíREZ-POUSSA E. Attribute and size reduction mechanisms in multi-adjoint concept lattices[J]. Journal of Computational and Applied Mathematics, 2017, 318: 388-402.
[14] REN R S, WEI L. The attribute reductions of three-way concept lattices[J]. Knowledge Based Systems, 2016, 99: 92-102.
[15] ZHAI Y H, LI D Y. Knowledge structure preserving fuzzy attribute reduction in fuzzy formal context[J]. International Journal of Approximate Reasoning, 2019, 115: 209-220.
[16] LI J H, KUMAR C A, MEI C L, et al. Comparison of reduction in formal decision contexts[J]. International Journal of Approximate Reasoning, 2017, 80: 100-122.
[17] SHAO M W, LI K W. Attribute reduction in generalized one-sided formal contexts[J]. Information Sciences, 2016, 378: 317-327.
[18] LI J H, MEI C L, XU W H, et al. Concept learning via granular computing, a cognitive viewpoint[J]. Information Sciences, 2015, 298: 447-467.
[19] SHI Y, MI Y L, LI J H, et al. Concept-cognitive learning model for incremental concept learning[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(2): 809-821.
[20] 李金海, 米允龙, 刘文奇. 概念的渐进式认知理论与方法[J]. 计算机学报, 2019, 42(10): 2233-2250.
LI J H, MI Y L, LIU W Q. Incremental cognition of concepts, theories and methods[J]. Chinese Journal of Computers, 2019, 42(10): 2233-2250.
[21] XU W H, LI W T. Granular computing approach to two-way learning based on formal concept analysis in fuzzy datasets[J]. IEEE Transactions on Cybernetics, 2016, 46 (2): 366-379.
[22] SEBASTIEN F. A proposal for extending formal concept analysis to knowledge graphs[C]//Proceedings of the 13th International Conference on Formal Concept Analysis, Nerja, Jun 23-26, 2015: 271-286.
[23] 李金海, 魏玲, 张卓, 等. 概念格理论与方法及其研究展望[J]. 模式识别与人工智能, 2020, 33(7): 619-642.
LI J H, WEI L, ZHANG Z, et al. Concept lattice theory methods and their research prospect[J]. Pattern Recognition and Artificial Intelligence, 2020, 33(7): 619-642.
[24] JI S X, PAN S R, ERIK C, et al. A survey on knowledge graphs, representation, acquisition, and applications[J]. IEEE Transactions on Neural Networks and Learning Systems, 2022, 33(2): 494-514.
[25] NATHANI D, CHAUHAN J, SHARMA C, et al. Learning attention-based embeddings for relation prediction in know-ledge graphs[C]//Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, Florence, Jul 28-Aug 2, 2019. Stroudsburg: ACL, 2019: 4710-4723.
[26] BORDES A, USUNIER N, GARCIA-DURAN A, et al. Translating embeddings for modeling multi-relational data[C]//Proceedings of the 2013 Neural Information Processing Systems, Lake Tahoe, Dec 5-8, 2013. Piscataway: IEEE, 2013: 2787-2795.
[27] 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, Que- bec, Jul 27-31, 2014. Menlo Park: AAAI, 2014: 1112-1119.
[28] 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 Intelligence, Austin, Jan 25-30, 2015. Menlo Park: AAAI, 2015: 2181-2187.
[29] JI G L, HE S Z, XU L H, 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 Language Processing, Beijing, Jul 26-31, 2015. Stroudsburg: ACL, 2015: 687-696.
[30] DETTMERS T, MINERVINI P, STENETORP P, et al. Convolutional 2D knowledge graph embeddings[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 1811-1818.
[31] NGUYEN D Q, NGUYEN T D, NGUYEN D Q, et al. A novel embedding model for knowledge base completion based on convolutional neural network[C]//Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics, New Orleans, Jun 1-6, 2018. Stroudsburg: ACL, 2018: 327-333.
[32] BORDES A, GLOROT X, WESTON J, et al. A semantic matching energy function for learning with multi-relational data[J]. Machine Learning, 2014, 94(2): 233-259.
[33] OU M D, CUI P, PEI J, et al. Asymmetric transitivity preserving graph embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference of Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 1105-1114.
[34] ZHANG Z H, HUANG J B, TAN Q L. Association rules enhanced knowledge graph attention network[J]. Knowledge-Based Systems, 2022, 239: 108038.
[35] MAO Y Y, CHEN H H. Rule-guided compositional representation learning on knowledge graphs with hierarchical types[J]. Mathematics, 2021, 9(16): 1978.
[36] LI J H, MEI C L, LV Y J. A heuristic knowledge reduction method for decision formal contexts[J]. Computer and Mathematics with Applications, 2011, 61: 1096-1106.
[37] LI J H, MEI C L, LV Y J. Knowledge reduction in formal decision contexts based on an order preserving mapping[J]. International Journal of General Systems, 2012, 41(2): 143-161.
[38] ZHAI Y H, LI D Y, QU K S. Fuzzy decision implications[J]. Knowledge-Based Systems, 2013, 37: 230-236.
[39] ZHAI Y H, LI D Y, QU K S. Fuzzy decision implication canonical basis[J]. International Journal of Machine Learning and Cybernetics, 2018, 9(11): 1909-1917.
[40] ZHAI Y H, LI D Y, ZHANG J. Variable decision knowledge representation, a logical description[J]. Journal of Computational Science, 2018, 25: 161-169.