acceptodds
Under review as a conference paper at ICLR 2027

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Expressive power of GNNs, Logical Expressiveness

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_aZffOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies GNN expressivity, namely preservation under three graph operations: embeddings (extensions), injective homomorphisms, and homomorphisms. To derive the results, authors first focus on logic (so they restrict GNNs to so called threshold-based classifiers). Inb the logic setting, they are able to show that a class of (pointed) graphs is preserved under one of these operations iff it is expressible in suitable fragments of graded modal logic, and then that the class of graphs accepred by a GNN is preserved under these relations iff they are expressible in the corresponding fragments. The second half of the paper deals with syntactic definitions of GNNs that realize these preservation results, which leads to three new classes of GNNs and all capture precisely their corresponding logical formalism.

The paper contains very nice theoretical results, the logical part is probably of independent interest, although GNNs are probably the most obvious applications.

Critical strengths
  • Very good theoretical results, with connections from several areas, and a direct application of finite model theory in machine learning.
  • Paper is nonetheless very easy to read.
Critical weaknesses
  • The main weakness of the paper is the lack of discussion in terms of practical impact. The main question that I would like to be answered is: Why would someone implement one of MGNNs, augmented MGNNs or MAX-MGNNs instead of a more standard GNN model? In terms of expressive power, a more powerful GNN model capable of capturing all graded modal logic would suffice. I think authors discuss about building models to specifically enforce structural preservation properties on the passing, and this could be an interesting answer, but more expanded discussion would be ideal.
Questions for authors
  • please engage with the weakness stated above.
Reviewer_BsRvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This article presents new results about the expressivity of GNNs. Given various levels of structural preservation of the GNNs, different corresponding logical descriptions are given. The authors consider three levels of preservation: embeddings (extensions), injective homomorphisms, and homomorphisms. To each of those preservations a precise logical framework is presented. The authors also introduce another yardstick of logical expressiveness, the monotonic GNNs that they compare those three categories of GNNs to.

To the best of my knowledge this helps to complement the existing results that focus on restricted architectures and activation functions.

Critical strengths

This article has the benefit to give an original standpoint to describe the logical expressiveness from the invariances of the GNNs architecture. This allows for the understanding of expressiveness to remove the underlying architecture and apply those results across various architectures.

Critical weaknesses

The article falls short on one main level which is to compare their results deeper to the existing ones in the literature (concretely in terms of consequence for various architectures), and how their results allow to make progress in the understanding of GNNs' expressivity.

Also, there is no high level description on the proof's approaches in the main text.

Questions for authors

It is claimed that the main technical challenge is stated via Theorem 4 (in the introduction). However; it holds for the Embedding relation. Then, Theorem 7 seems to refine that statement. Can the authors elaborate on this?

Reviewer_sfcuOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the expressiveness of classes of graph neural networks (GNNs) that are closed with respect to structural relations via logical characterisations. It is shown that the class of GNNs preserved under embeddings is characterized by existential graded modal logic, those preserved under injective homomorphisms by existential-positive graded modal logic and those preserved under homomorphisms by existential-positive modal logic. It is also shown that the properties expressible by these classes correspond to restricted GNN architectures; GNNs preserved under embeddings express the same properties as monotonic GNNs with an additional augmentation layer, GNNs preserved under injective homomorphisms express the same properties as monotonic GNNs, and GNNs preserved under homomorphisms express the same properties as monotonic GNNs that use MAX as the aggregation function.

Critical strengths

Clarity: The paper is very easy to follow. The structure makes sense, and intuitive explanations and useful examples are given without ever delving into excessive detail.

Soundness: The reviewer could not find any errors in the analysis provided in the paper.

Critical weaknesses

Significance: The logical expressiveness of GNNs via different modal logics and graded modal logics in particular is well-established in the literature, which limits the significance somewhat.

Questions for authors

Why is it important to characterize classes of GNNs that are preserved under structural relations? More discussion on this, if possible, may help motivate the paper to the reader.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.