analiza aiqbench
This research establishes a semantic framework for Graph Neural Networks (GNNs) by linking their structural preservation properties to specific fragments of graded modal logic. By demonstrating that broad classes of GNN architectures correspond directly to logical formalisms like existential positive modal logic, the study provides theoretical guarantees on expressiveness independent of arbitrary architectural choices. This work advances fundamental machine learning theory and offers a rigorous mathematical foundation for understanding how graph-based models process structural data.
Structural Preservation and the Logical Expressiveness of Graph Neural Networks
arXiv:2606.17882v1 Announce Type: new Abstract: 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.
Abstract: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.
Artificial Intelligence (cs.AI)
arXiv:2606.17882 [cs.AI]
(or arXiv:2606.17882v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2606.17882 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 282 cuvinte
Subiecte conexe
The J-Space Debate, Agent Swarms, and Pacing Frontier AI - Digital Minds Newsletter #4
LessWrong · 18 sept. 2026
Researchers Decode up to 1,023 Qubits Using Rank Decomposition
Quantum Zeitgeist · 3 oct. 2026
Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks
arXiv · 17 iun. 2026
Parallel Noising in Neural Markov Logic Networks
arXiv · 23 iul. 2026