A Hybrid Genetic-Bootstrapping Approach to Link Resources in the Web of Data

A Hybrid Genetic-Bootstrapping Approach to Link Resources in the Web of Data Andrea Cimmino(B)and Rafael Corchuelo(B) University of Seville, ETSI Inform´atica, Avda. Reina Mercedes, s/n, Sevilla, Spain {cimmino,corchu}@us.es Abstract. In the Web of Data, real-world entities are represented by means of resources, for instance the southern Spanish city “Seville” that is represented by means of the resource that is available at http:// es.dbpedia.org/page/Sevilla in the DBpedia dataset. Link rules are intended to link resources that are different, but represent the same real-world entities; for instance the resource that is available at https:// www.wikidata.org/wiki/Q8717 represents exactly the same real-world entity as the resource aforementioned. A link rule may establish that two resources that represent cities should be linked as long as the GPS coordinates are the same. Such rules are then paramount to integrating web data, because otherwise programs would deal with every resource independently from the other. Knowing that the previous resources represent the same real-world entity allows them to merge the information that they provide independently (which is commonly known as integrating link data). State-of-the-art link rules are learnt by genetic programming systems and build on comparing the values of the attributes of the resources. Unfortunately, this approach falls short in cases in which resources have similar values for their attributes, but represent different real-world entities. In this paper, we present a proposal that hybridises a genetic programming system that learns link rules and an ad-hoc filtering technique that bootstraps them to decide whether the links that they produce must be selected or not. Our analysis of the literature reveals that our approach is novel and our experimental analysis confirms that it helps improve the F1score, which is defined in the literature as the harmonic mean of precision and recall, by increasing precision without a significant penalty on recall. 1 Introduction The Web of Data has made it possible for programs to have access to a variety of data about real-world entities. Furthermore, the Linked-Data principles [4] Supported by the Spanish R&D programme (grants TIN2013-40848-R and TIN2013- 40848-R). The computing facilities were provided by the Andalusian Scientific Computing Centre (CICA). We are grateful to Dr. Carlos R. Rivero and Dr. David Ruiz for earlier ideas that led to the results in this paper. We also thank Dr. Francisco Herrera for his hints on statistical analyses and sharing his software with us. support the idea that resources that are different but represent the same realworld entities must be linked so as to facilitate data integration. Link rules are intended to help link resources automatically. The literature provides several proposals to machine learn link rules by means of genetic programming systems [2,11,12,19,20]. Such rules build on transformation and similarity functions that are applied to the values of the attributes of two resources to check if they can be considered similar enough (by attributes we mean their datatype properties); if they are, then the input resources are assumed to represent the same real-world entity and are then linked; if they are not, then the input resources are kept apart. Our experience confirms that such link rules fall short because some resources that represent different real-world entities have attributes with similar values. For instance, think of the many different authors who have the same name or the many different films that have similar titles. In this paper, we present a hybrid approach to the problem: first, we use a state-of-the-art genetic programming system to learn a set of link rules; we then select a base link rule and apply it in order to obtain a collection of candidate links; the remaining rules are then bootstrapped to analyse the neighbours of the resources involved in each candidate link (the neighbours are the resources that can be reached by means of their object properties); finally, we analyse how similar they are in order decide which of the candidate links must be selected as true positives and which must be discarded as false positives. Our analysis of the related work unveils that this is a novel approach since current state- of-the-art link rules do no take the neighbours into account. Our experimental analysis confirms that precision can be improved by 68% in average, with an average −10% impact on recall; overall, the average improvement regarding the F1score is 47%. We also conducted the Iman-Davenport test to check that these differences are statistically significant regarding precision and the F1score, but not regarding recall. Our conclusion is that ours is a very good approach to help programs integrate the data that they fetch from the Web of Data. The rest of the article is organised as follows: Sect. 2reports on the related work; Sect. 3provides the details of our proposal; Sect. 4presents our evaluation results; finally, Sect. 5summarises our conclusions. 2 Related Work The earliest techniques to learn link rules were devised in the field of traditional databases, namely: de-duplication [7,17], collective matching [1,3,6,14,21], and entity matching [15]. They set a foundation for the researchers who addressed the problem in the context of the Web of Data, where data models are much richer and looser than in traditional databases. Some of the proposals that are specifically-tailored to web data work on a single dataset [10,16], which hinders their general applicability; there are a few that attempt to find links between different datasets [5,8,9,13], but they do not take the neighbours of the resources being linked into account, only the values of the attributes; that is, they cannot make resources with similar values for their attributes apart in cases in which they represent different real-world entities. An additional problem is that they all assume that data are modelled by means of OWL ontologies. Unfortunately, many common datasets in the Web of Data do not rely on OWL ontologies, but on simple RDF vocabularies that consists of classes and properties whose relationships and constraints are not made explicit. The previous problems motivated several authors to work on techniques that are specifically tailored to work with RDF datasets. Most such proposals rely on genetic programming algorithms [11,12,19,20] in which chromosomes encode the link rules as trees, which facilitates performing cross-overs and mutations. They differ regarding the expressivity of the language used to encode the link rules and the heuristics used to implement the selection, replacement, cross-over, and mutation operators, as well as the performance measure on which the fitness function relies. Isele and Bizer [11,12] contributed with a supervised proposal called Genlink. It is available with the Silk framework [24], which is gaining impetus thanks to many real-world projects [23]. It uses a tournament selection operator, a generational replacement operator, custom cross-over and mutation operators, and its fitness function relies on the Matthews correlation coefficient. It can use a variety of custom string transformation functions and the Levenshtein, Jaccard, Numeric, Geographic, and Date string similarity measures. An interesting feature is that the size of the link rules must not be pre-established at design time, but it is dynamically adjusted during the learning process. Ngomo and Lyko [19] contributed with a supervised proposal called Eagle, which is available with the LIMES framework [18]. It uses a tournament selection operator, aμ+βreplacement operator, tree cross-over and mutation operators, and its fitness function relies on the F1score. It does not use transformation functions, but the Levenshtein, Jaccard, Cosine, Q-Grams, Overlap, and Trigrams string similarity functions. The maximum size of the link rules must be pre-established at design time. Nikolov et al. [20] contributed with an unsupervised proposal. It uses a roulette-wheel selection operator, an elitist replacement operator, a tree cross-over operator, a custom mutation operator, and a pseudo F1fitness function. Transformations are not taken into account, but the library of similarity functions includes Jaro, Levenshtein, and I-Sub. The maximum size of the link rules is also set at design time. There is a diverging proposal by Soru and Ngomo [22]. It supports the idea of using common machine-learning techniques on a training set that consists in a vectorisation of the Cartesian product of the resources in terms of the similarity of their attributes. Transformation functions are not taken into account and the only string similarity functions considered are Q-Grams, Cosine, and Levenshtein. Whether the size of the rules must be pre-set or not depends on the underlying machine learning technique. Unfortunately, none of the proposals that work on RDF datasets take the neighbours of the resources into account. The previous analysis, makes it clear that the state of the art does not account for a proposal to link resources in RDF datasets that takes their neighbours into account. Our proposal is specifically-tailored to work with such datasets and it is novel in that it is not intended to generate link rules, but leverages the rules that are learnt with other proposals and bootstraps them in order to analyse the neighbours, which our experimental analysis confirms that has a positive impact on precision without degrading recall. 3 Our Proposal Our proposal consists in two components, namely: the first one learns link rules and the second one filters out the links that they produce. The link rule learner is based on Genlink [12], which is a state-of-the-art genetic programming system that has proven to be able to learn good link rules for many common datasets. It is well-documented in the literature, so we focus on describing the second one, which constitutes our original contribution. The filter is an ad-hoc component that works as follows: it takes a link rule and executes it to produce a set of candidate links; then, it analyses the neighbours of the resources involved in each candidate link by bootstrapping the remaining rules; links in which the corresponding neighbours are similar enough are preserved as true positive links while the others are discarded as false positive links. Below, we present the details of the filter, plus an ancillary method that helps measure how similar the neighbours of two resources are. Example 1. Figure 1presents two sample datasets that are based on the DBLP and the NSF datasets. The resources are depicted in greyed boxes whose shapes encode their classes (i.e., the value of property rdf:type), the properties are represented as labelled arrows, and the literals are encoded as strings. The genetic programming component learns the following link rules in this scenario, which we represent using a Prolog-like notation for the sake of readability: r1:link(A, R)ifrdf:type(A)=dblp:Author, rdf:type(R)=nsf:Researcher, NA=dblp:name(A),N R=nsf:name(R), levenstein(lfname(NA),lfname(NR)) >0.80. r2:link(A, P)ifrdf:type(A)=dblp:Article, rdf:type(P)=nsf:Paper, TA=dblp:title(A),T P=nsf:title(P), jaccard(lowercase(TA),lowercase(TP)) >0.65. where levenstein and jaccard denote the well-known string similarity functions (normalised to interval [0.00,1.00]), lfname is a function that normalises people’s names as “last name, first name”, and lowercase is a function that changes a string into lowercase. Intuitively, link rule r1is applied to a resource Aof type dblp:Author and a resource Rof type nsf:Researcher; it computes the normalised Levenshtein similarity between the normalised names of the author and the researcher; if it is greater than 0.80, then the corresponding resources are linked. Link rule r2 dblp:weiwang dblp:article1 dblp:article2dblp:article3 dblp:article4 “Wei Wang”“Flexible and…” “Read only…” “Grid based…” “Grid-Based…” nsf:weiwang1 nsf:award1nsf:award2 nsf:paper1 nsf:paper2 nsf:paper3 nsf:weiwang2 nsf:award3 nsf:paper4 “Wang, Wei” “Fuzzy resolution…” “Grid-Based…” “Flexible and…” “Comp. Sci.” “Comp. Sci.” “Biology” “Phenotypes of…” “Wang, Wei” dblp:title dblp:title dblp:writtenBy dblp:writtenBy dblp:title dblp:title dblp:writtenBy dblp:writtenBy dblp:name nsf:name nsf:leadsnsf:leads nsf:leads nsf:supports nsf:supports nsf:supports nsf:title nsf:title nsf:title nsf:title nsf:supports nsf:name nsf:type nsf:type nsf:type dblp:Author dblp:Article nsf:Researcher nsf:Award nsf:Paper nsf:binwliu nsf:award4 nsf:paper5 “Comp. Sci.” “Alpha: An…” “Liu, Bin W.” nsf:leads nsf:title nsf:supports nsf:name nsf:type dblp:binliu dblp:article5 “Bin Liu” “ALPHA - An…” dblp:writtenBy dblp:name dblp:title Fig. 1. Running example. should now be easy to interpret: it is applied to a resource Aof type dblp:Article and a resource Pof type nsf:Paper and links them if the normalised Jaccard similarity amongst the lowercase version of the title of article Aand the title of paper Pis greater than 0.65. It is not difficult to realise that link rule r1links resources dblp:weiwang and nsf:weiwang1or dblp:binliu and nsf:binwliu, which are true positive links, but also dblp:weiwang and nsf:weiwang2, which is a false positive link. In cases like this, the only way to make a difference between such resources is to analyse their neighbours, be them direct (e.g., dblp:weiwang and dblp:article2) or transitive (e.g., nsf:weiwang1and nsf:paper2).  3.1 Filtering Links Figure 2presents the method to filter links. It works on a base link rule r,aset of supporting link rules S, a source dataset D1, a companion dataset D2,and a threshold θthat we explain later. It returns K, which is the subset of links produced by base link rule rthat seem to be true positive links. Fig. 2. Method to filter links. The method first initialises Kto an empty set, stores the source and the target classes of the base link rule in sets C1and C2, respectively, and the links that result from applying it to the source and the companion datasets in set L1. The main loop then iterates over the set of supporting link rules using variable r. In each iteration, it first computes the sets of source and target classes involved in link rule r, which are stored in variables C 1and C 2, respectively; next, it finds the set of paths P1that connect the source classes in C1with the source classes in C 1in dataset D1; similarly, it finds the set of paths P2that connect the target classes in C2with the target classes in C 2in dataset D2. By path between two sets of classes, we mean a sequence of object properties that connect resources with the first set of classes to resources with the second set of classes, irrespective of their direction. Simply put: the idea is to find the way to connect the resources linked by the base link rule with the resources linked by the supporting link rule, which is done by the intermediate and the inner loops. The intermediate loop iterates over the set of pairs of paths (p1,p 2)fromthe Cartesian product of P1and P2. If there is at least a pair of such paths, it then means that the resources involved in the links returned by base link rule rmight have some neighbours that might be linked by supporting link rule r. The inner loop iterates over the collection of links (a, b)insetL1. It first finds the set of resources Athat are reachable from resource ausing path p1in source dataset D1and the set of resources Bthat are reachable from resource busing path p2in the companion dataset D2. Next, the method applies supporting link rule rto the source and the companion dataset and intersects the resulting links with A×Bso as to keep resources that are not reachable from aor bapart; the result is stored in set E. It then computes the similarity of sets Aand B; intuitively, the higher the similarity, the more likely that resources aand brefer to the same real-world entity. If the similarity is equal or greater than threshold θ, then link (a, b) is added to set K; otherwise, it is filtered out. When the main loop finishes, set Kcontains the collection of links that involve neighbours that are similar enough according to the supporting rules. We do not provide any additional details regarding the algorithms to find paths or resources since they can be implemented using Dijkstra’s algorithm to find the shortest paths in a graph. Computing the similarity coefficient is a bit more involved, so we devote a subsection to this ancillary method below. Example 2. In our running example, link rule r1is the base link rule, i.e., we are interested in linking authors and researchers, and we use link rule r2as the support link rule, i.e., we take their articles and papers into account. Their source classes are C1={dblp:Author}and C 1={dblp:Article}, respectively, and their target classes are C2={nsf:Researcher}and C 2={nsf:Paper}, respectively. Link rule r1returns the following links: L1={(dblp:weiwang, nsf:weiwang1), (dblp:weiwang, nsf:weiwang2),(dblp:binliu, nsf:binwliu)}; note that the first and the third links are true positive links, but the second one is a false positive link. Link rule r2returns the following links: L2={(dblp:article1,nsf:paper3), (dblp:article2,nsf:paper2),(dblp:article4,nsf:paper2),(dblp:article5, nsf:paper5)}, which are true positive links. The sets of paths between the source and target classes of r1and r2are P1={dblp:writtenBy} and P2={nsf:leads, nsf:supports}.Now,thelinks in L1are scanned and the resources that can be reached from the resources involved in each link using the previous paths are fetched. Link l1=(dblp:weiwang, nsf:weiwang1) is analysed first. The method finds A={dblp:article1, dblp:article2, dblp:article3, dblp:article4}by following resource dblp:weiwang through path dblp:writtenBy; similarly, it finds B= {nsf:paper1,nsf:paper2,nsf:paper3}by following resource nsf:weiwang1 through path nsf:leads, nsf:supports. Now supporting link rule r2is applied and the results are intersected with A×Bso as to keep links that are related to l1only; the result is E={(dblp:article1,nsf:paper3),(dblp:article2, nsf:paper2),(dblp:article4,nsf:paper2)}. Then, the similarity of Aand Bin the context of Eis computed, which returns 0.67; intuitively, there are chances that l1is a true positive link. Link l2=(dblp:weiwang, nsf:weiwang2) is analysed next. The method finds A={dblp:article1, dblp:article2, dblp:article3, dblp:article4}by following resource dblp:weiwang through path dblp:writtenBy; next, it finds B= {nsf:paper4}by following resource nsf:weiwang2through path nsf:leads, nsf:supports. Now supporting link rule r2is applied and the result is intersected with A×B, which results in E=∅. In such a case the similarity is zero, which intuitively indicates that it is very likely that l2is a false positive link. Link l3=(dblp:binliu, nsf:binwliu) is analysed next. The method finds A= {dblp:article5}by following resource dblp:binliu through path dblp:writtenBy; Fig. 3. Method to compute similarity. next, it finds B={nsf:paper5}by following resource nsf:binwliu through path nsf:leads, nsf:supports. Now supporting link rule r2is applied and the result is intersected with A×B, which results in E={(dblp:article5,nsf:paper5)}. The similarity is now 1.00, i.e., it is very likely that link l3is a true positive link. Assuming that θis set to, e.g., 0.50, the filterLinks method would return K={(dblp:weiwang, nsf:weiwang1),(dblp:binliu, nsf:binwliu)}. Note that the previous value of θis intended for illustration purposes only because the running example must necessarily have very little data. 3.2 Computing Similarity Figure 3shows our method to compute similarities. Its input consists of sets A and B, which are two sets of resources, and E, which is a set of links between them. It returns the Szymkiewicz-Simpson overlapping coefficient, namely: overlap(A, B)= |A∩B| min{|A|,|B|} The previous formula assumes that there is an implicit equality relation to compute A∩B,|A|,or|B|. In our context, this relation must be inferred from the set of links Eby means of Warshall’s algorithm to compute the reflexive, commutative, transitive closure of relation E, which we denote as E. The method to compute similarities relies on two ancillary functions, namely: reduce, which given a set of resources Xand a set of links Ereturns a set whose elements are subsets of Xthat are equal according to E,andintersect,which given two reduced sets of resources Xand Yand a set of links Ereturns the intersection of Xand Yaccording to E. Their definitions are as follows: reduce(X, E)={W|W∝W⊆X∧W×W⊆E)} intersect(X, Y, E)={W|W∝W⊆X∧∃W:W⊆Y∧W×W∈E} where X∝φdenotes the maximal set Xthat fulfils predicate φ,thatis: X∝φ⇐⇒ φ(X)∧( ∃X:X⊆X∧φ(X)) The method to compute similarities then works as follows: it first reduces the input sets of resources Aand Baccording to the set of links E; it then computes the intersection of both reduced sets; finally, it computes the similarity using Szymkiewicz-Simpson’s formula on the reduced sets. Example 3. Analysing link l1=(dblp:weiwang, nsf:weiwang1) results in sets A={dblp:article1, dblp:article2, dblp:article3, dblp:article4},B={nsf:paper1, nsf:paper2,nsf:paper3},andE={(dblp:article1,nsf:paper3),(dblp:article2, nsf:paper2),(dblp:article4,nsf:paper2)}.IfEis interpreted as an equality relation by computing its reflexive, symmetric, transitive closure, then it is not difficult to realise that dblp:article2and dblp:article4can be considered equal, because dblp:article2is equal to nsf:paper2and nsf:paper2is equal to dblp:article4. Thus, set Ais reduced to A={{dblp:article1},{dblp:article2, dblp:article4},{dblp:article3}} and set Bis reduced to B={{nsf:paper1}, {nsf:paper2},{nsf:paper3}}. As a conclusion, |A∩B|=|{{dblp:article1, nsf:paper3},{dblp:article2, dblp:article4,nsf:paper2}}| =2,|A|=3,and |B|= 3; so the similarity is 0.67. When link l2=(dblp:weiwang, nsf:weiwang2) is analysed, A= {dblp:article1, dblp:article2, dblp:article3, dblp:article4},B={nsf:paper4},and E=∅. Since the equality relation Eis then empty, the similarity is zero because the intersection between the reductions of sets Aand Bis empty. In the case of link l3=(dblp:binliu, nsf:binwliu), A={dblp:article5},B= {nsf:paper5},andE={(dblp:article5,nsf:paper5)}. As a conclusion, |A∩B|= |{{dblp:article5,nsf:paper5}}| =1,|A|=1,and|B|= 1, where Aand B denote, respectively, the reductions of sets Aand B; so the similarity is 1.00.  4 Experimental Analysis In this section, we first describe our experimental environment and then comment on our results. Computing facility: We run our experiments on a virtual computer that was equipped with four Intel Xeon E5-2690 cores at 2.60 GHz and 4 GiB of RAM. The operating system was CentOS Linux 7.3. Prototype: We implemented our proposal with Java 1.8 and the following components: the Genlink implementation from the Silk Framework 2.6.0 to generate link rules, Jena TDB 3.2.0 to work with RDF data, ARQ 3.2.0 to work with SPARQL queries, and Simmetrics 1.6.2, SecondString 2013-05-02, and JavaS- tringSimilarity 1.0.1 to compute string similarities. Evaluation datasets:1We used the following datasets: DBLP, NSF, BBC, DBpedia, IMDb, RAE, Newcastle, and Rest. We set up the following scenarios: (1) DBLP–NSF, which focuses on the top 100 DBLP authors and 130 principal NSF researchers with the same names; (2) DBLP–DBLP, which focuses on the 9 076 DBLP authors with the same names who are known to be different people; (3) BBC–DBpedia, which focuses on 691 BBC movies and 445 DBpedia films that have similar titles; (4) DBpedia–IMDb, which focuses on 96 DBpedia movies and 101 IMDb films that have similar titles; (5) RAE–Newcastle, which focuses 1The datasets are available at https://goo.gl/asvKQV.