Investigating the Logical Capability of Graph Neural Networks via the Connection to ๐2
Zhangquan Zhou, Shijiao Tang ยท Data Intelligence ยท 2024
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 ๐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 ๐2 formulas. Expanding on these insights, we introduce an innovative version of GNN architectures capable of dealing with general ๐2 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 ๐2 formulas. We prove that the proposed models exhibit the equivalent expressiveness to ๐2. This underpins the profound alignment between the logical capability of GNNs and the inherent nature of the logical language ๐2. 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 ๐2 formulas.