1 Presentation of the System

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 p, v pairs, where p denotes a "property" and v denotes a "value". Subject serves as unique token for a real-world object, and p, v pairs describe the features of this real-world object. Instance matching aims to find 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 find coreferent instances by discriminative properties [2]. This approach is very effective but needs some improvements to meet the requirements of the DOREMUS task, which is to find 1:1 equivalence relationship between two datasets. So, we design njuLink, where "nju" represents "Nanjing University". The key idea of njuLink lies in finding what is essential to determine whether two instances are coreferent. Driven by this, first, 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 finds 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.

There are four steps in the workflow 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. The task we participated in is to find coreferent instance pairs between two datasets. To make our descriptions more clear, we give some notations as follows:

(1) Let D x and D y be two different datasets, respectively; (2) The elements with superscript x are from D x and those with superscript y are from D y , e.g., instances, properties and values in D x are i x , p x and v x , respectively; and (3) Every instance pair i x , i y mentioned in this article is composed of an instance i x from D x and an instance i y from D y , and i x is written to the left and i y is written to the right, this also applies to property pairs p x , p y and value pairs v x , v y .

Preprocess Data. For an instance, njuLink preprocesses the values describing it. There are three types of values: Blank node, URI and Literal (plain or typed). If a value is blank node, njuLink ignores it. Literal is divided into two kinds: typed literal, like boolean and integer, and plain literal, which is often accompanied with a language tag. 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 v x and v y be two values owned by properties p x and p y , respectively. First, njuLink judges whether v x and v y are meaningful to be compared. There are three situations under which comparing them are not meaningful: (1) They both have language tags and their language tags are different; (2) The types of them are different; and (3) One of them is blank node.

Second, let T (v x ) be the type of v x . If v x and v y are meaningful to be compared, the strategies to find their similarity, denoted by V alSim(v x , v y | p x , p y ), vary with their types:

where for typed literal, njuLink uses indicator function (indicatorF unc(v x , v y )) to get their similarity, e.g., when two literals are both date time type, their similarity is 1 if the two literals are equal, and 0 otherwise. For URI and plain literal, njuLink uses I-Sub [3] to calculate the similarity. When the similarity of v x and v y is higher than a threshold, they are considered as a similar value pair. The threshold is set to 0.65, which is suggested by the authors of I-Sub [3].

Calculate similarity of a property pair. Let p x and p y be two properties owned by instances i x and i y , respectively. A property may have more than one value, we let the sets of values of p x and p y be V al(p x , i x ) and V al(p y , i y ), respectively. First, we find value set that has a smaller size. Without loss of generality, we assume that V al(p x , i x ) is the smaller one here. For a value v x in V al(p x , i x ), the maximum similarity between it and the values in V al(p y , i y ) is calculated by M axV alSim(v x , V al(p y , i y )). The maximum similarity between values of V al(p x , i x ) and V al(p y , i y ), which is also considered as the maximum similarity of property pair p x , p y , is denoted by M axP ropSim(p x , p y | i x , i y ):

If M axV alSim(v x , V al(p x , i x )) of v x is higher than a threshold (i.e. 0.65), value v x is considered as a matched value, we define the sets of matched values and unmatched values between p x of i x and p y of i y as follows:

If M axP ropSim(p x , p y | i x , i y ) is higher than a threshold (0.65), the property pair p x , p y is similar w.r.t. instance pair i x , i y . Note that this property pair is not guaranteed to be similar in another instance pair. For every matched value v x of V al(p x , i x ), we sum up its similarity by M atV alSimSum(p x , p y | i x , i y ):

Construct Training Set. Let D x and D y be two different datasets and i x m , i y n be an instance pair, where i x m is from D x and i y n is from D y . 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 D y randomly to form an instance set, namely instSet y . These 20 instances should be under the same class of i y n in Positives, i.e., if instances in Positives are to describe "student", the instances selected should describe "student", too.

Then, njuLink picks up instances i x m from every instance pair i x m , i y n in Positives to form another instance set, namely instSet x . So, instSet x contains 20 instances because there are 20 instance pairs in Positives. After that, for every one in instSet x , njuLink selects an instance from instSet y and makes them an instance pair. Note that every instance in instSet x and instSet y 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 instSet y by selecting instances randomly.

Identify Discriminative Property Pairs. For every instance pair i x m , i y n from Positives, where i x m and i y n represent two different instances, njuLink makes every property of i x m and every property of i y n a pair. Then, njuLink finds 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 p x k , p y j in candidate property pair set, where p x k and p y j represent properties, njuLink calculates the maximum similarity that an instance pair i x , i y on it (M axP ropSim(p x k , p y j | i x , i y )). If the similarity is higher than a threshold, which is 0.65, this instance pair is a coreferent instance pair found by p x k , p y j , otherwise, this instance pair is not coreferent judged by p x k , p y j .

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 classification.

Every property pair p x k , p y j 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 pair is coreferent, if it is also a coreferent one found by p x k , p y j , it is put into TP, otherwise, it is put into FP. When an instance pair is not coreferent, if it is also a non-coreferent one judged by p x k , p y j , 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 p x k , p y j in candidate property pair set, njuLink uses four sets generated by it to obtain the information gain of it, denoted by IG(p x k , p y j ):

where E(T ) measures the information entropy of the original training set T , and E(T p x k ,p y j ) measures the information entropy after using p x k , p y j to classify instance pairs in T . If IG(p x k , p y j ) is higher than a threshold, p x k , p y j 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 find coreferent instances are from two aspects: (1) Get detailed similarity w.r.t. an instance pair; and (2) Find the most coreferent instance pair, e.g., for an instance i and an instance set instSet, we assume that every instance in instSet seems to be coreferent with i. To find the real coreferent instance pair, first, we use every instance in instSet to form an instance pair with i, and then, we compare the detailed similarity of each instance pair formed and only record the instance pair with highest similarity. It guarantees 1:1 equivalence relationship between two datasets.

Let DiscrP ropSet(D x , D y ) denote the set of discriminative property pairs. First, for every instance in D x , njuLink combines it with every instance in D y to generate many instance pairs, and for every generated instance pair i x m , i y n , njuLink finds the set of similar discriminative property pair for it, which is denoted by SimDiscrP ropSet(i x m , i y n ):

where P rop(i x m ) and P rop(i x n ) are the sets of properties of i x m and i y n , respectively. Secondly, njuLink calculates seven features below to represent the similarity of the pair:

1) The size of SimDiscrP ropSet(i x m , i y n ).

2) The sum of information gain of each similar discriminative property pair IGSum(i x m , i y n ):

3) The sum of detailed information gain of each similar discriminative property pair DIGSum(i x m , i y n ):

where DIG(p x k , p y j | i x m , i y n ) denotes the detailed information gain of a similar discriminative property pair w.r.t. i x m , i y n . 4) The sum of detailed similarity sum of each similar discriminative property DSimSum(i x m , i y n ): 18)

where DSim(p x k , p y j | i x m , i y n ) denotes the detailed similarity sum of a similar discriminative property w.r.t. i x m , i y n . 5) The number of similar common property pairs. 6) The sum of maximum similarity of each similar common property pair w.r.t.

i x m , i y n .

7) The number of property pairs that two properties of each one have the same local names. We make every property in P rop(i x m ) and every property in P rop(i y n ) a property pair and check them all.

Besides discriminative property pairs, we also use three features from common property pairs because we find 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 first time to be checked, we record it, otherwise, drop it. It guarantees the 1:1 equivalence relationship between two datasets D x and D y .

You can find the source code and the jar tested by SEALS client successfully on GitHub: https://github.com/nju-websoft/njuLink.

The alignment files for DOREMUS task should be available at the official website: http://islab.di.unimi.it/content/im_oaei/2017/.

There are two sub-tasks under DOREMUS, namely HT and FPT. HT aims to obtain 1:1 equivalence relationship between instances whose data have different types of heterogeneities, while FPT aims to get the same relationship as that of HT between instances with high similarity.

njuLink succeeds in finding property pairs with high discriminability, which are shown in Table 1. The results of evaluation are shown in Table 2 and Table 3.

How to apply different approaches according to different datasets automatically? During the development of njuLink, we adjust the way to find coreferent instances according to the requirements of DOREMUS. But the adjusted approach is not applicable for all tasks. So, finding a way to decide appropriate approaches automatically is necessary.

njuLink is dedicated to finding coreferent instances by utilizing discriminative property pairs. The Instance Matching track of this year show many new things to us. This helps us find 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.