In this work, we present a novel approach for link discovery under constraints pertaining to the expected recall of a link discovery task. Given a link specification, the approach aims to find a subsumed link specification that achieves a lower run time than the input specification while abiding by a predefined constraint on the expected recall it has to achieve. Our approach, combines downward refinement operators with monotonicity assumptions to detect such specifications. Our results suggest that our different implementations can detect subsumed specifications that abide by expected recall constraints efficiently, thus leading to significantly shorter overall run times than our baseline.
A knowledge base K is a set of triples (s; p; o) 2 (I [ B) I (I [ B [ L), where I is the set of all Internationalized Resource Identifiers (IRIs) B is the set of all RDF blank nodes and L is the set of all literals. Given two sets of RDF resources S and T from two (not necessarily distinct) knowledge bases as well as a relation R, the main goal of LD is to discover the mapping = f(s; t) 2 S T : R(s; t)g. To achieve this goal, declarative LD frameworks rely on link specifications (LSs), which describe the conditions under which R(s; t) can be assumed to hold for pairs (s; t) 2 S T . Several grammars have been used for describing a LS in previous works [3]. In general, these grammars assume that a LS consists of : (i) Similarity measures m (m : S T P2 ! [0; 1]), through which property values of resources found in the input datasets S and T can be compared and (ii) operators op. An Atomic LS is a filter f = (m; ), where m is a similarity measure and 2 [0; 1] is a threshold. Operators combine two LSs L1 and L2 to a more complex specification L = (f; ; op(L1; L2)). For L = (f; ; op(L1; L2)), we call op the operator of L. We define the mapping [[L]] S T of the LS L as the set of links that will be computed by L when applied to S T . We denote the size of a mapping [[L]] by j[[L]]j. We define the selectivity of a link specification L as sel(L) = j[[L]]j=jS T j. The aim of sel is to encode the predicted value of j[[L]]j as a fraction of jS T j. This is akin to the selectivity definition often used in the database literature. A LS L0 is said to achieve a recall k w.r.t. to L if k j[[L]]j = j[[L]]\[[L0]]j. If [[L0]] [[L]], then the recall k of L0 abides by the simpler equation k j[[L]]j = j[[L0]]j. A specification L0 with [[L0]] [[L]] is said to achieve an expected recall k w.r.t. to L if k sel(L) = sel(L0). Formally, given a specification L, the aim of partial-recall LD is to detect a rapidly executable LS L0 v L with an expected recall of at least k 2 [0; 1], i.e. a LS L0 with sel([[L0]]) k sel([[L]]), where k 2 [0; 1] is a minimal expected recall set by the user.
The LS L0 is subsumed by the LS L (denoted L v L0) when [[L]] [[L0]] for any
fixed pair of sets S and T . Note that v is a quasi-ordering (i.e., reflexive and transitive)
on the set of all LS, which we denote LS. A key observation that underlies our approach
is as follows: 8 ; 0 2 [0; 1] > 0 ! (m; ) v (m; 0): This observation can be
extended to LS as follows: (
We call : LS ! 2LS a downward refinement operator if 8L 2 LS : L0 2
(L) ! L0 v L, where (LS; v) is a quasi-ordered space. L0 is called a specialisation
of L. We denote L0 2 (L) with L L0. Given L as input, the idea behind our
approach is to use a refinement operator to compute L0 v L with at least a given
expected recall k w.r.t L. We define the corresponding refinement operator over the
space (2LS ; v) as follows:
(L) = >>>>><>>8(;Lm; ; next( )) iiifff LLL === ((Lmm;;;; 1));^ < 1;
>>( (L1) t L2) [ (L1 t (L2)) if L = L1 t L2;
>>>( (L1) u L2) [ (L1 u (L2)) if L = L1 u L2;
:>> (L1)nL2 if L = L1nL2:
(
Our refinement operator is finite, incomplete, proper and redundant if L, S and T are finite. being incomplete is not a restriction for our purposes given that we aim to find Ls that run faster and thus do not want to refine the input LS L to L0 that might make our implementation of the operator slower. Given that is finite, we can generate for any chosen node completely in our implementation. being redundant means that after a refinement, we need to check whether we have already seen the newly generated LS. Hence, we need to keep a set of seen LS. Finally, being proper means that while checking for redundancy, there is no need to compare LS with any of their parents. 3
The basic goal behind LIGER is to find the LS 2 (L0) that achieves the lowest
expected run time while (
The basic implementation of LIGER is dubbed C-RO. Our approach takes as input: a LS L0, an oracle O which can predict the run times and selectivity of LS, the minimal expected recall k and a refinement time constraint maxOpt. We begin by asking O to provide the algorithm with estimations of the selectivity of L0 (selL0 ). We define a refinement tree with L0 as its root. For each refined LS, the set of refined LSs are added as children nodes to the currently refined LS, and a leaf node is as a LS that can not be refined any further. We assign L0 as the best subsumed LS and the best run time rt with L0’s runtime estimation from O. The algorithm computes the desired selectivity value (seldes) as a fraction of L0’s selectivity. Then, we add L0 to the set Buf f er, that serves as a buffer and includes LSs obtained by refining L0 that have not yet been refined. All LSs that were generated through the refinement procedure as well as the input LS L0 are stored in another buffer named T otal. By keeping track of these LSs, we avoid refining a LS more than once and address the redundancy of our refinement operator. The refinement of L0 stops when the refinement time has exceeded maxOpt, or if the Buf f er is empty or the selectivity of returned by O is equal to seldes. At each iteration, the algorithm selects the next node for refinement as follows: first, it retrieves the run time estimation of each LS L that belongs to Buf f er using O. Then, it selects the next LS for refinement as the LS with minimum run time estimation (Lxt). The algorithm then checks if Lxt receives a better runtime score, and assigns Lxt as the new value of and updates rt accordingly. Finally, the algorithm refines Lxt by implementing . For each subsumed LS, the algorithm checks if it already exists in set T otal, to ensure that LIGER does not explore LSs that have already been seen before. Each remaining subsumed LS is added to T otal and the algorithm proceeds in computing its selectivity. If its selectivity is higher or equal to the desired selectivity, the algorithm updates Buf f er by adding the new LS.
One key observation pertaining to the run time of L0 2 (L) is that by virtue of L0 v L, RT (L0) RT (L) will most probably hold. By virtue of the transitivity of , L1 2 (L) ^ L2 2 (L) ^ RT (L1) RT (L2) ! 8L0 2 (L1): RT (L0) RT (L2) also holds. We call this assumption the monotonicity of run times. Since the implementation of C-RO does not take this monotonicity into consideration, we wanted to know whether this assumption can potentially improve the run time of our approach. We then implemented an extension of LIGER with the monotonicity assumption (dubbed ROMA). RO-MA uses a hierarchical ordering on the set of unrefined nodes. By incorporating RO-MA as a search strategy, the refinement tree is expanded using a “top-down” approach until there are no nodes to be further explored in a particular path. 4
We evaluated our approach on seven datasets [4, 2]. All LS used during our experiments
were generated automatically by the unsupervised version of the
genetic-programmingbased ML approach EAGLE [5] as implemented in LIMES [6]. Regarding the Oracle
O mentioned in Section 3, LIGER assumes that it can (i) approximate its run time
using a linear model described in [1], and (ii) estimate its selectivity as follows: (
We first compared the execution time of C-RO and RO-MA (see Table 1) against the Baseline for all 7 datasets alongside with LIGER. As expected, all variations of LIGER require less execution time than the Baseline. As a result, LIGER produces more time-efficient LS, even when maxOpt is set to a high value. LIGER performs best on VILLAGES for k = 0:1 and maxOpt = 0:4 s, where it can reduce the average runtime of the 100 LSs we considered by 88%. On the smaller BDLP-ACM dataset, RO-MA performs best and achieves a time reduction of the run time by 77:5%. Futhermore, we studied how the strategies C-RO and RO-MA compare to each other (see Table 1). Our average results suggest that RO-MA outperforms C-RO on average. The statistical significance of these results is confirmed by a paired t-test on the average run time distributions (significance level = 0.95). Our intuition that the monotonicity of run times can potentially improve the run time of our approach is supported by the results on three out of the seven datasets (Abt-Buy, DBLP-ACM and Amazon-GP). On the remaining four datasets, RO-MA outperforms C-RO on average. Still, when C-RO outperforms RO-MA, the absolute differences are minute. Additionally, both subsumed LSs received the same selectivity. Hence, when the available refinement time is limited, RO-MA should be preferred when aiming to carry out partial-recall LD. The highest absolute difference between C-RO and RO-MA is achieved on the DBLP-Scholar dataset, where RO-MA is 1179:59 s faster than C-RO, while the highest relative gain of 776.28% by C-RO against the Baseline is achieved on VILLAGES (k=10%, maxOpt = 400), which is the largest dataset of our experiments.
Finally, we wanted to measure the loss of F-measure of a machine-learning approach when presented with the results of partial-recall LD vs. the F-measure it would achieve using the full results. We use WOMBAT [8], which is currently the only approach for learning LSs from positive examples. Our results show that with an expected partial recall of 50%, WOMBAT achieves at least 76.6% of the F-measure that it achieves when presented with all the data generated by EAGLE (recall = 100%). 5
We presented LIGER, the first partial-recall LD approach. We provided a formal definition of a downward refinement operator along with its characteristics,which we used to develop an algorithm for partial-recall LD. We thus evaluated our approach on 7 datasets and showed that by using our refinement operator, we are able to detect LS with guaranteed expected recall efficiently. Our extension of the LIGER algorithm with a monotonicity assumption pertaining to the run time of the LS was shown to be slightly better than the basic LIGER implementation. In future work, we will build upon LIGER to guarantee the real selectivity and recall of our approaches with a given probability.