# Relational GNNs Cannot Learn C2 Features for Planning

arXiv: https://arxiv.org/abs/2506.11721 · HTML: https://mlsanity.com/paper/2506.11721/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 11 references that are in the map.
- First posted on arXiv 13 Jun 2025.

## Builds on (most cited first, 9 of 9)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks](https://mlsanity.com/paper/2009.05613/) (2020)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)

## Abstract (arXiv)

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.