Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposed a simple linear programming model for learning logical rules for KG completion. The model selects candidate rules from KG with explicit constraints and then solves a linear programming problem. The authors conduct experiments on several public datasets and the model has better efficiency than baseline models. 
main_review: Advantages: 
* The problem of learning logical rules is very crucial. 
* The proposed model is very simple and seems to be effective. 
* The efficiency is better than some previous works. 

Disadvantages: 
* The paper is hard to follow, which requires improvements. 
* The motivation of the model is confusing, which seems to have no significant improvement compared to existing works such as Neurallp and DRUM. They reduce the search space by changing the order of summation and multiplication when calculating rules, which can also be regarded as low-rank decomposition of rule-score tensors. 
* In my opinion, the most time-consuming module of Neurallp and DRUM is LSTM. If they directly use the coefficients of relations in the rule as the learnable parameters, it would be much faster and may achieve comparable performance. I am not sure the proposed method is also faster than the simplified version of Neurallp and DRUM. 
* There are several works that the author didn’t compare with, such as [1,2], which can learn more complex rules. 

Minor issues:
I -> i in equation 2.

[1] Yang, Yuan, and Le Song. "Learn to Explain Efficiently via Neural Logic Inductive Learning." International Conference on Learning Representations. 2019.

[2] Teru, Komal, Etienne Denis, and Will Hamilton. "Inductive relation prediction by subgraph reasoning." International Conference on Machine Learning. PMLR, 2020.


summary_of_the_review: In summary, the paper presentation requires improvements and the motivation for designing such a model is not clear. There are several methods that the authors did not use for comparison.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents a method to obtain weights for a knowledge graph scoring model for link prediction. There are numerous good algorithms for mining rules from knowledge graphs (e.g. AnyBURL and AMIE). Less research has focused on the problem of creating scoring functions based on an (implicit) list of rules. This is what the present paper proposes. 

The core idea is to formulate a linear program whose solution corresponds to a scoring method. Instead of incorporating all rules (there are typically many!) into the LP formulation, the authors propose a column generation approach. 


main_review: Generally, the paper is well written, proposes a novel approach to obtain a scoring function given a set of rules and a KG, and has convincing experimental results. 

The only criticism I’d have is some missing related work. The authors cite exhaustively from the literature on knowledge graph embedding methods and rule-based approaches. However, there is a large body of work in the statistical relational learning community, focusing precisely on computing a scoring function (here: marginal probability or MAP state; and/or computing rule weights) in large probabilistic models defined through weighted rules. Below are two representative examples who proposed (among other things) column generation techniques and formulating the problem as an ILP. It’s not an LP but one could relax the ILP. I believe this is work that should be cited as related. In fact, I believe a discussion of these related approaches in the context of SRL might be illuminating and bring SRL researcher to pay attention to the idea proposed here in the context of knowledge graph completion. 

https://arxiv.org/abs/1206.3282

https://arxiv.org/abs/1304.4379
summary_of_the_review: Good paper but some discussion of highly related work is missing
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a simple method to generate logic rules, where rules are generated by a shortest-path heuristic and rule weights by solving a linear program.

main_review: First, the paper does have it's strong points:

S1. Simple, easy to understand approach.

S2. Only requires shortest-path computations, rule evaluation, and an LP solver.

S3. Decent results.

However, in the light of the current state-of-the-art, the paper falls short severely (W1). It's also overly limited in the type of rules that can be generated and how they can be combined (W2).

W1. Does not include SOTA approaches and falls behind in all areas where benefits are claimed: [A] (not cited) proposes a rule learner which (1) has a larger language bias, (2) is orders of magnitude faster than the proposed approach on a less powerful machine, and (3) produces higher-quality predictions, and (4) is simple. E.g., on the largest YAGO3 dataset: paper 21h, .45 MRR, 60 cores; [A] 16min, >=.49 MRR, 4 cores. It's not clear what the benefits of the proposed approach really are, if any.

[A] Christian Meilicke, Melisachew Wudage Chekol, Daniel Ruffinelli and Heiner Stuckenschmidt: Anytime Bottom-Up Rule Learning for Knowledge Graph Completion. IJCAI 2019.

W2. The rule generation heuristics are well-known; there is no novelty here (it's also not claimed). It appears that only chain rules that correspond to shortest path can be learned. The language bias is thus quite limited and does not include other types of rules known to be usefule, most notably, rules involving constants ("X lives in New York" => "X speaks English"). There has been prior research in how rules are combined (e.g., [A] uses the most confident rule); it's not clear whether a linear combination of rules is a good idea in the first place. Here an ablation and comparison to prior approaches is missing. As for pruning negative-weight rules: There isn't much pruning at all: only 50 candidate rules are generated per relation in the first place in the experimental study. These candidates are useful in that they are generated sequentially based on the candidates so far, but this idea is also present in prior work (e.g, RNNLogic, [A]).

summary_of_the_review: In the light of the current state-of-the-art, the paper falls short severely (W1). It's also overly limited in the type of rules that can be generated and how they can be combined (W2).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: To solve the problem that rule-based methods in knowledge graph completion tasks are lack of scalability to large datasets, this manuscript presents a simple linear programming model to choose rules from a list of candidate rules and assign weights accordingly. Some experiments are therefore designed and conducted to demonstrate some interesting results. 
main_review: Strengths:
This manuscript exploits the idea of linear programming into knowledge graph completion tasks and then presents a model to prove the sufficiency of their idea. Some interesting experimental results are well demonstrated. 

Weaknesses:
There is no in-depth comparison of the algorithm with previously known work.  Section 2 simply listed a bundle of ‘literature review’.  However, it is still hard to judge whether the algorithm is an improvement on previous work.
summary_of_the_review: This is a well-written paper having some interesting results. A few minor revision are list below.
* The idea of using column generation techniques to add new rules is interesting. However, the methods and theoretical innovations are still not sufficient. The author(s) must dig deeper into the innovation points before the article can be accepted.
* The literature review is weak. Related work has not been investigated sufficiently before just presenting the author’s model.
review_title: null

Meta-review: The paper shows how to make use of a linear program for extracting logical rules for knowledge graph completion. Overall, the reviewers and I agree that this is an interesting and important direction for research. Moreover, the presented approach shows good performance with rather small sets of rules extracted. However, all reviewers point out that the related work is not well discussed. While the authors have improved the related work sections during the rolling discussion, overall the positioning of the new method has still to be improved, including a better empirical comparison across different datasets. Overall, we would like to encourage the authors to polish their line of research based on the feedback from the reviews.
Decision: Reject