EL Embeddings: Geometric construction of models for the Description Logic EL ++
Maxat Kulmanov Wang Liu-Wei Yuan Yan Robert Hoehndorf



One-loop functional renormalization group study for 
the dimensional reduction and its breakdown 
in the long-range random field O(N) spin model 
near lower critical dimension

    Yoshinori Sakamoto
    December 30, 2023
=================================================================================================================================================================================




  An embedding is a function that maps entities from one algebraic
  structure into another while preserving certain
  characteristics. Embeddings are being used successfully for mapping
  relational data or text into vector spaces where they can be used
  for machine learning, similarity search, or similar tasks. We
  address the problem of finding vector space embeddings for theories
  in the Description Logic that are also models of the TBox. To
  find such embeddings, we define an optimization problem that
  characterizes the model-theoretic semantics of the operators in within ^n, thereby solving the problem of finding an
  interpretation function for an theory given a particular domain
  Δ. Our approach is mainly relevant to large theories and
  knowledge bases such as the ontologies and knowledge graphs used in
  the life sciences. We demonstrate that our method can be used for
  improved prediction of protein–protein interactions when compared
  to semantic similarity measures or knowledge graph embeddings.




§ 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 ^n 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 <cit.>.

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 ^n
<cit.>.


The embeddings can project entities and relations within a knowledge
graph into ^n 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 ^n 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
<cit.>.

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) <cit.>. In particular
the life sciences have developed a large number of ontologies
formulated in the Web Ontology Language (OWL) <cit.>, and
many of the life science ontologies fall in the OWL 2 EL profile
<cit.>, which is based on the Description Logics <cit.>. 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 <cit.> or semantic similarity measures
<cit.>. 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 <cit.>. 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 Embeddings explicitly
generate – or approximate – models for an theory and therefore
approximate the interpretation function. 


For this purpose, we formulate the problem of finding a model as an
optimization problem over ^n. 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 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.



§ RELATED WORK



 §.§ The Description Logic and its application
  in life sciences




The Description Logic ℰℒ^++
<cit.> 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 ℰℒ^++ is summarized in Table
<ref> (omitting concrete domains which we will not consider
here). also forms the basis of the OWL 2 EL profile of OWL
<cit.>.

The ABox axioms (instantiation and role assertion) in can be
eliminated by replacing C(a) with { a }⊑ C and
r(a,b) with { a }⊑∃ r.{ b }, and every 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)
<cit.>.




ℰℒ^++ is widely used to represent and reason over life
science ontologies such as the Gene Ontology <cit.>,
the Human Phenotype Ontology <cit.>, or SNOMED CT
<cit.>. These ontologies are often large and require fast
decision procedures for automated reasoning, which can provide
<cit.>. 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.







 §.§ 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
<cit.>. Translation-based embeddings, such as TransE
<cit.>, generate vector space representations of entities and
relations in a graph such that
𝐚 + 𝐫≈𝐛 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 <cit.>.






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
<cit.>. 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 <cit.>.



 §.§ 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 <cit.>. 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
𝒜ℒ𝒞 theories <cit.>.

In life sciences, semantic similarity measures can be applied
predictively <cit.>; 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
<cit.> can be used to determine protein–protein
interactions based on the biological assumption that interacting
proteins are likely to have similar functions
<cit.>; similarly, semantic similarity
measures are used to identify candidate genes associated with diseases
<cit.>. Widely-applied semantic similarity measures
in life sciences include Resnik's similarity <cit.> or the
weighted Jaccard index <cit.>. Recently, semantic similarity
is also measured based on knowledge graph embeddings, for example for
predicting protein–protein interactions <cit.>.



§ GEOMETRIC MODELS FOR ℰℒ^++




 §.§ Relation model and normalization

Our aim is to extend knowledge graph embeddings so that they
incorporate the operators (conjunction, existential
quantification) and can express the bottom concept . We use a
relational embedding model, TransE <cit.>, to map relations into
^n. We chose TransE due to its simplicity; however, our method
can accommodate different relational models.

Let O = (ℂ, ℝ, 𝕀; ax) be an ontology
consisting of a set of class symbols ℂ, relation symbols
ℝ, individual symbols 𝕀, and a set of axioms
ax. We first transform ax into a normal form following <cit.>; 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 <cit.> we
transform the set of axioms into one of four forms where C, D, E ∈ℂ and R ∈ℝ: C ⊑ D; C ⊓ D
⊑ E; C ⊑∃ R.D; ∃ R.C ⊑
D. 




 §.§ Objective functions


If an theory T has a model then it also has an infinite model,
and therefore it also has a model with a universe of ^n for any
n (Löwenheim–Skolem upwards) <cit.>.  The embedding
function our model aims to find is intended to approximate the
interpretation function ℐ in the semantics (Table
<ref>).  Specifically, our embedding function η aims to map each
class C to an open n-ball in ^n (η(C)) and every binary
relation r to a vector in ^n. 
We define a geometric ontology embedding η as a pair (f_η,
r_η) of functions that map classes and relations in O into
^n, f_η : C ∪ R ↦^n and r_η : C ↦. 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 geometrical within
^n. 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. <ref>) 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.


    loss_C ⊑ D(c,d) = 
       max(0, f_η(c) - f_η(d) + r_η(c) - r_η(d) - γ) 
        + |f_η(c) - 1| + |f_η(d) - 1|


The loss function for the second normal form (Eqn. <ref>),
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/2f_η(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-h^2),
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. <ref>.  The first term in Eqn. <ref> 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 term makes 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).

    loss_C ⊓ D ⊑ E(c,d,e) = 
       max(0, f_η(c) - f_η(d) - r_η(c) - r_η(d) - γ) 
        + max(0, f_η(c) - f_η(e) - r_η(c) - γ) 
        + max(0, f_η(d) - f_η(e) - r_η(c) - γ) 
        +  max(0, min(r_η(c), r_η(d)) - r_η(e) - γ)
        + |f_η(c) - 1| + |f_η(d) - 1| + |f_η(e) - 1|


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 <ref> and <ref> capture this
intention. 

    loss_C ⊑∃ R.D(c,d,r) = 
       max(0, f_η(c) + f_η(r) - f_η(d)  + r_η(c) - r_η(d) - γ) 
        + |f_η(c) - 1| + |f_η(d) - 1|



    loss_∃ R.C ⊑ D(c,d,r) = 
       max(0, f_η(c) - f_η(r) - f_η(d) - r_η(c) - r_η(d) - γ) 
        + |f_η(c) - 1| + |f_η(d) - 1|


In the normal forms for ,  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
<ref> captures disjointness loss.

    loss_C ⊓ D ⊑(c,d,e) = 
       max(0, r_η(c) + r_η(d) - f_η(c) - f_η(d) + γ) 
        + |f_η(c) - 1| + |f_η(d) - 1|


Loss <ref> captures the intuition that a class is
unsatisfiable by minimizing the radius r_η of the class. 

    loss_C ⊑(c) = r_η(c)


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. <ref>) for ∃ R.C ⊑.

    loss_∃ R.C ⊑(c,r) = 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 <ref>.

    loss_C ⋢∃ R.D(c,d,r) = 
       max(0, r_η(c) + r_η(d) - f_η(c) + f_η(r) - f_η(d) + γ) 
        + |f_η(c) - 1| + |f_η(d) - 1|








Finally, we add the constraints r_η(⊤) = ∞ to capture the
intuition that the interpretation of ⊤ is Δ^ℐ =
^n, and r_η(x) ≥ 0 for all x. 



 §.§ Embeddings and models




  Let T be a theory in . If γ≤ 0 and
  loss_n(η(T)) = 0 then T has a model.
  
  
  
  

We outline a proof of this theorem.
First, we set Δ = ^n.
By construction, ⊤ = Δ^ℐ = ^n. We interpret
each class C as the set of points lying within the open n-ball
η(C), C^ℐ = { x ∈^n | f_η(C) - x <
r_η(C) } and every binary relation r as a set of tuples
r^ℐ = { (x,y) | x + f_η(r) = y }.
We need to show that the conditions in Table <ref> 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^ℐ⊆ D^ℐ; 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 ∈^n | f_η(C) - x < r_η(C)}⊆{ x
∈^n | f_η(D) + f_η(R) - x  < r_η(D) } and
therefore
η(C) ⊆{ x ∈^n | ∃ y ∈Δ^ℐ
: (x,y) ∈ R^ℐ y ∈ D^ℐ}; normal
form 4 trivially satisfies ∃ R.C ⊑ D. It follows
similarly from the loss functions <ref>–<ref>
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.



 §.§ 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 <ref>). We implement the algorithm in two
parts. First, the processing of ontologies in OWL format and
normalization into the normal forms are performed using the OWL API
and the APIs provided by the jCel reasoner which implements the normalization rules <cit.>. Training of embeddings and
optimization is done using Python and the TensorFlow library, and we
use the Adam optimizer <cit.> for updating embeddings.









§ EXPERIMENTS




 §.§ 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. <ref>–<ref>). We chose a margin γ = 0 and
an embedding dimension of 2 so that we can visualize the generated
embeddings in ^2. Figure <ref> shows the resulting
embeddings. 

    Male    ⊑ Person 
        Female    ⊑ Person 
        Father    ⊑ Male 
        Mother    ⊑ Female 
        Father    ⊑ Parent 
        Mother    ⊑ Parent 
        Female ⊓ Male    ⊑
        Female ⊓ Parent    ⊑ Mother 
        Male ⊓ Parent    ⊑ Father 
       ∃ hasChild.Person    ⊑ Parent 
        Parent    ⊑ Person 
        Parent    ⊑∃ hasChild.⊤





 §.§ 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 <cit.>. The
information about the functions of proteins is represented through the
Gene Ontology (GO) <cit.>, 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 formalism
<cit.>. Common approaches to predicting protein–protein
interactions (PPIs) include network-based approaches and the use of
semantic similarity measures <cit.>.

We use the PPI dataset provided by the STRING database
<cit.> 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
<cit.>); if an interaction between two proteins
P_1 and P_2 exists in STRING, we assert interacts(P_1,P_2). 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
<cit.>; 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 <cit.>
implementation in the PyKEEN framework <cit.> 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 <cit.> and Lin's similarity <cit.>,
together with the best-match average strategy for combining pairwise
class similarities <cit.>, 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. <ref>
for this prediction.

    sim(c, r, d) =  -max   (0, f_η(c) + f_η(r) -
         f_η(d)
    
       - r_η(c)     - r_η(d) - γ)


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)[Detailed results are available at
  <https://www.dropbox.com/s/wresfh9fkfah4ei/supplement.pdf?dl=0>.].
We report results on our testing set in Table <ref>
for the yeast PPI dataset and in Table <ref> for the
human PPI dataset.

For a query interaction interacts(P_1, P_2) we predict interactions
of P_1 to all proteins from our training set and identify the rank
of P_2. 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
<cit.>.



§ DISCUSSION

Knowledge graph embeddings and other forms of relational learning
methods are increasingly applied in scientific tasks such as
prediction of protein–protein interactions, gene–disease
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 which is widely used in life science
ontologies <cit.> and combined with biological knowledge
graphs <cit.>.
EL Embeddings generate models for 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
<cit.>. In future work, we intend to explore more of the
negatives that arise from the 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 .




named




