This paper explores the connections between Graph Neural Networks (GNNs) and logical formalisms by fixing architectural choices such as types of aggregation, combination, and activation functions, defining restricted classes of GNNs. These choices allow for the translation of logical formulas into equivalent GNNs and vice versa.
We take a semantic perspective to establish the logical expressiveness of GNN classifiers preserved under structural properties: embeddings (extensions), injective homomorphisms, and homomorphisms. For each property, we show that there exists a fragment of graded modal logic characterizing the class of GNNs.
Specifically, preservation under embeddings, injective homomorphisms, and homomorphisms corresponds to existential graded modal logic, its existential-positive fragment, and existential-positive modal logic, respectively. These results characterize the expressiveness of broad classes of GNNs independently of specific architectural choices, and we also demonstrate that each class admits a GNN architecture of the same expressiveness.
Technically, our approach employs a new well-quasi-order result for trees of bounded height, yielding finite representations of unraveling-invariant classes.
Blogger's Review: This paper reveals the expressive power of GNNs under structural preservation by linking it with logical formalisms, offering a fresh perspective on the study of Graph Neural Networks. The mutual translation between logic and network architectures highlights the potential connections between deep learning and logical reasoning, paving the way for broader applications of GNNs.