=Paper=
{{Paper
|id=Vol-3739/abstract-16
|storemode=property
|title=Strong Faithfulness for ELH Ontology Embeddings (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-3739/abstract-16.pdf
|volume=Vol-3739
|authors=Victor Lacerda,Ana Ozaki,Ricardo Guimarães
|dblpUrl=https://dblp.org/rec/conf/dlog/LacerdaO024
}}
==Strong Faithfulness for ELH Ontology Embeddings (Extended Abstract)==
https://ceur-ws.org/Vol-3739/abstract-16.pdf
Strong Faithfulness for ELH Ontology Embeddings
(Extended Abstract)
Victor Lacerda1 , Ana Ozaki1,2 and Ricardo Guimarães3
1
University of Bergen, Norway
2
University of Oslo, Norway
3
Zivid
Abstract
We present a region-based geometric model for embedding normalized ℰℒℋ ontologies into a continuous vector
space and formally prove that normalized ℰℒℋ has the strong faithfulness property on convex geometric models.
This means that there is an embedding that precisely captures the original ontology. We first prove the statement
assuming (possibly) non-convex regions, and then impose convexity on the regions, showing that the property
still holds.
Keywords
Geometric Models, Description Logics, Knowledge Graph Embedding, Faithfulness
1. Introduction
Knowledge Graphs (KGs) are a popular method for representing knowledge using triples of the form
(subject, predicate, object), called facts, corresponding to role assertions in DL ABoxes. Although KGs
contain a large number of facts, they are incomplete. This has sparked interest in using machine
learning methods to suggest plausible facts to add to the KG based on patterns found in the data using
KG embedding techniques, which aim to create representations of KGs in low-dimensional finite vector
spaces [1, 2, 3, 4].
Embeddings that consider TBoxes formulated in description logic are a more recent phenomenon, here
referred as ontology embeddings, where the ontology can have both facts and a TBox [5, 6, 7, 8, 9, 10, 11].
Ontology embeddings offer advantages over traditional KGEs as they exploit the semantic relationships
between concepts and roles. One question that arises is how similar to the source ontology these
embeddings are, and, more strictly, whether the generated embeddings are guaranteed to precisely
represent the meaning of the source ontology and its entailments (of particular interest, the TBox
entailments), such that one can freely move from its classical set-theoretic interpretation to its geometric
one. This property is called the strong model faithfulness property [7]. So far, no previous work for
ontology embeddings for fragments of ℰℒ++ has attempted to prove this property holds for their
embedding method, nor has its existence been formally proven for the ℰℒℋ language.
We investigate whether ℰℒℋ has the strong faithfulness property over convex geometric models. We
first prove the statement for embeddings in low dimensions, considering a region-based representation
for (possibly) non-convex regions. We investigate strong faithfulness on convex geometric models with a
number of dimensions connected to an ontology’s signature and domain. We do so including embeddings
for role inclusions, a problem that has not been well studied in the ℰℒℋ ontology embedding literature.
Additionally, we consider model checking in convex geometric models.
2. Preliminary Definitions
Geometric models We go from the traditional model-theoretic interpretation of the ℰℒℋ description
logic to geometric interpretations, adapting definitions by Gutiérrez-Basulto and Schockaert [4] and
DL 2024: 37th International Workshop on Description Logics, June 18–21, 2024, Bergen, Norway
$ victor.botelho@uib.no (V. Lacerda); anaoz@uio.no (A. Ozaki); ricardo.guimaraes@uib.no (R. Guimarães)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Bourgaux et al. [12]. Here we present the basic ingredients of the notion of a geometric interpretation.
The main idea of geometric models is that the sets on which we define our interpretation functions are
continuous vector spaces, and that the interpretation of concepts and roles are defined over geometric
regions.
Definition 1 (Isomorphism Preserving Linear Maps). Let 𝑚 be a natural number and 𝑓 : R𝑚 × R𝑚 ↦→
R2·𝑚 a fixed but arbitrary linear map satisfying the following:
1. the restriction of 𝑓 to R𝑚 × {0}𝑚 is injective;
2. the restriction of 𝑓 to {0}𝑚 × R𝑚 is injective;
3. 𝑓 (R𝑚 × {0}𝑚 ) ∩ 𝑓 ({0}𝑚 × R𝑚 ) = {02·𝑚 };
where 0𝑚 denotes the vector (0, ..., 0) with 𝑚 zeros. For instance, the concatenation function is a linear
map that satisfies Points 1, 2, and 3.
Definition 2 (Geometric Interpretation). Let 𝑓 be an isomorphism preserving linear map and 𝑚 a natural
number. An 𝑚-dimensional 𝑓 -geometric interpretation 𝜂 of (𝑁𝐶 , 𝑁𝑅 , 𝑁𝐼 ) assigns to each 𝐴 ∈ 𝑁𝐶 a
region 𝜂(𝐴) ⊆ R𝑚 , to each 𝑟 ∈ 𝑁𝑅 a region 𝜂(𝑟) ⊆ R2·𝑚 , and to each 𝑎 ∈ 𝑁𝐼 a vector 𝜂(𝑎) ∈ R𝑚 . We
have that 𝜂(⊥) := ∅, 𝜂(⊤) := R𝑚 , and for arbitrary ℰℒℋ concepts:
𝜂(𝐶 ⊓ 𝐷) := 𝜂(𝐶) ∩ 𝜂(𝐷) and 𝜂(∃𝑟.𝐶) := {𝑣 ∈ R𝑚 | ∃𝑢 ∈ 𝜂(𝐶) with 𝑓 (𝑣, 𝑢) ∈ 𝜂(𝑟)}.
An 𝑚-dimensional 𝑓 -geometric interpretation 𝜂 satisfies
• a concept assertion 𝐴(𝑎), if 𝜂(𝑎) ∈ 𝜂(𝐴), a role assertion 𝑟(𝑎, 𝑏), if 𝑓 (𝜂(𝑎), 𝜂(𝑏)) ∈ 𝜂(𝑟),
• an ℰℒℋ instance query (IQ) 𝐶(𝑎), if 𝜂(𝑎) ∈ 𝜂(𝐶),
• an ℰℒℋ CI 𝐶 ⊑ 𝐷, if 𝜂(𝐶) ⊆ 𝜂(𝐷), and an RI 𝑟 ⊑ 𝑠, if 𝜂(𝑟) ⊆ 𝜂(𝑠).
We write 𝜂 |= 𝛼 if 𝜂 satisfies an ℰℒℋ axiom 𝛼. A geometric interpretation satisfies an ontology 𝒪,
in symbols 𝜂 |= 𝒪, if it satisfies all axioms in 𝒪. We define model faithfulness based on the work by [7].
Definition 3 (Faithfulness). Let 𝒪 be a satisfiable ontology (or any other representation allowing the
distinction between IQs and TBox axioms). Given an 𝑚-dimensional 𝑓 -geometric interpretation 𝜂, we say
that:
• 𝜂 is a strongly concept-faithful model of 𝒪 iff, for every concept 𝐶 and individual name 𝑏, if
𝜂(𝑏) ∈ 𝜂(𝐶) then 𝒪 |= 𝐶(𝑏);
• 𝜂 is a strongly IQ-faithful model of 𝒪 iff it is strongly concept-faithful and for each role 𝑟 and
individual names 𝑎, 𝑏: if 𝑓 (𝜂(𝑎), 𝜂(𝑏)) ∈ 𝜂(𝑟), then 𝒪 |= 𝑟(𝑎, 𝑏);
• 𝜂 is a strongly TBox-faithful model of 𝒪 iff for all TBox axioms 𝜏 : if 𝜂 |= 𝜏 , then 𝒪 |= 𝜏 .
We say that an ontology language has the strong faithfulness property over a class of geometric
interpretations 𝒞 if for every satisfiable ontology 𝒪 in this language there is a geometric interpretation
in 𝒞 that is both a strongly IQ-faithful and a strongly TBox-faithful model of 𝒪.
3. Strong Faithfulness on Convex Models
We prove that normalized ℰℒℋ has the strong faithfulness property over a class of convex geometric
models. We introduce a new mapping 𝜇 from the domain of a classical interpretation ℐ to a vector space
and a new geometric interpretation 𝜂ℐ based on this mapping. Our proofs now require us to fix the
isomorphism preserving linear map 𝑓 used in the definition of geometric interpretations (Definition 2).
We choose the concatenation function, denoted ⊕, as done in Gutiérrez-Basulto and Schockaert [4].
The strategy for proving strong faithfulness for normalized ℰℒℋ requires us to (a) find a suitable
non-convex geometric interpretation for concepts and roles, and (b) show that the convex hull of the
region maintains the property.
µ(e)
A
1 µ(d)
1
B
0
1 a
Figure 1: Axes colored in red, blue, and green correspond to the dimensions for 𝑎, 𝐴, and 𝐵, respectively.
Definition 4. Let ℐ = (∆ℐ , ·ℐ ) be a classical ℰℒℋ interpretation, and 𝒪 an ℰℒℋ ontology. We start by
defining a new map 𝜇 : ∆ℐ ↦→ Rd , where d corresponds to |𝑁𝐼 (𝒪)|+|𝑁𝐶 (𝒪)|+|𝑁𝑅 (𝒪)|·|∆ℐ |. We assume,
without loss of generality, a fixed ordering in our indexing system for positions in vectors, where indices 0
to |𝑁𝐼 (𝒪)| − 1 correspond to the indices for individual names; |𝑁𝐼 (𝒪)| to 𝑘 = |𝑁𝐼 (𝒪)| + |𝑁𝐶 (𝒪)| − 1
correspond to the indices for concept names; and 𝑘 to 𝑘 + (|𝑁𝑅 (𝒪)| · |∆ℐ |) − 1 correspond to the indices
for role names together with an element of ∆ℐ . We write 𝑣[𝑎], 𝑣[𝐴], and 𝑣[𝑟, 𝑑] to refer to the position in a
vector 𝑣 corresponding to 𝑎, 𝐴, and 𝑟 together with an element 𝑑, respectively (according to our indexing
system). For example, 𝑣[𝑎] = 0 means the value at the index corresponding to the individual name 𝑎 is 0.
A vector is binary iff 𝑣 ∈ {0, 1}d . We define 𝜇 using binary vectors. For all 𝑑 ∈ ∆ℐ , 𝑎 ∈ 𝑁𝐼 , 𝐴 ∈ 𝑁𝐶
and 𝑟 ∈ 𝑁𝑅 :
• 𝜇(𝑑)[𝑎] = 1 if 𝑑 = 𝑎ℐ , otherwise 𝜇(𝑑)[𝑎] = 0,
• 𝜇(𝑑)[𝐴] = 1 if 𝑑 ∈ 𝐴ℐ , otherwise 𝜇(𝑑)[𝐴] = 0, and
• 𝜇(𝑑)[𝑟, 𝑒] = 1 if (𝑑, 𝑒) ∈ 𝑟ℐ , otherwise 𝜇(𝑑)[𝑟, 𝑒] = 0.
We introduce a definition for (possibly) non-convex geometric interpretations, using 𝜇.
Definition 5. Let ℐ be a classical ℰℒℋ interpretation. The geometric interpretation of ℐ, denoted 𝜂ℐ , is
defined as:
𝜂ℐ (𝑎) := 𝜇(𝑎ℐ ), for all 𝑎 ∈ 𝑁𝐼 ,
𝜂ℐ (𝐴) := {𝜇(𝑑) | 𝜇(𝑑)[𝐴] = 1, 𝑑 ∈ ∆ℐ }, for all 𝐴 ∈ 𝑁𝐶 ,
𝜂ℐ (𝑟) := {𝜇(𝑑) ⊕ 𝜇(𝑒) | 𝜇(𝑑)[𝑟, 𝑒] = 1, 𝑑, 𝑒 ∈ ∆ℐ }, for all 𝑟 ∈ 𝑁𝑅 .
An intuitive way of thinking about our definition 𝜇 is that it maps domain elements to a subset of
the vertex set of the d-dimensional unit hypercube, as in Fig. 1.
Example 1. Consider 𝐴, 𝐵 ∈ 𝑁𝐶 and 𝑎 ∈ 𝑁𝐼 . Let ℐ be an interpretation with 𝑑, 𝑒 ∈ ∆ℐ such that
𝑑 = 𝑎ℐ , 𝑑 ∈ 𝐴ℐ , and 𝑒 ∈ 𝐴ℐ ∩ 𝐵 ℐ . We illustrate 𝜇(𝑑) and 𝜇(𝑒) in Fig. 1. In symbols, 𝜇(𝑑)[𝑎] = 1,
𝜇(𝑑)[𝐴] = 1, and 𝜇(𝑑)[𝐵] = 0, while 𝜇(𝑒)[𝑎] = 0, 𝜇(𝑒)[𝐴] = 1, and 𝜇(𝑒)[𝐵] = 1.
Theorem 1. For all ℰℒℋ axioms 𝛼, ℐ |= 𝛼 iff 𝜂ℐ𝒪 |= 𝛼.
The canonical models need to be finite because the definition of 𝜂ℐ uses vectors in a finitely-
dimensional space whose dimension depends on the size of ∆𝐼 and 𝒪. We then employ finite canonical
models for normalized ℰℒℋ since canonical models for arbitrary ℰℒℋ CIs are not guaranteed to be
finite. The following holds for the canonical model just defined.
Theorem 2. Let 𝒪 be a normalized ℰℒℋ ontology. The following holds
• for all ℰℒℋ IQs and CIs 𝛼 in normal form over sig(𝒪), ℐ𝒪 |= 𝛼 iff 𝒪 |= 𝛼; and
• for all RIs 𝛼 over sig(𝒪), ℐ𝒪 |= 𝛼 iff 𝒪 |= 𝛼.
Theorem 3. Let 𝒪 be an ℰℒℋ ontology and let ℐ𝒪 be the canonical model of 𝒪. The d-dimensional
(possibly non-convex) ⊕-geometric interpretation 𝜂ℐ𝒪 of ℐ𝒪 is a strongly and IQ and TBox faithful model
of 𝒪.
Here, the vectors mapped by 𝜇 and the regions given by the non-convex geometric interpretation 𝜂ℐ
are the anchor points for the convex closure of these sets. The geometric interpretation obtained by
taking the convex hull is denoted 𝜂ℐ* .
Theorem 4. Let 𝜂ℐ be a geometric interpretation as in Definition 5. If 𝛼 is an ℰℒℋ CI, an ℰℒℋ RI, or an
ℰℒℋ IQ in normal form then 𝜂ℐ |= 𝛼 iff 𝜂ℐ* |= 𝛼.
Since normalized ℰℒℋ has a finite canonical model, we can take advantage of the previous theorem
to generalize it to arbitrary interpretations by applying it to the canonical ℐ𝒪 of 𝒪.
Theorem 5. Let 𝒪 be a normalized ℰℒℋ ontology and let ℐ𝒪 be the canonical model of 𝒪. The d-
dimensional convex ⊕-geometric interpretation of ℐ𝒪 is a strongly IQ and TBox faithful model of 𝒪.
Corollary 6. Normalized ℰℒℋ has the strong faithful property over ⊕-geometric interpretations.
Acknowledgments
Lacerda is supported by the Research Council of Norway, project number 316022, led by Ozaki.
References
[1] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, O. Yakhnenko, Translating embeddings
for modeling multi-relational data, in: C. J. Burges, L. Bottou, M. Welling, Z. Ghahramani,
K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems, volume 26, Cur-
ran Associates, Inc., ., 2013. URL: https://proceedings.neurips.cc/paper_files/paper/2013/file/
1cecc7a77928ca8133fa24680a88d2f9-Paper.pdf.
[2] R. Abboud, I. Ceylan, T. Lukasiewicz, T. Salvatori, BoxE: A box embedding model for knowl-
edge base completion, in: H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, H. Lin
(Eds.), Advances in Neural Information Processing Systems, volume 33, Curran Associates,
Inc., ., 2020, p. 9649–9661. URL: https://proceedings.neurips.cc/paper_files/paper/2020/file/
6dbbe6abe5f14af882ff977fc3f35501-Paper.pdf.
[3] A. Pavlovic, E. Sallinger, ExpressivE: A spatio-functional embedding for knowledge graph comple-
tion, in: The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali,
Rwanda, May 1-5, 2023, OpenReview.net, 2023. URL: https://openreview.net/pdf?id=xkev3_np08z.
[4] V. Gutiérrez-Basulto, S. Schockaert, From knowledge graph embedding to ontology embedding?
an analysis of the compatibility between vector space representations and rules, in: M. Thielscher,
F. Toni, F. Wolter (Eds.), KR, AAAI Press, ., 2018, pp. 379–388. URL: https://aaai.org/ocs/index.php/
KR/KR18/paper/view/18013.
[5] B. Xiong, N. Potyka, T.-K. Tran, M. Nayyeri, S. Staab, Faithful embeddings for EL++ knowledge
bases, in: The Semantic Web – ISWC 2022, Springer International Publishing, ., 2022, pp. 22–38.
doi:10.1007/978-3-031-19433-7_2.
[6] M. Jackermeier, J. Chen, I. Horrocks, Box2 el: Concept and role box embeddings for the description
logic EL++, CoRR abs/2301.11118 (2023). URL: https://doi.org/10.48550/arXiv.2301.11118.
[7] Ö. L. Özçep, M. Leemhuis, D. Wolter, Cone semantics for logics with negation, in: C. Bessiere
(Ed.), IJCAI, ijcai.org, ., 2020, pp. 1820–1826.
[8] X. Peng, Z. Tang, M. Kulmanov, K. Niu, R. Hoehndorf, Description logic EL++ embeddings
with intersectional closure, CoRR abs/2202.14018 (2022). URL: https://arxiv.org/abs/2202.14018.
arXiv:2202.14018.
[9] X. Peng, Z. Tang, M. Kulmanov, K. Niu, R. Hoehndorf, Description logic EL++ embeddings with
intersectional closure, CoRR abs/2202.14018 (2022). URL: https://arxiv.org/abs/2202.14018.
[10] S. Mondal, S. Bhatia, R. Mutharaju, Emel++: Embeddings for EL++ description logic, in: A. Martin,
K. Hinkelmann, H. Fill, A. Gerber, D. Lenat, R. Stolle, F. van Harmelen (Eds.), AAAI-MAKE, volume
2846 of CEUR Workshop Proceedings, CEUR-WS.org, ., 2021. URL: https://ceur-ws.org/Vol-2846/
paper19.pdf.
[11] C. d’Amato, N. F. Quatraro, N. Fanizzi, Injecting background knowledge into embedding models
for predictive tasks on knowledge graphs, in: R. Verborgh, K. Hose, H. Paulheim, P.-A. Champin,
M. Maleshkova, O. Corcho, P. Ristoski, M. Alam (Eds.), The Semantic Web, Springer International
Publishing, Cham, 2021, p. 441–457.
[12] C. Bourgaux, A. Ozaki, J. Z. Pan, Geometric models for (temporally) attributed description logics,
in: M. Homola, V. Ryzhikov, R. A. Schmidt (Eds.), DL, volume 2954 of CEUR Workshop Proceedings,
CEUR-WS.org, ., 2021. URL: https://ceur-ws.org/Vol-2954/paper-7.pdf.