Methods for learning embedding functions that map the underlying entities to a vector space have gained significant attention in recent times. Different methods for learning embedding functions try to preserve the critical properties of, and relations between, the underlying entities (such as words, concepts, documents, nodes and edges in a graph) in the 𝑛-dimensional vector space. A variety of embeddings for Knowledge Graphs [1,2,3,4,5,6] have been proposed. These methods differ in terms of the underlying properties of the knowledge bases preserved in the vector space. For example, the TransE [1] model considers the relations in a KG as a translation operator over the entities, TransH [2] models the relations as a hyperplane in the vector space to allow for reflexive, one-to-many, many-to-one, and many-to-many relations, DistMult [3] uses Matrix Factorization based approach to bring similar entities and relations together in the vector space. However, most of the KG embedding models focus on capturing the structural properties of the graph and the interaction between the entities and do not take into account the constraints and characteristics of the underlying ontology. Consequently, the embeddings produced by such methods are not suited for reasoning tasks such as classification, satisfiability and consistency checking. Kulmanov et al. [7] have recently proposed EL Embeddings (ElEm) and have described a geometric interpretation of embedding ++ ontologies in an 𝑛-dimensional vector space (Section 3). However, the ElEm embeddings are limited in terms of the coverage of ++ constructs as they ignore the role oriented constructs in such ontologies. Further, the use case considered by them is predicting protein-protein interactions that is modeled as a traditional link prediction task in knowledge bases. In this work, we address the limitations of ElEm embeddings and propose EmEL++ embeddings. We build upon the framework introduced by Kulmanov et al. [7] and extend it to offer more complete coverage of the ++ semantics (Section 3.1) for performing subsumption reasoning task. Baader et al. [8] have shown that all the standard reasoning tasks in ++ ontologies can be reduced to subsumption task. Thus, to the best of our knowledge, we present the first attempts at performing reasoning tasks by embedding ontologies in a vector space. We compare our proposed approach using four ontologies of different sizes and characteristics. Our evaluation shows that EmEL ++ outperform the traditional KG embeddings at the reasoning task and are also able to preserve the characteristics of underlying ontologies better. We would also like to emphasize that performing reasoning in the vector space is critical as it has the potential to speed up the reasoning process significantly. As we describe in Section 4, the subsumption task in vector space involves computing distances between the source class and all the other classes in the ontology. In the worst case, this is an 𝑂(𝑛) operation where 𝑛 is the number of classes. Thus, irrespective of the complexity of the underlying ontology, the subsumption task could be performed in 𝑂(𝑛) time. Further, with uses of techniques such as semantic hashing or binarized embeddings [9], the similarity based search operations can be performed in 𝑂(1) time. Therefore, we believe that embedding based approaches, despite their lower accuracies than standard reasoners and no theoretical guarantees of performance, offer a promising direction of future research to develop more efficient reasoners, especially for more complex description logics such as (OWL 2 DL).
A wide range of methods for computing KG embeddings have been proposed. Node2Vec [10] initiated the idea of learning features for networks addressing the scalability challenge. Although their results are decent for link prediction task but they make assumptions on conditional independence of the feature space which may not hold true in real world scenarios. Eventually, this concept got popularized with KGs wherein, a fact is represented as a triple of the form (h,r,t). Semantic matching KG models exploit similarity based scoring functions and match latent semantics of entities and relations based on vector representations. For example, [4] proposed RESCAL which uses multiple matrices to represent relations among entities but scalability remains an issue. [3] proposed DistMult to overcome challenges of RESCAL. Although, DistMult is similar to RESCAL but DistMult ensures low number of parameters for relations by restricting the matrices. Later, translational based models for KG embeddings used distance based scoring functions. This technique gained most attention due to its simplicity to measure the correctness of a fact. It measures the plausibility of a fact as distance between the entities after translation carried out by relation. TransE [1], TransH [2] and TransR [6] being different variants of the same. TransE being the most representative model, treats the relations as translations such that given a fact, relation vector r minimizes the distance between h and t in vector space. Whereas, TransH interprets relations as translating operator on a hyperplane and TransR models entities and relations in two distinct spaces, performing translation on corresponding relation space. [11] worked on a novel approach inspired by the theory of quantum logic to embed a Knowledge Base (KB) in description logic. Existing works on ontology embedding such as Onto2vec [12] focused on using word2vec as an underlying model. Most of this work focuses on encoding the entities and relations, but they lack in handling the complex relations in an ontology. Recently, [13] pointed out the lack of expressivity in the classical approaches to model relations for KG embeddings. Moreover, their work indicates that geometric models are a better way to learn embeddings for ontologies. Further, [14] present a new approach using deep learning with knowledge based systems to emulate reasoning structure. Although, they perform experiments on a synthetic and a non-synthetic dataset, but in our work we look at multiple datasets with different characteristics and reason about their varying performances. However, [7] tries to overcome the drawbacks of KG embeddings but it does not address all the ++ constructs that are relevant to capture the relations present in an ontology. Further, the evaluation is focused only on link prediction task.
A description logic signature is a tuple ⟨𝑁 𝐶 , 𝑁 𝑅 , 𝑁 𝐼 ⟩, where 𝑁 𝐶 , 𝑁 𝑅 , and 𝑁 𝐼 are countably infinite, mutually disjoint sets of concept names, role names, and individual names respectively. In the following discussion, {𝐶, 𝐶 1 , 𝐶 2 , 𝐷, 𝐸, ⊤, ⊥} ∈ 𝑁 𝐶 , {𝑅, 𝑆, 𝑅 1 , 𝑅 2 } ∈ 𝑁 𝑅 , and {𝑎, 𝑏} ∈ 𝑁 𝐼 .
All the axioms in the ++ description logic can be reduced to one of the normal forms [15] as follows:
1. All the TBox axioms are in one of the four normal forms (𝐶 1 ⊑ 𝐷, 𝐶 1 ⊓ 𝐶 2 ⊑ 𝐷, ∃𝑅.𝐶 1 ⊑ 𝐷, and 𝐶 1 ⊑ ∃𝑅.𝐶 2 ). 2. The bottom concept can only appear on the right side of the equations, and can only appear in the first three normal forms. 3. All role inclusions are of the form 𝑅 ⊑ 𝑆 or 𝑅 1 •𝑅 2 ⊑ 𝑆.
Further, the instantiation and role assertion axioms in the ABox can be converted into TBox axioms as follows:
Thus, with the above transformations, all the axioms in an ++ ontology can be reduced to one of the normalized forms and the task of embedding ontologies in a vector space requires us to learn mapping functions for classes and relations that are part of the normal forms. Typically, for mapping the entities of interest to a vector space, requires to learn a mapping function subject to certain constraints, encoded in the form of an objective function that is optimized during the training phase. These objective functions are designed such that specific properties of the underlying entities are also retained in the vector space. For example, the word2vec [16] model for word embeddings minimizes the distance between contextually similar words, RDF2Vec [17] adapts language modeling approach to capture local information from the graph sub-structures, and TransE [1] model for KGs. Similarly, in this work we learn mapping functions that can embed ++ ontologies in a vector space. In order to do so, we build upon and extend the framework proposed by Kulmanov et al. [7] that interprets a class in the ontology as an 𝑛-ball (defined by its radius and center) in the vector space. Let us consider two classes 𝐶 and 𝐷 such that 𝐶 ⊑ 𝐷. Let these two classes be represented by their respective 𝑛-balls 𝑏 𝑐 and 𝑏 𝑑 in the vector space such that 𝑏 𝑐 ∶ {𝑐 ⃗, 𝑟 𝑐 } and 𝑏 𝑑 ∶ {𝑑 ⃗ , 𝑟 𝑑 }; where 𝑐 ⃗ and 𝑑 ⃗ are the centers and 𝑟 𝑐 and 𝑟 𝑑 are the radii of the respective 𝑛-balls. Geometrically, if 𝐶 ⊑ 𝐷, the mapping function should aim to ensure that the 𝑏 𝑐 lies inside 𝑏 𝑑 (Figure1 (a)). Similarly, if 𝐶 and 𝐷 are disjoint, the respective 𝑛-balls should not overlap with each other in the vector space (Figure1 (b)). Further, similar to the TransE model [1], the relations in the ontology are interpreted as translations operating on the classes. More specifically, if 𝐶 ⊑ ∃𝑅.𝐷, the center of 𝑛-ball representing 𝐶 can be moved to the center of the 𝑛-ball representing 𝐷 (Figure1 (c)).
With the intuitive framework described above, let us now describe the objective functions that should be optimized during the training phase to learn the mapping functions. Let 𝑒 𝑣 ∶ 𝐂 ∪ 𝐑 ⟼ 𝑅 𝑛 be the mapping function that maps each class and relation to a unique vector in the 𝑛-dimensional embedding space. For 𝐶 𝑖 ∈ 𝐂, the resulting vector corresponds to the centre of the 𝑛-ball representing the class. Further, let 𝑒 𝑟 ∶ 𝐶 ⟼ 𝑅 + be the mapping function that maps each class into a non-negative real number, that represents the radius of the 𝑛ball corresponding to class 𝐶. Thus, the pair (𝑒 𝑣 , 𝑒 𝑟 ) of functions represents the operations needed to embed an ++ ontology into an 𝑛-dimensional space. We now describe the various loss functions to represent the different constructs in ++ . The total loss that needs to be minimized during the learning process is the sum of the individual loss functions.
As described before, the first normal form (𝐶 ⊑ 𝐷) when embedded in a vector space can be interpreted geometrically as two 𝑛-balls, such that the 𝑛-ball corresponding to class 𝐶 lies inside the 𝑛-ball corresponding to 𝐷. Hence, our mapping functions 𝑒 𝑣 and 𝑒 𝑟 should bring the centers of the two classes closer to each other, and give the sub-class a smaller radius than the super-class. The loss function presented in Equation 1 captures this intuition and penalizes the mappings that do not adhere to these constraints. Also note that in addition to the above constraints, we also add margin loss (𝛾 ) and a normalization loss that brings the centres of 𝑛-balls of all the classes on the unity sphere.
In the vector space, the second normal form, i.e., 𝐶 ⊓ 𝐷 ⊑ 𝐸, implies that the 𝑛-ball for class 𝐸 should completely engulf the area of intersection of 𝑛-balls for classes 𝐶 and 𝐷. The first term in the loss function (Equation 2) imposes a penalty if the classes 𝐶 and 𝐷 are disjoint. The second and third terms together enforce that the center of the 𝑛-ball for class 𝐸 lies in the area of intersection of 𝑛-balls for classes 𝐶 and 𝐷 such that it satisfies the normal form. Finally, the fourth term requires the radius of the 𝑛-ball of 𝐸 to be greater than the smallest radii among 𝑛-balls of 𝐶 and 𝐷.
The first two normal forms are concerned with the mappings of classes and properties of their respective 𝑛-balls in the vector space. The next two normal forms, i.e., NF3 and NF4, involve relations and how they are associated with the classes. Recall that similar to TransE [1], we consider the relations in ontology as translations that operate on class instances. Consider the normal form 𝐶 ⊑ ∃𝑅.𝐷. In the vector space, 𝐶 and 𝐷 are represented as two 𝑛-balls 𝑏 𝑐 and 𝑏 𝑑 , respectively. If 𝑒 𝑣 (𝑅) is the vector for 𝑅 in vector space, then adding 𝑒 𝑣 (𝑅) to a point in 𝑏 𝑐 should move it to a point in 𝑏 𝑑 (i.e., 𝑅 translates the points in 𝑏 𝑐 to points in 𝑏 𝑑 ). The following loss functions capture these semantics as expressed by the third and fourth normal forms.
Recall from the discussion in Section 3 that the bottom concept can appear only on the right hand side of the first three normal forms [8]. We now present the loss functions for each of the three special cases. The resulting first normal form 𝐶 ⊑ ⊥ indicates that class 𝐶 is unsatisfiable. Thus, in the vector space, we represent this constraint by reducing the radius of class 𝐶 to zero. This is achieved by the following loss function.
Next, the second normal form with the bottom concept is 𝐶 ⊓ 𝐷 ⊑ ⊥ indicating that 𝐶 and 𝐷 are disjoint. In the vector space, this indicates that the 𝑛-balls of classes 𝐶 and 𝐷 are nonoverlapping. This is captured by the following loss function.
Finally, the third normal form ∃𝑅.𝐶 ⊑ ⊥ indicates that in the vector space translating 𝐶 by 𝑅 results in an unsatisfiable class. We already require the radius of unsatisfiable classes to be zero (Equation 5) and since translation does not change the radius of the original class, we have the following loss function.
The role vectors in our proposed framework serve the purpose of translating one class to another class. The constraints considered until now have imposed restrictions on the role vectors based on their relations with the 𝑛-balls of the concerned classes. We now present two loss functions to capture the constraints imposed by role inclusions and role chains in the ontology. The role inclusion of 𝑅 ⊑ 𝑆 implies that the vectors 𝑒 𝑣 (𝑅) and 𝑒 𝑣 (𝑆) in the vector space should be nearby because any translation produced by 𝑅 should also be producible by 𝑆 plus both the vectors should be in the same direction. This intuition is captured by the following loss function represented by Equation 8. Herein, the first term is indicative of the distance that ensures the vectors 𝑒 𝑣 (𝑅) and 𝑒 𝑣 (𝑆) lie in near vicinity of each other. The second term captures the directional aspect of roles in vector space such that they tend to be in same direction.
Next, we consider the hierarchy defined by the role chain 𝑅 1 •𝑅 2 ⊑ 𝑆. In the vector space, this implies that if class 𝐶 can be translated to class 𝐸 by successive application of 𝑅 1 and 𝑅 2 , it can also be translated to 𝐸 directly by the vector for role 𝑆 while preserving the direction of role vectors. The following loss function captures this behavior represented by Equation 9.
Often, negative sampling is employed during the training phase to learn better embeddings as negative samples can be easily generated to enhance the training data available. In order to incorporate negative samples in the training phase, the following loss function is employed.
Thus, the total loss for learning the embedding function is the sum of all the loss functions given by Equations 1-10. Further, we also add the constraint that radius of the satisfiable classes are non-negative and penalize the total loss for learning negative radius for classes.
Given an ++ ontology, we first normalize the ontology to generate the normal forms. These normal forms then constitute as a set of TBox statements wherein each axiom is treated as a positive sample. This normalization is performed using the OWL APIs and the APIs provided by the jCel reasoner which implements the normalization rules [18]. We then introduce negative samples using the third normal form. We randomly generate corrupted axioms following 𝐶 ⊑ ∃𝑅.𝐷, by replacing 𝐶 or 𝐷 with 𝐶 ′ or 𝐷 ′ such that neither 𝐶 ′ ⊑ ∃𝑅.𝐷 nor 𝐶 ⊑ ∃𝑅.𝐷 ′ are asserted axioms in the ontology. Therefore, based on the facts the training process learns ontology embedding such that the facts hold true.
The code for training of embeddings and optimization is implemented using Python and Tensorflow library, and Adam optimizer [19] is used for updating the embeddings. We start the learning process by initializing the embedding vectors for classes and relations by random values. We process the training samples in mini-batches for each of the losses defined for the normal forms along with the losses for roles, and update the embeddings depending upon the total loss i.e. the sum of all the loss functions. The update process is carried till saturation or a fixed number of epochs.
We use following four commonly used and publicly available ontologies of varying size and different characteristics. [20] is one of the most comprehensive ontology of clinical terms with more than 989186 TBox statements involving 307712 classes and 60 relations. [22] unifies the representation of gene across all species. It consists of 130094 TBox statements, 45907 classes and 16 relations. 4. GALEN [23] also represents clinical information. It consists of 84537 TBox statements with 24353 classes and 1010 relations.
Table 1 presents the four ontologies in the increasing order of their size (number of axioms) and highlights the differences between them in terms of the types of axioms. For instance, we note that SNOMED has 0 disjoint axioms and only 1 role chain axiom, despite being the largest amongst the four ontologies. On the other hand, GALEN, being one of the smaller ontologies, has the highest number of role inclusion (958) and role chain (58) axioms. Also, observe that ANATOMY is the only ontology considered that has the representation of all the EL constructs considered in this work.
We consider the following commonly used knowledge graph embeddings for comparison with our proposed EmEL ++ embeddings. [1], one of the most frequently used embedding model for knowledge graph, introduced the idea of translation based embeddings where the relations between entities is interpreted as a translation operation between the entities. 2. TransH [2], is an extension of TransE that better handles reflexive, one-to-many, manyto-one, and many-to-many relations. TransH considers relations as hyperplanes in the embedding space. The translation operation is then performed over the projections of entities on the hyperplane. 3. DistMult [3], a matrix factorization based embedding model, has been found empirically to perform well at compositional reasoning tasks. 4. EL Embeddings (ElEm) [7] is one of the first embedding models for the ++ description logic based model. Our proposed model is also an extension of ElEm embeddings and enhances ElEm by introducing additional constraints for a more comprehensive coverage of ++ description logic. We use the pykeen framework [24] for implementations of TransE, TransH, and DistMult embedding models. For ElEm embeddings, we used the source code provided by the authors1 . Our implementation of EmEL ++ is publicly available at https://github.com/kracr/EmELpp.
For learning the embeddings by different models, we first normalize the ontologies as described in Section 3. Next, we remove 30% of the subclass relation pairs from the normalized ontology to be used for validation (20%) and testing (10%). The remaining ontology with 70% sub-class relation pairs is used as the training set for learning the embedding functions. Further, we take an inferences set that consists of the inferences drawn on the training set using a standard Elk reasoner to evaluate the performance of learned embeddings. We perform hyper-parameter tuning using the 20% validation set and report the performance of fine-tuned models on the test set. The hyper-parameters to tune for all the models are the dimensions of the embedding vectors, and the margin parameter 𝛾 . We consider 𝑛 = {50, 100, 200} and 𝛾 = {−0.1, 0, 0.1} yielding nine different settings. The best performing hyper-parameters for each of the models are reported in Table 2.
We chose subsumption as the main task to evaluate the effectiveness of the proposed EmEL ++ embeddings. Note that once we have embedded the ontologies in a vector space, we have to reduce all the tasks we want to accomplish to operations that can be performed in an 𝑛dimensional space. We reduce the task of subsumption in the embedding vector space as a distance-based operation. Given a test instance of the form 𝐶 ⊑ 𝐷, we take 𝐷 as our source class and rank all the other classes in the ontology in increasing order of their distance from 𝐷 in the vector space. We then compare the effectiveness of different embedding models based on the rank at which 𝐶 is present in the ranked list. An embedding model that successfully captures the subclass relation between the two classes should be able to assign vector representations to the two classes that are very close to each other, hence, producing a lower rank for 𝐶.
Table 3 summarizes the performance of embedding models for test and inferences set. We report and evaluate the performance using six metrics. Hits at ranks 1, 10 and 100 report the fraction of test cases for which the expected class was found within top 1, 10 and 100 ranks, respectively. A median rank of 𝑚 means that for 50% of the test cases, the correct answer was
found below rank 𝑚. 90 𝑡ℎ percentile rank denotes the rank value below which the correct class was found for 90% of the test cases. The first observation that we make from Table 3 is that ElEm and EmEL ++ embeddings perform better than the three commonly used KG embeddings (TransE, TransH, and DistMult). This observation highlights the inadequacy of traditional KG embeddings that do not consider the ontological constructs and rely only on the structural properties of the underlying graph. Both ElEm and EmEL ++ embeddings incorporate specific constraints and charactersitics of ++ description logic, and hence, the embeddings produced by these models are better at retaining the properties of the underlying ontologies in the vector space. Next, we note from the two tables that there is no clear winner among ElEm and EmEL ++ . While EmEL ++ outperforms ElEm for the GALEN and GO ontologies, there is no clear winner for Anatomy and SNOMED ontologies as their performance varies. This observation is consistent with previous empirical studies comparing different link prediction methods that found that no single method outperforms across a variety of datasets [25,26]. We speculate that this divergence in performance could be attributed to the different distributions of the types of axioms in the ontology (ref.
Next, we compare the ElEm and EmEL ++ in terms of retaining the underlying characteristics of ontology in vector space. Recall that both the models map the classes in an ontology to 𝑛-balls in the vector space. Further, the mapping is such that the 𝑛-ball of a super-class subsumes the 𝑛-balls of its sub-classes. Thus, for a test instance 𝐶 ⊑ 𝐷, we check that the 𝑛-ball of class 𝐶 lies inside the 𝑛-ball of class 𝐷 in the vector space. Note that since we have the centers and radii of the corresponding 𝑛-balls, this can be checked easily. Table 4 presents the training, testing, and the inference accuracy obtained for the two embedding models for this task. We report accuracy values, i.e., the fraction of instances where the subsumption relation between the classes was maintained in the vector space. Note that this is a much stricter criterion for even if the subclass 𝑛-ball is slightly outside the 𝑛-ball of the superclass, it will be considered a failure. We observe from Table 4 that EmEL ++ outperforms the ElEm embeddings for all the datasets and across all settings. This indicates that EmEL ++ embeddings are better at preserving the class relationships in the mapped vector space than ElEm embeddings.
We proposed EmEL ++ , an embedding model for ++ ontologies. EmEL ++ builds upon and extends the previously proposed ElEm embeddings by focusing on role inclusions and role chains and offers a more complete coverage of ++ . Experiments with four different ontologies showed that EmEL ++ outperforms traditional KB embeddings on the subsumption reasoning task. Further, when compared with ElEm embeddings, it is able to better preserve the underlying semantics of the ontologies in the vector space. We have also shown how to perform the subsumption reasoning task in a vector space, which is an 𝑂(𝑛) operation in the worst case. We believe this is an important capability and it offers exciting directions for future work.