Research on the Parallel Tractability of Knowledge Graph Reasoning based on Boolean Circuits
作者机构：School of Information Science and EngineeringNanjing Audit University Jinshen College Nanjing 211815China
出 版 物：《Data Intelligence》 (数据智能（英文）)
年 卷 期：2024年第6卷第3期
页 面：692-719页
核心收录：
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：Knowledge graph Reasoning Parallel tractability Boolean circuit the NC complexity
摘 要：Although neural methods have been comprehensively applied in different fields,symbolic based logic reasoning is still the main choice for numerous applications based on knowledge *** enhance the efficiency of knowledge graph reasoning,researchers studied how to design parallelalgorithms for reasoning,and take advantage of high-performance architectures,like neural *** parallel algorithms and architectures improve the performance of reasoning to some degree,the task of reasoning is essentially bounded by its computational complexity,i.e.,the PTiMe-Completeness or higher *** means that the task of reasoning is not parallelly *** this work,we investigate the parallel tractability of knowledge graph reasoning from the perspective of parallel *** concentrate on knowledge graphs that are Datalog *** aim to capture the parallelly tractable classes of knowledge graphs,for which,the task of reasoning falls in the NC *** this end,we employ the computational model of Boolean circuit to formalize knowledge graph reasoning and further obtain all the theoretical *** then use the results to analyze DHL(Description Horn Logic),a fragment of description *** give the properties that ensure the parallel tractability of DHL *** can utilize our results to check the parallel tractability of real knowledge *** addition,the Boolean circuits proposed in this paper can also be used to construct neural networks to perform knowledge graph reasoning.
维普期刊数据库