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 ...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.展开更多
基金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".
文摘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.
