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

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.

Investigating the Logical Capability of Graph Neural Networks via the Connection to C_(2)

Graph neural networks(GNNs)have garnered substantial application across a spectrum of real-world scenarios due to their remarkable ability to handle data organized in the form of graphs.Nonetheless,the full extent of GNNs'computational properties and logical capability remains a subject of ongoing investigation.This study undertakes an exploration of the logical capabilities intrinsic to GNNs,approaching the matter from a theoretical standpoint.In this pursuit,a pivotal connection is established between GNNs and a specific fragment of first-order logic known as C_(2),which serves as a logical framework for modeling graph data.Recent research further amplifies this discourse,introducing a subcategory of GNNs named ACR-GNN,illustrating that GNNs are capable of emulating the evaluation process of unary C,formulas.Expanding on these insights,we introduce an innovative version of GNN architectures capable of dealing with general C,formulas.To attain this,we employ a mechanism known as message passing for GNN reconstruction.The proposed GNN adaptations allow for simultaneous updating of node and node pair features,thereby enabling the management of both unary and binary C,formulas.We prove that the proposed models exhibit the equivalent expressiveness to C_(2).This underpins the profound alignment between the logical capability of GNNs and the inherent nature of the logical language C,.We conduct several experiments on both of synthetic and real-world datasets to support our claims.Through the experiments,we verify that our suggested models outperform both ACR-GNN and a commonly used model,GIN,when it comes to evaluating C,formulas.