EL Embeddings: Geometric Construction of Models for the Description Logic EL++

1 Introduction

There has been a recent proliferation of methods that generate "embeddings" for different types of entities. Often, these embeddings are functions that map entities within a certain structure into a vector space Rn such that a set of structural characteristics of the original structure are preserved within the vector space. For example, word embeddings are generated for words within a corpus of text based on the distribution of words and their co-mentions [Mikolov et al., 2013].

Knowledge graph embeddings are used to project sets of discrete facts into a vector space over real numbers and aim to preserve some structural properties of the graph within Rn [Nickel et al., 2016; Wang et al., 2017]. The embeddings can project entities and relations within a knowledge graph into Rn such that they can naturally be used as features for machine learning tasks such as classification, regression, or clustering, or directly utilize similarity measures within Rn for determining semantic similarity, performing reasoning by analogy, and thereby predict relations. Most knowledge graph embedding approaches find the embedding function through optimization with respect to an objective function and, optionally, a set of constraints [Wang et al., 2017].

∗Contact Author

Inference in knowledge graphs is often limited to composition of relations. Model-theoretic languages such as Description Logics can also be used to express relational knowledge while adding operators that cannot easily be expressed in graph-based form (quantifiers, negation, conjunction, disjunction) [Baader, 2003]. In particular the life sciences have developed a large number of ontologies formulated in the Web Ontology Language (OWL) [Grau et al., 2008], and many of the life science ontologies fall in the OWL 2 EL profile [Hoehndorf et al., 2011], which is based on the Description Logics EL++[Motik et al., 2009]. The life science ontologies are used to express domain knowledge and serve as a foundation for analysis and interpretation of biological data, for example through statistical measures [Subramanian et al., 2005] or semantic similarity measures [Pesquita et al., 2009]. Recently, "ontology embeddings" were developed for life science ontologies that map classes, relations, and instances in these ontologies into a vector space while preserving certain syntactic properties of the ontology axioms and their deductive closure [Smaili et al., 2018]. However, embeddings that rely primarily on preserving syntactic properties of knowledge bases within a vector space are limited by the kind of inferences that can be precomputed and expressed in the knowledge representation language, and do not utilize prior knowledge about the semantics of operators during the search for an embedding function.

Here, we introduce EL Embeddings, a method to generate embeddings for ontologies in the Description Logic EL++. EL Embeddings explicitly generate - or approximate - models for an EL++theory and therefore approximate the interpretation function. For this purpose, we formulate the problem of finding a model as an optimization problem over Rn . An alternative view on EL Embeddings is that we extend knowledge graph embeddings with the semantics of conjunction, existential quantification, and the bottom concept.

We demonstrate that the resulting embeddings can be used for determining semantic similarity or suggest axioms that may be entailed by the theory. As large EL++theories are mainly used in the life sciences, we evaluate our approach on a large knowledge base of protein-protein interactions and protein functions. We show that our method can improve the prediction of protein-protein interactions when compared to semantic similarity measures and to knowledge graph embeddings.

2 RelatedWork

2.1 The Description Logic EL++and Its Application in Life Sciences

The Description Logic EL++ [Baader et al., 2005] is a Description Logic for which subsumption can be decided in polynomial time and which is therefore suitable for representing and reasoning over large ontologies. The syntax and semantics of EL++ is summarized in Table 1 (omitting concrete domains which we will not consider here). EL++also forms the basis of the OWL 2 EL profile of OWL [Motik et al., 2009].

The ABox axioms (instantiation and role assertion) in EL++can be eliminated by replacing C(a) with {a} ⊑ C and r(a, b) with {a} ⊑ ∃r.{b}, and every EL++TBox can be normalized into one of four normal forms: C ⊑ D, C ⊓D ⊑ E, ∃R.C ⊑ D, and C ⊑ ∃R.D (where the bottom concept can only appear on the right-hand side and only in the first three normal forms) [Baader et al., 2005].

EL++ is widely used to represent and reason over life science ontologies such as the Gene Ontology [Ashburner et al., 2000], the Human Phenotype Ontology [Zemojtel et al., 2016], or SNOMED CT [Schulz et al., 2009]. These ontologies are often large and require fast decision procedures for automated reasoning, which EL++can provide [Baader et al., 2005]. The ontologies in the life-science domain are also used as components in knowledge graphs to structure data and provide background knowledge about classes within their domains.

2.2 Knowledge Graph Embeddings

Knowledge graph embedding methods have been developed to map entities and their relations expressed in a knowledge graph into a vector space while preserving relational and other semantic information under certain vector space relations [Nickel et al., 2016]. Translation-based embeddings, such as TransE [Bordes et al., 2013], generate vector space representations of entities and relations in a graph such that a + r ≈ b if r(a, b) is a relation in the knowledge graph. Other approaches include methods for exploring the neighborhood of nodes in the graph and encoding these nodes and their relations [Wang et al., 2017].

Knowledge graphs are heterogeneous graphs with an explicit semantics and an inference relation; one way in which the semantics of relations in a knowledge graph can be taken into account when generating knowledge graph embeddings is by pre-computing a limited form of deductive closure on the graph before finding the embeddings [Nickel et al., 2016; Wang et al., 2017]. Such an approach has also been applied successfully in the life sciences where knowledge graph embeddings based on deductively closed graphs have been used for predicting gene-disease associations or drug targets [Alshahrani et al., 2017].

2.3 Semantic Similarity

A related yet alternative approach to using knowledge graph embeddings for relational learning is the use of semantic similarity measures to compare two classes within an ontology, or two instances with respect to the axioms within an ontology [Pesquita et al., 2009]. There is a wide range of semantic similarity measures, most of which operate on graphs or sets constructed from a theory syntactically (e.g., by applying a certain closure on a theory to generate graphs) but can also be applied to model structures such as the canonical models of ALC theories [Harispe et al., 2015].

In life sciences, semantic similarity measures can be applied predictively [Pesquita et al., 2009]; ontologies provide biological features, and similarity between the biological features can be indicative of an underlying biological relation. For example, semantic similarity between proteins linked to functions in the Gene Ontology [Ashburner et al., 2000] can be used to determine protein-protein interactions based on the biological assumption that interacting proteins are likely to have similar functions [Kulmanov and Hoehndorf, 2017]; similarly, semantic similarity measures are used to identify candidate genes associated with diseases [Albrecht and Schlicker, 2007]. Widely-applied semantic similarity measures in life sciences include Resnik's similarity [Resnik, 1995] or the weighted Jaccard index [Pesquita et al., 2009]. Recently, semantic similarity is also measured based on knowledge graph embeddings, for example for predicting protein-protein interactions [Smaili et al., 2018].

3 Geometric Models for EL++

3.1 RelationModel and Normalization

Our aim is to extend knowledge graph embeddings so that they incorporate the EL++operators (conjunction, existential quantification) and can express the bottom concept ⊥. We use a relational embedding model, TransE [Bordes et al., 2013], to map relations into Rn . We chose TransE due to its simplicity; however, our method can accommodate different relational models.

Let O = (C, R, I; ax) be an EL++ontology consisting of a set of class symbols C, relation symbols R, individual symbols I, and a set of axioms ax. We first transform ax into a normal form following [Baader et al., 2005]; we eliminate the ABox by replacing each individual symbol with a singleton class and rewriting relation assertions r(a, b) and class assertions C(a) as {a} ⊑ ∃r.{b} and {a} ⊑ C. Using the conversion rules in [Baader et al., 2005] we transform the set of axioms into one of four forms where C,D,E ∈ C and R ∈ R: C ⊑ D; C ⊓ D ⊑ E; C ⊑ ∃R.D; ∃R.C ⊑ D.

3.2 Objective Functions

If an EL++theory T has a model then it also has an infinite model, and therefore it also has a model with a universe of Rn for any n (L¨owenheim-Skolem upwards) [Barwise and Etchemendy, 2002]. The embedding function our model aims to find is intended to approximate the interpretation function I in the EL++semantics (Table 1). Specifically, our embedding function η aims to map each class C to an open n-ball in Rn (η(C)) and every binary relation r to a vector in Rn . We define a geometric ontology embedding η as a pair (fη, rη) of functions that map classes and relations in O into Rn , fη : C ∪ R ↦→ Rn and rη : C ↦→ R. The function fη(x) maps a class to its center or maps a relation to its embedding vector, and rη(x) maps a class x to the radius associated with it.

We formulate one loss function for each of the normal forms so that the embedding η preserves the semantics of EL++geometrical within Rn . The total loss for finding η is the sum of the loss functions for all the normal forms. We first assume that none of the classes are ⊥. The first loss function (Eqn. 1) aims to capture the notion that, if C ⊑ D, then η(C) should lie in η(D). For all loss functions we use a margin parameter γ; if γ < 0 then η(C) lies properly inside η(D). Also, we add normalization loss for all class embeddings in the loss functions, essentially moving the centers of all n-balls representing classes to lie on the unity sphere.

The loss function for the second normal form (Eqn. 2), C ⊓ D ⊑ E, should capture the notion that the intersection or overlap of the n-balls representing C and D should lie within the n-ball representing E; while the overlap between η(C) and η(D) is not in general an n-ball, the loss should characterize the smallest n-ball which includes the intersection of η(C) and η(D) and minimizes its non-overlap with η(E). Let h = rη(c)2-rη(d)2+‖fη(c)-fη(d)‖2 2‖fη (c)-fη (d)‖ , then the center and radius of the smallest n-ball containing the intersection of η(C) and η(D) are fη(c)+ h ‖fη(c)-fη(d)‖ (fη(d)-fη(c)) and √rη(c)2 - h2 , respectively. However, we found it difficult to implement this loss due to very large gradients and therefore use the approximation of this loss given in Eqn. 2. The first term in Eqn. 2 is a penalty when the n-balls representing C and D are disjoint; the second and third terms force the center of η(E) to lie inside the intersection of η(C) and η(D);

the fourth termmakes the radius of η(E) to be larger than the radius of the smallest n-balls of the intersecting classes; this radius is strictly larger than the radius of the smallest n-ball containing the intersection and therefore satisfies the condition that the intersection should lie within η(E).

The first two normal forms do not include any quantifiers or relations. Every point that lies properly within an n-ball representing a class is a potential instance of that class, and we apply relations as transformations on these points (following the TransE relation model). Therefore, relations are transformations on n-balls. Equations 3 and 4 capture this intention.

In the normal forms for EL++, ⊥ can only occur on the right-hand side in three of the normal forms. We formulate separate loss functions for the cases in which ⊥ appear. First, C ⊓ D ⊑ ⊥ states that C and D are disjoint and therefore η(C) and η(D) should not overlap. Equation 5 captures disjointness loss.

Loss 6 captures the intuition that a class is unsatisfiable by minimizing the radius rη of the class.

Since we use TransE as model for relations, the radius of an n-ball cannot change after a transformation by a relation. Therefore, we use the same loss (Eqn. 7) for ∃R.C ⊑ ⊥.

While our model does not need negatives, we can use negatives as in translating embeddings to improve predictive performance. For this purpose, we add an optional loss for C ̸⊑ ∃R.D as in Equation 8.

Finally, we add the constraints rη(⊤) = ∞ to capture the intuition that the interpretation of ⊤ is ∆I = Rn , and rη(x) ≥ 0 for all x.

3.3 Embeddings andModels

Theorem 1 (Correctness). Let T be a theory in EL++. If γ ≤ 0 and lossn(η(T )) = 0 then T has a model.

We outline a proof of this theorem. First, we set ∆ = Rn . By construction, ⊤ = ∆I = Rn . We interpret each class C as the set of points lying within the open n-ball η(C), C I = {x ∈ Rn | ‖fη(C) -x‖ < rη(C)} and every binary relation r as a set of tuples rI = {(x, y)|x + fη(r) = y}. We need to show that the conditions in Table 1 are satisfied if loss(T) = 0. The loss is the sum of losses for the four normal forms, all of which are non-negative.

The remaining conditions are preserved for each of the four normal forms and their respective losses: by construction, normal form 1 ensures that, if C ⊑ D is in the TBox, then C I ⊆ DI ; the loss of normal form 2, C ⊓ D ⊑ E, constructs the smallest n-ball containing the intersection of η(C) and η(D) and ensures that this n-ball lies within the η(E); normal form 3, C ⊑ ∃R.D, applies a relation transformation to all instances x of C (i.e., it constructs fη(x) + fη(R) for all elements x of the n-ball η(C)) and ensures that each instance of C lies within η(D), therefore ensuring that {x ∈ Rn | ‖fη(C) -x‖ < rη(C)} ⊆ {x ∈ Rn | ‖fη(D) + fη(R) -x‖ < rη(D)} and therefore η(C) ⊆ {x ∈ Rn |∃y ∈ ∆I : (x, y) ∈ RI ∧ y ∈ DI }; normal form 4 trivially satisfies ∃R.C ⊑ D. It follows similarly from the loss functions 5-7 that ⊥ is interpreted as ∅; the only case requiring more attention is C ⊓ D ⊑ ⊥ where it is possible that the hyperspheres bounding the n-balls η(C) and η(D) touch. In our interpretation, we assume that hyperballs are open so that the n-balls are disjoint even if their bounding hyperspheres touch.

3.4 Training and Implementation

While our algorithm can find, or approximate, a model without any negative samples for any of the four normal forms, these models are usually underspecified. We intend to use our embeddings for relational learning which benefits from a representation in which asserted and implied axioms can be discriminated from those that should not hold true. Therefore, we follow a similar strategy for sampling negatives as in TransE and randomly generate corrupted axioms in third normal form (C ⊑ ∃R.D) by replacing either C or D with a class C ′ or D′ such that neither C ′ ⊑ ∃R.D nor C ⊑ ∃R.D′ are asserted axioms in the ontology.

We randomly initialize the embeddings for classes and relations. We then sample formulas for each loss function in mini-batches and update the embeddings with respect to the sum of the loss functions (see Algorithm 1). We implement the algorithm in two parts. First, the processing of ontologies in OWL format and normalization into the EL++normal forms are performed using the OWL API and the APIs provided by the jCel reasoner which implements the EL++normalization rules [Mendez, 2012]. Training of embeddings and optimization is done using Python and the TensorFlow library, and we use the Adam optimizer [Kingma and Ba, 2014] for updating embeddings 1 .

The runtime of the training process is linear in the number of axioms in the input ontology while inference time is linear in the number of all entities. The first step in the training process is eliminating the ABox by creating singleton classes for instances and transforming axioms into normal forms. This transformation can be performed in linear time with respect to the size of the TBox [Baader et al., 2005]. The second step is to compute loss functions for all axioms in our training data. Computing the loss functions is linear in the size of embeddings (which is a constant) and we compute and optimize loss functions for all axioms every epoch. Consequently, training runtime complexity is O(epochs · n · m) where n is the number of all axioms, m is the embedding size, and epochs is the number of training iterations. In order to do inference for a query, we need to compute our similarity function for all entities. Therefore, inference time complexity is linear in the number of entities and the similarity function is computed in O(m) (with the embedding size m).

Algorithm 1: Algorithm used for training EL Embeddings

• input : An ontology O = (C,R, I; ax) in OWL format; margin γ; dimension n; epochs epochs; batchsize bs output: embeddings (fη, rη) 1 // eliminate ABox 2 C ← C ∪ {a} for each a ∈ I 3 ax ← ax ∪ ({a} ⊑ ∃r.{b}) for each r(a, b) ∈ ax 4 ax ← ax ∪ ({a} ⊑ C) for each C(a) ∈ ax 5 // apply EL++normalization rules 6 (axnf1, axnf2, axnf3, axnf4) = normalize(ax) 7 // separate axioms with ⊥ for NF 1, 2 and 4 8 (axnf1, axbot1) = separate(axnf1) 9 (axnf2, axbot2) = separate(axnf3) 10 (axnf4, axbot4) = separate(axnf4) 11 // generate negatives for proteins in NF 3 12 negnf3 = negatives(axnf3) 13 D← {axnf1} ∪ {axnf2} ∪ {axnf3} ∪ {axnf4} ∪ {axbot1} ∪ {axbot2} ∪ {axbot4} ∪ {negnf 3} 14 // initialize embeddings 15 fη(c) = uniform(0, 1) for each c ∈ C 16 rη(c) = uniform(0, 1) for each c ∈ C 17 fη(r) = uniform(0, 1) for each r ∈ R 18 for e ∈ epochs do 19 // Randomly sample a minibatch of size bs for each loss type 20 (snf1, snf2, snf3, snf4, sbot1, sbot2, sbot4, sneg) = sample(D, bs) 21 // Update embeddings w.r.t. 22 ∑ ∇loss(snf1, snf2, snf3, snf4, sbot1, sbot2,
• sbot4, sneg)
• 23 end

1 All code is freely available on

https://github.com/bio-ontology-research-group/el-embeddings/

4 Experiments

4.1 Example: Family Domain

We first construct a simple test knowledge base to test our model. We use the family domain in which we generate a knowledge base that contains examples for each of the normal forms (Eqn. 9-20). We chose a margin γ = 0 and an embedding dimension of 2 so that we can visualize the generated embeddings in R2 . Figure 1 shows the resulting embeddings.

4.2 Protein-Protein Interactions

Prediction of interactions between proteins is a common task in molecular biology that relies on information about sequences as well as functional information [Pesquita et al., 2009; Kulmanov and Hoehndorf, 2017]. The information about the functions of proteins is represented through the Gene Ontology (GO) [Ashburner et al., 2000], a large manually-created ontology with over 45,000 classes and 100,000 axioms. GO can be formalized in OWL 2 EL and therefore falls in the EL++formalism [Golbreich and Horrocks, 2007]. Common approaches to predicting proteinprotein interactions (PPIs) include network-based approaches and the use of semantic similarity measures [Kulmanov and Hoehndorf, 2017].

We use the PPI dataset provided by the STRING database [Roth et al., 2016] to construct a knowledge graph of proteins and their interactions. We construct two graphs for human and yeast organisms with relations for which a confidence score of 700 or more is assigned in STRING (following recommendations in STRING [Roth et al., 2016]); if an interaction between two proteins P1 and P2 exists in STRING, we assert interacts(P1, P2). We further add the associations of proteins with functions from the GO, provided by STRING, together with all classes and relations from GO. For this we use two representation patterns. First, we generate an OWL representation in which proteins are instances, and if protein P is associated with the function F we add the axiom {P} ⊑ ∃hasFunction.F (based on the ABox axiom (∃hasFunction.F)(P)). We use this information together with the native OWL version of GO provided by the OBO Foundry repository [Smith et al., 2007]; when applying knowledge graph embeddings to this representation, we use the RDF serialization of the complete OWL knowledge base as the knowledge graph. While the OWL-based representation is suitable for our EL Embeddings, knowledge graph embeddings and semantic similarity measures would benefit from a graph-based representation. We therefore create a second representation in which we replace all axioms of the type X ⊑ ∃R.Y in GO with a relation R(X, Y ), and link proteins to their functions using a hasFunction relation (i.e., if protein P has function F , we assert R(P, F )).

We generate a training, testing, and validation split (80%/10%/10%) from interaction pairs of proteins. We use the TransE [Bordes et al., 2013] implementation in the PyKEEN framework [Jabeen et al., 2019] on both representations (native OWL/RDF and the "plain" representation) to generate knowledge graph embeddings and use them for link prediction. We implement two semantic similarity measures, Resnik's similarity [Resnik, 1995] and Lin's similarity [Harispe et al., 2015], together with the best-match average strategy for combining pairwise class similarities [Pesquita et al., 2009; Harispe et al., 2015], and compute the similarity between proteins based on their associations with GO classes. To predict PPIs with EL Embeddings, we predict whether axioms of the type {P} ⊑ ∃hasFunction.{F} hold. We use the similarity-based function in Eqn. 21 for this prediction.

We evaluate the predictive performance based on recall at rank 10, rank 100, mean rank and area under the ROC curve using our validation set. In our experiments, we perform an extensive search for optimal parameters for TransE and our EL Embeddings, testing embeddings sizes of 50, 100, 200, and 400. We also evaluate the performance with different margin parameters γ, using -0.1, -0.01, 0, 0.01, and 0.1. The optimal set of parameters for EL Embeddings are embedding size = 50 and γ = -0.1. For TransE (plain) embedding size = 50 (human) and 100 (yeast), for TransE (RDF) embedding size = 400 (human) and 200 (yeast) 2 .

2 Detailed results are available at https://www.dropbox.com/s/ wresfh9fkfah4ei/supplement.pdf?dl=0.

We report results on our testing set in Table 2 for the yeast PPI dataset and in Table 3 for the human PPI dataset.

For a query interaction interacts(P1, P2) we predict interactions of P1 to all proteins from our training set and identify the rank of P2. Then we compute the mean of ranks for all interactions in our testing set. We refer to this result as raw mean rank. Since the interactions from our training and validation set will rank higher than those in our testing set, we perform this evaluation excluding training and validation interactions and report them as Filtered. We further report the area under the ROC curve (AUC) which is more commonly used for evaluating PPI predictions [Kulmanov and Hoehndorf, 2017; Alshahrani et al., 2017].

5 Discussion

Knowledge graph embeddings and other forms of relational learning methods are increasingly applied in scientific tasks such as prediction of protein-protein interactions, genedisease associations, or drug targets. Our work on EL Embeddings is motivated by the need to incorporate background knowledge into machine learning tasks. This need exists in particular in scientific domains in which large formal knowledge bases have been created that can be utilized to constrain optimization or improve search. Our embeddings are based on the Description Logic EL++which is widely used in life science ontologies [Smith et al., 2007] and combined with biological knowledge graphs [Alshahrani et al., 2017]. EL Embeddings generate models for EL++theories and do not rely on precomputing deductive closures of graphs, and account for the semantics of conjunction, existential quantifiers, and the bottom concept (and therefore basic disjointness between classes).

While EL embeddings do not require negatives, we implement a form of negative sampling by randomly changing classes in axioms, similarly to how TransE and other knowledge graph embeddings generate negatives [Wang et al., 2017]. In future work, we intend to explore more of the negatives that arise from the EL++theories directly. For example, we can encode the unique names assumption by asserting {a} ⊓ {b} ⊑ ⊥ for all instances a, b ∈ I, and infer further negatives by exploring disjointness.

Another limitation of our method is the use of TransE as relational model which does not allow us to capture role inclusion axioms or model relations that are not one-to-one relations. Most of the EL Embedding loss functions require no or little changes when using a different relation model; however, as a consequence of using TransE as relation model, for example the loss function for ∃R.C ⊑ ⊥ is degenerate and will need to be modified. Extending the relation model is not the only extension possible to our model; in the future, we also intend to explore improvements towards covering more expressive logics than EL++.