- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes Neural Description Logic Machines (NDLMs), an architecture for predicate learning and its applications to planning. It represents relational structures with unary and binary predicates. Fixed operations, including role composition and quantification, generate intermediate logical features, which are then combined by learnable feed-forward networks. The main idea is to support reasoning with three logical variables without explicitly storing ternary predicate tensors, yielding quadratic activation memory in the number of objects. The paper analyzes NDLM’s expressivity with respect to a three-variable fragment of first-order logic and evaluates it on graph classification, action-model learning, and general-policy learning. The performances are comparable on several planning tasks and show generalization across instance sizes, but NDLM does not consistently outperform existing methods on graph classification and concept learning.
Critical strengths
- NDLM uses fixed relational operations to construct logical features and FFNs to learn their combinations. This approach has a clear logical motivation and an accompanying expressivity analysis.
- NDLM performs well in action-model learning and demonstrates generalization across instance sizes. Its quadratic activation memory is a practical advantage over NLMs that explicitly maintain ternary tensors.
Critical weaknesses
- Some key notations lack references, such as the interpretation and closed-world assumptions, etc.
- The Application in Planning section can be merged with Related Work or Experiment.
- The distinct contribution over prior work remains unclear. Methods such as PPGN also enable 3-wl expressiveness relational reasoning with quadratic space complexity. The additional benefits of NDLM’s logic-informed structure need to be explained more clearly.
- The expressivity is still limited to a three-variable fragment of first-order logic with predicates of arity at most two.
Questions for authors
- Section 6 assumes that pointwise FFNs can implement the required Boolean functions exactly, whereas the experiments use relatively simple single-layer FFNs. Could the authors clarify the relationship between the theory and the implemented configuration, especially any requirements on activation functions, width, and depth?
- Since PPGN and related methods also support higher-order relational reasoning with quadratic storage, could the authors clarify NDLM’s distinctive inductive bias and the settings in which it is beneficial? More direct comparisons of performance, memory, and runtime would help assess the significance of the contribution.
- Moreover, can the authors compare the results with Relational Networks [1] and Slot Attention [2] encoders? Besides, can the authors explain the difference in expressiveness of the proposed methods with the above two models?
- Some general-policy experiments use an additional transitive-closure module. Could the authors distinguish the capabilities of the base NDLM from the extended version and explain how transitive closure affects computational cost and the reported results?
Reference: [1] Santoro A, Raposo D, Barrett DG, Malinowski M, Pascanu R, Battaglia P, Lillicrap T. A simple neural network module for relational reasoning. Advances in neural information processing systems. 2017;30. [2] Locatello F, Weissenborn D, Unterthiner T, Mahendran A, Heigold G, Uszkoreit J, Dosovitskiy A, Kipf T. Object-centric learning with slot attention. Advances in neural information processing systems. 2020;33:11525-38.
Thank you for your constructive feedback. The restriction to predicates of arity at most two allows the architecture to use quadratic memory, and the limited expressivity of FO3 helps the network generalize to instance sizes not seen during training (see our answer to Q2). We added the references for the notation (Section 2), an explanation of how the expressivity result relates to the implemented FFNs (Appendix E.2), controlled comparisons with PPGN (Appendix C), resource comparisons (Appendix B.4.1 and B.5.1), and Relation Networks as a baseline (Tables 2 and 3). Below, we describe these additions and address your questions.
Q1
Thank you for raising this point. We added an appendix subsection (Appendix E.2) explaining how the exact Boolean-FFN assumption simplifies the analysis and how the construction transfers to our single-layer FFNs. Sigmoid FFNs can approximate elementary Boolean connectives arbitrarily closely. Pairwise multiplications can increase approximation errors, while min/max aggregations do not amplify them; suitably parameterized sigmoid gates restore the chosen error bound after each layer. Thus, every fixed formula can be approximated arbitrarily closely. Identity FFNs, together with the nonlinear Stage 1 operators, realize Boolean operations exactly on domains with at least two objects. These constructions require channels for intermediate predicates and may add layers, so the precise depth bound remains specific to the idealized assumption.
Q2
NDLMs aggregate with min and max instead of sums, so they cannot count. This is the inductive bias that distinguishes them from PPGNs, and it is beneficial when the target must generalize to larger instances, as in planning (see our answer to Q4 of Reviewer yH7B for details).
We also added direct comparisons with PPGN. When only irrelevant objects are added at test time (Appendix C.1), PPGN drops to 75% accuracy while NDLM stays at 100%. PPGN also fails to generalize to larger instances on most planning tasks that NDLM solves (Tables 2 and 3), and for some domains even fails to fit the training data. Parameters, epoch times, and peak memory are reported in Appendix B.4.1 and B.5.1.
Q3
We have added Relation Networks as baselines for both action-model and general-policy learning, adapting our inputs to their expected data format while preserving the supplied unary and binary predicates. In action-model learning, they achieved perfect training and test predictions in only 1/10 runs for Blocksworld preconditions and 1/10 runs for Blocksworld effects, and in 0/10 runs for all other domain–task combinations. In general-policy learning, they solved 12.8 ± 0.6/13 training problems in Gripper but only 1.0 ± 1.0/18 test problems, indicating poor generalization to larger instances. In Logistics, they struggled even on the training instances, solving only 0.3 ± 0.5/24 training problems and 0/20 test problems.
Slot Attention learns object representations from input features. This does not exactly fit our predicate learning setup, where the task is to infer additional, potentially more complex, predicates from given predicates. We therefore view it as a potentially complementary representation-learning component, particularly for perceptual inputs.
To the best of our knowledge, neither Relation Networks nor Slot Attention has an exact characterization in terms of a logical language comparable to our characterization of NDLMs in FO≤23.
Q4
Adding transitive closure to the architecture increases the runtime to O(n4). Without the transitive closure it would not be possible to solve Blocksworld, Miconic, and Navigation-xy with the architecture in a generalizing way. In Blocksworld for example, to free a block x that lies under a tower, the policy must unstack the top block of that tower, i.e., the clear block above x. “Above” is the transitive closure of on. Without TC, a network of depth k can only find this block in towers up to a fixed height (roughly 2k, see Appendix B.7). With TC, it finds it in towers of any height.