Structural Preservation and the Logical Expressiveness of Graph Neural Networks

The paper establishes a connection between graph neural networks (GNNs) and logical formalisms by defining classes of GNNs based on architectural choices related to aggregation, combination, and activation functions. It demonstrates that structural preservation properties, such as embeddings and homomorphisms, correspond to specific fragments of graded modal logic, thereby characterizing the logical expressiveness of GNN classifiers. This work is significant for AI practitioners as it provides a framework for understanding the theoretical limits and capabilities of GNNs, potentially guiding the design of more expressive models.