Search papers, labs, and topics across Lattice.
This paper establishes a semantic framework connecting graph neural networks (GNNs) to logical formalisms by identifying structural properties that preserve logical expressiveness, such as embeddings and homomorphisms. By translating logical formulae into equivalent GNNs and vice versa, the authors characterize various classes of GNN classifiers through fragments of graded modal logic. The key finding reveals that each structural preservation property corresponds to specific logical fragments, providing a comprehensive understanding of GNN expressiveness independent of architectural choices.
Structural properties of GNNs reveal deep connections to graded modal logic, offering a new lens to understand their expressiveness.
Bridges between graph neural networks (GNNs) and logical formalisms have been established by fixing architectural choices, such as the types of aggregation, combination, and activation functions. These choices define restricted classes of GNNs for which tight correspondences with logical formalisms can be obtained, by showing that logical formulae can be translated into equivalent GNNs and, conversely, that GNNs can be translated into equivalent formulae. In this paper we take a semantic perspective by establishing the logical expressiveness of classes of GNN classifiers that are preserved under structural properties: embeddings (extensions), injective homomorphisms, and homomorphisms. We show that, for each such property, there exists a fragment of graded modal logic characterising the class of GNNs. In particular, 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 characterise the expressiveness of broad classes of GNNs independently of specific architectural choices, but we also show that each of these classes admits a GNN architecture of the same expressiveness. Technically, our approach uses a new well-quasi-order result for trees of bounded height, yielding finite representations of unravelling-invariant classes.
