Rules over a Knowledge Graph (KG) capture interpretable patterns in data and various methods for rule learning have been proposed. Since KGs are inherently incomplete, rules can be used to deduce missing facts. Statistical measures for learned rules such as confidence reflect rule quality well when the KG is reasonably complete; however, these measures might be misleading otherwise. So it is difficult to learn high-quality rules from the KG alone, and scalability dictates that only a small set of candidate rules is generated. Therefore, the ranking and pruning of candidate rules is a major problem. To address this issue, we propose a rule learning method that utilizes probabilistic representations of missing facts. In particular, we iteratively extend rules induced from a KG by relying on feedback from a precomputed embedding model over the KG and external information sources including text corpora. Experiments on real-world KGs demonstrate the effectiveness of our novel approach both with respect to the quality of the learned rules and fact predictions that they produce.
Motivation. Rules are widely used to represent relationships and dependencies among
data items in datasets and to capture the underlying patterns in data [
Rule learning has recently been adapted for the setting of Knowledge Graphs
(KGs) [
Rules over KGs are of the form head body , where head is a binary atom and body
is a conjunction of, possibly negated, binary or unary atoms. When rules are automatically
learned, statistical measures like support and confidence are used to assess the quality of
rules. Most notably, the confidence of a rule is the fraction of facts predicted by the rule
that are indeed true in the KG. However, this is a meaningful measure for rule quality only
when the KG is reasonably complete. For rules learned from largely incomplete KGs,
confidence and other measures may be misleading, as they do not reflect the patterns in the
? This poster is accompanying our conference paper [
Suppose we had a perfect oracle for the true and complete KG. Then we could learn even more sophisticated rules such as r3 : livesIn(X ; Y )
worksFor (X ; Z ); hasHeadquarterIn(Z ; Y ); not locatedIn(Y ; USA): This rule would capture that most people work in the same city as their employers’ headquarters, with the USA being an exception (assuming that people there are used to long commutes). This is an example of a rule that contains a negated atom in the rule body (so it is no longer a Horn rule) and has a partially grounded atom with a variable and a constant as its arguments.
Problem. The problem of KG incompleteness has been tackled by methods that (learn
to) predict missing facts for KGs (or actually missing relational edges between existing
entities). A prominent class of approaches is statistics-based and includes tensor
factorization, e.g., [
These kinds of embeddings can complement the given KG and are a potential asset in overcoming the limitations that arise from incomplete KGs. Consider the following gedankenexperiment: we compute embeddings from the KG and external text sources, that can then be used to predict the complete KG that comprises all valid facts. This would seemingly be the perfect starting point for learning rules, without the bias and quality problems of the incomplete KG. However, this scenario is way oversimplified. The embeddings-based fact predictions would themselves be very noisy, yielding also many spurious facts. Moreover, the computation of all fact predictions and the induction of all possible rules would come with a big scalability challenge: in practice, we need to restrict ourselves to computing merely small subsets of likely fact predictions and promising rule candidates.
Our Approach. In this work we propose an approach for rule learning guided by external sources that allows to learn high-quality rules from incomplete KGs. In particular, our method extends rule learning by exploiting probabilistic representations of missing facts computed by embedding models of KGs and possibly other external information sources.
More formally, let G be a KG, then a probabilistic KG P is a pair P = (G; f ) where f is a probability function over the facts (or KGs edges), where we assume f (a) = 1 for each fact a 2 G, which is already known to be true. Our proposal is to learn rules that not only describe the available graph G well, but also predict highly probable facts based on the function f . The key questions here are how to define the quality of a given rule r based on P and how to exploit it during rule learning for pruning out not promising rules. We define a quality measure for rules over probabilistic KGs as a function : (r; P) 7! , where 2 [0; 1]. To measure the quality of r over P we propose: – to measure the quality 1 of r over G, where 1 : (r; G) 7! 2 [0; 1], – to measure the quality 2 of Gr (i.e., G extended with edges derived using r) by relying on Pr = (Gr; f ), where 2: (G0; (G; f )) 7! 2 [0; 1] for G0 G is the quality of extensions G0 of G over the signature of G given f , and – to combine the result as the weighted sum.
That is, we define our hybrid rule quality function (r; P) as follows: (r; P) = (1 ) 1(r; G) + 2(Gr; P) (3) In this formula 1 can be any classical quality measure of rules over complete graphs. Intuitively, 2(Gr; P) is the quality of Gr wrt f that allows us to capture the information about facts missing in G that are relevant for r. The weighting factor , we call it embedding weight, allows one to choose whether to rely more on the classical measure 1 or on the measure 2 of the quality of the extension Gr.
We propose to realize this approach by iteratively constructing rules over a KG and by collecting feedback from a precomputed embedding model, through specific queries issued to the model for assessing the quality of (partially constructed) rule candidates. This way, the rule induction loop is interleaved with the guidance from the embeddings, and we avoid scalability problems. Our machinery is also more expressive than many prior works on rule learning from KGs, by allowing non-monotonic rules with negated atoms as well as partially grounded atoms. Within this framework, we devise confidence measures that capture rule quality better than previous techniques and thus improve the ranking of rules.
Contribution. We propose a rule learning approach guided by external sources, and show how to learn high-quality rules by utilizing feedback from embedding models. We implement our approach and present extensive experiments on real-world KGs, demonstrating the effectiveness of our approach with respect to both the quality of the mined rules and predictions that they produce. Our code and data are made available to the research community at https://github.com/hovinhthinh/RuLES.