An Ontology Matching Approach Based on Affinity-Preserving Random Walks

1 Introduction

Ontologies have recently gained popularity because they help with inter-operability, information sharing and knowledge reuse. However, there are many different ontologies that describe the same domain, they are often different from each other because they have been designed and constructed independently by different ontology developers. As a result, how to address the heterogeneity of ontologies has attracted considerable attention in recent years.

Ontology matching is the process of finding semantic correspondences between entities from different ontologies. It is one of the most effective solutions to solving the semantic heterogeneity problem [Shvaiko and Euzenat, 2013].

1 The OAEI is an international initiative organizing annual campaigns for evaluating ontology matching systems. All of the ontologies provided by OAEI are described in OWL-DL language, and like most of the other participants our approach manages the OWL ontology. OAEI: http://oaei.ontologymatching.org/

A myriad of approaches have been proposed for ontology matching. In graph-based ontology matching approaches, graphs are used to represent the two input ontologies and compute structural similarities of graphs. Examples of these approaches include Anchor-Prompt [Noy and Musen, 2001], GMO [Hu et al., 2005] and Similarity Propagation [Li et al., 2009; Ngo et al., 2012b]. Anchor-Prompt is an ontology merging and mapping tool, which treats ontologies as directed labeled graphs. The basic idea is that if two pairs of entities are similar and there are paths connecting them, the entities in these paths are often similar as well. GMO is an iterative structural matcher, that uses RDF bipartite graphs to represent ontologies and computes structural similarities between entities by recursively propagating their similarities in the bipartite graphs. Similarity Propagation (SP) is a graph matcher inspired from the work in [Melnik et al., 2002], which aims at database schema matching. SP uses fixed-point computation to determine corresponding nodes in the graphs. The basic idea is that the similarity between two nodes depends on the similarity between their adjacent nodes, or that similarities of nodes can propagate to their respective neighbors. SP is effective and has been embedded in some outstanding ontology matching systems such as RiMOM[Li et al., 2009] and YAM++[Ngo et al., 2012b].

In this paper, we propose a new graph-based approach based on random walks, which is inspired by the work in [Cho et al., 2010] that aims at a graph matching problem in the image processing field. We introduce an association graph constructed with nodes as candidate mappings and edges as affinities between candidate mappings, and we show that the search for mappings between two to-be-matched ontologies can be cast as a node ranking and selection problem in the association graph. We summarize our contributions as follows. (1) We establish a novel random walk view for ontology matching and provide a random walk interpretations for ontology matching. (2) We preserve the original affinity relations between ontology entity pairs by adding an absorbing node into the traditional Markov chains to differentiate the potential true and false mappings. (3) We dynamically add the 1:1 matching constraint to the process of random walk to further improve performance.

To evaluate the effectiveness of our approach, we conduct experiments on the public datasets published in the OAEI campaign. The experimental results show that our matching approach achieves a competitive performance when compared with the state-of-the-art systems.

2 Problem Statement

Ontology is a formal, explicit specification of a shared conceptualization in terms of classes, properties and relations [Euzenat and Shvaiko, 2013]. The process of ontology matching is to find correspondences between entities (classes, properties or individuals) from two ontologies. A mapping or a correspondence is defined as a four-tuple (as written in Eq. (1)), where e1 and e2 represent the entity in ontology O1 and O2 , respectively, r is a type of matching relation (e.g., equivalent, subsume) and k → [0, 1] is the degree of confidence of matching relation between e1 and e2 [Mao et al., 2010].

Similar to the work in [Mao et al., 2011; Shvaiko and Euzenat, 2013; Ngo et al., 2012a], we limit the type of entity to class and property, and focus on discovering only equivalent mappings between entities with cardinality 1:1. That is, one class (property) in ontology O1 can be matched to at most one class (property) in ontology O2 and vice versa.

3 RandomWalks for Ontology matching

Ontology (more accurately, OWL ontology) can be modeled as a graph[Hu et al., 2005; Euzenat and Shvaiko, 2013]. That is, given an ontology, we can define a graph G =< V, E >, where V is the set of labeled nodes representing the entities in the ontology and E is the set of edges representing the relations between two entities. Thus, ontology matching can be viewed as a graph matching problem that aims at finding the semantically similar nodes between two ontology graphs.

In this paper, we treat the problem of ontology matching between two given ontology graphs as a random walk process on an association graph Grw = (V rw , Erw ) constructed from the input ontology graphs, which will be described in detail in Sec.3.1. Then, the original ontology matching problem between ontologies is equivalent to selecting suitable nodes in the association graph Grw because the selected nodes correspond to mappings between entities. To select nodes in Grw , we adopt the statistic of the Markov random walks, which have been used to compute the ranking or relevance of web pages on the Internet [Kleinberg, 1999; Page et al., 1999]. Thus, finding mappings between ontologies O1 and O2 can finally be viewed as node ranking and selection problems by random walks on the association graph Grw .

3.1 Association Graph fromOntologies

Nodes in the Association Graph

We present here the composition of nodes in the association graph. As shown in Figure 1, ellipses and squares in the ontology graph Gi , where i ∈ {1, 2}, represent classes and properties, respectively. A node via ∈ V rw in the association graph Grw denotes a candidate mapping < c1i , c2a > (c denotes the class) or < p1i , p2a > (p denotes the property) because classes (properties) can only be matched to classes (properties). Here, the subscripts i and a denote the ith and ath node in the ontology graphs G1 and G2 , respectively.

Edges in the Association Graph

To set edges between nodes in the association graph, we first extract the existing four main types of relations between classes and properties in the ontology. These relations are: (1) the is-a relation between two classes or two properties; (2) the hasProperty relation between a class and its properties; (3) the hasDomain relation between a property and its domain classes; and (4) the hasRange relation between a property and its range classes. Then, we set an edge between two nodes via ∈ V rw and vjb ∈ V rw if and only if the relations of entity pairs (e1i , e1j ) and (e2a , e2b ) are exactly the same. For example, in Figure 1 (Grw ), there is an edge between nodes v11 and v32 because the entities e13 and e22 are subclasses of entities e11 and e21 , respectively.

Edge Weights Assignment

We compute the weight wia;jb of edge Erw ia;jb with the method described in Algorithm 1 for which the returning value is an n×n real diagonal matrix W, where n is the number of nodes in graph Grw . In Algorithm 1, the array ES contains similarity scores between classes and properties, which is computed with the cosine formula based on the classes' and properties' TFIDF vectors created from their descriptions. The descriptions of an entity include: local name, label, comment, subterms, superterms (both for classes and properties) and properties and instances (for classes) or domain and range (for properties). Pre-processing steps for the description label and comment consist of tokenization, lemmatization, stop word removal and translations as in [Cheatham and Hitzler, 2013].

Algorithm 1: Computing the weights of Erw

Input: The number of entities in O1 and O2 , m1 and m2; The set of nodes in the association graph, V ; The array of entity similarity, ES; Output: The weight matrix, W; 1 for all vh ∈ V do 2 ei ← the entity vh 1 fromO1 ; 3 ea ← the entity vh 2 fromO2 ; 4 for all vk ∈ V do 5 ej ← the entity vk 1 fromO1 ; 6 eb ← the entity vk 2 fromO2 ; 7 if hasSameRelation(ei, ej , ea, eb) then 8 sim ← (ESh + ESk) / 2; 9 if sim ̸= 0 then 10 wia;jb ← exp(sim); 11 else 12 wia;jb ← 1.0/(m1 + m2); 13 else 14 wia;jb ← 1.0/|V |; 15 wh;h ← exp(ESh); 16 returnW;

In Algorithm 1, exp() means the exponential function, and hasSameRelation is used for checking the equality of relation between ei and ej and between ea and eb in the original graphs. We can see that the larger the wia;jb value is, the more likely the nodes vh and vk in Grw represent mappings. It is different from the methods of assigning weights to edges in Similarity Propagation[Li et al., 2009; Ngo et al., 2012b], in which edge weights are empirically determined by the number of outgoing edges of source nodes. However, the weights of edges in our association graph are calculated based on not only the relations but also the similarities between entities. We call wia;jb "affinity" between these two nodes in the association graph, and the affinity matrix W will be used to compute the transition probability matrix of the Markov chain in Sec.3.2.

3.2 Affinity-Preserving RandomWalks

Imagine a walker who takes off from an arbitrary node in a graph and then successively visits new nodes by randomly selecting one of the outgoing edges according to a Markov transition probability and then repeats this process. In this way, we define a random walk on a graph.

Problem of Internet Democracy

Generally, to define the transition probability matrix for a Markov chain on a weighted graph, traditional approaches convert the affinity or weight matrix W to a row stochastic matrix by P = D-1W, where D is a diagonal matrix with entries Dii = di = ∑j Wij. This practice can be found in PageRank [Page et al., 1999], in which each outgoing hyperlink from a node i is row-normalized by 1/di. This also can be interpreted as Internet Democracy [Langville and Meyer, 2004]. However, in our ontology matching task, there exists lots of pseudo candidate mappings (i.e., outlier nodes); this row normalization can strengthen the adverse effect of the pseudo mappings and weaken the true mappings (i.e., inlier nodes). For example, in Figure 1 (G1 , G2 ), suppose the class c11 and the property p11 correspond to the class c21 and the property p21 , respectively. The democratic normalization on Grw scales up the affinities of outgoing edges of outlier nodes such as <c11 , c22> and <p11 , p22> when compared with the affinities of two inlier nodes <c11 , c21> and <p11 , p21> because the affinity sum of an outlier node is usually smaller than that of an inlier node. A similar problem also exists in Similarity Propagation [Li et al., 2009; Ngo et al., 2012b], in which the confidences from the parent node are evenly distributed to subnodes even if some of these subnodes are outliers.

Affinity Preserving in Random Walks

To preserve the original affinity relations while transforming the affinity matrix into the stochastic transition matrix for random walks, some other normalization methods should be used. We define a maximum degree dmax = maxidi and construct an augmented graph Garw (as shown in Figure 1 (Garw )) with an absorbing node vabs, which soaks affinity dmax - di out of all the unabsorbed nodes. In this special Markov chain, once the random walker reaches the absorbing node, he cannot walk out of there. Because each node in the graph Garw has the same degree of dmax, its affinity matrix normalized by 1/dmax results in a stochastic matrix and corresponds to an absorbing Markov chain [Seneta, 2006], which preserves the original affinity relations of the association graph Grw . We call this approach an "affinity-preserving random walk" as it is used in [Cho et al., 2010], which aims at a graph matching problem in the image processing field, and the word "affinity" there means the similar degree between two nodes of an image. The transition matrix P and absorbing Markov chain of this affinity-preserving random walk are formulated as follows.

where W/dmax is a |V rw | × |V rw | substochastic matrix, and 1 is a |V rw | × 1 vector with all elements 1 and 0 with all elements 0. Because the steady state distribution of the absorbing Markov chain is always (0T 1), it cannot be used for node ranking in the same way as PageRank [Page et al., 1999]. For the purpose of ranking nodes on the absorbing Markov chain, we denote X(n) as the node where a random walker in the absorbing Markov chain of Eq.(2) stays at time n and define the conditional distribution ¯x(n) as

which refers to the distribution of unabsorbed node via ∈ Garw at time n. If ¯x(n+1) = ¯x(n) = ¯x, we call ¯x a quasistationary distribution of the absorbing Markov chain. This corresponds to a steady-state distribution in the Markov chain without absorbing nodes. ¯x is a |V rw |×1 real vector, and the element ¯xh ∈ ¯x represents the final probability that the random walker visits the unabsorbed node Via ∈ V arw .

3.3 Finding mappings fromwalking results

Because each unabsorbed node in graph Garw consists of entities e1i ∈ O1 and e2a ∈ O2 , we say that the larger the visit probability of the unabsorbed node Via ∈ V arw is, the more likely is the mapping that it represents. To extract mappings from the steady-state probabilities of nodes in graph Garw , we first construct a bipartite graph Gb = (V 1 , V 2 ;Eb ), and the weight of Eia ∈ Eb is set to the visit probability of the unabsorbed node Via ∈ V arw . This bipartite graph is displayed in Figure 1 (Gb ). Suppose the number of entities in ontologies O1 and O2 is N1 and N2, respectively; then, an N1 × N2 matrix S can be derived from the weighted bigraph Gb . In the matrix S, the value of element Sia will be set to 0 if the edge Eia ̸∈ Eb or the visit probability of the unabsorbed node Via ∈ Garw otherwise. We then use the Stable Marriage (SM) algorithm [Hopcroft and Karp, 1973; He, 2006], which has been widely used for finding 1:1 mappings in bigraphs, to extract the final mappings from the matrix S.

3.4 Mapping-Oriented RandomWalks

In the affinity-preserving random walks presented in Sec.3.2, the 1:1 matching constraint has not been considered in the random walk process and has only been used in the last step of extracting final mappings. Because the calculation process of affinity-preserving randomwalks is iterative, taking the 1:1 matching constraint as a post-processing separate step may gradually submerge some true mappings and highlight some pseudo mappings. For example, in Figure 1, suppose the class entities c11 and c12 correspond to class entities c21 and c22 , respectively, and the similarities of class entity pairs (c11 , c21 ) and (c12 , c22 ) are much larger than those of class entity pair (c12 , c22 ). Then, during the affinity-preserving random walks, the true mapping < c12 , c22 > will be gradually submerged and the pseudo mapping < c11 , c21 > will be highlighted.

How, then, can we consider the 1:1 matching constraint in the affinity-preserving random walk? Inspired by the personalization approach widely used in webpage ranking methods [Haveliwala, 2002; Langville and Meyer, 2004], which strengthens the effects of inlier nodes in random walks, we achieve this goal by adopting a jump in the random walk: The random walker moves by traversing an edge with probability α or by performing a jump to some other nodes with probability 1-α. The variable α represents the bias between the two possible actions, i.e., following an edge or jumping.

Algorithm 2: MORW for Ontology Matching

Input: The weight matrix, W; The starting and maximum number of iteration, B and M; The mapping-oriented factor, α;

Output: The steady-state distribution, ¯x;

1 dmax ←maxidi; 2 P←W/dmax; 3 Initialize the starting probability x as uniform; 4 for i ← 1, 2, ...,M do 5 if i < B then 6 ¯x ← Px; 7 else 8 t ← selectingBySM( ¯x ); 9 r ← amplifyingElements( ¯x, t ); 10 r ← r/ ∑ rai; 11 ¯x ← αPx + (1 - α)r; 12 ¯x ← ¯x/ ∑ ¯xai; 13 if ||¯x - x||2 < ε then 14 return ¯x; 15 x ← ¯x; 16 return ¯x;

The probability distribution when adopting the personalized jump is updated as follows.

where a mapping-oriented jump vector r is added to the affinity-preserving random walk of Eq.(2). That is, we use the jumps for generating a biased random walk to the 1:1 matching constraint. Particularly, we first apply the Stable Marriage (SM) algorithm to select potential mappings (i.e., inlier nodes), then amplify the distribution of these inlier nodes by ex×maxx and normalize x. This procedure is equivalent to attenuating small values of x and amplifying large values of x and made the unreliable mappings contribute insignificantly, which has been denoted by the selectingBySM function and amplifyingElements function in Algorithm 2. Accordingly, our mapping-oriented random walk is formulated by

where f(·) denotes the mapping-oriented function incorporating 1:1 constraints. Note that this is a dynamic Markov chain for which the jump distribution is dynamically varying and dependent on the present distribution of x, unlike conventional jumps in random walks [Haveliwala, 2002; Langville and Meyer, 2004]. As the f(·) generates a jump distribution close to a good solution, the subsequent random walks strengthen the distribution and move toward the final solution. The quasi-stationary distribution of the mappingoriented random walk is computed using the iteration method as summarized in Algorithm 2, in which the parameter B is used to reduce the influence of disturbance from the initial uniform distribution x.

4 Experiments

4.1 Data sets and evaluation criteria

Because the annual OAEI (Ontology Alignment Evaluation Initiative) campaign has become an authoritative contest in the area of ontology matching, we use the datasets from OAEI to evaluate our proposed approach. All of the ontologies in the dataset are described in OWL-DL language.

Development dataset: the Standard Benchmark 2012 dataset, which OAEI provides for participants to develop their systems before entering the competition, is used as the development dataset in our experiments. This dataset contains one reference ontology and 109 target ontologies. We use this dataset to set the parameters in our approaches.

Testing dataset: (1) the Benchmark-Biblio 2012 dataset, which contains one reference ontology and 94 target ontologies; and (2) the Benchmark-Biblioc 2013 dataset, which has five sub-datasets with one reference ontology and 93 target ontologies in each sub-dataset. We use these two datasets to evaluate the effectiveness of our approach.

In the matching scenario, each target ontology should be mapped to the reference ontology. We followed the standard evaluation criteria from the OAEI campaign, calculating the precision, recall and F-measure for each test. The version computed here is the harmonic mean of precision and recall.

4.2 Experiments on the Development dataset

We conduct experiments on the development dataset to check the correctness and rationality of our proposed approaches and select the final values of parameters in the approaches. The compared approaches are: (1) VSM (vector space model), which uses TFIDF vectors (as described in Sec.3.1.) to measure the similarities between classes and properties by cosine similarity and then applies Stable Marriage (SM) algorithm to extract the final mappings without random walk. This approach can be viewed as a baseline. (2) RNRW (Row-Normalized Random Walk), for which the transition probability matrix is a row-normalized affinity matrix. (3) APRW (Affinity-Preserving Random Walk), which is described in Sec.3.2. (4) MORW (Mapping-Oriented RandomWalk), which is presented in Sec.3.4. The final settings of our approach are as follows: The maximum number of iteration M is 300, the number of starting iteration B is 50, the mapping-oriented factor α is 0.7, and the minimum error ε is 1E-60. Table 1 reports the comparison results.

As shown in Table 1, the F-measure reached 77.3% even in the case of the vector space model (VSM) for matching. In our random walk-based approaches, the similarities, which have been employed by VSM, are used to create the transition probability matrix. When the 1:1 matching constraint has not been considered in the process of random walk (i.e., in the APRW approach), the matching F-measure is 82.3%. When we take this constraint into account during the random walk (i.e., in the MORW approach), the F-measure improved by approximately 1% on the whole dataset. The F-measure of RNRW is even lower than that of VSM, and this shows that the settlement of the Internet democracy problem is very important in our approach.

4.3 Experiments on the test dataset

We conduct experiments on the test datasets to evaluate the effectiveness of our approach. We use the same model settings as in the experiment conducted on the development dataset. The experimental results are presented in Table 2.

As we can see from Table 2, due to the improper row normalization, RNRW perform even worse than the VSM baseline by about 10 percent in F-measure on both test datasets. However, by introducing the absorbing node in the association graph and incorporating the 1:1 matching constraints, both APRW and MORW outperform the VSM baseline by large margins. MORW perform slightly better than APRW consistently on both datasets. To determine whether the difference is significant, we conduct significance test using the sample evaluation method, which was proposed by Van Hage et al. [2007] to assess ontology-matching performances. The test results on both datasets show that the performance difference between APRW and MORW is significant at a confidence level of 95% and justify the necessity of the additional jumping technique used in MORW.

4.4 Comparison with OAEI Participants

We compare our final ontology matching approach MORW with other multi-strategy matching systems on the two testing datasets. Figure 2 shows the results of the top five matching systems according to their F-measure on the BenchmarkBiblio 2012 dataset and Benchmark-Biblioc 2013 dataset.

As shown in Figure 2, our MORW outperforms most of the participants except for the MapSSS system, for which the F-measure is 0.87 in 2012, and the YAM++ and CroMatcher systems, for which the F-measures are 0.89 and 0.88 in 2013, respectively. Unlike MapSSS, our approach does not use any external resources such as Google queries in its current version. In the YAM++ approach, the gold standard datasets that are taken from the Benchmark dataset published in OAEI 2009 are used to generate training data to train a decision tree classifier. And in the classifying phase, each pair of elements from two ontologies is predicted as being matched or not according to its attributes. However, our approach is entirely an unsupervised ontology matching approach, but it does not exclude using training data to help initialize the transition probability of the Markov chain to further improve the performance. Unfortunately, despite consulting a great deal of materials, we do not know any of the details for the CroMatcher approach, at least at the present time.

5 Related work

In addition to the graph-based approaches described in the introductions, there are also other approaches such as linguistic matching, hybrid matching, machine learning-based matching and probabilistic matching.

Linguistic matching is the construction of virtual documents. V-Doc [Qu et al., 2006] is an example of a linguistic matcher. It exploits the RDF graph to extract the description information from three types of neighboring entities, including subject neighbors, predicate neighbors and object neighbors. Hybrid matching uses linguistic information (e.g., name, label, and description) and structural information (e.g., key properties and taxonomic structure) to find correspondences between entities. For example, Falcon-AO++ [Jauro et al., 2014] is a hybrid matching system that supports the interactive contribution of a domain expert in the matching process. There are several works that exploit the machine learning techniques for ontology matching. Doan et al. [2003] created a well-known machine learning-based ontology mapping system, in which the joint probability distribution of the concepts is measured to find similar concepts. In [Eckert et al., 2009], string-based, linguistic and structural measures (in total 23 features) were used as inputs to train an SVM classifier to align ontologies. Mao et al. [2010] proposed a neural network-based approach to search for a global optimal solution that can satisfy ontology constraints to the greatest extent possible to find mappings. CSR (Classification-based learning of Subsumption Relations) is a generic method for automatic ontology matching between concepts based on supervised machine learning [Spiliopoulos et al., 2010]. It specifically focusses on discovering subsumption correspondences. SMB (Schema Matcher Boosting) is an approach to combining matchers into ensembles [Gal, 2011]. It is based on a machine learning technique called boosting, which is able to select (presumably the most appropriate) matchers that participate in an ensemble. Some researchers have explored using a probabilistic scheme for ontology matching. iMatch [Albagli et al., 2009] is a probabilistic interactive ontology matching system based on Markov networks. It first builds a specific Markov network for a given pair of ontologies, and the topology of the network is defined based on constraints and rules; then, it uses initial match distributions to initialize the evidence potentials of the network, and ultimately, it exploits probabilistic reasoning in the Markov network to compute the final alignment. CODI is a probabilistic-logical ontology matching system [Niepert et al., 2010; Huber et al., 2011]. It is based on Markov logic networks and provides a declarative framework for matching classes, properties and individuals. The matching problem is reduced to a maximum a posteriori inference in the Markov logic network, which is in turn solved by using integer linear programming.

Our approach belongs to the graph-based ontology matching approaches. The main characteristics of our approach are the following: (1) edge weights in our association graph are measured by the affinity between entities rather than being assigned based on experience as in other graph-based approaches such as Similarity Propagation[Li et al., 2009; Ngo et al., 2012b]; (2) our affinity-preserving random walk approach differentiates the potential true and false mappings in order to weaken the adverse effect of pseudo-mapping nodes, while in previous graph-based approaches, these mappings have been treated equivalently; (3) in the random walk view, our mapping-oriented random walk approach adopts the personalization strategy of PageRank algorithms [Haveliwala, 2002] by dynamically adding jumps for the matching constraints, which has only been used in the final step in most of the previous approaches. This can simultaneously update and exploit the confidences of candidate mappings to further improve the performance.

6 Conclusions

In this paper, we propose a novel ontology matching approach based on random walks. In particular, inspired by the personalization strategy of PageRank algorithms, we propose an affinity-preserving random walk to avoid the Internet democracy problem in our task. Furthermore, to incorporate the matching constraints into the random walks dynamically, a mapping-oriented random walk approach is proposed. We evaluate our approach on the public datasets from OAEI campaigns, and the experimental results show that the matching quality of our approach nears the highest levels. In future work, we plan to integrate external resources such as search engines and labeled data into our approach to help with the calculations of the transition probability matrix.

Acknowledgments

This research is supported by National Key Basic Research Program of China (No.2014CB340504) and National Natural Science Foundation of China (No.61375074,61273318). The corresponding authors of this paper are Baobao Chang and Zhifang Sui.