Structural Preservation and the Logical Expressiveness of Graph Neural Networks

• URL: http://arxiv.org/abs/2606.17882v1
• Date: Tue, 16 Jun 2026 12:57:50 GMT
• Title: Structural Preservation and the Logical Expressiveness of Graph Neural Networks
• Abstract summary: We take a semantic perspective by establishing the logical expressiveness of classes of graph neural networks (GNNs) preserved under structural properties.<n>We show that, for each such property, there exists a fragment of graded modal logic characterising the class of GNNs.<n>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.
• Score: 10.885910878567456
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Do We Really Need GNNs with Explicit Structural Modeling? MLPs Suffice for Language Model Representations [50.45261187796993]
  Graph Neural Networks (GNNs) fail to fully utilize structural information, whereas Multi-Layer Perceptrons (MLPs) exhibit a surprising ability in structure-aware tasks.<n>This paper introduces a comprehensive probing framework from an information-theoretic perspective.
  arXiv  Detail & Related papers  (2025-06-26T18:10:28Z)
• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization [0.6215404942415159]
  Hierarchical Ego Graph Neural Networks (HEGNNs) are an expressive extension of graph neural networks (GNNs)<n>HEGNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that can distinguish graphs up to isomorphism.<n>Our experimental results confirm the practical feasibility of HEGNNs and show benefits in comparison with traditional GNN architectures.
  arXiv  Detail & Related papers  (2025-06-16T18:39:31Z)
• Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective [24.729126775414922]
  We provide a theoretical framework to determine the homomorphism counting power of an arbitrary class of graph neural networks (GNNs) As the considered design space is large enough to accommodate almost all known powerful GNNs, our result greatly extends all existing works, and may find its application in the automation of GNN model design.
  arXiv  Detail & Related papers  (2024-10-04T15:36:48Z)
• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  We show that each formula can be transformed into an equivalent graph neural network (GNN)<n>We also show that the satisfiability problem is PSPACE-complete.
  arXiv  Detail & Related papers  (2024-04-30T21:16:38Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  Homomorphism expressivity measures the ability of GNN models to count graphs under homomorphism. By examining four classes of prominent GNNs as case studies, we derive simple, unified, and elegant descriptions of their homomorphism expressivity. Our results provide novel insights into a series of previous work, unify the landscape of different subareas in the community, and settle several open questions.
  arXiv  Detail & Related papers  (2024-01-16T17:23:23Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible neural networks (INNs) are neural network architectures with invertibility by design. Thanks to their invertibility and the tractability of Jacobian, INNs have various machine learning applications such as probabilistic modeling, generative modeling, and representation learning.
  arXiv  Detail & Related papers  (2022-04-15T10:45:26Z)
• Equivariant Neural Network for Factor Graphs [83.26543234955855]
  We propose two inference models: Factor-Equivariant Neural Belief Propagation (FE-NBP) and Factor-Equivariant Graph Neural Networks (FE-GNN) FE-NBP achieves state-of-the-art performance on small datasets while FE-GNN achieves state-of-the-art performance on large datasets.
  arXiv  Detail & Related papers  (2021-09-29T06:54:04Z)
• Neural Production Systems [90.75211413357577]
  Visual environments are structured, consisting of distinct objects or entities. To partition images into entities, deep-learning researchers have proposed structural inductive biases. We take inspiration from cognitive science and resurrect a classic approach, which consists of a set of rule templates. This architecture achieves a flexible, dynamic flow of control and serves to factorize entity-specific and rule-based information.
  arXiv  Detail & Related papers  (2021-03-02T18:53:20Z)
• Stability of Algebraic Neural Networks to Small Perturbations [179.55535781816343]
  Algebraic neural networks (AlgNNs) are composed of a cascade of layers each one associated to and algebraic signal model. We show how any architecture that uses a formal notion of convolution can be stable beyond particular choices of the shift operator.
  arXiv  Detail & Related papers  (2020-10-22T09:10:16Z)
• Algebraic Neural Networks: Stability to Deformations [179.55535781816343]
  We study algebraic neural networks (AlgNNs) with commutative algebras. AlgNNs unify diverse architectures such as Euclidean convolutional neural networks, graph neural networks, and group neural networks.
  arXiv  Detail & Related papers  (2020-09-03T03:41:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.