Ontology matching is an important task to achieve interoperation between semantic web applications using different ontologies. Structural similarity plays a central role in ontology matching. However, the existing approaches rely heavily on lexical similarity, and they mix up lexical similarity with structural similarity. In this paper, we present a graph matching approach for ontologies, called GMO. It uses bipartite graphs to represent ontologies, and measures the structural similarity between graphs by a new measurement. Furthermore, GMO can take a set of matched pairs, which are typically previously found by other approaches, as external input in matching process. Our implementation and experimental results are given to demonstrate the e®ectiveness of the graph matching approach.
Web ontologies written by RDF Schema [
In this paper, we present a new approach to ontology matching called GMO (Graph Matching for Ontologies). It uses bipartite graphs to represent ontologies, and measures the structural similarity between graphs by a new measurement. Usually, GMO takes a set of matched pairs, which are typically found previously by other approaches, as external input in the matching process, and output additional matching pairs by comparing the structural similarity. The input mapping given to GMO can be gained by variant approaches available, and may have big variance in size. So, our structural similarity is designed to be independent to lexical similarity, and the e®ectiveness of GMO is tested with variant sized input mapping. The rest of this paper is organized as follows: Ontology representation based on Bipartite Graph is presented in Section 2. A measure of structural similarity between a pair of web ontologies is proposed in Section 3. Our implementation is described in Section 4. Experimental results are reported in Section 5, and some comparison to related work is discussed in Section 6. Finally, Section 7 summarizes our work and outlines some of future work.
RDF model, a foundation of Semantic Web, has the nature of graph structure. OWL ontology can be mapped to an RDF Graph as stated in the fourth section of rdfs:subClasOf rdfs:subClasOf ex1:Supervisor
ex1:Graduate rdfs:domain rdfs:range rdfs:subClasOf ex1:supervise
ex1:PhD_Candidate
s
o s o o o
OWL S&AS [
According to the well-established methods from graph
theory, we utilize the RDF Bipartite Graph model [
De¯nition 1. Let G~A be the RDF bipartite graph of OA. The directed bipartite graph of ontology OA, denoted by GA, is a derivation of G~A by replacing the "s" edges with edges pointing to statement nodes, and the "p" and "o" edges with edges pointing from statement nodes. The adjacency matrix of GA is called the matrix representation of ontology OA, denoted by A. Note: The matrix has the following block structure, 0 0 where AES is a matrix representing the connections from external entities to statements; AS is a matrix representing the connections from ontology entities within OA (internal entities) to statements; AE is a matrix representing the connections from statements to external entities of OA; AOP is a matrix representing the connections from statements to internal entities. rdfs:subClassOf
rdfs:domain stA3 stA1 stA2 stA5 stA4 ex1:PhD_Candidate ex1:Graduate ex1:Scholastics ex1:Supervisor ex1:supervise The external entities for an ontology are usually those vocabulary de¯ned by RDFS or OWL, built-in data types, and data literals. In some cases, the external entities may include some common ones (e.g. FOAF terms) used in two ontologies to be compared, and the ones speci¯ed in an input mapping. Therefore, the separation of "external" and "internal" is relative to the current matching process. In addition, when external entities of OA are not used as subject in OA (as in Fig. 2), AES is a zero matrix.
As an example, Fig. 2 shows the directed bipartite graph of ontology OA. The matrix representation of ontology OA is as follows: rdfs : subClassOf 2 rdfs : domain 6
rdfs : range 6 ex1 :eePxxee1h1xxD11:: S::SCcGusahuprnopealdredaivrssudvtitaasAiiosctt1eeesr 66666666666 ssstttAAA324 6666664 1110 0001 0000 0000 1100 0001 0010 0000 stA5 0 0 1 0 0 1 0 0 0000 0010 0001 1000 10000 77777777777 : 1 0 0 0
We propose in this section a measure of structural similarity for ontology. With this measure, the structural similarity matrix is illustrated by an example. Then, the updating equations for structural similarity matrix are re¯ned according to entity classi¯cation. Finally, a process for similarity computing is outlined.
Here, we conduct the structural comparison between
entities in the two directed bipartite graphs for given
ontologies. The idea of our measure is as follows.
Similarity of two entities from two ontologies comes from
the accumulation of similarities of involved statements
(triples) taking the two entities as the same role
(subject, predicate, object) in the triples, while the
similarity of two statements comes from the accumulation of
similarities of involved entities (including external
entities) of the same role in the two statements being
compared. Our formulation of structural similarity (3.1)
and (3.2) is based on the similarity measurement
between directed graph vertices proposed in the literature
[
The formulation in [
Xk+1 = BXkAT + BT XkA;
k = 0; 1; : : :
(3:0)
where Xk is the nB £ nA matrix of entries xij at
iteration k, and A and B are the adjacency matrices of GA
and GB respectively. It is proved in the literature [
De¯nition 2. (A measure of structural similarity for ontology) Let A and B be the matrix representation of ontologies OA and OB respectively. Let Ok represent the similarity matrix of ontology entities within B to ontology entities within A at iteration k, Sk represent the similarity matrix of statements within B to statements within A at iteration k, and EBA mean the similarity matrix of the external entities of B to the external entities of A. Suppose A, B and Xk (the structural similarity matrix of B to A at iteration k) has the following block form respectively .
AE
AOP BE
BOP 0 EBA
AES 1 AS 0
A ; BES 1 BS 0
A ; 1
A Sk The updating equations for structural similarity matrix are de¯ned as follows: Ok+1 Sk+1 = =
If the limits of normalized even of iterations with O0 = 1 and S0 = 1 (we denote by 1 the vector or matrix whose entries are all equal to 1) of this updating equations exist, we take the limit of Ok as the structural similarity matrix of ontologies OB to OA.
Our formulation of structure similarity, (3.1) and (3.2),
di®er from the one in [
ex2:Other rdfs:domain rdfs:range
rdfs:subClassOf ex2:teach
ex2:OverseaStudent rdfs:subClassOf rdfs:range
rdfs:domain stB2 stB3 stB1 stB4 stB6 stB5 ex2:Other ex2:People ex2:OverseaStudent ex2:Student ex2:Teacher ex2:teach Nodes are classi¯ed in di®erent categories, (iii) The similarities between external entities are kept unchanged during updating.
Let OA be the ontology described in section 2, OB be the ontology depicted in Fig. 3.
The similarity matrix EBA between external entities used in OB and OA is set in advance as rdfs : subClassOf 2 1 rdfs : domain 4 0 rdfs : range 0
For most cases, we can classify the entities described in a given ontology as properties, classes, instances (individuals and data literals). In fact, this kind of classi¯cation is guaranteed to be success for OWL DL and FOL subset of RDFS.
After successful classi¯cation, we can re¯ne the matrix representation form (MR) of ontology OA, in section 2, as follows: 0 AEP S 1 0 AP S 1 where AEP S ; AECS and AEIS represent the connections from external properties, classes and individuals to statements, respectively; AP S ; ACS and AIS represent the connections from internal properties, classes and individuals to statements, respectively; AEP ; AEC and AEI represent the connections from statements to external properties, classes and instances (including data literals); AP OP ; ACOP and AIOP represent the connections from statements to internal properties, classes and instances, respectively. As shown in above, we can also make the re¯nement of ontology OB: 0 BEP S 1 0 BP S 1 BES = @ BECS A ;
BEIS
BS = @ BCS A ;
BIS BE = (BEP ; BEC ; BEI );
BOP = (BP OP ; BCOP ; BIOP ): The similarity matrix of external entities and the structure similarity matrix of ontologies have the diagonal structure as follows:
EBA 0 EPBA 0 Pk Ok
1 A ; where EPBA, ECBA and EIBA represent the similarity matrices of external properties, classes and individuals, respectively; Pk, Ck and Ik represent the similarity matrices of inner properties, classes and individuals, respectively.
The updating equations for structural similarity matrix are re¯ned as follows: Pk+1 Ck+1 Ik+1 +BEC ECBAATEC + BEI EIBAATEI +BP OP PkATP OP + BCOP CkATCOP +BIOP IkAITOP + BPT S PkAP S +BCTS CkACS + BITS IkAIS : (3:3) (3:4) (3:5) (3:6)
Note: The re¯ned formulation of structure similarity has two advantages: (1) good computing performance due to the matrix computation with blocks; (2) avoiding the unnecessary computing of similarity between di®erent kinds of entities, e.g. the ones between classes and properties.
The graph matching for ontologies is implemented as an important component of our tool for aligning ontology, which is called Falcon-AO. In Falcon-AO v0.3, the input mapping to GMO is a set of matched pairs generated by another component, called LMO (A Linguistic Matching for Ontologies). In this section, the implementation of GMO is explained, followed by a brief introduction of LMO.
Suppose the ontologies to be matched are denoted by OA and OB. Given an initial mapping as input, by applying GMO, additional matching pairs will be generated. The implemented process of GMO is outlined as follows.
1. Parse OA and OB, and transform them to corresponding RDF bipartite graphs. 2. Classify entities (including anonymous ones) in OA and OB as classes, properties and instances. 3. Coordinate OA and OB using coordination rules described in 4.2. 4. Determine external entities for OA and OB and setup external similarity matrix. In our implementation, the external entities are made of two parts: one includes built-in vocabularies of web ontology language, datatypes, data literals and URIs used in both OA and OB, and their similarity is preassigned; the other is identi¯ed by the input mapping. 5. Setup matrix representation for OA and OB. 6. Initialize the similarity matrices Pk; Ck; Ik; Sk with 1 (we denote 1 the matrix whose entries are all equal to 1, with corresponding rows and columns suitable to the context). 7. Run the even steps of iterations with updating equations (3.3)-(3.6) till some pre-de¯ned convergence precision is reached. 8. Find a one-one mapping by means of the similarity matrices Pk; Ck and Ik.
9. Output additional matching pairs.
In the current implementation, the iteration times of updating structural similarity matrix is set to 12, which is based on our primary experience. The ¯nding of oneto-one mapping is ¯nished when an estimated low similarity is reached.
Ontologies to be matched may be represented di®erently, due to the heterogeneous ways in expressing semantics and the inference capability brought from ontology languages. Therefore, it is necessary to coordinate the two ontologies before mapping them. Here, we outline several coordination rules, which are implemented in GMO. These rules can be classi¯ed into four categories presented as follows: ² Discarding: Some statements (triples) within an ontology may become redundant and/or worthless for computing structural similarity. For example, some typing statements such as (ex:A rdf:type owl:Class) become redundant after we successfully classify entities, and ontology header is worthless to structural comparing. Some rules are designed in GMO to discard such kinds of statements. ² Merging: Two entities could be stated to be same or equivalent to each other, e.g. (ex:A owl:equival entClass ex:B), then these entities should be merged in the RDF bipartite graph. There are some coordination rules to deal with this issue. ² Inference: In some situations, adding some inferred triples to the RDF bipartite graph with some inference rules would be helpful to structural comparing. For example, if there exist two triples, (ex:p owl:inverseOf ex:q) and (ex:q rdfs:domain ex:A), then, we could add one triple, (ex:p rdfs:range ex:A), if there is no triple to state the range of ex:p. ² List: To avoid heterogeneous in expressing a list using rdf:List, a List rule is presented. All members of a list are collected, and we use rdfs:member property to express the relation between the list and each of its members, instead of using RDF collection vocabularies(rdf:¯rst, rdf:rest and rdf:nil). More coordination rules will be introduced in later version of GMO. It is also worthy of note that there is a tradeo® between the cost of inference and the quality of mapping.
As is presented above, our GMO can be fed by an input mapping. In Falcon-AO v0.3, the input mapping to GMO is generated by LMO (A Linguistic Matching for Ontologies).
LMO includes two parts, one is based on string comparison, and the other is based on VSM (Vector Space Model). For string comparison, we use edit distance approach to calculate similarities between entities. For VSM, we treat the ontology entities (classes, properties and instances) as virtual documents. These virtual documents are constructed as "bags of terms" by using entity names, labels and comments, as well as neighbors' names or labels. Then, we can use VSM to gain the similarity matrix between entities. The details of LMO are out of the scope of this paper.
LMO brings some e®ectiveness to Falcon-AO, as demonstrated by the experimental results shown in section 5.2.
We have so far performed the GMO approach on OAEI 2005 benchmark test suite 1 and used standard information retrieval metrics to assess the results of our tests: Precision
=
Recall = F ¡ Measure = ]correct found alignments
]found alignments ]correct found alignments
]existing alignments 2 £ Precision £ Recall
: Precision + Recall ; ;
We tested the e®ectiveness of GMO on OAEI 2005 benchmark test cases, by taking some percentage of standard matched pairs as input mapping to GMO. The experimental results are demonstrated in Fig.4 by average precisions and recalls of all the test cases.
As shown below, with input matched pairs being fed increasingly, the GMO can ¯nd more additional correct matching pairs. The average precisions and recalls of test case #101-304 are indicated in y-axis, and the percentages of matched pairs as input mapping are shown in x-axis. It is worth noting that even with no input mapping, GMO still performs well, and the overall average precision and recall are 0.62 and 0.59 respectively. We have categorized all the test cases into four groups: test case #101-104, #201-210, #221-266 and #301-304. Their average F-Measure are shown in Fig.5. The results of test case #101-104 and #201-210 demonstrate that GMO is more suitable for those ontologies with similar structure than others. For these two categories of test cases, GMO still performs very nice without input mapping.
The weakness of GMO is also explicit. It performs not so well when the ontologies to be matched have a great 1http://oaei.inrialpes.fr/2005/benchmarks/ 100% 90% di®erence in structure (e.g. test case #221-266 and #301-304). In such cases, more matched pairs should provided as input.
The partial experiment results of our Falcon-AO are presented in Table 1, and you will see that Falcon-AO performs well for all these test cases.
The matched pairs generated by LMO are fed into GMO as input. In this step, we must make a decision between precision and e®ect, that is to say, the precision of input matched pairs should be as high as possible, and as is shown above, the amount will also a®ect the matching e®ect. The details of the decision will be presented in our experimental paper accompanied.
As can be seen from Table 1, our tool Falcon-AO works very well for test case #101-104 and test case #201Precision Recall 101-104 201-210 221-266 301-304 210, and performs pretty good for other two categories of test cases.
Our presented work falls into the scope of
similaritybased approaches to ontology matching. Logic based
approach, e.g. Semantic Matching [
Compared with them, our presented GMO approach uses bipartite graphs to represent web ontologies instead of using labeled graph or RDF graph, and measures the structural similarity between graphs by a new measurement. Our similarity model emphasizes the structural similarity based on the connection similarity, and does not depend on or mix up with lexical similarity. In addition, GMO approach can make use of a set of matched pairs found previously by other approaches. In fact, our similarity model also makes use of connections to "external" entities as well as matches between "external" entities identi¯ed earlier automatically or manually. This idea is similar to Anchor-PROMPT, but the method of similarity computing is very di®erent. Furthermore, our work is targeted to web ontologies, including RDFS and OWL. Currently, with an emphasis on FOL subset of RDFS and OWL Lite.
The experimental results reported on EON Ontology
Alignment Contest [
The GMO approach (a Graph Matching for Ontologies) presented in this paper has two distinguished features from early works as follows: (i) It uses bipartite graphs to represent ontologies instead of using labeled graph or RDF graph. The bipartite graph model can reveal the real structure of web ontologies to be compared. (ii) A new measure of structural similarity for web ontology. This measure will play an important role in ontology matching, especially when lexical similarity could not be gained.
Our GMO approach has been implemented in our ontology matchers. The experimental results demonstrated the feasibility and the e®ectiveness of GMO. As illustrated in Section 5, GMO is irreplaceable when there is little gain from lexical comparison. In addition, GMObased matcher can be integrated with other matchers. Therefore, GMO is also a complement to other related work in the area of ontology matching.
As we pointed out in Section 3, ontologies should be coordinated before comparison due to the heterogeneous ways in expressing semantics and the inference capability brought from ontology languages. However, it is not easy to select appropriate coordination rules due to the tradeo® between the cost of inference and the quality of mapping. Another issue is the interaction between similarities at conceptual layer and instance layer. In current stage of our implementation, we separate these two layers, and use matches at conceptual layer as inputs to compute similarities at instance layer.
In the case of comparing instance-intensive ontologies,
machine learning (e.g. GLUE [
As part of future research, we are going to improve the GMO approach and related algorithms in some aspects, e.g. coordination issue and layers issue. We plan to integrate GMO with techniques in machine learning and natural language processing to realize more powerful ontology matchers.
This work is jointly supported by National Key Basic Research and Development Program (2003CB317004) and JSNSF (BK2003001). We would like to thank Prof. Jianming Deng and Dr. Zhiqiang Gao for their suggestions. We are also grateful to other members in our team for their contributions. In the end, we would like to thank anonymous reviewers for their helpful suggestions. Further information about our tools and the experimental results can be found at 2. 2http://xobjects.seu.edu.cn/project/falcon/falcon.html