2024/03/18 by Simon Ståhlberg, Ståhlberg, Simon, Blai Bonet +3 · 2 citations
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2403.11734
openalex publication_date 2024/03/18 · openalex created_date 2024/03/20 · openalex updated_date 2026/08/02
GNN-based approaches for learning general policies across planning domains are limited by the expressive power of C2, namely; first-order logic with two variables and counting. This limitation can be overcame 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 C3, unlike 1- and 2-GNNs that are confined to C2, they require quartic time for message exchange and cubic space to store embeddings, rendering them infeasible in practice. In this work, we introduce a parameterized version R-GNN[t] (with parameter t) of Relational GNNs. Unlike GNNs, that are designed to perform computation on graphs, Relational GNNs are designed to do computation on relational structures. When t=∞, R-GNN[t] approximates 3-GNNs over graphs, but 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 expressivity 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 inputs only. Experimental results illustrate the clear performance gains of R-GNN[1] over the plain R-GNNs, and also over Edge Transformers that also approximate 3-GNNs.