Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: The paper aims to learn graph structured logical rules on knowledge graphs. It proposes three tasks, which I summarize as learning rule structure, instantiating a graph-structured rule (fill in a specific relation on the edge), and answering logical queries. However, many statements are entangled and mixed, the paper has many typos and inconsistency, making it hard to follow. I suggest the authors reformulate the tasks and the order or you can focus on one aspect/task and make it crystal clear.

Questions:
- What is the difference between logic rules and logical queries? The paper abuses terms like “logical rules”, “logical queries”, “logical rules for query”, making it extremely hard to follow. Are you learning logical rules or answering logical queries? 
- According to the definition 1, figure 1 is not showing 3 logical rules but rather 3 logical formulas/queries, because there is no $R_{cpx}$.
- I don't quite follow and agree with the statement “Note that, $R_{comp}$ can both be a relation that exists in the KG and the human-defined logic rule for a query, which tends to be more complex” I think $\wedge_i^n R_i$ can be complex, no matter it is a chain, tree or graph, but $R_{cpx}$ should always be a concrete relation that exists on KG, otherwise it’s meaningless, because $R_{cpx}$ can simply represent anything. (I assume $R_{comp}$ is a typo and you mean $R_{cpx}$ here)
- Here is another confusing statement “Note that, in previous works (Hamilton et al., 2018; Ren et al., 2020), the logical rule $R_{cpx} = \wedge^n_i R_i$ is given”, according to your definition 1, shouldn’t the logical rule be $\wedge^n_i R_i \to R_{cpx}$? 
- What is the relationship between $e(v_i, v_i’)$ and $R_i(v_i, v_i’)$?
- What is $G$ at the start of sec. 4.1, is it $G_e$ in section 2? There is also no $G$ anywhere in figure 1, you need to add some pointers.
- “We denote the adjacent matrix of relation $R_i$ as $A_i$ , which is a soft choice among adjacent matrices $A_k$ corresponding to all relations in R.” Then which one is the adjacency matrix $A$ or $A$ bar? According to your statement, it is $A$, but according to Eq. 2, it is $A$ bar.
- $\beta_{ik}$ comes out of nowhere. Why do you want to have this new parameter and what is the motivation?
- Why do you want to “by which we can use {$\beta_{ik}$} as learnable parameters to learn which relation should be assigned on each edge given the logical structure.”? I think you already have instantiated the edges right? E.g., in the right case in Figure 1, you already know that some edges are “read” and some edges are “friend”.
- The use of $S_r$ is not rigorous, for Eq. 3, it should be $s_r$({$X$},$Y)$ instead of $s_r(X,Y)$.
- Why do you have $A_1$ to $A_5$ in Eq.3, but in the example, you only have 3 relations: “read”, “read(inv)”, “friend”.
- In Sec. 4.3, it’s not “(1)”, “(2)”, but rather “Eq. (1)”, “Eq. (2)”
- Add reference and citations to the statement in the Computation Complexity paragraph.
- I did not find how the model answers logical queries (task 3) in the inference step, i.e., given a new $(${$X_j$}$,R_{cpx})$, how to find $Y$.
- In the case study section, it only shows how the model deals with task 1, i.e., when the logical structure is given. Considering there are 3 tasks, it would be better if you can show examples for the other 2 tasks.
- The datasets in the experiment section are small-scale and synthetic. What is the real-world application of the model? You claim that “For more complex rules, we generate a synthetic dataset because the real-world datasets are usually noisy.”, but isn’t the whole goal of the paper to model the real-world data and robust to noisy links?
- What is the evaluation setup? Table 2 lists the performance of query answering, (task 3), where are the results for the other 2 tasks? Also, I assume DRUM/Neural-LP can only handle link prediction in the original paper, there lacks details how you improve DRUM to model complex queries.

review_title: Novel idea. Writing has much room for improvement. Experiments are synthetic

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes techniques that generate logical rules out of knowledge graphs; the idea is to produce more complex rules than usual by exploiting a differentiable formulation of the associated learning process. This is a relevant theme as rule learning from knowledge graphs is important in practice due to its potential interpretability (as compared to black-box schemes based on embeddings). The solution is relatively simple to describe, with a score that leads to differentiable learning, and some needed insights to obtain useful results. The empirical testing seems fine and does indicate that the method is useful in practice.

I must say that I was very interested in the "Einstein sum notation" but I could not quite see what it is and, more importantly, I could not see how this notation helps anything. Of course I understand that the authors do not have much space to explain details of this formalism, but some clarification would really help: I doubt that readers of ICLR papers will know this notation in detail. In fact, it would be nice to indicate how important this notation is in the whole system. 

One question: looking at Figure 1 I see some questions on knowledge graphs and their possible answers, I cannot see exactly where are the "rules" there. 

Overall the text can be followed but it could be revised so as to be made more didactic; also there are some annoying typos that should be fixed. For example:
- Abstract, line 6: "observing [that] the".
- Introduction, line 8: "ruleS".
- What is "widely-existed graph-like logical rules"?
review_title: Relevant and important topic, interesting idea with some novel twists

final_score: rating: 4: Ok but not good enough - rejection
review_content: #### Summary

This paper proposes a differentiable model to learn "graph-like" (ie, more general than tree-like) logical rules over a knowledge base from example instances of the target relation. The key contributions are the generalization beyond tree-like rules, an Einsum expression notation, and an experimental evaluation.

#### Strong and weak points

I found Figure 1 and the associated running examples to be extremely helpful. The decomposition and definition of the three tasks was also very clear. On the other hand, I found the notation and presentation text of Definition 1 and Section 4.1 to be dense and confusing. The auxiliary removing and merging relations could also have benefitted from some more explanation like a diagram or worked example.

The key innovation (in my reading) is the use of the learnable $\beta$ softmax parameters to determine which relations should be "active" in a given learned rule, as well as the normalized score objective which would penalize rules with many "spurious" groundings that satisfy the antecedent of the implication.

The significance or usefulness of graph-like rules could be established more convincingly. The Figure 1 running example seems a little contrived, and the experimental evaluation for these rules had to rely synthetic data. It would be helpful to identify important applications or research directions that would be unblocked by this work.

Experimental results against strong baselines show comparable performance on simpler (chain and tree-like) rules, and much stronger results (as expected) on graph-like rules.

The actual mechanics of what gets computed and how are not very clear. The einsum notation is nice, but it is not rigorously shown why or how the operations cannot be expressed as matrix operations, or what actual computational graph PyTorch would generate under the hood to run learning and inference.

#### Recommendation (accept or reject) with one or two key reasons 

I would argue to reject primarily on clarity and rigor concerns, and somewhat less so on significance of graph-like rules.

#### Supporting arguments

I think there are some potentially exciting contributions here in terms of the beta-softmax formulation and being able to handle graph-like rules. That said the core technical content could be developed more clearly, and underlying details about complexity and computation should be handled more carefully. Some more specificity around use cases or research directions for graph-like rule learning could also further strengthen the submission.

#### Questions to clarify / additional evidence required

Why is the target relation called $R_{cpx}$ (ie, what does "cpx" mean)? This notation doesn't seem common in the related works.

"NP-hard problem" is mentioned a few times but without citation or clarification. The "Computational complexity" Big-O term is given without explanation or justification, and furthermore it was not clear what $m$ meant. Also, is the differentiable training approach guaranteed to find global optima, or only local ones? Is there an approximation factor or rounding gap between solutions found by this approach and the ground truth combinatorial optimum solution?

Section 4.1: minor typos "evaluate the plausibility of a logical _rule_" and "_adjacency_ matrix".


#### Additional feedback to improve

It might be worth reviewing the literature in logical rules learning, eg, [Turning 30: New Ideas in Inductive Logic Programming](https://arxiv.org/pdf/2002.11002.pdf) might be relevant. Relatedly, I think the terminology of "rule groundings" and related ideas from [Markov Logic Networks](https://homes.cs.washington.edu/~pedrod/papers/mlj05.pdf) would probably be helpful here. This work also seems particulary related to [Learning the Structure of Markov Logic Networks](https://homes.cs.washington.edu/~pedrod/papers/mlc05a.pdf).

It would be helpful to at least mention the normalized score earlier in the paper when the intuition for rule scoring is introduced, as I was immediately curious why this wouldn't lead to rules which add "easily satisfied" free variables and edges in order to increase the score.



review_title: Compelling core idea, could be tightened up on clarity and rigor

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper addresses the problem of logic structure learning, AKA, finding rules that generate a noisy knowledge graph. The innovation here is that the learning algorithm can address a much broader spectrum of rules than current methods. The key ingredient of the proposed method is a differentiable scoring function that models the rules.

* I think the authors are making the problem unreasonably complicated formalism to express the scoring function. It would have been much easier to express their algorithm in higher order tensors for equations (1),(2),(3)
* The A_i matrices they want to learn can be consolidated in a 3-dimensional tensor. Then what they need in order to obtain the s_r scoring function is a sumproduct over this tensor. In reality wha they are trying to learn is this huge but potentially sparse tensor. I would also like to point that from equation (3) it is implied that their algorithm cannot learn arbitrarily long recursive relations. Notice that in equation (3) each relation is used once only. For example, you cannot have A_3[Z1, Z2]A_3[Z2, Z3]....
* Another limitation which I think is important is that it does not learn the negation. That is probably an easy fix, but I think it is worth mentioning.

* The experiments are a bit limited in scope, but they are convincing. I realize that for the complexity of the algorithm it might be hard to scale to more datasets. I would have preferred if some timing results were reported too.

* What I find odd is that the authors didn’t try to model the 3-dimensional tensor A with a deep network. It would have definitely helped them scale better. I am not sure how they would have implemented the merge and remove operator but this is worth investigating

Overall I think the work is interesting and novel, but it is far from being practical for the moment. 

review_title: Addressing a difficult problem with moderate success

Meta-review: While all reviewers see a lot of value in the paper, it cannot be accepted in its current form: too many issues with clarity. A more focused paper, with clear task and contributions is recommended.
The revisions and answers to reviewer questions are greatly appreciated and go a long way towards addressing these concerns for a future submission.
Decision: Reject