njuLink is a tool designed for instance matching. It mainly matches instances by nding discriminative property pairs. Also, to meet 1:1 equivalence relationship for the OAEI 2017 DORUMES task, we make several improvements. In this report, we describe the design ideas and show our evaluation results.
1.1
State, purpose, general statement With the rapid development of the Semantic Web, the amount of RDF data on the Semantic Web is growing in an unprecedented pace. This also brings great challenges to instance matching. On the Semantic Web, an instance describes a real-world object, it is composed of a subject and many hp; vi pairs, where p denotes a \property" and v denotes a \value". Subject serves as unique token for a real-world object, and hp; vi pairs describe the features of this real-world object. Instance matching aims to nd the instances that describe the same real-world object and establish links between them. If two instances describe the same real-world object, we consider them as coreferent instances or a coreferent instance pair. Thanks to a lot of existing work, e.g., the Linked Open Data (LOD) Initiative, millions of links have been established. But, there are still a huge number of instances that potentially refer to the same object but have not been interlinked yet.
Our previous work tries to nd coreferent instances by discriminative properties [2]. This approach is very e ective but needs some improvements to meet the requirements of the DOREMUS task, which is to nd 1:1 equivalence relationship between two datasets. So, we design njuLink, where \nju" represents \Nanjing University". The key idea of njuLink lies in nding what is essential to determine whether two instances are coreferent. Driven by this, rst, njuLink builds a small-scale training set via predicting coreferent and non-coreferent instance pairs. Then, by analyzing the value similarity of every instance pair in training set, njuLink nds some property pairs named discriminative property pairs, which have the ability to identify whether two instances are coreferent. Finally, for an instance pair, njuLink calculates the similarity of values based on the discriminative property pairs, the similarity of values based on common property pairs and the similarity of properties that they have to determine if the instances in this pair is coreferent. 1.2
Speci c techniques used
There are four steps in the work ow of njuLink, which is shown in Fig. 1. We
will describe the strategies to calculate the similarity of values and the similarity
of properties shortly.
with superscript x are from Dx and those with superscript y are from Dy, e.g.,
instances, properties and values in Dx are ix, p
x and vx, respectively; and (
First, njuLink records the type of each value. Then, if the value has a language tag, njuLink also records it. Thirdly, for literals, njuLink replaces punctuations and stop words like \at", \in", \for" with space by a NLP tool, and then njuLink removes all space. For URIs, njuLink only records its local name. Finally, njuLink transforms subjects, properties and values to lowercase letters and stores them for the next step.
Strategies to Calculate Similarity. We describe our strategies to obtain the similarity of a value pair and the similarity of a property pair next.
Calculate similarity of a value pair. Let vx and vy be two values owned
by properties px and py, respectively. First, njuLink judges whether vx and vy are
meaningful to be compared. There are three situations under which comparing
them are not meaningful: (
Second, let T (vx) be the type of vx. If vx and vy are meaningful to be compared, the strategies to nd their similarity, denoted by V alSim(vx; vy j px; py), vary with their types:
V alSim(vx; vy j px; py) =
indicatorF unc(vx; vy); T (vx) = typed literal
I-Sub(vx; vy); otherwise
(
Calculate similarity of a property pair. Let px and py be two properties
owned by instances ix and iy, respectively. A property may have more than
one value, we let the sets of values of px and py be V al(px; ix) and V al(py; iy),
respectively. First, we nd value set that has a smaller size. Without loss of
generality, we assume that V al(px; ix) is the smaller one here. For a value vx
in V al(px; ix), the maximum similarity between it and the values in V al(py; iy)
is calculated by M axV alSim(vx; V al(py; iy)). The maximum similarity between
values of V al(px; ix) and V al(py; iy), which is also considered as the maximum
similarity of property pair hpx; pyi, is denoted by M axP ropSim(px; py j ix; iy):
M axV alSim(vx; V al(py; iy)) = vny2Vmaal(xpy;iy) V alSim(vx; vny j px; py);
(
max x vm 2V al(px;ix)
If M axV alSim(vx; V al(px; ix)) of vx is higher than a threshold (i.e. 0.65), value vx is considered as a matched value, we de ne the sets of matched values and unmatched values between px of ix and py of iy as follows:
M atV al(px; py j ix; iy) = fv j v 2 V al(px; ix) U nmatV al(px; py j ix; iy) = fv j v 2 V al(px; ix) \ M axV alSim(v; V al(py; iy))>0:65)g; \ v 2= M atV al(px; py j ix; iy)g: (4) (5)
If M axP ropSim(px; py j ix; iy) is higher than a threshold (0.65), the property pair hpx; pyi is similar w.r.t. instance pair hix; iyi. Note that this property pair is not guaranteed to be similar in another instance pair. For every matched value vx of V al(px; ix), we sum up its similarity by M atV alSimSum(px; py j ix; iy): M atV alSimSum(px; py j ix; iy) =
X x vm2MatV al( px;py j ix;iy) (6) Construct Training Set. Let Dx and Dy be two di erent datasets and hixm; iyni be an instance pair, where ixm is from Dx and iyn is from Dy. The training set is divided into two parts, Positives and Negatives. Positives consist of coreferent instance pairs and Negatives are composed of non-coreferent instance pairs.
To construct Positives, njuLink picks up 20 instance pairs that have at least one property pair whose maximum similarity is very high. The threshold of similarity under this situation is 1.
When it comes to Negatives, njuLink chooses 20 instances from Dy randomly to form an instance set, namely instSety. These 20 instances should be under the same class of iyn in Positives, i.e., if instances in Positives are to describe \student", the instances selected should describe \student", too.
Then, njuLink picks up instances ixm from every instance pair hixm; iyni in Positives to form another instance set, namely instSetx. So, instSetx contains 20 instances because there are 20 instance pairs in Positives. After that, for every one in instSetx, njuLink selects an instance from instSety and makes them an instance pair. Note that every instance in instSetx and instSety is used only once. Finally, 20 generated instance pairs constitute the Negatives.
These 20 generated instance pairs can be considered as non-conferent ones approximately because the number of non-coreferent instances is much more than that of coreferent instances and njuLink constitutes instSety by selecting instances randomly.
Identify Discriminative Property Pairs. For every instance pair hixm; iyni from Positives, where ixm and iyn represent two di erent instances, njuLink makes every property of ixm and every property of iyn a pair. Then, njuLink nds out which property pair is similar and records it. So, njuLink can get the frequency of every similar property pair recorded after checking all instance pairs. If the frequency of a property pair is more than half of the size of Positives, which equals 10 in this case, njuLink records it in candidate property pair set.
For every property pair hpkx; pjyi in candidate property pair set, where pkx and pjy represent properties, njuLink calculates the maximum similarity that an instance pair hix; iyi on it (M axP ropSim(pkx; pjy j ix; iy)). If the similarity is higher than a threshold, which is 0.65, this instance pair is a coreferent instance pair found by hpkx; pjyi, otherwise, this instance pair is not coreferent judged by hpkx; pjyi.
The percentage of the number of coreferent instances found can measure the discriminability of a property pair, but we found a better approach in [1] to use information gain, which is widely used in classi cation.
Every property pair h k y
px; pj i of candidate property pair set can classify the whole training set to four sets, TP, FP, TN and FN, which denote true positives, false positives, true negatives and false negatives respectively. When an instance px; pjyi, it is put into pair is coreferent, if it is also a coreferent one found by h k TP, otherwise, it is put into FP. When an instance pair is not coreferent, if it is also a non-coreferent one judged by hpkx; pjyi, it is put into TN, otherwise, it is put into FN.
Finally, let T be the training set, which is the union of Positives (T +) and Negatives (T ). For every property pair hpkx; pjyi in candidate property pair set, njuLink uses four sets generated by it to obtain the information gain of it, denoted by IG(pkx; pjy):
IG(pkx; pjy) = E(T )
E(Thpkx;pjyi); E(T ) = jT +j log jT +j jT j jT j jT j log jT j ; jT j jT j E(Thpkx;pjyi) = jP j E(P ) jT j jQj E(Q); jT j E(P ) = jT P j log jT P j
jP j jP j E(Q) = jF P j log jF P j
jQj jQj P = T P + F N; Q = F P + T N; jF N j log jF N j ; jP j jP j jT N j log jT N j ; jQj jQj (7) (8) (9) (10) (11) (12) (13) where E(T ) measures the information entropy of the original training set T , y and E(Thpkx;pjyi) measures the information entropy after using hpkx; pj i to classify instance pairs in T . If IG(pkx; pjy) is higher than a threshold, hpkx; pjyi is considered as a discriminative property pair. We set the threshold 0.2 in our tool. njuLink gets a set of discriminative property pairs after checking all property pairs in candidate property pair set.
Find Coreferent Instances. The key ideas to nd coreferent instances are
from two aspects: (
Let DiscrP ropSet(Dx; Dy) denote the set of discriminative property pairs. First, for every instance in Dx, njuLink combines it with every instance in Dy to generate many instance pairs, and for every generated instance pair hixm; iyni, njuLink nds the set of similar discriminative property pair for it, which is denoted by SimDiscrP ropSet(ixm; iyn): where P rop(ixm) and P rop(ixn) are the sets of properties of ixm and iyn, respectively. Secondly, njuLink calculates seven features below to represent the similarity of the pair:
2) The sum of information gain of each similar discriminative property pair IGSum(ixm; iyn):
IGSum(ixm; iyn) =
X hpkx;pjyi2SimDiscrP ropSet(ixm;iyn)
IG(pkx; pjy); (15) 3) The sum of detailed information gain of each similar discriminative property pair DIGSum(ixm; iyn): (16) (17) (19) DIGSum(ixm; iyn) =
X hpkx;pjyi 2SimDiscrP ropSet(ixm;iyn) DIG(pkx; pjy j ixm; iyn) = (jM atV al(pkx; pj j ixm; iyn)j y
DIG(pkx; pjy j ixm; iyn); jU nmatV al(pkx; pjy j ixm; iyn)j) IG(pkx; pjy); where DIG(pkx; pjy j ixm; iyn) denotes the detailed information gain of a similar discriminative property pair w.r.t. hixm; iyni. 4) The sum of detailed similarity sum of each similar discriminative property DSimSum(ixm; iyn):
DSimSum(ixm; iyn) = DSim(pkx; pjy j ixm; iyn); (18) DSim(pkx; pjy j ixm; iyn) = M atV alSimSum(pkx; pjy j ixm; iyn)
X hpkx;pjyi 2SimDiscrP ropSet(ixm;iyn)
IG(pkx; pjy); where DSim(pkx; pjy j ixm; iyn) denotes the detailed similarity sum of a similar discriminative property w.r.t. hixm; iyni. 5) The number of similar common property pairs. 6) The sum of maximum similarity of each similar common property pair w.r.t.
hixm; iyni. 7) The number of property pairs that two properties of each one have the same local names. We make every property in P rop(ixm) and every property in P rop(iyn) a property pair and check them all.
Besides discriminative property pairs, we also use three features from common property pairs because we nd discriminative property pairs are not enough to separate the most coreferent instance pairs from those that seem to be coreferent. A common property pair should meet two requirements: this property pair is not a discriminative property pair and two properties of it have the same local names.
Thirdly, njuLink sorts the instance pairs generated in descending order according to these seven scores of each one. The importance of these seven features is 1) > 2) > 3) > 4) > 5) > 6) > 7). Finally, njuLink selects instances in sorted instance pairs set from top to bottom, meanwhile, when we pick up instance pairs from top to bottom, if two instances of an instance pair are both the rst time to be checked, we record it, otherwise, drop it. It guarantees the 1:1 equivalence relationship between two datasets Dx and Dy. 1.3
Link to the system and parameters le You can nd the source code and the jar tested by SEALS client successfully on GitHub: https://github.com/nju-websoft/njuLink. 1.4
Link to the set of provided alignments (in align format) The alignment les for DOREMUS task should be available at the o cial website: http://islab.di.unimi.it/content/im_oaei/2017/. 2
There are two sub-tasks under DOREMUS, namely HT and FPT. HT aims to obtain 1:1 equivalence relationship between instances whose data have di erent types of heterogeneities, while FPT aims to get the same relationship as that of HT between instances with high similarity.
njuLink succeeds in nding property pairs with high discriminability, which are shown in Table 1. The results of evaluation are shown in Table 2 and Table 3. 3
How to apply di erent approaches according to di erent datasets automatically? During the development of njuLink, we adjust the way to nd coreferent instances according to the requirements of DOREMUS. But the adjusted approach is not applicable for all tasks. So, nding a way to decide appropriate approaches automatically is necessary.
HT FPT
Conclusion njuLink is dedicated to nding coreferent instances by utilizing discriminative property pairs. The Instance Matching track of this year show many new things to us. This helps us nd the weaknesses of njuLink and makes our original ideas better. Technical problems happened during the development also forced us to pay more attention to the way of realizing our tool. In the future, we will continue following the trends of instance matching with interests and try to solve issues on which we have not achieved good performance.
This work is supported by the National Natural Science Foundation of China (No. 61370019). During our development, we received much support from organizers and volunteers of OAEI, we would like to thank them for their help.