GNN Logical Expressiveness Characterized by Structural Preservation Properties.

The relationship between Graph Neural Networks (GNNs) and logical formalisms has traditionally been established by fixing specific architectural elements, such as aggregation, combination, and activation functions. This approach defines restricted GNN classes that can be tightly correlated with logical formulae through translation. This research takes a different, semantic perspective by investigating the logical expressiveness of GNN classifiers based on their preservation under various structural properties. Specifically, it examines preservation under embeddings (extensions), injective homomorphisms, and general homomorphisms. The findings reveal that for each of these structural properties, a corresponding fragment of graded modal logic precisely characterizes the class of GNNs exhibiting that preservation. For instance, preservation under embeddings corresponds to existential graded modal logic, while injective homomorphisms align with its existential-positive fragment, and general homomorphisms with existential-positive modal logic. These results provide a fundamental understanding of GNN expressiveness that is independent of particular architectural choices, although the paper also demonstrates that each characterized class admits a GNN architecture with equivalent expressiveness. The technical foundation includes a new well-quasi-order result for trees of bounded height, which facilitates finite representations of unravelling-invariant classes.