Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes the Monotonic Graph Neural Network (MGNN) model that can be exploited to learn tasks on knowledge graphs. Knowledge graphs are referred to as "datasets", that are based on constants, unary and binary predicates. A method is defined to encode a given dataset (i.e. a KG) as a colored graph, whose nodes correspond to the constants and pairs of constants. Edges of one out of four different "colors" (types) are added to encode the relationships between constants and the occurrences of their pairs in binary predicates. A vector is stored in each node to represent the truth table of each predicate when computed on the corresponding grounding. The MGNN processes such a graph to computed a new KG in which new facts are inferred. A theoretical result shows that an equivalent set of Datalog rules can be derived from the trained MGNN, thus providing a direct explanation of the learned model.
The proposed approach is evaluated on KG benchmarks, showing promising results when compared to other 2 state of the art methods.
main_review: The proposed method is very interesting since it provides a theoretically motivated model that is able to learn tasks on knowledge graphs, having the possibility to extract explanations. The MGNN just requires to apply simple constraints on the original GNN architecture to guarantee monotonicity in the implemented function (positive weights, monotonic activation functions, use of the max as aggregation operator for neighbor nodes). The most valuable property is the possibility to derive the datalog rules that the model implements, as guaranteed by the provided theoretical results.

Despite being generally a good quality contribution, in my own opinion, the paper suffers from some weaknesses.

- Some parts are quite hard to follow. Even if the main ideas can be understood and are explained with sufficient clarity, the more theoretical part is quite hard to follow (in particular, Section 3, that introduces the main theoretical results on the extraction of equivalent datalog rules from a trained MGNN).  Some concepts would need a more detailed description, with examples (figures, algorithms) to provide a mode immediate understanding. For instance, the extraction process is supported by theorem 8 but it requires the enumeration of all rules. In the experimental section it is described that some constraints are imposed on the search strategy to keep the complexity low. A schema of the generic procedure, that can be implemented for the rule extraction, would have given a more compact and clear view of the proposed method and its potential limitation with respect to complexity. Other important concepts are also difficult to grasp without simple practical examples. For instance, primal graphs and in particular (c,d)-tree-like structures for variables are important concepts to undestand the limitations of the proposed architecture (the two provided examples are for instance useful). If you look at defintion 9 and what follows (I guess that the two following paragraphs are not part of the definition and should not be in italics), many imporant concepts are introduced  that involve the rule structure and the representational power of the MGNN model. This is just in few lines... (btw, what is the dimension k? The numer of internal units in the GNN?)
- The limitations of the representational power of the MGNN model should be discussed more deeply. Theorem 10 is claimed to provide results on the expressiveness of the model, but beside the proof in the appendix and a few  lines after definition 9, this aspect is not detailed to make the reader understand the actual limitations in practice. The evaluation section reports a few rules that are extracted, but they are quite simple and limited to symmetry, inverse relations and subsumption. It would be useful to provide more examples of extracted rules. 
- The extaction process requires to enumerate all rules and to check them on the trained model by applying proposition 7. In the evaluation some restrictions on the considered rules are applied (rules with at most two body atoms). The issues about complexity and the possible solutions should be clearly pointed out.
- In the evaluation section there are not enough details on the used architecture (f.i. number of layers, activation function, etc). As far as I understand, the results are obtained on only one run for each dataset (dataset split/weight initialization). It would be useful to show how the architecture affects the results and how the training is stable (however this is not a major weakness since the paper contribution may be considered theoretical).

Minor remarks.
- When describing the MGNN model (definition 3) the notation of the dimension may be confusing because of the stacking of the layers. Is {\bf b}^{\ell} of dimesion n^\ell o m^\ell? 
- Does the encoding of the KG consider only the pairs of constants found in the binary predicates in KG? In case, may it happen that pairs not present in the graph are needed? 
- As far as I understand, all predicates (binary/unary) are considered in the vector attached to each node being it a single constant or a pair of constants. Is this just a choice to simplify the notation in the theoretical part or is it also used in the implementation? (I did not check the code).
summary_of_the_review: The paper provides an interesting model to learn tasks on knowledge graphs. However, there are some aspects (limitations of the model and of the extraction procedure, settings of the evaluation) that would need more details and/or discussion. Finally the are some parts that are dense in concepts/theory and are hard to follow (more examples/schemes would be useful to improve readability).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a Monotonic Graph Neural Network transformation (MGNN) for inductive knowledge graph completion, which allows the predictions to be explained symbolically by logical rules. 
main_review: Strengths:

- This paper studies how to improve the interpretability of GNN-based predictions, which is an important research direction.
- The authors provide a detailed theoretical analysis of the model’s ability to 
explain the GNN-based predictions by logical rules.

Weaknesses:

In terms of the experiments, my concerns are as follows.
- This proposed method is based on GNN. However, the comparison with GNN-based methods is missing. The authors may want to compare their approach with the state-of-the-art GNN-based ones, such as GraIL[1] .
- MGNN does not outperform some existing models like DRUM and AnyBURL on several benchmarks.
- The authors may want to provide some case studies to show how MGNN ensures that the predictions can be explained by logical rules, as what DRUM [2] does in Section 5.3.

In terms of the proposed model, MGNN assigns a feature vector to each link, which significantly increases the computational cost. This makes the model difficult to apply to large-scale knowledge graphs.

In terms of the writing, my concerns are as follows. 
- The necessary visual illustrations of the idea and the model architecture are missing, making this paper hard to follow. The authors may want to provide figures in Sections 2 and 3.
- The authors may want to specify some important details.
    - In Section 2, the authors say that the result of MGNN can be decoded to an output knowledge graph by "inverting the encoder". However, the decoding procedure is unclear. 
    - The definitions of $c_3$ and $c_4$ in Paragraph 4 are missing.
    - Some of the statements are confusing. For example, in Section 2, Definition 3 states that $\sigma$ is a mapping from $\mathbb{R}$ to $\mathbb{R}^+$, while the input of $\sigma$ in Eq. (1) belongs to $\mathbb{R}^d, d\geq 1$. Besides, each vertex of the result $M(G)$ is labelled by a boolean number, while in Definition 4 the label is a vector.

[1] Komal K Teru, Etienne Denis, and William L Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.

[2] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs. In NeurIPS, 2019. 

summary_of_the_review: This paper proposes a GNN-based method, named MGNN, which allows the predictions to be explained symbolically as logical reference to improve their interpretability. However, MGNN does not outperform existing approaches on some benchmarks, and it may be difficult to apply to large-scale knowledge graphs.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new family of GNN-based transformations for knowledge graphs, which is called monotonic GNNs (MGNNs). The key characteristic of MGNNs is that we can produce an equivalent set of rules for an arbitrary MGNN, and the rules and the MGNN-based transformation can produce the same facts. In other words, the rules can be used to explain how MGNNs make predictions. Moreover, the authors provide dedicated proofs for their formal statements. The experimental results on classification tasks for knowledge graph completion demonstrate the effectiveness of the approach.
main_review: Pros:

* It first transforms the original knowledge graph into a colored graph where each vertex is labeled by a feature vector and represents the facts of the corresponding entity or entity pairs. It further connects the vertices that refer to the common entities. Such a transformation is a bit inspiring, and it is naturally suitable for inductive settings.

* The authors make it clear that there is an equivalent set of rules for any MGNN, and that both can produce the same facts. Hence, we can use rules to understand the predictions made by MGNNs.

Cons:

* The approach appears to be straightforward. I discovered that Equation 1 is sufficient to describe the model. Furthermore, Section 3, which is two pages long, only states that there is a set of rules that can be used to derive the same facts as MGNNs. The authors should simplify this section and add some details to the appendix, in my opinion.

* It appears that rule extraction is a searching procedure that requires a lot of space and time. This could limit its use in larger datasets. Some baselines, such as DRUM and AnyBURL, can also capture rules. Although the exact relationship between the predictions and the results of applying the rules to these methods is unknown, the generated rules can still assist us in understanding their predictions to some extent. Table 2 also shows that these baselines can produce competitive results. Hence, I think the advantage of the proposed approach is not obvious.

Questions and Suggestions:

* The authors should add some citations regarding the transformation process into a colored graph, as there exists some work that adopts similar transformations.

* Theorem 10 describes the expressiveness limitation of MGNNs, i.e., MGNNs can only capture some rules. I want to know whether some baselines (e.g., DRUM and AnyBURL) also have this limitation, as they can also capture rules.

* The authors split the testing dataset and re-evaluated their approach in Table 3. I think it is better to provide the results of baselines in this setting.

* In Section 3, the authors said that "we can enumerate all such rules, apply Proposition 7 to each rule, and keep only the rules that pass this check". It seems that the rule extraction procedure is time-consuming. Can the authors provide the corresponding time cost? I also notice that the last column of Table 2 records the training time. I want to know whether the training time includes the time cost of rule extraction.

* In Section 4, the authors said that "to reduce the search space, we considered only rules with at most two body atoms". I think the extracted rules can not exactly describe the predictions made by MGNNs, as the authors only consider a part of the rules.

* From Table 4 and 5, I notice that $T_M$ captures much more rules than AnyBURL on FB15K-237, and fewer rules on WN18RR. Can the authors explain the phenomenon? Moreover, the fourth column in Table 5 shows the number of AnyBURL rules captured by $T_M$ on $S_I$. Can the authors provide the number of rules captured by AnyBURL on $S_I$? It will help readers see the proportions of rules generated by AnyBURL and $T_M$.

summary_of_the_review: The idea of the paper is interesting but the technical contributions are not very significant and the advantage of the proposed approach is not obvious.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper focuses on graphs representing sets of facts in a knowledge base, and casts knowledge graph completion as a graph labeling problem. The authors propose a particular encoding of facts into graphs, and introduce a particular family of "monotonic graph neural networks" (MGNNs) that share properties with logical inference rules in Datalog: namely, they prove that MGNNs are "monotonic under homomorphisms", which effectively means that renaming objects or introducing new facts never causes the classification to switch from True to False. The authors also prove that for any MGNN (with a fixed classification threshold) there exists a set of rules in Datalog that produce the same conclusions, and treat this as a symbolic explanation for the MGNN's behavior. They evaluate MGNNs on a set of knowledge graph completion tasks, and find that it performs on par with some other methods for knowledge graph completion.
main_review: ### Clarity and technical correctness
Overall, the paper is well written. I was able to follow the majority of the main paper, and the authors anticipated many of my technical questions and answered them with helpful examples and discussion (for instance, by walking through the intuitive interpretation of MGNNs, discussing how their method does not allow inferring transitivity relations, and describing how they set thresholds in their experiments).

Some specific comments on clarity:
- On page 5, it was difficult to follow the connection between the definition of "monotonic under homomorphisms" and the description of "monotonic" for constant-free programs; the paper simply states "Monotonicity under homomorphisms combines both of these properties." without saying how. (Is it that we can always construct a homomorphism from a smaller dataset to a larger one, and thus properties of the smaller dataset must also hold in the larger one?) It would be nice to have a short discussion of why an operator that is monotonic under homomorphisms is always monotonic.
- It would be useful to have a figure showing what the graph encoding of a dataset looks like.
- In section 4, it says the MGNN models were trained with "cross-entropy loss". What was used as the output probability for this loss? Was it a logistic sigmoid applied to $\lambda^L(v)$? This doesn't appear to be stated explicitly.

I believe the theorems are likely to be true, but I found some of the proofs difficult to follow and did not check them in detail. Although the paper does a good job at giving intuition in the main paper, I felt like this intuition was missing in some of the proofs, in particular in Theorem 10. Some things I had trouble following for the proof of Theorem 10:
- There are a huge number of definitions and new symbols being introduced, and I wasn't sure what those symbols were supposed to represent.
- The induction argument is very difficult to follow, I think because it omits the dependence of various quantities on the induction variable $\ell$ (I think), interleaves re-definition of values with proofs about them, and doesn't seem to have a well-stated goal (or at least I couldn't find it). As one point of confusion, after the end of the construction, it is stated that "C is a nonempty (3k, L)-tree-like conjunction for x" but I don't think this is ever explicitly proved, or even stated as something that should be proved; it seems like this should have been a property being maintained through the induction process?

### Interpretation of the extracted "explanations"
**(Edit: My original criticisms in this section are partially based on a flawed comparison to an alternative approach that I later realized did not make sense. I have added strikethrough for the parts I no longer believe to be correct.)**

The authors motivate their approach based on the quality of the explanations it extracts, and one of the stated strengths of their method is that the behavior of the MGNN can be fully characterized by a set of Datalog rules. The authors seem to be working under the assumption that Datalog rules are inherently better explanations than the original GNN. While this is plausible for hand-written Datalog rules, I'm not at all convinced the rules extracted by their method are particularly useful.

From what I could understand, it seems like their construction is roughly as follows:
- Constrain an MGNN such that it is monotonic under homomorphisms.
- Enumerate *all possible rules* up to a given size (under some constraints), where the size is determined by the receptive field of the MGNN. For each rule, construct a subgraph representing the body of the rule, and see if the MGNN classifies the head of the rule as true or false.
- ~~Collect *every subgraph* (or, equivalently, every rule) that the MGNN classifies as true and store them in a gigantic list.~~ **Edit: It's not possible to enumerate every possible subgraph of every possible dataset, since the MGNN may have arbitrarily many nodes in its receptive field. The authors describe a particular subset of rules, and concrete (sub)graphs that determine whether the GNN captures those rules. This subset is smaller than the set of all subgraphs (in particular it's finite). Additionally, the revised paper clarifies that they only include rules that are not subsumed by other rules, so every part of the extracted rules is actually relevant to the MGNN output.**
- ~~Use this list (effectively a lookup table) as an explanation of the MGNN.~~ **Edit: This is an oversimplification on my part; given that they restrict the form of considered subgraphs and do subsumption checks, it's not just a lookup table.**

The argument of Theorem 10, as far as I could follow it, appears to be that if the MGNN deduces that a particular fact as true in a knowledge graph D, then the subgraph of D that the MGNN looked at could be represented as a rule, and so it would be in the gigantic list of all possible subgraphs that the MGNN classifies as true.

~~While it is technically true that a gigantic list of all possible subgraphs that the MGNN classifies as true "fully characterizes" the set of graphs that the MGNN classifies as true, this doesn't really seem like a satisfactory explanation for why it does so. In fact, I think you could do a very similar thing for an ordinary GNN without monotonicity constraints: enumerate all possible subgraphs up to the receptive field of the GNN, and see which ones it classifies as true. But such an explanation seems mostly useless, since it boils down to a sort of tautology: "the output was true because this is one of the graphs in the list of things classified as true". Admittedly, it might be possible to simplify the MGNN explanation by only keeping the set of "minimal subgraphs" classified as true by the MGNN, and discarding any rule that is implied by another smaller rule (instead of using every extracted rule as their theorem assumes). It's also possible that the constraints on the rules lead to a smaller number of subgraphs (although it still seems like an exponentially large blowup). However, it's not obvious to me that this necessarily leads to set that is small enough to reason about.~~ **Edit: This comparison is flawed; it's not just a subgraph search, because there are infinitely many possible subgraphs (among the set of all datasets) and you can't enumerate all of them. The authors also do subsumption checks to ensure that the extracted rules are as simple as possible.**

Perhaps the authors can provide additional information about how many rules are needed to actually fully characterize their models? On page 8 they say "To reduce the search space, we considered only rules with at most two body atoms", which might suggest that it is computationally infeasible to actually fully characterize the performance of MGNNs by extracting rules of this form.

Additionally, it's possible that I am misunderstanding the rule extraction mechanism; if so, please let me know.

### Novelty and related work
I am not well versed in the knowledge base completion literature, but as far as I know the idea of constraining a GNN to be monotonic under homomorphisms of knowledge bases, and thus to behave like Datalog rules, is novel. However, there has been a fair amount of related work on neural networks that are monotonic for other purposes (and which use similar techniques of nonnegative matrices and monotonic activation functions, among others). As a few examples:

- You, Seungil, et al. "Deep lattice networks and partial monotonic functions." Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017. https://arxiv.org/abs/1709.06680
- Gupta, Maya, et al. "Monotonic calibrated interpolated look-up tables." The Journal of Machine Learning Research 17.1 (2016): 3790-3836. https://arxiv.org/abs/1505.06378
- Wehenkel, Antoine, and Gilles Louppe. "Unconstrained monotonic neural networks." Advances in Neural Information Processing Systems 32 (2019): 1545-1555. https://arxiv.org/abs/1908.05164

The technical details of the rule extraction mechanism seem novel as well, but as I've stated above, I'm not particularly convinced that the rules it extracts are particularly meaningful, so it's difficult to tell if this is significant.

### Empirical results
The authors evaluate their approach compared to two existing knowledge graph completion baselines. From the results, it seems like their method is not strictly better or worse than either of the baselines they present, and the different methods have a wide range of performance across the different datasets. One thing that would be useful would be to report standard deviation measures over different random seeds and training splits (specifically the 9:1 split used to construct the incomplete knowledge base and completion targets).

The authors note that the expressivity of MGNNs is limited by the power of "(c,d)-tree-like" rules, and that consequently they cannot express properties such as transitivity. They point to this as a possible reason for the low recall of their method on many of the datasets. They also include an experiment with an alternative test set where they ensure every output fact is at least structurally possible to be classified using their method, and show that recall improves; however, they don't report baseline performance for this test set so it's possible some of the improvement is just because this new test set is easier.

The authors also mention that they analyzed some of the rules by hand. I think it would be useful to include additional details of this, for instance by showing some of the extracted rules. I also wonder how close their extracted rules come to capturing the behavior of the MGNN; how many classifications of the MGNN can be explained using the extracted rules, and how many of them are left unexplained due to the truncation on the search method?

I also notice that their method learns orders of magnitude more rules than AnyBURL, e.g. their method learns roughly 90,000 rules on FB15K-237 v4, whereas AnyBURL achieves higher accuracy with only 3,574 rules. It seems like fewer rules should be better for a good explanation, right?

### Updated review (Nov 18)

After discussion with the authors, I have raised my score from 5 to 6. I misunderstood a few aspects of the proposed method in my initial review, and also compared it to an alternative approach which I later realized was incorrect. The authors have also addressed many of my concerns regarding clarity and missing experimental details.

I still feel that the paper could be improved by adding more of a discussion in the main paper of how to actually make use of the extracted rules to explain predictions made by a MGNN in practice. For instance, given the extracted set of rules, how do we formally verify properties of interest about the MGNN? Or, given a particular prediction of the MGNN in a particular dataset, how can we identify which facts the MGNN actually used to make its prediction? Can the full set of rules (e.g. those with more than two body atoms) be extracted quickly enough to make either of these practical? These details are especially important because the paper motivates the approach based on the trustworthiness/compliance/verifiability/fairness of the system. After discussion with the authors I believe doing this kind of verification and inspection should be possible in principle (although I have some concerns about runtime), but many of the details are buried in the appendix, and I think they should be given more of a focus.

### Updated review (Nov 22)

I have raised my score again from 6 to 8.
- The authors have added additional information about how to use Datalog reasoning engines to explain the behavior of the MGNN using the extracted rules.
- I am still unsure that it is feasible to extract every rule captured by the MGNN, which would make verification difficult. However, the authors have added new results showing that the subset of extracted rules with at most two body atoms still have fairly similar performance to the MGNN on their datasets. If verification is important, a user could then just use the extracted rules instead of the MGNN, allowing them to build a fully-explainable prediction system while trading off accuracy and computational cost (e.g. spending compute to extract more rules in exchange for a better, more-accurate approximation of the MGNN).

A few more suggestions for improvement:
- I would recommend briefly mentioning the computational constraints on the current rule-extraction algorithm in the introduction, to make it clear that there is a difference between the theoretical and practical ability to extract rules. Specifically, after the sentence "we can explicate the rules that are implicitly captured by the model and use them to fully explain each credit recommendation", I'd suggest adding another sentence stating that the existing algorithm for extracting rules may only explain a subset of predictions of the original MGNN (and, optionally, that the extracted rules could just be used directly if it is critical to be able to explain every prediction).
- In section 4 "Rule Extraction" after "we applied $T_P$ to the test dataset of each benchmark", it would be useful to explicitly refer to Table 6 in the appendix, so that readers know where to find that information.
- I think it would be important to include some results for AnyBURL and DRUM in Table 6 as well, by extracting a set of rules from them and then evaluating those rules. I am aware neither AnyBURL or DRUM has any theoretical guarantees about extracted rules, but as far as I understand it each method does produce some rules with thresholds, so it seems fair to take a subset of their rules (with threshold similarly tuned for accuracy). This would help answer the question of how much the MGNN adds over the baselines if you require that every prediction be explainable by rules.
summary_of_the_review: The main paper is well written and I think it is technically sound (although I found the proofs difficult to follow and did not fully verify them). ~~However, I'm not convinced that the rules they extract really count as "explanations": as far as I can tell the extracted rule sets can be extremely complex and may not have any more explanatory power than a gigantic lookup table~~. Empirical results are also not particularly strong; their system achieves comparable performance to other methods but seems to require orders of magnitude more rules and also has fundamental limits to its expressivity.

**Update (Nov 18):** After discussion with the authors, I have raised my score from 5 to 6; some of my concerns in my initial review were based on a misunderstanding of the proposed method, and the authors have addressed many of my comments regarding clarity and experimental details in the revised paper. I still feel that the paper could be improved by describing in more detail how to use the extracted rules to explain predictions, since this seems to be the main way their approach differs from prior work.

**Update (Nov 22):** I have raised my score again from 6 to 8. The authors have added more discussion of how Datalog engines can use the extracted rules and how accurately the truncated rule-extraction algorithm approximates the MGNN. Since the rule-based approximation performs fairly well (and could be improved by running the extraction algorithm for a longer time), it could be used directly for making predictions in domains where explaining every prediction is critical, and then standard Datalog tools could be used to explain all predictions.
review_title: null

Meta-review: This paper proposes monotonic graph neural networks (MGNNs) for the transformation of knowledge graphs. Specifically, MGNNs transform a knowledge graph into a colored graph where each node is represented by a numeric feature vector and each edge encodes the node relationship with different colors. The authors provide theoretical analysis showing that monotonic constraint can enable the model to derive logical inference rules in Datalog, and thus the trained model is explainable. 


The authors addressed most of the concerns raised by the reviewers, such as motivation, runtime, and comparison with existing baselines. Three of the four reviewers are positive (with the scores of 6 or above) towards acceptance after rebuttal discussions, and the remaining reviewer gives a score of 5 (below acceptance threshold) thinks that this work still lacks novelty, but he/she is not against acceptance if other reviewers choose so. Considering this work makes a good exploration on explainable graph neural networks, which is an interesting and important research direction, we recommend for acceptance. We thank the reviewers and the authors for their active discussion.
Decision: Accept (Poster)