Expressiveness of Graph Neural Networks in Planning Domains

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 12:35:45

Abstract: Graph Neural Networks (GNNs) have recently become the standard method of choice for learning with structured data, demonstrating particular promise in classical planning. Their inherent invariance under symmetries of the input graphs endows them with superior generalization capabilities compared to their symmetry-oblivious counterparts. However, this comes at the cost of limited expressive power. Notably, it is known that GNNs cannot distinguish between graphs that satisfy identical sentences of C$_2$ logic.
    
To leverage GNNs for learning policies in PDDL domains, one needs to encode the contextual representation of the planning states as graphs. The effectiveness of this encoding, coupled with a specific GNN architecture, hinges on the absence of indistinguishable states necessitating distinct actions. This paper provides a comprehensive theoretical and statistical exploration of such situations in PDDL domains across diverse natural encoding schemes and GNN models.

Main paper: 
 introduction: 
 Deep learning Neural Networks (NNs) occupy a prominent position in contemporary artificial intelligence (AI) re-20 search, exerting a substantial influence over all AI domains. Their recent generalization to variable-sized structured data, in the form of GNNs, then enabled their integration into classical planning, too (Toyer et al. 2018 (Toyer et al. , 2020;; Ståhlberg, Bonet, and Geffner 2022a,b, 2023) . The focus of this paper is on their use for learning policies in PDDL domains. More precisely, given a PDDL domain, we consider a policylearning algorithm that utilizes an NN model to predict the next action to take in any state that belongs to a given domain instance.Two aspects decide whether the policy-learning algorithm successfully solves a PDDL domain. The first aspect is the learning capacity of the underlying NN model, reflected mostly by its size, which must adequately reflect the combinatorial complexity of solving the given domain instances.The second aspect is the expressiveness of the NN model that must be sufficient for the given domain. The central aim of this paper is to focus on the latter. This is important since the structured NN architectures, such as GNNs, lack the universal approximation capabilities of their classic 40 feed-forward counterparts. GNNs represent functions whose output is invariant under the (permutation) symmetries of its inputs, which significantly improves their learning generalization. However, this comes at the cost of limited expressive power. Particularly, GNNs cannot distinguish between graphs beyond the constraints imposed by the 1-dimensional Weisfeiler-Lehman (WL) test (Morris et al. 2019; Xu et al. 2019; Grohe 2021) . We believe this aspect should be investigated in separation to discern whether a model is insufficient because of its limited learning capacity, or insufficient expressive power.There are two possible approaches to developing an NN policy-learning algorithm, either (i) design a custom, specifically tailored NN model, or (ii) use one of the existing GNN models applied on top of a suitable encoding, transforming domain instances into a graph-like data structure. An example of the first approach is ASNets (Toyer et al. 2018 (Toyer et al. , 2020)) , specifically crafted to reflect the structure of a planning domain and its instances, namely their actions and facts. This class of custom approaches comes with considerable variability but that also makes it difficult to systematically study its expressiveness. This is why we focus on the second approach, building on the existing, widespread GNN architectures (Wu et al. 2020) and their associated expressiveness characterizations (Grohe 2021) . The schema of this approach, with example works including (Ståhlberg, Bonet, and Geffner 2022a,b, 2023) , is depicted in Fig. 1 . Given a PDDL domain, its instance, and its particular state, respectively, we encode the corresponding contextual state representation into a suitable data structure to be processed by a GNN to output an action prediction. The encoding, together with the GNN architecture, then determines the overall expressiveness of the resulting policy-learning algorithm. This integration establishes a function f which, for a given state s and GNN parameters θ, yields a prediction f (s, θ). The expressiveness of this function then lies in its ability to distinguish between different states. Particularly, we call two states s, s ′ indistinguishable w.r.t. f if f (s, θ) = f (s ′ , θ) for any tuple of parameters θ. Note that this is a desired property of all the structured, symmetry-aware (G)NN architectures. However, we call an indistinguishable pair bad if s, s ′ should lead to different predictions. The main contribution of this paper is a theoretical and statistical analysis probing the prevalence of such bad state pairs in PDDL domains.We recall several concepts from mathematical logic that we will need in the sequel. A first-order relational language L consists of predicate symbols together with their respective arities and variables. 1 An atomic formula is an expression of the form R(x 1 , . . . , x n ) where R is an n-ary predicate symbol and each x i is a variable. The formulas of first-order logic (FOL) are built from atomic formulas using Boolean connectives and quantifiers ∀, ∃. A FOL-formula without free variables (i.e., all its variables belong to the scope of a quantifier) is called a sentence.The FOL formulas are interpreted in L-structures. An Lstructure is a tuple S = ⟨S, ⟨R S | R ∈ L⟩⟩ where S is a set of objects, and R S ⊆ S n is the interpretation of the n-ary predicate symbol R ∈ L. The fact that a FOL-sentence φ holds in S is denoted S |= φ.A (ground) atom over a set of objects S is an expressionof the form R(b 1 , . . . , b n ) where R is an n-ary predicate symbol and each b i ∈ S. The ground atom R(b 1 , . . . , b n ) holds in S iff ⟨b 1 , . . . , b n ⟩ ∈ R S .Note that there is a one-toone correspondence between L-structures on S and sets of ground atoms over S. Namely, an L-structure S can be represented as the set of ground atoms ψ S that hold in S, and conversely a set of ground atoms ψ represents an L-structureS ψ whose relation R is defined by ⃗ c ∈ R S ψ iff R(⃗ c) ∈ ψ.We say that two L-structures S, S ′ are isomorphic if there is a bijection σ :S → S ′ such that ⃗ c ∈ R S iff σ(⃗ c) ∈ R S ′for each predicate R ∈ L. In the expression σ(⃗ c), the bijection σ is applied component-wise to each object in ⃗ c.We call an L-structure binary if all its relations are at most binary. A graph is a binary L-structure G = ⟨G, E G , P G 1 , . . . , P G m ⟩ for the language L consisting of a binary predicate symbol E representing edges, and sev-120 eral unary predicate symbols P 1 , . . . , P m representing node properties. As graphs are not directed, E G must be a symmetric relation. Given G and a node u ∈ G, the set of its neighbours is denotedN G (u) = {v ∈ G | ⟨u, v⟩ ∈ E G }.The logic C is an extension of FOL, adding counting existential quantifiers ∃ ≥n for each n ≥ 1. A sentence ∃ ≥n xφ(x) holds in a structure if there are at least n pairwise different objects b such that φ(b) holds. The counting quantifiers are definable in FOL but they are not if we restrict the number of variables. The logic C k is the fragment of C having only k variables. To express more complex properties of a structure like a graph in C k , one often needs to "reuse"1 For simplicity, we assume that L do not contains constants. They can be easily simulated by unary predicates. More precisely, for each constant c, one introduces a unary predicate symbol Pc such that Pc(x) holds iff x = c. variables in nested formulas. For instance, in C 2 one can express that there is a node in a graph with property P 1 , such that all of its neighbours have at least three neighbours without property P 2 , as follows:∃xP 1 (x) ∧ ∀y(E(x, y) → ∃ ≥3 x(E(y, x) ∧ ¬P 2 (x)))The last quantifier ∃ ≥3 reuses the variable x. Inside the scope of ∃ ≥3 , we cannot refer to x introduced by the first existential quantifier anymore. Due to this limitation, C 2 can express that there is a path in a graph of any length, but not a cycle of length greater than 2, since once we reuse a variable we cannot refer back to check whether we closed the cycle.We say that two L-structures S, S ′ are C k -equivalent if they satisfy the same C k -sentences, i.e., for each C ksentence φ we have S |= φ iff S ′ |= φ. Two example nonisomorphic C 2 -equivalent graphs are depicted in Fig. 2 .We assume that the reader is familiar with classical planning and Planning Domain Definition Language (PDDL). We consider the normalized, non-numeric, non-temporal PDDL tasks without conditional effects, axioms, and negative preconditions, and with all formulas being conjunctions of atoms. The types are modeled as unary predicates. Hence, for each type (i.e., a set of objects), a corresponding unary predicate is interpreted by that set of objects; for details see (Helmert 2009) .A PDDL Domain is a pair D = ⟨L, A⟩ where L is a first-order relational language and A is a collection of action schemas. A state in D is an L-structure S. The action schemas define a state transition system using grounding in the usual way (Corrêa et al. 2020 ). Since we only deal with states, we skip the formal definition of the transition system.Given a state S, a goal is a set of ground atoms built from objects in S. A goal state is a state where all atoms from ψ G hold. A planning instance for a domain D is a pair ⟨S, ψ G ⟩ where S is a state and ψ G is a goal. Following (Ståhlberg, Bonet, and Geffner 2022a) , we integrate the goal ψ G into the state S by expanding its language L. We define an expansion L G of L such that for each n-ary predicate R in L, there is a new n-ary predicate R G in L G . Given a state S and a goal ψ G , an enriched state S G is an L G -structure whereR S G = R S for each predicate R ∈ L, and R S G G = {⃗ c | R(⃗ c) ∈ ψ G } for each predicate R G ∈ L G \ L.From now on, when we refer to a state, we mean a state enriched by the goal information.A plan for a state S G is a sequence of ground actions transforming S into a goal state. A plan is called optimal if it is shortest among all plans.The optimal value function V * assigns to a state the length of its optimal plan, and ∞ if there is none. The greedy policy for V * , selecting a successor state with the minimum value of V * , is the optimal policy for the domain D.To make the GNN predictions concrete in our experiments, we assume that the GNN predicts the optimal value function V * that defines the optimal greedy policy, in the same way as (Ståhlberg, Bonet, and Geffner 2022a) .The following theorem ensures that we can represent V * by a model that is invariant under symmetries of its inputs.Theorem 1. Let D = ⟨L, A⟩ be a PDDL domain and S, S ′ two isomorphic L G -structures. Then V * (S) = V * (S ′ ).The theorem can be proven by induction on the length of the plan. From Theorem 1, it also follows that states with different values of V * can be distinguished by a FOL sentence. Unfortunately, this need not be true for C 2 -sentences, as we will see in the next sections.GNNs have recently become the standard architecture for structured data, applied across various tasks in the form of node, edge, and graph classification/regression, with the latter corresponding to the prediction of V * that we consider 200 in this paper. GNN models generally take as input a binary graph-like structure whose nodes, and possibly edges, are labeled by real-valued "feature vectors". These are then consecutively processed through a series of parameterized differentiable transformations into the output prediction value.The specific GNNs may differ in many aspects. The relevant one for this paper is their input format, which can be an actual graph but also an arbitrary binary structure. If it is a graph, we only have a single undirected edge relation, and all the nodes must be of the same type, reflected by shared feature vector dimensions. If it is a binary structure, we can have several directed edge relations, corresponding to a multi-graph. Moreover, if the nodes are of different types, reflected by differently sized feature vectors, we call the input a heterogeneous (multi) graph, with a special case being the bipartite graph where we only have two types of nodes. Independently from the above classification, a GNN architecture either supports edge features or not.GNN models are generally based on the concept of "message-passing". From the theoretical point of view, the expressiveness of message-passing architectures has been extensively studied for graphs without edge features, as defined in the FOL Section 2. We recall the most important results here; for an overview see (Grohe 2021) .Given a graph G = ⟨G, E, P 1 , . . . , P n ⟩, the feature vector u ∈ {0, 1} n of a node u ∈ G is constructed from the unary predicates P i as follows:u i = 1 iff P i (u) holds in G.We refer to the above construction as a multi-hot encoding.A GNN g based on the message passing scheme consists of several layers ℓ 1 , . . . , ℓ k . Each layer ℓ i for i < k takes a graph G whose nodes are labeled by a real-valued vector and updates its labeling. For a node u ∈ G, we denote the feature vector entering the first layer by u (0) . Each layer ℓ i for i < k then produces new vectors u (i) based on the formula:u (i+1) = comb(u (i) , agg({{v (i) | v ∈ N G (u)}})) (1)where {{. . .}} denotes a multiset, agg is a function aggregating the multiset of the feature vectors of all neighbours of a node u, and comb is a function combining the feature vector of u with the result of agg.The final "read-out" layer ℓ k then takes the multiset of all the vectors from the ℓ k-1 layer and, similarly to agg, aggregates them into a single output value:ro({{u (k-1) | u ∈ G}}) (2)We denote the tuple of all the parameters contained within the respective comb, agg, and ro parameterized differentiable functions from all the layers of the GNN g as θ, and the output of such g as g(G, θ).Note that the computation done by the message-passing is conceptually the same as in the Color Refinement Algorithm (CR). CR computes a node-coloring for a colored graph by applying Equation ( 1), with agg being the identity function and comb being concatenation. CR can be used as an isomorphism test for two graphs that is as strong as the 1-dimensional Weisfeiler-Lehman test (1-WL); see (Grohe 2021) . It is known that 1-WL cannot distinguish all nonisomorphic graphs. More precisely, it can distinguish exactly those that are not C 2 -equivalent (Cai, Fürer, and Immerman 1992) . Thus, it is not surprising that message-passing GNNs have the same limitations. The following two theorems were independently proved in (Morris et al. 2019; Xu et al. 2019) .Theorem 2. Let g be a GNN and G, G ′ two graphs. If G, G ′ are C 2 -equivalent, then g(G, θ) = g(G ′ , θ) for any tuple of parameters θ.It follows from the above theorem that we cannot distinguish two C 2 -equivalent graphs by a message-passing GNN, no matter its number of layers or dimensionality of the parameters used in their comb and agg functions.The reverse direction holds as well, even though the result is not uniform. Particularly, for each n there is a GNN that is able to distinguish all pairwise C 2 -non-equivalent graphs up to size n. Theorem 3. Let n ≥ 1. There is a GNN g and parameters θ such that for all graphs G, G ′ of order at most n, if G, G ′ are not C 2 -equivalent, then g(G, θ) ̸ = g(G ′ , θ).Whether a particular GNN actually distinguishes two graphs depends on the number of layers and the functions comb, agg and ro. Crucially, it depends on how well agg can separate two different multisets of (feature) vectors. For instance, it is known that agg based on the summation sum are more expressive than those based on mean, with max being the least expressive variant (Xu et al. 2019) .To further increase the GNN expressiveness, there are various higher-order GNN variants, mostly mimicking the k-dimensional WL test; see (Grohe 2021) . Here, instead of single nodes, we compute the 1-WL over a graph built from all k-tuples of nodes. Such variants can then distinguish graphs up to C k -equivalence. However, the number of k-tuples grows fast with k, hence variants based on k-sets (sets of size k) were introduced instead (Morris et al. 2019) . Although k-sets are more efficient, they lose the theoretical connection with the WL test.To apply a GNN to learn a policy, one needs to design an encoding of the enriched state into a data structure compatible with the GNN's input format. In this section, we systematically explore the space of such possible encodings to be later tested in our experiments. Each encoding converts an Lstructure S either to a labeled graph, multi-graph, or bipartite (multi) graph (Sec. 2). We further decompose each encoding into two steps. The first step converts the L-structure S to a binary structure S 2 . The second step transforms the binary structure into the GNN input.To define a binary structure S 2 from an L-structure S, there are several natural choices for creating its objects:• the objects in S 2 are the objects in S,• the objects in S 2 are the atoms that hold in S,• the combination of the above cases, i.e., we create objects in S 2 from both the objects and the valid atoms in S,• the objects in S 2 are (ordered) pairs of objects from S.In the following subsections, we discuss each variant in detail. As a running example illustrating each encoding, we use the L G -structure from the following example.Example 4. Consider a language L consisting of a nullary predicate symbol N , two unary predicates R, L, a binary A, and ternary T . Recall that the language L G is the extension of L by the goal copies of all the predicates. The L Gstructure S is defined over the set of objects S = {r, l 1 , l 2 } so that it satisfies exactly the following set of ground atoms:{N, R(r), L(l 1 ), L(l 2 ), A(r, l 1 ), A G (r, l 2 ), T (r, l 1 , l 2 )}Before we describe the particular encodings, we introduce our notation regarding tuples of objects. For a tuple of objects ⃗ c, c i denotes its i-th element. The first encoding keeps the sets of objects in S and S 2 the same. To reduce the arity of predicates greater than 2 to binary, we simply relate two objects if they jointly occur in an atom that holds in S. Given a language L, we define its binarization L O as the language consisting of the same predicate symbols as L, but with arity of all the predicates beyond binary being equal to 2. Definition 5. Let S = ⟨S, ⟨R S | R ∈ L⟩⟩ be an L-structure. We define its object binary structure as an L O -structureS 2 = ⟨S, ⟨R S2 | R ∈ L O ⟩⟩ where R S2 = R Sfor a nullary or unary predicate symbol R. For a predicate R of arity at least 2, we define Note that all the binary relations in S 2 are symmetric by the definition because c 1 , c 2 might occur in any position in 340 ⃗ c. As a variant, it makes sense to keep the binary relations in S 2 the same as in S. However, for relations R S of arity greater than 2, there is no canonical way to define directions on R S2 . Hence, we keep all the binary relations symmetric in S 2 for simplicity. The structure S 2 for S defined in Ex-345 ample 4 is shown in Fig. 3 . The nullary and unary predicates are depicted as node labels. The fact that the nullary predicate N holds in S 2 is depicted as a label shared across all the objects. If there are several binary relations connecting two nodes, we list them along a single edge.⟨c 1 , c 2 ⟩ ∈ R S2 iff {c 1 , c 2 } ⊆ ⃗ c for some ⃗ c ∈ R S .Once we have the binary structure S 2 , we can build the corresponding GNN input. First, we encode the information about nullary and unary predicates into node feature vectors. This can be done by the multi-hot encoding (Sec. 2), where we treat the nullary predicates as unary ones that either hold 355 for all objects or none. Then, for a graph variant, we encode the information about all the relations connecting two nodes into a respective multi-hot edge feature vector or, for a multigraph variant, we treat each such relation as a separate edge with a corresponding one-hot feature vector. Depending on 360 the applied GNN model, the edge feature vectors are then either exploited or ignored.The next natural choice for objects of S 2 is the atoms that hold in S. The concept of connecting two atoms is then 365 based on their contained and shared objects. First, we connect two atoms if they share common objects. Second, we also connect two atoms if the symmetric difference of objects occurring in the atoms is related by a relation from S.Let L be a language and m the highest arity of a predicate 370 in L. We define a new language L A such that each predicate from L is in L A as a unary predicate, and for each pair ⟨i, j⟩ ∈ [1, m] 2 there is a binary predicate E i,j . Finally, for each predicate R of arity at least 2, there is a binary predicate R in L A . 375 Definition 6. Let S = ⟨S, ⟨R S | R ∈ L⟩⟩ be an L-structure. We define its atom binary structure as an L A -structure S 2 = ⟨A, ⟨R S2 | R ∈ L A ⟩⟩ where A is the set of all atoms that hold in S, i.e., each atom α ∈ A is of the form R(⃗ c) for some tuple ⃗ c ∈ R S .For a unary predicate R ∈ L A and an atom α ∈ A, we define α ∈ R S2 iff α = R(⃗ c). Hence, the unary predicates in L A express the predicate of a given atom. For a binary predicate E i,j ∈ L A and atoms α, β ∈ A,T R L L A A G N E 2,1 E 1,2 E 3,1 E 1,3 E 1,1 E 1,1 E 2,1 E 1,2 E 2,1 E 1,2 E 1,1 E 1,1 E 1,1 E 1,1 E 1,1 , T E 1,1 , T E 1 , 1 , E 2 , 2 E 1 , 1 , E 2 , 2 E 1 , 1 , E 3 , 2 E 1 , 1 , E 2 , 3we define ⟨α, β⟩ ∈ E S2 i,j iff α = R( ⃗ b), β = R ′ (⃗ c) and b i = c j . In words, the binary predicates E i,j tell us that the i-th object of the atom α is the same as the j-th object in the atom β.For a binary predicate R ∈ L A and atoms α, β ∈ A, we define390 ⟨α, β⟩ ∈ RS2 iff α = R ′ ( ⃗ b), β = R ′′ ( ⃗ b ′ ) and ⃗ b△ ⃗ b ′ ⊆ ⃗ c for some ⃗ c ∈ R S .The meaning of the predicate R is that if we remove all common objects from ⃗ b and ⃗ b ′ , the remaining set of objects appear in an atom of the form R(⃗ c) that holds in S.The atom binary structure S 2 for the running example is depicted in Fig. 4 . Each atom is labeled by its predicate. For example, the atom T (r, l 1 , l 2 ) is labeled by T , and A G (r, l 2 ) is labeled by A G . Then note the directed edge from T (r, l 1 , l 2 ) to A G (r, l 2 ) labeled by E 1,1 and E 3,2 , as the first object r in T (r, l 1 , l 2 ) is also the first object in A G (r, l 2 ). Likewise, the third object l 2 in T (r, l 1 , l 2 ) is the 400 second object in A G (r, l 2 ). Also note that the atom A(r, l 1 ) and A G (r, l 2 ) are related by T , since if we remove their shared object r, the remaining objects l 1 , l 2 occur in the atom T (r, l 1 , l 2 ).To make a GNN input from the atom binary structure, we follow a process analogous to the object binary structure. That is, the unary predicates are encoded into the node features, and the binary relations are encoded into edge features, forming either graph or multi-graph, depending on the choice of multi-hot or one-hot encoding, respectively.The next encoding builds the binary structure S 2 on both objects and atoms. This naturally leads to a bipartite graph as we have two sorts of nodes. The edge relations connect an object with an atom if the object occurs in the atom. Let L 415 be a language and m the highest arity of a predicate in L. We define a new language L OA such that each predicate from L is in L OA as a unary predicate, and for each i ∈ [1, m] there is a binary predicate E i . Finally, L OA has two extra unary predicates O, F to distinguish objects from atoms.R L L T R A A G L L N E 1 E 1 E 1 E 1 E 2 E 2 E 1 E 3 E 2 E 1Definition 7. Let S = ⟨S, ⟨R S | R ∈ L⟩⟩ be an Lstructure. We define its object-atom binary structure as an L OA -structure S 2 = ⟨S ∪ A, ⟨R S2 | R ∈ L OA ⟩⟩ where A is the set of all atoms that hold in S, O S2 = S, and F S2 = A. For a predicate R ∈ L and an atom α ∈ A, we define for the unary R ∈ L OA :α ∈ R S2 iff α = R(⃗ c).In other words, each atom knows its predicate. Moreover, if R ∈ L is unary and an object b ∈ S, we further defineb ∈ R S2 iff b ∈ R S .This means that each object knows its unary properties.For an object b ∈ S and an atom α ∈ A, we define ⟨b, α⟩, ⟨α, b⟩ ∈ E S2 i iff α = R(⃗ c) and b = c i . In other words, we relate the object b with the atom α via E i iff b occurs in the i-th position within the atom α.The object-atom binary structure for the structure S from Example 4 is shown in Fig. 5 . The atoms (i.e., elements of A) are depicted as black dots whereas the objects (i.e., elements of S) as black boxes. The atoms are labeled by their predicates and objects by the unary predicates from L they satisfy. An object is connected to an atom if it appears in that atom. For instance, the object l 2 is connected toT (r, l 1 , l 2 ) via E 3 , to A G (r, l 2 ) via E 2 , and to L(l 2 ) via E 1 .The GNN input is then formed analogously to the previous two cases, forming edge features from the respective binary relations, and two types of feature vectors for the object and atom nodes, respectively, resulting in a bipartite (multi) graph. Thus the information from the feature vectors attached to objects is propagated to the feature vectors of atoms, and vice versa. We note that the multi-graph variant of this bipartite encoding, together with a suitable GNN architecture, roughly corresponds to the model applied in (Ståhlberg, Bonet, and Geffner 2022a,b, 2023) .To reach beyond the expressive power of the C 2 logic, we also introduce an encoding inspired by the higher-order GNNs, namely 2-GNN (Morris et al. 2019) . Given a graph G, 2-GNN applies the message passing scheme to a graph built on 2-sets of objects. Two 2-sets {b 1 , b 2 } and {c 1 , c 2 } are connected by an edge if |{b 1 , b 2 } ∩ {c 1 , c 2 }| = 1, i.e., if they share a single object. Morris et al. also consider a "local" variant of the graph where the 2-sets are connected if they share a single object and the objects in their symmetric difference are connected by an edge in G.We model these 2-sets as 2-tuples whose components are sorted by a fixed total order ≤ on the set of objects, i.e.,⃗ b = ⟨b 1 , b 2 ⟩ for objects b 1 , b 2 such that b 1 ≤ b 2 .Using the non-strict ≤, unlike Morris et al., we thus also consider the singletons, represented as ⟨b, b⟩. Given a finite set S, we denote[S] 2 = { ⃗ b = ⟨b 1 , b 2 ⟩ | b 1 , b 2 ∈ S, b 1 ≤ b 2 }.We refer to the elements of [S] 2 as ordered pairs.Let L be a language. We define a new language L OP . The languages L and L OP agree on the nullary predicates. For each unary predicate P in L we have two copies P 1 , P 2 in L OP . For the remaining predicates R ∈ L of arity at least 2, we have one unary predicate R and one binary R in L OP . The language L OP further has an extra binary predicate E. Definition 8. Let S = ⟨S, ⟨R S | R ∈ L OP ⟩⟩ be an Lstructure. We define its object-pair binary structure as anL OP -structure S 2 = ⟨[S] 2 , ⟨R S2 | R ∈ L OP ⟩⟩where S 2 is the set of all ordered pairs of objects in S. The interpretation of nullary predicates in S 2 is the same as in S. For a unary predicate P ∈ L and an ordered pair⃗ b = ⟨b 1 , b 2 ⟩ ∈ [S] 2 , we define ⃗ b ∈ P S2 1 iff b 1 ∈ P S . and similarly, ⃗ b ∈ P S2 2 iff b 2 ∈ P S .For a unary predicate R ∈ L OP corresponding to a predicate R ∈ L of arity at least 2 and an ordered pair⃗ b = ⟨b 1 , b 2 ⟩ ∈ [S] 2 , we define ⃗ b ∈ R S2 iff {b 1 , b 2 } ⊆ ⃗ c for some ⃗ c ∈ R S .In other words, the ordered pairs know if their inner objects are related by the predicate R. For two ordered pairs ⃗ b, ⃗ c ∈ [S] 2 , we define⟨ ⃗ b, ⃗ c⟩ ∈ E S2 iff ⃗ b ̸ = ⃗ c and | ⃗ b ∩ ⃗ c| = 1.Lastly, for a binary predicate R ∈ L OP and two ordered pairs ⃗ b, ⃗ c ∈ [S] 2 , we define⟨ ⃗ b, ⃗ c⟩ ∈ RS2 iff ⟨ ⃗ b, ⃗ c⟩ ∈ E S2 and ⃗ b△⃗ c ⊆ ⃗ d for some ⃗ d ∈ R S .The object-pair binary structure for the structure S from Example 4 is shown in Fig. 6 . Note that the validity of the nullary atom N is depicted as a label N attached to all ordered pairs. The predicates labeling the ordered pairs with the subscript 1 (resp. 2) refer to properties of the first (resp. second) object in the pair. Ordered pairs are also labeled by the predicates relating their components. For instance, the ordered pair ⟨r, l 2 ⟩ is labeled by A G and T because r, l 2 occur in A G (r, l 2 ) and T (r, l 1 , l 2 ). The edges labeled by E connect different ordered pairs sharing a common object, e.g., ⟨l 1 , l 1 ⟩ is related to ⟨l 1 , l 2 ⟩ by E. Further edges connect those ordered pairs, already connected by E, whose symmetric difference-objects are related by a predicate. For instance, there is an edge T between ⟨r, l 1 ⟩ and ⟨r, l 2 ⟩ because they are related by E, ⟨r, l 1 ⟩△⟨r, l 2 ⟩ = {l 1 , l 2 } and both 505 l 1 , l 2 occur in T (r, l 1 , l 2 ).N, R 1 , R 2 N, R 1 , L 2 , A, T N, R 1 , L 2 , A G , T N, L 1 , L 2 N, L 1 , L 2 , T N, L 1 , L 2 E , Â, T E , Â G , T E, T E , Â, T E , Â G , T E , Â G , T E , Â, T E, T E, TThe GNN input is created from the L OP -structure S 2 in the same way as for the object binary structure. 
expressiveness: 
 The previous section detailed several encodings transform-510 ing an enriched state to a data structure suitable for existing GNN models. In this section, we take a theoretical point of view on their expressive power. Recall that we are interested in whether a PDDL domain D contains bad indistinguishable pairs of enriched states (Sec. 1). Since the policy 515 algorithm is supposed to solve instances within a given D, we only need to distinguish pairs of states from a single instance, which are always defined on a fixed set of objects and enriched by the same goal.Firstly, the expressive power of the algorithm might be 520 limited by the encoding. In practice (Sec. 5), this is often due to the conversion of the arbitrary input structure to the binary one. For instance, consider a language L with a single ternary predicate T and an L-structure S = ⟨{0, 1, 2}, T S ⟩ where T S = {⟨0, 1, 1⟩, ⟨1, 2, 2⟩, ⟨2, 0, 0⟩}. The object bi-525 nary structure for S (Definition 5) is then just a triangle with self-loops on the set {0, 1, 2}. Now consider a similar L-structure S ′ whose interpretation of T is T S ′ = T S ∪ {⟨0, 1, 2⟩}. Apparently, if we create the object binary structure for S ′ , we end up with the same triangle as be-530 fore. Thus S and S ′ are indistinguishable if we apply the encoding from Definition 5. On the other hand, the encodings given by the atom binary (Definition 6) and object-atom binary (Definition 7) structures can distinguish S and S ′ , as these structures differ in the number of valid ground atoms, 535 corresponding to nodes.Secondly, the expressiveness of a GNN is primarily limited by the C 2 -equivalence (Theorem 2) w.r.t. its input graphs. Hence, if the graphs produced by the encoding for a pair of enriched states S and S ′ are C 2 -equivalent, the GNN 540 will predict the same output for both. For instance, consider the well-known "blocksworld" PDDL domain, which contains at most binary predicates, ensuring that none of This sentence expresses that there is a "cycle" of length 3that cannot be equivalently expressed in C 2 . If we encode S, S ′ by the object binary structure (Definition 5), we obtain just their symmetric versions that are C 2 -equivalent as well. Similarly, the encoding based on the object-atom binary structure (Definition 7) does not resolve the issue, as it 555 also produces C 2 -equivalent graphs. Nevertheless, we can overcome the limits of C 2equivalence for the above-mentioned blocksworld states using the object-pair binary structure encoding (Definition 8). Recall that this encoding forms ordered pairs of objects that 560 are connected if they share a common object. This shared object can then be exploited as a "memory" for detecting the cycles. More precisely, the object-pair binary structure for S satisfies the following C 2 -sentence: ∃x, y(On(x) ∧ On G (y) ∧ On(x, y))Note that the variables x, y are now interpreted as or-565 dered pairs. The witnesses showing that the above sentence holds are the pairs ⟨a, b⟩ and ⟨a, c⟩. This yields On(⟨a, b⟩), On G (⟨a, c⟩), and On(⟨a, b⟩, ⟨a, c⟩) as these pairs share the object a, and the remaining objects b, c are related by On in S. On the other hand, the object-pair encoding of S ′ does not satisfy the above sentence since none of the ordered pairs sharing a single object is related by On.Note that similar reasoning can also be applied to the atom binary structure (Definition 6) since each atom, in fact, represents a tuple of objects. Therefore it effectively distinguishes the C 2 -equivalent blocksworld states as well. However, the collection of atoms need not represent all k-tuples of objects (e.g., all the ordered pairs). Consequently, the atom binary structure and object-pair binary structure encodings are not directly comparable in their expressive power. 
conclusions: 
 We systematically defined possible encodings of planning states into data structures compatible with common GNNs. Each such proposed encoding, in conjunction with several 675 compatible GNN models, was assessed for the presence of undesirably indistinguishable state pairs. Our findings highlight the superior expressiveness of the encodings based on atoms and object-pairs, relative to the, more common, encodings based on object-atom and object binary structures. 680 Nevertheless, their superiority is accompanied by larger GNN inputs and runtimes. Most of the empirical limitations of GNN expressiveness in planning domains then seem to stem from the presence of predicates with arity exceeding 2, a conclusion that aligns intuitively with the binary nature of 685 the message-passing scheme underlying the GNNs. 
5 experimental study: 
 The theoretical investigation of expressiveness for all the particular encodings and GNNs is considerably challenging, given the plethora of existing models and the limited applicability of Theorem 2 and Theorem 3 to only a selected sub- 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 blocks 0,31 0,31 0,00 0,00 0,00 0,00 0,00 0,04 0,04 depot 0,00 0,00 0,13 0,13 0,00 0,00 0,00 0,13 0,13 elevators 0,00 0,00 0,00 0,00 0,06 0,00 0,00 0,00 0,00 floortile 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 freecell 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 gripper 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 logistics 0,00 0,00 0,15 0,25 0,00 0,00 0,00 0,05 0,30 parcprinter 59,83 60,17 57,83 57,83 61,83 84,50 77,00 7,50 7,33 pegsol 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 rovers 0,00 0,00 0,04 0,04 0,17 0,55 0,55 0,00 0,00 satellite 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,67 tidybot 0,05 0,05 0,05 0,05 0,00 0,00 0,00 0,10 0,00 tpp 0,00 0,18 0,00 0,00 0,00 0,00 0,00 0,00 0,00 transport 0,00 0,00 0,00 0,08 0,00 0,00 0,00 0,00 0,17 visitall 0,07 0,00 0,20 0,07 0,00 0,00 0,00 0,00 0,00 woodworking 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 pipesworld 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 exceptions of "vacuum-sep" and "vacuum-sh" introduced in (Ståhlberg, Bonet, and Geffner 2022a) . These domains model multiple robots cleaning a single spot. The two variants differ in the maps defining the robots' allowed moves.In the first variant, each robot has its own map, unlike in the second variant, where the map is shared across the robots.The upper part of Tab. 1 presents the average numbers of bad state pairs for a particular encoding and GNN model across all PDDL domains. The absence of certain combinations is due to the incompatibility of the GNN model with the respective encoding. Notably, the combinations based on the most expressive encodings of the atom and object-pair binary structures (Sec. 3) tend to perform the best overall. The lower part of the table displays the performance of the encodings for the domains using a fixed GNN model (GEN by Li et al.) . As can be seen, for each domain there exists an encoding that can almost perfectly distinguish the states, with exceptions for "parcprinter", "scanalyzer", "sokoban", and both the "vacuum" domains. Interestingly, the "sokoban" domain appears particularly challenging across a wide range of settings, but can be effectively addressed with the A, O-P encodings. We note that a common trait of the difficult domains is the use of predicates of arity greater than 2. Conversely, the "pegsol" domain employs a ternary predicate and still exhibits no bad pairs. However, the ternary predicate in "pegsol" is static (unaffected by actions), and the states are modeled by unary 670 predicates, making the domain likely more manageable. 
: 
 pared to their symmetry-oblivious counterparts. However, this comes at the cost of limited expressive power. Particularly, it is known that GNNs cannot distinguish between graphs that satisfy identical sentences of C2 logic. To leverage GNNs for learning policies in PDDL domains, one needs to encode the contextual representation of the planning states as graphs. The expressiveness of this encoding, coupled with a specific GNN architecture, then hinges on the absence of indistinguishable states necessitating distinct actions. This paper provides a comprehensive theoretical and statistical exploration of such situations in PDDL domains across diverse natural encoding schemes and GNN models. 
 
 Appendix: This is slightly complicated by the fixed ReLU functions used in some of the GNNs, but is of negligible practical impact. 


Decision: There is a clear consensus to accept this paper. Congratulations. Please take into account the comments on the reviews when preparing the final version.

Reviews: review: strength_weakness: strength_weakness: The significance of the paper may be not high, given the nature and the scope of the results.
The theoretical analysis of expressiveness (section 4) is rather limited.

minor:
- footnote 1: "\calL do not" -> "\calL does not"
- "an example if which" -> "an example of which"
- there is only one example, should be labelled Example 1, not 4.
- the proofs of the Theorems are missing.
questions: questions: (1) The authors focus on detecting bad indistinguishable pairs. Can they elaborate/motivate why and to what extent is this task more appropriate than focusing on learning the "correct" V*, which is not directly addressed in the paper? Related to this, why not analyzing as well the problem of producing distinct outputs for state pairs which should produce the same output?

(2) How are exactly the GNN parameters chosen in the experimental study? I am assuming that the GNNs are not optimized (trained). Wouldn't it make more sense to compare the outputs of the trained GNNs instead of using sample parameters?

(3) The most recent GNN variants (e.g. subgraph GNNs) overcome "efficiently" the theoretical limits in expressive power derived for "vanilla" GNNs. Is that the case for any of the methods compared in Table 1? Can the authors elaborate a bit more on the implications of losing the theoretical connection with the WL test, and the relevance/significance of their results?

(4) Choosing the identity function as 'agg' in Eq (1) is not permutation invariant. Isn't this a problem to compute a node-coloring as in the CR algorithm?
strength_weakness: strength_weakness: 1. A contrast with runtimes and added complexity would help provide a better picture of the trade-offs in the paper. The paper makes note of this but does not provide any such metrics.
questions: questions: 1. Could you provide a brief overview of the drawbacks of the Object-Pair Binary Structure w.r.t scalability as the # of objects increase?

Post-rebuttal
===========
Thank you for answering my questions. Very interesting work and will help additional research in generalization.
strength_weakness: strength_weakness: The lack of detail explicitly given in setting up and describing the data presented about the experimental work is the biggest weakness. Questions I had regarding this that I did not see answered were:

 - What are the state(/problem) sizes (#states) and numbers of objects?  

 - Line 590, authors mention they generate "random states". How are these generated? Are they states reachable from the initial state of a benchmark task? Or are they truly random, and potentially 'invalid' in the sense they would never be encountered when solving a planning task? Does any care need to be taken to ensure these states are somehow representative of a relevant and sufficiently sized set wrt badness hunting/measuring? What about the distributions of values of the random states encountered in different domains? Do these all have the same shapes? 

Note: The above two points should be explained more in the paper, but given things are assumed to be somehow fair across all encoding-model measurements, I do not consider this a huge weakness. 

 - Reported is the average number of bad pairs. This admits comparisons as per the paper, because we suppose all encoding-models are evaluated here over the same set. So things are acceptable. But the weakness is that it's challenging to interpret the provided average, and get a sense of whether GNNs are likely or unlikely to be 'bad' in the sense developed here. I do not have a sense of the opportunity for badness or how that scales in different domains.

 - Actual function approximation performance at value function modelling and computation time are not considered.

 - On Line 613 the authors chose Rep=3. It is not obvious why they are confident that this number of repetitions is sufficient.

 - To reproduce exactly this experimental data may be quite difficult (inc. details related to the specifics of orderings for Def 8.), and it would be helpful if the software that is specific to planning, datasets of state-values (or for generating the same as used here), and these experiments were available to the community. Overall however, it seems the core distinguishing features of the state representations for the different encodings are described in sufficient detail. So, we should expect to reproduce the main experimental conclusions.

More detail about the different graph types would be welcome/helpful, although the lack of space in this format is noted as a constraining on this point. 

On Line 100 -  I think finiteness conditions be mentioned in this paragraph.

grammar: "The counting quantifiers are definable in FOL, but they are not if we restrict the number of variables."
questions: questions: Why are you confident your experimental datasets comprise a fair and representitive set of states wrt the opportunity for badness in each domain?