Measuring the distance between ontological elements is fundamental for ontology matching. String-based distance metrics are notorious for shallow syntactic matching. In this exploratory study, we investigate Wasserstein distance targeting continuous space that can incorporate various types of information. We use a pre-trained word embeddings system to embed ontology element labels. We examine the efectiveness of Wasserstein distance for measuring similarity between ontologies, and discovering and refining matchings between individual elements. Our experiments with the OAEI conference track and MSE benchmarks achieved competitive results compared to the leading systems.
Semantic and structural heterogeneity is widespread among ontologies. To bridge the
heterogeneity, almost all ontology matching systems [24, 11, 17] need to evaluate the distances
between ontological elements. String-based distance metrics have dominated the field [
While machine learning is efective in making use of ontology embeddings, a significant efort is required to gather training instances. Although some systems directly use the cosine similarity between embedding vectors [18] for deriving candidate matchings, the embeddings are first retrofitted through tailored training instances. In practice, the present top matching algorithms are largely unsupervised and rely only upon existing ontology and external sources. Motivated by the desired property of unsupervised learning, we posit the following question: If ontology elements can be readily encoded as embedding vectors, can we use them in an unsupervised fashion for ontology matching?
To research the question, we formulate ontology matching as an optimal transport problem
from a source ontology embedding space to a target ontology embedding space. Optimal
Transport (OT) [27] has been applied to various alignment applications including word embeddings
alignment [12], sequence-to-sequence learning [
The rest of the paper presents our research and is organized as follows. Section 2 introduces optimal transport and Wasswerstein distance. Section 3 describes the ontology embeddings used in this study. Section 4 measures ontology similarity in Wasswerstein distance. Section 5 derives matching candidates. Section 6 refines matching candidates. Section
Optimal transport (OT) [27] originated as a solution to the problem of transporting masses from one configuration onto another with
the least efort . OT had deep connections with major economic problems, for example, in logistics, production planning, and network routing, etc. Since then, optimal transport has been generalized from practical concerns to powerful mathematical tools for comparing distributions. In particular, given two point sets modeled as two discrete distributions, optimal transport is an efective approach for discovering a minimum cost mapping between the two sets. Considering the set of embedding vectors of an ontology as a set of points, we can apply optimal transport to discover a minimum cost mapping between two sets of ontology embeddings. probability distribution defined on the set ( x ) is a probability weight associated with the point x . Similarly, let =
Formally, given two sets of ontology embeddings X = {x ∈ ℝ , = 1..} and Y = {y ∈ ℝ , = 1..} , where each embedding is represented as a vector x or y ∈ ℝ . Let = be the probability distribution defined on the set X, where x is the Dirac at the point x and ∑
=1 ( x ) x ∑ =1 ( y ) y be the
Y, where y is the Dirac at the point y and ( y ) is a probability weight associated with the point y . Usually, we consider uniform weights, e.g., ( x ) = 1 , for = 1.. , and ( y ) = 1 , for = 1.. . However, if additional information is provided, ( x ) and ( y ) can incorporate the information as non-uniform distributions. Optimal transport (OT) defines an optimal plan for mass transportation and a distance between the two distributions.
Specifically, let C = [( x , y )], be a ground cost matrix with ( x , y ) measuring a ground distance between the individual embeddings x and y . Let T = [ ( x , y )], be a matrix of a transport plan (or couplings) with ( x , y ) specifying how much mass will be transported from point x to point y . Let Π(, ) be the set of all feasible transport plans defined as: Π(, )
d=ef {T ∈ ℝ+× |T1 = , T⊤1 = } where 1 and 1 are all one vectors, T1 = and T⊤1 = are marginal constraints on feasible plans. The Optimal Transport problem is to find the map T ∶ X → Y, where T = argmin ∑ ∑ ( x , y ) ⋅ ( x , y ), s.t., T1 = , T⊤1 =
T∈Π(,) =1 =1 The map T is also called coupling matrix. It gives rise to a distance measure between the two distributions called Wasserstein distance defined as: (, ) def =
min ⟨C, T⟩= T∈Π(,)
min ∑ ∑ ( x , y ) ⋅ ( x , y )
T∈Π(,) =1 =1 The optimization problem can be eficiently solved by replacing the objective with an entropy regularized objective such as in the sinkhorn algorithm [27].
Source
Target
Source
Target Paper Accepted_Paper
Optimal Transport
Document
Writer
Topic
Paper Accepted_Paper
Author Subject_Area (1) (2) (3) Document
Writer
Topic Example 1 Figure 1 illustrates the configuration of the optimal transport problem between a source and target ontology. The source ontology has 3 concepts: Document, Writer and Topic. The target ontology has 4 concepts which are: Paper, Accepted_Paper, Author and Subject_Area. The table in Figure 1 (a) shows the Euclidean distances as the ground costs between the embeddings of the source and target ontology concepts. The points in both the source and target embedding sets are uniformly distributed, as reported in the last column and the last row . By solving Equation (2), the table in Figure 1 (b) displays the optimal transport couplings between the points in the source and target embedding spaces. Notice the couplings are feasible because they satisfy the following marginal constraints: T1 = and T⊤1 = . By solving the Equation (3), the Wasserstein distance between the two embedding sets is 0.47 given the ground costs and the couplings.
Ontology embedding is the problem of encoding ontological elements as numerical vectors.
Various methods have been proposed for representing individual components in an ontology
as embeddings. For example, translational-based methods [
We will study the problem of matching the embeddings incorporating structural and logical
information in future work. In this exploratory study, we focus on the ontology embeddings
corresponding to the labels of the ontology elements, for example, the ‘rdfs:label’ of a concept.
we apply the pre-trained language model, fasttext [
Prior to applying optimal transport and Wasserstein distance for ontology matching, we first analyze some properties of Wasserstein distance for capturing ontology similarity. A desirable property is that Wasserstein distance should closely correlate with ontology similarity. That is, the more similar two ontologies are, the shorter the Wasserstein distance between them is. Quantitatively measuring the similarity between two ontologies is a very challenging problem. One option is to count the minimum number of graph edit operations to transform one graph to another. It is known that graph edit distance is NP-hard and it depends on a set of graph edit operations. Another option is the Jaccard Index on sets. If matchings between ontologies are available, we can define the Jaccard similarity between ontologies as follows: ( , ) =
| | | | + | | − | | , where and are source and target ontologies, | | and | | return the number of concepts in each ontology, is the set of matchings between and , and | | gives the number of matchings.
The OAEI Campaign provides a list of ontology matching tasks each with a set of curated matching references. In particular, the Conference track contains 21 matching cases among 7 conference ontologies. For each case, we compute: (1) its Jaccard similarity based on the given matching references, and (2) the Wasserstein distance between the ontology embeddings. We convert a Wasserstein distance, , to a Wasserstein similarity, as = − . Figure 2 shows the regression plot between the Wasserstein similarities and Jaccard similarities. Furthermore, we calculated the Pearson correlation coeficient (PCC) between the two sets of similarities defined as = ( , ) . The PCC is 0.77, indicating Wasserstein distance is highly correlated with the Jaccard coeficients when matchings between two ontologies are known. As a result, Wasserstein distance exhibits the desirable property for capturing ontology similarity. We can then leverage this good property for developing algorithms that derive and refine matchings using optimal transport as presented below.
Given a source and a target ontology, we first apply optimal transport globally to the ontologies for generating a set of candidate matchings. We then compute contextual local Wasserstein distances to refine the matchings by filtering out false positives.
In this section, we describe the building blocks for deriving matching candidates globally. Let X = {x ∈ ℝ , = 1..}
be the source ontology concept embeddings and Y = {y ∈ ℝ , = 1..} the target ontology concept embeddings. The optimal transport problem defined in Equation ( 2) be requires as input ground costs C = [( x , y )], and probability distributions ( x ) and ( y ). For label embedding spaces, we use the Euclidean distances as the ground costs. For the probability distributions, we estimate non-uniform weights using the shortest distances between source and target concept embeddings. In particular, for a source point x ∈ X, let = min=1 ( x , y ) be the shortest distance from x to all embedding points in the target space. The distribution ( x ) will be inversely proportional to for = 1.. . In other words, the greater the shortest distance from a source point to all target points, the less the weight associated with the source concept. Similarly, we estimate non-uniform probability distribution ( y ) associated with the target concepts using the shortest distances from target points to source points.
The solution, T = [ ( x , y )], , = 1.., = 1.. , is a coupling matrix between every source and target embedding point. We test the following two methods for deriving candidate matchings from the coupling matrix: • Mutual Nearest Neighbor (MNN): for a x ∈{x ∈ ℝ , = 1..} , find y ∈{y ∈ ℝ , = 1..} , such that, ( x , y ) = max{ ( x , y ), = 1..} and ( x , y ) = max{ ( x , y ), = 1..} .
{y ∈ ℝ , = 1..} , such that, ( x , y ) ≥ max{ ( x , y ), ≠ 1.. }, for = 1.. . • Top-K Targets (TopK): for a x ∈{x ∈ ℝ , = 1..} , find targets {y 1, y 2, .., y } ⊂ Example 2 In Figure 1(a), the shortest distances from the source concepts to the targets concepts are Document = 0.35, Writer = 0.37, and Topic = 0.58. Taking inverses of the distances and normalizing them gives rise to a non-uniform source distribution = {( Document) = 0.39, ( Write) = 0.37, ( Topic) = 0.24}. We can estimate the target probability distribution in the same way. After solving the optimal transport problem, we obtained the coupling matrix for the optimal transportation as shown in Figure 1(b). By applying MNN, we obtain the following correspondences: Document⇝Accepted_Paper, Write⇝Author, Topic⇝Paper. By applying TopK (K=2), we obtain a diferent set of correspondences each of which contains a set of potential target concepts for each source as follows:
Our experimental results (see Section 7) demonstrated that the global matching candidates (through MNN and TopK) outperformed most of the SOTA systems in terms of the recall metrics. To improve its overall F1 measures, we develop refinement steps presented in next section. ( ( Presentation , subClassOf , Conference_Event ) , ( Presentation , hasSpeaker , Conference_Contributor ) , ( Presentation , isAbout , Accepted_Paper ) )
We refine the candidate matchings by using Wasserstein distances between the local contexts of source and target ontology elements. The local context of an element contains the triples involving the element, including the subClassOf relationships connecting to the element’s parents and children, object property, and datatype property. For each matching candidate, we retrieve the local contexts of the source and target concepts. We then compute the local Wasserstein distance (localWD) between the local contexts by the following steps. First, compute the pairwise Wasserstein distance (pairWD) between each pair of triples in the contexts. The ground costs for computing the pairWDs are the Euclidean distances between the embeddings of the individual elements in the triples. Second, compute the local Wasserstein distance between the contexts by using the pairWDs as ground costs.
Example 3 Figure 3 illustrates the two-step procedure for computing the localWD for a matching candidate Presentation⇝Paper_Presentation. We first extract the local context of the source concept Presentation as a set of triples, ( Presentation) = { 1, 2, 3}, as follows: 1:(Presentation, subClassOf, Conference_Event), 2:(Presentation, hasSpeaker, Conference_Contributor), 3:(Presentation, isAbout, Accepted_Paper).
Similarly, we extract the local context of the target concept Paper_Presentation as a set of triples, ( Paper_Presentation) = { 1, 2, 3}, as follows: 1:(Paper_Presentation, subClassOf, Program_Event), 2:(Paper_Presentation, hasPresenter, Registered_Author), 3:(Paper_Presentation, hasPaper, Paper).
Given these two local contexts, we compute the pairwise WDs between the two sets of triples as illustrated in Figure 3(a) (where only 1⇝ 1, 2⇝ 2, and 3⇝ 3 are shown). Finally, we use the pairWDs as ground costs to compute the localWD between ( Presentation) and ( Paper_Presentation) as illustrated in Figure 3(b).
After computing the local WDs for all matching candidates, we refine the candidate matchings using the localWDs as a main factor. We describe the set of experiments and results in next section.
Setting Up. We name the process of deriving matching candidates from global coupling matrix as OTMapOnto_global. We add a sufix _mnn or _topK to it to indicate whether the candidates are derived by mutual nearest neighbors or top-K targets. In our experiments, we derive a large set of candidates by top-20 targets for refinement (thus, OTMapOnto-global_top20 in the following tables illustrating the results). We name the process of refining matching candidates through local Wasserstein distances as OTMapOnto_refinement. We evaluate these processes on the Conference track 1 and MSE benchmark2 in the OAEI Campaign. The code and Jupyter notebooks for the experiments is here3.
In the refinement process, we create interactions among localWDs, string-based distances, and embedding-based Euclidean distances. The interactions are performed by multiplication. We then examine any enhancements brought by the localWDs in comparison to only stringbased distances, embedding-based Euclidean distances, and their interactions. We compare the following cases: • String-based Levenshtein distances/similarities (string-based distance) • Interactions between the string-based distances and localWDs (string-context-distance) • Euclidean distances between the averaged embeddings of labels • Interactions between the Euclidean distances and localWDs • Wasserstein distances between the embeddings of labels • Interactions between the label Wasserstein distances and localWDs • Interactions among string-based distances, Euclidean distances, label Wasserstein distances, and localWDs
We converted each distance metric , to a similarity metric in [
1http://oaei.ontologymatching.org/2021/conference/index.html 2https://github.com/EngyNasr/MSE-Benchmark 3https://github.com/anyuanay/otmaponto_django
Evaluation on MSE Benchmark. The MSE benchmark contains 3 matching cases between 3 materials science and engineering ontologies: MaterialInformation, MatOnto, and EMMO (European Material Modeling ontology). We downloaded the two leading ontology matching systems AML4 and LogMap5 for comparison. The results are presented in Table 2. The table shows OTMapOnto_refinement achieved the best F1 performance for all 3 test cases.
We name our system as OTMapOnto [
Case 1 Case 2 Case 3
Matcher
OTMapOnto-refinement
OTMapOnto-global_mnn
AML
LogMap
OTMapOnto-global_top20
OTMapOnto-refinement
OTMapOnto-global_mnn
AML
LogMap
OTMapOnto-global_top20
OTMapOnto-refinement
AML
LogMap
OTMapOnto-global_mnn
OTMapOnto-global_top20
several tasks in the OAEI 2021 Campaign [
In discussing these results, it is important to note that this exploratory study only considered the embeddings of concept labels generated by a pre-trained model. In future work, we will develop ontology embeddings capturing additional ontology information including structural and logical components. For large scale ontologies, the × matrices associated with optimal transport are unscalable. It is quite evident that we need to break down the ontologies into smaller chunks for computing the optimal transport couplings. In moving forward, we will first partition the embeddings into clusters. Using Wasserstein distances to measure the similarities of pairs of clusters, we will aim to find candidate matchings from the pairs of clusters that are most similar.
AML [
EMNLP (2016). [11] Faria, D., Pesquita, C., Santos, E., Palmonari, M., Cruz, I.F., Couto, F.M.: The Agreement
MakerLight Ontology Matching System. In: OTM (2013). [12] Gabriel, P., Cuturi, M., Solomon, J.: Gromov-wasserstein averaging of kernel and distance matrices. In: ICML (2016). [13] Galkin, M., Berrendorf, M., Tapley Hoyt, C.: An Open Challenge for Inductive Link
Prediction on Knowledge Graphs. arXiv:2203.01520 (2022) [14] Grave, E., Joulin, A., Berthet, Q.: Unsupervised alignment of embeddings with wasserstein procrustes. In: PMLR (2019). [15] Hamilton, W.L.: Graph representation learning. Synthesis Lectures on Articial Intelligence and Machine Learning 14(3), 1–159 (2020) [16] He, Y., Chen, J., Antonyrajah, D., Horrock, I.: Bertmap: A bert-based ontology alignment system. in: AAAI (2022) [17] Jiménez-Ruiz, E., Cuenca Grau, B.: LogMap: Logic-Based and Scalable Ontology Matching.
In: ISWC (2011). [18] Kolyvakis, P., Kalousis, A., Smith, B., Kiritsis, D.: Biomedical ontology alignment: an approach based on representation learning. J Biomed Semant 9(21) (2018) [19] Lin, Y., Liu, Z., Sun, M., Liu, Y., Zhu, X.: Learning entity and relation embeddings for knowledge graph completion. In: AAAI (2015). [20] Lu, F., Cong, P., Huang, X.: Utilizing textual information in knowledge graph embedding:
A survey of methods and applications. IEEE Access (2020). [21] Maretic, H.P., Gheche, M.E., Chierchia, G., Frossard, P.: Got: An optimal transport framework for graph comparison. In: NeurIPS (2019). [22] Mikolov, T., Chen, K., Corrado, G.S., Dean, J.: Eficient estimation of word representations in vector space. CoRR (2013). [23] Nkisi-Orji, I., Wiratunga, N., Massie, S., Hui, K.Y., Heaven, R.: Ontology alignment based on word embedding and random forest classification. Machine Learning and Knowledge Discovery in Databases 11051I (2019) [24] Otero-Cerdeira, L., J., R.M.F., A., G.R.: Ontology matching: A literature review. Expert
Systems with Applications 42(2), 949–971 (2015) [25] Rocktäschel, T., Singh, S., Riedel, S.: Injecting logical background knowledge into embeddings for relation extraction. In: NAACL (2015). [26] Veira, N., Keng, B., Padmanabhan, K., Veneris, A.: Unsupervised embedding enhancements of knowledge graphs using textual associations. In: IJCAI (2019). [27] Villani, C.: Optimal Transport: Old and New (Grundlehren der mathematischen Wissenschaften (338)). Springer (2009) [28] Wang, Y., Zhang, H., Shi, G., Liu, Z., Zhou, Q.: A model of text-enhanced knowledge graph representation learning with mutual attention. IEEE Access (2020). [29] Wang, Z., Li, J.Z.: Text-enhanced representation learning for knowledge graph. In: IJCAI (2016)