Rule-Based Knowledge Graph Completion

There exist different evaluation protocols in the literature of how to measure the quality of a model in regard to its ability to perform KGC. Intuitively, one could simply define a classification problem in which positive facts need to be classified as true and negative facts as false. However, as discussed above, the KG does not contain negative examples. When sampling negative facts from all possible facts $ℰ\times 𝒫\times ℰ$, a large number of samples would describe useless statements such as $speaks(obama,europe)$. It turns out that these are too easy for many models leading to partly meaningless evaluation results.

In this work, we will focus on ranking-based protocols instead. They can be employed by exclusively using true facts and are based on the idea that a model should rank correct facts on top of all other non-existing facts without making a particular truth statement about them. Yet, they come with an intricacy in that they are based on answering queries opposed to directly predicting the truth values of target facts. These queries are formed from known facts, as shown in the following example.

Clearly, a query does not necessarily have to be based on an existing fact. We will nevertheless stick with this convention as it aligns with the practical procedure of the protocol that will be introduced in the following paragraphs. To this end, we assume that two queries are formed from a true base fact, one in tail direction and one in head direction as shown in the example. While there may be multiple correct answers to each of the queries, the base fact provides one true answer for each direction. For a given query, we require an ordered list of answer proposals, i.e., a ranking of candidate entities from the KG.

If the ranking is with respect to a head (tail) query, we call it a head (tail) ranking. We will equivalently also sometimes refer to the head direction or the tail direction of a ranking. Table 2 shows an example for a head and a tail ranking regarding queries formed from a base fact. We added some more languages in regard to the KG given in Figure 1. We have not yet discussed how a model or rule-based approach can create such a ranking and we will see in later sections that candidates are ranked by predicting scores for the respective triples. For the current discussion, it is enough to consider that a candidate that is ranked on top of another candidate is also more plausible. For example, in Table 2, the entity $anna$ is predicted as the most plausible answer in the tail ranking.

The standard procedure for ranking-based protocols is to filter rankings with all the known facts (except of the known current answers). This is done to not penalize models erroneously.

Commonly the original set of facts is split into training, validation and testing subgraphs. Then, all the known facts are given by the union and therefore the filtering is performed by using the facts of all the three subgraphs. Table 3 shows the filtered rankings when the filtering is applied to Table 2. In this case, we assume that the facts $speaks(bernd,german)$ and $speaks(lisa,english)$ are known and therefore the answers $german$ for the tail query and $lisa$ for the head query are filtered out. We can observe that the position of the true answer $english$ in the tail ranking moved from four to three and likewise in the head ranking the position of $bernd$ moved from three to two.

For calculating ranking-based metrics for KGC, we need to collect the ranking positions of the true answers after filtering. Therefore, we will now formally define the ranking position of an entity in a ranking.

With these definitions we can describe the final evaluation protocol that is used for estimating model quality in regard to KGC.

Let $𝒢$ denote here the facts of a test KG. Let us assume that we are given the filtered rankings for all queries based on the facts of $𝒢$ and let the definitions from the previous section apply. Then we have,

Where $\mathrm{𝙸𝚗𝚍}\{..\}$ is an indicator that evaluates to one if the condition in the braces is true and it evaluates to zero otherwise. In the definitions $q^s(q^o)$ refers to the tail (head) query based on fact $p(s,o)$ where we dropped the reference to the fact for brevity.

The MR is simply the average of all the ranking positions of the correct answers. The MRR is closely related. It is between zero and one (higher is better) and it gives higher weights for better ranking positions. For instance, an improvement by one position has higher effect on the MRR if the improvement is from position two to one compared to an improvement from 100 to 99. The Hits@k metrics measures in how many percent of rankings the true answer was within the top-k candidates. The Hits@1 metric can also be interpreted as the multi-class accuracy. The section is concluded with an example regarding the defined metrics.

The above sketch of our approach looks similar to the algorithm implemented in Aleph [49]. However, Aleph uses the bottom rule to define the boundaries of a top-down search. It begins with the most general rule and uses the atoms that appear in the bottom rule to create a specialization lattice. A specialization lattice is a directed graph where each node is a rule and an edge from $r$ to $r^{\prime }$ denotes that $r^{\prime }$ is more special than $r$. While in a specialization hierarchy each rule $r^{\prime }$ has only one more general $r$ rule as parent node, in a lattice $r^{\prime }$ might have several more general rules that are specialized by $r^{\prime }$.

Similarly, AMIE [17, 16] also does a top-down search, which in contrast to Aleph is complete because it does not limit which atoms to use to specialize a rule. Our approach differs fundamentally from both algorithms because we instantiate a set of rule patterns that results exactly in the beneficial subset of those rules that we would collect by creating a generalization lattice beginning from the bottom rule. In a generalization lattice every child rule is more general than the parent rule. We argue in the following that all relevant rules within the generalization lattice instantiate one of the rule types defined in the previous section. Based on this insight, we can directly instantiate these rule types without the need to create the complete lattice.

To find rules for a fixed relation, AnyBURL samples triples of that relation from the training set, and creates rules from them. Even though we do not know all the details of the overall algorithm yet, we can already conclude that AnyBURL’s search is obviously not complete. AMIE, on the other hand, will generate all rules that fulfill the quality criteria defined in the chosen settings. Thus, it can be described as a complete search. The incompleteness of our approach seems to be a significant drawback, however, we will later argue that it helps to detect the most important rules quickly at the beginning of the search. AMIE, on the other hand, might, for very large datasets not be able finish within an acceptable time frame, as it needs to construct all possible rules systematically.

Figure 2 shows a small subset of a knowledge graph $𝒢$. We use it to demonstrate how rules for the relation speaks can be learned. We construct a bottom rule of length $n$ starting with the edge that corresponds to $speaks(ed,d)$. This triple will be the head of the rule. To do this, we randomly walk $n$ steps in the graph, starting either from $ed$ or $d$. Together with the head triple, the result is a path of length $n+1$. In Figure 2, we have marked three paths that could be found for $n=2$ or $n=1$, respectively. The green and blue paths are acyclic, while the red path, including $speaks(ed,d)$, is cyclic. We convert these paths into the bottom rules (16), (17), and (18) given below.

So far, we explained the sketch of the path sampling procedure with an example. The details will be discussed in the following. In the paths that we sample for building bottom rules, each triple on a path is called a step. The steps can be made in the direction of a stated triple or in reverse direction. A step in reversed direction causes flipped terms in the corresponding atom of the resulting rule. Let $c_0$ to $c_n$ be the entities on a path. We call such a path an acyclic path if it does not visit the same entity twice, i.e., $c_i\ne c_j$ for each $i\ne j$. A path is a closed path if $c_0=c_n$ and $c_i\ne c_j$ for each of the remaining pairs of nodes. Such a path forms a cycle, as it ends where it began, and it does not contain any inner cycles.

A closed path results into a binary $𝐁$ rule and a special form of a ${𝐔}_{𝐜}$ rule where the constant in the head and body of the rule is the same. An acyclic path results into a ${𝐔}_{𝐜}$ rule (with different constants in head and body) and a ${𝐔}_{𝐝}$ rule. Our method to sample a path is to choose a random entity as a starting point of a random walk. This approach differs from randomly selecting a starting triple $r(c_0,c_1)$, which would favor entities that are used more often. Within the random walk, we randomly select one of the edges that the current node is involved in, i.e., we consider both in- and outgoing edges. Each of these edges is selected with the same probability. Then we follow the edge to the node that is connected to the current node and continue from that node.

If the walk arrives at an entity that has been visited before (prior to the last step), the procedure can be restarted until an acyclic or closed path has been found. It can be expected that the majority of sampled paths will be acyclic. Especially for longer paths it will not often be the case that $c_0=c_n$. This means that a pure random walk strategy will generate only few binary rules. This can be a problem for the resulting rule sets. According to the results presented in [33, 31] we know that a large fraction of correct predictions can be made with $𝐁$ rules.

Thus, it makes sense to design a specific strategy to search for closed paths. We have slightly modified the random walk strategy by explicitly looking for a fact that connects $c_{n-1}$ and $c_0=c_n$ in the last step. With an appropriate index it is possible to check the existence of a relation $p$ with $p(c_i,c_j)$ in constant time for any pair of constants. If we find such a triple, we use this as a final step in the constructed path. If we find several such triples, we pick randomly one of them. With this modification, we are able to find more closed paths in the same time span compared to the standard random walk. We are aware that there are more sophisticated methods for finding a closed path of length $n$, see for example [41]. We might also compute paths up to a certain length using the Floyd-Warshall algorithm in a preprocessing step. However, for our purpose a simple modification of the random walk procedure is sufficient.

We argue in the following that any generalization of a path of length $n+1$ will be a $𝐁$, ${𝐔}_{𝐜}$ or ${𝐔}_{𝐝}$ rule of length $n$ or a shorter rule, which can be constructed from a shorter path, or a rule that is not useful for making a prediction. We elaborate this point by analysing the generalization lattice rooted in Rule (17), depicted in the lower part of Figure 3. Note that AnyBURL does not compute the lattice, but directly instantiates that types of rules that we highlighted within the lattice using a yellow background color.

Each child node in the lattice results from one of two generalization operations.

1. 1.

   Replace all occurrences of a constant by a fresh variable.

2. 2.

   Drop one of the atoms in the body.

Note that we have only depicted those rules in the lattice that have at least one variable in the head. If this would not be the case, the rule would only predict a triple that is already stated in the knowledge graph, which is useless for completion. Not all rules that appear in the lattice are useful in the context of the overall algorithm. We highlighted the beneficial rules in Figure 3 with a yellow background color. The remaining rules, which are not instantiated by our algorithm, belong to one of the categories described in the following paragraph. We have associated the symbols $†$, $\ast$, and $\diamond$ to these categories and used them to mark the nodes in Figure 3.

Ambiguous prediction^†

The rule has an unconnected variable in the head, which does not appear in the body of the rule. Such a rule makes a prediction that something exists without exactly specifying what it is. Thus, it cannot be used to create a ranking of candidates. An example would be a rule such as $gender(X,Y)\leftarrow lives(X,usa)$, which states that an entity that is born in USA has a gender. If we have a query as $gender(john,\mathrm{?})$ the rule is not helpful at all, no matter where $john$ lives.

Shorter bottom rule^∗

The rule might be useful, but it would also appear in the lattice of a bottom rule which originates from a shorter path. This point is detailed in Section 4.2.5, where we introduce the notion of a path profile which determines the length of the bottom rules. We will see that each path profile has an associated reward in the context of the overall algorithm, which is computed by summing up the reward of each rule that stems from this profile. By suppressing shorter rules, we enforce that each rule can be uniquely assigned to its path profile and will only be created from shorter paths.

Useless atom^⋄

The body contains an atom without variables or an atom with a constant and a variable that appears in none of the other body atoms and also not in the head atom. Such atoms will always be true in the knowledge graph from which they were sampled and therefore do not affect the truth value of the body. These rules need to be generalized further. This can be done by dropping the specific atom, which results directly into a shorter rule, or by replacing a constant by a variable.

Note that a rule in the lattice marked with a ^† or ^∗ does not need to be generalized any further, because any resulting rule will be marked again with the same symbol. As already stated above, we depicted the relevant rules within the lattice to emphasise that the approach of AnyBURL is in that sense complete that it constructs all generalizations, which can be used to make a new prediction, by directly instantiating these rule types instead of setting up the full lattice.

Confidence and support have been introduced in Section 3 as standard metrics for measuring the quality of a rule. By repeating the steps described above multiple times, AnyBURL constructs a high number of rule candidates. However, AnyBURL stores only those rules that have a confidence and support above or equal to a certain threshold. This means that we have to compute the confidence scores for a very large number of rules. With respect to our example these are the rules marked with a yellow background.

It is expensive to precisely compute the confidence of a rule. Starting from the first atom in the body, any further body atom requires to compute a join on the variable that this atom shares with the previous atom. Moreover, since we are using the principle of object identity, we cannot ignore to which entities the join variables were bound, because these entities are not allowed as possible values for the other variables. For that reason it makes sense to approximate the confidence measure by drawing a sample of all body instantiations.

The most straight forward way to do this is to apply a depth first search (DFS) over body groundings. This strategy has been applied in the previous version of AnyBURL [31]. Given a $𝐁$ rule, it picks a random grounding of a head variable and follows via a DFS the chain of relations in the body collecting all groundings of the other head variable. This is done until a sufficient number of body groundings have been sampled. Meanwhile, the sampling procedure has been modified. A DFS based search suffers from the problem that, if a hub entity as usa, female or berlin is visited, all (or most) sampled paths might pass through this hub entity and the confidence of a rules as $h(X,Y)\leftarrow b_1(X,A),b_2(A,B),b_3(B,Y)$ might be estimated as the confidence of the more specific pattern $h(X,Y)\leftarrow b_1(X,usa),b_2(usa,B),b_3(B,Y)$. Therefore, the confidence would not inform about the general regularity.

Thus, we implemented a different sampling technique shown in Algorithm 1. This algorithm describes the procedure that we apply to approximate the confidence of $𝐁$-rules. We assume that the input to Algorithm 1 is a rule of the form $h(A_0,A_n)\leftarrow b_1(A_0,A_1),\mathrm{\dots },b_n(A_{n-1},A_n)$. The actual algorithm is a bit more complicated as it has to deal with flipped positions of $A_{i-1}$ and $A_i$, which can be handled easily with some additional case distinctions. We divided the algorithm into two functions. The first function determines the starting points for the search, while the second function uses these starting points to search for a full grounding of the atoms that are chained via variables $A_0$ to $A_n$. The starting points of the search are possible substitutions of variable $A_0$. They are collected in the set $𝕏$. As we use a set, each possible value appears only once. This means that an entity that appears quite often at the subject position of $b_1$ is not preferred over an entity that appears rarely in that position.

The algorithm uses elements $x$ from $𝕏$ repeatedly to find pairs $⟨x,y⟩$ that are the endpoints of a path that results in a body grounding of the given rule. There are several conditions and parameters that define when to stop this process. Parameter ${\text{max}}_{\alpha }$ determines the overall numbers of attempts to find a $⟨x,y⟩$ pair no matter if this attempt has been successful or not. Another stopping criteria is related to the number of pairs in $\mathrm{\Phi }$ found so far. If this number reaches the boundary ${\text{max}}_{\mathrm{\Phi }}$ the sampling process stops. The third criteria is an additional condition that allows to stop the sampling process early if repeatedly a pair is sampled that we found already previously. We count how often this happens in $\beta$, which is reset to $0$ whenever a new pair has been found. The default values for ${\text{max}}_{\beta }$, ${\text{max}}_{\mathrm{\Phi }}$, and ${\text{max}}_{\alpha }$ are 5, 1000 and 100000 respectively.

The beam-function (lines 22–39) searches for a path that leads from $x$, which is a substitution of $A_0$, over the chain of body relations to a substitution of $A_n$. It can be understood as an extreme form of a beam search, which selects candidates completely randomly and retains in each step only one candidate. Lines 23 to 27 are responsible for checking the OI constraints. As no variable appears twice in the subject position of the body atoms, we can simply check if the current entity stored in $v$ is amongst one of the previously visited $v$-values. We use this function repeatedly until we constructed a set of pairs $\mathrm{\Phi }$ as output of the algorithm. Now we have to check for each of these pairs $⟨x,y⟩\in \mathrm{\Phi }$ if it results in a grounding for the head of $r$. In particular, we approximate the confidence of the rule as the fraction of pairs in $\mathrm{\Phi }$ for which $h(x,y)\in 𝒢$ holds.

The algorithm can be easily modified to be applicable to ${𝐔}_{𝐜}$ and ${𝐔}_{𝐝}$-rules. Each of these rules uses only one variable in the head. Thus, we need to store a set of single values in $\mathrm{\Phi }$ instead of pairs. The beam-function needs to be modified to return a truth value that is true if a body grounding for a specific $x$ value has been constructed and false otherwise. If it was possible to construct a body grounding, the $x$ value is stored in $\mathrm{\Phi }$. Algorithm 1 makes it possible to approximate confidences values for very large knowledge bases were the exact computation of the confidence of a long $𝐁$ rule might require to construct an enormous amount of body groundings.

Up to now, we know that the main loop of AnyBURL samples paths, converts them into rules, and esimates their confidences. Rules that have a confidence above a certain threshold are stored and can later be used to predict missing triples. However, there are different types of paths and, thus, when calling the path samplig procedure we need to specify two parameters. Paths can vary in their length and we can distinguish between cyclic and acyclic paths. In the following we use the notion of a path profile. A path profile determines the length of a path and whether it is a cyclic or acyclic path. In each iteration of the main loop, we have to decide from which profile to sample paths. AnyBURL updates the policy that selects the path profiles after a certain time span. In the default setting this happens every five seconds. Moreover, on most computing devices AnyBURL will run several threads in parallel. Thus, AnyBURL needs to decide for each time span how to distribute the different path profiles over the available threads.

In the following we consider the path sampling problem as a special kind of multi-armed bandit problem [22]. This means that we have to decide about the policy that guides the overall process and how to quantify the reward associated to a learned rule. A path profile in our scenario corresponds to an arm of a bandit in the classical reinforcement learning setting. Each arm (or slot machine) in the bandit problem gives a reward when pulling that arm. The reward of pulling an arm corresponds in our scenario to the reward of creating rules from the paths that belong to a certain profile.

In [30], we developed different reward strategies. All of them are based on the notion of measuring the reward paid out by a profile in terms of the explanatory quality of the rules that were created by that profile. The explanatory quality of a rule set can, for example, be measured in terms of the number of triples of a given knowledge graph that can be reconstructed with the help of the rules from the set. Thus, summing up the support of the rules seems to be a well suited metric. Another reward strategy is based on the multiplication of the number of correct predictions by their confidence. In an extension of that reward strategy, the rule length can be taken into account to favour short rules over longer rules. This reward strategy is the default setting of AnyBURL. Experimental results showed that all of these strategies work well and there are only slight differences with respect to the predictive quality of the learned rule set.

All of these reward strategies can be combined with one of the following two policies. The first policy is a well known policy referred to as $ϵ$-greedy policy [52]. The parameter $ϵ$ is usually set to a relatively small positive value, for example $ϵ=0.1$. Every time a decision needs to be made, that decision is a random decision with a probability $ϵ$ and a greedy decision with a probability $1-ϵ$. When we talk about decisions, we mean the allocation of threads to path profiles. In the $ϵ$-greedy policy, a small number of decisions is randomized to reserve a small fraction of the available resources for exploration compared to an approach that would focus completely on exploitation.

In our context, a greedy decision assigns all cores, that have not been assigned randomly, to the path profile that generated the rule set that yielded the highest reward the last time it has been selected. This approach only be applied if there is a previous time span for each profile where that profile has achieved a reward. This is obviously not the case in the first time span $t_1$. For that reason we associate $\mathrm{\infty }$ as reward to each profile for an artificially introduced time span $t_0$. This results into a random selection in $t_1$ and ensures that each profile has been chosen once after the first few time spans have passed.

Note that our scenario differs from the classical multi-armed bandit setting in the sense that the expected reward of a certain profile will decrease any time we use this profile for generating rules. The more often we use that profile, the more probably it is to draw a path that results into a previously learned rule, which was created from the same or from a different path.¹¹1In Section 4.2 of [30] we explained that AnyBURL uses a canonical rule representation. While it is in principle a non-trivial problem to decide if two rules are equivalent, this is not the case for the language bias of AnyBURL. Thus, we can check in constant time if we found an equivalent rule in an earlier step. For that reason we do not base our decision on the average of all previous time spans, but look at the last time span that this profile has been used. The reward of a profile is shrinking continuously, with random ups and downs that are caused by drawing only a limited number of path samples. This results into flips between different profiles which are not caused by knowing more (exploration) but by the impact of exhausting profiles over time.

The $ϵ$-greedy policy might not be a good choice if some profile $\mathrm{𝑝𝑓}$ creates higher rewards than another profile ${\mathrm{𝑝𝑓}}^{\prime }$, however, ${\mathrm{𝑝𝑓}}^{\prime }$ would also generate relatively good rules that could be used to make correct predictions. Suppose further that both profiles are relatively stable, i.e., their reward decreases only slightly when they are used for generating rules. In such a setting, we might prefer to draw rules not only from path profile $\mathrm{𝑝𝑓}$ but also from ${\mathrm{𝑝𝑓}}^{\prime }$. For that reason we propose a second policy where we distribute the available computational resources to all profiles proportional to the reward that has been observed the last time they have been used. We refer to this policy as weighted policy. The weighted policy is the default setting of AnyBURL.

AnyBURL uses in its default setting the weighted policy and distinguishes between five path profiles: Cyclic paths of length two to four to generate $𝐁$ rules of length one to three, acyclic paths of length two to generate ${𝐔}_{𝐜}$ and ${𝐔}_{𝐝}$ rules with only one body atom, and paths of length one to sample ${𝐔}_{𝐳}$ rules. Figure 4 illustrates a typical behaviour. We omitted acyclic paths of length one for generating this visualisation as this path profile is always fully exhausted after a few time steps. We also modified the default setting by updating the policy every second. The upper part show the greedy policy, which focuses on cyclic paths of length two for the first ten seconds. After a mixed phase, where the algorithm flips between different profiles, the algorithm focuses mainly on acyclic paths of length 2 from second 100 to 10000. The weighted policy, which is depicted below the bar of the greedy approach, shows a similar behaviour.

An easy approach is given by defining the final score as highest confidence of all the rules that predicted a fact. We always assume in the following that a reference KG $𝒢$ and a learned set of rules $ℛ$ are given. Likewise, as above, $t$ is a target fact and ${ℛ}_{𝒢}(t)$ denotes the set of rules that predict $t$.

Max-aggregation was first used in the context of KGC by Galárraga et al. [16]. Clearly, only one rule contributes to the final score. This will naturally result in many ties, i.e., many facts or candidates are assigned with the same score as we argued in [31]. Therefore, when a ranking of candidates is desired, Max-aggregation can be adjusted to Max+ aggregation which takes into account more than one rule for the discrimination of candidates.

For the Max+ strategy, like in Max-aggregation, the predicting rule with the highest confidence still is of highest importance. For example, a prediction made by only one rule with confidence 0.8 would be ranked on top of a prediction that is made by hundreds of rules with a confidence of 0.6. Empirically, the adaption from Max-aggregation to Max+ has a strong effect on predictive performance in the context of KGC.

If smaller sets of rules are learned, it can be beneficial to take all rules into account that predicted the target fact.

The Noisy-or product originates from Bayesian networks where it is used to express independent causes [42] and it was proposed by Galárraga et al. [16] for KGC. The empirical robustness of Noisy-or aggregation depends largely on the rule redundancies present in the learned set of rules as the score for a fact increases by construction in the number of predicting rules. In cases where many rules are learned and many redundancies exist, the aggregation function might perform relatively poor. This can be mitigated, however, by only allowing for a fixed number of confidences of the predicting rules: the top-h number of confidences [6].

It is easy to see that Noisy-or top-h constitutes a compromise between Max-aggregation and Noisy-or aggregation. The score calculated with Noisy-or top-h will always be equal or larger compared to the Max-aggregation score and it will be smaller or equal compared to the Noisy-or score. This is especially beneficial as we already discussed that Max-aggregation will likely provide an underestimation and Noisy-or an overestimation of the predicted score. We will conclude this section with an example containing all the previously defined aggregation functions.