Relational GNNs Cannot Learn $C_2$ Features for Planning
This is an incremental theoretical analysis for AI planning researchers, highlighting a gap between empirical results and theoretical capabilities in GNN-based methods.
The paper tackles the problem of Relational Graph Neural Networks (R-GNNs) failing to learn value functions defined by C2 features in planning domains, despite theoretical motivations, and identifies alternative GNN architectures that may overcome this limitation.
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 $C_2$, first-order logic with two variables and counting. In the context of planning, $C_2$ features refer to the set of formulae in $C_2$ 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 $C_2$ features. We show that, contrary to empirical results, R-GNNs cannot learn value functions defined by $C_2$ features. We also identify prior GNN architectures for planning that may better learn value functions defined by $C_2$ features.