acceptodds
Under review as a conference paper at ICLR 2027

Extracting Symbolic General Policies from Boolean Relational GNNs

Abstract

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 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 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.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
generalized planning, classical planning, graph neural networks, description logics, interpretability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6F3rOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors begin with an R-GNN trained on classical planning problem instances, keeping the planning domain fixed throughout training. They then derive concepts in the sense of ALCI\mathcal{ALCI}. These concepts are constructed for every vector xx observed at a network layer during training and are true of the objects that produce that embedding at that layer for a given problem instance.

The authors show that these are genuine concepts in the ALCI\mathcal{ALCI} sense. They construct the concepts recursively across network layers and use a classifier on top of them to perform the task of the original network. The authors also show that finite training sets exist such that the concepts observed in those sets capture all possible concepts the network can produce, even when the number of objects grows without bound in non-training instances

Critical strengths

The methods and rigor are sound. This paper includes substantive mathematical proofs, resulting in a high standard of rigor and clarity. The presentation is good, considering the page limitations. I particularly appreciate the Limits section in lines 309–314, where the authors explicitly state that having twins is sufficient because the number of copies of the same message does not matter for a max aggregator.

The construction of the concepts is also explained very clearly.

It is interesting that the classifier gg, operating on top of the concepts constructed by the authors, performs better than the trained R-GNN. However, the authors must first train an R-GNN to derive these concepts.

Critical weaknesses

** The authors state that Theorem 2 explains why R-GNNs can learn from small problems and generalize well to large instances. I do not think this is what Theorem 2 establishes. The theorem states that the architecture of an R-GNN is such that, for a fixed LL, there is no real benefit from increasing the number of objects beyond a value represented in the training set. A substantive result (In My opinion) in this direction would show, for example, that the architecture learns the action schemas of the domain and how to use them from small instances, and therefore does not require training instances with a larger number of objects.

** Table 1: The authors state that their concepts are smaller, but is the number of concepts large? My understanding is that the authors construct a concept for each embedding observed during training, so mm in Section 4.3 could be very large. To complete Table 1, the authors should provide the number of concepts used by IDT, lay, flat, and Ours.

** This appears to be very strong technical work, rather than work that asks a highly novel question or resolves a question that has remained open for a long time. Therefore, I think the potential impact is relatively narrow.

Questions for authors
  1. Could the authors explain more of the ALCI notation in the supplementary material? What are the legal concepts in this formalization? Lines 113–124 address this, but only briefly. A more detailed explanation in the appendix would be helpful.

  2. In Equation (4), do the authors also need to include the inverses of rr for Theorem 1 to hold? Equation (1) seems to imply that there are messages for every binary predicate, but not a separate message for its inverse.

  3. The authors need to evaluate the trained network to evaluate the terms and find the prime implicants that lead to the construction of the target concepts?

  4. Theorem 2 and the part of the paper concerning concept extraction seem somewhat unrelated, except that Theorem 2 appears to guarantee that concepts can be learned from examples with a small/finite number of objects without encountering embeddings in unboundedly larger test instances that lead to previously undiscovered concepts. Am I mising something here?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 6F3r

We thank the reviewer for the careful review and for the kind words on the proofs and the Limits paragraph.

Theorem 2 and generalization. See the general response regarding Theorem 2. A result like the one you describe is beyond this paper, and for our networks it would not concern action schemas: they are transition classifiers that score pairs (s, s′), so they learn which state changes lead to the goal. The decoded policies have the form of the rule-based general policies of prior work (Francès et al., 2021), with conditions on how concept counts change. The closest we come to such a result is for one domain: the policy decoded from small Gripper instances is provably optimal on Gripper instances of every size (Theorem 4).

Number of concepts (Table 1). Your understanding is correct: we decode one concept per embedding vector observed on sampled training states. Since all methods decode the same network, they decode the same embedding vectors: 383 over the 12 domains and both layers, from 5 (satellite) to 73 (depots). The exception is flat ALCSAT, which decodes only the 259 last-layer vectors. The policies read fewer concepts than this. We will add these counts to Table 1.

Novelty. The work addresses an open question in generalized planning. Symbolic general policies are usually rules over description-logic features, and prior work on R-GNN policies studied their expressivity, i.e., what they can learn. To our knowledge, this is the first work to decode what trained R-GNN policies actually learn, and to show that it has the structure of those symbolic policies. Exact decoding makes a trained network something one can inspect and prove correct, as for Gripper, and the decoder applies to any GNN of this form over unary and binary relations.

Q1: Could the authors explain more of the ALCI notation in the supplementary material? What are the legal concepts in this formalization? Lines 113–124 address this, but only briefly. A more detailed explanation in the appendix would be helpful.

A: ALCI extends ALC with inverse roles. Atomic concepts are the unary predicates and roles are the binary predicates p and their inverses p⁻; concepts are C ::= A | ⊤ | ⊥ | ¬C | C ⊓ C | C ⊔ C | ∃r.C | ∀r.C. We will add an appendix with the full syntax and semantics.

Q2: In Equation (4), do the authors also need to include the inverses of R for Theorem 1 to hold? Equation (1) seems to imply that there are messages for every binary predicate, but not a separate message for its inverse.

A: Yes, and Eq. (4) includes them: R is defined just before it as the binary predicates and their inverses. Eq. (1) has no separate MLP for the inverse, but MLP_p outputs one message per argument: for on(a, b), a’s message depends on b’s embedding, so a is described by ∃on.C_x, and b’s message depends on a’s, so b is described by ∃on⁻.C_x. The proof of Theorem 1 needs both directions.

Q3: The authors need to evaluate the trained network to evaluate the terms and find the prime implicants that lead to the construction of the target concepts?

A: Yes, since we decode what the trained network has learned. We run it once on the sampled states to get each object’s embedding at each layer. The form of the pool in Eq. (4) is fixed by the architecture, but its features C_x are the embeddings of the previous layer. Evaluating the features on the same states gives the table of (feature vector, embedding) pairs, and prime implicants and MaxSAT work on this table alone, never on the weights. The network also labels which transitions it would take, to which the readout is fitted.

Q4: Theorem 2 and the part of the paper concerning concept extraction seem somewhat unrelated, except that Theorem 2 appears to guarantee that concepts can be learned from examples with a small/finite number of objects without encountering embeddings in unboundedly larger test instances that lead to previously undiscovered concepts. Am I mising something here?

A: No, that is exactly its role. We decode one concept per embedding vector from small instances. Without a bound, larger instances could always produce embeddings with no concept. Theorem 2 shows that all states of all instances up to some size N contain every embedding, so decoding there misses none. It does not say how large N is or that random sampling finds such a set; Theorem 3 gives N for Gripper and Ferry, and empirically no test instance produced an unseen embedding (App. C.4).

'The policies read fewer concepts than this. We will add these counts to Table 1.' -- please add this number to the table before end of review period

AuthorsOpenReview ↗

Response to Reviewer 6F3r

A new revision is submitted with the number of concepts added to Table 1. The changes are marked with a blue font color, to make it easier to see the changes. We will update the text with the promised changes for the camera-ready version of the paper.

I am satisfied with the authors' responses and thank them for their clarifications. In particular, the additional columns in Table 1 helped improve my understanding of the results.

The main results rely on specific properties of the max aggregator, which the authors, to their credit, explicitly acknowledge. I therefore believe that the results shed light on the "magic sauce" behind RGNNs in planning problems, but only to a relatively narrow extent.

Consequently, I will retain my current score, due to my concerns about the scope of the results.

Reviewer_TPdAOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper takes the planning "R-GNN" (~Stahlberg et al.), binarizes its object embeddings, and uses max aggregation. Every layer is then a Boolean function of a finite set of ALCI features read off the previous layer, so the embeddings can get decoded into DL concepts by exact DNF minimization. The readout is replaced by a decision tree over signs of changes in the concept counts. On 12 domains with single-atom (!) goals, the symbolic policies solve about as many test instances as the network, and the gripper policy is shown to be optimal.

Overall, describing GNNs in DL is an interesting direction and the paper has a clear idea behind it (which I appreciate). Though my impression is that the network was designed as an interpretability toy (binary + max agg, 2 layers, single-atom goals) and the paper then acts like it’s a miracle that it can be explained with binary logic, when it was designed exactly for that... What this restriction costs against the real-valued R-GNN isn’t measured, and "R-GNNs generalize because they learn logical features" is a lot more generic than what was actually shown, I think...

Critical strengths
  1. The feature pool is read off the network instead of being searched for (Thm 1), and the decoding is then exact - consistent by construction and, for the 73% of concepts where the enumeration finishes, certified minimal. That’s a real step beyond approximate post-hoc explainers, and quite interesting to the planning audience, I think.
  2. The paper is honest about the limits of its own theory (Sec. 5) - the overclaiming sits in the contributions list and the conclusion, so it’s fixable by rewriting.
Critical weaknesses
  1. Primarily, the restricted setup, and its (never measured) cost. GNNs actually classically generalize badly to larger instances, so if they do here, it’s likely some special corner case. And it is, by design: max agg (= no counting inside the encoder) gives finitely many object types, as the paper itself says in Sec. 5, and the finite cover (Thm 2) seems to follow from that alone. The max is inherited from Ståhlberg, but the authors’ own changes are all further restrictions - STE binarization, only 2 layers (the original R-GNNs were much deeper, afaik), and single-atom goals in all 12 domains (one sentence in Sec. 2). The original benchmarks had conjunctive goals afaik - is that perhaps exactly why counting is needed only in the readout here? With all this, the contributions start to sound quite trivial to me (Thm 2 says little more than that a finite complete training set exists, with no bound on N beyond the two worked-out domains). What would make it non-trivial is never measured: what does the restricted network cost against the real-valued R-GNN on the same splits (and how hard are these single-goal instances for a plain planner)? Also, "using only constraints that R-GNNs already have" (Sec. 7) just isn’t true, and insisting on DL rules out arity > 2 (none in these benchmarks, but common elsewhere) when even the DNF machinery wouldn’t care (I think).

  2. The readout isn’t really extracted, and its fidelity is never reported. All the guarantees are about the encoder concepts. The readout tree is fitted as a good/bad classifier on the network’s labels, the policy is a ranking (best successor), and nothing says how often the tree reproduces the network, on the decoding states or on test. Already in gripper the sign patterns can’t separate the 110 optimal from the 540 non-optimal drops that the network does separate (Fig. 1), and the policy seems to be rescued by a priority/fallback semantics that appears only in Sec. 6.3, not in the method (Sec. 4.3). The rules also test only signs of count changes, never the counts themselves (one normally needs both, no?). I guess this is where the plan quality goes - coverage on par (btw. with cycle avoidance and a 1000-step horizon), but much longer plans on blocks-on-table or driverlog, which the abstract’s “on par ... optimal wherever the R-GNN policy is” doesn’t tell.

Questions for authors
  • Primarily, how does the binarized 2-layer network compare to the real-valued R-GNN (and a plain planner) on the same splits? Cost or free lunch?
  • Why single-atom goals? Does the decoding survive conjunctive goals and deeper networks? (seems like L=2 already hits the cap/limit?)
  • Readout fidelity on decoding states and on test -- how are successors ranked, and is the fallback priority gripper-only?
  • How many concepts/rules do the other policies actually read (e.g. depots has 55 layer-2 concepts)? (Still readable?)
  • The 4.4x is against your own greedy baseline/ablation (and ALCSAT is smaller wherever it fits) - perhaps say so in the abstract?

Suggestion: state the single-atom goals and the depth up front (next to max + binary), rescope the "R-GNNs generalize because..." story to what was actually shown, and possibly let the rules test counts as well as signs (as in Bonet & Geffner).

4 comments
AuthorsOpenReview ↗

Response to Reviewer TPdA

We thank the reviewer for their detailed review and constructive feedback to our paper. On the framing (the restricted setting, stating single-atom goals and depth up front, and rescoping “R-GNNs generalize because…”), please see the general response, where we address all three.

Conjunctive goals and counting. Counting is not needed inside the encoder: a conjunctive goal needs the number of unachieved goal atoms, which the readout’s sum provides (in Gripper, the encoder marks each ball not yet in its goal room). Earlier R-GNNs for conjunctive goals also used (smooth) max aggregation (Ståhlberg et al., 2022b).

Theorem 2. Theorem 2 rests on max aggregation, and its role is to justify decoding from bounded instances. Bounds on N are domain-dependent; Theorem 3 gives them for Gripper and Ferry.

“Constraints that R-GNNs already have.” Binary embeddings, L1 regularization and two layers are our design choices on top of the R-GNN, and Section 7 will state them as such. On arity, see the general response.

Signs vs. counts. We saw no clear benefit: with count changes as tree inputs, the symbolic policies solve 1,693 instances (signs: 1,690), and with the counts in both states plus their changes, which allow conditions such as n = 0, they solve 1,586. Signs largely suffice because the policy ranks successors: an effect such as “n decreases” exists only when n > 0, so the leaf ranking acts as a priority list.

Plan quality. This comes from the readout: a tree over signs of count changes is coarser than the network’s MLP, so it sometimes ranks a non-optimal successor first. The revised abstract will say that coverage is similar, sometimes with longer plans (blocks-on, blocks-on-table, depots, driverlog; Table 5). Both policies use the same cycle avoidance and horizon.

Q1: Primarily, how does the binarized 2-layer network compare to the real-valued R-GNN (and a plain planner) on the same splits? Cost or free lunch?

A: Binarization costs little. The real-valued R-GNN solves 1,670 test instances against 1,643, with similar plan quality: on the 1,456 instances all methods solve, the geometric mean of plan length over optimal is 1.19 (real-valued) and 1.22 (binary). It is also decodable, with symbolic policies solving 1,712 (binary: 1,690). Binarization buys interpretability: 259 last-layer embedding vectors instead of 2,999 (real-valued vectors rounded to three decimals), and no unseen vectors at test time (App. C.4), whereas the real-valued network has unseen vectors in childsnack, depots, driverlog and transport. With the same 1 h / 16 GB limits, LAMA solves 1,715 and LM-cut 1,548 (optimal plans).

Q2: Why single-atom goals? Does the decoding survive conjunctive goals and deeper networks? (seems like L=2 already hits the cap/limit?)

A: For goals, see the general response. Networks with 10, 20 and 30 layers solve 1,621, 1,663 and 1,598 instances (2 layers: 1,643). At 10 layers, every decoded concept is consistent with the network in all 12 domains; what grows is the number of concepts: 28–1,218 per domain, against 5–73 at 2 layers. The prime cap affects only minimality certificates, not consistency: it stops enumeration for 27% of the concepts at 2 layers and 77% at 10 layers.

Q3: Readout fidelity on decoding states and on test -- how are successors ranked, and is the fallback priority gripper-only?

A: The readout is fitted to the network’s labels, not decoded, so the exactness guarantees cover the concepts; we will make this explicit. Leaves are ranked by their fraction of good training transitions; the policy picks a successor in the highest-ranked leaf (ties uniformly at random). A fallback is an impure leaf and can occur in any domain; we will define this in Section 4.3. The top-ranked successor agrees with the network’s on 88–100% of decoding states and 61–100% of test states (lowest in driverlog and transport), and 100% in the five domains where both policies are optimal. In Gripper, the 110 optimal and 540 non-optimal drops share the fallback leaf, but it is chosen only when no higher-ranked successor exists, so the policy is still optimal (Theorem 4).

Q4: How many concepts/rules do the other policies actually read (e.g. depots has 55 layer-2 concepts)? (Still readable?)

A: Seven policies read 1–8 last-layer concepts with 2–16 rules (tree leaves), and are readable; blocks-on, childsnack, depots, driverlog and transport read 15–51 concepts with 33–478 rules and are not readable as a whole. We will add a table.

Q5: The 4.4x is against your own greedy baseline/ablation (and ALCSAT is smaller wherever it fits) - perhaps say so in the abstract?

A: IDT is our adaptation of Pluska et al.’s decoder to the same pool, and ALCSAT, not restricted to a DNF, finds shorter concepts but reproduces the network exactly only in ferry, gripper and satellite. We will say so in the abstract.

Thank you for the detailed response and new results -- they answer my questions, I think - i.e, binarization costs little and conjunctive goals work with the same pipeline, so my "interpretability toy" was a bit overstated, fair enough. On the other hand, the new numbers seem to confirm the rest: the readout agreement drops on the harder domains, almost half of the policies isn't readable, and deeper networks blow up the number of concepts. So the readable/certified version comes from shallow networks and the easier domains (say so upfront, as promised). I’d also like the per-domain readout agreement and the readability table (the one reviewer 6F3r also asks for) in the revision itself.

AuthorsOpenReview ↗

Response to Reviewer TPdA

We have submitted an updated version of the paper with the number of concepts added to Table 1 and the readout agreement (Table 10, Appendix C.7). The changes are marked with a blue font color, to make it easier to see the changes. We will add the promised changes to the text in the camera-ready version of the paper.

Thank you, I’ve seen the revision (Tables 1&10) - makes sense. Framing changes in the camera-ready is fine with me, and I intend keep my (good enough) score.

Reviewer_xaJLOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper extracts a symbolic description from an binarized R-GNN trained on classical planning problems to learn a domain-dependent, instance-independent planning policy.

Each R-GNN layer consists of multiple MLPs. Each MLP, one per predicate, receives object embeddings of the arguments in the previous layer and returns messages. The messages a single object received are max-pooled and fed to the MLP, one per object, then activated by the binarizer to generate the next embedding.

Binarization is done by straight-through estimator, rather than with variational distribution (as in Jang et al, 2017), categorical classification via embedding vector (as in VQVAE), or post-hoc quantization as in LLMs.

The network is trained on a pre-generated path in a PDDL problem to classify whether a state transition is on an optimal path or not. I could not find how the state transition training data were generated.

Then each R-GNN layer is approximated by a description logic (DL) representation found by a MaxSAT solver using states sampled from small problem instances. Several other methods for extracting similar symbolic rules were compared against the proposed approach.

They claim that this DL aproximation is accurate and a planner using the DL-based policy perform as well as or slightly better than the original R-GNN policy. They also showed that in some domains, the extracted policy can be proven as optimal, through a domain-specific analysis.

Critical strengths

The approach taken in this paper is sound and natural --- If I try something similar, it would be a similar approach. So this is a solid research.

Critical weaknesses

It seems like DL representation can only accomodate binary predicates and the author explicitly states that all evaluated domains have predicates of arity up to 2.

The paper is not clear about the instance size / benchmark set of the evaluated instances. It appears that several domains maxed out, i.e., R-GNN can solve all instances. This has two issues:

First, the max-out may be hiding the difference, and the claim that the original R-GNN policy and its DL policy have comparable performance may be substantiated. In a larger instances, there would be difference.

Second, the experiemnt only covers the number of solved instances under fixed steps, therefore does not measure the runtime separately. An R-GNN and an efficiently compiled form of description logic rule would have significant low-level performance difference, probably in favor of the DL policies. This difference is not evaluated in this paper. Unless this benefit, the advantage of DL is rather weak; just interpretability and a very marginal performance difference, at least in the current evaluation set that is maxing out.

The evaluated instances have another issue: it says they are restricted to a single goal. This is an unrealistic assumption that deviates from the usual planning benchmarks. This is different from saying that every planning instance can be converted into an instance with a single goal atom by adding a dummy action with the goal condition as the precondition.

Questions for authors

It is unclear if there is similar work on learning and extracting a generalized planning policy and how this work relates to such work. The authors mentioned methods (IDT, ALCSAT, etc) with corresponding previous work that extracts knowledge from R-GNN, but it is not clear if they are targeting generalized planning policy. Is this the first instance of such work?

Is there any way to remove the restriction on the predicate arity?

How are the state transitions for training generated?

2 comments
AuthorsOpenReview ↗

Response to Reviewer xaJL

We thank the reviewer for the detailed comments. One clarification on the summary: the DL policy is not an approximation of the network. On all sampled states, the decoded concepts reproduce its embeddings exactly by construction (Proposition 1 and Table 4).

Runtime. We now measure it, with a vectorized bitset evaluator that replaces the old one and raises the coverage from 1,662 to 1,690. We also timed both policies on the same states, single-threaded on the same CPU. A step of the symbolic policy, evaluating the concepts on all successors and choosing a successor with the rules, takes 5.5 ms at the median against 28 ms for the R-GNN (the paper’s evaluator: 208 ms), and the symbolic policy is faster in all 12 domains. Of the 28 new solves, 16 are in childsnack, all optimal. The only timeouts left are in childsnack, where states have up to 3.7 million successors. We will report runtimes separately for the network and the symbolic policy in the revision.

Single-atom goals. Please see the general response.

Instance sizes and saturated domains. Appendix C.1 (Table 3) gives the instance sizes: training instances have at most 24 objects, validation instances at most 28, and test instances up to 1,461. We agree that coverage near 100% can hide differences between policies. In the five domains where the R-GNN doesn’t solve every test instance, the two policies differ. The symbolic policy solves more instances in blocks-clear (133 vs 117), childsnack (140 vs 124), depots (279 vs 275) and transport (166 vs 150), and fewer in driverlog (75 vs 80). The difference is clearest on the hardest instances. On the 208 test instances that the optimal planner LM-cut cannot solve within the same 1 h limit, the R-GNN solves 142 and the symbolic policy 183. Every one of the 142 is also solved by the symbolic policy. No finite benchmark can show that two policies behave alike on all larger instances; that requires a proof, as we give for Gripper, and we will make this explicit in the paper.

Advantage of the DL policies. Beyond interpretability, the DL policies can be verified, and they solve more test instances than the network (1,690 vs 1,643), though with longer plans in four domains (Table 5). Because the policy is symbolic, we can prove that it is optimal on every Gripper instance (Theorem 4), whereas testing the network shows this only on the test instances.

Q1: It is unclear if there is similar work on learning and extracting a generalized planning policy and how this work relates to such work. The authors mentioned methods (IDT, ALCSAT, etc) with corresponding previous work that extracts knowledge from R-GNN, but it is not clear if they are targeting generalized planning policy. Is this the first instance of such work?

A: Symbolic generalized planning learns policies directly over description-logic features from a grammar-generated pool, without a network (Bonet & Geffner, 2018; Francès et al., 2021; Drexler et al., 2022). Neural approaches learn R-GNN policies (Ståhlberg et al., 2022a,b; 2023), but do not extract them. To our knowledge, we are the first to extract symbolic general policies from trained R-GNN policies. The closest methods are IDT (Pluska et al., 2024), which distills GNNs over a single binary relation into decision trees outside planning, and ALCSAT, which learns DL concepts from examples. We will make this explicit in Section 7.

Q2: Is there any way to remove the restriction on the predicate arity?

A: Yes; please see “Predicates of arity > 2” in the general response.

Q3: How are the state transitions for training generated?

A: We expand the full state spaces of the training instances, which gives the optimal goal distance of every state. During training, each example is drawn by picking a training instance, a goal distance uniformly at random (including dead ends), a state at that distance and one of its applicable actions. The transition is labelled good iff it reduces the optimal goal distance by exactly one, and bad otherwise (including any transition into or out of a dead end). No plans or trajectories are used. We will add this to Section 3.

Reviewer_xaJLOpenReview ↗

thanks

thanks for the reply.

questions re: single-atom goals and re: arity are resolved.

re: dataset preparation, That is quite an expensive pipeline! But I understand that it is not your main contribution, so I wouldn't press it more. One room for improvement I have is that such a dataset would be imbalanced (there would be fewer successors that approach the goal than those that go away from it). Normalizing the pos/neg would make it learn better.

Since I don't have many complaints about it, I consider raising the score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

We thank all reviewers for their careful and constructive reviews. We address the shared concerns here and the individual points in each response.

Note that the numbers for the symbolic policies are updated compared to the paper, as we implemented a faster concept evaluator with which the symbolic policies solve a few more instances.

Goal of the paper. Expressivity results (e.g. Barceló et al., 2020; Grohe, 2021) characterize what R-GNNs can represent. We ask what a trained R-GNN policy actually computes. For R-GNNs with max aggregation and binary embeddings, each embedding must be an ALCI concept and we decode it exactly. The decoded concepts reproduce the network’s embeddings on every sampled state (consistency 1.000). Outperforming the R-GNN is not the goal; what we gain is a policy that can be read and reasoned about. For Gripper we prove that the decoded policy is optimal on every instance (Theorem 4), a proof that testing cannot provide and that would be hard to obtain from the trained network directly. At the same time, we are not just trying to interpret the learned R-GNNs, but explaining them symbolically in terms of concepts, where a proof of optimality is possible.

Single-atom goals. We chose them because our aim is to understand what the network learns, not to compete with state-of-the-art general policies. In many domains, conjunctive goals can be solved by solving each goal atom in any order. The method itself does not depend on single-atom goals. We have trained the R-GNNs on the same domains with conjunctive goals and decoded them with the same pipeline. This gives symbolic policies that solve 1,639 of 1,736 instances with 2–4 goal atoms (R-GNN: 1,590) and 1,418 of 1,568 with 5–10 atoms (R-GNN: 1,306). The price is readability: with conjunctive goals the policies read more concepts and have more rules, so fewer of them are small enough to inspect by hand. We will add these results to the revision.

Predicates of arity > 2. The restriction comes from the description logic ALCI, which has only unary concepts and binary roles; the decoder itself (prime implicants and MaxSAT over Boolean features) does not depend on arity. Higher arities could be handled with a description logic with n-ary relations, such as DLR (Calvanese, De Giacomo & Lenzerini), but this extension would make the interpretation of the decoded concepts harder.

Theorem 2. Theorem 2 implies that larger instances create no new object-level computations of the encoder, which is what makes decoding from small instances possible. We will state this role precisely in the abstract, introduction and conclusion accordingly, and state the setting up front: max aggregation, binary embeddings, L = 2, predicates of arity ≤ 2, single-atom goals.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.