Extracting Symbolic General Policies from Boolean Relational GNNs

Relational graph neural networks (R-GNNs) learn policies for classical planning that generalize to much larger instances than those seen in training, but the policies are opaque, and it is unclear why they generalize so well. We shed light on this question by extracting symbolic policies from R-GNNs with max aggregation and binary object embeddings. We show that every layer of such a network can be described in description logic: the update of each object's embedding is a Boolean function of a finite set of $\mathcal{A}\mathcal{LC}\mathcal{I}$ features derived from the network itself. Decoding a layer thus reduces to finding, for each embedding vector, a minimal DNF over these features, which we solve exactly with SAT and MaxSAT. The resulting concepts are consistent with the network on all sampled training states by construction, and provably minimal whenever the search finishes within its budget. Rules over changes in concept counts then replace the readout, separating the transitions the network considers good from the others. We further prove that instances up to some fixed size already contain every computation the network performs on an object of any instance, however large, with explicit bounds for Gripper and Ferry. Across 12 domains, the symbolic policies solve 94.6% of the test instances, on par with the 93.6% of the R-GNN policies, and remain optimal wherever the R-GNN policy is. Our concepts are $4.4\times$ smaller than those of a greedy decision-tree decoder, and in some cases the policies are readable and provably optimal on every instance. The results illustrate that R-GNNs generalize across planning instances because, regardless of the number of objects, they map objects into finitely many classes characterized by logical concepts that support general policies.