Relational GNNs Cannot Learn C2 Features for Planning

Relational Graph Neural Networks (R-GNNs) are a GNN-based approach for learning value functions that can generalise to unseen problems from a given planning domain. R-GNNs were theoretically motivated by the well known connection between the expressive power of GNNs and C2, first-order logic with two variables and counting. In the context of planning, C2 features refer to the set of formulae in C2 with relations defined by the unary and binary predicates of a planning domain. Some planning domains exhibit optimal value functions that can be decomposed as arithmetic expressions of C2 features. We show that, contrary to empirical results, R-GNNs cannot learn value functions defined by C2 features. We also identify prior GNN architectures for planning that may better learn value functions defined by C2 features.