A two-step procedure for learning a link-discovery blocking scheme is presented. Link discovery is the problem of linking entities between two or more datasets. Identifying owl:sameAs links is an important, special case. A blocking scheme is a one-to-many mapping from entities to blocks. Blocking methods avoid O(n2) comparisons by clustering entities into blocks, and limiting the evaluation of link speci cations to entity pairs within blocks. Current link-discovery blocking methods use blocking schemes tailored for owl:sameAs links or that rely on assumptions about the underlying link speci cations. The presented framework learns blocking schemes for arbitrary link speci cations. The rst step of the algorithm is unsupervised and performs dataset mapping between a pair of dataset collections. The second supervised step learns blocking schemes on structurally heterogeneous dataset pairs. Application to RDF is accomplished by representing the RDF dataset in property table form. The method is empirically evaluated on four real-world test collections ranging over various domains and tasks.
With the advent of Linked Data, discovering links between entities has emerged
as an active area of research [
Blocking methods require a blocking scheme to cluster entities. Advanced
methods have been proposed to use a given blocking scheme e ectively; relatively
fewer works address the learning of blocking schemes. Even within ER, blocking
scheme learners (BSLs) have met practical success only recently [
Learning link-discovery blocking schemes for arbitrary underlying links remains unaddressed. Because the link can be arbitrary, a training corpus is required. Consider the example in Figure 1. Given a small number of such examples, the proposed BSL adaptively learns a scheme that covers true positives while reducing full quadratic cost, without relying on the formal link speci cation itself. Note that the learned blocking scheme is di erent from a learned link speci cation. In this paper, we exclusively address blocking.
In the Big Data era, scalability, automation and heterogeneity are essential components of systems and hence, practical requirements for real-world link discovery. Scalability is addressed by blocking, but current work assumes that the dataset pairs between which entities are to be linked are provided. In other words, datasets A and B are1 input to the pipeline, and entities in A need to be linked to entities in B. Investigations in some important real-world domains show that pairs of dataset collections also need to undergo linking. Each collection is a set of datasets. An example is government data. Recent government e orts have led to release of public data as batches of les, as one of our real-world test sets demonstrates. Thus, two scalability issues are identi ed: at the collection level, and at the dataset level. That is, datasets in one collection rst need to be mapped to datasets in the second collection, after which a blocking scheme is learned (and later, applied) on each mapped dataset pair.
Automation implies that human intervention needs to be kept to a minimum. In practice, this means that methods need to rely on fewer training examples. Finally, a heterogeneity issue arises if datasets in the collections are in two di erent data models, such as RDF and tabular.
The proposed BSL addresses these challenges in a combined setting. It takes
as input two collections of datasets, with each collection an arbitrary mix of
RDF and tabular datasets. The rst step of the BSL performs unsupervised
dataset mapping by relying on document similarity and e cient solutions to the
Hungarian algorithm [
The rest of this paper is structured as follows. Section 2 describes the related work in this area. Section 3 describes the property table representation and the BSL in detail. Section 4 describe the experimental results, and the paper concludes in Section 5. 2
Link Discovery has been researched actively since the original Silk paper [
Blocking has been extensively studied in the record linkage community [
Multiple techniques for using blocking schemes have been investigated in
the Semantic Web community [
In this section, the two steps of the overall BSL in Figure 3 are described.
Note that dataset mapping is an optional 2 step, but the second step (the core
learner) is essential. As a preliminary, the property table representation is also
summarized.
2 Albeit empirically advantageous, when applied, as Section 4 will show.
Property tables were rst proposed as physical data structures to e ciently
implement triple stores [
The pseudocode for dataset mapping is given in Algorithm 1. The inputs to the algorithm are the dataset collections R and S and a boolean con dence function that is subsequently described. We de ne a dataset collection as a set of independently released datasets. Without loss of generality, assume that jRj jSj. The output desired is a con dent mapping M R S.
Algorithm 1 represents each dataset in each collection as a term frequency (TF) vector. The TF vector for each dataset is constructed by assigning a unique position to each distinct token and recording the count of that token in the dataset. Each TF vector is normalized by dividing each element by the total count of the respective token in the corresponding collection. A normalized TF vector is di erent from a TFIDF3 vector. 3 The TFIDF vector is constructed by dividing each element of a TF vector by the number of datasets in the corresponding collection in which the token occurred at least once (in lines 6 and 7) rather than the total count of the token in that collection.
A matrix Q is initialized with Q[i][j] containing the dot product of
normalized TF vectors Ri and Sj . Once the matrix is constructed, the max Hungarian
algorithm is invoked on the matrix, which has at least as many columns as rows,
by the assumption above [
The con dence of each mapping is evaluated by C. As an example of a con dence function, suppose the function returns True for a returned mapping (i; j) i Q[i][j] is the dominating score, that is, greater than every score in its constituent row and column. Intuitively, this means that the mapping is not only the best possible, but also non-con icting. In some sense, this assumes an aggressive strategy against false positives. Other4 strategies can be formulated for other requirements; we leave these for future work.
Assuming the dominating strategy a priori, the Hungarian algorithm can be
modi ed to terminate in linear time (in R and S), otherwise it is cubic in the
collection size [
Intuitively, dataset mapping is expected to be a well-performing heuristic because constituent datasets are independently released. Algorithms like LIMES, Canopy Clustering and unsupervised methods bene t because they can cluster entities in isolated dataset pairs, rather than all the entities in the collection. With correct mapping, both quality and scalability are expected to improve. Experimentally, the gains are demonstrated in Section 4. 3.3
Given two structurally heterogeneous tabular sources, the goal of the second step
is supervised learning of a heterogeneous blocking scheme. In earlier works, DNF
blocking schemes were found to be fairly representative and learned using
setcovering algorithms [
Note that the originally proposed algorithm had no concept of bagging and assumed the training set was representative enough. Algorithm 2 shows how bag4 For example, using a threshold to map multiple datasets to each other.
Input: Dataset Collections R and S, boolean con dence function C Output: A mapping M between R and S 1. for all datasets Ri 2 R do
T!iR := Term Frequency vector of terms in Ri 2. end for 3. for all datasets Si 2 S do
T!iS := Term Frequency vector of terms in Si
4. end for
5. Construct vectors T R!;S , with jth element T R!;S [j] :=
ging can be incorporated, to work with small5 training sets. Bagging parameters
; are now also input. speci es the number of bagging iterations and is the
sampling rate for bagging. In each bagging iteration, a fraction of the overall
training sample is chosen to undergo feature selection by calling
FisherDisjunctive (Algorithm 3 in [
In some cases, training examples might not be available at all. If the task
is learning owl:sameAs links, the automatic training set generator in our
original work can be used to generate noisy training samples [
Input : Positive feature-vectors set FD, negative feature-vectors set FN , coverage parameter , pruning parameter , bagging iterations , sampling size Output : Blocking scheme B 1. Initialize B0 := 2. for all iter = 1 : : : do
Randomly sample (with replacement) jFDj and jFN j vectors from FD and FN , insert into new sets F N0 and F D0 respectively
B0 := B0 [ F isherDisjunctive(F D0; F N0 ; ; ) 3. end for 4. Output disjunction of elements in B0 as B In this section, the algorithm is experimentally evaluated. Datasets, metrics and baseline are rst described, followed by a set of results and a discussion. The algorithm is evaluated on four real-world dataset collections over three different domains, described in Table 1. In the rst test set, the rst collection consists of a single RDF dataset describing court cases decided in Colombia, along with various properties of those cases. The second collection has two RDF datasets, only one of which is relevant for linkage. This dataset describes article numbers (as literal object values) in the Colombia constitution6. The task is to predict links between the cases in the rst collection and the articles in the second collection used to decide the case. An example was shown in Figure 1. The second test set is similar, but for Venezuela. The third test set consists of ten US 6 constituteproject.org government estimated budget datasets from 2009 to 2013, released separately by the Treasury department and the Joint Committee on Taxation. All datasets in this collection were published in tabular form, but the two collections are structurally heterogeneous. The goal is to link entities (describing a particular budget allocation) that share the same budget function (such as health) in the same year. These three test cases are proper dataset collections, given at least one collection contains more than one dataset. Other such collections can also be observed on the respective website7.
The fourth test set contains collections derived from the video games domain and di ers from the other three test sets in three important respects. First, the dataset mapping step is not applicable, since each collection only contains one dataset. Note that the datasets in this test set are large compared with the other test sets. Second, the rst dataset is RDF and was queried from DBpedia8 while the second dataset is tabular and from a popular charting website9. Finally, the noisy training set generator can be used, given the link is owl:sameAs. We have collected all publicly available test cases on a single portal10, along with other implementation details such as the features (or SBPs) used in the experiments. 4.2
We adopted two metrics, Pairs Completeness (PC) and Reduction Ratio (RR),
from the blocking literature [
As earlier stated, many popular link discovery systems like Silk [
The dataset mapping step was applied on the rst three test sets in Table 1. It is not applicable to the fourth test set. The dominating strategy introduced earlier was used as the con dence function in Algorithm 1. For the second step, note that the baseline chooses seeds randomly. We compensated by conducting ten trials for each run of the algorithm, and averaging PC and RR. The threshold was tuned and set to a low value of 0:0005 to maximize baseline recall.
The parameters in Algorithm 2 were set to values that were found after some
initial tuning (on a subset of the rst test collection). The size of initial training
set was set to 300 each for both duplicates (jFDj) and non-duplicates (jFN j).
was set to 10, to 30, to 0:8 and to 0:2. In additional experiments, we varied
each of these parameters by 50%. There was no signi cant di erence from the
results we subsequently show with these parameter settings. Future work will
investigate automatic parameter tuning. In our earlier work, the feature selection
was also found robust to varying parameters [
To evaluate the learned blocking scheme in a practical blocking method, one
additional parameter, maxBucketPairs is used to enable a technique called block
purging [
With the dominating strategy, dataset mapping yielded perfect mappings for all three test sets. We ran some additional experiments, including using more government test data (from years 2003-2013 instead of 2009-2013) and Constitute and Case Law data from other countries, and the mappings were still perfect. It would seem, therefore, that the normalized TF measures and the dominating strategy are suited to the problem, at least on the tested domains.
Figure 4 shows the PC-RR tradeo results of the learned blocking scheme for Canopy Clustering and the proposed method both with and without dataset mapping12, on the Colombia and Venezuela collections. The gains of dataset 12 Recall that dataset mapping was designed to be compatible with other algorithms as well, including Canopy Clustering. mapping are readily apparent for CC in both cases. The proposed method, Hetero, outperforms the non dataset-mapping version of CC but the gap narrows considerably when dataset mapping is employed. This shows that, in cases where training sets are not readily available, an o -the-shelf dataset mapping algorithm can boost performance. The dataset mapping gains for Hetero aren't signi cant on Venezuela, mainly because the algorithm performs well on this dataset even without mapping. On CC, however, the gains are again apparent. Note that Venezuela ((b) in Figure 4) represents some of the challenges of doing link discovery versus just ER. The proposed BSL was able to overcome these challenges by employing bagging and feature selection.
Figure 5a shows the results on the ve-pair government budget data. For this collection, the gains of dataset mapping are ampli ed. This is because there are more datasets in the collection, so the dataset mappings are particularly useful. We ran further experiments on the full government data (from years 2003-2013) and con rmed this. This time, Hetero also shows noticeable gains, with the curve shifting to the right when dataset mapping is employed. Figure 5b shows the results for learning blocking schemes for ER. The BSL is able to signi cantly outperform CC, regardless of whether it is completely unsupervised or with a provided perfectly labeled training set.
Finally, we repeated the experiments above but without bagging. Highest fscores13 of PC and RR declined on all cases by at least 5%, with 95% statistical signi cance using Student's distribution. Otherwise, the graphical trends were similar. We do not repeat the gures here. 5
In this paper, a link-discovery blocking scheme learner was proposed. The rst step of the method operates in an unsupervised fashion and performs dataset mapping by employing document-level similarity measures. It is compatible with existing clustering and blocking algorithms, experimental savings demonstrated on two such methods. The second step is a heterogeneous BSL that uses techniques like bagging to achieve robust performance, even as the training sets remain constant and the datasets grow in size.
Future work will evaluate the dataset mapping step and the accompanying
con dence strategies more extensively, and develop parameter tuning techniques
for the learner itself. Another important aspect is investigating scalability of the
learner; in particular, we are developing techniques for `pruning' property tables
so that the learner can e ciently scale by learning schemes in a reduced feature
space. We believe that this provides an excellent opportunity for cross-fertilizing
ongoing scalability e orts in the ontology matching community [