SAFRAN: An interpretable, rule-based link prediction method outperforming embedding models
Year: 2021

Abstract:
Neural embedding-based machine learning models have shown promise for predicting novel links in knowledge graphs. Unfortunately, their practical utility is diminished by their lack of interpretability. Recently, the fully interpretable, rule-based algorithm AnyBURL yielded highly competitive results on many general-purpose link prediction benchmarks. However, current approaches for aggregating predictions made by multiple rules are affected by redundancies. We improve upon AnyBURL by introducing the SAFRAN rule application framework, which uses a novel aggregation approach called Non-redundant Noisy-OR that detects and clusters redundant rules prior to aggregation. SAFRAN yields new state-of-the-art results for fully interpretable link prediction on the established generalpurpose benchmarks FB15K-237, WN18RR and YAGO3-10. Furthermore, it exceeds the results of multiple established embedding-based algorithms on FB15K-237 and WN18RR and narrows the gap between rule-based and embedding-based algorithms on YAGO3-10.

heading: 1. Introduction
text: Link prediction in knowledge graphs is a vibrant area of research and development and encompasses a wide range of different approaches. Currently, most state-of-the-art approaches use low-dimensional representations (embeddings) of knowledge graphs to predict new knowledge. However, as such approaches are black boxes, the validity of their predictions can be questioned due to lack of interpretability. Recent research has focused on learning symbolic rules from knowledge graphs that try to detect correlations of entities in knowledge bases and express them as first-order Horn rules. In contrast to neural models, such rule-based methods are fully transparent and predictions can be explained intuitively.
However, while current research on rule-based approaches puts a lot of emphasis on designing rule-mining algorithms, research on methods for applying learned rules and aggregating their predictions in a meaningful way is comparatively neglected.
AnyBURL [Meilicke et al., 2019, 2020] is currently one of the best performing symbolic rule learners and demonstrated results competitive with embedding methods on link prediction benchmarks such as FB15k-237. However, the application of rules generated by AnyBURL is currently limited by functional redundancies, making it difficult to meaningfully aggregate predictions made by different rules and thereby limiting predictive performance.
In this paper, we introduce the high-performance rule application framework SAFRAN1 (’Scalable And fast non-redundant rule application’) that employs a novel aggregation approach. We propose an algorithm called Non-redundant Noisy-OR that detects redundant rules prior to aggregation, mitigating their negative effects and improving predictive performance. This algorithm for aggregating predictions is not necessarily restricted to rules learned by AnyBURL and could also be applied to other rule-based systems.

heading: 2. Preliminaries

heading: 2.1 Link prediction
text: Knowledge graphs contain facts, such as “Amsterdam is the capital of the Netherlands” or “Marie Curie was born in Warsaw”, which are represented as semantic triples containing a subject (head h), predicate (relation r) and object (tail t). Formally, a knowledge graph is a directed heterogeneous multigraph G = (E,R, T ) where E and R are the set of entities and relations respectively and T is a set of triples {(h, r, t)} ⊆ E ×R×E. The task of link prediction is to predict either the tail of a given head and relation (h, r, ?) or the head of a given tail and relation (?, r, t) such that the resulting triple describes a correct fact which has not been in G before.

heading: 2.2 AnyBURL
text: We now give an overview about the main AnyBURL algorithm, which is explained in detail in [Meilicke et al., 2019] and [Meilicke et al., 2020]. AnyBURL (Anytime Bottom Up Rule Learning) is a novel walk-based method and is currently one of the best symbolic rule learners, competing with current state-of-the-art embedding approaches [Rossi et al., 2021]. Walk-based (bottom-up) methods are based on the idea that sampled paths from a knowledge graph (random walks) are examples of very specific rules, which can be transformed into more general rules. Learned rules can then be applied to the knowledge graph for the prediction of novel links between entities.
AnyBURL learns rules in the form of first-order logic Horn rules of length n. In each iteration of the algorithm for mining rules the algorithm samples a random triple h(c0, c1), f.e. lives(max, uk) from the training set. Starting from either the head or the tail of this triple, AnyBURL performs a random walk of length n, resulting in a ground
1. Code can be found at https://github.com/OpenBioLink/SAFRAN
path in the form of h(c0, c1) ← b1(c1, c2), . . . , bn(cn, cn+1), f.e. speaks(max, english) ← lives(max, uk), lang(uk, english). The sampled ground path is subsequently generalized into three predefined types of rules shown in Table 1. Cyclic rules can be generalized from cyclic paths (c0 = cn+1), while AC2 rules can be generalized from acyclic paths (c0 6= cn+1). AC1 rules are hybrid, as they can be both generalized from cyclic (if c0 = cn+1) and acyclic (if c0 6= cn+1) paths. All rules that can be generalized from the previous example ground path can be seen in Table 2.
The following applies for inferring a set of head triples Ĥr from the body of a rule r:
Ĥr =  {h(ey, ex)|ex, ey ∈ E ∧ ∃e2, ..., en b1(ex, e2), . . . , bn(en, ey) ∈ T}, if type = C {h(c0, ex)|ex ∈ E ∧ ∃e2, ..., en b1(ex, e2), . . . , bn(en, cn+1) ∈ T}, if type = AC1 {h(c0, ex)|ex ∈ E ∧ ∃e2, ..., en+1 b1(ex, e2), . . . , bn(en, en+1) ∈ T}, if type = AC2
AnyBURL calculates the confidence of a rule as the size of the union of inferred triples by a rule and the triples of the training set divided by the number of inferred triples conf(r) = |Ĥr ∩ T |/|Ĥr|, where T is the set of triples contained in the training set.

heading: 2.3 Aggregation
text: Rule-based link prediction methods, such as AnyBURL, produce many rules with different confidences that are subsequently applied to the knowledge graph in order to generate candidates for a link prediction task. Upon a link prediction task p(s, ?), rule r generates the set of predictions {y|p(s, y) ∈ Ĥr} that could act as substitutions for the question mark. Rules can either predict zero, one or multiple entities. As the same entities can be proposed by multiple rules which may differ in confidence, an aggregation of these confidences is required to assess the final confidence of a prediction. Table 3 shows the confidences and results of five fictional rules.
One aggregation approach called Maximum aggregation is using the maximum of these confidences [Meilicke et al., 2019]. The score of an entity
score(e) = max{conf(r1), . . . , conf(rk)}
is the maximum confidence of all rules r1, . . . , rk that predict entity e. If the maximum confidences of two or more entities are the same, these entities are further ranked by their second best confidence and so on, until all top-k candidates can be distinguished or all rules are processed. This approach results in the following list of ranked candidates when applied to the solutions of Table 3: rankingmax = 〈(b, 0.9), (a, 0.9), (c, 0.8)〉. As the second best rule that proposes b has a higher confidence than the second best rule which proposes a, b is ranked before a.
Unfortunately, the Maximum aggregation is constrained to relatively simple predictions: Each prediction is primarily informed by only a single rule with the highest confidence; it is not possible to make predictions based on a weighted combination of different rules. These limitations of maximum aggregation are potentially addressed by noisy-or aggregation, first proposed in this context by [Galárraga et al., 2015]. Instead of taking the maximum of confidences, the probability that at least one of the rules proposed the correct candidate is used for generating a list of ranked candidates. The score of an entity e can thus be calculated as
score(e) = 1− k∏
i=1
(1− conf(ri))
where r1, . . . , rk are rules that predict entity e. Applying the Noisy-OR approach to the results of Table 3, the entities are ranked as follows: rankingnoisy = 〈(c, 0.94), (b, 0.93), (a, 0.9)〉. This ranking differs from the maximum approach. As c is proposed by the second and third most confident rules, its aggregated confidence is higher than a or b, entities proposed by the most confident rule.
In theory, Noisy-OR allows for more sophisticated confidence aggregation. However, it assumes independence/non-redundancy of all rules. As most rules that can be derived from real-world knowledge bases are in some way redundant with other rules, Noisy-OR was found to perform worse than maximum aggregation in practice.

heading: 2.4 The detrimental effect of redundancy on Noisy-OR aggregation
text: Redundancies in rules can lead to overestimation of confidences of predicted entities when aggregating using Noisy-OR. As two redundant rules generate the same predictions for the same reasons, the confidences of entities predicted by both rules are overestimated due to double counting. Consider the rules shown in Table 4 where this problem becomes apparent. If the training set contains the ground path lives(john, uk), lang(uk, english), each rule would predict speaks(john, english) upon the prediction task speaks(john, ?) for the same reasons. Aggregating the confidences of all three rules using Noisy-OR would result in an overestimated confidence of 0.988 for the entity english.
While these redundancies are apparent, redundancies between rules are often less obvious in practice. Redundancy between two rules can arise from special relationships between relations, such as relations that are nearly equivalent, symmetric relations or relations entailing other relations. Consider the rules shown in Table 5. The first example shows two
rules being redundant based on entailment, as every capital of a country is a city within that country. The second example shows redundancy based on the symmetric relationship married. Both rules generate predictions for languages spoken by a person, based on what language its spouse speaks. The third example shows that such relationships are not restricted to single relations, but can arise from a combination of relations, as the combination parent → brother is a duplicate of the relation uncle.
It is important to understand that there is usually no explicit information available about the symmetry of married nor do we know that capital is more specific than city. It is not even possible to grasp this information from the dataset itself as it might be incomplete and noisy. This makes it impossible to decide redundancy via a procedure that makes use of relevant background knowledge.

heading: 3. Approach

heading: 3.1 Algorithm
text: To overcome the problem of redundancy when using the Noisy-OR aggregation method, we propose an approach to cluster rules based on their redundancy degree prior to aggregation. Predictions of rules in a cluster are aggregated using the Maximum approach, as this approach is not susceptible to redundancies. Predictions of the different clusters are then further aggregated using the Noisy-OR approach. We call the resulting aggregation technique Non-redundant Noisy-OR. A pseudocode of Non-redundant Noisy-OR can be seen in Appendix G.
As a metric for redundancy between two rules ri, rj the Jaccard Index sim(ri, rj) = |Ĥri ∩ Ĥrj |/|Ĥri ∪ Ĥrj | of the sets of inferred triples is used. As the calculation of the Jaccard coefficient is very inefficient for large sets, the Jaccard coefficient is estimated using the MinHash scheme [Broder, 1997], which makes time complexity linear and memory usage constant.
Naturally rules are pre-clustered by their relation of the head atom, as two rules having a different relation in the head are never used in the same prediction task and the union of their inferred triples is always empty hri 6= hrj → Ĥri ∩ Ĥrj = ∅. Thus, similarity matrices of rules are calculated for each head relation and used to cluster the rules.
Two rules ri, rj are considered redundant and assigned to the same cluster if sim(ri, rj) > t, where t is a threshold. However a global threshold t is not capable of defining the cutoff point for redundancy for all relations, rule types and directions of prediction (prediction of head entities or tail entities). As the sets of rules that predict for different relations may vary in distribution of type, length or specificity, the threshold that generates the optimal clustering for a relation may not generate the optimal clustering for a different relation. Furthermore as relations may vary in multiplicity the direction of the prediction has to taken into account. Therefore, a distinct threshold for the prediction of heads and prediction of tails for each relation is required in order to be able to optimally cluster an entire rule set. Furthermore, within a set of rules that predict for the same relation, optimal thresholds may vary between types of rules. As can be seen by the examples in Table 4, the type combination of C and AC1 often tends to form set-subset relation. The Jaccard Index is very insensitve to such relationships. While e.g. a Jaccard index of 0.25 between a rule of type C and a rule of type AC1 may indicate a high redundancy due to the dominance of set-subset relationships within rules of this type combination, it may be considered as a fairly low evidence level for a redundancy between two rules of type C, where such relationships are not as prominent. Thus a differentiation of rule types is needed when defining the cutoff value for redundancy between two rules of a certain relation. For each combination of rule types an independent threshold parameter is used to determine redundancy. Conclusively, the threshold of similarity for rules that predict entities of direction d (head or tail) of a h-triple (we use h to refer to a relation, while r is used to refer to rules) is given by thd = [tC/C , tC/AC1, tC/AC2, tAC1/AC2, tAC1/AC1, tAC2/AC2]. Note that if thd = [0, 0, 0, 0, 0, 0] only the Maximum aggregation is used and if thd = [1, 1, 1, 1, 1, 1] only Noisy-OR.
An optimal clustering of rules that predict h-triples is given by the type combination thresholds thd that maximize the fitness of the clusters for predicting new links. This fitness is evaluated on the validation set using the mean-reciprocal rank based on the topk predicted entities. SAFRAN uses one of two search strategies for finding the optimal thresholds: grid search (parameter sweep) and random search. For grid search the range of possible thresholds [0.0, 1.0] is divided by n equally distant steps and each threshold is subsequently used for clustering. For the grid search, we do not distinguish between rule-type specific parameters but use a single relation-specific fix parameter thd to limit the search space. Contrary to this, the random search randomly samples the six rule-typespecific thresholds of thd.

heading: 3.2 An Example and its Explanation
text: Figure 1 demonstrates the effect of our algorithm. It has two parts that both illustrate the list of predicted entities for the prediction task genre artist(?, Bryan Adams). The upper half of the figure shows the result of applying the Non-redundant Noisy-OR approach, while the lower part presents the results of the maximum aggregation. In addition to the candidate lists some explanations in terms of the rules or rule clusters that predict these entities are
shown. For the Non-redundant Noisy-OR we depict the two clusters that have the highest maximum confidence. By aggregating these clusters via the Noisy-OR multiplication, the highest rank candidate is Pop rock.
A different result can be observed for the maximum aggregation. The correct entity Pop rock is ranked at the third position, while the first position is occupied by Heavy Metal. The example illustrates nicely that the influence of a single rule can be too strong in the maximum approach, while the Non-redundant Noisy-OR approach allows to aggregate the results in a more meaningful way. This holds in particular if the clusters make sense and combine similar reasons for a prediction within the same cluster. Therefore, in addition to improving predictive performance, our algorithm provides explanations that are easier to understand and that provide deeper insights about the underlying data and the rules derived from them.

heading: 4. Experiments
text: We conducted experiments with three established link prediction datasets, including FB15k237 [Toutanova and Chen, 2015], WN18RR [Dettmers et al., 2018] and YAGO3-10 [Dettmers et al., 2018]. An overview of these datasets can be seen in Table 6. For our experiments we selected only datasets without train-test leakage. We abstained from performing experi-
ments on the parent datasets FB15k (WN18) [Bordes et al., 2013] of FB15k-237 (WN18RR) as they were found to suffer from heavy testing leakage (f.e. some triples in the test data are present as inverse triples in the training data).
Training, inferencing and evaluations were run on a machine with 24 physical (48 logical) Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz cores and 264 GB of RAM. As SAFRAN and AnyBURL do not utilize GPU-accelerated computing, only CPUs were used. For optimal comparison with the best results using the maximum aggregation approach presented in [Meilicke et al., 2020], the same learning parameters were adopted for the same datasets. Rulesets used for the results were learned for 1000 seconds each, using 22 threads. For rules learned from WN18RR the maximum length of cyclic rules was set to 5, while for all other datasets a maximum length of 3 was used. The maximum length of acyclic rules was set to 1 for all datasets. As FB15k-237 contains reflexive triples in the form of r(c, c) a flag was set that allows AnyBURL to use such reflexive triples for learning rules. The same rulesets were used for inference and evaluation with AnyBURL and SAFRAN. Random search was performed using a n of 10 and 10000 iterations, while grid search was performed with a n of 200.
We compare our results with the established latent models RESCAL [Nickel et al., 2011], TransE [Bordes et al., 2013], DistMult [Yang et al., 2015], ComplEx [Trouillon et al., 2016], ConvE [Dettmers et al., 2018], RotatE [Sun et al., 2019], TuckER [Balazevic et al., 2019] and the rule-based methods AMIE+ [Galárraga et al., 2015], RuleN [Meilicke et al., 2018], C-NN [Ferré, 2020], Neural LP [Yang et al., 2017], RLvLR [Omran et al., 2018], DRUM [Sadeghian et al., 2019], GPFL [Gu et al., 2020b]. For details on these approaches we refer to their respective original papers. For each approach we report the filtered mean reciprocal rank (MRR), filtered hits@1 and filtered hits@10, where predicted triples that are already known are filtered out, except the test triple itself. The results for FB15k-237, WN18RR and YAGO3-10 can be seen in Table 7. All results reported by us were evaluated according to the average policy [Rossi et al., 2021] (see Appendix A), where the rank of a target entity within a group of same score entities is the average rank of this group. Reported results from [Rossi et al., 2021], [Ruffinelli et al., 2020] were evaluated using the same protocol. Results of C-NN, GPFL, AMIE+, RuleN were evaluated using ordinal (random) policy which results in very similar results than average policy, while to the best of our knowledge there is no information available about the policy used for evaluating RLvLR. Results of DRUM and Neural LP were evaluated using the top policy which is biased towards producing better evaluations results and cannot be compared directly to other results.
Our aggregation method in the more exhaustive random search outperforms both symbolic and subsymbolic approaches on FB15k-237 and WN18RR. This is a surprising result as both data sets have been used for years to evaluate and improve performance of latent methods that are build on the concept of embeddings. On YAGO3-10 the results are
slightly worse. For this data set ComplEx achieves an MRR that is 0.012 higher. However, AnyBURL together with the Non-redundant Noisy-OR is still among the top performing techniques. With our approach we offer a fully interpretable symbolic approach, that allows to explain the results in terms of the rules that generated them, while we are still able to compete with or even outperform latent approaches. The improvement against the AnyBURL default maximum aggregation technique differs a lot between datasets. While we observe a clear improvement of more than 3% in terms of MRR for FB15k-237, the improvement for the other datasets is around 0.5% to 1%. Currently we do not understand the reason for this differences. The most probable explanation is a lower degree of redundancy in the rules that describe the regularities encoded in these datasets.
Another reason for this may be the small validation set sizes of WN18RR and YAGO310. While the training set of YAGO3-10 is the biggest of the three datasets used in the experiments, the size of its validation set is only 0.46% of the dataset, compared to 6.6% in FB15k-237. However, non-redundant Noisy-OR needs an appropriate sized validation set that represents a broad spectrum of relations and entities to be able to fully recognize redundancies. The validation set size of WN18RR is 3.4% of the dataset. However as the overall dataset is considerably small, the absolute size of its validation set is only 3,134 triples. As rules generated by AnyBURL can generalize to unseen entities [Ferré, 2020], this size may not be sufficient to generate the most optimal clustering.
In our experiments we used two different search techniques. The random search performs better in most cases. As explained above, it learns thresholds that distinguish between different rule types. Thus, only a random selection of all possible threshold combinations is visited during the search. Nevertheless, type-specific thresholds seem to make sense as the results are in most cases slightly better compared to the grid search, which learns a single threshold per relation.
To support our claim that Non-redundant Noisy-OR could potentially be applied to other rule-based approaches, we performed experiments on all used data sets using rules learned by AMIE+. The results can be seen in Appendix F. We used AMIE in its default setting. This means that it mines only cyclic rules. This could be the reason that we observed no or only a very limited improvement on each data sets with the exception of FB15k-237.
To ascertain the importance of optimal thresholds, we performed another experiment. We evaluated each relation in the validation set using Noisy-OR and Maximum aggregation and apply the approach with the maximum MRR of each relation to the test set. Results for the datasets can be seen in Table 7 denoted as VS. All metrics improved compared to the Maximum aggregation but could not achieve the gain of Non-redundant Noisy-OR.

heading: 5. Related Work
text: One of the most prominent rule mining systems is AMIE, which has been described first in [Galárraga et al., 2015] and later, including several extension and improvements in [Lajus et al., 2020]. These papers focus mainly on mining rules (including the confidence computation) rather than their application. This is typical for most rule-mining or inductive logic programming (ILP) papers. The authors touch the topic of how to aggregate confidences only in a single experiment where they compare maximum and the Noisy-OR aggregation. According to their results the Noisy-OR approach works better.
In [Ferré, 2020] another interesting variation of Noisy-OR, the Dempster–Shafer score [Denoeux, 1995], has been applied. This approach is not based on rules, but relies on another symbolic representation using concepts of nearest neighbours. In their experiments the authors found that the aggregation using the Dempster–Shafer score performs at best 1.3 % worse than the maximum score [Ferré, 2020].
It might make sense to decouple the learning of rules from the model used for their application. ProbLogic [De Raedt et al., 2007] offers a well-defined model for applying probabilistic rules to a given set of facts (or triples). ProbLog evaluates probabilistic logic programs by combining Selective Linear Definite clause resolution (SLD-resolution) with methods for computing the probability of Boolean formulae. Using ProbLog for applying the rules learned by a rule miner would be similar to the Noisy-OR aggregation we described above. As ProbLog is based on a model-theoretic notion of entailment, predictions created by a rule might enable other rules to fire, which might again result into further predictions (and so on). While this makes sense from a conceptual point of view, such an approach results in runtime problems for larger datasets.
In [Kuželka and Davis, 2020] the authors proposed Markov Logic as a powerful framework for solving knowledge base completion tasks. Instead of learning rules, the authors propose to learn the weights of a Markov logic network. As a consequence, dependencies
between regularities are modeled in a complex way, which would lead to a non-trivial aggregation of evidences. However, the analysis remains entirely theoretical and, so it is doubtful whether the approach is applicable to larger knowledge graphs.
The concept of rule redundancy is crucial for rule aggregation. If two rules predict the same candidate for the same reason, a Noisy-OR aggregation makes no sense. In [Gu et al., 2020a] a rule hierarchy was used to detect redundant rules. However, the application model is based on the maximum aggregation strategy, which means that the removal has no positive impact on the predictive quality. Indeed, the authors focus their experiments on runtime performance and report about a positive impact without a decrease in the predictive quality.
It is important to understand that the notion of rule redundancy is not limited to logical or extentional equivalence. Approaches to detect equivalent duplicate rules are well known in ILP, and have for example been implemented in QuickFOIL [Zeng et al., 2014]. Instead of that, we have to deal with problems where two rules are only partially or nearly redundant.
We note that there are a few approaches that try to generate post-hoc explanations of predictions made by latent models such as knowledge graph embeddings. However, as opposed to AnyBURL/SAFRAN which provides ad-hoc explanations for every predicted triple, such approaches often fail to find explanations. F.e. the approach proposed in [Zhang et al., 2019] applied to the knowledge graph embedding CrossE can only find explanations for 40% of triples in the test set of the FB15K dataset. Furthermore it is not fully transparent if generated explanations actually represent the reason for a prediction of a latent model.

heading: 6. Conclusion
text: Interpretable models drastically improve the trust and practical utility of predictions, and help to address current concerns about intransparency and unwanted bias in machine learning models. We introduced a novel method for fully interpretable link prediction that yields new state-of-the-art results among interpretable methods and outperforms state-of-the-art embedding models on some of the established benchmarks. Furthermore, our approach provides explanations that reveal clustering patterns in underlying data and derived rulesets. While our approach can significantly improve predictive performance of rule-based approaches, a more in-depth analysis is needed to assess the quality of generated clusters, which we plan to do in future work. We hope that beyond their direct practical utility, our results help to reinvigorate interest into novel rule-based approaches to complement the embedding- and deep learning-based approaches that have been at the center of attention in machine learning research over the past years.

heading: Acknowledgments
text: This work received funding from netidee grant 5171 (’OpenBioLink’).

heading: Appendix A. Evaluation metrics and same score policy
text: We now formally define used metrics in our experiments. Let t = 2 ∗ |T | be the number of prediction tasks in test set T and ranki be the rank of the correct entity in the predicted list of entities for completion task i, then Hits@k and mean-reciprocal rank (MRR) are defined as follows:
Hits@k = 1
t t∑ i=1 1 if ranki < k
MRR = 1
t t∑ i=1 1 ranki
There are multiple policies for dealing with entities that have the same score as the correct entity [Rossi et al., 2021]:
• Top: The correct entity is given the best rank among a group of same score entities.
• Bottom: The correct entity is given the worst rank among a group of same score entities. This policy is the most conservative.
• Average: The rank of the correct entity is the mean rank of all predictions that tie their score with the correct entity.
• Ordinal : The rank of the correct entity is given the rank in which it appears in the group of same score entities. This policy usually corresponds to the random policy.
• Random: The rank of the correct entity is given a random rank of the ranks within the group of same score entities. This policy usually corresponds to the average policy.
When comparing results from different sources it is important to use comparable policies for dealing with same score entities. F.e. results evaluated with the top policy can be artificially boosted and thus they cannot be compared to results evaluated with the ordinal/random or average policy.

heading: Appendix B. Ruleset Statistics

heading: Appendix C. Runtime comparison AnyBURL - SAFRAN
text: Table 9 shows a comparison of the runtimes of AnyBURL and SAFRAN, when inferencing filtered predictions of all relevant rules for each prediction task in the test set of a dataset.
The experiment was performed with 8 physical (16 logical) AMD Ryzen 7 PRO 4750U @ 1700 MHz cores and 16 GB of RAM. SAFRAN could drastically improve the runtime of rule application.

heading: Appendix D. Threshold Statistics

heading: Appendix E. Clustering Statistics
text: Table 11 shows statistics of formed clusters for a selection of relations. As can be seen, the average cluster size varies greatly between relations. Extreme examples are the relations happenedIn where primarily small clusters were formed and isAffiliatedTo where one big cluster and several smaller clusters were formed.

heading: Appendix F. Experiments with AMIE+
text: Table 12 shows the results of Non-redundant Noisy-OR applied to rules learned with AMIE+. Rules were learned with default settings, in which AMIE+ only learns cyclic rules. The results can be seen in Table 12. As with rules learned by AnyBURL, Nonredundant Noisy-OR could achieve the biggest performance gain on the FB15k-237 dataset. However, the gains on other datasets are significantly small due to the restriction of the default setting to only cyclic rules. As the rule set only contains only rules of one type (i.e. cyclic rules), only a grid search was performed with the same settings as in Table 7.

heading: Appendix G. Pseudocode of Non-redundant Noisy-OR
text: Algorithm 1 Non-redundant Noisy-OR: Clustering Input: Set of entities E, Set of relations R, Rule set RS, Thresholds TR of size |R| × 6, Test set T for relation rel in R do . Calculation of clusters of redundant rules
relevantRules ← rules in RS having relation rel in head; for ri in relevantRules do
for rj in relevantRules do similarityMatrix[ri][rj ]← jaccard(ri, rj)
end for end for clusters[rel]← Ø for ri in relevantRules do
visited[ri]← 0 end for for ri in relevantRules do
if visited[ri] = 0 then cluster ← Ø Q← {ri} while Q is not empty do
rj ← Q.dequeue() cluster ← cluster ∪ {rj} visited[rj ]← 1 for rk in relevantRules do
if similarityMatrix[rj ][rk] > TR[rel][type(rj , rk)] then if visited[rk] = 0 then
Q.enqueue(rk) end if
end if end for
end while clusters[rel]← clusters[rel] ∪ {cluster}
end if end for
end for for prediction task t in T do . Application of clusters of redundant rules
for e in E do nrnoisy[e]← 0 end for for cluster in clusters[relation(t)] do
for e in E do maximum[e]← 0 end for for rule in cluster do
predictions← prediction(rule, t) for e in E do
if e ∈ predictions then maximum[e]← max(maximum[e], confidence(rule));
end if end for end for for e in E do
nrnoisy[e]← noisy(nrnoisy[e],maximum[e]) end for
end for end for

Review summaries:
The paper introduces SAFRAN rule application framework to improve upon the existing AnyBURL interpretable rule-based link prediction approach. SAFRAN helps to solve the redundancies that affect the aggregation step in AnyBURL and introduces Non-redundant Noisy-OR (NRNO) to detects and clusters redundant rules before the aggregation step. In several link prediction benchmarks, SAFRAN achieves SOTA performances for rule-based algorithms and in two out of three datasets even beats multiple embedding-based algorithms with good explainability.

This paper studies the problem of link prediction for knowledge graph completion with rule-based methods. Specifically, it builds on a recent strong rule-based method, AnyBURL, for mining rules from a KG, and mainly studies the application of the mined rules. Recognizing the limitations of the Maximum and Noisy-OR rule aggregation strategies used in prior work, this paper proposes SAFRAN, a rule application strategy that clusters rules of the same relation based on their similarity with the hope that redundant rules will be clustered together. The Maximum strategy is then used within each cluster and the Noisy-OR strategy is used to aggregate clusters. Empirical results on FB15K-237, WN18RR, and YAGO3-10 are strong, outperforming embedding-based methods as well as the Maximum and Noisy-OR baselines.