  GNN-based approaches for learning general policies across planning domains
are limited by the expressive power of $C_2$, namely; first-order logic with
two variables and counting. This limitation can be overcomed by transitioning
to $k$-GNNs, for $k=3$, wherein object embeddings are substituted with triplet
embeddings. Yet, while $3$-GNNs have the expressive power of $C_3$, unlike $1$-
and $2$-GNNs that are confined to $C_2$, they require quartic time for message
exchange and cubic space for embeddings, rendering them impractical. In this
work, we introduce a parameterized version of relational GNNs. When $t$ is
infinity, R-GNN[$t$] approximates $3$-GNNs using only quadratic space for
embeddings. For lower values of $t$, such as $t=1$ and $t=2$, R-GNN[$t$]
achieves a weaker approximation by exchanging fewer messages, yet
interestingly, often yield the $C_3$ features required in several planning
domains. Furthermore, the new R-GNN[$t$] architecture is the original R-GNN
architecture with a suitable transformation applied to the input states only.
Experimental results illustrate the clear performance gains of R-GNN[$1$] and
R-GNN[$2$] over plain R-GNNs, and also over edge transformers that also
approximate $3$-GNNs.
