Completeness-aware Rule Learning from Knowledge Graphs

1 Introduction

Motivation. Advances in information extraction have led to general-purpose knowledge graphs (KGs) containing billions of positive facts about the world (e.g., [Carlson et al., 2010; Bollacker et al., 2007; Auer et al., 2007; Mahdisoltani et al., 2015]). KGs are widely applied in semantic web search, question answering, web extraction and many other tasks. Unfortunately, due to their wide scope, KGs are generally incomplete. To account for the incompleteness, they typically adopt the Open World Assumption (OWA) under which missing facts are treated as unknown rather than false.

An important task over KGs is rule learning [Galarraga et al., 2015; Gad-Elrab et al., 2016; Sazonau et al., 2015; Wang and Li, 2015; Lisi, 2010; d'Amato et al., 2016], which is relevant for a variety of applications ranging from knowledge graph curation (completion, error detection) [Paulheim, 2017] to data mining and semantic culturonomics [Suchanek and Preda, 2014]. However, since such rules are learned from incomplete data, they might be erroneous and might make incorrect predictions on missing facts. For example, from the KG in Fig. 1 the rule r1 : hasChild(X,Y) ←worksAt(X,Z), educatedAt(Y,Z) could be mined, which states that workers of certain institutions often have children among the people educated there, as this is frequently the case for popular scientists. While r1 is clearly not universal and should be ranked lower than the rule r2 : hasSibling(X,Z) ← hasFather(X, Y), hasChild(Y, Z), standard rule measures like confidence (i.e., conditional probability of the rule's head given its body) incorrectly favor r1 over r2 for the given KG.

∗Full version appeared at ISWC 2017.

Efforts have been put into adding completeness information to databases [Levy, 1996; Etzioni et al., 1997] and recently to knowledge bases [Razniewski et al., 2016; Darari et al., 2013]. This could be done by detecting the concrete numbers of facts of certain types that hold in the real world (e.g., "Einstein has 3 children") exploiting Web extraction or crowd-sourcing [Prasojo et al., 2016; Darari et al., 2016; Mirza et al., 2017]. Such meta-data provides a lot of hints about the KG's topology, and reveals parts that should be especially targeted by rule learning methods. However, surprisingly, to date, no systematic way of making use of such information in rule learning exists.

In this work we exploit meta-data about the expected number of edges in KGs for better assessment of learned rules.

State of the art and its limitations. In [Galarraga et al., 2015] a completeness-aware rule scoring based on the partial completeness assumption (PCA) was introduced. The idea of PCA is that whenever at least one object for a given subject and a predicate is in a KG (e.g., "Eduard is Einstein's child"), then all objects for that subject-predicate pair (Einstein's children) are assumed to be known. This assumption was taken into account in rule scoring, and empirically it turned out to be indeed valid in real-world KGs for some topics. However, PCA inappropriately treats cases, when edges in a graph are randomly missing. Similarly, whether to count absence of contradiction as confirmation for default rules was discussed in [Doppa et al., 2011]. In [Gal´arraga et al., 2017] new completeness data was learned from a KG by taking as ground truth completeness data obtained via crowd-sourcing. The acquired statements were used in a post-processing step of rule learning to filter out violating predictions. However, this kind of filtering does not have any impact on the quality of the mined rules and the incorrect predictions for instances about which no completeness information exists.

Contributions. In this shortened version of our work [Pellissier Tanon et al., 2017] we present an approach that accounts for meta-data about the number of edges that should exist for given subject-predicate pairs in the ranking stage of rule learning. The novel rule ranking measures have been evaluated both on real-world and synthetic datasets, showing that they outperform existing ones both with respect to the quality of the mined rules and the predictions they produce.

2 Preliminaries

Knowledge graphs. Knowledge graphs (KG) represent interlinked collections of factual information, and they are often encoded using the RDF data model [Lassila and Swick, 1999]. The content of KGs is a set of 〈subject predicate object〉 triples, e.g., 〈john hasChild alice〉. For encyclopedic knowledge graphs on the semantic web, usually the open world assumption (OWA) is employed, i.e., these graphs contain only a subset of the true information.

In the following we write triples using binary predicates, like hasChild(john, alice). A signature of a KG G is ΣG = 〈R, C〉, where R is the set of binary predicates and C is the set of constants appearing in G. Following [Darari et al., 2013], we define the gap between the available graph G a and the ideal graph G i , which contains all correct facts over R and C that hold in the real world. An incomplete data source is a pair G = (G a , G i ) of two KGs, where G a ⊆ G i and ΣGa = ΣGi . Note that the ideal graph G i is an imaginary construct whose content is generally not known. What is known instead is to which extent the available graph approximates/lacks information wrt. the ideal graph, e.g., "Einstein is missing 2 children and Feynman none"). We formalize this knowledge as cardinality assertions in Sec. 3.

Rule learning. Association rule learning concerns the discovery of frequent patterns in a data set and the subsequent transformation of these patterns into rules. A conjunctive query Q over G is of the form p1(x1, y1), . . . , pm(xm, ym), where xi and yi are symbolic variables or constants and pi ∈ R are binary predicates. The answer of Q on G is the set Q(G) = {(ν(x1), . . . , ν(xm), ν(y1), . . . , ν(ym)) | ∀i : pi(ν(xi), ν(yi)) ∈ G} where ν is a function that maps variables and constants to elements of C. The support of Q in G is the number of distinct tuples in the answer of Q on G [Dehaspe and De Raedt, 1997].

An association rule is of the form Q1 ⇒ Q2, such that Q1 and Q2 are both conjunctive queries and Q1 ⊆ Q2, i.e., Q1(G ′ ) ⊆ Q2(G ′ ) for any possible KG G ′ . We call Q2 the body of the rule and Q1 its head. In this work we exploit association rules for reasoning purposes, and thus (with some abuse of notation) treat them as logical rules, i.e., for Q1 ⇒ Q2 we write Q2\Q1 ← Q1, where Q2\Q1 refers to the set difference between Q2 and Q1 seen as sets of atoms.

Classical scoring of association rules is based on rule support, body support and confidence. For a rule r : h(X , Y ) ← B where B is a conjunctive query over the variables ⃗Z ⊇ X, Y and/or constants, they are defined in [Galarraga et al., 2015] as:

where #γ : Γ denotes the number of γ that fulfill the condition Γ, and conf (r) ∈ [0, 1].

Example 1. Consider the KG G a in Fig. 1 and the rules r1 : hasChild (X , Y ) ← worksAt (X, Z), educatedAt (Y, Z) and r2 : hasSibling (X , Z ) ← hasFather (X , Y ), hasChild (Y , Z ) mined from it. The body and rule supports of r1 over the KG are supp(B) = 8 and supp(r1 ) = 2 respectively. Hence, we have conf (r1 ) = 28 . Analogously, conf (r2 ) = 16 .

Support and confidence were originally developed for scoring rules over complete data. If data is missing, their interpretation is not straightforward and they can be misleading. In [Galarraga et al., 2015], confidence under the partial completeness assumption (PCA) has been proposed as a measure, which guesses negative facts by assuming that data is usually added to KGs in batches, i.e., if at least one child of John is known then most probably all John's children are present in the KG. Formally, the PCA confidence is defined as

Example 2. We obtain confpca(r1 ) = 24 . Indeed, since carol and dave are not known to have any children in the KG, four existing body substitutions are not counted in the denominator. Meanwhile, we have confpca(r2 ) = 16 , since all people that are predicted to have siblings by r2 already have siblings in the available graph.

Given a rule r and a KG G the application of r on G results in a rule-based graph completion. More formally,

Definition 1 (Rule-based KG completion). Let G be a KG over the signature ΣG = 〈R, C〉 and let r : h(X , Y ) ← B be a rule mined from G, i.e. a rule over ΣG. Then the completion of G is a graph Gr := G ∪ {h(x, y) | ∃⃗Z : B}.

Example 3. We have G a r1 = G a ∪ { hasChild(john, dave), hasChild(carol, mary), hasChild(dave, dave), hasChild(carol, carol), hasChild(dave, bob), hasChild(mary, dave) }.

Note that G i is the perfect completion of G a , i.e., it is supposed to contain all correct facts with entities and relations fromΣGa that hold in the current state of the world. The goal of rule-based KG completion is to extract from G a a set of rules R such that ∪r∈RG a r is as close to G i as possible.

3 Completeness-aware Rule Scoring

Scoring and ranking rules are core steps in association rule learning. A variety of measures for ranking rules have been proposed, with prominent ones being confidence, conviction and lift. The existing (in-)completeness-aware rule measure in the KG context (the PCA confidence (4) [Galarraga et al., 2015]) has two apparent shortcomings: First, it only counts as counterexamples those pairs (x, y) for which at least one h(x, y′ ) is in G a for some y ′ and a rule's head predicate h. Hence, it may incorrectly give high scores to rules predicting facts for very incomplete relations, e.g., place of baptism. Second, it is not suited for data in non-functional relations that is not added in batches, such as awards, where the important ones are added instantly, while others much slower or never.

Thus, in this work we focus on the improvements of rule scoring functions by making use of the extra (in-)completeness meta-data. Before dwelling into the details of our approach we discuss the formal representation of such meta-data.

Cardinality Statements. We represent the (in)completeness meta-data using cardinality statements by reporting (the numerical restriction on) the absolute number of facts over a certain relation in the ideal graph G i . More specifically, we define the partial function num that takes as input a predicate p and a constant s and outputs a natural number corresponding to the number of facts in G i over p with s as the first argument:

These cardinality statements can be obtained using web extraction techniques [Mirza et al., 2017]. With such statements, it is also possible to encode cardinalities on the number of subjects for given predicates and objects, provided that inverse relations can be expressed in a KG.

Naturally, the number of missing facts for a given p and s can be obtained as

Example 4. Consider the KG in Fig. 1. and the following cardinality statements for it:

• num(hasChild, john) = num(hasChild,mary) = 3; num(hasChild , alice)=1; num(hasChild , carol )=num(hasChild , dave)=0;
• num(hasSibling, bob) = 3; num(hasSibling, alice) = num(hasSibling , carol ) =num(hasSibling , dave) =2.

We then have:

• miss(hasChild,mary) = miss(hasChild, john) = miss (hasChild , alice) =1; miss (hasChild , carol ) =miss (hasChild , dave) =0;
• miss(hasSibling, bob)= miss(hasSibling, carol )=2; miss (hasSibling ,alice) = miss (hasSibling ,dave)= 1.

We are now ready to define the completeness-aware rule scoring problem. Given a KG and a set of cardinality statements, completeness-aware rule scoring aims to score rules not only by their predictive power on the known KG, but also wrt. the number of wrongly predicted facts in complete areas and newly predicted facts in known incomplete areas.

In the following we discuss and compare two novel approaches for completeness-aware rule scoring. These are (i) the completeness confidence, and (ii) directional metric. Henceforth, all examples consider the KG in Fig. 1, rules from Ex. 1, and cardinality statements described in Ex. 4.

3.1 Completeness Confidence

In this work we propose to explicitly rely on incompleteness information in determining whether to consider an instance as a counterexample for a rule at hand or not.

To do that, we first define two indicators for a given rule r : h(X , Y ) ← ⃗B, reflecting the number of new predictions made by r in incomplete (npi(r)) and, respectively, complete (npc(r )) KG parts:

(8)

Note that summation is done exactly over those entities for which miss is defined. Exploiting these additional indicators for r : h(X, Y ) ← ⃗B we obtain the following completenessaware confidence:

Example 5. The rule r2 matches more the real world than r1 and, so, should be preferred over it. For our novel completeness confidence, we get confcomp(r1 ) = 26 and confcomp(r2 ) = 1 2 , resulting in the desired rule ordering, not achieved by existing measures (see Ex. 1 and 2).

Under the closed world assumption confcomp(r) = conf(r) because ∀x : miss(h, x) = 0. Similarly, under the partial completeness assumption confcomp(r) = confpca(r). Thus, our completeness confidence is a more general measure than both the standard and the PCA confidence.

3.2 Directional Bias

If rule mining does make use of completeness information, and both do not exhibit any statistical bias, then intuitively the rule predictions and the (in)complete areas should be statistically independent. On the other hand, correlation between the two indicates that the rule-mining is (in)completeness-aware.

Example 6. Suppose in total a given KG stores 1 million humans, and we know that 10,000 (1%) of these are missing some children (incompleteness information), while we also know that 1000 of the persons are definitely complete for children (0.1%). Let the set of rules mined from a KG predict 50,000 new facts for the hasChild relation. Assuming independence between predictions and (in)completeness statements, we would expect 1% out of 50,000, i.e., 500 facts to be predicted in the incomplete areas and 0.1%, i.e., 50 in the complete KG parts. If instead we find 1000 children predicted for people that are missing correspondingly many children, and 10 for people that are not missing these, the former deviates from the expected value by a factor of 2, and the latter by a factor of 5.

Following the intuition from the above example, we propose to look at the extent of the non-independence of completeness information and rule mining to quantify the (in)completenessawareness of rule mining. Let us consider predictions made by rules in a given KG, and denote by enpi(r) and enpc(r) the expected numbers of facts added by the rule r in the incomplete and complete areas respectively. Then for α ∈ [0, 1] being the weight given to completeness versus incompleteness, the directional coefficient of r is defined as follows:

Unlike the other measures that range from 0 to 1, the directional coefficient takes values between 0 and infinity, where 1 is the default. The higher the directional coefficient is, the more "completeness-aware" the rules are.

In practice, expected values might be difficult to compute, and statistical independence is a strong assumption. An alternative that does not require knowledge about expected values is to directly measure the proportion between predictions in complete and incomplete parts. We call this the directional metric, which is computed as

The metric is similar to the directional coefficient, but does not require knowledge about the expected number of predictions in complete/incomplete KG parts. It is designed to range between 0 and 1 again, thus allowing convenient weighting with other [0, 1] measures. The directional metric of a rule that predicts the same number of facts in incomplete as in complete parts is 0.5, a rule that predicts twice as many facts in incomplete parts has a value of 0.66, and so on.

We propose to consider the combination of a weighted existing association rule measure, e.g., confidence or lift and the directional metric, with the weighting factor β = 0..1. Using confidence, we obtain

Example 7. It holds that direct metric(r1 ) ≈ 0.33 and direct metric(r2 ) = 0.8. Moreover, for confidence we get wdm(r1 ) ≈ 0.29 and wdm(r2 ) ≈ 0.48 with β = 0.5.

4 Evaluation

We have implemented our completeness-aware rule learning approach in a C++ system prototype CARL 1 , following a standard relational learning algorithm implementation such as [Goethals and den Bussche, 2002].

We restrict the search space by mining rules of the form

We aim to compare the predictive quality of the top k rules mined by our completeness-aware approach with the ones learned by standard rule learning methods: (1) AMIE [Galarraga et al., 2015] (PCA confidence) and (2) WarmeR [Goethals and den Bussche, 2002] (standard confidence).

1 The source code and all the data are available at https: //github.com/Tpt/CARL.

• Standard confidence

PCA confidence Directional metric

• Completeness confidence Weighted directional metric

Figure 2: Evaluation results for WikidataPeople and LUBM datasets

Dataset. We used two datasets for the evaluation: (i) WikidataPeople, which is a dataset we have created from the Wikidata knowledge graph, containing 2.4M facts over 9 predicates about biographical information and family relationships of people; and (ii) LUBM, which is a synthetic dataset describing the structure of a university [Guo et al., 2011].

For the WikidataPeople dataset, the approximation of the ideal KG (G i ) is obtained by applying solid rules from the family domain. We acquired cardinality statements using data from Freebase [Pellissier Tanon et al., 2016] and hand-crafted rules relying on the PCA [Galarraga et al., 2015] assumption. This resulted in 10M cardinality statements.

LUBM G i , with 1.2M facts, was constructed by running the LUBM data generator. 464K cardinality statements were obtained by assuming the PCA on the whole dataset.

Experimental Setup. To assess the effect of our proposed measures, we first construct versions of the available KG (G a ) by removing parts of the data from G i and introducing a synthetic bias in the data (i.e., leaving many facts in G a for some relations and few for others). The synthetic bias is needed to simulate our scenario of interest, where some parts of G a are very incomplete, while others are fairly complete, which is indeed the case in real world KGs. In Wikidata, for instance, 2.7% of all humans have an assertion about their father, yet only 0.8% have an assertion about their mother.

We proceed in two steps: First, we define a global ratio, which determines a uniform percentage of data retained in the available graph. To further refine this, we then factor a predicate ratio individually for each predicate.

For a given predicate, the final ratio of facts in G a retained from those in G i is then computed as min(1, 2 · k · n), where k is the predicate ratio and n is the global ratio.

The assessment of the rules learned from different versions of the available KG is performed by comparing rule predictions with the approximation of G i . More specifically, every learned rule is assigned a quality score, defined as:

This scoring naturally allows us to control the percentage of rule predictions that hit our approximation of G i , similar to standard precision estimation in machine learning.

Results. From every version of the available KG we have mined rules of the form (13) and kept only rules r with conf (r) ≥ 0.001 and supp(r) ≥ 10, whose head coverage (ratio of the number of predicted facts that are in G a over the number of facts matching the rule head) is greater than 0.001.

Evaluation results for WikidataPeople and LUBM datasets are in Figure 2. The horizontal axis displays the global ratio used for generating G a . The Pearson correlation factor (vertical axis) between each ranking measure and the rules quality score (14) is used to evaluate the measures' effectiveness.

For the WikidataPeople KG, directional metric, weighted directional metric and completeness confidence show the best results. For the LUBM KG, the completeness confidence outperforms the rest of the measures, followed by the standard confidence and the weighted directional metric.

5 Conclusion

We have defined the problem of learning rules from incomplete KGs enriched with the exact numbers of missing edges of certain types, and proposed several novel rule ranking measures that effectively make use of the meta-knowledge about complete and incomplete KG parts: completeness confidence and the (weighted) directional metric. Our measures have been injected in the rule learning prototype CARL and evaluated on real-world and synthetic KGs, demonstrating significant improvements both with respect to the quality of mined rules and predictions they produce.