Research on the Parallel Tractability of Knowledge Graph Reasoning based on Boolean Circuits  

作　　者：Zhangquan Zhou 

机构地区：[1]School of Information Science and Engineering,Nanjing Audit University Jinshen College Nanjing 211815,China

出　　处：《Data Intelligence》2024年第3期692-719,共28页数据智能（英文）

基　　金：supported by The Natural Science Foundation of the Jiangsu Higher Education Institutions of China under grant number 22KJB520003.The project name is"Research on Representation and Reasoning of Knowledge Graphs based on Semantic Mapping".

摘　　要：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 graphs.To enhance the efficiency of knowledge graph reasoning,researchers studied how to design parallelalgorithms for reasoning,and take advantage of high-performance architectures,like neural networks.Although 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 complexities.This means that the task of reasoning is not parallelly tractable.In this work,we investigate the parallel tractability of knowledge graph reasoning from the perspective of parallel complexity.We concentrate on knowledge graphs that are Datalog rewritable.We aim to capture the parallelly tractable classes of knowledge graphs,for which,the task of reasoning falls in the NC complexity.To this end,we employ the computational model of Boolean circuit to formalize knowledge graph reasoning and further obtain all the theoretical results.We then use the results to analyze DHL(Description Horn Logic),a fragment of description logic.We give the properties that ensure the parallel tractability of DHL reasoning.One can utilize our results to check the parallel tractability of real knowledge graphs.In addition,the Boolean circuits proposed in this paper can also be used to construct neural networks to perform knowledge graph reasoning.

关 键 词：Knowledge graph REASONING Parallel tractability Boolean circuit the NC complexity 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]