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 kn...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.展开更多
Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula....Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively.展开更多
基金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.
基金supported in part by the National Natural Science Foundation of China under Grant No.61871242in part by the State Key Laboratory of ASIC(Application Specific Integrated Circuit)&System of China under Grant No.2021KF008.
文摘Boolean satisfiability (SAT) is widely used as a solver engine in electronic design automation (EDA). Typically, SAT is used to determine whether one or more groups of variables can be combined to form a true formula. All solutions SAT (AllSAT) is a variant of the SAT problem. In the fields of formal verification and pattern generation, AllSAT is particularly useful because it efficiently enumerates all possible solutions. In this paper, a semi-tensor product (STP) based AllSAT solver is proposed. The solver can solve instances described in both the conjunctive normal form (CNF) and circuit form. The implementation of our method differs from incremental enumeration because we do not add blocking conditions for existing solutions, but rather compute the matrices to obtain all the solutions in one pass. Additionally, the logical matrices support a variety of logic operations. Results from experiments with MCNC benchmarks using CNF-based and circuit-based forms show that our method can accelerate CPU time by 8.1x (238x maximum) and 19.9x (72x maximum), respectively.
