Convex and Bilevel Optimization for Neuro-Symbolic Inference and Learning

Thank you for your time. We are happy to learn you found the paper to be structured, motivated, and important to the research community. We have itemized responses to your comments and questions below:

• Regarding the parallelization strategies for our D-BCD inference algorithm, we would like to emphasize that connected components (CC) and lock-free (LF) D-BCD algorithms should be applied in different settings. Specifically, the CC parallelization strategy should be used when there are many independent groups of variables, i.e., many connected components of the factor graph defining the inference problem. For instance, in the MNIST-Add problem, each addition example, i.e., a set of images defining an addition, creates an independent set of variables contained in a single connected component of the inference factor graph. On the other hand, LF should be applied when the factor graph is large but connected. This is the case in the citation networks like Citeseer and Cora. Furthermore, we are happy that D-BCD often outperforms ADMM in a single round of inference, as shown in Table 2, however, we feel its real strength is shown when it is applied to learning where inference is repeated, and it can leverage warm-starts, as demonstrated in Table 3.
• In response to the comment on the experiments' baselines, we emphasize that ADMM is the state-of-the-art inference algorithm for NeuPSL. Furthermore, we have included alternative inference baselines in the extended inference runtime experiments in E.4 of the appendix. Moreover, Dual-BCD is the first inference algorithm developed for the dual LCQP formulation of NeuPSL inference presented in this work, i.e., the first algorithm to produce optimal dual variables that can be used to produce both optimal primal variables and principled learning gradients. For baselines in performance experiments, we want to underscore the primary contribution of the paper is the learning algorithm rather than the NeSy framework of NeuPSL, i.e., we are comparing our method to the incumbent training algorithm that can only minimize value-based losses. We have included other NeSy frameworks in the four datasets of Tables 5 and 6 as reference points.
• Q1) The LF-BCD algorithm does poorly on the MNIST-Addition problem because, in this setting, the likelihood of multiple processes simultaneously updating overlapping sets of variables is high. This is because the total size of the factor graph is relatively small and made up of tightly connected components. For this reason, the LF-BCD algorithm takes longer to converge. The CC-BCD algorithm, in this case, is effective as processes work on the many disjoint groups of variables in parallel. We expect the LF-BCD performance would improve if the total size of the factor graph increased, i.e., if there were more MNIST-Addition examples.
• Q2) The value-function is parameterized, and the goal is to learn parameter settings from data. The energy function defining the value-function integrates neural and symbolic models. The high-level architecture (the neural layers and the symbolic structure) is designed by a human using a framework like NeuPSL.

Thank you for your thorough review. We are excited to see such an accurate summary, and we feel the actionable suggestions you gave for improving the paper's clarity have improved our submission. We have itemized responses to your comments and questions below:

• We have revisited and improved the exposition of the NeSy learning algorithm in section 4. Specifically, we have substituted the proximal operator with its definition, clarified function dependencies, and emphasized the connection between the original optimization problem of inference and the Moreau envelope in section 5. Moreover, we have added a brief description of how the dual/penalty variables are updated, and we point the reader to the appendix for more details.
• The pseudo-inverse of the constraint matrix is unnecessary for learning as long as an inference algorithm solving the LCQP dual is used to obtain optimal dual variables. Hence, the development of the dual block coordinate descent algorithm.
• Q1) Algorithm 1 does require computing both the value-function and the Moreau envelope of the energy function. For NeuPSL, the energy function, and thus the value-function, is regularized and its minimizer is found using the dual BCD algorithm. As previously mentioned, we have added a description of the connection between the original optimization problem of NeuPSL inference and the Moreau envelope in section 5.
• Q2) The mapping of primal to dual variables is not necessary as long as one solves the dual LCQP formulation of inference to obtain optimal dual variables needed for learning gradients. For this reason, the pseudo inverse of the constraint matrix does not need to be computed when the dual BCD algorithm is used. We have added a discussion motivating and clarifying this point in Section 5.3.
• Q3) We are unaware of previous work using Moreau envelopes to smooth energy functions to support gradient-based parameter learning. We have emphasized this novelty in the introduction.
• Q4) What we meant by the statement you referred to is that the dual BCD algorithm developed for the regularized LCQP formulation produces the optimal dual variables that are necessary for computing principled sub-gradients that can be used for learning. Previous inference algorithms developed for NeuPSL have only operated on the non-smooth primal formulation in equation 17 of the appendix. We edited this statement to be more direct and clear and added the original primal inference formulation back to the main body of the paper to clarify the contribution.

Thank you for your thoughtful review. We appreciate the effort you took to carefully read and grasp the paper. We want to acknowledge the fact that although you claim this research is far from your expertise, your summary is accurate and your reviews are valuable and show you understood our motivations and methods. We have responded to each of your comments and questions below:

• We have added to the structure and discussion in our related work (Section 2). Specifically, we have expanded on the definition and comparison between implicit differentiation and value-function approaches to bilevel optimization.
• We have consolidated and simplified the statements of theorems 5.1 and 5.2.
• The prediction performance results presented in our empirical evaluation, Section 6, improve upon the performance of NeuPSL models presented in published research. Please see Appendix E.1 for details on the NeuPSL models. Moreover, we have included prominent alternative NeSy baselines for the Citeseer, Cora, and MNIST experiments in Tables 5 and 6. This gives a relative point for comparison of the performance of NeuPSL.
• Q1) An implicit differentiation approach derives an analytic expression for the gradient of the upper-level objective using implicit differentiation. The resulting gradient requires second-order derivatives of the lower-level objective function and constraints (if they are supported) at the lower-level minimizer. On the other hand, value-function approaches reformulate the bilevel problem as a single-level constrained program to derive gradient-based methods that only require a gradient of the optimal value of the lower-level objective function.
• Q2) The constraint in 7 can correctly be either an inequality or equality. We intended it to be an inequality as that is becoming a standard in value-function formulations. We updated the text to match the mathematical formulation.
• Q3) We would be happy to add additional metrics to our evaluation that you feel would better represent the performance than the ones mentioned in Table 1. However, we are unsure what types of evaluation you are referring to. We included additional NeSy methods as reference points for the four datasets in Tables 5 and 6, and we want to reiterate that the results in Table 4 improve upon the performance of NeuPSL models presented in published research.

Thank you for your review. Below is an itemized response to comments and questions:

• We have expanded our related work section, and included in this change is the addition of a subset of the NeSy papers you have cited. However, many of these new citations belong to a subgroup of NeSy systems that enforces constraints on the structure of the symbolic model to ensure the final prediction has an explicit expression for its gradient with respect to the model parameters. In this work, we focus on the general setting where inference is an expressive and complex optimization problem, i.e., an explicit form of the gradient of the prediction, i.e., the problem solution, with respect to the model parameters does not exist or is impractical to compute. Going into detail on a tangential research direction under the large umbrella of NeSy is distracting for the reader and we maintained the focus on systems in the more general category and on bilevel optimization.
• Regarding the comment on “toy datasets,” the MNIST-Addition dataset has become a canonical task in the NeSy community. We and other researchers have found it useful for developing and evaluating our methods. As you suggested, using entities other than digits is undoubtedly a valid possible experimental setting, and we encourage its exploration. However, we feel the seven real-world datasets, together with the two MNIST Addition settings, form an extensive empirical evaluation.
• Q1) You are absolutely correct that a line of NeSy approaches making predictions with an explicit gradient with respect to the neural and symbolic parameters exists. This research has undoubtedly made significant strides in creating efficient and end-to-end differentiable NeSy models. However, an emerging and, in our opinion, more advanced line of NeSy research exists where predictions are solutions to complex optimization problems [1,2,3,4,5,6,7,8]. For these models, predictions are not guaranteed to have an analytic map from the inputs and parameters or even be differentiable, and traditional deep-learning techniques are not directly applicable. For instance, you cited NeuPSL as an end-to-end trainable model via backpropagation. While it is true the gradient of the neural parameters is computed using the backpropagation algorithm, the gradient propagated in the original NeuPSL publication [1] is not from a supervised loss and is not with respect to the final NeuPSL prediction. Rather the gradient is for a value-based loss. Moreover, our paper is the first to formally show the value-function of NeuPSL is sub-differentiable (Theorem 5.3) with respect to the neural network predictions. Previous research, including [1], assumed this was the case without formal proof.
• Q2) NeSy-EBMs are highly expressive and are used to perform large-scale joint reasoning with loopy dependencies and to ensure the satisfaction of constraints during both learning and inference. Moreover, NeSy-EBMs often do perform exact inference, contrary to your implication, and exploring this direction of research is valuable to the community.
• Q3) Variations in performance between models in the MNIST-Addition tasks are a result of several differences. In the MNIST problem, NeuPSL inference is solved to an exact solution during both learning and final evaluation. Furthermore, the BCE loss used to train NeuPSL includes both a minimizer and a value-based loss, which can lead to data efficiency and good generalization. Lastly, we used the neural model architectures provided in the original publications for LTNs and DeepProblog, and naturally, there are variations in the implementations.

References:

1. Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Yang Wang, and Lise Getoor. Neupsl: Neural probabilistic soft logic. In IJCAI, 2023.
2. Sridhar Dasarth, Sai Akhil Puranam, Karmvir Aingh Phogat, Sunil Reddy Tiyyagura, and Nigel Duffy. Deeppsl: End-to-end perception and reasoning. In IJCAI, 2023.
3. Giuseppe Marra, Michelangelo Diligenti, Francesco Gianini, Marco Gori, and Marco Maggini. Relational Neural Machines. In ECAI, 2020.
4. Samy Badreddine, Artur d’Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. AI, 303(4):103649, 2022.
5. Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging Deep Learning and Logical Reasoning Using a Differentiable Satisfiability Solver. In ICML, 2019.
6. Brandom Amos and J. Zico Kolter. OptNet: Differentiable Optimization as a Layer in Neural Networks. In ICML, 2017.
7. Paolo Dragone, Stefano Teso, and Andrea Passerini. Neuro-Symbolic Constraint Programming for Structured Prediction. In NeSy, 2021.
8. Cristina Cornelio, Jan Stuehmer, Shell Xu Hu, and Timothy Hospedales. Learning Where and When to Reason In Neuro-Symbolic Inference. In ICLR, 2023.

Thanks your response.

• I'm sorry, but i'm not really sure I'm convinced by your reasoning for omit this line of work from your related works, especially in light of using the MNIST-Addition dataset and comparing against DeepProbLog, DeepStochLog and NeuPSL which belong to that very same line of work.

• I'm not sure what the authors mean by "enforces constraints on the structure of the symbolic model to ensure the final prediction has an explicit expression for its gradient with respect to the model parameters", but again all these works enforce logical constraints on the output of the neural network.

• I don't oppose the use of MNIST-Addition, rather the specific variant being used where the sum of only two digits are considered. In all the neuro-symbolic approaches that i'm aware of, the innovation comes in the probabilistic inference occurring on top of the neural networks classifier. We are already able to perform exact inference in the task of MNIST-Addition using 2 digits, which is why most recent approach have ramped up the difficulty of the task by considering more than 2 digits as it is in that regime that the exact inference approaches such as deepproblog struggle.

• "more advanced line of NeSy research exists" I'm not sure I understand, or agree with such a sentiment; the SAT solver used in SATNET and OPTNet is pretty much the same machinery that powers deepproblog, semantic loss as well as many of the other publications I have cited. NeuPSL and DeepPSL and Logic tensor networks are all relaxations of semantic loss (cited above) using fuzzy logic.

• "For instance, you cited NeuPSL as an end-to-end trainable model via backpropagation. While it is true the gradient of the neural parameters is computed using the backpropagation algorithm, the gradient propagated in the original NeuPSL publication [1] is not from a supervised loss and is not with respect to the final NeuPSL prediction" I agree that the gradient does not derive from labeled data, rather from minimizing the (relaxed) probability of a logical constraint (using fuzzylogic) w.r.t the network's output distribution.

• Q2) I don't doubt that EBMs are highly expressive, it's not clear to me how one can reason tractably and exactly under such models, let alone condition the distribution on constraints?

• Q3) I'm still not clear on how, under the same setting, NeuPSL which minimizes a relaxation of the original problem (Section B in the appendix of the Neupsl paper states: "NeuPSL operates on real-valued logic, which improves scalability but is a relaxation of the original problem"), can outperform an exact minimizer i.e. deepproblog