Link discovery plays a key role in the integration and use of data across RDF knowledge graphs. Active learning approaches are a common family of solutions to address the problem of learning how to compute links from users. So far, only active learning from perfect oracles has been considered in the literature. However, real oracles are often far from perfect (e.g., in crowdsourcing). We hence study the problem of learning how to compute links across knowledge graphs from noisy oracles, i.e., oracles that are not guaranteed to return correct classi cation results. We present a novel approach for link discovery based on a probabilistic model, with which we estimate the joint odds of the oracles' guesses. We combine this approach with an iterative learning approach based on re nements. The resulting method, Ligon, is evaluated on 11 benchmark datasets. Our results suggest that Ligon achieves more than 95% of the F-measure achieved by state-of-the-art algorithms trained with a perfect oracle.
The provision of links between knowledge graphs in RDF3 is of central
importance for numerous tasks on the Semantic Web, including federated queries,
question answering and data fusion. While links can be created manually for
small knowledge bases, the sheer size and number of knowledge bases commonly
used in modern applications (e.g., DBpedia with more than 3 106 resources)
demands the use of automated link discovery mechanisms. In this work, we focus
on active learning for link discovery. State-of-the-art approaches that rely on
active learning [
mons License Attribution 4.0 International (CC BY 4.0)."
not impossible to uphold in real-world settings (e.g., when crowdsourcing training data). No previous work has addressed link discovery based on oracles that are not perfect.
We address this research gap by presenting a novel approach for learning
link speci cations (LS) from noisy oracles, i.e., oracles that are not guaranteed
to return correct classi cations. This approach is motivated by the problem of
learning LS using crowdsourcing. Previous works have shown that agents in real
crowdsourcing scenarios are often not fully reliable (e.g., [
The contributions of this paper are as follows: (1) We present a formalization of the problem of learning LS from noisy oracles. We derive a probabilistic model for learning from such oracles. (2) We develop the rst learning algorithm dedicated to learning LS from noisy data. The approach combines iterative operators for LS with an entropy-based approach for selecting most informative training examples. In addition, it uses cumulative evidence to approximate the probability distribution underlying the noisy oracles that provide it with training data. Finally, (3) we present a thorough evaluation of Ligon and show that it is robust against noise, scales well and converges with 10 learning iterations to more than 95% of the average F-measure achieved by Wombat|a state-of-the-art approach for learning LS|provided with a perfect oracle. 2
Knowledge graphs (also called knowledge bases) in RDF are de ned as sets of triples K (R [ B) P (R [ B [ L), where R is the set of all resources, i.e., of all objects in the domain of discourse (e.g., persons and publications); P R is the set of all predicates, i.e., of binary relations (e.g., author); B is the set of all blank nodes, which basically stand for resources whose existence is known but whose identity is not relevant to the model and L is the set of all literals, i.e., of values associated to datatypes (e.g., integers).4 The elements of K are referred to as facts or triples. We call the elements of R entities or resources.
The link discovery task on RDF knowledge graphs is de ned as follows: Let S and T be two sets of resources, i.e., S R and T R. Moreover, let r 2 P be a predicate. The aim of link discovery is to compute the set M = f(s; t) 2 S T : r(s; t)g. We call M a mapping. In many cases, M cannot be computed directly and is thus approximated by a mapping M 0. To nd the set M 0, declarative
link discovery frameworks rely on link speci cations (LS), which describe the
conditions under which r(s; t) can be assumed to hold for a pair (s; t) 2 S T .
Several formal models have been used for describing LS in previous works [
LS consist of two types of atomic components: similarity measures m, which allow the comparing of property values of input resources and operators op, which can be used to combine LS to more complex LS. Without loss of generality, we de ne a similarity measure m as a function m : S P T P ! [0; 1]. An example of a similarity measure is the edit similarity dubbed edit5 which allows computing the similarity of a pair (s; t) 2 S T w.r.t. the values of a pair of properties (ps; pt) for s resp. t. An atomic LS is a pair (m; ). A complex LS is the result of combining two LS L1 and L2 through an operator that allows merging the results of L1 and L2. Here, we use the operators u, t and n as they are complete w.r.t. the Boolean algebra and frequently used to de ne LS. An example of a complex LS is given in Figure 1.
We de ne the semantics [[L]] of a LS L w.r.t. a mapping as given in Table 1. The mapping [[L]] of a LS L w.r.t. S T contains the link candidates generated by L. A LS L is subsumed by L0, denoted by L v L0, if for all mappings , we have [[L]] [[L0]] . Two LS are equivalent, denoted by L L0 i L v L0 and L0 v L. Subsumption (v) is a partial order over the set of LS, denoted L. 3
We model oracles for r as black boxes with a characteristic function ! : S T ! ftrue; falseg. The characteristic function !i of the oracle i returns true i the oracle i assumes that r(s; t) holds. Otherwise, it returns false. For ease of notation, we de ne LC = S T and call the elements of LC link candidates. For l 2 LC, we write l > to signify that r(l) holds, i.e., r(s; t) is true for l = (s; t). Otherwise, we write l ?. We now assume a learning situation typical for crowdsourcing, where n oracles are presented with a link candidate l and asked whether l > holds. We can describe each oracle i by the following four probabilities: 1 p(!i(l) = truejl >), i.e., the probability of the oracle i generating true positives. This value is exactly 1 for a perfect 5 We de ne the edit similarity of two strings s and t as (1 + lev(s; t)) 1, where lev is the Levenshtein distance. oracle. 2 p(!i(l) = falsejl >), the probability of false negatives (0 for a perfect oracle). 3 p(!i(l) = truejl ?), i.e., the probability of false positives, (0 for a perfect oracle), and 4 p(!i(l) = falsejl ?), the probability of true negatives (1 for a perfect oracle). Given that p(AjB) + p(:AjB) = 1, the sum of the rst two and last two probabilities is always 1.
Example 1. A noisy oracle can have the following description: p(!i(l)=truejl >)=0:7; p(!i(l)=truejl ?)=0:5; p(!i(l)=falsejl >)=0:3; p(!i(l)=falsejl ?)= 0:5.
For compactness, we use the following vector notation in the rest of the formal model: !! refers to the vector of characteristic functions over all oracles. We write !!(l) = !x to signify that the ith oracle returned the xi for the link candidate l. Let us assume that the probabilities underlying all oracles i are known (we discuss ways to initialize and update these probabilities in the subsequent section). Recalling that we assume that our oracles are independent, we can now approximate the probability that l y (with y 2 f>; ?g) for any given link candidate l using the following Bayesian model: odds(l=>j !w=!x )=Yn p(!i=xijl >) :
i=1 p(!i=xijl ?)
A key idea behind our model is that a link candidate l can be considered to be
a correct link if odds(l >j !w = !x ) k with k > 1. A link candidate is assumed
to not be a link if odds(lj !w = !x ) 1=k. All other link candidates remain
unclassi ed. Computing the odds for a link now boils down to (1) approximating
the four probabilities which characterize our oracles and (2) computing o+. As
known from previous works on probabilistic models [
Qin=1 p(!i=xijl y)
Qin=1 p(!i=xi) p(l y) Recall that the odds of an event A occurring are de ned as odds(A) = p(A)=P (:A). For example, the odds of any link candidate being a correct link (denoted o+) are given by o+ = p(l p(l >) for any l 2 LC: ?) o+ is independent of l and stands for the odds that an element of LC chosen randomly would be a link. Given feedback from our oracles, we can approximate the odds of a link candidate l being a correct link by computing the following: (1) (2) (4) Algorithm 1: Ligon Learning Algorithm
Input: Set of positive examples E0 1 j 0 ; 2 foreach oracle i do 3 Initialize confusion matrix Ci with 12 ; 4 repeat 5 foreach oracle i do 6 Gather !i(l) for each l 2 Ej;
Train Active Learner (Wombat by default) using Sij=0 Ei;
foreach link candidate l 2 E do
Get the oracle result vector !x for l;
13 Compute the set E+ of positive examples with odds(l = >j !w = !x )
14 Compute the set E of negative examples with odds(l = >j !w = !x )
15 j j + 1 ;
16 Ej E+ [ E ;
17 until termination criterion holds ;
18 return best link speci cation;
k ;
k1 ;
2. Equivalence strategy: If r is an equivalence relation (e.g., owl:sameAs), then
the set of all possible candidates has the size jSjjT j. There can be at most
min(jSj; jT j) links between S and T as no two pairs (s; t) and (s; t0) can be
linked if t 6= t0 and vice-versa (see [
jSjjT j min(jSj; jT j) 3. Approximate strategy: We approximate o+ by using our learning approach.
We select the mapping [[L ]] computed using the best speci cation L learned by Ligon (see the subsequent Section) as our best current approximation of the mapping we are trying to learn. o+ is then computed as follows: o+
j[[L ]]j jSjjT j j[[L ]]j : (6) We quantify the e ect of these strategies on our learning algorithm in our experiments. 4
Ligon is an active learning algorithm designed to learn LS from noisy oracles. An overview of the approach is given in Algorithm 1 and explained in the sections below. Confusion Matrices. We begin by assuming that we are given an initial set E0 LC of positive and negative examples for links. In the rst step, we aim to compute the initial approximations of the conditional probabilities which describe each of the oracles i. To this end, each oracle is assigned a confusion matrix Ci of dimension 2 2 (see lines 2-3 of Algorithm 1). Each entry of the matrix is initialized with 12 to account for potential sampling biases due to high disparities between conditional probabilities. The rst and second row of each Ci contains counts for links where the oracle returned true resp. false. The rst and second column of Ci contain counts for positive resp. negative examples. Hence, C11 basically contains counts for positive examples that were rightly classi ed as > by the oracle. In each learning iteration, we update the confusion matrix by presenting the oracle with unseen link candidates and incrementing the entries of C (see lines 4-8 of Algorithm 1). We discuss the computation of the training examples in the subsequent section. Based on the confusion matrix, we can approximate all conditional probabilities necessary to describe the oracle by computing the 2 2 matrix D with dij = cij =(c1j + c2j ). For example, d11 p(!i(l) = truejl >). We call D the characteristic matrix of . Example 2. Imagine an oracle were presented with a set of 5 positive and 5 negative training examples, of which he classi ed 4 resp. 3 correctly. We get " 9 5 # " 9 5 # C = 23 27 and D = 132 172 .
2 2 12 12
Updating the Characteristic Matrices. Updating the probabilities is done via the
confusion matrices. In each learning iteration, we present all oracles with the link
candidates deemed to be most informative. Based on the answers of the oracles,
we compute the odds for each of these link candidates. Link candidates l with
odds in [0; 1=k] and [k; +1[ are considered to be false respectively true. The
new classi cations are subsequently used to update the counts in the confusion
matrices and therewith also the characteristic matrix of each of the oracles.
Active Learning Approach. So far, we have assumed the existence of an active
learning solution for link discovery. Several active learning approaches have been
developed over recent years [
Example 3. Let us assume jBij = 4. A link candidate l returned by two of the LS in Bi would have a probability p(l; Bi) = 0:5. Hence, it would have an entropy e(l; Bi) = 0:5.
Termination Criterion. Ligon terminates after a set number of iterations has been achieved or if a link speci cation learned by Wombat achieves an Fmeasure of 1 on the training data. 5
We aimed to answer 6 research questions with our experimental evaluation: Q1. Which combination of strategies for computing odds and the threshold k leads to the best performance?, Q2. How does Ligon behave when provided with an increasing number of noisy oracles?, Q3. How well does Ligon learn from noisy oracles?, Q4. How well does Ligon scale?, Q5. How well does Ligon perform compare to batch learning approaches trained with a similar number of examples? and Q6. How general is Ligon, i.e., can Ligon be applied to problems outside the link discovery domain? and does Ligon depend on the underlying active learning algorithm?
Experimantal Setup. All experiments were carried out on a 64-core 2:3
GHz PC running OpenJDK 64-Bit Server 1:8:0 151 on Ubuntu 16:04:3 LTS. Each
experiment was assigned 20 GB RAM. We evaluated Ligon using 8 link
discovery benchmark datasets. Five of these benchmarks were real-world datasets [
Parameter Estimation. Our rst series of experiments aimed to answer Q1. We ran Ligon with k = 2; 4; 8 and 16. These settings were used in combination with all three strategies for computing o+ aforementioned. A rst observation is that the AUC achieved by Ligon does not depend much on the value of k nor on the strategy used. This is a highly positive feature of our algorithm as it suggests that our approach is robust w.r.t. to how it is initialized. Interestingly, this experiment already suggests that Ligon achieves more than 95% of the performance of the original Wombat algorithm trained with a perfect oracle.
We chose to run the remainder of our experiments with the setting k = 16 combined with the equivalent strategy as this combination achieved the highest average F-measure of 0.86.
Comparison with Perfect Oracle. In our second set of experiments, we answered Q2 by measuring how well Ligon performed when provided with an increasing number of oracles. In this series of experiments, we used 2, 4, 8, and 16 oracles which were initialized randomly. k was set to 16 and we used the Equivalent strategy. Once more, the robustness of our approach became evident as its performance was not majorly perturbed by a variation in the number of oracles. In all settings Ligon achieves an average AUC close to 0.86 with no statistical di erence. We can hence conclude that the performance of our approach depends mostly on the initial set of examples E0 being accurate, which leads to our prior|i.e., the evaluation of the initial confusion matrix of the oracles|being su cient. This su cient approximation means that our Bayesian model is able to distinguish between erroneous classi cations well enough to nd most informative examples accurately and generalize over them. In other words, even a small balanced set containing 5 positive and 5 negative examples seems su cient to approximate the confusion matrix of the oracles su ciently well to detect positive and negative examples consistently in the subsequent steps. This answers Q2. Figures 2 and 3 show the detailed results of running Ligon for 10 iterations for each of our 8 benchmark datasets.
To answer Q3, we also ran our approach in combination with a perfect oracle (i.e., an oracle which knew and returned the perfect classi cation for all pairs 1.00 0.99 0.98 0.97 0.94 0.90 0.86 0.82 1.00 0.96 0.92 from (S; T )). The detailed results are provided in Figures 3 and 2. Combining our approach with a perfect oracle can be regarded as providing an upper bound to our learning algorithm. Over all datasets, Ligon achieved 95% of the AUC achieved with the perfect oracle (min = 88% on DBpedia-LMDB, max = 100% on Restaurants ) of the AUC achieved with the perfect oracle. This answers Q3 and demonstrates that Ligon can learn LS with an accuracy close to that of an approach provided with perfect answers.
Runtime. In our third set of experiments, we were interested in knowing how well our approach scales. To this end, we measured the runtime of our algorithm while running the experiments carried out to answer Q2 and Q3. In our experiments, Wombat, the machine learning approach used within Ligon, makes up for more than 99% of Ligon's runtime. for more detailed results see Table 2. This shows that the Bayesian framework used to re-evaluate the characteristic matrices of the oracles is clearly fast enough to be used in interactive scenarios, which answers Q4. Our approach completes a learning iteration in less than 10 seconds on most datasets, which we consider acceptable even for interac
Ligon tive scenarios. The longer runtime on DBLP-GoogleScholar (roughly 16 seconds per iteration on average) is due to the large size of this dataset. Here, a parallel version of the Wombat algorithm would help improving the interaction with the user. The implementation of a parallel version of Wombat goes beyond the work presented here.
Comparison with Batch Learning. While active learning commonly
requires a small number of training examples to achieve good F-measures, other
techniques such as pessimistic and re-weighted batch learning have also been
designed to achieve this goal [
Generalization of Ligon. In our last set of experiment, we implemented a
generalization of Ligon for binary classi cation tasks behind link discovery. We
thus used the active learning framework JCLAL [
Link Discovery for RDF knowledge graphs has been an active research area for
nearly a decade, with the rst frameworks for link discovery [
We presented Ligon, an active learning approach designed to deal with noisy oracles, i.e., oracles that are not guaranteed to return correct classi cation results. Ligon relies on a probabilistic model to estimate the joint odds of link candidates based on the oracles' guesses. Our experiments showed that Ligon achieves 95% of the learning accuracy of approaches learning with perfect oracles in the link discovery setting. Moreover, we showed that Ligon is (1) not dependent on the underlying active learning algorithm and (2) able to deal with other classi cation problems. In future work, we will evaluate Ligon within real crowdsourcing scenarios. A limitation of our approach is that it assumes that the confusion matrix of the oracles is static. While this assumption is valid with the small number of iterations necessary for our approach to converge, we will extend our model so as to deal with oracles which change dynamically. Furthermore, we will extend Ligon to handle n-ary classi cation problems and evaluate it on more stat-of-the-art approaches from the deep learning domain. Acknowledgments. This work has been supported by the EU H2020 project KnowGraphs (GA no. 860801) as well as the BMVI projects LIMBO (GA no. 19F2029C) and OPAL (GA no. 19F2028A).