Towards a Complete Logical Framework for GNN Expressiveness
Authors: Tuo Xu
Venue: ICLR 2025 Oral (2025)
Keywords: graph neural networks
logic
Primary area: learning on graphs and other geometries & topologies
TL;DR: Analyze the logical expressiveness of arbitrary graph neural networks

Abstract: Designing expressive Graph neural networks (GNNs) is an important topic in graph machine learning fields. Traditionally, the Weisfeiler-Lehman (WL) test has been the primary measure for evaluating GNN expressiveness. However, high-order WL tests can be obscure, making it challenging to discern the specific graph patterns captured by them. Given the connection between WL tests and first-order logic, some have explored the logical expressiveness of Message Passing Neural Networks. This paper aims to establish a comprehensive and systematic relationship between GNNs and logic. We propose a framework for identifying the equivalent logical formulas for arbitrary GNN architectures, which not only explains existing models, but also provides inspiration for future research. As case studies, we analyze multiple classes of prominent GNNs within this framework, unifying different subareas of the field. Additionally, we conduct a detailed examination of homomorphism expressivity from a logical perspective and present a general method for determining the homomorphism expressivity of arbitrary GNN models, as well as addressing several open problems.

Published as a conference paper at ICLR 2025
TOWARDS A COMPLETE LOGICAL FRAMEWORK FOR GNN EXPRESSIVENESS
Tuo Xu Independent Researcher tourxuê vive com
ABSTRACT
Designing expressive Graph neural networks (GNNs) is an important topic in graph machine learning fields. Traditionally, the Weisfeiler-Lchman (WL) test has been the primary measure for evaluating GNN expressiveness. However, high- order WL tests can obscure, making challenging to discern the specific graph patterns captured by them. Given the connection between WL tests and first-order logic, some have explored the logical expressiveness of Message Passing Neural Networks. This paper aims to establish comprehensive and systematic rela- tionship between GNNs and logic. We propose a framework for identifying the equivalent logical formulas for arbitrary GNN architectures, which not only ex- plains existing models, but also provides inspiration for future research. As case studies, we analyze multiple classes of prominent GNNs within this framework, unifying different subareas of the field. Additionally, we conduct a detailed ex- amination of homomorphism expressivity from logical perspective and present general method for determining the homomorphism expressivity of arbitrary GNN models, as well as addressing several open problems.
INTRODUCTION
Graph Neural Networks (GNNs) are the dominant approaches for learning graph-structured data and have achieved remarkable success over the past few years. Among them, Message Passing Neural Networks (MPNNs) (Kipf & Welling 20) are prominent GNN models that learn node and graph representations by aggregating information from neighbors. However, a noticeable drawback of GNNs lies in their limited expressive power. Xu et al. Morris et al. (2019) discovered that the separation power of MPNNs is inherently restricted by 1-dimensional Weisfeiler- Lehmman (I- WL) test. Subsequently, many studies have focused enhancing expressiveness and designing more powerful GNN models using the WL framework as a metric.
While the k- WL hierarchy offers systematic measure of GNN expressiveness that increases with k, it remains somewhat limited. First, it lacks interpretability. Despite 1-WL being relatively straightforward procedure which aggregates neighborhood information, is hard understand what k-WL actually learns and how it surpasses (k: 1)- Second, WL tests are arguably too coarse evaluate the expressive power of GNN models ÇZhang et al. 2024 Morris et al. 2022 Puny et al. 2023): many works (Qian et al. 2022 Frasca et al. 2022) only provide loose upper bounds of expressiveness of their proposed models in terms of h WL and most efficient GNNs are only proved to be more expressive than 1-WL by constructing specific example graphs (Zhang & Li
2021 Bevilacqua et al. 2021 Zhang et al. 2023).
Apart from the WI. hierarchy, some works systematically study GNN expressivity from various per- spectives. For instance, Zhang et al. (2024) identified all substructures captured by several popular GNN models. Xu & Zou| (2024) examined the approximate inference capabilities of popular GNN models. These works, although provide novel insights about GNN expressivity, still lack extend- ability: they do not provide general method for analyzing the expressiveness of arbitrary GNN models using their theoretical framework. Thus, considerable effort required when considering novel GNN variants.
To address these limitations, this paper studies GNN expressivity from a logical perspective. Previ- research, such Barceló et al. (2000), investigated the logical expressivity of MPNNs, while

---

Published as a conference paper at ICLR 2025
Huang al. (2024) explored the logical expressivity of a specific class of GNN models for link prediction in knowledge graphs. However, these works study MPNNs and other GNN variants sepa- rately, leaving many popular models unexamined. Additionally, there still lacks unified framework for assessing the logical expressivity of general GNN models.
Contributions. This paper presents a novel framework for assessing the logical expressivity of arbitrary GNN models, provided they can be represented through a series of combination and ag- gregation operations. We present a method for constructing the set of logical formulas captured by these GNN models. Using this framework, we describe the logical expressivity of popular GNN models in terms of graph-level, node-level, and link-level predictions, Furthermore, we demonstrate how several key topics in GNN expressivity, such as homomorphism expressivity, expressivity com- parisons, and estimating WL upper bounds, can be effectively addressed by leveraging the logical expressivity results present in this study.
2 BACKGROUND
Notations and definitions. We use O to denote sets and use (() to denote multisets. The index set is denoted as [n] n.. In this paper we consider finite, directed graphs with node and edge labels. Let G' (Va, Eg) be a graph where Va denotes the set of nodes in G and Eg the set edges. E denotes the label function that maps nodes and edges to labels: {(u) is the label of node and E(u, v) the label of (u, v) provided that edge (u, v) exists. (N) denotes the set of generalized neighbors of node u: certain GNNs might generalize the concept of neighbor in graphs in different manners. For example, in MPNNs the neighbors of node x is conventionally defined as (M) == {y E(r,y) 9) E E where & is the set of edges; 2-FGNNs define the neighbor of a node pair (z, y) to be N2-PONN (I, y) {[(z, 2), (2, use symbols sp, 1), o.... to refer to logic formulas.
V} where V the set of nodes. We
In this paper we focus on logic formulas and GNN models that operate on nodes and more generally node tuples. For instance, logic formulas (x 22, 2:3) and GNNs that learn representations for node pairs. We define the order of logic formulas and GNNs be the size of node tuples considered, e.g. the order of va is 3 and the order of GNNs that compute representations for node pairs is 2. For notation brevity we use u, V, x.... E V* to refer to node tuples where h: E (0. 1, 1.... of them, e.g. (x11,, 222 v3) is represented by (x(x) where x is a 3-order tuple x = (.1. 22, 23)- Specially, = 1, then u E V1 represents nodes in graphs; if k = 0, then u e V simple represents none.
the order
Graph isomorphism. as H. if [V = VHl and there exists a bijective permutation π : VG + VH satisfying: (1) u,, &
Two graphs = (Va, Eg) and H (VH, Eh) are isomorphic, denoted
(z(w), (v)) E Eu for u, E VG. (2) ((u) {(T(r)) for u Va and (3) for (u,b) E Eg. Such æ is an isomorphism from G to H. Our work is
f(u, v) = (1)) also closely related to family of necessary tests for graph isomorphism namely Weismeiler-Lehman
(WL) tests introduced in Appendix B
First-order Logic. We briefly introduce first-order logic and its relation with graphs. Consider the following formula
(xx) = Red(x) A By (E(s, v) A Blue(y))
There are two variables var(4p) {ar, y) in the formulation of sp, and y has exactly one free variable free(()) {x} which is not bounded by any quantifiers 3, V. (o(x) is true iff x is Red and exists a Blue y such that E(x, 3) holds. It is straightforward to relate this formula with graphs: variables x, y are corresponded nodes in graphs and the predicates Blue, Red are corresponded to node labels while E' is corresponded to edges. Therefore, (pxx determines whether a node x is Rod and has a Blue neighbor.
In this paper we focus on a fragment of the first-order logic which allows the utilization of counting quantifiers 'Nt The semantic of the quantifier 32N where N (1,2, is describe "there exists no less than N variables such that". For example, consider
/ (x) = 2 (F( v) A Blue(y))
2

---

Published as a conference paper at ICLR 2025
(x) is true iff has 2 or more Blue neighbors. Such family of logic formulas is called First-order Logic with Counting quantifiers (FOC) and possesses following property.
Proposition 1. (Cai et al. 1992) For any graphs G, H, k- WL assigns the same color to and H iff all FOC formulas with more than k variables classifies G and H the same.
Graph neural networks. GNNs can be generally described as graph functions that are invariant under isomorphism. Most popular GNNs follow color refinement paradigm Zhang al. (2024) to achieve such invariance: they maintain a representation for each node (or more generally, node tuple) and iteratively updates these representations via combination and aggregation functions. Consider, for example, message passing neural networks (MPNNs) Morris et al. (2019), which maintains a representation (x)) for node a at layer I. The representations are updated using the following formula:
X (x) COMU) (x), AGG (fx"
where (OM represents an arbitrary function combining two representations and AGG (H- B) represents an arbitrary permutation-invaiiaa function that aggregates multi-set of representations.
There also many other popular GNNs, which are listed in Appendix C Generally, these models maintain representation ( (u) for node tuple at layer Let L be the total number of layers of
GNN model. Then the representation x (1)(() ) for node tuple u at layer T, serves the output of the GNN. Since this paper studies the relationship between GNNs and logic formulas, we focus on GNNs with binary outputs (i.e., true and false).
LOGICAL EXPRESSIVITY OF GRAPH NEURAL NETWORKS
3.1 EQUIVALENT LOGIC SETS
Given GNN model M and a logic formula yp, let x(u) be the output of M for node tuples u e V We say M captures if the results of &o are reproduced by M, Concretely, M captures y if the orders of M and op are equal, and (p( = x(u) holds for arbitrary graph and u Vk, In this paper, we attempt to answer the question: what formulas can GNN models capture? This leads to the following definition of logical expressivity.
Definition 2. Given a family of functions X (e.g. a class of GNNs) where each function X E X maps k-order node tuples to (true, false), the equivalent logic set of X' is subset & of first order logic formulas satisfying:
The order of each yp E + is k;
For all E 4, there exists E X' such that for arbitrary graphs G and u E Va p(u) true iff x(u) true, and we say X captures s.
A FOC formula is captured by X iff it in d.
Given arbitrary positive integer N and E X' there exists &p E & satisfying: for any graphs with no more than N nodes and u E Vgg ppu) = true iff x(u) true.
Given any graphs G, Hl and E VL v V all x X cannot distinguish u, v iff all logic formulas E & classify u, v the same.
In our definition, we emphasize the equivalence between logic formulas and GNNs by stating that the discriminating power of all yp E & and all x E X' are equivalent, which follows the setting in Cai al. (1989). Also, we attempt to study the one-to-one correspondence between each GNN model X E X' and each y E Φ. The ideal statement would be: given arbitrary X E X, there exists p &b such that (u)) X(u) for all possible However, there does exist GNN models which is not captured by any logic formulas, and thus we relax the statement to be the forth statement in Definition 2
3

---

Published as a conference paper at ICLR 2025
The equivalent logic sets therefore sufficiently describe the logical expressiveness of GNN models. Moreover, similar to the homomorphism expressivity (Zhang et al. 2024). the metric of equivalent logic sets is also quantitative, precisely describe their expressiveness, making it finer than metrics based on graph isomorphism tests which only provide qualitative results. Moreover, the equivalent logic sets can also be used to compare the expressivity of different GNNs; a class of GNN models M1 is more expressive than M2 iff' 42 C 1 where 1 L2 are the equivalent logic set of M1 and M2 respectively. Above all, the significance of logical expressivity lies in its interpretability:: we can not only describe what patterns GNN models can capture, but also understand the expressivity gap of different models by studying the difference of the corresponding equivalent logic sets.
can identify distinct logic sets for different GNN models that
3.2 DESCRIBING LOGICAL EXPRESSIVITY FOR GNNS
is evident that the equivalent logic set of GNNs can be infinite. We utilize a recursive construction procedure to describe such sets, similar to previous works. Consider the set of graded model logic & dde Rijke 1996). & is defined by specifying how its elements are recursively constructed: to begin with, let Col(x) E & where Col represents node colors. Each element of &b is either Col, or one of the following:
-p(x),
((z) ('(z,, EZ (E(z, v) A p(y)),
where y,, s E + and N is positive integer. Therefore, we define & by specifying how its elements are constructed, starting from the input node colors Col. For notation brevity we can abbreviate the definition into one line:
((x) = 2NN (z)(()) A E(x, (x) I x'(x) A (xx Col(a:),
(1)
with the convention that logic formulas oo together with its superscript variants vp', sp" belong to the same logic set &. In Section 1. we discovered that Eq. [ describes the equivalent logic set of MPNNs with undirected, homogeneous input graphs.
4 GENERAL AGGREGATE-COMBING NETWORKS
To formally discuss the logical expressivity of arbitrary GNN models, we first summarize GNN models including Message Passing Neural Networks (Xu et al. 2018), Higher-order GNNs (Mor- ris et al. 2018). Subgraph GNNs (Bevilacqua et al. 2021), via unified design paradigm namely General Aggregate-Combine Combine Neural Networks (GACNNs). The basic idea is straightforward: we decompose the structure of different GNN layers into the same, principled aggregution and com- bination function series, which further enable us to study the expressive power of different GNN models via a unified framework.
Formally, let (u) be the representation of a k-order node tuple u E D computed by the I- GACNN layer. The (1 + 1)-th GACNN layer takes (u) as input and evaluates x (u+))(u) for E Dk (u+ computed by x (u) via sequence of two operations: combination (denoted by COM) and aggregation (denoted by AGG) COM(..) represents arbitrary function combining two representations, and AGG represents a permutation-invarie
function that aggregates a multi-set of representations. The evaluation of GACNN layer is decomposed into a series of intermediate variables (x(") define either
1.. Denoting Xo = (!)) and XK+1 = x (I+1), we
(I)
,.., xx
x (u) = CC (t) or (²) - ACG!" (IIEN
(v)
S 11, COM." is a combination function, AGG is an aggregation function and (u) is the generalized neighbor of u defined by the GNN model. Specially, we denote by (0) = (u) the initial representation of u. The above definition generally expresses the aggregation and combination steps of GNN layers.
where S j.k
Example. To better introduce the idea of GACNNs we illustrate how MPNNs are described by the above GACNNs construction steps. Consider MPNNs Xu et al. (2018) whose layers are defined by
x ((+) = C (x (x),
(ffx0) (v) N()))
4

---

Published as a conference paper at ICLR 2025
@
(a)
(b)
(c)
Figure I: Left: the structure of the example GACNN. Middle: the structure of the equivalent logic sets, each corresponding one of the nodes in the left GACNN. Right: the structure of the equivalent logic sets of the left GACNN, regardless of the number layers I.
where æ, y denotes nodes in graphs. We can simply decompose one layer of MPNN into
x (x) COM!) (x))
Xi (x) O (1 N())))
In this manner we describe the MPNN layers using the principled GACNN framework. For more ex- amples, appendix G.6 how we build popular GNN variants using the GACNN framework.
The advantage of decomposing GNN layers into a series of the principled aggregation and combination procedures that we can unify the study of complicated GNN models into the study of AGG and COM modules. Consider, for example, the Local 2-GNN model. The evaluation of this model can be illustrated as Figure (a), where the node (1++1 represents represen- tations of all nodes layer / + and is evaluated directly by Xi (!) and (1) which are again evaluated by their children along the hierarchy until (") It is evident that by explicitly expanding the evalu- ation procedure of X (1+1), the whole and complicated GNN computation structure is broken down into small and simple pieces containing only two types of computation: let Xp be (parent) node, then if Xp only has one child Xr. Xp is evaluated in the form of Xp AGG, )) otherwise Xp has two children XI. Xr and evaluated by X = COMp (Xi, X+). In this manner we break down the computation procedure of GNNs into principled aggregation and combination procedure, each corresponding to a parent-children pair in the computation graph. We next investigate the logical expressivity of GACNNs by studying the local property of such parent-children pairs.
Structure of GACNNs.
5 ON THE EQUIVALENT LOGIC FRAGMENT OF GRAPH NEURAL NETWORKS
In this section discuss the separation power and function approximation property of general graph neural networks by providing the equivalent logic set of arbitrary GACNNs.
5.1 EQUIVALENT LOGIC SETS FOR GENERAL. COMPUTATION PROCEDURE
For now let relax the utilization of GACNN models and focus purely the two types of compu- tation units AGG and COM proposed in Section 4 Concretely, suppose a set {x1, X2.... Xx) AGG, (vl v (G))))), (=(
each Xt for & [K] is defined by either (u) COM; (u), (u))). or (i(u) = INIT; (u) where i > j, k. Moreover, X maps node tu- ple binary outputs (true, false). We next show that it possible to find the equivalent logic sets of XK.
Theorem 3. Let Xe be the set of all possible X defined above [K]. There exists {$1,... 4x} defined below, such that & k is the equivalent logic set of XX-
X=(u)= AGG, (lxx(v) V
- p = E2N (p)(v) IvEN)(w)) (1p((u)) (u) A (u)),
5

---

Published as a conference paper at ICLR 2025
F(0)
F
F(2)
(a)
(b)
(c)
(d)
(e)
Figure 2: (a) (d): An illustration of logic formulas and GNN behaviours. (e) - (f): An illustration of the subgraph used for construct the homogeneous expressivity, (e) corresponds the construction of up: Aryzwu ((F(x,)) v) A Ely, =) A Ely, w) A F(w,u)) (f) corresponds to 2-FGNNs.
Xi(u) COM, (u)
(u( == (u(() (u)(u) 74((()) (u) A (
xi(u)= INIT; (u) - (u(u)) == atp(u) -v((()) (u(()) (f)
where p o9 F 9j 4x Pk
4 for i, [K].
Note that by denoting (:( atp(u) u), mean that p E c is capable of capturing all structures of the subgraph induced by u. Concretely, for each possible color Col of atp, there exists a sp cool (u) that is true if and only the color of assigned by atp is Col. the indicator: ccondition is true iff the condition is satisfied.
The results Theorem specifiies the construction equivalent logic sets for arbitrary computation procedure built upon aggregation and combination functions, which is not only confined to graphs and GACNN models. As the central finding of this paper, it enables the study of complicated models built upon multiple heterogeneous layers and graphs containing node and edge labels. Consider Figure for example: the equivalent logic set of each node in the computation graph in Figure (a) only depends on its local neighbors. If the equivalent logic set ((() of (") known, all logic sets in Figure (b) are specified by Theorem 3 This indicates that once the input representations can be described by logic formulas, we are able determine the logical expressivity of arbitrary functions over the input representations built upon aggregation and combination functions.
Remark. The logic formulas in Theorem are described using operators :²5 and A, which follows the settings in previous works (Barceló et al., 2020). Each operator is corresponded to specific property of GNNs. First, the major characteristic of GNNs as neural networks that GNNs make predictions based on not only the current instance (e.g. node), but also its relation with others (which is expressed by edges in graphs). This is realized via the aggregation of information among nodes. The logic operation 32 which expresses "exists least N", exactly corresponds to this property: consider Figure 2 (a) for example. Suppose we want to color a node as blue if it has two red neighbors. GNNs achieve the target by directly explores the neighbors of the current node æ and decides whether it is Blue by aggregating the colors of its neighbors. Once GNN found that there 2 red nodes in its neighborhood, decides the current node should be colored blue. Logic formulas achieve the same target by noticing that for a node x, if we can find two nodes y that satisfies Red(y) E(x, y). the color of x should be blue. This process can be expressed by Blue(x)= == _ (Red((y) A E(z,y), Therefore, we can understand the aggregation procedures in GNNs via the logical operation 32N More generally, consider Figure 2 (b), and suppose we want to decide two nodes (æ, y) are linked if they are connected via red node. This can also be done by aggregating the neighbors of x and y: once there is a common neighbor of and y which is colored red, I and y are linked. This can be expressed by the logic formula Link(æ, y) == (z, 2) A Red(z) A E(2, y)). In real world, this is useful for link prediction tasks: for example predicting whether person is another person's 's y grandparent in a kinship graph, which is realized by checking whether there exists z who x' child and y's parent. The procedure can be similarly expressed by Grandparent (I. v) = Az(Parent 2) A Parent

---

Published as a conference paper at ICLR 2025
Second, the operators and A are used to recombine existing logic formulas to obtain more com- plex ones. This implies the ability of GNNs to recombine existing information and make complex predictions. This ability is crucial for practical tasks: for example in molecule classification tasks it is necessary to recombine the raw input features of each node to predict molecular properties. Con- sider (c), and suppose we want color node blue if is neither red gray. Obviously this can be done by a GNN layer without aggregating the neighborhood information. A logic formula Blue(z)) = -R) A -Gray(a (a)) exactly expresses this. Consider a more complex example Figure (d). and suppose we want to color a node gray if it has red neighbor and a blue neighbor. This can be realized by Gray(z) == i (a:) A (2())) where ff (z) == By (Bluc(y)), (P2(2) == (x(Re(22). In this manner, we recombine the information 1I,, PP2 obtained by aggregating the neighbors of x.
5.2 EQUIVALENT LOGIC SETS FOR GACNNS
In this section we formally describe our results for GACNNs. We assume a L-layer GACNN layers defined in the form of Eq. 2 For layer I E [L], let (1) be the output representation at layer I and let { {x1 ,...,.....
(1) (1)
} be the set of intermediate representations when computing x (1+1) from x
Similarly, we denote 4.()) to be the equivalent logic set of x( and e.") the equivalent logic set of for E [K]. Obviously (()) and ( for E [K] and I E [L] are directly defined by Theorem which directly leads to the following result:
Corollary 4. The equivalent logic of T-laaer GACNNs defined above is given by $(L).
Corollary 4 requirrss to specify the number of GACNN layers L. To derive a general result for all
GACNNS regardless of the number of layers, we propose the following proposition.
(1) Proposition 5. Denote Xo = XK+1 x((+1) and $ Øk+1 Do = o Let $(1), { (L)
HE(K]
be the equivalent logic sets defined above. Then, + = Ur llL) and 4; = U 10th for i E [K] are defined by
Xi (u) A (ffx5 13) (x) (x) Ivee ( for E [0, oo)
(u(u) = 3Nt v (1)(v) IveNe(w)) (mpp(u) (/(() A (u() atp(()).
X: (((()) C
(1) (xg) (0)
(u), xf (1 (w) for 1 E (0,
( == ( pp (u) (1) (4(11) ^ (u) atp("))
where ps, 9. of E 22 p, E 2 Ph E for i E (0) K + 1].
The difference between Proposition 5 and Theorem Is that we now allow the construction of arbitrary number of GACNN layers. As long as GACNN layers share identical structure (which holds for most GNN models), we can fully describe their logical expressivity by & regardless of the number of layers. The structure of logic sets in Proposition 5 is illustrated in Figure (c), where each set is irrelevant to the number of layers/ / and is constructed recursively. Given any class of GNN models, so long we can break down a layer into series of aggregation and combination operations, we can formally define its logical expressivity using Proposition
About graph-level readout. Generally, GNNs compute graph representations by aggregating node tuple representations, i.e. XG AGG (ffx()) (z) (u) e V* V*)]) where L is the output layer. We determine the equivalent logic set of xG below.
Proposition The equivalent logic set &G of the graph representation XG defined above given by
PG == 3NN (<(())) 1-w'g w'a A w/, where Pa., &c. 4'6 E &a. and y is the equivalent logic set of (L).
The results in this section provide general method for determining the equivalent logic set of arbi- trary GACNNs. In the remaining of this paper, we utilize these results to discuss several important topics implied by the logical expressiveness of GNNs.
7

---

Published as a conference paper at ICLR 2025
6 IMPLICATIONS
With the complete description of logical expressivity for general GNN models in previous section, we now discuss how these results provide novel insights into understanding modern GNN frame- works. In this section, we highlight the significance of our theory by introducing important results induced by our theory.
6.1 REGARDING EXISTING GNN MODELS
First of all, we apply our results to formally describe the logical expressivity of popular GNNs
including models for graph-level or node-level prediction MPNNs (Xu et al. (2018). Subgraph GNNs |Bevilacqua et al. 2021 Qian et al. 2022), Local GNNs (Zhang et al. (2024), Folklore-type GNNs (Zhang et 2024) and models for link prediction NBFNet (Zhu al. 202T). SEAL (Zhang al. 2020), etc. The details of these models are in Appendix For brevity we make the convention that the equivalent logic set of each class of GNNs represented by and denote by y,, G' E + the elements of Φ. To properly express & it is sometimes convenient to also define an auxiliary logic set which helps with the explanation of &b We denote v. v',,.. E Vi as such auxiliary logic sets. The result is summarized in Proposition 7 For notation brevity, since the terms in the form of p := = 4 A x" atp emerges in the definition of all logic formulas, they are omitted in the following description.
Proposition 7. The equivalent logic sets of GNN models can be separately defined as:
MPNN: ((x) := 32 (1p' A E(y,x)), where E is the edge predicate.
Subgraph GNN (weak):
p(œ) = 32% (v(z, vi) v) 3 (1/ 2) A E(z,v)).
Subgraph GNN (strong):
p(x) == 3 y (4'(v) A (l ((., := 32 N (b(z, 2) A E(2,y) (v(())
*
NBFNet: ş(r, v) = 22
8)).
Local 2-GNN: p(x,y) = ==
F(2, | (E(x, (B,,
2-FGNN: plz, y) == 228 (e(,,
SEAL (MPNN):
*((,y) == 3N z (v(2, 2, B)) (0, == 32 N (v(a,, w. y) A E(w,
2-GNN: ((x,y) = 32ル 2 (v'(xr, 2)) | (2((=,)))
Proposition 7 gives a unified description of the logical expressivity of popular GNN models. The result of MPNNs follows Barceló et al. (2020). Following up, it is obvious that Subgraph GNNs (weak) surpasses MPNN by modeling more complex relations between nodes: rather than simply the edges E, they deploy the more general logic formulas th for modeling relations between nodes, which is obviously more powerful. Continuing, Subgraph GNN (strong) further strengthen y by not only allowing the single-source update pattern (xx == 32N 2 (v/ (x,2)) E(z, y)), but also ag- gregating information across different sources ((x, v) == (yy) (since :(v) aggregates (² v) with different sources =). The rest of GNNs compute node-pair representations. Starting from NBFNet. it models the relation between two nodes cfx, v) by checking intermediate nodes and its relation w.r.t. the two end nodes (z, 2), E(2. 22.0 y). This is useful for link prediction tasks, e.g. to pre- dict whether two nodes are connected Connect(z, y) := 3z (Connect (z, y) A E(y. 2)) E(x, V), which predicts the unknown Connect relation by utilizing the known edges F. This pattern is sim- ilar with the Bellman-Ford algorithm BBrrs & Theodorakopoulos (202)), which is single-source shortest path algorithm. The logic formulas sp(x, 3) corresponding to NBFNet are also constructed with the single source node x. Local 2-GNN extends NBFNet by considering two sources x, y sepa- rately, which allows the construction of more complex logic formulas. 2-FGNNs further generalize by defining s0(æ, y) in multi- source manner, analogous to Floyd shortest path algorithm. SEAL also defines ((x, 3) in a multi-soure manner, but it instead constructs (xx 2, y) and uses the inter- mediate nodes z to perceive the relation between x; y simultaneously. 2-GNNs, although compute
8

---

Published as a conference paper at ICLR 2025
node-pat -ade-ppirrre representations, not suitable for link prediction since it fails to even express the simple logic rule GrandParent((; y) := 3e (Parent 2). A Parent y)).
6.2 STRUCTURAL AWARENESS OF GNNS
There has been several works that study what graph structures different GNNs are aware of, such as cycles, cliques, etc. These concepts can be unified with logic formulas. For example, determining whether node is in a 3-clique can be written as
c3 (a) By, (F(x,,) A E(U,2) ((2,)))
Therefore, whether GNN models can capture 3-clique patterns depends on whether it captures PP-ellique- However, determining 3-clique is a trivial task, and in practice it is often necessary to study whether GNNs can capture more complex structural patterns. We consider the concept of homogeneous expressivity proposed by Dell al. (2018); /Zhng et al. (2024).
Homomorphism expressivity. Homomorphism expressivity is theory developed to precisely describe the structures of graphs being captured by GNNs. Concretely, let
(Va,Ea), H = (Vn, Enr) be two graphs. A homomorphism from F to G is mapping π VG - V/ that preserves labels (if any) and edges, i.e. (T(u), (()) E EF for all (u, v) E &g and {(u) = {(T())) for all nodes u, (u, v) = ((TT(() (u), T()) if there are node labels or edge labels respectively. Hom (F, G) is defined to be the number of homomorphisms from F to G. The crux is, to find all subgraphs F' for GNNs such that, for all pairs of graphs G, H, GNNs distinguish G, H - Hom F, G) + Hom H). Such set of subgraphs is referred as the homomorphism expressivity of GNNs. Dell et al. (2018) gives the homomorphism expressivity for 1-WL (MPNNs), while [Zhang et al. (2024) extends the results to several popular GNN models.
Similar as previous discussions, in this section we aim at providing general method to determine the homomorphism expressivity of GACNNs, based our findings about equivalent logic sets. Suppose we are given a class GACNNs whose equivalent logic set is Q. To simplify the discus- sion, we first assume node/ / edge labels. We assume that the concept of neighbors in GACNNs is deseribed by composition of edges: for example in MPNNs the neighbors of a node x is defined by 1 (x) == E(x, y) where E is the edge predicate; similarly in NBFNet (m.:)eNN == Ely, z). The homomorphism expressivity F can be constructed from the logic formulas in via the follow- ing procedure.
1. Remove all formulas in 4 that contains negation 32" where 2:
2. For each formula yp E Φ, add graph F into FF which is defined below:
(a) There exists a bijective mapping T from var(()) to Vr, i.e. from the variables in (we avoid the reuse of variables to the nodes in F.
(b) For any variables x. y E var((), E(x, y) is a term in y iff E(T(x),T(y)) is an edge of F.
A discussion about the reuse of variables and why we avoid this technique is in Appendix B We now explain the procedure. Consider for example constructing a subgraph F for the logic formula 6o Eryawu ((E(z, y) Ely, 2) A Ely, w) A E(w, u)). The construction of F is illustrated in Figure (c), where F possesses node corresponding to each variable x, y, 2, u in yp and contains edges F. (xx, (), Ely, =), Fly, w) and F(w,, u). We have the following result:
Theorem 8. Given class GACNN models and suppose & be the equivalent logic set. Let F be the homomorphism expressivity constructed by as discussed above. For all pairs of graphs G, H. the following statements are equivalent:
1. Hom(F, MM,FFFG G* Hom (F, H)r all F F.F.
2. All GACNNs do not distinguish G and H.
E.g. pdx) := Exx u) A Ex(E(z, v))). The variable x reused. This is a technique often used in the context of logic to reduce the number of used symbols. In the construction of homogeneous expressivity we avoid this technique and write pp()) as (xx) = Fy( (F(x, y) A A2(F(( v))) that all variables are explicitly expressed. As result, there 3 variables x, y, 2 total.

---

Published as a conference paper at ICLR 2025
Theorem 8 validates the effectiivness of our construction procedure. Together, provide a gen- eral method to identify the homomorphism expressivity for arbitrary GACNNs, which extends the known results in previous works (Dell et al. 2018 Zhang al. 2024). Meanwhile, we have solved a conjecture in Zhang et al. 2024). i.e. when a GNN can be described by a GACNN, its homomor- phism expressivity exists and is given by Theorem g
Example. We illustrate the strategy of recursively constructing homogeneous expressivity F by investigating 2-FGNNs, whose equivalent logic set & (removed negation and 32t for N 2 2) is given by pzz,, y) == 3e (a, 2) (z, y)) yp' (x, A (" v) atp y). Let 4(0) be the equivalent logic set of (-layer 2-FGNNs. Let F(() be the homogeneous expressivity constructed at iteration I. For F(() at beginning, there are only two graphs in F(O) corresponding to ol()) ((1)
(z. y) == atp( o y), as illustrated in top of Figure (f). At the next iteration, we consider the more complex (12), which is given by
where (2,
(0) v) == 72 (v1 (I,, 2) A 22 00 (2, (2.1))
Pi (x, v) A F22 (Ir, v) atp v)-
We can simply construct F(I) by reusing the known results about F(O) Specially, to construct (p (I, = 3z ( (0) (xx, =) A 92 (z, (z, we start from an empty graph F and add three nodes Ux: Uuy U2 corresponding to variables z, y, in (p()) Then, we replace Us) and (U2, U2) with the known subgraphs in F(0), illustrated in middle of 2 (f). By continuing this procedure, the homomorphism expressivity F is constructed, as illustrated in bottom of F
6.3 EXPRESSIVITY COMPARISON
It is also convenient to obtain the upper bounds with regard WL tests thanks the relation of logic and WL studied in Cai et al. (992), as well as comparing the expressive power of different GNN models:
Proposition 9. Suppose the equivalent logic set of a class of GNN models is t. Then, the expressive power of the GNN models is bounded by k-Wl, iff all logic formulas in tb can be expressed with at most l variables.
Note that it is trival check the number of variables in setting: recall that in Propo- sition [ the equivalent logic sets are defined by specifying the grammar of logic formulas. This implies that can simply check the number of variables emerged in the grammar. For
example, consider Subgraph GNN (weak). There are 2 free variables {I. y) in sp(x) ==
A (x) (*p(r) and 3 variables {xr, y, y, in (xx := g2N (6'(a z) A E(2,8) v)) (x) ('(x)) A (x)) E(x, y). Therefore, the expressive power of Subgraph GNN (weak) is bounded by 3-WL. We summarize the section by introducing following
g2N y (yp (y) A (xx y)) (xxx (x((x)
results for popular GNN models.
Corollary 10. The expressivity of GNN models satisfies: MPNNs I-WL <. Subgraph GNNs (weak) NBFNet < SSubgraph GNNs (strong) < Local 2-FGNN < 2-FGNN = 3-WL, 1-WL < SEAL < 4- WL.
7 LIMITATION AND CONCLUSION
Limitation.
The results of this paper are applicable to GNNs that can be expressed by GACNNs. Our framework is not applicable for GNNs which do not consist sole of aggregation and combination operations. For example, Graphormer-GD (Zhang et al.) (023) which injects distance information into node pairs and cannot be described by aggregation or combination layers.
Conclusion. In this paper we present novel framework for systematically describe the logical expressivity of GNN models built upon combination and aggregation operations. We analyze the logical expressivity of popular GNN models and provide insight about many important topics in graph representation learning including expressivity comparison, structural awareness of GNNs, estimating WL expressivity, etc. Our framework serves as toolbox to understand both existed and new GNN architectures: with new GNNs being designed, one can easily obtain the logical expressivity, study the substructures captured by them and bound these models with WI tests.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2020. URL https:
www.seeatttttt. wttps//mmmiicccooo.orooooo/////o :tw.:laaa...rrroooutt:::::::::a 235358622
John Baras and George T'eoodorakopoulos, Path problems in networks. Springer Nature, 2022.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan- Pablo Silva.
The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.
Pablo Barcel'o, o, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Neural Information Processing Systems, 2021. URL https: //api semant cscholar wrg./org//oooeoeeee (tgg//ooppsSTD:342200
Leon Bergen, Timothy J. O'Doneel, and Dzmitry Bahdanau. Systematic generalization with edge transformers. In NeurlPS, 2021a.
Leon Bergen, Timothy J. O' O'Donnel, and Dzmitry Bahdanau. Systematic generalization with edge transformers. In Neural Information Processing Systems, 2021b. URL https://api.
wttp://aaarrrr/oouussstt..a semanticscho org/ Corpus ID: 2
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, G. Bal- amurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. ArXiv, abs/21 10.02910, 2021. URL https:/ /atp://app... http://.....ss....p....mmm iesemnnticscoolass org/
CorpusTD:2384000
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Lio', Guido Montúfar, and Michael M. Bronstein. Weisfeiler and lehman go cellular. Cw networks. In Neural Information Processing Systems, 2021a. URL hattps://apt /ttt:://ap..eennnicccchhoot semanticschola:
Teg/CorpusID:
235606230
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Lio', and Michael M. Bronstein. Weisfeiler and lehman go topological: Message passing simplicial net- works. ArXiv, abs/2103.03212, 2021b. URL https: aapi..... eeemanticschollll. .org/
CorpusID:23211063:
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 45:657-668, 2020. URL https://api.
bemanticscholar... org/ ortp://cccccolaaoooooooouuuuuuaa
21970861711
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1989.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In ICLR, 2023.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? ArXiv, 04405, 2020. URL http:://app.eeemamticcccooooooo
orr//oopusID:211000 :
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. ArXiv, abs/2110.00577, 2021. URL
org.
CoIpusIDD233253223
M. de Rijke. A note on graded modal logic. Stud Logica, 64:271-283, 1996. URL https
7/api. semant icachola wtw..rrg/oooopss::911ee.....

---

Published as a conference paper at ICLR 2025
Holger Dell, Martin Grohe, and Gaurav Rattan. Lov', ass meets weisfeiler and leman. arXiv preprint arXiv:1802.08877, 2018.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. ArXiv, abs/2206. 140. 2022. URL
https://ap1 semant icschol ar. :t:p://oooput1:::9990000
Floris Geerts and Juan L. Reutter. Expressiveness and approximation properties of graph neural networks. ArXiv, 0as/2204.046611, 2022. URL http:s///pp..smmanticccco....s org/
CorpusID:24808450
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Alexander Rieck, and Karsten M. Borgwardt. Topological graph neural networks. ArXiv, abs/2102.07835,, 2021. URL
Xingyue Huang, Miguel Romero, Ismail Ceylan, and Pablo Barceló. A theory of link prediction via relational weisfeiler-leman on knowledge graphs. Advances Neural Information Processing Systems, 36, 2024.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Neural Information Processing Systems, 2019. URL
org/Corpus 152282222
Thomas Kipf and Max Welling. Variational graph auto-encoders. ArXiv, abs/16l 1.03088, 2016a.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02900 2016b.
Liu, Bernardo Cuenca Grau, Ian Horrocks, and Egor V. Kostylev. Indigo: Gnn-based induc- tive knowledge graph completion using wair- encoding. In Neural Information Processing Systems, 2021. URL https:://///m http://pp...aaaaaaaaooooaaoooa.a ott.a/a.........oror......2.111.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. ArXiv, abs/1812.099// 2018. URL https: api www.nticscholla.t...... org/ Corpus ID: 5165556999
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. ArXiv, Abs/1195.1111
101.111166...1111.11111111111116 1136, 2019a. URL hwwp::ttpssstcc..... /api http:/:///a...smattnammm semant iesnanttcscholass org/
CorpusTD: 66228757
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. ArXiv, abs/1901.00944. 2019b. URL attts:://api.semanttiioo
org/
CorpusID:55316743
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gau- rav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neu- ral networks. In AAAI Conference on Artificial Intelligence, 2018. URL https:://pp.
semanticsch lar.
ar. org/CorpusID: 5291 9090
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Gauray Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation--qqivaat ing, pp. 16017-16042. PMLR, 2022.
graph networks. In International Conference on Machine Learn
Martin Otto. Graded modal logic and counting bisimulation. ArXiv. abs/1910.00039, 2019. URL attps://app semant iereeanticcche icscco ar. otg/ ID: 2006103313300
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network tensions. ArXiv, 1288422011.1884,, 2022. URL https://////... /tp../api..a www.nt org/
CorpusTD:246430444
12

---

Published as a conference paper at ICLR 2025
Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. In International Conference on Machine Learning, pp. 28191-28211 PMLR. 2023.
Chen Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Or- dered subgraph aggregation networks. ArXiv, abs/2206. 11668, 2022. URL https://apt
wtt/Corppss:::299222222222 24999924414
Komal K. Teru, E. Denis, and William L. Hamilton. Inductive relation prediction by subgraph
reasoning. In International Conference on Machine Learning, 2019. URL https://app semanticscher arr. wttp:orroo//ttt1111111
Erik H. Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphismm-based graph neural nets.
In Neural Information Processing Systems, 2021.
htc//oorpussD::22227755
232092767
Kristina Toutanova, Xi Victoria Lin, Wen tau Yih, Hoifung Poon, and Chris Quirk. Compositional learning of embeddings for relation paths in knowledge base and text. In ACZ. 2016.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXiv: 110.00181, 2018.
Tuo Xu and Lei Zou. Rethinking and extending the probabilistic inference capacity of gnns. In The Twelfth International Conference on Learning Representations, 2024.
Jiaxuan You, Jonathan M. Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In AAAI Conference Artificial Intelligence, 2021. URL https://api. semanticscho org/Corpus :31 698873
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gans via graph biconnectivity. ArXiv, 0D0/2301109500 2023. URL https://api.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: quantitative framework for gnn expressiveness. In International Conference on Ma- chine Learning, 2024.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Neural Information Processing Systems, 2018. URL https:/ wemp.sssssatttccchollss... org/ CorpusID:3573113
Muhan Zhang and Yixin Chen. Inductive matrix completion based graph neural networks. In ICLR, 2020.
Muhan Zhang and Pan Li. Nested graph neural networks. ArXiv, 10./2110.111999 2021. URL : 239885856
https::/app www.nt aor.eiaa........oooooooiio wrtg/orpps
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using
graph neural networks for multi-node representation learning. In Newral Information Processing Systems, 2020. htRLhttts: http:///aapaaaaaaiaaae..mm www.seeeetnnnsooeeeeeee www.aaa.oooo.ooooo...iaaaa.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplift- ing any gnn with local structure awareness. ArXiv, abs/2110.03753, 2021. URL https:
//api. www.ssssnnniccchllrr...... http::/ccc....c.a.ooooooooaaaaa.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford net- works: A general graph neural network framework for link prediction. Neural Information Processing Systems, 2021. URL patts://aap/ semanticscholas org/CorpusID.
235422273
13

---

Published as a conference paper at ICLR 2025
A RELATED WORKS
In this section we discuss related works that studies the expressive power GNNs and several GNN models investigated in this paper.
Studying the expressive power of GNNs has been hot topic in graph machine learning community. Xu et al. (2018) investigate the expressive power of GNNs by relating MPNNs with 1- tests, making it possible to utilize many know results about WL. tests for the analysis of GNNs. Barceló al. (2200) study the logical expressiveness of MPNNs which is close to our work. Compared with them, we successfully design method to describe the logical expres- aggregation-combinntie
Expressivity of GNNs.
sivity for arbitrary aggregation combination networks and analyzed several important implications brought by our work, including homomorphism expressivity, comparison of expressive power, etc. Zhang al. (2024) investigate several popular GNN models and study their expressive power in the perspective of homomorphisms. Compared with their work, we propose a general method to deter- mine the homomorphism expressivity for arbitrary aggregation-coomiiatioo networks while solving a conjecture in Zhang et al. (2024) in the meantime.
To summarize, the major advantages of our works are:
(I) Our study establishes a deeper connection between GNNs and logic. Briefly speaking, previous works (Barceló et al. 2020) only study set & of logic formulas for MPNNS such that:
All logic formulas E & can be captured by MPNNs.
A logic formula can be captured by MPNN iff it is in 4
It is worth noting that the above statements only guarantees that the logic formulas can be captured by MPNNs. Intuitively, this does not establish an equivalence between logic and GNNs. Instead, in our work, we study a set & of logic formulas for GNNs such that:
All logic formulas E & can be captured by GNNs.
The GNNs are equivalently expressive with + in distinguishing non-isomorphic graphs.
Therefore, our theory reveals deeper connection between GNNs and logic (i.e. the equivalence between GNNs and logic.)t
(2) Our study specifies the logical expressiveness of arbitrary GNNs, provided that their layers are built using aggregation and combination functions.
(3) this paper, we establish a connection between logic and the homomorphism expressivity of GNNs.
Higher order GNNs. Since the works of Xu al. (2018); Morris al. (2018) that relate GNNs with the I-WL tests, it is straightforward to extend GNNs by imitating higher-order WL tests. Pre- cisely, k-order WL tests assign colors for k-tuples of nodes and perform color aggregation between different tuples. Similarly, instead of learning representations for nodes, many works choose to apply the message passing paradigm higher-order WL. tests to GNNs and directly learn represen-
tations for node tuples (Morris et al., [0188] Maron et al. 2019a 2018 2019h Keriven & Peyrr 2019
Azizian & Lelarge 2020 Geerts & Reutter 2022).
Subgraph GNNs. Since the higher order GNNs are often too expensive for larger graphs, many works try to find cheaper ways to design more expressive GNNs. variety works feed subgraphs to MPNNs. At each layer, set of subgraphs is generated according to some predefined permutation-
invariant policies, including node deletion (Cotta et al. 202I), edge deletion Bevilacqua et al. (202T).
node marking (Papp& & Wattenhofer] 2022) ego-networks (Zhao et al.) 2021 Zhang & Li 202 You
et al. 2021). We will focus on the unified ESAN framework proposed by |evilaaquaa et al. (021).
Qian al. (2022) Frasca et 2022 studied the expressive power of different branches of subgraph
GNNs.
There is another way to design GNNs that surpass 1-WL by structing structural features for GNNs. Chen et al. (2020) showed that regular MPNNs cannot cap- ture simple patterns such cycles, cliques and paths. Bouritsas al. (200)) Barcel' 'o et al. (2021)
Substructure counting GNNs.
14

---

Published as a conference paper at ICLR 2025
proposed apply substructure counting pre-processing. and add substructure information into node features. BBodnrr et al. (2021b al: Thiede et al. (202I); Hoon et al. (2021) further designed novel WL variants and proposed nuula- approaches that captures complex substructures.
GNNS for link prediction. Standard GNNs learn representations for each node. Early methods such GAE Kipf & Welling (2016a) GNN
encoder and decode link representations as a function over node representation pairs. These methods are problematic in capturing complex graph structures, and might lead to poor performance. Later on, labeling trick was introduced by SEAL & Chen (2018) and adopted by Grall. et al. (019)). (GMC/Zhag & Chen 2020)) INDIGO Liu et al. (2021). etc. These methods encode source and target nodes mark them differ- ently from the rest of the graph, and are proved to be more powerful than GAE. ID-GNN You et al. (2021 and NBFNet Zhu et al. (202T) both augments GNNs with the identity of the source nodes. Besides, All-path Toutanova et al. (2016) encodes relations as linear projections and proposes to ef- ficiently aggregate all paths with dynamic programming. However, All-Path restricted bilinear models, has limited link prediction capability and is also not inductive. Edge Transforoerr [Brggnn et al. (202 lab utilizes attention mechanism to learn representations for nodes and links. While also follows the 2-FWL message passing procedure, operates directly fully conneced graphs and have no proposals for simplifications as we do, thus it is not scalable to larger graphs. ELPH and BUDDY (Chamberlain et al. (2033) incorporate neighbor counting into node features to enhance the link prediction performance of MPNNs.
B WEISFEILER-LEHMEE TESTS
In this section we introduce the Weisfeiler-Lehmee (WL) tests and their variants. Weisfeiler-Lehman (WL) tests are a family of necessary tests for graph isomorphism. Apart from some corner cases (Cai et al. 1992). they are effective and computationally efficient tests for graph isomorphism. Its I-dimensional variant iteratively aggregates the colors of nodes and their neighbors and then injec- tively hashes them into new colors. The algorithms decides two graphs non-isomorphic if the colors of two graphs are different.
Extending from classic WI. tests, k-dimensional WL test (k-WL.) refines colors for node tuples. At beginning, the color of node tuple is set to be injective w.r.t. the structure of u. denoted as atp(u). That is, for arbitrary two tuples u = (41, (&.) and v (el,..., Ux). atp(u) = atp(v) iff' there exists an isomorphism π for the subgraphs induced by nodes in u, v and r(u)) vù for i I,... k. WL then recursively refines these colors until convergence.
B.1
WL (COLOR REFINEMENT)
The classic 1-WL test (Weisfeiler & Leman 1968) maintains color for each node which is refined by aggregating the colors of their neighbors. It can be easily applied on node-featured graphs (Xu et al. 2018) as in Algorithm
Algorithm 1: The 1-WL test (color refinement)
Input G = (A, X)
++00; 0:
2 ch + hash(ax,) for all v E Va:
while not converge do
d+1 + hash(c (fd, | uE (()))))s
1+1+1:
end
return (f o Vall:
The iteration converges when the partitions of nodes no longer changes. The 1-WL test decides two graphs are non-isomorphic if the multisets of colors the two graphs are different. The WL algorithm successfully distinguishes most pairs of graphs, apart from some special examples such as regular graphs. Similarly, given subset nodes C, 1-WL define its color as (fc, u E C)). and 1- distinguishes of nodes if the colors of them differernt.
15

---

Published as a conference paper at ICLR 2025
B.2 k-WL
The k-WL tests extend 1-WL to coloring k-tuples of nodes as in Algorithm 2 where we use v to denote tuple of nodes, G[ for ordered subgraphs. The neighbors (** (v) are defined follows: assume = (V,, Uk), then ~²
NY. (v)). where
(1) {{ (11, 11 u, e4,,... 0k) u V}
Algorithm 2: The k- WL tests
Input :G = (A, X)
11+ 0;
cg < -hash(G'u)) (() for all v E Vg:
while not converge do
d+1 hash(dt, [f TucluENNi (
1+l+1:
end
return
(1:4 I for all E v]))
B.3 F-FWL
The F-F CCai et al. 1989) test is equally expressive with the (k+1)-WLL test. has the same ini- tialization with [k- WL. The neighbors AV*(w) are defined follows: assume (U1, ..r Uk),
then then.V* (D) = {{A* f (v) u E V)). where
N (v) = ((u, U2,..., Uk), (01, U. ... Uk); (V1 (UI...., u. 2k))
Algorithm 3: The k-FWL tests
Input : G = X)
1-+ 0;
c t -hash(G(o)) for all E VG:
while not converge do
1+1 + hash(c,, (cu, (f u (x)))))
1+1+1;
end
return
(1:4 v Vo for all u E e)]
B.4 COLORS OF k-WL/ k-FWL
From the previous discussions k-WL and k-FWL both assign colors for k-tuples of nodes. The color of the graph G is defined by
cg Hash(ffc. co y* }}))
Similarly, given any subset of nodes S C V. we also define its color as
cs = Hash ((fc, Q s* }}},
C ABOUT GNN MODELS
In this section we decompose several popular GNN models using the GACNN framework. First, MPNNs Xu et al. (2018) whose layers are defined by
(1+) C (x)( AG ((x*W))eeN()))
16

---

Published as a conference paper at ICLR 2025
where z, y denotes nodes in graphs, be simply decomposed into
(x) COMP (x)))))
(x) (x)= AGG (xxW)leeNe
In this manner we describe the MPNN layers using the principled GACNN framework. To better explain our framework, consider Local 2-GNN JONN[Zhang et al. (2024) whose layers are defined by
(+))) COMO (x") AGG (ff ((xx)(x))) (
(3)
AGG (1xx
Similarly, we can decompose one layer of Local 2-GNN into
(x. COM (x (I.))
(=.y) coM th
(x.)) (z.0))
X2 (c, = AGG (1x0))))
@ (x, AGG ((==)
(4)
where COM C are combination functions satisfying COM (XM))")))) = COM" (x,X' for arbitrary representations x'"',x.
MPNN.
(x) = COM (x)) (ueeN))))))))
Subgraph GNN (weak).
(x) = AGG
v}f)) (v)
AGG x (x, y) = COM (x, AGG (1)"a)))AC(((()=====))))>))))))) (x"(x,))
Subgraph GNN (strong).
(1+)) v) COM (I.) ((x*(a)))= (o). ((x*))))))))))
(z) AGG (x.tt)(.xxllee))
NBFNet.
(v. (x.)) COM (x.) ((I()):))
Local 2-GNN.
x (1+1) COM (I, (Hax ACG (H))(a)))xeN)))))
2-FGNN.
(x,)) (x.y)= COM (x,) (1))) 12
SEAL (MPNN).
(x,1(xx221)) COM (x, AGG (
(e)(()))))))
(++1) = AGG (ff
17

---

Published as a conference paper at ICLR 2025
2-GNN
COM COM (I.)), ((xx(( AGG
(ffx ((xx))))))Z))))))
(x,u)
D NUMERICAL EXPERIMENTS
In this section perform numerical experiments empirically validate our theoretical results. The motivation of this section is to test the logical expressivity of several GNN models by checking whether they are able express specific logic formulas on synthetic data. Generally, the experiments are divided into two parts: one to test the node classification capacities of GNNs and the other to test the link prediction capacities of GNNs.
The experiments are designed as below. We conduct two types of tasks. First, we would like to test the GNNs' ability to learn logic formulas. In this part, we specify the target logic formula oo we want to learn. Then, we randomly generate graphs with initial node colors encoded by zero-one vectors. After that, we apply y on the generated graphs and label each node x (or node pair (a.y)) where (p(x) (or (z, y)) is true with target label 1. We then train each GNN model the graphs and observe the results. For each task the GNNs are divided into two classes: one for node classification and the other for link prediction. Second, we would like to test the GNNs' ability to distinguish non-isomorphic graphs. In this part, we manually construct several pairs of graphs and show that they can be distinguished by different logic formulas. Then, we test whether GNNs can separate the graphs. The detail of each experiment is presented below.
Experiment setting. For all GNNs choose the aggregation AGG to be sum, and the combina- tion function COM to be
COM(ar, y) W y²
where W is parameter matrix. We refer to GNN-k as the GNN model with layers, i... MPNN-1 refers to MPNN which has one aggregation-comminnttie layer. For the last layer, the sigmoid function selected as the activation function. For the rest of the layers, the ReLU function selected as the activation function.
We randomly generate graphs as follows. We consider Erdös-Rent Renyi graphs, which are random graphs by specifying N the number of nodes and the possibility for each edge to exist, We then randomly color each node with specified probability. After that, we apply the logic formulas on generated graphs and obtain the prediction targets for the GNNs. Each train and test graph contains 500 nodes. Each test-larger graph contains 1000 nodes.
D.1 LEARNING LOGICAL FORMULAS
D.1.1 NODE CLASSIFICATION
Target logic formulas. creasing complexity:
For node classification we consider three target logic formulas with in-
pi (x) Red(x) By (X( A Blue(=))),
(2(x) = 3y B) A E(z, A 2)y,
(2(x) == (y (v)).
We pick GNN models by analyzing the above formulas. f1 is expressed by MPNNs. y2 is expressed by Subgraph GNNs (weak) but not MPNNs. (Pa is expressed by 2-FGNNS but not Subgraph GNNs (weak). Hence, we choose MPNNs, Subgraph GNNs (weak) and 2-FGNNs. For Subgraph GNNs, we follow the node marking policy (Bevilacqua et al. 2021 and set the initial color of (r, x)) to be the color of z. For 2-FGNNs, the node representation of node is obtained by the representation of (x, .). The results are shown in Table We can see that the results meet our expectation.
Results about 101. 1P decides whether node is red and is connected to blue node via 2 edges. It can be decomposed by (z) == A Ay x) (v)()) and (y()) == Red(y) A y) A Blue(2)) thus it is simple and can be expressed by MPNNs. Also, according the decomposition two MPNN layers are required to express y1. Similarly, two Subgraph GNN layers are required to express 11. The results in Table satisfy this.
18

---

Published as a conference paper at ICLR 2025
Table 1 Results on node classification.
Algorithm
P1
AP2
Train
Test
Test-larger
Train
Test
Test-larger
Train
Test
Test-larger
MPNN-1
0.907
0.903
0.909
0.867
0.865
0,666
0.866
0.865
0.527
MPNN-2
1.000
1.000
1.000
0.863
0.863
0,556
0.868
0.878
0.657
MPNN-3
1.000
1.000
1.000
0.855
0.864
0.601
0.877
0.877
0.477
Subgraph-1 1
0,905
0.903
0.899
0.867
0.872
0.668
0.882
0.859
0.524
Subgraph-2
1.000
1.000
1.000
1.000
1.000
1.000
0.914
0.906
0.682
Subgraph-3
1.000
1.000
1.000
1.000
1.000
1.000
0,901
0,905
0.582
2-FGNN-1
1.000
1.000
1.000
0.865
0.862
0.666
0.857
0.847
0,531
2-FGNN-2
1,000
1.000
1.000
1,000
1.000
1.000
0,891
0.896
0.639
2-FGNN-3
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
Results about P2- f2 decides whether the node in a 3-clique and requires at least three variables M/, z and thus cannot be expressed by MPNNs. However, it can be expressed by Subgraph GNNs:
we can decompose 62 into (2(()) ;= (y i (z, y)), , v (z, y) := E( y) A (v>(,, (x, 2) (E 2)), (1, = E(x,2) 2). which directly corresponds to the equivalent logic set of Subgraph GNNs. Also, it can be seen from the decomposition that two Subgraph GNN layers are required to express 92., since there are two nested formulas 4/1, 1/2. For 2-FGNNs, two layers are required: we have (2)( == (bx x) and (bxx.2 == By(bi (I,, v), E(y, th1 (z, v) == 3z(E(x, x) E(z,v)). The results in Table meet the expectation.
Results about P3. fs decides whether the node is adjacent to 3-clique, which cannot be expressed by Subgraph GNNs. For 2-FGNNs, we can decompose 4s into (a(x) := (1,, ()r,, == Hy(1n1 (2r y) Fly, 1/1 (I., y) == Az(12(y, (22,,)) Fly, 2) A Fuel Ely, w) A F(w, z)), thus it can be expressed by 2-FGNNs with 3 layers. The results in Ta- ble I meet the expectation.
D.1.2 LINK PREDICTION
Target logic formulas. complexity:
For link prediction we consider two target logic formulas with increasing
si (2, = Red(x) A Blue(y), (2 3z(Blue(=) A E(x, z) A E(z,)))
We pick MPNNs and NBFNet. For MPNNs, the representation node pair (z, y) is obtained by combining the representation of node and node y. The results are presented in Table 2
About Pp. 1 is extremely simple: decides two nodes are connected if one of them red and the other is blue. This logic formula does not consider the relation between the two nodes, and can be expressed by MPNNs. The results in Table 2 meet the expectation.
About (22- Compared with 10,, $82 more complex and decides two nodes are connected if they are connected via blue node. Such form of p2 is more practical and considers the relation between the two node: for example, deciding whether one person is another one's 's grandparent in a kinship graph can be done by checking whether they connected via another person with the predicate "parent". However, MPNNs fail to express 62. NBFNet is sufficient for expressing P2, as we can decompose into 2 (z. 8) 32(v(z, 2) A E(2, v)) and ι(x in [ the expectation, where we can see that there exists a large margin between MPNNs and NBFNet for learning 222-
E(x, 2) A Blue(z). The results
19

---

Published as a conference paper at ICLR 2025
Table 2: Results link prediction.
Algorithm
yP
S22
Train
Test
Test-larger
Train
Test
Test-larger
MPNN-1
1.000
1.000
1.000
0.818
0.819
0.586
MPNN-2
1.000
1.000
1.000
0.817
0.817
0.328
NBFNet-1
1.000
1.000
1.000
1.000
1.000
1.000
NBFNet-2
1.000
1.000
1.000
1.000
1.000
1.000
2-FGNN-1
1.000
1.000
1.000
1.000
1.000
1.000
2-FGNN--2
1.000
1.000
1.000
1.000
1.000
1.000
Figure An illustration of several graph pairs.
D.2 SEPARATION POWER
We design several non-isomorppic graph pairs and test whether GNNs can distinguish the nodes / node tuples in them. This includes:
A cycle with nodes and cycle with nodes, as illustrated in Figure 3 left. They are 2-regular graphs. The task is to separate the nodes. The nodes can be separated by =(x) == ( (tl...)))(((() (xx y) == 3z(E(z, 2) A E(z, y) A E(z, y)). It cannot be expressed by MPNNs, but be expressed by Subgraph GNNs (weak) and more powerful models.
Shrikhande Graph and Rook's 's 4x4 graph as illustrated in Figure right. The task is to separate the graph. They are strongly regular graphs which cannot be separated by 2-FWL, and thus 2-FGNNs.
The results presented in Table
E ABOUT VARIABLES IN LOGIC FORMULAS
Consider the formula
(0x) = Red(x) A (y(( 3z(E(z,9))).
The formula has a free variable x which not bounded by the quantifier and two quantified variables y, which are bounded by 3. Therefore, the formula has variables in total. Given graph G, a grounding of (rxx) in G is a mapping y from the variables in yfxx to the nodes in G. For example consider the graph in Figure
4 There are groundings m,, 1/2 from (px) to it, with
7) (x) = U1, 771 (1) = U2 mi (z) = and 17 x) = 11, (g) = 02 (2) = Uy.
To reduce the number of symbols used in logic formula, there is trick which is to reuse the variable r and replace every occurrence of in with x, leading to:
g'(x) == Red(x) A By x)) Ex(E(x,
To ground vp (xx on G. one still needs to substitute the variables in ('(x) with the nodes in G. This indicates that in Figure 4 we need to substitute the outer variable in Red(x) with and the inner
variable r in 3x (xx, y)) with Vyy or Vs. Therefore, when the variables are reused, the grounding no longer well-defined mapping from variables to nodes, and the essentially different variables x, in (xx) are expressed by the same symbol x in (xx) To avoid such clunky situations, we avoid the reuse of variables.
20

---

Published as a conference paper at ICLR 2025
Table 3: Results on separation power.
Graph
MPNN
Subgraph
2-FGNN SEAL
2-regular
X
Shrikhande & Rook's 4x4
X
V1
V22
V3
V4
V5
Figure 4: An example graph which has two groundings for (f()) = Red(x) A By(E(y, x) A Ez(E(2,))))
The properties of F constructed by y. Recall that to construct the homomorphism expressivity, we construct graph F for y which defined below:
1. There exists a bijective mapping from the variables in yp to the nodes in F.
2. For any variables x, y in y,, E(x, y) is a term in y iff E(T(x),, T())) is an edge of F.
We define the concept of injective grounding:
Definition 11. An injective grounding from a logic formula yo to a graph is a grounding from to G' that maps different variables in yp to different nodes in G (without the reuse of variables).
It is now obvious that F is the minimum graph that contains an injective grounding from ip.
F LINK PREDICTION AND LOGIC
In this section we briefly discuss how the logical expressivity of GNNs affects their link prediction capabilities. We also attempt explain, why compared node classification or graph classification tasks, there often exists a larger margin between MPNNs and other advanced GNN variants (see, e.g. Zhu (2
Beginning with MPNNs.
The logic formulas expressed by MPNNs are of the form
(x) = 32. (yp' (v)) A E(y, x)) -upp y A Ag"..
For MPNNs, to predict whether pair of nodes (x. v) linked, it is common combine the representation of x and e.g.
pred(x, y) MLP(h hy),
where heg hy are the representations of and y respectively. Using Theorem it is evident that pred is expressed by
((r,)) = == (08) - et' A t".
(5)
Intuitively, this can be understood gathering the information of æ and y respectively, which does not consider the correlation between x and existed in the structure of the graph. To explain this more concisely, consider Figure (a). (a). For arbitrary &o defined above, (p(1) = =((2) = (P(4)) since the nodes U1,22, U2, are isomorphic. This implies that for arbitrary t/ defined above, (011, 22) = (1(1,, va), and thus vé fail to separate (v1, U2) between (01, V3). However, is obvious that the structure between (Vi, v2) and (vi, v3) are different:
and U2 connected via node while and By are not connected. This illustrates that for the link prediction of (æ, y), MPNNs can only check each node 2, separately, and fails to consider the correlation between them. This is also reflected in the definition of 2p in Eq. ex(x, y) is constructed by ((x) and (py) separately, and there does not exist logic formulas besides v that jointly consider and y.
21

---

Published as a conference paper at ICLR 2025
91
92
U1
V3
P1
P3
1/2
C1
(a)
(b)
Figure An example graph for link prediction tasks.
More powerful variants. To explain what is crucial for link prediction, consider the simple task: given a graph of family kinship, the target is predict whether one person another person y's grandparent. In Figure (b) where each node represents person and the directed edges represent the relation "parent". This typical link prediction task, which cannot be done by MPNNs: as
discussed above, MPNNs are confused by (91 e1) and (g2. ci) and thus can mistakenly considers Sa the grandparent of c also they are not relatives. The correct logic formula for this task can be written as
Grandparent y) = 3z (zPaeentt(z; 2) A Parent(z, 8)).
(6)
We believe this simple formula reflects the key logical patterns that should be considered in link prediction tasks, which can be written in the form of
(xx, v) == 3NM 2<'' 2) A (²(,,))) - ip' A
(7)
which is used by 2-FGNNs. Compared with MPNNs, this logic formula directly models the correla- tion between z, y with 5æ y). Moreover, the structures between and is perceived by checking the relation between each node = and (x, y) via 32N 2(y'(xx, 2) A (z((z))) For example, Figure 5 (b), the relation between 9l, C1 is judged by checking whether there is an intermediate node connected both of them via 32M pı (Parent(y1, P2) ) Parent (P1, G1)). We also note that there variant weaker than Eq. but also empirically performs well for link prediction:
(x v) 32 2(0' (x, 2) A E(z, -ip' 1 A d",
which is used by NBFNet. This variant also expresses the Grandparent predicate.
To summarize, believe the reason that MPNNs relatively weak for link prediction tasks that they cannot express the relation between arbitrary pair of nodes as Eq. 7 and Eq. [ do. Intuitively, MPNNs can only express concepts like "x is grandparent, is grandchild, then x is the grandparent of y²", which can be described by the following logic formula within the expressiveness of MPNNs:
Grandparent(r, y) TsGrandparent((s) A IsChild(y),
IsGrandparent((c) = Fl "yy(Paret(rr, y) A Az(Parent ())))
IsGrandchild(z)) 3y((Prret(yy,x)) 3z(Parent(z. (2)))
Therefore, the ability of expressing Eq. or Eq. is required for describing the Grandparent predicate. reality, we notice that many advanced GNN models designed for link prediction (Zhu
et al. 2021 I Liu et al. 2021 Zhang & Chen 2018 Teru al. 2019: You et al. 2021 Bergen al.
202 b) follows this intuition.
G PROOF
G.1 PROOF OF THEOREM
3
Theorem 3
Let Xr be the set all all possible x; defined above for E [K). There exists (01,..., xx) defined betow, such that &x is the equivalent logic set of XK-
X=(u)= AGG, (lxx(v) v
- p = 324 3 IvEN)(w)) (mp((u)) (u) A (u)),
22

---

Published as a conference paper at ICLR 2025
(e) COM, (x, (x,()))x(u)) xx(u))
(u) :- (2(() (x(()) -mp((u) (u(()) A (u),,
(u(u) INIT, (u) = (.(u) == atp(u) (p/(() (d(()) pl((),
where p1. 93 PR @b for i, j,k [K]. sketch. sketch.
The theorem represents a major technical contribution, so we present a proof sketch below. Our proof is divided into two parts, presented in Appendix G.T First, we show that each logic formula Pi E D can be captured by Xi. Obviously, for = I, we only have (or(u) (u) == atp(u) (u) (((()
INIT (u). By induction on i, we suppose all 9j E Φ for j < i can be captured by Xj- Then, given arbitrary Pi, we provide a method explicitly construct the corresponding (COM, Joe(f) {AGG,} and (INIT) JEE( functions that 4; is captured by Xt-
A "p" (u)), which can be directly described by Xi(
In the next step, we prove that for any graphs G, H. and u Vg. E V X cannot distinguish u, v iff all yo E t; classify u, v the same. By utilizing the fact that each yi E &; is captured by Xi. the first direction is proved. It is therefore only necessary to show (u) # xx(v) = there exists Pi E t; satisfying (u(( * (v.)). Again, we prove by induction on i. Suppose for all j < i the statement holds. We then enumerate all possible cases where (u) * x:(:): for example (u( COM; (u), Xx (u)), then there are three cases: (1) (u( & xy(v),xx(M) = xx(;;;
(2) (u) = (v), (u) + X* (v), and (3) X, (u) + Xy (v), * xx(v). For each case, we provide method to construct for E 4; satisfying (u) F (v)),, thus concluding the proof. O
Proof. Recall that the definition of equivalent logic set Ø of a family of graph functions Xx is defined as:
1. The order of each y E 4x matches that of XK E XR:
2. For all ( E Kx, there exists XK E Xx such that for arbitrary graphs G and u E V&. ęp (u) true iff (u( true;
3. A logic formula is captured by X' iff it in +:
4. Given arbitrary positive integer N and XK E Xk. there exists yı E ix satisfying: for any graphs G with no more than N nodes and u E Vg Vx ( (n) = true iff (x(u) = true
5. Given any graphs G, H and u E VGG v E V4 all XK E Xx cannot distinguish u, v iff all logic formulas и E Φx classify u, the same.
The proof is divided into four parts, each corresponding one of the statement.
Statement 1. The order of each рo 4x matches that of XK E Xg. The statement naturally holds.
Statement 2. For all Øx Kx, there exists Xk E Xx such that for arbitrary graphs G and V&. (x (u) true iff Xx (u) true. We prove this by manually constructing the aggregation and combination functions such that yo is captured by XK- To do this, we first preset the following definition.
Definition 12. Given finite set of logic formulas o we define graph function x to fully expresses G. if the output of x is vector of binary values whose dimension is [o]. Moreover, for each o E Φ there exists dimension d of the output of x such that for arbitrary graph G and node tuple u, (u) (u).
Using the definition above, we have the following lemmas.
Lemma 13. Let Φ be set of logic formulas which is fully expressed by X1- Let to be defined by (u) == =2" (PI(V)) A IveN(w)) (-pp(1)) | ('(()) ^ (u)),,
23

---

Published as a conference paper at ICLR 2025
where (p, p..p',4 sp" E Q. and we restrict N where N is arbitrary positive integer. Then, there exists an aggregation function AGG such that x(u) = AGG(((xx())) v E (N())) fully expresses 4
Lemma 14. Let 21, D2 be a set of logic formulas which is fully expressed by X1. Let & be defined by
P2(()) (p) (2(()) A (u),
where 9: s6', 40" E Φ. Then, there exists combination function COM such that x(u) COM(xi (2))) expresses 4.
are ready to show that for any рK 4x, there is XX Ax such that fp (u) XK u holds for arbitrary u. We prove this by induction.
With Lemma 13
Let (#1,-., 4x. } be sets of logic formulas defined in Theorem 3 For E [K], denote Φ.a to be the fragment of Φ; where the superscripts of quantifiers 32" are less than N. Moreover, we define N to be the maximum superscript of the quantifiers in şp. Then, at beginning for $2, we only have
(u() : atp(u)) (u) (u) A (u)).
where P1, 14. of L1. Obviously, Φ is finite, and there exists init function INIT; such that Xi (u) = (N) fully expresses 11 Next, suppose at some iteration i, there exists a function
Xi that fully expresses o.¹. Then for @ by directly utilizing the results in Lemma 13 14 it
obvious that there still exists Xi+1 that fully expresses &N Finally, at iteration K, let X be
the function that fully expresses A. From Definition 12 it evident that the output of Xxx has dimension for each formula
N. By only preserving the dimension corresponding to {o (denoted as dimension d), there exists XK (u) Xx (u][d] that satisfies: for arbitrary graphs G and VG. Px (u) = true iff XK (u) = true.
Statement logic formula is captured by X iff is in T. prove the statement, we need to show that
Lemma 15. Given arbitrary X, let & be constructed as Theorem captured by X E X is in t
3 Then, all logic formulas
The lemma is proved via a reduction from GACNNs to MPNNs in Appendix G.14
Statement 4. Given arbitrary positive integer N and X E XK, there exists fp E d satisfying: for any graphs G with no more than nodes and E VA (x(()) true iff Xu(u)= = true. We first introduce the following lemma.
Lemma 16. Given series of functions (Xi,..., XK} where each function Xs maps a node tuple to a discrete color and is defined by either (i(u) AGG, (lxx(v) (N())) xi(u) COM (u), Xx (u)) or Xi (u) = INIT; (u). Let X, be the set of all possible Xi defined in the above manner for [K]. Let o; be the set specified by Theorem of X, Then, for arbitrary
i [K] and each possible color col of X there exists a logic formula go0 E &. satisfying:
0000 true =
(i( col
for arbitrary graph G with more than N nodes and Vg.
the sets of logic formulas defined in Theorem Lemma 16 indicates that for arbitrary N, there exists a logic formula y E T for each X and col a possible color of X such that (u) true = (u) col. evident that for Xx. the statement: x (u) = true iff (u) = true is just a special case where x only has binary colors. Therefore, the proof completes.
Therefore, given {x....., X and
Statement 5. Given any graphs G, Hl and u E VA E Vk all XK E Xx cannot distinguish u. v iff all logic formulas Φk E 4x classify u, v the same. This result a direct corollary of the statements 2, 3. Let N max([Val. (a[)) It is obvious that if there is XK Xx that Xx (u) # X (v), there also exists a Φx E &x where & is specified in statement that satisfies Pk # ppx (V), and vice versa.
24

---

Published as a conference paper at ICLR 2025
G.2 PROOF OF THEOREM g
Theorem 8 Given a class of GACNN models and suppose & be the equivalent logic set. Let F be the homomorphism expressivity constructed by & as discussed above. For all pairs of graphs G, H. the following statements are equivalent:
1. Hom(F, G) = Hom H for all F F.
2. All GACNNs do not distinguish and H.
Proof sketch. Theorem represents another major technical contribution of the paper, so we present proof sketch below. Given the homomorphism expressivity F and for any graph G, the intuition that we can use logic formulas to count the number of homomorphisms from each F E to G. Consider the graph in Figure 2 (a) for example: the number of homomorphisms from it to G is N iff 9 : J=N v(E(u,; Vy) A Elvy, Uw) A Ev V2) A E(v,, vw)) evaluates true G, where (U'z Uy: Uz, tw. V.). The next step of our proof is involved and shows that such y can be expressed by logic formulas in the equivalent logic set and vice versa, which is presented in Appendix G.2 thus concluding the proof.
Proof. From Proposition it is evident that statement is equivalent to: All o & do not distin- guish G and H. We therefore instead prove:
All yp E & do not distinguish G and = Hom G) = Hom H) for all FEF.
We first prove the direction left to right. Given each yp E that does not contain negation - or 32.V
where N 2 2, recall that the corresponding F is constructed by:
1. Start from an empty graph F;
2. Construct the nodes of F: Add a node for each variable emerged in yp (we avoid the reuse of variables);
3. Construct the structure of F: Add an edge (Uz, vy) for each edge term F(x,, y) in s. Add Ft F.
Before we start, we first introduce some useful quantifiers 3 N 3.. which express "there exists exactly N" and "there exists no more than N respectively. Note that the two quantifiers can be directly deduced by NNt; REE == -12N+1 and 7=N = 3NH A BSN.
Note that all &p satisfying the constraint (i.e. without negation or 32M for N > 1) can be flattened into the form of:
6 = 3x Fxg. Exx E(x,, Rj,) A.. A ([Diar:iju)
where ip. Jp E [K] for all p E [M] We now prove that there is a logic formula ab E + that captures Hom G) 1, i.e. given arbitrary graph G. vi is true iff Hom G) 1. Suppose F is constructed by yo as:
s := 3x Exp...Exxx E(T,, 25d A A..AA "
Then by letting
El RJ,) A... E(Isss xg... x-...=1lx = 3 3
We now show that for arbitrary graph G, v/ true iff Hom(F, G) 1. By the construc- tion of F each variable X1. ... XK is corresponded to a distinct node tuple in F and each term Fl Fi ).... F( Iznm) ) corresponded to distinct edge in F. If & true on G, then there exists grounding X1 - uj....,
+ such that all T ),,,, E( Zjnn are true. Then the mapping म F + G that π (V = u for / E [K] where Uny is the node in F correspond- ing the variable in v.. obviously is homomorphism from F to G, therefore Hom G) 2 1. Further more, suppose Hom (o G) > 1, then there exists another T' * π that is also a homomor- phism from F to G. which indicates that the grounding for E(I,, Fy, )...., E(Iisr Tfs to be true not unique. In this case, v is not true because there exists not only one X.. X such that El ((rr)))3))): ..., E( Fy is true, violating the quantifiers 7=1 in dh.
25

---

Published as a conference paper at ICLR 2025
We next prove that there is also logic formula v/ 4 that captures Hom(F. N for arbitrary N: that is, for any graphs G. H. Hom(F, G) * Hom(F. F, H) = there exists & such that e evaluates to different values on G and H. We prove by contradiction and assume all 1 & evaluates to the same
value on G and H. We denote Vnim.....x = E Th x " " (Ametn) E Fi
By assumption t'nnng..mg evaluates to the same value on G, H. for any ni, n22, .... nK. We now construct vb such that v evaluates true on G.
Let be constructed by varphi == 3x Txx..x...3xxx ; Tn) A.. El Time such that Hom [F, G) N * Hom H.. Let X be the tuple of all variables in şo: X (X1X99 K2,, ..)))) For all homomorphisms from to G, let V be the set of images X from to G. We first pick all Wn. that evaluates to true G. First, have the following result:
Lemma 17. If my > for some [K], then Day u..... false on G.
Therefore, there are only finite Vming....x that evaluates to true G. and ny S N for all & [K]. For some Pn.n....xx true on G, we refer to its grounding as a mapping from the variables X in di to the corresponding tuple of nodes V in G, and V is the grounding result. We then have the following result:
Lemma 18. For Vn.nz...u and V Vmnmm.....m ng o my for some k [K]. then then grounding results of Vn,ng....xx and Ummmp...my are different, Lee. there exists no that is both a grounding result of Vning...nx and Vmmmp....
Let = [Vnnnn.... ng I for [K], Vnina.... true on G} {&lafng... | [4]
where L [S]. Then we have the following result:
=
Unf pnfnnh..nn E & evaluates true on G.
(E(L)
Moreover, according to Lemma 18 is evident that the total number of different grounding results can be evaluated as
Number of grounding results of o4 mb....k
[E[L]
Σ
II
T
[E[Z]
KE[K]
Since a grounding is also exactly homomorphism from to G, we have
Σ
Number of grounding results of Waf
[E
Hom (F,G) N.
By assumption, é also evaluates to true on H, which indicates that Uninh...nn evaluates to true for I e [L] on H. As result,
Hom F, H)
Number of grounding results of mn.n.....k
[E(2)
-N.
This yields a contradiction where we assume Hom(F, H) < Hom (F.G) = N. Thus the proof completes.
We next prove the other direction, iee. for any graphs G, H. there exists & such that & evaluates to different values and H Hom F, G) o Hom H). Without loss of generality assume v evaluates to true on G and false on H. We first introduce the following lemma:
Lemma 19. If there is v ues on G and H, then there exists & E + in the form of Uninz..n = (Ape(p) Elsi, 2s,)) A LE(,,, #5,)) that also evaluates to different values G and H.
T such that tb evaluates
different val-
"
26

---

Published as a conference paper at ICLR 2025
Without loss of generality, may assume that there exists in the form described by Lemma 19 that evaluates to true on G and false on H. We now prove that there must exists a F E such that Hom FF G) * Hom
Given
Φ
3x EX2
A PE[P]
E( Tzp))
A
-E(ii 23nn)
qE[Q]
let grd( (, G) be the number of groundings from the variables in Ø to G. Obviously grd is exten-
sion to hom which allows negative edges (I 2n for q E [Q]. We have the following result:
Lemma 20. If Hom (F.G) Hom (F, for all F F, then every & E & of the above form satisfies:
grd(ø, G) (r,
We define
Pny Tex 3x/ .x..
3x x2 .x.2 3x? ...x2''0
A PE(Pl.
hllandpp ielandip E
E Lilandin
Ji
gE[Q)
Note that On RK sume Hom(F, F, G) = Hom FF, H) for arbitrary F E F. By Lemma 20 it is obvious that grd (on G) gonggnnn..... H) for all n1, ... nk. First consider the case where V11.... true on G. Obviously we have grd(øn...1.
for arbitrary n1, n2 .... nK. We now prove by contradiction. As-
(rd(,n1..1, H), which in- dicates that there exists exactly one grounding from @11...1 to И and thus V1I...1 true on H. which yields contradiction. We now assume VNN, No..NNN evaluates to true G. We prove that the evaluation of d/N, No....N can be determined by the number of groundings from (ompe....k n& E [Nk] for ls E [K] to G, i.e.
By proof by induction, we already know that $11.... evaluates true on G exactly when grd (o G) = and thus v5 is captured by (grd(ón....s G)). Now consider we are to prove NN NN..N..NN is captured by (ed m) [Naa) for RE[K]- Let us consider the groundings from ON, No...N G. Obviously we can divide the groundings into two parts:
1. The non-injective groundings, i.e. groundings that maps different variables in NN.No...NK to the same node in G.
2. The injective groundings, i.e, groundings that maps different variables in Φ No.... to different nodes G.
Obviously the number of non-injective groundings can be computed by (rd G) where for all & [K] ny < & [K] and there exists k [K] n& Ng. Thus, the number of injective homomorphisms can evaluated. If the following constraints hold:
The number of injective groundings from On @npm..... to G is larger than 0,
The numbers of injective groundings from dn, -ng-Ing..n mx Dn ma +h..ng Pn.. to G
are O,
then obviously Vn....xx evaluates to true. Therefore this yields contradiction and the proof com- pletes.
27

---

Published as a conference paper at ICLR 2025
G.3 PROOF OF COROLLARY
Corollary
The equivalent logic set of Ilaaee GACNNs defined above is given by (()).
Proof. This is direct result derived from Theorem 3 when we explicitly write down the computa-
tion procedure of I-layer GACNNs.
G.4 PROOF OF PROPOSITION
5
Proposition 5 The equivalent logic set of all GACNNs defined above is given by 1 Ui (()).
Moreover, let Φ; U o
(1) for [K] then t and ( exist and defined by similar
procedure Theorem For the brevity of notation denote (1) as XK+1 as Do in the following description.
(1) (t+1) as Xo and +o
(1)
(1) (u) AGG (f1x50 12 (x) (v) Xi
(u) == ANt (px(v) (vEAi(w)) (-p((u) (1( A ( atp(u))
(3) (u) COM (x) (u). x4 (u)
(u == (u(4) px (u) ( (u( A (u) atp(u),
where Pai 2. of E p. P, E 2 E for i (0) []]
Obviously, consider all numbers of layers simultancously, the equivalent logic set is given by & = U (()), Since for layer I the corresponding equivalent logic set o is given by
Proof.
X (3) (u) AGG (f(x5)) (1) (x) (x) NE(U))))
( (u) = ANt (100 (v) A IveNi(u)) [pp))(()) (()) A (u),
(3) (u) = COM
x 10 (u))
- p. = (u)
(u) |/ ( (u) - ((()) ((( A (u),
11) !!" E ( p) 9 9b x where pi :i o
!
(1) (1)
(1) for U[K], and
6 (u) == atp(u).
obvious that the construction of t; in Proposition
5 is a union of all ( for 1 E [0, oo): at
beginning ; : (tp(u) thus this moment 4; ( Suppose some iteration b; (! Then in next iteration we add
(u) 3 N
(v) A IvEN((u) (u) (u)(u) (u) (u) A (u) atp(u)
to D,, and we still have D.- = Φ (1-1) Therefore &b U (()) is given by Proposition
G.5 PROOF OF PROPOSITION 6
Proposition 6 The equivalent logic set Ve of the graph representation Xa defined above is given by vb = 3 (v(())
bb w/ AW",
where v, H. v0" E V.
Proof. This direct result derived from Theorem 3 Since
XG AGG (f(x(u) u E v*]])
where V is the set of nodes in G and A: is the order of u, V is specified by Theorem as above. n
28

---

Published as a conference paper at ICLR 2025
G.6
PROOF OF PROPOSITION 7
Proposition
7
The equivalent logic sets of GNN models can be separately defined as:
MPNN: (p(x) := 32Nx (v) A E)x, where E is the edge predicate.
Subgraph GNN (weak):
((r) = 32% y (vb 9)). and ((x
328 (z, 2) A E(z,y)).
Subgraph GNN (strong):
((x))
= 3Nt (40 (v) A (v x)) (2.
(V 2) A y)z (:p(y)
NBENet: ((r,, v) 9NF 1222(19' (4' (x. 2) A F(z,
Local 2-GNN: p(z,)) = 2 (z,2) E(2, v))) | (E' 2) A (z..i)))
2-FGNN: ((x, v) == 32 2
(z,1))
SEAL (MPNN): ((.,y)
328 2 (b(2, 2))) 2,,)
32N (V(2, v) A E(w,2)) 2)))
2-GNN: y) == 32 (z, 2)) 12 (vd (z,
Proof sketch. The proposition directly utilize the results in Proposition to derive the equivalent logic sets of popular GNNs. We present a proof sketch for Local 2-GNNs and illustrate the pipeline for determining the expressivity of certain GNN models. First, we explicitly write down the GNN layers Eq. 3 Then, we transform the GNN layers into GACNN layers by decomposing each layer into sequence of AGG and COM functions, as in Eq. 3 By utilizing Proposition 3 we can directly obtain the equivalent logic set of Local 2-GNNs as below. (Again, we omit the terms in the form of yp -up sp' A Ay" atp for notation brevity.)
((x, u) = (2,,,)) (1r,
(1 v) == (2( (Ps(,, v),
(2(2,, v) = 3=> x(p(2,)) A F(Ix,)),, (3(x, v) = 32N *( 2) A F(2,y));
where so, E + is the equivalent logic set of Local 2-GNNs, and 9o E $ f2 E $2 43 E Q are
auxiliary logic sets. It is therefore only one step before the result in Proposition 7 by substituting the definition of 42, 4Pa into 1o and further substituting the definition of ( into y, we can write down the definition of &p into one line:
(a,, y) == vx) 32 (10(xx, 2) A E(2, v))) 132 2 (E(x, A (2,,
Removing the redundant term p(z, y) = p'(x, y) directly yields the result in Proposition 7
Proof. By utilizing the results from Proposition Sappositionnnand and further simplify the resulted equivalent logic sets, can casily obtain these results. Note that for brevity omit the terms xp == =-p' 1p A y""
MPNN.
(x)) = COM (x (2), ([xxWlv
N(
+x(x)= == =z((z) 132 (1((() A E(x,y))
=x(x)= == =NN x (5 E(z, v)).
Subgraph GNN (weak). The layers are given by
(x) = AGG (ffx* a* (a,v) y =
x (1+ (x, v) COM (x (z, (x0(x,)))=EN())
Therefore the equivalent logic sets are given by x(x) 2 (z((z))))
((x v) d' ()(x))) 32% (6'(z,)
which can be directly simplified as
<(x) = 32t (1) y)) (xx,)) = NNZ² (1x A E(z, v)),
29

---

Published as a conference paper at ICLR 2025
Subgraph GNN (strong). The layers are given by
x (ut (x, v) = COM (2 (x (z. (1l ((x="a,)))= ()) AGG (H+x")))==)x))))
(x) = AGG (x (x 2)) I vE
x
Therefore the equivalent logic sets are given by
(xx, v) = (z v) |2 (v((, A E(z,g)) (p(() 322% (1((2) A E(z, ()) ((z)= == 32 y (e(y.))) x)).
Substituting (zz y) == (p(2) A (z v)) to the second line leads to <(x) = 32 2 (x'(z) A E(z,z)).
Therefore, the above & can also be described by
((x) == 32 y (1)( A #), (5. == 32 (x(o,)) ((z,)) /p(().
NBFNet.
x (++) (x, v) = COM (x (z, v). AGG ((xx"(==))=ENN)]])
,1(x, v) = =1,(xr,)) v) 3 2 (44(2z 2) A E(z,g))
x)(x,v)= = =N (z, 2) ^ E(z,y))
Local 2-GNN.
x COM (x (I, v), AGG (1f (2,x (x AGG ((
*p(x,)) v) = ('(,,)) | 2 (z 2) E(z,8))) | (E',,) ((((,)))
+p(z,y) = 32N = (10 (x, x) ((z, 1 (E'(z, 2) (z..))))
2-FGNN.
x(+1 v) = COM (z, AGG (ffcoM(x 2), x),x) (z.))) | (ze)))))
>)(0,)) == ('xx, v) 332" (vb(z, y, 2)) blz 2,2) = p(z, 8) (2),2)
*,(z, y) = 3 (1/ (I, 2) 40 (
The last line holds because 1zz y) E 1 where 1 1z, v) true for all (z,y).
SEAL (MPNN). The layers are given by
(1, = COM (x)( 2). AGG (x, E N(t))))
x x AGG (11x4)11,
Therefore the equivalent logic sets are given by
v) = = (,(2),
()x,2,y) = 32. w (v(x, w. w.v) A E(w,
2-GNN
x (++1((z)) y) = COM (x "x, y) (ff ((xx(),)) AGG ((1x)()))22))))
*p(x, v) = (2(,,)) | (x)) |320 (x
(p(,,) = ==2²2 (10' (x. =))) 132N 2 (v²(2,,
30

---

Published as a conference paper at ICLR 2025
G.7 PROOF OF PROPOSITION
Proposition 9 Suppose the equivalent logic set of a class of GNN models is D. Then, the expressive power of the GNN models is bounded by k-WI, iff the number of variables of the logic formulas in & is at most k.
Proof. Given any graphs G, Cai et al. (1992) states that the following statements are equivalent:
k- WL distinguishes G, H:;
There is a FOC₁ formula that distinguishes G, H.
Recall that FOC& is subset of first-order formula that allows quantifiers M2 but restricts the formulas to only possess Obviously, in Proposition is a subset of FOCR, thus the expressive power of GNNs is bounded by k-WL.
G.8 PROOF OF COROLLARY 10
The expressivity of GNN models satisfies: MPNNs = I-WI. <, Subgraph GNNs (weak) NBFNet Suugrapph GNNs (strong) < -Local 2-FGNN <, 2-FGNN 3-WI, I-WL
Corollary 10
SEAL < 4-WL.
Proof. By utilizing Proposition Proposition 6 Proposition and the known results (Xu et al.
2018 Qian et al. 2022 Huang et al. 2024 Cai et al. 1992). obviously Corollary I0 holds.
G.9
PROOF OF LEMMA 13
Lemma
Let t be a set of logic formulas which is fully expressed by X1- Let & be defined by
(u) == =2t ( A IvEN(()) 1 (u) (u) A (u)),
where sp, 4p,, 40 E Φ, and we restrict n. < N where N an arhitrary positive integer. Then, there exists aggregation function AGG such that x(u) AGG(((xlv)) veN(u))) fully expresses 4.
Proof. We prove by manually constructing the AGG function. For each yp E t let {spt.... ..... p4) where sp for I [L] be the series of sub-formulas of such that if Gp a sub-formula of yo then p g. Also, we denote x[yo] to be the dimension of x that corresponds to the formula &p E ④. We prove by induction on the sub-formula series of yo. 1) At beginning for yp" only have yp (u) == 32M (fi(v) IveA(w)). In this case let
AGG" (Hxi(v) x())(])== AGG
(There no less than N E Nuu) such that (v((((p)) true).
2) Suppose at iteration I, all (u) for AGG" (fxx(vv v (u)))). We now need to show that of can also be captured by x. We show
can captured by some x(u)
this by designing specific AGG' function there is also x x()) [oo]] AGG (ffxi(v) e (u)))) that captures of (u). It is also straightforward to prove: If (u) == (p) for some E [1 - 1]. then
= AGG (fxx(v) v v = (Hx(M)) vv false).
If (f) (P)) A (u) then
AGG (fxx(v) vv = 1(AGG (fxxivv) v ((()))) AGGs (1xx e = true).
Otherwise 6 (u) F2N (6 v N(u)) which is already proved in 1).
n
31

---

Published as a conference paper at ICLR 2025
G.10
PROOF OF LEMMA 14
Lemma
14
Let 11, D2 be set of logic formulas which is fully expressed by X1, X2. Let o be
defined by
= = (i (2(()) | (p)(()) (2(() A (u).
where P, ,', E Q. Then, there exists combination function COM such that x(u) = (O) fully expresses 4.
Proof. Let (xpt,..,,x*) be the series of sub-formulas of such that if sp is sub-formula of Sa then p < q. We prove by induction on the sub-formula series of $
1) At beginning for ep we only have sp (u) == @ (u) or ( == p2(n). In this case we let
x(u) == Xi (u) or x(u) = (2)).. Since 1 22 are the equivalent sets of X1 X2 respectively, sp is captured by X.
2) Suppose at iteration all (²(()) for p < can be captured by some x"(u) = (x) (2),xx We show that by designing specific COM' function there is also x"( = (x),), that captures (u(). It is straightforward to prove: If ('(u)= = (u). then COM' (xi( (') (u() A (u) then
1(COMP (xi( = false].
COM' (x), xe())) (COM (u), xe(u)) COM (xi (u), x2)) true).
Otherwise we have of (u) = (u) or o' = (2(u). In this case op can also be captured by x as proven in 1).
G.11 PROOF OF LEMMA I6
Lemma 16 Given a series of functions (X1, Xk} where each function X² maps a node tuple a discrete color and is defined by either (i( AGG; (ffx(vv) v ((()))) (u(u) COM (u), X0 (u))) or x;(u) = INIT; (u). Let X, be the set of all possible Xi defined in the above manner for [K]. Let Φ; be the set specified by Theorem 3 of Xx Then, for arbitrary
i [K] and each possible color col of X there exists logic formula oo0l T satisfying:
p (u) true for arbitrary graph G with no more than N nodes and u E V.g
(i) col
Proof. For arbitrary Xi and ,, if the statement in Lemma 16 holds, i.e. for each possible color col of Xi. there exists a logic formula o:t E & satisfying: o (u) true >
xi(u) col
for arbitrary graph G with N-captured by + We present the following lemmas.
than N nodes and Vg. say Φ; N-captures Xi, and Xi is
Lemma 21. Let Xa be a function that maps node tuple discrete color, which is N-captured by P1. Let x(u) = AGG AGG(lxxiYe v E N (u)))) where AGG is some aggregation function. Then by defining & as below:
<pu) == 32"v (fI(v) A IvEN(w;) (u) o0 (u) A ("(
where p, 2.44 4p E Φ. & N- N-captures X-
Lemma 22, Let X1. be functions that map a node tuple to discrete color, which are N- N-captured by 11, D2 respectively. Let x(u) =
where COM some combination
function. Then by defining & as below:
<u(u) == P1 (u) (2(()) (1) (5( A (u).
where p.pp'pp" " E 4. & N -acapuress x-
We now ready prove Lemma 16 At beginning for xi (u) INTT(u), we only have
(u) = atp(u) ( (u) A (f)
where (P,, v/, soff Φ1. It is evident that X1 is N-captured by Φ; and 4, is finite. Suppose at iteration I, Xp is N-captured by Φ for all < I. By directly utilizing Lemma 21 21] is obvious that b N-captures sot. Therefore the proof completes.
32

---

Published as a conference paper at ICLR 2025
G.12 PROOF OF LEMMA 21
Lemma 21 Let XI be a finction that maps a node tuple to discrete color, which is N-captured by 11. Let x(u) = (GGG(( e (u))) where AGG is some aggregation function. Then
by defining as below:
(u) == 32t ( A IveV(w)) 1 (u) o A (u),
where ii ,'"" E Φ. & N-captures X-
Proof. For each possible color col of X. below we construct a logic formula eool satisfying than N nodes and u V
ooo (u) true -
x(u) col for all graph G with and show that co is in 4b
For notation brevity we use col, to refer to colors of Xi and col to refer to colors of X. We first create intermediate function x' which is defined by
x'u)) (aahh(lxx v E (()))))
(10)
where hash is injective hashing function that maps different inputs different colors. Therefore, X can be written in the form of: (u) - (x'((x) with some function f. We first show that x' N- captured by by constructing a yool' for each color col' of x', then show that X is also N-captured by 4.
First, recall that two multisets are different Hxi (w) w E (())) # Hxi(w) [ WEW((v) if there exists color col, of Xi such that
[(w] W E Mu)), Xa (w) = col, } * Kw EVV(),,)
col
Therefore, x' maps two tuples u, to different colors if there exists color col, of X1 that the above equation holds. Note that since we only consider graphs with no more than nodes, X1 has finite colors. It is evident that
rewrite Eq. into:
x (u) hash (K ((E)) col. }
col.
||
SvlveN(u)) xi(v) col
where col....., col, enumerates through all colors of XI, and hash' a perfect hashing function. We now show that the above definition xf x' can be fully reproduced using logic formulas.
Denote by l the order of X1- If we only consider graphs with no more than N nodes, then it obvious that hash' is function with domain [N*] x [N*]
x [N*] (repeated for times). which is finite. For each color col' of x'. we now construct the logic formula yoll" Suppose the color col' is corresponded to the case below:
N(u) = col. |
VVlve = col,
VVllveN(u), = colf
Then we define
cor
(u) = 3 0000)) (v) A IvEN(U))
(a= (1 (v) A LveN(u))
^
A_.
^ (3 coff (v) A IvEN(w)))
Therefore, cool' (u) true iff (u) col'. Also, cor (u) Φ. Next, we prove that for each color col of (()) ((x(1)), there also exists col that col(n) true iff x(u) = col. From the
33

---

Published as a conference paper at ICLR 2025
above discussion, f is function that maps the colors col' of x (which is finite if we only consider graphs with no more than N nodes) to the colors col of x (which is again finite). Obviously, each color col is corresponded to subset C of the colors of x' where x(u) col iff x'u) C. We define
col
V cor (u).
col' EC
is now evident that for all graphs with no more than N nodes, co (u) true - x(u) col.
Also scol (u) is in 4. Thus the proof completes.
G.13 PROOF OF LEMMA 22
Lemmal 22 X1. be functions that map node tuple to a discrete color, which are N N-captured by 11, 22 respectively. Let x(u) (O)( (2 where COM some combination function. Then by defining & as below:
<(u) == ş (u) (2)( (1) (2) A (u).
where e, ". E &. & N-capiures X-
Proof. The proof is similar to the proof of Lemma 21 For each possible color col of X. below we construct logic formula eol satisfying eo (u) true > x(u) col for all graph G with no more than N nodes and V and show that o is in db
For notation brevity we use col,, col2 to refer to colors of X1, X2 respectively and use col to refer to colors of X. We first create intermediate function x' which is defined by X'uu) = hash X2()),
(11)
where hash is perfect hashing function. Since we only consider graphs with no more than N nodes, the colors of X1 and X2 are finite. We denote by CI, C2 the set of colors of XI, respectively. The domain of hash is thus C x Cz. Suppose color col' of x' defined by col' hash(col, col2)
where X1, are some colors of X1, X2,X2 respectively. Then, by letting
ooll (u) col: (u) A (u),
((u col' for graphs with no more than N nodes. Also, obviously col' (u) is in Φ. We next show that for x which can be expressed by x(u) = f'x (u)) for some f. there still exists oool for each color col of x such that x(u) col = (u). This
have cal (u) true =
proof is exactly the same as in the proof of Lemma 21 Therefore, the proof completes.
L
G.14 PROOF OF LEMMA [5]
Given arbitrary X, let 4 be constructed as in Theorem captured by X E X is in +.
Lemma 15
Then, all logic formulas
Proof. We first define the concept finite aggregation functions.
Definition 23. Recall that aggregation function is mapping from multiset of colors to color:
AGG(ffx(u) u E (Vv) = col.
where col stands for the output color. From Appendix G.12 is obvious that if the number of colors of x is finite, we can write AGG equivalently in the form
AGG(f(x(u) u N(v)))) = f N(u), = col!
V(uv col?
([ v ( = col
where col', col enumerate through all possible colors of It obvious that f: N N.NNNN... x XN - where C denotes the set of output colors. We say such an aggregation function AGG is finite, the number of possible colors of x is finite, and there exists a positive integer N such that for all I [c).
f(11, mr m....., [(m,..., n 1,..., ne) if ny N.
34

---

Published as a conference paper at ICLR 2025
In this case say the aggregation function is bounded by N The above definition implies:
If the input colors of AGG are finite, then the output colors are also finite;
.N,,,... No) is constant for sufficiently large N1,-... Ne-
Intuitively, finite aggregation functions does not distinguish the situations where there more than N items each color. Extending from the definition of finite aggregation functions, we define the concept of finite X E X.
Definition 24. Given arbitrary X' as defined in Theorem We say a X X' is finite, if all aggrega- tion functions used for constructing x are finite.
Note that, if X is finite, the possible colors of x are also finite (which is shown in Appendix G.12 We now ready prove the lemma.
We prove Lemma 15 by noticing the following fact.
Lemma 25. If a formula to is expressed by some E X, it is expressed by a ffiite x E X.
Lemma 25 is intuitive, as given a specific formula v/, the maximum counting number N of the quantifiers 3 is determined, and thus for each term in the form of (z)((v) also does not distinguish the situations where there are more than Ny that satisfies (vv)). Note that in Appendix G.12 have provided a method for constructing logic formula &P E & that expresses such finite E X. Hence, if a first-order logic formula vú is expressed by some X E X, it is expressed by finite X E X, which further expressed by a logic formula yp E Φ. This implies that E 4, thus concluding the proof.
G.15
PROOF OF LEMMA 25
Lemma 25
Ifa FOC formula sp is expressed by some x E X, it is expressed by finite X.
Proof. The proof is direct generalization Otto 2019) follows.
Lemma 26. (Lemma 2.5 in Otto (2019)). For ip in first-order logic that is invariant under eog over the class of all (or just all finite) pointed Kripke structures, there are e, l N s.I. s(x) is invariant under- # over the class of all (or just all finite) pointed Kripke structures.
In the above lemma, for two nodes x, y in graphs, x ~ y indicates that two nodes x, y are not distinguished by MPNNS (1-WL). x c.l indicates that two nodes æ, y are not distinguished by MPNNs (1-WL) with layers and aggregation functions bounded by c. We generalize the above lemma to setting as follows.
Suppose a logic formula &b is captured by some E X, as stated Lemma 25 vention, suppose X is defined by series of functions fxi...., {x) where we denote XK X and each function Xi maps a node tuple to a discrete color and is defined by either Xa(u) = AGG, (v)
As con-
E (()))) xu( COM, (x,(u), (u)) (u) INIT, (u). We de- note X1..... Xx to be the set of all Xi..... XK- For each generalized neighbor N₁. we denote its corresponding predicate (v) as EN, where Ev, (v, u) is true iff v NN(u). Given graph G, we define the unrolling of G by X at u, denoted as F Unrx u), to be structure for first-order logic described as follows.
Denote (X,) to be the order of X E X, has a tuple of nodes u for u.
Repeat for K times:
For each node tuple existed in F and each generalized neighbor Ns in F, suppose v E NG( in the original graph, then add a tuple of nodes u in F and let Ex, (v. u) = true if u does not exists in F.
35

---

Published as a conference paper at ICLR 2025
The above procedure generalize the rooted unfolding tree T of graphs G at in that:
In the rooted unfolding tree ''' two nodes are connected by edges E if the corresponding a tree with root 2.
nodes in G are neighborhood.
In the unrolling F two node tuples are connected by generalized edges EN; if the corre- sponding node tuples in G are generalized neighborhood N₁. F is a tree if we only consider the generalized edges Ex; and consider each node tuple as a ensemble, with root u.
Next, our proof step is similar to Otto 2019). For two node tuples u, v, we denote u ~xx and v are not separated by any X E X.. First, we would like to mention that for any graphs G, H and u E V v E V4, u ~x v = " ~'x v where u, v are tuples in Unrx u), Unrx (G, v) corresponding to respectively. It is straightforward: since the evaluation steps of any X X on u E V& are exactly the same as X applied on u in Xnrx u).
Next, show that any first-order logic formula di with quantifier rank that is invariant under ~x, is generalized [-local for some / = f() in restriction to all unrolling graphs that are generalized tree (as mentioned ahove) to depth where define function is generalized I-local if it only considers node tuples up to distance 7 by generalized edges. This corresponds to Lemma 2.3 in Otto (2019). The prove is straightforward: since X E X itself is 1-local, &b must also be I-local. Also, each unrolling is naturally K -local, since it is tree with depth K.
N such that for any unrolling of Next, we need the following fact that for any q E N, there graphs P1 = UG, u), F2 = Xnr v):
u ~~ v p(u)= = Φ for all first-order logic formula 6 with variables no more than q-
The above fact a direct generalization of Lemma 2.4 in Otto (2019). Since & consists no more than q variables, it can only most consider q distinct nodes and thus capture them. Given to captured by X E X, we now show that a is captured by a finite E X bounded by some N. This is equivalent that are not separated by any finite E X bounded by N, (u) (vv). Without loss of generality assume (u)) true. Let u, be the tuples Un, u), Xnrx v) corresponding to u, respectively. Then we have:
q is enough for X' to
showing that, for any graphs G, H and Va v E V
(by x V A u ~ v)) (u) = true + (bu) true
(bv)) true
(by Hocallityy implied in Unrx(G, u) and Unrx(H, v))
(vv) true
(by u x v 4 ~xxx v).
G.16 PROOF OF LEMMA
Lemma If n2 > N for some k E [K], then Vnanz... false on
Proof. Obviously if my > N for some E [K], we have
Hom Hom(F,C) G)
II n
KE[K]
>N,
which contradicts with the fact that Hom (F,G) N.
G.17 PROOF OF LEMMA 18
For Uning and Um.m..... my: if nu # m& m some k [K], then then grounding results of Un.nz...axx and Umnyma... are different, Lee. there exists no that is both a grounding result of //nngg... and Umngmg....g
Lemma 18
36

---

Published as a conference paper at ICLR 2025
Proof. Since n # my for some k [K], assume that ny * my while ny my for & + 1, 1. We prove by contradiction. Suppose V = (V1...,, VK) is both a grounding result of Pninz...ax and 1 mm.. This indicates that for Vninz...xxx by fixing its variables to
V1,X2 = 22 X1-1 V1-1, there exists exactly ny different groundings of X satisfying
I X X142 M J XK
ElIbm Izmm
mE[M)
in G. However, for Wmemy....m by fixing its variables to = V1, = V2. X1-1 == Vi-1 there exists exactly my different groundings of x₁ satisfying
m X1+1 =1 XI+2
= XK
E( Iim)
mE[M]
in G. Since my ny for A E || K] and my # my, this yields contradiction.
G.18 PROOF OF LEMMA 19
Lemma If there is vi E 4 such that vi evaluates to different values on G and H, then there exists vp in the form of p= m x x XK (Nwe(p) Exxi,, Tz2)) Agelo) -E(I, Kz.)) that also evaluates different values on G and H.
Proof. We prove this by constructing of the form
= 7 X1-..
A (E(MM)
F1 Fmm
that explicitly captures the colors of X- Concretely, similar as Theorem tions fx XL} where xI is defined by
suppose a series func-
(x) hash (xp(x), Xx(x)),
xx(x) = hash (ylxp(y) y E (x())))
or
xi(x) = atp(xx.
The difference between Theorem 3 and here is that we replace AGG and COM functions with injective hash function. Obviously the separation power of (XI)EeL)) here is no less than that in Theorem 3 The above procedure can be regarded as general color refinement algorithm where the value Xi is called the color of x computed by Xt- We define the signature logic set V of chi to be the set that satisfiesfor each color C, there exists the E Φ such that
the (x) true
x(x) C.
We now provide method construct the signature logic V,, We define:
1.
(x( = hash (x), + (x)(x) (x) A (x)
2.
(x) hash (ffxp()) y E (x())))
(x) = --Ny (1yeN(x)) A N (vp(y) A lyleN(o)
A g=Nyy (vp(v) A 1yDEN(0)) A...
where N₂ > N₁ >
37

---

Published as a conference paper at ICLR 2025
3.
xx(x) atp(x)
+))(x) == latp(x)=CC
where for each possible structure of a k-node graph (k is the order of x; we consider node orders thus there are 2 structures in total; suppose the nodes of the k-node graph are V1 Vi,..., Ug), there is a corresponding 1i that evaluates to true iff there an isomorphism from the subgraph induced by to the structure of the corresponding k-node graph that maps o2 to 24 for E [k] where x = (I1,-.,,AA) Tk).
We next prove that the above V indeed is the signature logic set of XI- We denote vi (x) as the logic formula that evaluates to true iff xx(x) = C' where is the color x evaluated by Xi- For situation 3 the statement obviously holds. For situation I, suppose NP pr V, the signature logic sets of Xp, Xy respectively. For each color C₁ of Xı where C₁ hash Cp,, C2), we have
v (x) = 23 x (x) A o (x()
which is true iff (x) Ct. Thus the statement still holds.
For situation 2, suppose v is the signature logic set of Xp. Each color C₁ of xi defined by
C hash (1(C) p: cp:-..)) hash ({(C), Ni), (Cp: N2);
where Cp., C2 Cp.... are colors produced by Xps and N1,N2,... 1 are the numbers of the colors Cp,, C2. emerged in the multiset, We then have
(vr)()))) A 1IEE ( N3 Naya vp c
(x(())) lySEN(E)) ( )
3* w/ (x) = 3 3 3 Mi (
Specially, if the multiset empty, we have
C: == = y1
Then, o (x) is true iff xx)x) C. 5 is also in V, Therefore, we have constructed the signature logic set of xI. Obviously, all s/r E V,, can be written the form of
(x) = - X1 N xK
A F(c,, R.r A (-F(ss, 2b,))) PE(P)
rE(Q)
For two graphs G, H. if there exists & that distinguishes them, then obviously the corresponding also distinguishes them. Without loss of generality, suppose the color of x applied on G C. Let d be the logic formula that evaluates true iff C. Then, we have
evaluates to true on and false on H.
Recall that since J can written in the form of
(x) = No X1 3 NK xx
A pE(M)
Fla Rz,)) A (-F(es, 21,)) VE(()
the proof completes.
G.19
PROOF OF LEMMA 20
Lemma
20
If Hom (F, G)
Hom H) for all E F, then every & & of the above form
satisfies:
(rd G) grd (db, H).
38

---

Published as a conference paper at ICLR 2025
Proof. We prove by contradiction and assume Hom(F, G) exists given by
Hom (F, H) for all F F but there
= 3x 3x.......33 .X
A PE(P)
E(x,, 1 Fzp)
A
-Bi Fie)
(E(Q)
that classifies G and H differently. Without loss of generality we assume & evaluates true in
G. By the definition of grd, obviously if Hom F, G) = Hom(F, F, H) for all F E F, we have grd (1,, G) (rd (b H) for all v C + where db E V of the form
+ = Fx Fxx...
A
Blss, (
PE(P)
i.e. vi contains no negative edges E. next show that we can use grd( for sb to infer grd(Ø,)) .). We denote
0g = 3x 3xIK..3KK
A PE(PI
E( Rzo) A (-E(ra,, rE(a]
We now show that we can use the results grd (1.)) for th E V to infer grd for q 0, 1,.,,.. Q. We denote X .x.,....k] For g = O, obviously Φ" v thus the statement naturally holds. Since the groundings of n² consist of two parts:
that satisfy ApElr Flri, Ff A Fl(ssy (11
X that satisfy APE(P) Fl Ti,) A (r )t,), corresponding Φ1.
Obviously the two part do not intersect. Therefore, grd (1, = grd( ggrd( where E(s,,, xz,) E(Ier z1.))
( = ExI,..Exx
PE[P)
Similarly, to infer gr2())))) ) the set of X that satisfy (MPELP) E(De, 25)) consists of four non- intersect parts:
ApelP1 E(Ii, Fzp) A E(I,, Lt, E(I Ft,),
Ape(p) E(Ii,, Tjp)) A El E(I., Lt,, ^ -E Exx Ftt.)
ApeeT ElIi,, {ip) A E((x Rr ^ El Ttay ) -peer E(I;, xi,) ^ 1 -E(Ea Dr, A-EAEEEEe EE sta):
According to our assumption the first part known. For the second part, since (Npetry Fl A E( consists of two non-intersect parts:
*Npelpy E(Ii, xjp) A E(r,, Lt,) ) A E(Tey Fta), -peepp E(Ii, Ij A E( I1,)) Ex Tt,).
Thus the second part can also be inferred, and so does the third part. Therefore, the set of nodes that satisfy (Ape(p) Fi(x,,,, "x4,) can be inferred, and thus also grd (2,, G) grd (thz; H) Using the same strategy one can show that
grd, G) grd pgy H)
39

---

Published as a conference paper at ICLR 2025
for any q. Therefore, this yields the contradiction.
40


Reviews:
[{"review_id": "UwLEr9o4Sb", "reviewer": "Reviewer_ar9b", "summary": "The paper presents a novel framework aimed at systematically assessing the logical expressiveness of GNNs. It proposes a comprehensive relationship between GNNs and logic, offering a method to construct logical formulas equivalent to arbitrary GNN architectures. The paper also discusses the implications of this framework for understanding existing models, comparing expressiveness across models, and estimating WL test bounds.", "questions": "1. Early work also explained the expressiveness of GNNs from a logical perspective. What new contributions have your contributions made compared to their work? Specifically, what are the differences between the second-order logic they used and the first-order logic used in your work? What are the respective advantages and disadvantages?\n\n2. Please further elaborate and supplement what each operation in first-order logic specifically corresponds to in terms of what the model learns from the graph?\n\n3. Zhang et al. proposed a refined framework for assessing the expressiveness of GNNs in \"Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness.\" Compared to the assessment method proposed in the paper, what are the respective strengths and weaknesses? Could you provide a detailed comparative analysis?\n\n4. The paper compares several typical GNN models using a unified framework. Could you further explain how the differences in logical expressions of different GNN models correspond to the actual capabilities of the models in practice?\n\n5. Please supplement experiments to prove the completeness, rationality, and correctness of the theoretical aspects of the paper. This would be very helpful for understanding the differences between models and selecting models suitable for specific tasks.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**Solid Theory**: The paper constructs a solid theoretical foundation through extensive mathematical proofs and derivations.\n\n**Unified Framework**: By establishing a connection between GNNs and first-order logic, the paper proposes a theoretical framework that can unify different GNN models. This framework allows for a systematic comparison of the expressiveness of different GNN models.\n\n**Novel Perspective**: The paper analyzes and explains the expressiveness of GNN models from the perspective of first-order logic, providing a new perspective for understanding these models.", "weaknesses": "**Limited Comparison and Analysis**: The paper does not specifically analyze what each operation in first-order logic implies about what the model has learned, nor does it directly compare with other existing expressiveness assessment frameworks, such as the work mentioned by Zhang et al.\n\n**Practical Guidance for Model Development**: Although the paper provides an assessment framework, it lacks specific guidance on how to use this framework to guide the development of high-expressiveness GNN models.\n\n**Insufficient Experimental Validation (Not necessarily a con)**: The paper lacks an experimental section to validate the effectiveness, rationality, and correctness of its framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IOR9d4IiPr", "reviewer": "Reviewer_oDss", "summary": "The authors introduce a framework to assess the logical expressivity of Graph Neural Network (GNN) models by analyzing their underlying combination and aggregation operations. By constructing sets of logical formulas that each GNN model can capture, this method provides insights into the types of logical properties these models can represent and distinguish. Intuitively, a GNN captures a formula $\\phi$ in FO if, for any graph G, the results of $\\phi$ applied on G are fully reproduced by the representations computed by the GNN.\nBy mapping GNN operations to logical formulas, the framework identifies the set of logical statements a GNN can inherently represent. This is a more fine-grained approach to understanding the expressivity of GNNs compared to the WL hierarchy. The paper explores GNN expressivity across different prediction tasks—graph-level, node-level, and link-level—highlighting the logical distinctions between models when applied to tasks at each of these levels.", "questions": "- There should be a limitations section. For instance, do these results apply to graphs with node attributes as well? What other limitations has the proposed framework for assessing expressiveness of GNNs? What could be future work?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- A new theoretical framework for assessing the expressive power of GNNs by relating it to fragments of FO\n- Classification of existing MPNNs, subgraph GNNs\n- Ability to assess the expressive power wrt to the ability to capture certain substructures (motifs) in graphs\n- Affirms conjecture from prior work", "weaknesses": "- The presentation could be improved in several places. For instance, there could be more illustrations and examples throughout the paper. \n- Nitpick: I would refrain from assigning very positive attributes, \"simple,\" \"elegant,\" etc., to your own results and proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "333QpnvIQA", "reviewer": "Reviewer_pXBi", "summary": "The paper first proposes GACNNs, a generalisation of several GNN architectures, using sequences of combination and aggregation functions over node tuples. This allows them to subsume several existing GNNs models. They then prove the logical expressivity of GACNNs and apply those results to find the equivalent logic sets for 8 GNN variants. Finally, they show how the logical expressivity can be used to also find the homomorphism expressivity and k-WL expressivity of the model.", "questions": "1. L134 the GNN outputs \"true\" for a node. Does this mean that GNNs are restricted to those that do binary classification on nodes? If so, this is not stated explicitly anywhere.\n2. L140 why are logic sets \"quantitative\" but k-WL or homomorphism tests are not?\n3. L171 - what does \"u\" refer to? This needs to be more explicit.\n4. L179 I find it strange that the computation counts down (from K + 1) within a GACNN layer, but at the layer level it counts up from 0. Is there a good reason for this?\n5. L180 \"generalised neighbour\" has not been defined. What does this precisely refer to?\n6. L196 why not use an example of an existing GNN model here?\n7. L262 \"logic sets at the bottom\" have so far only been presented to be able to be atp(u), so what else could this refer to?\n8. L351 \"more general v\". In what sense is it more general? And why is it obviously more powerful?\n9. L450 how useful is the construction, given its recursive nature?\n10. L472 why is the WL bound on SEAL so weak, given proposition 9? Shouldn’t we be able to exactly specify it’s WL expressivity?\n11. Is the paper claiming to have generalised all GNNs? L482 seems to suggest so.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The contribution is significant and will be of interest to the ICLR community. It unifies existing work on logical expressivity of GNNs, as well as showing the consequences that this has for two other important methods of analysing GNN expressivity.\n2. The paper makes good use of space, sticking to the recommended 9 pages and rarely making redundant statements.\n3. The quality of the work appears to be good, although I haven't been able to properly verify the soundness of the proofs.\n4. The authors have made it clear where their work fits into the existing literature, and what their contribution is.", "weaknesses": "Major:\n1. The main section of the paper lacks intuitions as to why the theorems are true, as well as proof sketches. These would greatly benefit the reader, particularly for a central result such as Theorem 3.\n2. Due to a mixture of typos and imprecision, it is sometimes unclear what the authors are intending to stay from a technical perspective. This is particularly problematic in a paper that consists solely of theory. For example: on L262, the \"logic sets at the bottom\" have so far only been presented to be able to be atp(u), so what else could this refer to? And on L171, what does 'u' refer to? One might reasonably assume a node, but further down it also appears to refer to node tuples.\n3. I have many other smaller concerns with the paper, which altogether come together into a major concern.\n\nMedium:\n1. L187 the example is far too simple and doesn't do enough to explain the idea of having a sequence of operations within each layer. It is not obvious how other real GNNs can be made from these building blocks. Using a more complex example like Local 2-GNN would be more beneficial.\n2. In Theorem 3, equivalent logic sets are being used for each x_i, but they have so far only been defined for GNNs, not these building blocks. A more general definition of equivalent logic sets is needed.\n3. L327 \"auxiliary logic set\". One might assume that this relates to global readouts, given that these greek letters were just used above. However, that interpretation does not seem to fit with the proposition. It is not clear, and should be stated explicitly what this logic set is for, as well as using different notation to separate it from global readouts if that is not what it intends to represent.\n4. L331 the jump from the GNN models to their expressivity is not clear. It would be helpful to see an example of the whole pipeline in effect: GNN model -> GACNN -> equivalent logic -> simplification of the logic\n5. L406 the construction is presented in a somewhat clunky manner, and would benefit from being both more precise and concise. E.g. the enumeration (a-c) is just the definition of a graph that can be done inline\n\nMinor:\n1. L35 \"many studies\" needs a citation\n2. L38 it is unclear why k-WL lacks interpretability\n3. L49 \"although provides\"\n4. L55 MPNNs are already a generalisation of several GNNs models, so it is misleading to say they analyse different GNN models separately.\n5. L76 \"is denoted\"\n6. L97 \"leave\"\n7. L105 \"predicate\", \"corresponds\"\n8. In section 3.1, GNNs are referred to without having been defined yet.\n9. L140 \"district\"\n10. L152 \"the elements\" -> \"each element\"\n11. L166 no need for \"etc\", since you already said \"including\"\n12. L172 should be clearer that it's a sequence of two operations, not just two operations\n13. L182 \"variants\", but only one is described\n14. L187 the appendix should be referenced here for the construction of the other GNN models within this framework\n15. L254 \"existed\"\n16. L255 \"edges\" -> \"neighbourhoods\", since we're generalising to node tuples\n17. L270 \"function\", \"Similar as previous\"\n18. L281 \"is\" = \"are\"\n19. L298 \"its layers\" -> \"a layer\", since all layers have been assumed to have the same structure\n20. L309 \"provides\"\n21. L323 \"prediction\"\n22. L365 \"although computes\"\n23. L376 \"tasks\"\n24. L392 should this not be \"homomorphism expressivity\"? Homogenous has other connotations. Also \"beautiful\" is emotive language and should be avoided\n25. L404 full stop should not be there\n26. L464 - 466 is a bit verbose, and restating the obvious", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)