Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposed using tensor operator, i.e. einsum, to perform mean field inference in MLN. Author demonstrated that each iteration of the MF message passing can be efficiently computed using a sequence of einsum operation. This not only enables one to perform approximate inference in MLN, the inference procedure can easily implemented as neural layers to perform neural-symbolic learning. In particular, author demonstrated that it achieves good results on relational prediction tasks when combining a neural predictor and a MLN regularizer. 
strength_and_weaknesses: Strength:
1. It is likely the first work that applies mean field on MLNs. The reduction of the mean field procedure using einsum makes the procedure easy to be implemented and accelerated. 
2. Author shows good result of using MLNs as a regularizer for learning a model in relational application, e.g. UW-CSE and Cora.

Cons:
1. The notation introduced in the paper is a little bit dense, e.g. variables with many super scripts and lower scripts. It was challenging for the reviewer to go through the equations within few passes. One unsolicited suggestion is to remove some of the super script when the context is clear. E.g. In Theorem 4.3, the super script on the n might be known from the context and can be dropped. Alternatively, adding more examples on how each equation is computed might also help. 
clarity,_quality,_novelty_and_reproducibility: The clarity of the paper is good, although the notations are quite dense. 

The idea of performing mean field inference on MLN using einsum is interesting and author further demonstrated its applications in various 
prediction tasks. 

On the reproducibility, author explained well on the implementation of LogicMP layer, and they also explain how the LogicMP layer interplay with a neural network backbone for generating predictions in relational problems.

I have two questions/comments:

1. It is known that probabilistic database (PDB) can be converted to a MLN [1]. There is an inference algorithm in PDB that uses relational join and aggregation operator, which is similar to the einsum. The inference algorithm is exact for safe query, and can be an approximation when the query is not safe. Is there any possible connections between the proposed method and PDB inference literature.
[1] https://simons.berkeley.edu/sites/default/files/docs/5662/talk-simons-2016.pdf

2. On the  experiment result shown in Table 2, can author also present the quality of the NN backbone alone without the distillation from the LogicMP? I think this could be a better motivation for neural modelers of applying LogicMP when there are soft logical connections between the outputs.


summary_of_the_review: In general, the paper delivers an interesting approach to perform inference in MLNs, and authors further demonstrated that the inference procedure can be integrated with a neural backbone to perform prediction tasks while leveraging the logical connections between the output.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to improve inference in Markov Logic Networks through the use of deep models. In particular, Mean Field inference is implemented as layers which pass messages to compute summations more efficiently by exploiting logical structure in the MLN.

The time complexity analysis is performed to show that the exponential complexity of a Mean Field iteration is reduced for chain ruled formulas in the MLN. Further by parallelizing, we can achieve far salable computations of the messages in the MF iterations. Einstein summation is used to reduce complexity of enumerating all possible groundings of a first-order formula. It is shown that in some cases, even when the total number of groundings of the formula is large, the complexity of computing messages can be reduced by performing summations using Einsum. 

Experiments are performed with 3 datasets in the MLN literature. Comparisons are with existing MLN-based inference algorithms as well as ExpressGNN which is a GNN-based approach for MLN inference. Results indicate that the proposed approach is accurate and also scale well with increased number of groundings.

strength_and_weaknesses: Strengths
-The use of Mean-Field inference for MLNs through deep model layers seems like a novel contribution to me.
-The complexity analysis is performed rigorously and shows the scalability of the proposed method.
-Experiments show that the proposed method scales well over large number of groundings while also being accurate

Weakness
-One weakness is that the problem of controlling the exponential grounding problem in MLNs has been explored in earlier work. For example, Venugopal et al. (AAAI 2015) model the same problem using a junction tree formulation and use approximate message passing to scale up the computations. In such cases, the complexity is dependent not on the number of groundings but the width of the tree-decomposition. For a chain formula, this width is small but for more densely connected formulas, this is large. Other similar approaches have also been explored. 
Thus, I am not sure how the proposed method compares in terms of significance.

-The experiment baselines particularly for CORA does not seem as strong. Another approach that implements MLNs through deep models (Graph Markov Neural Nets, Qu et al. ICML 2020) seems to show better performance. In general, I feel experiments on just two datasets (since smokers is more of a toy dataset) does not strongly demonstrate the significance of the proposed method.

clarity,_quality,_novelty_and_reproducibility: The paper is mostly well written and has rigorous complexity analysis. The significance of the work could have been demonstrated better wth relation to prior work as well as experiments with more state-of-the-art systems.
summary_of_the_review: The connection of Mean Field iterations and the deep model layers seems nice. Also, parallelizing the computations and demonstrating scalability is a nice contribution since inference in MLNs is known to be hard due to the large number of groundings. However, as I understand it, other approaches have tried to address the grounding problem in MLNs, so maybe the novelty is limited.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new method for inference in MLNs.

strength_and_weaknesses: + Very interesting idea
+ Well written paper
- lack of experimental results

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and it reports a new method to do efficient inference in MLNs
summary_of_the_review: The paper is well written and the claims are supported by theoretical proofs.

It is not clear whether the structure of the MLNs are fixed or learned from scratch. In this case this should be explained in the paper.
In particular, while the part concerning the mean-field approach is very clear and correctly presented, there is a lack of description about the structure learning adopted in the paper. 

Furthermore, more datasets could be used in order to prove the validity of the approach.

Finally, the paper is interesting but could be improved integrating some parts as reported above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes an approximate inference algorithm for Markov Logic networks (MLNs) with disjunctive clauses.  The exponential grounding of the first-order structure is mitigated by leveraging a neural network architecture called LogicMP, which implements an efficient mean field approximation of the true posterior.

strength_and_weaknesses: Pros:
+ MLNs represent a very popular class of relational probabilistic models. 
+ Advances in MLN inference are valuable for a broad audience.

Cons:
- In my opinion, the presentation of the proposed approach should be greatly improved before publication (details in the Clarity section).
clarity,_quality,_novelty_and_reproducibility: I found the paper very hard to read in multiple sections, as well as a number of unsubstantiated claims.

---

    "[...] lifted methods are not only difficult to implement ..."

Why?

    "... but also infeasible when the symmetric structure becomes invalid, e.g., one other model is integrated."

What does 'one other model is integrated' means in this context? Also, there exists work on lifted inference in asymmetric MLNs [2].

---

The role of latent variables in Eq.1 is not clear to me. This is also the first time that I encounter LVs in the context of MLNs. Somewhere in the text it is mentioned that latent variables are used to model unobserved facts, under an open world assumption (OWA). Yet, most works on MLNs use CWA. I feel like the OWA made in this work is crucial for understanding the whole approach, but it is only mentioned in the experiments (Sec. 5.2) and its discussion is deferred to Appendix L.

---

How mean-field variational inference can be used in MLN is also unclear. Adding an example to Section 4 would be beneficial as Fig. 1 is not really informative in this regard.
How is the variational distribution constructed? What parameters are optimized to minimize the KL divergence? 
The work supposedly uses neural networks, but it is not clear how these LogicMP layers are structured or trained. What are the parameters of LogicMP?

---

I also found the use of Einsum optimization quite convoluted.

    "Naturally, we can generate all the propositional groundings in Gf as a set of hyper-edges to perform the aggregation."

Hyper-edges over what? No hyper-graph is mentioned before this sentence.

The abstract claims that "In most practical cases, it can reduce the complexity significantly to polynomial for the formulae in conjunctive normal form (CNF)". 
This is a very strong statement. What 'most cases' means exactly? I couldn't find a formal definition of this set of cases in the text.

---

The experimental section gives some clues on the proposed approach,
but also raises more questions.

    "In general, LogicMP poses no constraints to its applications and can incorporate logic rules for various purposes."

This is a very vague sentence. I thought that LogicMP layers are used to approximate inference in MLNs.

    "Ideally, it can serve as a logic CRF for arbitrary neural networks and be trained end-to-end via maximum likelihood estimation (MLE) as in CRFasRNN (Zheng et al., 2015). However, as the labeled data is rare in our datasets, MLE is prone to overfitting and we turn to semi-supervised learning where rules act as priors to infer the latent variables."

This paragraph is hinting at different applications.

    "We fix the formula weights of 1 [...] for all the experiments."

Why? Shouldn't the weights of the MLN be learned from data? If these weights are fixed, what is optimized during the training?

    "Note that LogicMP can perform full graph computation efficiently, but the practical results indicate that training with sampling is more stable for the learning of logical knowledge for the backbone model."

What does 'full graph computation' mean? What is the 'backbone model'? The notion was never mentioned before.

---

Notes:

Hinge-Loss Markov Random Fields (HL-MRFs) is not an inference technique for MLNs, but a different (albeit similar) probabilistic model. See Section 4.2 in [1].

References:

[1] Bach, Stephen H., et al. "Hinge-loss markov random fields and
probabilistic soft logic." (2017).

[2] Van den Broeck, Guy, and Mathias Niepert. "Lifted probabilistic
inference for asymmetric graphical models." AAAI, 2015.

summary_of_the_review: The problem considered in this work is relevant, but I had an hard time reading the paper. I fully read the paper multiple times, but there are still important aspects of the proposed approach that I don't understand. I cannot reccomend the current version for publication.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors tackle the problem of performing inference in Markov logic networks (MNLs) and propose to speed up classical mean field (MF) approximations by introducing two observations, the ability to rule-out some groundings while computing messages in MF and the possibility to optimize the summations in the messages by rewriting these summations as a series of matrix multiplications (expressed in einsum notation). At the same time, they propose a neural backbone to be integrated in the inference process, realizing a neuro-symbolic hybrid approach via posterior regularization. This should put the proposed LogicMP on the same ball park of DeepProblog [1].

The reviewers appreciated the direction of the paper and the implementation perspective taken by the authors to speed up the grounding and inference in MLNs. This can have great potential. Several concerns were raised during the reviewing phase, however. These include three major factors: the presentation of the work, the empirical comparison and the theoretical speed up. 

First, the proposed contribution sits in between proposing a neuro-symbolic approach but also a speed-up for classical MLN inference schemes. The way it is presented highlights mostly the second part, relegating the first in the Appendix, where however not enough details are provided. By not properly disentangle the two aspects, it is not clear which contributes most to the results and why people should adopt LogicMP.

In fact, more crucially, the experimental setting mostly concentrates on comparing the downstream task (classification accuracy) of approach on some classical MLN benchmark in a mixed setting that makes it somehow hard to clearly focus on evaluating the contribution along the two aforementioned dimensions: how good/relevant is the speed up w.r.t. other approximate MLN inference schemes and how does it compare against other neuro-symbolic reasoners (e.g., DeepProblog).
Specifically, the authors compare the gains in time only in Fig 6 measuring AUC-PR/minutes and number of groundings/seconds. But they do so on a subset of the datasets and not report raw times. It is important also to compare the optimized einsum selection w.r.t. a normal einsum operation. Furthermore, it is not clear if competitors can parallelize over the GPU as well.
Regarding competitors, the only neuro-symbolic competitor seems ExpressGNN, but it is orders of magnitude slower by design.
  
Lastly, the computational complexity gains are written in a misleading way. The first speed up from discarding non-relevant grounding looks sound but not surprising. Concerning the "einsum trick", The gain, as presented, seem to go from exponential to polynomial, but we should remark that operating in einsum notation cannot lower the computational complexity of an operation per se, but at most speed it up by not materializing in memory some intermediate products. Furthermore their exponential complexity is quite an extreme worst case bound that considers the most naive way to perform matrix (or tensor) multiplications. The gain in complexity that the authors highlight is due from using an optimized scheduler that breaks a chain of matrix multiplications into intermediate steps as to bound the complexity of each step to be worst-case cubic. Note that this can always be done, at the cost of finding the optimal breakdown. The cost of this optimization step is not discuss and does not seem to be easily bound. Worst-case, the optimizer might return the unoptimized chain of multiplications. This is why it is important to measure how a call to an unoptimized einsum operation can perform w.r.t. the optimized variant.

During the rebuttal, the authors tried to address all concerns and greatly improved the current status of the paper. Reviewers appreciated the effort. However, the discussion post rebuttal highlighted that some core concerns are still not properly addressed and opened up other perspective (discussed above) where the paper contribution is not clearly disentangled and properly evaluated. The paper would greatly benefit from incorporating the following suggestions
- Rewriting the presentation as positioning the paper in the broader neuro-symbolic literature and discussing why competitors such as 
- Benchmarking inference quality (in terms of distance from true marginals/conditionals/likelihood) against approximate MLN schemes, after fixing the same MLN and weights and removing the neural backbone in LogicMP
- Compare against Lifted inference in MLN (it is not clear if BP/LiftedBP is the best of both or one of the two)
- Time comparison in seconds of the different ablation tests and approximate inference competitors on synthetic and real-world datasets while using the same CPU (or GPU) setting for all competitors.

The paper is rejected.
 
[1] - Manhaeve, Robin, et al. "Deepproblog: Neural probabilistic logic programming." Advances in Neural Information Processing Systems 31 (2018).
justification_for_why_not_higher_score: We debated about the possibility of acceptance and we agreed that the current state of the paper would need some non-trivial reworking and some more experiments.
Decision: Reject