- 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 . These concepts are constructed for every vector 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 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 , 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 , 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 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
-
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.
-
In Equation (4), do the authors also need to include the inverses of 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.
-
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?
-
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
'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
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.
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).