# Capturing Knowledge Graphs and Rules with Octagon Embeddings

Victor Charpenay1 Steven Schockaert2
1Ḿines Saint-Etienne, UMR 6158 LIMOS, Saint-Étienne, France
2Cardiff University, Cardiff, UK
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Region based knowledge graph embeddings represent relations as geometric
regions. This has the advantage that the rules which are captured by the model
are made explicit, making it straightforward to incorporate prior knowledge
and to inspect learned models. Unfortunately, existing approaches are severely
restricted in their ability to model relational composition, and hence also
their ability to model rules, thus failing to deliver on the main promise of
region based models. With the aim of addressing these limitations, we
investigate regions which are composed of axis-aligned octagons. Such octagons
are particularly easy to work with, as intersections and compositions can be
straightforwardly computed, while they are still sufficiently expressive to
model arbitrary knowledge graphs. Among others, we also show that our octagon
embeddings can properly capture a non-trivial class of rule bases. Finally, we
show that our model achieves competitive experimental results.

##  1 Introduction

Knowledge graphs, i.e. sets of (entity, relation, entity) triples, have become
one of the most popular frameworks for knowledge representation, with
applications ranging from search Reinanda et al. (2020) and recommendation Guo
et al. (2022) to natural language processing Schneider et al. (2022) and
computer vision Marino et al. (2017). Their popularity has spurred an
extensive line of work dedicated to representation learning on knowledge
graphs. Most works in this area focus on the paradigm of knowledge graph
embedding Bordes et al. (2011), aiming to learn a vector representation
$\mathbf{e}$ for each entity $e$ and a scoring function $s_{r}$ for each
relation $r$ such that $s_{r}(\mathbf{e},\mathbf{f})$ reflects the likelihood
that $(e,r,f)$ is a valid triple, i.e. that entity $e$ is in relation $r$ with
entity $f$.

Knowledge graph embeddings are intended to capture semantic regularities,
making it possible to predict plausible triples that were missing from the
original knowledge graph. Consider, for instance, the seminal TransE model
Bordes et al. (2013), which uses scoring functions of the form
$s_{r}(\mathbf{e},\mathbf{f})=-d(\mathbf{e}+\mathbf{r},\mathbf{f})$, where
$\mathbf{r}\in\mathbb{R}^{n}$ is an embedding of the relation $r$,
$\mathbf{e},\mathbf{f}\in\mathbb{R}^{n}$ are entity embeddings of the same
dimension and $d$ is a distance metric. Note that
$s_{r}(\mathbf{e},\mathbf{f})$ achieves its maximal value of $0$ iff
$\mathbf{e}+\mathbf{r}=\mathbf{f}$. We can thus say that the embedding fully
supports the triple $(e,r,f)$ when $s_{r}(\mathbf{e},\mathbf{f})=0$. If
$\mathbf{r_{1}}+\mathbf{r_{2}}=\mathbf{r_{3}}$ we have that
$s_{r_{1}}(\mathbf{e},\mathbf{f})=0$ and $s_{r_{2}}(\mathbf{f},\mathbf{g})=0$
together imply $s_{r_{3}}(\mathbf{e},\mathbf{g})=0$. In this sense, we can say
that the embedding captures the following rule:

$\displaystyle r_{1}(X,Y)\wedge r_{2}(Y,Z)\rightarrow r_{3}(X,Z)$ (1)

This correspondence between knowledge graph embeddings and symbolic rules is
appealing. For instance, if we already know that (1) is valid, we can impose
$\mathbf{r_{1}}+\mathbf{r_{2}}=\mathbf{r_{3}}$ when learning the embedding. We
can also use this correspondence to inspect which semantic dependencies a
learned embedding is capturing. Unfortunately, TransE has some inherent
limitations, which mean that certain knowledge graphs cannot be faithfully
captured Wang et al. (2018). This has been addressed in more recent models
such as ComplEx Trouillon et al. (2017), ConvE Dettmers et al. (2018) and
TuckER Balazevic et al. (2019b), to name just a few, but while these models
often perform better on the task of link prediction, the connection between
their parameters and the captured semantic dependencies is considerably more
opaque.

Region based knowledge graph embedding models Gutiérrez-Basulto and Schockaert
(2018); Abboud et al. (2020); Pavlovic and Sallinger (2023) aim to get the
best of both worlds, increasing the expressivity of TransE while maintaining
an explicit correspondence between model parameters and semantic dependencies.
They represent each relation $r$ as a geometric region
$X_{r}\subseteq\mathbb{R}^{2n}$. We say that a triple $(e,r,f)$ is captured by
the embedding if $\mathbf{e}\oplus\mathbf{f}\in X_{r}$, where $\oplus$ denotes
vector concatenation. To characterise semantic dependencies, we can then
exploit the fact that the intersection, subsumption and composition of
relations can be naturally modelled in terms of their embeddings $X_{r}$. For
instance, we say that the embedding captures the rule $r_{1}(X,Y)\wedge
r_{2}(X,Y)\rightarrow r_{3}(X,Y)$ iff $X_{r_{1}}\cap X_{r_{2}}\subseteq
X_{r_{3}}$. To model rules of the form (1), we can characterise relational
composition as follows:

$\displaystyle X_{r}\diamond
X_{s}=\\{\mathbf{e}\oplus\mathbf{g}\,|\,\exists\mathbf{f}\in\mathbb{R}^{n}\,.\,\mathbf{e}\oplus\mathbf{f}\in
X_{r}\wedge\mathbf{f}\oplus\mathbf{g}\in X_{s}\\}$ (2)

We then say that (1) is captured iff $X_{r_{1}}\diamond X_{r_{2}}\subseteq
X_{r_{3}}$. Rules of the form (1), which are sometimes referred to as closed
path rules, play an important role in link prediction Meilicke et al. (2019).
When designing a region based model, it is thus important that the composition
of regions can be straightforwardly characterised. However, existing
approaches are severely limited in this respect. For instance, BoxE Abboud et
al. (2020) cannot model relational composition at all, while ExpressivE
Pavlovic and Sallinger (2023) uses parallelograms, which are not closed under
composition.

To address these concerns, our aim in this paper is to develop a region based
model which is as simple as possible, while (i) still being expressive enough
to capture arbitrary knowledge graphs and (ii) using regions which are closed
under intersection and composition. Based on these desiderata, we arrive at a
model which relies on axis-aligned octagons (with all angles fixed at 45
degrees). We show that despite their simplicity, the proposed octagon
embeddings are sufficiently expressive to properly capture a large class of
rule bases. This is an important property, among others because it means that
we can inject prior knowledge, in the form of a given rule base, without
unintended consequences. Our result is considerably more general than what is
possible with BoxE, which is not able to capture any closed path rules, and
more general than what is known about ExpressivE. Moreover, because
compositions and intersections of octagons can be straightforwardly computed,
octagon embeddings are considerably more practical than existing alternatives.
While our main focus is on better understanding the expressivity of region
based models, we have also empirically evaluated the proposed octagon
embeddings. We found octagons to achieve results close to the current state-
of-the-art. This demonstrates that learning octagon embeddings is a promising
strategy, especially in contexts where both knowledge graphs and rules need to
be modelled.

##  2 Preliminaries

Let $\mathcal{E}$ and $\mathcal{R}$ be sets of entities and relations
respectively. We consider knowledge graph embeddings in which each entity
$e\in\mathcal{E}$ is represented by a vector $\mathbf{e}\in\mathbb{R}^{n}$ and
each relation $r\in\mathcal{R}$ is represented by a region
$X_{r}\subseteq\mathbb{R}^{2n}$. We refer to such representations as region-
based knowledge graph embeddings. We say that a triple $(e,r,f)$ is captured
or supported by a given embedding if $\mathbf{e}\oplus\mathbf{f}\subseteq
X_{r}$. This notion of support allows us to unambiguously associate a
knowledge graph with a given geometric embedding, which in turn allows us to
study the expressivity of knowledge graph embedding models. In practice, we
typically use regions with soft boundaries. This makes learning easier and it
is better aligned with the fact that link prediction is typically treated as a
ranking problem rather than a classification problem. We will return to the
issue of learning regions with soft boundaries in Section 5.

(a) TransE bands

(b) Hexagons

Figure 1: Basic region based embeddings. Figure 2: Region-based embeddings
with octagons.

#### Coordinate-wise region embeddings.

Region based embeddings were first studied from a theoretical point of view in
Gutiérrez-Basulto and Schockaert (2018). Their setting allowed relations to be
represented by arbitrary convex polytopes. Using such regions is not feasible
in practice, however, as they require exponentially many parameters. A natural
solution is to use regions $X_{r}$ which can be described using $n$ two-
dimensional regions $X^{i}_{r}$:

$\displaystyle
X_{r}\,{=}\,\\{(x_{1}{,}...,x_{n},y_{1}{,}...,y_{n})\,|\,\forall
i\in\\{1{,}...,n\\}.(x_{i},y_{i})\in X^{i}_{r}\\}$ (3)

We call such region based embeddings _coordinate-wise_. For example, we can
view TransE as a coordinate-wise region based embedding model, where

$\displaystyle X^{i}_{r}=\\{(x,y)\,|\,u_{i}^{-}\leq y-x\leq u_{i}^{+}\\}$ (4)

In this case, the two-dimensional regions correspond to unbounded bands, as
illustrated in Figure 1. ExpressivE Pavlovic and Sallinger (2023) is also a
coordinate-wise model, where the regions $X^{i}_{r}$ are parallelograms. An
important drawback of parallelograms is that they are not closed under
composition: if $X^{i}_{r_{1}}$ and $X^{i}_{r_{2}}$ are parallelograms, then
it may be that $X^{i}_{r_{1}}\diamond X^{i}_{r_{2}}$ is not a parallelogram,
with $\diamond$ defined as in (2). Similarly, parallelograms are not closed
under intersection. To address these limitations, we can consider some
alternatives. Starting from the TransE bands defined in (4), a natural
generalisation is to add domain and range constraints, i.e. to use hexagonal
regions of the following form, as also illustrated in Figure 1:

$\displaystyle X^{i}_{r}=\\{(x,y)\,|\,$ $\displaystyle u_{i}^{-}\leq y-x\leq
u_{i}^{+},$ (5) $\displaystyle x_{i}^{-}\leq x\leq x_{i}^{+},y_{i}^{-}\leq
y\leq y_{i}^{+}\\}$

Unfortunately, as we will see in Section 4, such hexagons are not sufficiently
expressive to capture arbitrary knowledge graphs. As a minimal extension, we
consider octagons of the following form, as illustrated in Figure 2:

$\displaystyle X^{i}_{r}=\\{(x,y)\,|\,$ $\displaystyle u_{i}^{-}\leq y-x\leq
u_{i}^{+},v_{i}^{-}\leq x+y\leq v_{i}^{+},$ (6) $\displaystyle x_{i}^{-}\leq
x\leq x_{i}^{+},y_{i}^{-}\leq y\leq y_{i}^{+}\\}$

Throughout the paper, we will refer to regions of the form (6) as octagons.
However, note that some of these regions are degenerate, having in fact fewer
than eight vertices.

#### Cross-coordinate region embeddings.

Some region based models go beyond coordinate-wise embeddings. We will refer
to them as _cross-coordinate_ models. For instance, BoxE Abboud et al. (2020)
uses regions of the following form:

$\displaystyle X_{r}=\\{$
$\displaystyle(x_{1},\ldots,x_{2n},y_{1},\ldots,y_{2n})\,|\,$ (7)
$\displaystyle\forall
i\in\\{1,\ldots,n\\}\,.\,(x_{i},y_{n+i})\,{\in}\,A^{i}_{r}\wedge(x_{n+i},y_{i})\,{\in}\,B^{i}_{r}\\}$

An advantage of cross-coordinate models is that they can rely on simpler two-
dimensional regions. For instance, the regions $A^{i}_{r}$ and $B^{i}_{r}$ in
the BoxE model essentially correspond to TransE bands. While a coordinate-wise
model with TransE bands is not sufficiently expressive to capture arbitrary
knowledge graphs, by using cross-coordinate comparisons, BoxE can circumvent
this limitation.

#### Capturing rules.

The main promise of region based models is that the spatial configuration of
the regions reveals the semantic dependencies that are captured. Let us first
consider a closed-path rule of the following form:

$\displaystyle r_{1}(X_{1},X_{2})\wedge\ldots\wedge
r_{k}(X_{k},X_{k+1})\rightarrow r(X_{1},X_{k+1})$ (8)

Such a rule can be encoded using relational composition and set inclusion, as
follows:

$r_{1}\circ\ldots\circ r_{k}\subseteq r$

Accordingly, we say that a region based embedding captures this rule iff the
following inclusion holds:

$X_{r_{1}}\diamond\ldots\diamond X_{r_{k}}\subseteq X_{r}$

Other types of rules can be modelled in a similar way. For instance, a rule
such as $r_{1}(X,Y)\wedge r_{2}(X,Y)\rightarrow r(X,Y)$ is captured by a
region based embedding if $X_{r_{1}}\cap X_{r_{2}}\subseteq X_{r}$.

To illustrate how rules can be captured by region based embeddings, first
consider a coordinate-wise model with TransE bands, i.e. regions of the form
(4). We have that $X_{r_{1}}\diamond\ldots\diamond X_{r_{k}}\subseteq X_{r}$
holds iff $\sum_{i=1}^{k}u_{r_{i}}^{-}\geq u_{r}^{-}$ and
$\sum_{i=1}^{k}u_{r_{i}}^{+}\leq u_{r}^{+}$. This means that every rule of the
form (8) can be satisfied. However, the model is not sensitive to the order in
which the relations in the body appear. For instance, whenever
$r_{1}(X,Y)\wedge r_{2}(Y,Z)\rightarrow r(X,Z)$ is satisfied, we also have
that $r_{2}(X,Y)\wedge r_{1}(Y,Z)\rightarrow r(X,Z)$ is satisfied, which is
clearly undesirable. Coordinate-wise models with TransE bands are thus not
sufficiently expressive to properly capture rules.

Now consider a cross-coordinate model such as BoxE, using regions of the form
(71). It holds that $(x_{1},\allowbreak\ldots,\allowbreak x_{2n},\allowbreak
z_{1},\allowbreak\ldots,\allowbreak z_{2n})\in X_{r_{1}}\diamond X_{r_{2}}$
iff there are $y_{1},\allowbreak\ldots,\allowbreak y_{2n}\in\mathbb{R}$ such
that for every $i\in\\{1,\ldots,n\\}$ we have:

$\displaystyle(x_{i},y_{n+i})$ $\displaystyle\in A_{r_{1}}^{i}$
$\displaystyle(x_{n+i},y_{i})$ $\displaystyle\in B_{r_{1}}^{i}$
$\displaystyle(y_{i},z_{n+i})$ $\displaystyle\in A_{r_{2}}^{i}$
$\displaystyle(y_{n+i},z_{i})$ $\displaystyle\in B_{r_{2}}^{i}$

This is the case iff for every $i\in\\{1,\ldots,n\\}$ we have:

$\displaystyle(x_{i},z_{i})$ $\displaystyle\in A_{r_{1}}^{i}\diamond
B_{r_{2}}^{i}$ $\displaystyle(x_{n+i},z_{n+i})$ $\displaystyle\in
B_{r_{1}}^{i}\diamond A_{r_{2}}^{i}$

While $X_{r_{1}}\diamond X_{r_{2}}$ constrains the pairs $(x_{i},z_{i})$ and
$(x_{n+i},z_{n+i})$, any region $X_{r_{3}}$ rather constrains the pairs
$(x_{i},z_{n+i})$ and $(x_{n+i},z_{i})$. It is thus not possible to have
$X_{r_{1}}\diamond X_{r_{2}}\subseteq X_{x_{3}}$, unless in trivial cases
where $X_{r_{1}}=\emptyset$, $X_{r_{2}}=\emptyset$, or (if infinite bounds are
allowed) $X_{r_{3}}=\mathbb{R}^{4n}$. In all these trivial cases, the
embedding also captures other rules, e.g. if $X_{r_{1}}=\emptyset$ then all
rules of the form $r_{1}(X,Y)\wedge r_{4}(Y,Z)\rightarrow r_{5}(X,Z)$ are also
satisfied.

ExpressivE is able to capture rules of the form (8), while avoiding unintended
consequences Pavlovic and Sallinger (2023). However, in practice we are
typically interested in capturing _sets_ of such rules, and it is unclear
under which conditions this is possible with ExpressivE. Another drawback of
ExpressivE is that compositions and intersections of regions are difficult to
compute, which, among others, makes checking whether a given rule is satisfied
computationally expensive. Moreover, it is not clear how injecting rules into
the learning process can then be done in a practical way.

##  3 Modelling Relations with Octagons

In this paper, we focus on coordinate-wise models where the two-dimensional
regions are octagons. Let us write $X_{r}=[O_{1}^{r},\ldots,O_{n}^{r}]$ to
denote that relation $r$ is defined using the octagons
$O_{1}^{r},\ldots,O_{n}^{r}$, in the sense that
$(x_{1},\allowbreak\ldots,\allowbreak x_{n},\allowbreak
y_{1},\allowbreak\ldots,\allowbreak y_{n})\in X_{r}$ iff $(x_{i},y_{i})\in
O_{i}^{r}$ for each $i\in\\{1,\ldots,n\\}$. Clearly, if
$X_{r}=[O_{1}^{r},\ldots,O_{n}^{r}]$ and $X_{s}=[O_{1}^{s},\ldots,O_{n}^{s}]$
then we have $X_{r}\cap X_{s}=[O_{1}^{r}\cap O_{1}^{s},\ldots,O_{n}^{r}\cap
O_{n}^{s}]$ and $X_{r}\diamond X_{s}=[O_{1}^{r}\diamond
O_{1}^{s},\allowbreak\ldots,\allowbreak O_{n}^{r}\diamond O_{n}^{s}]$. To
study how properties such as reflexivity, symmetry and transitivity can be
satisfied in octagon embeddings, it is thus sufficient to study these
properties for individual octagons, which is what we focus on in this section.

#### Parameterisation.

Let us write $\mathsf{Octa}(x_{i}^{-},\allowbreak x_{i}^{+},\allowbreak
y_{i}^{-},\allowbreak y_{i}^{+},\allowbreak u_{i}^{-},\allowbreak
u_{i}^{+},\allowbreak v_{i}^{-},\allowbreak v_{i}^{+})$ to denote the octagon
defined in (6). Note that the eight parameters are not independent. For
instance, we have that $\mathsf{Octa}(x^{-},\allowbreak x^{+},\allowbreak
y^{-},\allowbreak y^{+},\allowbreak u^{-},\allowbreak u^{+},\allowbreak
v^{-},\allowbreak v^{+})=\mathsf{Octa}(x^{-},\allowbreak x^{+},\allowbreak
y^{-},\allowbreak y^{+},\allowbreak u^{-},\allowbreak
u^{+},\allowbreak\max(v^{-},x^{-}+y^{-}),\allowbreak v^{+})$. Indeed, if
$x\geq x^{-}$ and $y\geq y^{-}$, we also have $x+y\geq x^{-}+y^{-}$, meaning
that the bound $x+y\geq v^{-}$ can be strengthened to
$x+y\geq\max(x^{-}+y^{-},v^{-})$. We call the parameters $(x^{-},\allowbreak
x^{+},\allowbreak y^{-},\allowbreak y^{+},\allowbreak u^{-},\allowbreak
u^{+},\allowbreak v^{-},\allowbreak v^{+})$ _normalised_ if they cannot be
strengthened, i.e. if increasing any of the lower bounds or decreasing any of
the upper bounds always leads to a different octagon. As the following
proposition reveals, we can easily normalise any set of parameters.111All
proofs can be found in the appendix.

######  Proposition 1.

Consider the following set of parameters:

$\displaystyle x_{1}^{-}=$
$\displaystyle\max(x^{-},v^{-}-y^{+},y^{-}-u^{+},0.5\cdot(v^{-}-u^{+}))$
$\displaystyle x_{1}^{+}=$
$\displaystyle\min(x^{+},v^{+}-y^{-},y^{+}-u^{-},0.5\cdot(v^{+}-u^{-}))$
$\displaystyle y_{1}^{-}=$
$\displaystyle\max(y^{-},u^{-}+x^{-},v^{-}-x^{+},0.5\cdot(u^{-}+v^{-}))$
$\displaystyle y_{1}^{+}=$
$\displaystyle\min(y^{+},u^{+}+x^{+},v^{+}-x^{-},0.5\cdot(u^{+}+v^{+}))$
$\displaystyle u_{1}^{-}=$
$\displaystyle\max(u^{-},y^{-}-x^{+},v^{-}-2x^{+},2y^{-}-v^{+})$
$\displaystyle u_{1}^{+}=$
$\displaystyle\min(u^{+},y^{+}-x^{-},v^{+}-2x^{-},2y^{+}-v^{-})$
$\displaystyle v_{1}^{-}=$
$\displaystyle\max(v^{-},x^{-}+y^{-},u^{-}+2x^{-},2y^{-}-u^{+})$
$\displaystyle v_{1}^{+}=$
$\displaystyle\min(v^{+},x^{+}+y^{+},u^{+}+2x^{+},2y^{+}-u^{-})$

Then
$\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})=\mathsf{Octa}(x_{1}^{-},\allowbreak
x_{1}^{+},\allowbreak y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak
u_{1}^{-},\allowbreak u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$.
Furthermore, if we have $x_{1}^{-}>x_{1}^{+}$, $y_{1}^{-}>y_{1}^{+}$,
$u_{1}^{-}>u_{1}^{+}$ or $v_{1}^{-}>v_{1}^{+}$ then
$\mathsf{Octa}(x^{-},\allowbreak x^{+},\allowbreak y^{-},\allowbreak
y^{+},\allowbreak u^{-},\allowbreak u^{+},\allowbreak v^{-},\allowbreak
v^{+})=\emptyset$. Otherwise, the set of parameters $(x_{1}^{-},\allowbreak
x_{1}^{+},\allowbreak y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak
u_{1}^{-},\allowbreak u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$
is normalised.

Figure 3: Example of an octagon encoding a transitive relation.

#### Capturing relational properties.

As we saw in the previous section, two operations are of particular importance
for capturing rules: intersection and composition. The _intersection_ of
$\mathsf{Octa}(x_{1}^{-},\allowbreak x_{1}^{+},\allowbreak
y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak u_{1}^{-},\allowbreak
u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$ and
$\mathsf{Octa}(x_{2}^{-},\allowbreak x_{2}^{+},\allowbreak
y_{2}^{-},\allowbreak y_{2}^{+},\allowbreak u_{2}^{-},\allowbreak
u_{2}^{+},\allowbreak v_{2}^{-},\allowbreak v_{2}^{+})$ is the following
octagon:

$\displaystyle\mathsf{Octa}($
$\displaystyle\max(x_{1}^{-},x_{2}^{-}),\allowbreak\min(x_{1}^{+},x_{2}^{+}),\max(y_{1}^{-},y_{2}^{-}),$
$\displaystyle\min(y_{1}^{+},y_{2}^{+}),\allowbreak\max(u_{1}^{-},u_{2}^{-}),\allowbreak\min(u_{1}^{+}u_{2}^{+}),$
$\displaystyle\max(v_{1}^{-},v_{2}^{-}),\allowbreak\min(v_{1}^{+},v_{2}^{+}))$

Octagons are also closed under _composition_ , as the following proposition
reveals.

######  Proposition 2.

Let $O_{1}=\mathsf{Octa}(x_{1}^{-},\allowbreak x_{1}^{+},\allowbreak
y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak u_{1}^{-},\allowbreak
u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$ and
$O_{2}=\mathsf{Octa}(x_{2}^{-},\allowbreak x_{2}^{+},\allowbreak
y_{2}^{-},\allowbreak y_{2}^{+},\allowbreak u_{2}^{-},\allowbreak
u_{2}^{+},\allowbreak v_{2}^{-},\allowbreak v_{2}^{+})$ be non-empty octagons
with normalised parameters. Then $O_{1}\diamond
O_{2}=\mathsf{Octa}(x_{3}^{-},\allowbreak x_{3}^{+},\allowbreak
y_{3}^{-},\allowbreak y_{3}^{+},\allowbreak u_{3}^{-},\allowbreak
u_{3}^{+},\allowbreak v_{3}^{-},\allowbreak v_{3}^{+})$, where:

$\displaystyle x_{3}^{-}$
$\displaystyle=\max(x_{1}^{-},x_{2}^{-}-u_{1}^{+},v_{1}^{-}-x_{2}^{+})$
$\displaystyle x_{3}^{+}$
$\displaystyle=\min(x_{1}^{+},x_{2}^{+}-u_{1}^{-},v_{1}^{+}-x_{2}^{-})$
$\displaystyle y_{3}^{-}$
$\displaystyle=\max(y_{2}^{-},u_{2}^{-}+y_{1}^{-},v_{2}^{-}-y_{1}^{+})$
$\displaystyle y_{3}^{+}$
$\displaystyle=\min(y_{2}^{+},u_{2}^{+}+y_{1}^{+},v_{2}^{+}-y_{1}^{-})$
$\displaystyle u_{3}^{-}$
$\displaystyle=\max(y_{2}^{-}-x_{1}^{+},u_{2}^{-}+u_{1}^{-},v_{2}^{-}-v_{1}^{+})$
$\displaystyle u_{3}^{+}$
$\displaystyle=\min(y_{2}^{+}-x_{1}^{-},u_{2}^{+}+u_{1}^{+},v_{2}^{+}-v_{1}^{-})$
$\displaystyle v_{3}^{-}$
$\displaystyle=\max(x_{1}^{-}+y_{2}^{-},u_{2}^{-}+v_{1}^{-},v_{2}^{-}-u_{1}^{+})$
$\displaystyle v_{3}^{+}$
$\displaystyle=\min(x_{1}^{+}+y_{2}^{+},u_{2}^{+}+v_{1}^{+},v_{2}^{+}-u_{1}^{-})$

The _inverse_ of a relation can also be straightforwardly characterised. Let
us define the inverse of an octagon
$O=\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})$ as:

$\displaystyle
O^{\text{inv}}=\mathsf{Octa}(y^{-},y^{+},x^{-},x^{+},-u^{+},-u^{-},v^{-},v^{+})$
(9)

Then clearly we have $(x,y)\in O$ iff $(y,x)\in O^{\text{inv}}$, hence the
relation encoded by $O^{\text{inv}}$ is indeed the inverse of the relation
encoded by $O$. It also follows that $O$ is _symmetric_ if the following
conditions are satisfied: $x^{-}=y^{-}$, $x^{+}=y^{+}$ and $u^{-}=-u^{+}$.
Similarly, assuming the parameters are normalised, the relation captured by
the octagon $O$ is _reflexive_ over its domain $[x^{-},x^{+}]$, i.e. $\forall
x\in[x^{-},x^{+}]\,.\,(x,x)\in O$, iff the following conditions are satisfied:

  * •

$u^{-}\leq 0\leq u^{+}$;

  * •

$v^{-}\leq 2x^{-}\leq 2x^{+}\leq v^{+}$.

From the definition of composition, it straightforwardly follows that a non-
empty octagon with normalised coordinates is _transitive_ , i.e. satisfies
$O\diamond O\subseteq O$, iff the following conditions are satisfied:

  * •

$u^{-}\leq\max(y^{-}-x^{+},2u^{-},v^{-}-v^{+})$;

  * •

$u^{+}\geq\min(y^{+}-x^{-},2u^{+},v^{+}-v^{-})$;

  * •

$v^{-}\leq\max(x^{-}+y^{-},u^{-}+v^{-},v^{-}-u^{+})$;

  * •

$v^{+}\geq\min(x^{+}+y^{+},u^{+}+v^{+},v^{+}-u^{-})$.

We can also show the following.

######  Proposition 3.

Let $O=\mathsf{Octa}(x^{-},\allowbreak x^{+},\allowbreak y^{-},\allowbreak
y^{+},\allowbreak u^{-},\allowbreak u^{+},\allowbreak v^{-},\allowbreak
v^{+})$ and assume that these parameters are normalised. It holds that
$O\diamond O=O$ iff one of the following conditions is satisfied:

  * •

$O=\emptyset$;

  * •

$O=[x^{-},x^{+}]\times[y^{-},y^{+}]$ with $x^{+}\geq y^{-}$ and $x^{-}\leq
y^{+}$;

  * •

$O=\\{(x,x)\,|\,x\in[x^{-},x^{+}]\\}$;

  * •

$u^{-}=0$, $u^{+}>0$, $v^{-}<v^{+}$, $v^{-}-x^{+}\leq x^{-}$, $x^{+}\leq
v^{+}-x^{-}$, $v^{-}-y^{+}\leq y^{-}$, $y^{+}\leq v^{+}-y^{-}$ and
$u^{+}=\min(y^{+}-x^{-},v^{+}-v^{-})$;

  * •

$u^{-}<0$, $u^{+}=0$, $v^{-}<v^{+}$, $v^{-}-x^{+}\leq x^{-}$, $x^{+}\leq
v^{+}-x^{-}$, $v^{-}-y^{+}\leq y^{-}$, $y^{+}\leq v^{+}-y^{-}$ and
$u^{-}=\max(y^{-}-x^{+},v^{-}-v^{+})$.

Figure 3 shows an octagon which satisfies the conditions from the fourth case.
If we compose an octagon with itself a sufficient number of times, we always
end up with one of the octagon types from Proposition 3. In particular, let us
define $O^{(m)}$ as $O^{(m-1)}\diamond O$ for $m\geq 2$ and $O^{(1)}=O$. We
then have the following result.

######  Proposition 4.

If $v^{-}<v^{+}$ then there exists some $m\geq 1$ such that $O^{(m)}\diamond
O=O^{(m)}$.

##  4 Expressivity of Octagon Embeddings

We now study the ability of octagon embeddings to capture knowledge graphs and
rules. We will denote a given knowledge graph embedding as $\gamma$. Such an
embedding represents each entity $e\in\mathcal{E}$ as the vector
$\gamma(e)\in\mathbb{R}^{n}$ and each relation $r\in\mathcal{R}$ as the region
$\gamma(r)\subseteq\mathbb{R}^{2n}$. We say that $\gamma$ is an octagon
embedding if it is a coordinate-wise model in which $\gamma(r)$ is defined in
terms of octagons, for each $r\in\mathcal{R}$.

###  4.1 Capturing Knowledge Graphs

With each region based embedding $\gamma$ we can associate the knowledge graph
$\mathcal{G}_{\gamma}=\\{(e,r,f)\,|\,\gamma(e)\oplus\gamma(f)\in\gamma(r)\\}$.
An important question is whether a given region based embedding model is
capable of modelling any knowledge graph, i.e. whether for any knowledge graph
$\mathcal{G}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ there
exists an embedding $\gamma$ such that $\mathcal{G}=\mathcal{G}_{\gamma}$.
When using coordinate-wise embeddings with TransE bands, this is not possible
Wang et al. (2018); Kazemi and Poole (2018). In fact, for a coordinate-wise
model with hexagons of the form (69) this is still not possible as the
following proposition reveals.

######  Proposition 5.

Let $X_{r}$ be a hexagon region of the form (69) and let
$\mathbf{e},\mathbf{f}\in\mathbb{R}^{n}$. If $\mathbf{e}\oplus\mathbf{f}\in
X_{r}$ and $\mathbf{f}\oplus\mathbf{e}\in X_{r}$ then we also have
$\mathbf{e}\oplus\mathbf{e}\in X_{r}$.

From this proposition, it follows that the hexagon model cannot correctly
capture a knowledge graph containing the triples $(e,r,f)$ and $(f,r,e)$ but
not $(e,r,e$). However, if we use octagons instead of hexagons, we can
correctly capture any knowledge graph.

######  Proposition 6.

Let $\mathcal{G}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ be a
knowledge graph. There exists an octagon embedding $\gamma$ such that
$\mathcal{G}=\mathcal{G}_{\gamma}$.

###  4.2 Capturing Rules

We now analyse which sets of rules can be correctly captured by octagon
embeddings. Previous work Abboud et al. (2020) has focused in particular on
the following types of rules222 _Asymmetry_ rule was called _anti-symmetry_ in
Abboud et al. (2020). We use the former to avoid any confusion with the
standard notion of anti-symmetric relations. Furthermore, Abboud et al. (2020)
defined _inversion_ as $r_{1}(X,Y)\equiv r_{2}(Y,X)$. We consider inversion as
a rule, since the equivalence can be straightforwardly recovered by two
inversion rules.:

Symmetry: $\displaystyle r(X,Y)\rightarrow r(Y,X)$ (10) Asymmetry:
$\displaystyle r(X,Y)\rightarrow\neg r(Y,X)$ (11) Inversion: $\displaystyle
r_{1}(X,Y)\rightarrow r_{2}(Y,X)$ (12) Hierarchy: $\displaystyle
r_{1}(X,Y)\rightarrow r_{2}(X,Z)$ (13) Intersection: $\displaystyle
r_{1}(X,Y)\wedge r_{2}(X,Y)\rightarrow r_{3}(X,Y)$ (14) Mutual exclusion:
$\displaystyle r_{1}(X,Y)\wedge r_{2}(X,Y)\rightarrow\bot$ (15) Composition:
$\displaystyle r_{1}(X,Y)\wedge r_{2}(Y,Z)\rightarrow r_{3}(X,Z)$ (16)

Let us define the inverse region $X_{r}^{\textit{inv}}$ as follows:

$X_{r}^{\textit{inv}}{=}\\{(x_{1},...,x_{n},y_{1},...,y_{n})\,|\,(y_{1},...,y_{n},x_{1},...,x_{n})\in
X_{r}\\}$

Note that when $X_{r}=[O_{1},\ldots,O_{n}]$ then
$X_{r}^{\textit{inv}}=[O_{1}^{\textit{inv}},\allowbreak\ldots,\allowbreak
O_{n}^{\textit{inv}}]$ with $O_{i}^{\textit{inv}}$ as defined in (9). Each of
the aforementioned rule types can be straightforwardly modelled using regions.
In particular, we say that a region based embedding $\gamma$ captures or
satisfies (10) iff $\gamma(r)\subseteq\gamma(r)^{\textit{inv}}$; (11) iff
$\gamma(r)\cap\gamma(r)^{\textit{inv}}=\emptyset$; (12) iff
$\gamma(r_{1})\subseteq\gamma(r_{2})^{\textit{inv}}$; (13) iff
$\gamma(r_{1})\subseteq\gamma(r_{2})$; (14) iff
$\gamma(r_{1})\cap\gamma(r_{2})\subseteq\gamma(r_{3})$; (15) iff
$\gamma(r_{1})\cap\gamma(r_{2})=\emptyset$; and (16) iff
$\gamma(r_{1})\diamond\gamma(r_{2})\subseteq\gamma(r_{3})$. For a set of rules
$\mathcal{K}$ and a rule $\rho$, we write $\mathcal{K}\models\rho$ to denote
that $\rho$ is entailed by $\mathcal{K}$ in the usual sense. We also write
$\gamma\models\rho$ to denote that the embedding $\gamma$ captures the rule
$\rho$.

We are interested in analysing whether a given region based embedding model
can capture a set of rules $\mathcal{K}$, without capturing any other rules,
i.e. such that for any rule $\rho$ it holds that $\gamma\models\rho$ iff
$\mathcal{K}\models\rho$. Whether this is possible in general depends on the
kinds of rules which $\mathcal{K}$ is permitted to contain. We first show a
negative result. We call a region based embedding $\gamma$ convex if
$\gamma(r)$ is convex for every $r\in\mathcal{R}$.

######  Proposition 7.

There exists a consistent set of hierarchy, intersection and mutual exclusion
rules $\mathcal{K}$ such that every convex embedding of the form (70) or (71)
which satisfies $\mathcal{K}$ also satisfies some hierarchy rule which is not
entailed by $\mathcal{K}$.

We can show the same result when only hierarchy, intersection and asymmetry
rules are permitted. Note that Proposition 17 also applies to BoxE, and thus
contradicts the claim from Abboud et al. (2020) that BoxE can capture
arbitrary consistent sets of symmetry, asymmetry, inversion, hierarchy,
intersection and mutual exclusion rules. The underlying issue relates to the
fact that the considered embeddings are defined from two-dimensional regions,
and when these regions are convex, Helly’s theorem imposes restrictions on
when intersections of such regions can be disjoint. Furthermore, note that
Abboud et al. (2020) did not consider composition rules, as such rules cannot
be captured by BoxE. When we omit asymmetry, mutual exclusion and composition
rules, we can capture any rule base, as the following result shows.

######  Proposition 8.

Let $\mathcal{K}$ be a set of symmetry, inversion, hierarchy and intersection
rules. There exists a coordinate-wise octagon embedding $\gamma$ which
satisfies $\mathcal{K}$, and which only satisfies those symmetry, inversion,
hierarchy and intersection rules which are entailed by $\mathcal{K}$, and
which does not satisfy any asymmetry, mutual exclusion and composition rules.

Let us now shift our focus to composition rules. First, we have the following
negative result, showing that octagon embeddings cannot capture arbitrary sets
of composition rules.

######  Proposition 9.

Let $\mathcal{K}=\\{r_{1}(X,Y)\wedge r_{1}(Y,Z)\rightarrow
r_{2}(X,Z),r_{2}(X,Y)\wedge r_{2}(Y,Z)\rightarrow r_{3}(X,Z)\\}$. It holds
that every octagon embedding $\gamma$ which satisfies $\mathcal{K}$ also
satisfies some composition rule which is not entailed by $\mathcal{K}$.

The underlying issue relates to composition rules where the same relation
appears more than once. If we exclude such cases, we can correctly embed sets
of composition rules.

######  Definition 1.

An _extended composition rule_ over a set of relations $\mathcal{R}$ is an
expression of the form:

$r_{1}(X_{1},X_{2})\wedge\ldots\wedge r_{k}(X_{k},X_{k+1})\rightarrow
r_{k+1}(X_{1},X_{k+1})$

where $k\geq 1$ and $r_{1},\ldots,r_{k+1}\in\mathcal{R}$. Such a rule is
called _regular_ if we have $r_{i}\neq r_{j}$ for $i\neq j$.

Regular composition rules generalise the hierarchy and composition rules from
Abboud et al. (2020), noting that the latter work also required the three
relations appearing in composition rules to be distinct.

######  Proposition 10.

Let $\mathcal{K}$ be a set of regular composition rules. Assume that any
extended composition rule entailed by $\mathcal{K}$ is either a trivial rule
of the form $r\subseteq r$ or a regular rule. There exists an octagon
embedding $\gamma$ which satisfies $\mathcal{K}$, and which only satisfies
those extended composition rules which are entailed by $\mathcal{K}$.

This result is significant given the importance of composition rules for link
prediction Meilicke et al. (2019), among others. Moreover, a similar result
was not yet shown in previous work on region based embeddings, to the best of
our knowledge. At the same time, however, the result is limited by the fact
that only regular rules are considered and no inverse relations. Knowledge
graph completion often relies (explicitly or implicitly) on rules such as
$\textit{playsForTeam}(X,Y)\wedge\textit{playsForTeam}^{-1}(Y,Z)\wedge\textit{playsSport}(Z,U)\rightarrow\textit{playsSport}(X,U)$.
Our analysis suggests that capturing sets of such rules would require an
octagon model with cross-coordinate comparisons, which we leave as a topic for
future work.

##  5 Learning Octagon Embeddings

In our theoretical analysis, determining whether a triple $(e,r,f)$ is
supported by an embedding was based on a discrete criterion: either
$\mathbf{e}\oplus\mathbf{f}$ lies in $X_{r}$ or it does not. In practice,
however, we need to learn regions with fuzzy boundaries, given that link
prediction is typically treated as a ranking problem, rather than a
classification problem. Continuous representations are typically also easier
to learn than discrete structures. Let us consider a region
$X_{r}=[O_{1}^{r},\ldots,O_{n}^{r}]$, where
$O_{i}^{r}=\mathsf{Octa}(x_{i}^{-},\allowbreak
x_{i}^{+},\allowbreak,y_{i}^{-},\allowbreak
y_{i}^{+},\allowbreak,u_{i}^{-},\allowbreak
u_{i}^{+},\allowbreak,v_{i}^{-},\allowbreak v_{i}^{+},\allowbreak)$. Let us
write $\mathbf{x}^{-}=(x_{1}^{-},\ldots,x_{n}^{-})$ and similar for
$\mathbf{x}^{+}$, $\mathbf{y}^{-}$, $\mathbf{y}^{+}$, $\mathbf{u}^{-}$,
$\mathbf{u}^{+}$, $\mathbf{v}^{-}$ and $\mathbf{v}^{+}$. Octagon embeddings
impose the following four constraints on an entity pair $(e,f)$:

$\displaystyle\mathbf{x}^{-}$ $\displaystyle\leq\mathbf{e}\leq\mathbf{x}^{+}$
$\displaystyle\mathbf{y}^{-}$ $\displaystyle\leq\mathbf{f}\leq\mathbf{y}^{+}$
$\displaystyle\mathbf{u}^{-}$
$\displaystyle\leq\mathbf{f}-\mathbf{e}\leq\mathbf{u}^{+}$
$\displaystyle\mathbf{v}^{-}$
$\displaystyle\leq\mathbf{e}+\mathbf{f}\leq\mathbf{v}^{+}$

We will refer to the regions defined by these four constraints as _bands_. We
can straightforwardly use the sigmoid function $\sigma$ to convert the
constraints into soft scores. For the $u$-constraint we can use the following
“distance” to the $u$-band:

$\displaystyle\text{dist}_{u}(e,r,f)$
$\displaystyle=\sigma\big{(}|(\mathbf{f}-\mathbf{e})-\mathbf{u}_{c}|-\mathbf{u}_{w}\big{)}$
(17)

where we write $\mathbf{u}_{c}=(\mathbf{u}^{+}+\mathbf{u}^{-})/2$ and
$\mathbf{u}_{w}=(\mathbf{u}^{+}-\mathbf{u}^{-})/2$. The functions
$\text{dist}_{x}$, $\text{dist}_{y}$ and $\text{dist}_{v}$ are defined
analogously. Note that $\mathbf{e}\oplus\mathbf{f}\in X_{r}$ iff
$\text{dist}_{x}(e,r,f)\geq 0.5$, $\text{score}_{y}(e,r,f)\geq 0.5$,
$\text{dist}_{u}(e,r,f)\geq 0.5$ and $\text{dist}_{v}(e,r,f)\geq 0.5$.
Furthermore note that BoxE and ExpressivE also convert interval constraints
into soft scores. However, rather than using scores of the form (17), these
models use a piecewise linear function of the distance to the centre of the
interval. Although a different slope is used for points inside and outside the
interval, we may question to what extent the resulting embeddings still define
regions. While the regions defined by scoring functions of the form (17) also
have fuzzy boundaries, this “fuzziness” is mostly limited to the immediate
vicinity of the boundary.

We also consider a variant of the distance function (17) which uses learnable
attention weights $\mathbf{u}_{\text{att}}$, as follows:

$\text{dist}^{\prime}_{u}(e,r,f)=\mathbf{u}_{\text{att}}\odot\text{dist}_{u}(e,r,f)$
(18)

where we write $\odot$ for component-wise multiplication. Weighted variants of
$\text{dist}_{x}$, $\text{dist}_{y}$ and $\text{dist}_{v}$ are defined
analogously. The attention weights intuitively allow the model to “forget”
certain constraints, e.g. by focusing only (or primarily) on the $u$ band in
some coordinates. An overall score is calculated as follows (and similar for
the weighted variant):

$s(e,r,f)=-\|\sum_{i\in\\{u,v,x,y\\}}\text{dist}_{i}(e,r,f)\|_{p}$ (19)

As in BoxE and ExpressivE, coordinate-wise scores are aggregated to a scalar
by taking their negated norm. In the above expression, $p$ is a
hyperparameter. Learning occurs by minimizing the following margin loss
function with self-adversarial negative sampling Sun et al. (2019):

$\displaystyle-\log\big{(}\sigma(\lambda-s(e,r,f))\big{)}-\sum_{i=1}^{|N|}\alpha_{i}\log\big{(}\sigma(s(e_{i},r,f_{i})-\lambda)\big{)}$

where
$\mathbf{\alpha}=\text{softmax}(\left[s(e_{1},r,f_{1});\ldots;s(e_{n},r,f_{n})\right]$,
the margin $\lambda$ is a hyperparameter, and
$N=\\{(e_{1},r,f_{1}),\allowbreak\ldots,\allowbreak(e_{n},r,f_{n})\\}$ is a
set of randomly sampled negative examples.

##  6 Experimental Results

We consider several variants of our model. The full model is denoted by uvxy,
whereas ux refers to a model in which $\text{dist}_{v}$ and $\text{dist}_{y}$
are not used, and similar for the other variants. For $uv$ and $uvxy$, we have
used the variant with attention weights (18). For the other configurations,
attention weights were not used, as they were found to make little
difference333A more complete analysis of the impact of attention weights can
be found in the appendix.. Note that our $u$ model is almost identical to
TransE, except that an explicit width parameter is used, while uv can be seen
as a variant of ExpressivE without learnable scale factors.

Table 1 compares the performance of our model with TransE Bordes et al.
(2013), BoxE Abboud et al. (2020) and ExpressivE Pavlovic and Sallinger (2023)
for link prediction, using the two most common benchmarks Toutanova and Chen
(2015); Dettmers et al. (2018). As usual, performance is measured using
Hits@$k$ and Mean Reciprocal Rank (MRR). All results are for 1000-dimensional
embeddings for FB15k-237 and 500-dimensional embeddings for WN18RR, following
BoxE and ExpressivE’s experimental setup. Other hyperparameters are specified
in the appendix.

| FB15k-237 | WN18RR
---|---|---
| H@1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10 | MRR
TransE | 22.3 | 37.2 | 53.1 | 33.2 | 01.3 | 40.1 | 52.9 | 22.3
BoxE | 23.8 | 37.4 | 53.8 | 33.7 | 40.0 | 47.2 | 54.1 | 45.1
ExpressivE | 24.3 | 36.6 | 51.2 | 33.3 | 46.4 | 52.2 | 59.7 | 50.8
$u$ | 22.8 | 37.2 | 53.2 | 33.0 | 00.4 | 40.4 | 52.0 | 21.6
$ux$ | 22.9 | 36.4 | 52.6 | 32.7 | 00.4 | 40.4 | 53.2 | 22.0
$uxy$ | 22.8 | 36.5 | 52.3 | 32.6 | 01.7 | 46.7 | 53.8 | 22.5
$uv^{*}$ | 23.0 | 35.7 | 51.1 | 32.3 | 42.8 | 46.5 | 50.1 | 45.5
$uvxy^{*}$ | 22.8 | 35.6 | 50.6 | 32.0 | 44.3 | 49.9 | 56.6 | 48.5
Table 1: Link prediction performances of region based embedding models.
Configurations with ∗ use the variant with attention weights.

Figure 4: Distribution of scale factors in 40-dimensional ExpressivE
embeddings for FB15k-237 (left) and WN18RR (right).

The performance of $u$ is almost identical to TransE, which suggests that the
addition of an explicit width parameter plays no significant role. Adding the
$x$, $y$ and $v$ constraints does not bring any benefits on FB15k-237. On
WN18RR, however, introducing the $v$ constraint has a big impact on H@1, which
goes from less than 1% for $u$, $ux$ and $uxy$ to more than 40% for $uv$ and
$uvxy$. This result is in line with Proposition 5, which states that hexagons
cannot capture relations that are both symmetric and irreflexive: for most
WN18RR relations, models without $v$ constraints incorrectly rank $(e,r,e)$
triples first. Including the $x$ and $y$ constraints also clearly helps the
model in the case of WN18RR. Introducing attention weights, as in (18), has a
significant positive effect on the overall performance on WN18RR but not for
FB15k-237. For instance, without attention weights, $uvxy$ achieves a H@1 of
4.8, H@3 of 43.5, H@10 of 53.4 and MRR of 25.5 (not shown). As Table 1 shows,
$uvxy$ outperforms BoxE on all metrics. Further analysis can be found in the
appendix.

Overall, we find that octagon embeddings slightly, but consistently,
underperform ExpressivE. We may wonder whether this reflects the inherent
limitations of using fixed angles. In fact, when inspecting the scale factors
in learned ExpressivE embedddings, we noticed that most are close to $-1$, $0$
or $1$ (see Figure 4). In other words, most of the learned parallelograms are
diamonds ($uv$), bands ($u$, $v$, $x$, $y$) and squares ($xy$), all of which
can be represented in our octagon model. This suggests that the
underperformance of the octagon model is rather the result of
overparameterisation. On the one hand, we have shown theoretically that all
four constraints are needed to capture semantic dependencies, and this is also
confirmed by our empirical results on WN18RR. On the other hand, not all
constraints might be needed for all coordinates. The use of attention weights
was inspired by this view, but the weights themselves of course also introduce
further parameters.

##  7 Related Work

Knowledge graph embeddings have generally been classified in three broad
categories: linear models, tensor decomposition models and neural models Hogan
et al. (2021). Linear models use a distance to score triples, after applying a
linear transformation to entity or relation embeddings, e.g. a translation
Bordes et al. (2013) or rotation Sun et al. (2019). Region based models can
essentially be viewed under the same umbrella, where the idea of computing
distances between points is generalised to evaluating relationships between
points and regions. Tensor decomposition models, such as ComplEx Trouillon et
al. (2017); Lacroix et al. (2018), TuckER Balazevic et al. (2019b) and QuatE
Zhang et al. (2019), view knowledge graphs as a three-dimensional tensor,
which can be factorised into (low-rank) entity and relation embeddings. While
these models tend to perform well, they often come with a significantly higher
computational cost. Another important limitation is that they are far less
interpretable in terms of how they capture semantic dependencies between
relations. Bilinear models also have important theoretical limitations when it
comes to capturing rules Gutiérrez-Basulto and Schockaert (2018). Neural
models, including ConvE Dettmers et al. (2018) and graph neural network based
approaches Zhu et al. (2021), are even less interpretable than tensor
decomposition models.

Knowledge graph embeddings have been combined with rules in various ways. For
instance, it has been proposed to incorporate learned rules Guo et al. (2018)
or hard ontological constraints Abboud et al. (2020) when learning knowledge
graph embeddings. Conversely, learned embeddings have been exploited for
implementing an efficient rule mining system Omran et al. (2018). The ability
of models to capture rules has also been evaluated indirectly, for instance by
analysing their inductive generalisation capabilities Trouillon et al. (2019)
or their ability to capture intersections and compositions of relations for
evaluating complex queries Arakelyan et al. (2021); Wang et al. (2023).

Region based approaches are closely related to ontology embeddings. In
particular, several models have recently been introduced for the Description
Logic $\mathcal{EL}^{++}$, which features subsumption and composition of
relations, as well as union and intersection of concepts. Concepts are
typically embedded as hyperballs Mondal et al. (2021) or hypercubes Xiong et
al. (2022). The Box2EL model Jackermeier et al. (2023) also represents
relations as regions, based on BoxE, which was found to improve performance.
Given the limitations of BoxE on modeling composition, an evaluation of more
expressive region based models is likely to yield even better results,
although such an evaluation is yet to be performed.

##  8 Conclusions

The study of region based knowledge graph embedding essentially aims to
identify the simplest models that are capable of capturing particular types of
reasoning patterns. Despite the extensive work on knowledge graph embedding,
there are still surprisingly many open questions on this front. With the aim
of furthering our understanding of region based models, we have studied an
approach based on octagons. Octagons where shown to be capable of capturing
arbitrary knowledge graphs, while a simpler model based on hexagons is not.
Octagons also have the desired property of being closed under intersection and
composition, which is not the case for closely related models such as BoxE and
ExpressivE. We have furthermore shown that the octagon model is capable of
modelling (particular) sets of composition rules, which is an important
property that was not yet shown for existing region based models. Our
empirical results show that octagon embeddings slightly underperform
ExpressivE and further work is needed to better understand whether this
performance gap can be closed by changing how the octagons are learned.

## Acknowledgments

Computations have been performed on the supercomputer facilities of the
Mésocentre Clermont-Auvergne of the Université Clermont Auvergne. Steven
Schockaert was supported by grants from EPSRC (EP/W003309/1) and the
Leverhulme Trust (RPG-2021-140).

##  Appendix A Modelling Relations with Octagons

###  A.1 Parameterisation

In general, we can strengthen the bounds of an octagon
$\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})$ as follows:

$\displaystyle x^{-}$
$\displaystyle\leftarrow\max\left(x^{-},v^{-}-y^{+},y^{-}-u^{+},\frac{v^{-}-u^{+}}{2}\right)$
(20) $\displaystyle x^{+}$
$\displaystyle\leftarrow\min\left(x^{+},v^{+}-y^{-},y^{+}-u^{-},\frac{v^{+}-u^{-}}{2}\right)$
(21) $\displaystyle y^{-}$
$\displaystyle\leftarrow\max\left(y^{-},u^{-}+x^{-},v^{-}-x^{+},\frac{u^{-}+v^{-}}{2}\right)$
(22) $\displaystyle y^{+}$
$\displaystyle\leftarrow\min\left(y^{+},u^{+}+x^{+},v^{+}-x^{-},\frac{u^{+}+v^{+}}{2}\right)$
(23) $\displaystyle u^{-}$
$\displaystyle\leftarrow\max\left(u^{-},y^{-}-x^{+},v^{-}-2x^{+},2y^{-}-v^{+}\right)$
(24) $\displaystyle u^{+}$
$\displaystyle\leftarrow\min\left(u^{+},y^{+}-x^{-},v^{+}-2x^{-},2y^{+}-v^{-}\right)$
(25) $\displaystyle v^{-}$
$\displaystyle\leftarrow\max\left(v^{-},x^{-}+y^{-},u^{-}+2x^{-},2y^{-}-u^{+}\right)$
(26) $\displaystyle v^{+}$
$\displaystyle\leftarrow\min\left(v^{+},x^{+}+y^{+},u^{+}+2x^{+},2y^{+}-u^{-}\right)$
(27)

To see why these update rules are sound, let us consider for instance the
first rule. The reason why we can strengthen $x^{-}$ to $v^{-}y^{+}$, in case
$x^{+}<v^{-}-y^{+}$ is because $v^{-}$ is a lower bound on $x+y$ and $y^{+}$
is an upper bound on $y$, hence $v^{-}-y^{+}$ is a lower bound on $(x+y)-y=x$.
The other cases are all analogous. It turns out that applying the update rules
(20)–(27) once is sufficient for obtaining a normalised set of parameters, as
captured by the following proposition.

######  Proposition 11.

Consider the following set of parameters:

$\displaystyle x_{1}^{-}=$
$\displaystyle\max\left(x^{-},v^{-}-y^{+},y^{-}-u^{+},\frac{v^{-}-u^{+}}{2}\right)$
$\displaystyle x_{1}^{+}=$
$\displaystyle\min\left(x^{+},v^{+}-y^{-},y^{+}-u^{-},\frac{v^{+}-u^{-}}{2}\right)$
$\displaystyle y_{1}^{-}=$
$\displaystyle\max\left(y^{-},u^{-}+x^{-},v^{-}-x^{+},\frac{u^{-}+v^{-}}{2}\right)$
$\displaystyle y_{1}^{+}=$
$\displaystyle\min\left(y^{+},u^{+}+x^{+},v^{+}-x^{-},\frac{u^{+}+v^{+}}{2}\right)$
$\displaystyle u_{1}^{-}=$
$\displaystyle\max\left(u^{-},y^{-}-x^{+},v^{-}-2x^{+},2y^{-}-v^{+}\right)$
$\displaystyle u_{1}^{+}=$
$\displaystyle\min\left(u^{+},y^{+}-x^{-},v^{+}-2x^{-},2y^{+}-v^{-}\right)$
$\displaystyle v_{1}^{-}=$
$\displaystyle\max\left(v^{-},x^{-}+y^{-},u^{-}+2x^{-},2y^{-}-u^{+}\right)$
$\displaystyle v_{1}^{+}=$
$\displaystyle\min\left(v^{+},x^{+}+y^{+},u^{+}+2x^{+},2y^{+}-u^{-}\right)$

Then
$\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})=\mathsf{Octa}(x_{1}^{-},\allowbreak
x_{1}^{+},\allowbreak y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak
u_{1}^{-},\allowbreak u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$.
Furthermore, if we have $x_{1}^{-}>x_{1}^{+}$, $y_{1}^{-}>y_{1}^{+}$,
$u_{1}^{-}>u_{1}^{+}$ or $v_{1}^{-}>v_{1}^{+}$ then
$\mathsf{Octa}(x^{-},\allowbreak x^{+},\allowbreak y^{-},\allowbreak
y^{+},\allowbreak u^{-},\allowbreak u^{+},\allowbreak v^{-},\allowbreak
v^{+})=\emptyset$. Otherwise, the set of parameters $(x_{1}^{-},\allowbreak
x_{1}^{+},\allowbreak y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak
u_{1}^{-},\allowbreak u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$
is normalised.

###### Proof.

The fact that
$\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})=\emptyset$ as
soon as $x_{1}^{-}>x_{1}^{+}$, $y_{1}^{-}>y_{1}^{+}$, $u_{1}^{-}>u_{1}^{+}$ or
$v_{1}^{-}>v_{1}^{+}$ follows immediately from the soundness of the update
rules (20)–(27). Let us therefore assume $x_{1}^{-}\leq x_{1}^{+}$,
$y_{1}^{-}\leq y_{1}^{+}$, $u_{1}^{-}\leq u_{1}^{+}$ or $v_{1}^{-}\leq
v_{1}^{+}$. Note that this also entails $x^{-}\leq x^{+},y^{-}\leq
y^{+},u^{-}\leq u^{+},v^{-}\leq v^{+}$. We show that the following points
belong to $\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})$:

$\displaystyle(x_{1}^{-},v_{1}^{-}-x_{1}^{-})$
$\displaystyle(x_{1}^{-},u_{1}^{+}+x_{1}^{-})$
$\displaystyle(y_{1}^{+}-u_{1}^{+},y_{1}^{+})$
$\displaystyle(v_{1}^{+}-y_{1}^{+},y_{1}^{+})$
$\displaystyle(x_{1}^{+},v_{1}^{+}-x_{1}^{+})$
$\displaystyle(x_{1}^{+},u_{1}^{-}+x_{1}^{+})$
$\displaystyle(y_{1}^{-}-u_{1}^{-},y_{1}^{-})$
$\displaystyle(v_{1}^{-}-y_{1}^{-},y_{1}^{-})$

This is sufficient to show the proposition, because each of the lower and
upper bounds is witnessed for one of these points. For instance, the fact that
$(x_{1}^{-},v_{1}^{-}-x_{1}^{-})$ belongs to the octagon implies that the
lower bound $x_{1}^{-}$ is tight, while the fact that
$(y_{1}^{+}-u_{1}^{+},y_{1}^{+})$ belongs to the octagon implies that the
upper bound $u_{1}^{+}$ is tight.

To show that $(x_{1}^{-},v_{1}^{-}-x_{1}^{-})$ belongs to the octagon, we have
to verify that the following inequalities are satisfied:

$\displaystyle x^{-}\leq x_{1}^{-}\leq x^{+}$ $\displaystyle y^{-}\leq
v_{1}^{-}-x_{1}^{-}\leq y^{+}$ $\displaystyle u^{-}\leq
v_{1}^{-}-2x_{1}^{-}\leq u^{+}$ $\displaystyle v^{-}\leq v_{1}^{-}\leq v^{+}$

We find:

  * •

We trivially have $x^{-}\leq x_{1}^{-}$.

  * •

We obtain $x_{1}^{-}\leq x^{+}$ from the assumption that $x_{1}^{-}\leq
x_{1}^{+}$ and the fact that $x_{1}^{+}\leq x^{+}$.

  * •

We now show $y^{-}\leq v_{1}^{-}-x_{1}^{-}$:

    * –

If $x_{1}^{-}=x^{-}$ we have $v_{1}^{-}-x_{1}^{-}=v_{1}^{-}-x^{-}\geq
x^{-}+y^{-}-x^{-}=y^{-}$.

    * –

If $x_{1}=v^{-}-y^{+}$ we have $v_{1}^{-}-x_{1}^{-}\geq
v^{-}-(v^{-}-y^{+})=y^{+}\geq y^{-}$.

    * –

If $x_{1}=y^{-}-u^{+}$ we have
$v_{1}^{-}-x_{1}^{-}\geq(2y^{-}-u^{+})-(y^{-}-u^{+})=y^{-}$.

    * –

If $x_{1}=\frac{v^{-}-u^{+}}{2}$ we know that $\frac{v^{-}-u^{+}}{2}\geq
y^{-}-u^{+}$ and thus $\frac{v^{-}+u^{+}}{2}\geq y^{-}$. Using this
inequality, we find $v_{1}^{-}-x_{1}^{-}\geq
v^{-}-\frac{v^{-}-u^{+}}{2}=\frac{v^{-}+u^{+}}{2}\geq y^{-}$.

  * •

We show $v_{1}^{-}-x_{1}^{-}\leq y^{+}$:

    * –

If $v_{1}^{-}=v^{-}$ we have $v_{1}^{-}-x_{1}^{-}\leq v^{-}-(v^{-}-y^{+})\leq
y^{+}$.

    * –

If $v_{1}^{-}=x^{-}+y^{-}$ we have $v_{1}^{-}-x_{1}^{-}\leq
x^{-}+y^{-}-x^{-}=y^{-}\leq y^{+}$

    * –

If $v_{1}^{-}=u^{-}+2x^{-}$ we have $v_{1}^{-}-x_{1}^{-}\leq
u^{-}+2x^{-}-x^{-}\leq u^{-}+x^{-}$, where $u^{-}+x^{-}\leq y^{+}$ follows
from the assumption that $y_{1}-\leq y_{1}^{+}$.

    * –

If $v_{1}^{-}=2y^{-}-u^{+}$ we have $v_{1}^{-}-x_{1}^{-}\leq
2y^{-}-u^{+}-(y^{-}-u^{+})=y^{-}\leq y^{+}$.

  * •

We show $v_{1}^{-}-2x_{1}^{-}\geq u^{-}$:

    * –

If $x_{1}^{-}=x^{-}$ we have
$v_{1}^{-}-2x_{1}^{-}\geq(u^{-}+2x^{-})-2x^{-}=u^{-}$.

    * –

If $x_{1}=v^{-}-y^{+}$ we have $v_{1}^{-}-2x_{1}^{-}\geq
v^{-}-2(v^{-}-y^{+})=2y^{+}-v^{-}\geq u_{1}^{+}\geq u_{1}^{-}\geq u^{-}$.

    * –

If $x_{1}=y^{-}-u^{+}$ we have $v_{1}^{-}-2x_{1}^{-}\geq
2y^{-}-u^{+}-2(y^{-}-u^{+})=u^{+}\geq u^{-}$.

    * –

If $x_{1}=\frac{v^{-}-u^{+}}{2}$ we have $v_{1}^{-}-2x_{1}^{-}\geq
v^{-}-(v^{-}-u^{+})=u^{+}\geq u^{-}$.

  * •

We show $v_{1}^{-}-2x_{1}^{-}\leq u^{+}$:

    * –

If $v_{1}^{-}=v^{-}$ we have $v_{1}^{-}-2x_{1}^{-}\leq
v^{-}2(\frac{v^{-}-u^{+}}{2})=u^{+}$.

    * –

If $v_{1}^{-}=x^{-}+y^{-}$ we know that $x^{-}+y^{-}\geq 2y^{-}-u^{+}$ and
thus $u^{+}\geq y^{-}-x^{-}$. Using this inequality we find
$v_{1}^{-}-2x_{1}^{-}\leq=x^{-}+y^{-}-2x^{-}=y^{-}-x^{-}\leq u^{+}$.

    * –

If $v_{1}^{-}=u^{-}+2x^{-}$ we have $v_{1}^{-}-2x_{1}^{-}\leq
u^{-}+2x^{-}-2x^{-}=u^{-}\leq u^{+}$.

    * –

If $v_{1}^{-}=2y^{-}-u^{+}$ we have $v_{1}^{-}-2x_{1}^{-}\leq
2y^{-}-u^{+}-2(y^{-}-u^{+})=u^{+}$.

  * •

We trivially have $v^{-}\leq v_{1}^{-}$.

  * •

We have $v_{1}^{-}\leq v+$ because of the assumption that $v_{1}^{-}\leq
v_{1}^{+}$.

The result for the other seven points follows by symmetry. ∎

###  A.2 Composing Octagons

######  Lemma 1.

Let $O=\mathsf{Octa}(x^{-},x^{+},y^{-},y^{+},u^{-},u^{+},v^{-},v^{+})$ be an
octagon with normalised parameters. The vertices of this octagon are as
follows:

$\displaystyle(x^{-},v^{-}-x^{-})$ (28) $\displaystyle(x^{-},u^{+}+x^{-})$
(29) $\displaystyle(y^{+}-u^{+},y^{+})$ (30)
$\displaystyle(v^{+}-y^{+},y^{+})$ (31) $\displaystyle(x^{+},v^{+}-x^{+})$
(32) $\displaystyle(x^{+},u^{-}+x^{+})$ (33)
$\displaystyle(y^{-}-u^{-},y^{-})$ (34) $\displaystyle(v^{-}-y^{-},y^{-})$
(35)

###### Proof.

Trivial. ∎

######  Proposition 12.

Let $O_{1}=\mathsf{Octa}(x_{1}^{-},\allowbreak x_{1}^{+},\allowbreak
y_{1}^{-},\allowbreak y_{1}^{+},\allowbreak u_{1}^{-},\allowbreak
u_{1}^{+},\allowbreak v_{1}^{-},\allowbreak v_{1}^{+})$ and
$O_{2}=\mathsf{Octa}(x_{2}^{-},\allowbreak x_{2}^{+},\allowbreak
y_{2}^{-},\allowbreak y_{2}^{+},\allowbreak u_{2}^{-},\allowbreak
u_{2}^{+},\allowbreak v_{2}^{-},\allowbreak v_{2}^{+})$ be non-empty octagons
with normalised parameters. Then $O_{1}\diamond
O_{2}=\mathsf{Octa}(x_{3}^{-},\allowbreak x_{3}^{+},\allowbreak
y_{3}^{-},\allowbreak y_{3}^{+},\allowbreak u_{3}^{-},\allowbreak
u_{3}^{+},\allowbreak v_{3}^{-},\allowbreak v_{3}^{+})$, where:

$\displaystyle x_{3}^{-}$
$\displaystyle=\max(x_{1}^{-},x_{2}^{-}-u_{1}^{+},v_{1}^{-}-x_{2}^{+})$ (36)
$\displaystyle x_{3}^{+}$
$\displaystyle=\min(x_{1}^{+},x_{2}^{+}-u_{1}^{-},v_{1}^{+}-x_{2}^{-})$ (37)
$\displaystyle y_{3}^{-}$
$\displaystyle=\max(y_{2}^{-},u_{2}^{-}+y_{1}^{-},v_{2}^{-}-y_{1}^{+})$ (38)
$\displaystyle y_{3}^{+}$
$\displaystyle=\min(y_{2}^{+},u_{2}^{+}+y_{1}^{+},v_{2}^{+}-y_{1}^{-})$ (39)
$\displaystyle u_{3}^{-}$
$\displaystyle=\max(y_{2}^{-}-x_{1}^{+},u_{2}^{-}+u_{1}^{-},v_{2}^{-}-v_{1}^{+})$
(40) $\displaystyle u_{3}^{+}$
$\displaystyle=\min(y_{2}^{+}-x_{1}^{-},u_{2}^{+}+u_{1}^{+},v_{2}^{+}-v_{1}^{-})$
(41) $\displaystyle v_{3}^{-}$
$\displaystyle=\max(x_{1}^{-}+y_{2}^{-},u_{2}^{-}+v_{1}^{-},v_{2}^{-}-u_{1}^{+})$
(42) $\displaystyle v_{3}^{+}$
$\displaystyle=\min(x_{1}^{+}+y_{2}^{+},u_{2}^{+}+v_{1}^{+},v_{2}^{+}-u_{1}^{-})$
(43)

###### Proof.

It is straightforward to verify that $O_{1}\diamond O_{2}\subseteq O_{3}$
holds. For instance, if $(x,z)\in O_{1}\diamond O_{2}$, by definition there
exists some $y$ such that $(x,y)\in O_{1}$ and $(y,z)\in O_{2}$. We thus have:

  * •

$x\geq x_{1}^{-}$, since $(x,y)\in O_{1}$;

  * •

$y\geq x_{2}^{-}$, since $(y,z)\in O_{2}$, and $y-x\leq u_{1}^{+}$, since
$(x,y)\in O_{1}$, and thus also $x\geq x_{2}^{-}-u_{1}^{+}$;

  * •

$x+y\geq v_{1}^{-}$, since $(x,y)\in O_{1}$, and $y\leq x_{2}^{+}$, since
$(y,z)\in O_{2}$, and thus also $x\geq v_{1}^{-}-x_{2}^{+}$

Together, we have thus found that
$x\geq\max(x_{1}^{-},x_{1}^{-},x_{2}^{-}-u_{1}^{+},v_{1}^{-}-x_{2}^{+})$,
which corresponds to the bound (36). We can similarly show that the bounds
(37)–(43) are satisfied for any $(x,z)\in O_{1}\diamond O_{2}$, from which it
follows that $O_{1}\diamond O_{2}\subseteq O_{3}$.

Now we show that the equality holds. Let
$(x_{4}^{-},x_{4}^{+},y_{4}^{-},y_{4}^{+},u_{4}^{-},u_{4}^{+},v_{4}^{-},v_{4}^{+})$
be the normalisation of the parameters
$(x_{3}^{-},x_{3}^{+},y_{3}^{-},y_{3}^{+},u_{3}^{-},u_{3}^{+},v_{3}^{-},v_{3}^{+})$,
computed as in Proposition 11. If $x_{4}^{-}>x_{4}^{+}$,
$y_{4}^{-}>y_{4}^{+}$, $u_{4}^{-}>u_{4}^{+}$ or $v_{4}^{-}>v_{4}^{+}$ we have
that
$O_{3}=\mathsf{Octa}(x_{4}^{-},x_{4}^{+},y_{4}^{-},y_{4}^{+},u_{4}^{-},u_{4}^{+},v_{4}^{-},v_{4}^{+})=\emptyset$.
Since we have already established that $O_{1}\diamond O_{2}\subseteq O_{3}$,
we then also have $O_{1}\diamond O_{2}=\emptyset$ and thus the stated result
holds. Let us therefore assume throughout the remainder of this proof that
$x_{4}^{-}\leq x_{4}^{+}$, $y_{4}^{-}\leq y_{4}^{+}$, $u_{4}^{-}\leq
u_{4}^{+}$ and $v_{4}^{-}\leq v_{4}^{+}$. Because of Lemma 1, to complete the
proof, it is sufficient to show that the following points belong to
$O_{1}\diamond O_{2}$:

$\displaystyle(x_{4}^{-},v_{4}^{-}-x_{4}^{-})$
$\displaystyle(x_{4}^{-},u_{4}^{+}+x_{4}^{-})$
$\displaystyle(y_{4}^{+}-u_{4}^{+},y_{4}^{+})$
$\displaystyle(v_{4}^{+}-y_{4}^{+},y_{4}^{+})$
$\displaystyle(x_{4}^{+},v_{4}^{+}-x_{4}^{+})$
$\displaystyle(x_{4}^{+},u_{4}^{-}+x_{4}^{+})$
$\displaystyle(y_{4}^{-}-u_{4}^{-},y_{4}^{-})$
$\displaystyle(v_{4}^{-}-y_{4}^{-},y_{4}^{-})$

For each such a point $(x^{*},z^{*})$ we need to show that there exists some
$y^{*}\in\mathbb{R}$ such that $(x^{*},y^{*})\in O_{1}$ and $(y^{*},z^{*})\in
O_{2}$. This is the case iff the following conditions are satisfied:

$\displaystyle x_{1}^{-}$ $\displaystyle\leq x^{*}\leq x_{1}^{+}$ (44)
$\displaystyle y_{2}^{-}$ $\displaystyle\leq z^{*}\leq y_{2}^{+}$ (45)

and

$\displaystyle\max(y_{1}^{-},u_{1}^{-}+x^{*},v_{1}^{-}-x^{*},x_{2}^{-},z^{*}-u_{2}^{+},v_{2}^{-}-z^{*})$
$\displaystyle\leq\min(y_{1}^{+},u_{1}^{+}+x^{*},v_{1}^{+}-x^{*},x_{2}^{+},z^{*}-u_{2}^{-},v_{2}^{+}-z^{*})$
(46)

We used Gurobi444https://www.gurobi.com to verify that the conditions
(44)–(46) are indeed necessarily satisfied for each of the vertices
$(x^{*},z^{*})$. ∎

###  A.3 Characterising Self-Compositions

Rather than characterising transitivity directly, we first study a more
general problem. For an octagon $O$, we define $O^{(k)}=O^{k-1}\diamond O$,
for $k\geq 2$, and $O^{(1)}=O=\mathsf{Octa}(x^{-},\allowbreak
x^{+},\allowbreak y^{-},\allowbreak y^{+},\allowbreak u^{-},\allowbreak
u^{+},\allowbreak v^{-},\allowbreak v^{+})$. Assume that the parameters of $O$
are normalised. In other words, $O^{(k)}$ is the octagon we obtain if compose
$O$ with itself $k-1$ times. We now analyse the nature of the resulting
octagons. Among others, this will allow us to characterise under which
conditions the relation captured by $O$ is _transitive_. Let us use subscripts
to denote the parameters of $O^{(l)}$, i.e. we write
$O^{(l)}=\mathsf{Octa}(x_{l}^{-},\allowbreak x_{l}^{+},\allowbreak
y_{l}^{-},\allowbreak y_{l}^{+},\allowbreak u_{l}^{-},\allowbreak
u_{l}^{+},\allowbreak v_{l}^{-},\allowbreak v_{l}^{+})$. Note that:

$\displaystyle x^{-}_{l+1}$
$\displaystyle=\max(x_{l}^{-},x^{-}-u_{l}^{+},v_{l}^{-}-x^{+})$ (47)
$\displaystyle x^{+}_{l+1}$
$\displaystyle=\min(x_{l}^{+},x^{+}-u_{l}^{-},v_{l}^{+}-x^{-})$ (48)
$\displaystyle y^{-}_{l+1}$
$\displaystyle=\max(y^{-},u^{-}+y_{l}^{-},v^{-}-y_{l}^{+})$ (49)
$\displaystyle y^{+}_{l+1}$
$\displaystyle=\min(y^{+},u^{+}+y_{l}^{+},v^{+}-y_{l}^{-})$ (50)
$\displaystyle u^{-}_{l+1}$
$\displaystyle=\max(y^{-}-x_{l}^{+},u^{-}+u_{l}^{-},v^{-}-v_{l}^{+})$ (51)
$\displaystyle u^{+}_{l+1}$
$\displaystyle=\min(y^{+}-x_{l}^{-},u^{+}+u_{l}^{+},v^{+}-v_{l}^{-})$ (52)
$\displaystyle v^{-}_{l+1}$
$\displaystyle=\max(x_{l}^{-}+y^{-},u^{-}+v_{l}^{-},v^{-}-u_{l}^{+})$ (53)
$\displaystyle v^{+}_{l+1}$
$\displaystyle=\min(x_{l}^{+}+y^{+},u^{+}+v_{l}^{+},v^{+}-u_{l}^{-})$ (54)

We now have the following results.

######  Lemma 2.

If $u^{+}<0$ or $u^{-}>0$ then there exists some $k\in\mathbb{N}$ such that
$O^{(k)}=\emptyset$.

###### Proof.

Assume that $u^{+}<0$; the case for $u^{-}>0$ is entirely analogous. From the
characterisation of composition (47)–(54), we know that for each $l\geq 1$ we
have:

$\displaystyle x^{-}_{l+1}$ $\displaystyle\geq x^{-}-u_{l}^{+}$ $\displaystyle
x^{+}_{l+1}$ $\displaystyle\leq x^{+}_{l}$ $\displaystyle u_{l+1}^{+}$
$\displaystyle\leq u^{+}+u_{l}^{+}$

If $u^{+}<0$, it follows that $x^{-}_{l+1}\geq x^{-}+(l-1)|u^{+}|$. For
sufficiently large $l$ we thus have $x^{-}_{l}>x^{+}$ meaning that
$O^{(l)}=\emptyset$. ∎

######  Lemma 3.

Suppose that the parameters of the octagon are normalised. If $u^{-}\leq 0$
and $u^{+}\geq 0$ then $x_{l}^{+}=x_{2}^{+}$, $x_{l}^{-}=x_{2}^{-}$,
$y_{l}^{+}=y_{2}^{+}$ and $y_{l}^{-}=y_{2}^{-}$ for all $l\geq 2$.
Furthermore, for all $l\geq 1$ we have $u_{l}^{-}\leq 0$, $u_{l}^{+}\geq 0$,
$v_{l}^{-}\leq v^{-}$ and $v_{l}^{+}\geq v^{+}$.

###### Proof.

Suppose $u^{-}\leq 0$, $u^{+}\geq 0$ and $v^{-}<v^{+}$. We first show by
induction that the following are true for $l\geq 1$:

$\displaystyle x_{l}^{-}$ $\displaystyle\leq\max(x^{-},v^{-}-x^{+})$ (55)
$\displaystyle x_{l}^{+}$ $\displaystyle\geq\min(x^{+},v^{+}-x^{-})$ (56)
$\displaystyle y_{l}^{-}$ $\displaystyle\leq\max(y^{-},v^{-}-y^{+})$ (57)
$\displaystyle y_{l}^{+}$ $\displaystyle\geq\min(y^{+},v^{+}-y^{-})$ (58)
$\displaystyle u_{l}^{-}$ $\displaystyle\leq 0$ (59) $\displaystyle u_{l}^{+}$
$\displaystyle\geq 0$ (60) $\displaystyle v_{l}^{-}$ $\displaystyle\leq v^{-}$
(61) $\displaystyle v_{l}^{+}$ $\displaystyle\geq v^{+}$ (62)

Note that these inequalities are trivially satisfied for $l=1$. Now suppose
the induction hypothesis is satisfied for $l=k$; we show that the hypothesis
is also satisfied for $l=k+1$.

  * •

We have $x_{k+1}^{-}\leq\max(x_{k}^{-},v_{k}^{-}-x^{+})$ since $u_{k}^{+}\geq
0$ by the induction hypothesis. From the induction hypothesis we furthermore
have $x_{k}^{-}\leq\max(x^{-},v^{-}-x^{+})$ and $v_{k}^{-}\leq v^{-}$. We thus
find $x_{k+1}^{-}\leq\max(x^{-},v^{-}-x^{+})$.

  * •

Entirely analogously, we find $x_{k+1}^{+}\geq\min(x^{+},v^{+}-x^{-})$

  * •

We now show that $u_{k+1}^{-}\leq 0$. First, we have $y^{-}-x_{k}^{+}\leq
y^{-}-\min(x^{+},v^{+}-x^{-})$. Since the parameters are normalised, we have
$y^{-}-x^{+}\leq u^{-}\leq 0$ and $y^{-}-v^{+}+x^{-}\leq v^{-}-v^{+}$ and by
assumption we have $v^{-}-v^{+}<0$. We thus have $y^{-}-x_{k}^{+}\leq 0$. By
the induction hypothesis we also immediately find $u^{-}+u_{k}^{-}\leq 0$.
Finally, we also find $v^{-}-v_{k}^{+}\leq v^{-}-v^{+}\leq 0$. We thus have
found $u_{k+1}^{-}\leq 0$.

  * •

In the same way we show $u_{k+1}^{+}\geq 0$.

  * •

We now show $v_{k+1}^{-}\leq v^{-}$. First, we have
$x_{k}^{-}+y^{-}\leq\max(x^{-},v^{-}-x^{+})+y^{-}$. Since the parameters are
normalised, we have $x^{-}+y^{-}\leq v^{-}$ and $v^{-}-x^{+}+y^{-}\leq
v^{-}+u^{-}\leq v^{-}$. From the induction hypothesis we also trivially find
$u^{-}+v_{k}^{-}\leq u^{-}+v^{-}\leq v^{-}$ and $v^{-}-u_{k}^{+}\leq v^{-}$.
We have thus found $v_{k+1}^{-}\leq v^{-}$.

  * •

In the same way, we find $v_{k+1}^{+}\geq v^{+}$.

As a consequence of (55)–(62), we now immediately find that for all $l\geq 2$
we have

$\displaystyle x_{l}^{-}$ $\displaystyle=\max(x^{-},v^{-}-x^{+})$
$\displaystyle x_{l}^{+}$ $\displaystyle=\min(x^{+},v^{+}-x^{-})$

∎

######  Lemma 4.

Suppose $u^{-}<0$, $u^{+}>0$ and $v^{-}<v^{+}$. Then there exists some
$m\in\mathbb{N}$ such that
$O^{(l)}=[x_{2}^{-},x_{2}^{+}]\times[y_{2}^{-},y_{2}^{+}]$ for all $l\geq m$.

###### Proof.

Since $u^{+}>0$ and $u^{-}=u_{1}^{-}<0$, we have:

$\displaystyle(v_{2}^{+}=x_{1}^{+}+y^{+})\vee(v_{2}^{+}>v_{1}^{+})$ (63)

and in the same way, we also find

$\displaystyle(v_{2}^{-}=x_{1}^{-}+y^{-})\vee(v_{2}^{-}<v_{1}^{-})$ (64)

Since $u^{-}<0$ we have $u^{-}+u_{2}^{-}<u_{2}^{-}$. Furthermore, from
$v_{2}^{+}>v_{1}^{+}$ it follows that $v^{-}-v_{2}^{+}<v^{-}-v_{1}^{+}\leq
u_{2}^{-}$. Together, this implies:

$\displaystyle(v_{2}^{+}>v_{1}^{+})\Rightarrow(u_{3}^{-}=y^{-}-x_{2}^{+})\vee(u_{3}^{-}<u_{2}^{-})$

More generally, in the same way we can show:

$\displaystyle(v_{l+1}^{+}>v_{l}^{+})\Rightarrow(u_{l+2}^{-}=y^{-}-x_{2}^{+})\vee(u_{l+2}^{-}<u_{l+1}^{-})$
$\displaystyle(v_{l+1}^{-}<v_{l}^{-})\Rightarrow(u_{l+2}^{+}=y^{+}-x_{2}^{-})\vee(u_{l+2}^{+}>u_{l+1}^{+})$
$\displaystyle(u_{l+1}^{+}>u_{l}^{+})\Rightarrow(v_{l+2}^{-}=x_{2}^{-}+y^{-})\vee(v_{l+2}^{-}<v_{l+1}^{-})$
$\displaystyle(u_{l+1}^{-}<u_{l}^{-})\Rightarrow(v_{l+2}^{+}=x_{2}^{+}+y^{+})\vee(v_{l+2}^{+}>v_{l+1}^{+})$

Next, we show:

$\displaystyle(v_{l+1}^{+}\geq x_{2}^{+}+y_{2}^{+})$
$\displaystyle\Rightarrow(u_{l+2}^{-}\leq
y_{2}^{-}-x_{2}^{+})\vee(u_{l+2}^{-}<u_{l+1}^{-})$
$\displaystyle(v_{l+1}^{-}\leq x_{2}^{-}+y_{2}^{-})$
$\displaystyle\Rightarrow(u_{l+2}^{+}\geq
y_{2}^{+}-x_{2}^{-})\vee(u_{l+2}^{+}>u_{l+1}^{+})$
$\displaystyle(u_{l+1}^{+}\geq y_{2}^{+}-x_{2}^{-})$
$\displaystyle\Rightarrow(v_{l+2}^{-}\leq
x_{2}^{-}+y_{2}^{-})\vee(v_{l+2}^{-}<v_{l+1}^{-})$
$\displaystyle(u_{l+1}^{-}\leq y_{2}^{-}-x_{2}^{+})$
$\displaystyle\Rightarrow(v_{l+2}^{+}\geq
x_{2}^{+}+y_{2}^{+})\vee(v_{l+2}^{+}>v_{l+1}^{+})$

Assume $v_{l+1}^{+}\geq x_{2}^{+}+y_{2}^{+}$. First suppose
$u_{l+2}^{-}=y^{+}-x_{l+1}^{-}=y^{+}-x_{2}^{-}$. Noting that $y^{+}\geq
y_{2}^{+}$ we clearly have $u_{l+2}^{-}\leq y_{2}^{-}-x_{2}^{+}$. Now suppose
$u_{l+2}^{-}=u^{-}+u_{l+1}^{-}$. Since $u^{-}<0$ we clearly have
$u_{l+2}^{-}<u_{l+1}^{-}$. Finally, suppose $u_{l+2}^{-}=v^{-}-v_{l+1}^{+}$.
Then we find:

$\displaystyle u_{l+2}^{-}$ $\displaystyle=v^{-}-v_{l+1}^{+}\leq
v^{-}-x_{2}^{+}-y_{2}^{+}\leq y_{3}^{-}-x_{2}^{+}=y_{2}^{-}-x_{2}^{+}$

We thus have that in any case, either $(u_{l+2}^{-}\leq y_{2}^{-}-x_{2}^{+})$
or $(u_{l+2}^{-}<u_{l+1}^{-})$ holds. The other three assertions are shown in
entirely the same way. Together with (63)–(64), this means that for even
values of $l$, we have

$\displaystyle(u_{l+1}^{-}\leq
y_{2}^{-}-x_{2}^{+})\vee(u_{l+1}^{-}<u_{l}^{-})$ (65)
$\displaystyle(u_{l+1}^{+}\geq
y_{2}^{+}-x_{2}^{-})\vee(u_{l+1}^{+}>u_{l}^{+})$ (66)
$\displaystyle(v_{l}^{-}\leq x_{2}^{-}+y_{2}^{-})\vee(v_{l}^{-}<v_{l-1}^{-})$
(67) $\displaystyle(v_{l}^{+}\geq
x_{2}^{+}+y_{2}^{+})\vee(v_{l}^{+}>v_{l-1}^{+})$ (68)

Now we consider odd values of $l$. If $u_{2}^{+}=y^{+}-x_{1}^{-}$ or
$u_{2}^{+}>u_{1}^{+}$ holds, then we find that (66) holds, as well as (67) for
$l\geq 3$. Now suppose $u_{2}^{+}<y^{+}-x_{1}^{-}$ and $u_{2}^{+}\leq
u_{1}^{+}$. This is only possible if $u_{2}^{+}=v^{+}-v_{1}^{-}$. If
$v_{3}^{-}=x_{2}^{-}+y^{-}$ or $v_{3}^{-}<v_{2}^{-}$ holds, then we find that
(67) (66) hold for odd $l$ with $l\geq 3$. Now suppose we have
$v_{3}^{-}>x_{2}^{-}+y^{-}$ and $v_{3}^{-}\geq v_{2}^{-}$. This is only
possible if $v_{3}^{-}=v^{-}-u_{2}^{+}=v^{-}-v^{+}+v_{1}^{-}$. Continuing in
this way, we find that there must be an odd $l$ for which (66) and (67) are
satisfied. Indeed, suppose this were not the case. We then find:

$\displaystyle u_{4}^{+}$
$\displaystyle=v^{+}-(v^{-}-v^{+}+v_{1}^{-})=2(v^{+}-v^{-})$ $\displaystyle
v_{5}^{-}$ $\displaystyle=v^{-}-2(v^{+}-v^{-})=3v^{-}-2v^{+}$ $\displaystyle
u_{6}^{+}$ $\displaystyle=v^{+}-(3v^{-}-2v^{+})=3(v^{+}-v^{-})$ $\displaystyle
v_{7}^{-}$ $\displaystyle=v^{-}-3(v^{+}-v^{-})=4v^{-}-3v^{+}$
$\displaystyle\ldots$

In particular, since $v^{-}<v^{+}$, we find for odd $l$ that
$v_{l+2}^{-}<v_{l}^{-}$ and $u_{l+3}^{+}>u_{l+1}^{+}$. This means that there
must be some odd $l$ for which $v_{l}^{-}=x_{2}^{-}+y^{-}$. This implies that
(66) and (67) are satisfied for sufficiently large odd $l$. In the same way,
we find that this is the case for (65) and (68). Putting everything together,
we have that (65)–(68) are satisfied for all sufficiently large $l$. This, in
turn, implies that for sufficiently large $l$, all of the bounds
$u_{l}^{-},u_{l}^{+},v_{l}^{-},v_{l}^{+}$ become trivial. This shows that for
sufficiently large $l$, we have
$O^{(l)}=[x_{l}^{-},x_{l}^{+}]\times[y_{l}^{-},y_{l}^{+}]$, and thus by Lemma
3, we also find $O^{(l)}=[x_{2}^{-},x_{2}^{+}]\times[y_{2}^{-},y_{2}^{+}]$. ∎

######  Lemma 5.

Suppose $u^{-}=0$, $u^{+}>0$ and $v^{-}<v^{+}$. For each $l\geq 1$ we have
$u_{l}^{-}=0$, $v_{l}^{-}=v^{-}$ and $v_{l}^{+}=v^{+}$. Moreover, there exists
some $m$ such that either $u_{l}^{+}=y^{+}-x_{2}^{-}$ for every $l\geq m$ or
$u_{l}^{+}=v^{+}-v^{-}$ for every $l\geq m$. In particular this also means
that $O^{(m)}=O^{(l)}$ for all $l\geq m$.

###### Proof.

We first show that $u_{l}^{-}=0$ for all $l$. Recall that:

$u_{l+1}^{-}=\max(y^{-}-x_{l}^{+},u^{-}+u_{l}^{-},v^{-}-v_{l}^{+})$

From Lemma 3 we know that $v_{l}^{+}\geq v^{+}$, and since we assumed
$v^{-}<v^{+}$ we thus have $v^{-}-v_{l}^{+}\leq 0$. We thus straightforwardly
find by induction that:

$u_{l+1}^{-}=\max(y^{-}-x_{l}^{+},0)$

Moreover, from Lemma 3 we know that $u_{l+1}^{-}\leq 0$. Together, we can thus
conclude $u_{l}^{-}=0$ for all $l\geq 1$.

Next we show that $v_{l}^{+}=v^{+}$ for all $l$. First recall that:

$v_{l+1}^{+}=\min(x_{l}^{+}+y^{+},u^{+}+v_{l}^{+},v^{+}-u_{l}^{-})$

Since we already established that $u_{l}^{-}=0$, this simplifies to

$v_{l+1}^{+}=\min(x_{l}^{+}+y^{+},u^{+}+v_{l}^{+},v^{+})$

Moreover, from Lemma 3 we know that $v_{l}^{+}\geq v^{+}$ and by assumption we
have $u^{+}>0$. Thus we obtain:

$v_{l+1}^{+}=\min(x_{l}^{+}+y^{+},v^{+})$

Finally, since we know from 3 that $v_{l+1}^{+}\geq v^{+}$ we find
$v_{l+1}=v^{+}$.

Now we show $v_{l}^{-}=v^{-}$ for all $l$. First recall that

$v_{l+1}^{-}=\max(x_{l}^{-}+y^{-},u^{-}+v_{l}^{-},v^{-}-u_{l}^{+})$

which simplifies to

$v_{l+1}^{-}=\max(x_{l}^{-}+y^{-},v_{l}^{-},v^{-}-u_{l}^{+})$

Since $u_{l}^{+}\geq 0$ by Lemma 3, by induction we find

$v_{l+1}^{-}=\max(x_{l}^{-}+y^{-},v^{-})$

Finally, since $v_{l+1}^{-}\leq v^{-}$ by Lemma 3, we obtain
$v_{l+1}^{-}=v^{-}$.

Finally, we consider $u_{l}^{+}$. Recall that:

$u_{l+1}^{+}=\min(y^{+}-x_{l}^{-},u^{+}+u_{l}^{+},v^{+}-v_{l}^{-})$

which simplifies to

$u_{l+1}^{+}=\min(y^{+}-x_{l}^{-},u^{+}+u_{l}^{+},v^{+}-v^{-})$

If $u_{l+1}^{+}=u^{+}+u_{l}^{+}$ then clearly we have $u_{l+1}^{+}>u_{l}^{+}$.
For sufficiently large $l$, we must thus have:

$u_{l}^{+}=\min(y^{+}-x_{2}^{-},v^{+}-v^{-})$

In other words, either $u_{l}^{+}$ is trivial or $u_{l}^{+}=v^{+}-v^{-}$. ∎

In entirely the same way, we find:

######  Lemma 6.

Suppose $u^{-}<0$, $u^{+}=0$ and $v^{-}<v^{+}$. Then for each $l\geq 1$ we
have $u_{l}^{+}=0$, $v_{l}^{-}=v^{-}$ and $v_{l}^{+}=v^{+}$. Moreover, there
exists some $m$ such that either $u_{l}^{-}=y^{-}-x_{2}^{+}$ for every $l\geq
m$ or $u_{l}^{-}=v^{-}-v^{+}$ for every $l\geq m$. In particular this also
means that $O^{(m)}=O^{(l)}$ for all $l\geq m$.

######  Lemma 7.

Suppose $u^{-}=u^{+}=0$. Then for each $l\geq 1$ we have $O^{(l)}=O^{(1)}$.

###### Proof.

If $u^{-}=u^{+}-0$, and assuming the initial parameters are normalised, we
have $O^{(1)}=\\{(x,x)\,|\,x\in[x^{-},x^{+}]\\}$. From this characterisation,
it immediately follows that $O^{(1)}\circ O^{(1)}=O^{(1)}$. ∎

######  Lemma 8.

Suppose $u^{-}\leq 0$, $u^{+}\geq 0$ and $v^{-}=v^{+}$. For even $l$ we have:

$O^{(l)}=\\{(x,x)\,|\,x\in[\max(x^{-},v-x^{+}),\min(x^{+},v-x^{-})]\\}$

while for odd $l\geq 3$ we have:

$O^{(l)}=\\{(x,v-x)\,|\,x\in[\max(x^{-},v-x^{+}),\min(x^{+},v-x^{-})]\\}$

###### Proof.

Let us write $v$ for $v^{-}=v^{+}$. Assuming the initial parameters are
normalised, we have:

$O^{(1)}=\\{(x,v-x)\,|\,x\in[x^{-},x^{+}]\\}$

and thus

$O^{(1)}\diamond O^{(1)}=\\{(x,x)\,|\,x\in[x^{-},x^{+}]\text{ and
}v-x\in[x^{-},x^{+}]\\}$

In other words:

$O^{(2)}=\\{(x,x)\,|\,x\in[\max(x^{-},v-x^{+}),\min(x^{+},v-x^{-})]\\}$

Continuing in this way, we find

$O^{(l)}=\\{(x,v-x)\,|\,x\in[\max(x^{-},v-x^{+}),\min(x^{+},v-x^{-})]\\}$

for odd $l\geq 3$ and

$O^{(l)}=\\{(x,x)\,|\,x\in[\max(x^{-},v-x^{+}),\min(x^{+},v-x^{-})]\\}$

for even $l\geq 2$. ∎

Let us now show the main result about octagons capturing transitive relations.

######  Proposition 13.

Let $O=\mathsf{Octa}(x^{-},\allowbreak x^{+},\allowbreak y^{-},\allowbreak
y^{+},\allowbreak u^{-},\allowbreak u^{+},\allowbreak v^{-},\allowbreak
v^{+})$ and assume that these parameters are normalised. It holds that
$O\diamond O=O$ iff one of the following conditions is satisfied:

  * •

$O=\emptyset$;

  * •

$O=[x^{-},x^{+}]\times[y^{-},y^{+}]$, $x^{+}\geq y^{-}$ and $x^{-}\leq y^{+}$;

  * •

$O=\\{(x,x)\,|\,x\in[x^{-},x^{+}]\\}$;

  * •

$u^{-}=0$, $u^{+}>0$, $v^{-}<v^{+}$, $v^{-}-x^{+}\leq x^{-}$, $x^{+}\leq
v^{+}-x^{-}$, $v^{-}-y^{+}\leq y^{-}$, $y^{+}\leq v^{+}-y^{-}$ and
$u^{+}=\min(y^{+}-x^{-},v^{+}-v^{-})$;

  * •

$u^{-}<0$, $u^{+}=0$, $v^{-}<v^{+}$, $v^{-}-x^{+}\leq x^{-}$, $x^{+}\leq
v^{+}-x^{-}$, $v^{-}-y^{+}\leq y^{-}$, $y^{+}\leq v^{+}-y^{-}$ and
$u^{-}=\max(y^{-}-x^{+},v^{-}-v^{+})$.

###### Proof.

If $u^{+}<0$ or $u^{-}>0$, we know from Lemma 2 that $O\diamond O=O$ can only
hold if $O=\emptyset$. Furthermore, $O=\emptyset$ is clearly sufficient for
$O\diamond O=O$ to hold.

If $u^{-}<0$, $u^{+}>0$ and $v^{-}<v^{+}$, we know from Lemma 4 that
$O\diamond O=O$ can only hold if $O=[x^{-},x^{+}]\times[y^{-},y^{+}]$ and
moreover $x^{-}=x^{-}_{2}$, $x^{+}=x^{+}_{2}$, $y^{-}=y^{-}_{2}$,
$y^{+}=y^{+}_{2}$. These latter conditions are satisfied if $x^{-}\geq
v^{-}-x^{+}$, $x^{+}\leq v^{+}-x^{-}$, $y^{-}\geq v^{-}-y^{+}$ and $y^{+}\leq
v^{+}-y^{-}$. From $O=[x^{-},x^{+}]\times[y^{-},y^{+}]$, together with the
assumptions that the parameters are normalised, we furthermore know that
$v^{-}=x^{-}+y^{-}$ and $v^{+}=x^{+}+y^{+}$. We thus arrive at the conditions
$x^{-}\geq x^{-}+y^{-}-x^{+}$, $x^{+}\leq x^{+}+y^{+}-x^{-}$, $y^{-}\geq
x^{-}+y^{-}-y^{+}$ and $y^{+}\leq x^{+}+y^{+}-y^{-}$. These conditions are
equivalent with $x^{+}\geq y^{-}$ and $x^{-}\leq y^{+}$. Finally, note that we
can also trivially verify that the conditions stated in the second bullet
point are sufficient for $O\diamond O=O$ to hold.

If $u^{-}=u^{+}=0$ we have $O=\\{(x,x)\,|\,x\in[x^{-},x^{+}]\\}$ and we
clearly have $O\diamond O=O$.

If $u^{-}=0$, $u^{+}>0$ and $v^{-}<v^{+}$, then we know from Lemma 5 that
$O\diamond O=O$ can only hold if either $u^{+}=y^{+}-x^{-}$ or
$u^{+}=v^{+}-v^{-}$. Furthermore, we also need to ensure that
$x^{-}=x_{2}^{-}$, $x^{+}=x_{2}^{+}$, $y^{-}=y_{2}^{-}$ and $y^{+}=y_{2}^{+}$,
which is the case iff $v^{-}-x^{+}\leq x^{-}$, $x^{+}\leq v^{+}-x^{-}$,
$v^{-}-y^{+}\leq y^{-}$ and $y^{+}\leq v^{+}-y^{-}$. We thus clearly have that
the conditions stated in the fourth bullet point are necessary. To see why
they are also sufficient, we can use (47)–(54) to verify that $O^{(2)}=O$. We
trivially find $x_{2}^{-}=x^{-}$, $x_{2}^{+}=x^{+}$, $y_{2}^{-}=y^{-}$ and
$y_{2}^{+}=y^{+}$. To see why $u_{2}^{-}=u^{-}=0$, note that
$u^{-}+u_{1}^{-}=0$ and $v^{-}-v^{+}<0$. Furthermore, $y^{-}-x_{1}^{+}\leq 0$
follows from the assumption that $x^{-}\geq v^{-}-x^{+}$. Indeed, together
with the observation that $v^{-}\geq x^{-}+y^{-}$ we find $x^{-}\geq
x^{-}+y^{-}-x^{+}$ which is equivalent with $x^{+}\geq y^{-}$. We trivially
have $u_{2}^{+}=u^{+}$, since we assumed $u^{+}=\min(y^{+}-x^{-},v^{+}-v^{-})$
and $u^{+}+u^{+}>u^{+}$ since $u^{+}>0$. Next, we also have $v^{-}_{2}=v^{-}$
because $u^{-}+v_{1}^{-}=v^{-}$, $v^{-}-u^{+}<v^{-}$, and we furthermore have
$v^{-}\leq x^{-}+y^{-}$ since the parameters are normalised. In the same way
we also find $v_{2}^{+}=v^{+}$.

The case where $u^{-}<0$, $u^{+}-0$ and $v^{-}<v^{+}$ is entirely analogous.

If $v^{-}=v^{+}$, it follows from Lemma 8 that $O$ can $O\diamond O=0$ can
only hold in the trivial case where $O=\\{(x,x)\\}$ for some $x\in\mathbb{R}$,
which was already covered since we then have $u^{-}=u^{+}=0$. ∎

######  Proposition 14.

If $v^{-}<v^{+}$ then there exists some $m\geq 1$ such that $O^{(m)}\diamond
O=O^{(m)}$.

###### Proof.

This immediately follows from Lemmas 2, 4, 5, 6 and 7. ∎

##  Appendix B Expressivity of Octagon Embeddings

###  B.1 Capturing Knowledge Graphs

The following result concerns hexagon of the following form:

$\displaystyle X^{i}_{r}=\\{(x,y)\,|\,$ $\displaystyle u_{i}^{-}\leq y-x\leq
u_{i}^{+},$ (69) $\displaystyle x_{i}^{-}\leq x\leq x_{i}^{+},y_{i}^{-}\leq
y\leq y_{i}^{+}\\}$

######  Proposition 15.

Let $X_{r}$ be a hexagon region of the form (69) and let
$\mathbf{e},\mathbf{f}\in\mathbb{R}^{n}$. If $\mathbf{e}\oplus\mathbf{f}\in
X_{r}$ and $\mathbf{f}\oplus\mathbf{e}\in X_{r}$ then we also have
$\mathbf{e}\oplus\mathbf{e}\in X_{r}$.

###### Proof.

Let $\mathbf{e}=(e_{1},\ldots,e_{n})$ and $\mathbf{f}=(f_{1},\ldots,f_{n})$ be
the embeddings of entities $e$ and $f$. Since $(e,r,e)\notin\mathcal{G}$ there
must exist some coordinate $i$ such that one of the following holds:

$\displaystyle e_{i}$ $\displaystyle<x_{i}^{-}$ $\displaystyle e_{i}$
$\displaystyle>x_{i}^{+}$ $\displaystyle e_{i}$ $\displaystyle<y_{i}^{-}$
$\displaystyle e_{i}$ $\displaystyle>y_{i}^{+}$ $\displaystyle 0$
$\displaystyle<u_{i}^{-}$ $\displaystyle 0$ $\displaystyle>u_{i}^{+}$

where $(x_{i}^{-},x_{i}^{+},y_{i}^{-},y_{i}^{+},u_{i}^{-},u_{i}^{+})$ are the
parameters of the hexagon representing relation $r$ in coordinate $i$. If
$e_{i}<x_{i}^{-}$ or $e_{i}>x_{i}^{+}$ were to hold, then the triple $(e,r,f)$
would not be satisfied in coordinate $i$ either. Similarly, if
$e_{i}<y_{i}^{-}$ or $e_{i}>y_{i}^{+}$ were the case, then $(f,r,e)$ would not
be satisfied in coordinate $i$. Suppose that $0<u_{i}^{-}$. Since $(e,r,f)$
holds, we know that $f_{i}-e_{i}\geq u_{i}^{-}>0$, or in other words
$f_{i}>e_{i}$. But because $(f,r,e)$ holds, we also know that $e_{i}-f_{i}\geq
u_{i}^{-}>0$, or in other words $e_{i}>f_{i}$, a contradiction. We similarly
arrive at a contradiction if $0>u_{i}^{+}$ were to hold. ∎

######  Proposition 16.

Let $\mathcal{G}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ be a
knowledge graph. There exists an octagon embedding $\gamma$ such that
$\mathcal{G}=\mathcal{G}_{\gamma}$.

###### Proof.

We represent each entity $e$ as a vector $\gamma(e)=\mathbf{e}$ of dimension
$n=|\mathcal{R}|\cdot|\mathcal{E}|$. In particular, each coordinate in
$\mathbf{e}$ is associated with an entity $f\in\mathcal{E}$ and relation
$r\in\mathcal{R}$; let us write $e_{r,f}$ for that coordinate. We show that
there exists an octagon based embedding, which satisfies a triple $(e,r,f)$
iff it belongs to $\mathcal{G}$. In particular, we choose the coordinates of
$\mathbf{e}$ as follows:

$\displaystyle e_{r,f}=\begin{cases}0&\text{if $e=f$}\\\ 1&\text{if $e\neq f$
and $(f,r,e)\in\mathcal{G}$}\\\ 2&\text{otherwise}\end{cases}$

Let us write $O^{s}_{r,e}$ for the octagon representing relation $r$ in
coordinate associated with entity $e$ and relation $s$. For all coordinates
where $s=r$, we choose $O^{s}_{r,e}=[0,2]\times[0,2]$. The octagons
$O^{r}_{r,e}$ are chosen as follows:

  * •

If $(e,r,e)\in\mathcal{G}$ we choose $O^{r}_{r,e}$ as the pentagon with
vertices $(0,0),(0,1),(1,2),(2,2),(2,0)$. We will refer to this degenerate
octagon as $O^{+}$.

  * •

Otherwise, we choose $O^{r}_{r,e}$ as the pentagon with vertices
$(0,1),(1,2),(2,2),(2,0),(1,0)$. We will refer to this degenerate octagon as
$O^{-}$.

These two octagons are depicted in Figure 5.

Suppose $(e,r,f)\in\mathcal{G}$. We need to show that $(e_{s,g},f_{s,g})\in
O^{r}_{s,g}$ for every $s\in\mathcal{R}$ and $g\in\mathcal{E}$. If $s\neq r$
then this is trivially satisfied. Let us now consider the cases where $s=r$.

  * •

If $g\neq e$, we have $e_{r,g}\in\\{1,2\\}$ and thus $(e_{r,g},f_{r,g})\in
O^{r}_{r,g}$, regardless of the value of $f_{r,g}\in\\{0,1,2\\}$ and whether
$O^{r}_{r,g}=O^{+}$ or $O^{r}_{r,g}=O^{-}$.

  * •

Now suppose $g=e$ with $e\neq f$. Then $e_{r,g}=e_{r,e}=0$. Since
$(e,r,f)\in\mathcal{G}$, we have $f_{r,g}=1$. We thus have
$(e_{r,g},f_{r,g})\in O^{r}_{r,g}$, regardless of whether $O^{r}_{r,g}=O^{+}$
or $O_{r,g}=O^{-}$.

  * •

Finally, suppose $g=e=f$. Since we assumed that
$(e,r,f)=(e,r,e)\in\mathcal{G}$ we have that $O^{r}_{r,g}=O^{+}$. We also have
$e_{r,g}=f_{r,g}=e_{r,e}=0$ and thus $(e_{r,g},f_{r,g})\in O^{+}$.

Now suppose $(e,r,f)\notin\mathcal{G}$. We need to show that there exists some
$g\in\mathcal{E}$ such that $(e_{r,g},f_{r,g})\notin O^{r}_{r,g}$. If $e=f$ we
know that $O^{r}_{r,e}=O^{-}$ since we assumed $(e,r,e)\notin\mathcal{G}$ .
Moreover, have $e_{r,e}=0$ and thus $(e_{r,e},e_{r,e})\notin O^{-}$. Now
assume $e\neq f$. We show that $(e_{r,g},f_{r,g})\notin O^{r}_{r,g}$ for
$g=e$. In other words, we show that $(e_{r,e},f_{r,e})\notin O^{r}_{r,e}$. We
have $e_{r,e}=0$ and $f_{r,e}=2$. Regardless of whether $O^{r}_{r,g}=O^{+}$ or
$O^{r}_{r,g}=O^{-}$ we thus find $(e_{r,g},f_{r,g})\notin O^{r}_{r,g}$. ∎

(a) $O^{-}$

(b) $O^{+}$

Figure 5: Illustration of the octagons constructed in the proof of Proposition
16.

###  B.2 Capturing Rules: Negative Results

The following result concerns region based embeddings of the form

$\displaystyle X_{r}=\\{(x_{1}{,}...,x_{n},y_{1}{,}...,y_{n})\,|\,\forall
i\,{\in}\,\\{1{,}...,n\\}.(x_{i},y_{i})\in X^{i}_{r}\\}$ (70)

and

$\displaystyle X_{r}=\\{$
$\displaystyle(x_{1}{,}...,x_{2n},y_{1}{,}...,y_{2n})\,|\,$ (71)
$\displaystyle\forall
i\in\\{1{,}...,n\\}\,.\,(x_{i},y_{n+i})\,{\in}\,A^{i}_{r}\wedge(y_{i},x_{n+i})\,{\in}\,B^{i}_{r}\\}$

######  Proposition 17.

There exists a consistent set of hierarchy, intersection and mutual exclusion
rules $\mathcal{K}$ such that every convex embedding of the form (70) or (71)
which satisfies $\mathcal{K}$ also satisfies some hierarchy rule which is not
entailed by $\mathcal{K}$.

###### Proof.

Let $\mathcal{K}$ contain the following rules:

$\displaystyle\\{s_{i}(X,Y)\rightarrow
r_{j}(X,Y)\,|\,i\,{\in}\,\\{1,2,3,4\\},j\,{\in}\,\\{1,2,3,4\\}{\setminus}\\{i\\}\\}$

as well as the following rules:

$\displaystyle r_{2}(X,Y)\wedge r_{3}(X,Y)\wedge r_{4}(X,Y)$
$\displaystyle\rightarrow s_{1}(X,Y)$ $\displaystyle s_{1}(X,Y)\wedge
r_{1}(X,Y)$ $\displaystyle\rightarrow\bot$

Note that $\mathcal{K}$ is indeed consistent. In fact, we can capture the
rules in $\mathcal{K}$ using a region-based embedding $\gamma$ in
$\mathbb{R}^{3}$ as follows:

$\displaystyle\gamma(s_{1})$ $\displaystyle=\\{(0,0,0)\\}$
$\displaystyle\gamma(s_{2})$ $\displaystyle=\\{(1,0,0)\\}$
$\displaystyle\gamma(s_{3})$ $\displaystyle=\\{(0,1,0)\\}$
$\displaystyle\gamma(s_{4})$ $\displaystyle=\\{(0,0,1)\\}$
$\displaystyle\gamma(r_{1})$
$\displaystyle=\text{CH}(\\{(1,0,0),(0,1,0),(0,0,1)\\})$
$\displaystyle\gamma(r_{2})$
$\displaystyle=\text{CH}(\\{(0,0,0),(0,1,0),(0,0,1)\\})$
$\displaystyle\gamma(r_{3})$
$\displaystyle=\text{CH}(\\{(0,0,0),(1,0,0),(0,0,1)\\})$
$\displaystyle\gamma(r_{4})$
$\displaystyle=\text{CH}(\\{(0,0,0),(1,0,0),(0,1,0)\\})$

where we write CH to denote the convex hull.

Now let us consider convex embeddings $\gamma$ of the form (70). Suppose such
an embedding satisfies the rules in $\mathcal{K}$. Suppose furthermore that
$\gamma(r)\neq\emptyset$ for every relation
$r\in\\{s_{1},s_{2},s_{3},s_{4},r_{1},r_{2},r_{3},r_{4}\\}$. Since $\gamma$
satisfies $s_{1}(X,Y)\wedge r_{1}(X,Y)\rightarrow\bot$, there must be some
$\ell\in\\{1,\ldots,n\\}$ such that $X_{s_{1}}^{\ell}\cap
X_{r_{1}}^{\ell}=\emptyset$, where we write $X^{i}_{r}$ for the two-
dimensional convex region modelling relation $r$ in coordinate $i$. Since
$s_{1}(X,Y)\rightarrow r_{2}(X,Y)$, $s_{1}(X,Y)\rightarrow r_{3}(X,Y)$ and
$s_{1}(X,Y)\rightarrow r_{4}(X,Y)$ are satisfied, with
$\gamma(s_{1})\neq\emptyset$, we know that there exists some point $p_{1}\in
X_{r_{2}}^{\ell}\cap X_{r_{3}}^{\ell}\cap X_{r_{4}}^{\ell}$. In the same way,
we find that there exist points $p_{2}\in X_{r_{1}}^{\ell}\cap
X_{r_{3}}^{\ell}\cap X_{r_{4}}^{\ell}$, $p_{3}\in X_{r_{1}}^{\ell}\cap
X_{r_{2}}^{\ell}\cap X_{r_{4}}^{\ell}$ and $p_{4}\in X_{r_{1}}^{\ell}\cap
X_{r_{2}}^{\ell}\cap X_{r_{3}}^{\ell}$. From Helly’s theorem, it then follows
that there exists a point $q\in X_{r_{1}}^{\ell}\cap X_{r_{2}}^{\ell}\cap
X_{r_{3}}^{\ell}\cap X_{r_{4}}^{\ell}$. Because $\gamma$ satisfies the rule
$r_{2}(X,Y)\wedge r_{3}(X,Y)\wedge r_{4}(X,Y)\rightarrow s_{1}(X,Y)$, we must
then also have that $q\in X_{s_{1}}^{\ell}$. This is a contradiction since we
assumed $X_{s_{1}}^{\ell}\cap X_{r_{1}}^{\ell}=\emptyset$ and we have $q\in
X_{r_{1}}^{\ell}$. It follows that some of the regions
$\gamma(s_{1}),\gamma(s_{2}),\gamma(s_{3}),\gamma(s_{4})$ must be empty. But
then $\gamma$ always satisfies rules which are not entailed by $\mathcal{K}$.
For instance, if $\gamma(s_{1})=\emptyset$ then, among others we have that
$\gamma\models s_{1}\rightarrow r_{1}$.

For convex embeddings of the form (71), we find from the fact that $\gamma$
satisfies $s_{1}(X,Y)\wedge r_{1}(X,Y)\rightarrow\bot$ that there must be some
$\ell\in\\{1,\ldots,n\\}$ such that $A_{s_{1}}^{\ell}\cap
A_{r_{1}}^{\ell}=\emptyset$ or $B_{s_{1}}^{\ell}\cap
B_{r_{1}}^{\ell}=\emptyset$. The remainder of the proof is then entirely
analogous, focusing on the regions $A_{r}^{\ell}$ or $B_{r}^{\ell}$ rather
than $X_{r}^{\ell}$. ∎

Let the octagons $O^{(l)}$ be defined as in Section A.3.

######  Lemma 9.

Suppose $u^{-}\leq 0$, $u^{+}\geq 0$ and $v^{-}\leq v^{+}$. For every $l\geq
2$ it holds that $O^{(l)}\subseteq O^{(l+2)}$.

###### Proof.

From Lemma 3 we already know that

$\displaystyle x_{l+2}^{-}$ $\displaystyle=x_{l}^{-}$ $\displaystyle
x_{l+2}^{+}$ $\displaystyle=x_{l}^{+}$ $\displaystyle y_{l+2}^{-}$
$\displaystyle=y_{l}^{-}$ $\displaystyle y_{l+2}^{+}$
$\displaystyle=y_{l}^{+}$

For the remaining bounds, entirely similar as in the proof of Lemma 4, we
find:

$\displaystyle(v_{l+1}^{+}\geq
v_{l}^{+})\Rightarrow(u_{l+2}^{-}=y^{-}-x_{2}^{+})\vee(u_{l+2}^{-}\leq
u_{l+1}^{-})$ $\displaystyle(v_{l+1}^{-}\leq
v_{l}^{-})\Rightarrow(u_{l+2}^{+}=y^{+}-x_{2}^{-})\vee(u_{l+2}^{+}\geq
u_{l+1}^{+})$ $\displaystyle(u_{l+1}^{+}\geq
u_{l}^{+})\Rightarrow(v_{l+2}^{-}=x_{2}^{-}+y^{-})\vee(v_{l+2}^{-}\leq
v_{l+1}^{-})$ $\displaystyle(u_{l+1}^{-}\leq
u_{l}^{-})\Rightarrow(v_{l+2}^{+}=x_{2}^{+}+y^{+})\vee(v_{l+2}^{+}\geq
v_{l+1}^{+})$

Note that $u_{l+2}^{-}=y^{-}-x_{2}^{+}$ implies $u_{l+2}^{-}\leq u_{l+1}^{-}$,
and similar for the other cases. These implications can thus be simplified to:

$\displaystyle(v_{l+1}^{+}\geq v_{l}^{+})\Rightarrow(u_{l+2}^{-}\leq
u_{l+1}^{-})$ (72) $\displaystyle(v_{l+1}^{-}\leq
v_{l}^{-})\Rightarrow(u_{l+2}^{+}\geq u_{l+1}^{+})$ (73)
$\displaystyle(u_{l+1}^{+}\geq u_{l}^{+})\Rightarrow(v_{l+2}^{-}\leq
v_{l+1}^{-})$ (74) $\displaystyle(u_{l+1}^{-}\leq
u_{l}^{-})\Rightarrow(v_{l+2}^{+}\geq v_{l+1}^{+})$ (75)

From Lemma 3 we also know that $v_{2}^{+}\geq v^{+}$ and $v_{2}^{-}\leq
v^{-}$. Putting everything together, we find that for even values of $l$, the
following hold:

$\displaystyle(u_{l+1}^{-}\leq u_{l}^{-})$ (76) $\displaystyle(u_{l+1}^{+}\geq
u_{l}^{+})$ (77) $\displaystyle(v_{l}^{-}\leq v_{l-1}^{-})$ (78)
$\displaystyle(v_{l}^{+}\geq v_{l-1}^{+})$ (79)

Let $l\geq 2$. We show that $u_{l+2}^{-}\leq u_{l}^{-}$.

  * •

First assume that $l$ is even. Then we already know that $u_{l+1}^{-}\leq
u_{l}^{-}$. We can only have $u_{l+2}^{-}>u_{l+1}^{-}$ if
$u_{l+2}^{-}=v^{-}-v_{l+1}^{+}$. From $u_{l+2}^{-}>u_{l+1}^{-}$, we also find
that $v^{-}-v_{l+1}^{+}>v^{-}-v_{l}^{+}$ has to hold, or in other words
$v_{l}^{+}>v_{l+1}^{+}$, which is only possible if
$v_{l+1}^{-}=v^{+}-u_{l}^{-}$. But then we find
$u_{l+2}^{-}=v^{-}-v_{l+1}^{+}=v^{-}-v^{+}+u_{l}^{-}\leq u_{l}^{-}$. In any
case, we thus find that $u_{l+2}^{-}\leq u_{l}^{-}$.

  * •

Now assume that $l$ is odd. From (76) we know $u_{l+2}^{-}\leq u_{l+1}^{-}$.
Suppose $u_{l+1}^{-}>u_{l}^{-}$. Note that $u_{l+2}^{-}\leq u_{l}^{-}$ is
trivially satisfied if
$u_{l+2}^{-}=y^{-}-x_{l+1}^{+}=y^{-}-x_{2}^{+}=y^{-}-x_{l-1}^{+}$. If
$u_{l+2}^{-}=v^{-}-v_{l+1}^{+}$ we find
$u_{l+2}^{-}=v^{-}-v_{l+1}^{+}=v^{-}-v^{+}+u_{l}^{-}\leq u_{l}^{-}$ as in the
previous case. Now assume $u_{l+2}^{-}=u^{-}+u_{l}^{-}$. From
$u_{l+1}^{-}>u_{l}^{-}$, using (72), we find $v_{l}^{+}<v_{l-1}^{+}$. This is
only possible if $u_{l+1}^{-}=v^{-}-v_{l}^{+}$ and
$v_{l}^{+}=v^{+}-u_{l-1}^{-}$. We find
$u_{l+2}^{-}=u^{-}+u_{l+1}^{-}=u^{-}+v^{-}-v^{+}+u_{l-1}^{-}$. If
$u_{l+2}^{-}>u_{l}^{-}$ were to hold, we would thus have
$u^{-}+v^{-}-v^{+}+u_{l-1}^{-}>u_{l}^{-}\geq u^{-}+u_{l-1}^{-}$, which implies
$v^{-}>v^{+}$, a contradiction.

In entirely the same way, we can show that $u_{l+2}^{+}\geq u_{l}^{+}$,
$v_{l+2}^{-}\leq v_{l}^{-}$ and $v_{l+2}^{+}\geq v_{l}^{+}$. ∎

######  Proposition 18.

Let $\mathcal{K}=\\{r_{1}(X,Y)\wedge r_{1}(Y,Z)\rightarrow
r_{2}(X,Z),r_{2}(X,Y)\wedge r_{2}(Y,Z)\rightarrow r_{3}(X,Z)\\}$. It holds
that every octagon embedding $\gamma$ which satisfies $\mathcal{K}$ also
satisfies some composition rule which is not entailed by $\mathcal{K}$.

###### Proof.

Let $\gamma$ be a coordinate-wise octagon embedding satisfying the rules in
$\mathcal{K}$ and let $\gamma(r_{1})=X_{r_{1}}=[O_{1},\ldots,O_{n}]$. First
assume that there is some $i$ such that $O_{i}=\mathsf{Octa}(x^{-},\allowbreak
x^{+},\allowbreak y^{-},\allowbreak y^{+},\allowbreak u^{-},\allowbreak
u^{+},\allowbreak v^{-},\allowbreak v^{+})$ with $u^{+}<0$ or $u^{-}>0$. Then
we know from Lemma 2 that there exists some $k\in\mathbb{N}$ such that
$O_{i}^{(k)}=\emptyset$. This also means that $X_{r_{1}}^{(k)}=\emptyset$,
where we define $X_{r_{1}}^{(l)}=X_{r_{1}}^{(l-1)}\diamond X_{r_{1}}$ for
$l\geq 2$ and $X_{r_{1}}^{(1)}=X_{r_{1}}$. Among others, we find that $\gamma$
satisfies the following composition rule, which is not entailed by
$\mathcal{K}$:

$\displaystyle r_{1}(X_{1},X_{2})\wedge\ldots\wedge
r_{1}(X_{k},X_{k+1})\rightarrow r_{2}(X_{1},X_{k+1})$

Now assume that none of the octagons $O_{1},\ldots,O_{n}$ has a strictly
negative $u^{+}$ bound or a strictly positive $u^{-}$ bound. From Lemma 9 it
then follows that:

$X_{r_{1}}\diamond X_{r_{1}}\subseteq X_{r_{1}}\diamond X_{r_{1}}\diamond
X_{r_{1}}\diamond X_{r_{1}}$

It follows that $\gamma$ satisfies the following composition rule, which is
not entailed by $\mathcal{K}$:

$r_{1}(X,Y)\wedge r_{1}(Y,Z)\rightarrow r_{3}(X,Z)$

∎

###  B.3 Capturing Non-Composition Rules

Let $\mathcal{K}$ be a rule base consisting of symmetry, inversion, hierarchy
and intersection rules. We construct an octagon embedding
$\gamma_{\mathcal{K}}$ satisfying these rules, without satisfying any rules
not entailed by $\mathcal{K}$. Let $\mathcal{R}$ be the set of relations
appearing in $\mathcal{K}$. We consider assignments
$\alpha:\mathcal{R}\rightarrow\\{-2,-1,0,1,2\\}$ and write $\mathcal{A}$ for
the set of all such assignments. We will construct embeddings with one
coordinate for each assignment, writing $\alpha_{i}$ for the assignment
associated with coordinate $i$. The following octagons will play a central
role:

$\displaystyle X_{j}$ $\displaystyle=\text{CH}\\{(0,0),(j,j),(j,0)\\}$
$\displaystyle Y_{j}$ $\displaystyle=\text{CH}\\{(0,0),(j,j),(0,j)\\}$
$\displaystyle Z$
$\displaystyle=\text{CH}\\{(0,0),(0,1),(1,2),(2,2),(2,1),(1,0)\\}$

Note that $X_{j}^{\textit{inv}}=Y_{j}$. Let $O_{r,i}$ be the octagon
representing relation $r$ in coordinate $i$. We initialise these octagons as
follows:

$\displaystyle O^{(0)}_{r,i}=\begin{cases}X_{\alpha_{i}(r)}&\text{if
$\alpha_{i}(r)>0$}\\\ Y_{|\alpha_{i}(r)|}&\text{if $\alpha_{i}(r)<0$}\\\
Z&\text{otherwise}\end{cases}$

We then consider the following update rules ($j\geq 1$):

$\displaystyle O^{(j)}_{r,i}=\textit{cl}\\{$ $\displaystyle O^{(j-1)}_{r,i}$
$\displaystyle\cup\\{O^{(j)}_{s,i}\,|\,\mathcal{K}\models s\subseteq r\\}$
$\displaystyle\cup\\{(O^{(j)}_{s,i})^{\textit{inv}}\,|\,\mathcal{K}\models
s\subseteq r^{-1}\\}$ $\displaystyle\cup\\{O^{(j)}_{s,i}\cap
O^{(j)}_{t,i}\,|\,\mathcal{K}\models s\cap t\subseteq r\\}\\}$

Clearly, in each iteration, we have $O^{(j)}_{r,i}\supseteq O^{(j-1)}_{r,i}$.
Furthermore, there are only finitely many values $O^{(j)}_{r,i}$ can take
(i.e. the closures of subsets of $\\{X_{1},X_{2},Z,Y_{1},Y_{2}\\}$). This
iterative process will thus reach a fix point after a finite number of steps.
Let $O_{r,i}$ be the resulting octagons, and $\gamma_{\mathcal{K}}$ the
associated octagon embedding. The following result immediately follows from
the proposed construction:

######  Lemma 10.

It holds that $\gamma_{\mathcal{K}}$ captures every rule in $\mathcal{K}$.

We now show that $\gamma_{\mathcal{K}}$ does not satisfy any unwanted rules.

######  Lemma 11.

Assume $\mathcal{K}\not\models r\subseteq s$. There exists a coordinate $i$
such that $O_{r,i}\not\subseteq O_{s,i}$.

###### Proof.

Consider the following assignment:

$\displaystyle\alpha_{i}(t)=\begin{cases}2&\text{if $t=r$}\\\
1&\text{otherwise}\end{cases}$

We show by induction that for any relation $t$ it holds that $X_{2}\subseteq
O^{(j)}_{t,i}$ implies $\mathcal{K}\models r\subseteq t$ and $Y_{2}\subseteq
O^{(j)}_{t,i}$ implies $\mathcal{K}\models r^{-1}\subseteq t$, from which it
will follow in particular that $O^{(j)}_{r,i}\not\subseteq O^{(j)}_{s,i}$. The
base case is trivially satisfied since we only have $X_{2}\subseteq
O^{(j)}_{t,i}$ for $t=r$, while $Y_{2}\subseteq O^{(j)}_{t,i}$ does not hold
for any relation. Now suppose the result is known to hold for all octagons
$O^{(j-1)}_{t,i}$.

We now consider the inductive case. Suppose $X_{2}\subseteq O^{(j)}_{t,i}$.
Note that all octagons are closures of subsets of $X_{1},X_{2},Y_{1},Y_{2}$.
For such octagons, we have $X_{2}\subseteq\textit{cl}(O_{1},\ldots,O_{k})$ iff
$X_{2}\subseteq O_{j}$ for some $j$. We thus have that one of the following
cases must be true.

  * •

If $X_{2}\subseteq O^{(j-1)}_{t,i}$ then by induction we have
$\mathcal{K}\models r\subseteq t$.

  * •

If $X_{2}\subseteq O^{(j-1)}_{p,i}$ with $\mathcal{K}\models p\subseteq t$
then by induction we have $\mathcal{K}\models r\subseteq p$, and thus we also
find $\mathcal{K}\models r\subseteq t$.

  * •

If $Y_{2}\subseteq O^{(j-1)}_{p,i}$ with $\mathcal{K}\models p\subseteq
t^{-1}$ then by induction we have $\mathcal{K}\models r^{-1}\subseteq p$, and
thus we also find $\mathcal{K}\models r\subseteq t$.

  * •

If $X_{2}\subseteq O^{(j-1)}_{p,i}\cap O^{(j-1)}_{q,i}$ with $p\cap q\subseteq
t$ then by induction we have $\mathcal{K}\models r\subseteq p$ and
$\mathcal{K}\models r\subseteq q$ and thus also $\mathcal{K}\models r\subseteq
t$.

The proof for $Y_{2}\subseteq O^{(j)}_{t,i}$ is entirely analogous. ∎

######  Lemma 12.

Assume $\mathcal{K}\not\models r\subseteq s^{-1}$. There exists a coordinate
$i$ such that $O_{r,i}\not\subseteq O_{s,i}^{\textit{inv}}$.

###### Proof.

We consider the same assignment as in the proof of Lemma 11:

$\displaystyle\alpha_{i}(t)=\begin{cases}2&\text{if $t=r$}\\\
1&\text{otherwise}\end{cases}$

We then again have that for any relation $t$ it holds that $X_{2}\subseteq
O^{(j)}_{t,i}$ implies $\mathcal{K}\models r\subseteq t$ and $Y_{2}\subseteq
O^{(j)}_{t,i}$ implies $\mathcal{K}\models r^{-1}\subseteq t$. We have in
particular that $X_{2}\subseteq O^{(j)}_{s^{-1},i}$ iff $Y_{2}\subseteq
O^{(j)}_{s,i}$. The latter implies $\mathcal{K}\models r^{-1}\subseteq s$,
which is equivalent to $\mathcal{K}\models r\subseteq s^{-1}$. Since we
assumed $\mathcal{K}\models r\not\subseteq s^{-1}$, it follows that
$X_{2}\not\subseteq O^{(j)}_{s^{-1},i}$ and thus $O_{r,i}\not\subseteq
O_{s,i}^{\textit{inv}}$. ∎

Note that the above lemma also holds if $r=s$, so we have also established
that $\gamma_{\mathcal{K}}$ does not capture any unwanted symmetry rules.

######  Lemma 13.

Assume $\mathcal{K}\not\models r_{1}\cap r_{2}\subseteq s$. There exists a
coordinate $i$ such that $O_{r_{1},i}\cap O_{r_{2},i}\not\subseteq O_{s,i}$.

###### Proof.

Consider the following assignment:

$\displaystyle\alpha_{i}(t)=\begin{cases}2&\text{if
$t\in\\{r_{1},r_{2}\\}$}\\\ 1&\text{otherwise}\end{cases}$

The remainder of the proof is entirely analogous to the proof of Lemma 11. In
particular, in the same way, we find by induction that for any relation $t$ it
holds that $X_{2}\subseteq O^{(j)}_{t,i}$ implies $\mathcal{K}\models
r_{1}\cap r_{2}\subseteq t$ and $Y_{2}\subseteq O^{(j)}_{t,i}$ implies
$\mathcal{K}\models r_{1}^{-1}\cap r_{2}^{-1}\subseteq t$. ∎

######  Lemma 14.

For any $r_{1},r_{2},s\in\mathcal{R}$, there exists a coordinate $i$ such that
$O_{r_{1},i}\diamond O_{r_{2},i}\not\subseteq O_{s,i}$.

###### Proof.

Consider the following assignment.

$\displaystyle\alpha_{i}(t)=\begin{cases}0&\text{if
$t\in\\{r_{1},r_{2}\\}$}\\\ 1&\text{otherwise}\end{cases}$

Note that we clearly have $(0,2)\notin O_{r,i}^{(l)}$ for any
$r\in\mathcal{R}$ and $l\geq 0$. However, we also have

$\displaystyle O_{r_{1},i}\diamond O_{r_{2},i}\supseteq Z\diamond
Z=\text{CH}\\{(0,0),(0,2),(2,0),(2,2)\\}$

Since $(0,2)\in O_{r_{1},i}\diamond O_{r_{2},i}$ we obtain
$O_{r_{1},i}\diamond O_{r_{2},i}\not\subseteq O_{s,i}$. ∎

Finally, the following two lemmas, showing that $\gamma_{\mathcal{K}}$ does
not capture any unwanted asymmetry and mutual exclusion rules, follow
trivially from the construction.

######  Lemma 15.

Let $r_{1},r_{2}\in\mathcal{R}$. For every coordinate $i$, it holds that
$O_{r_{1},i}\cap O_{r_{2},i}\neq\emptyset$.

######  Lemma 16.

Let $r\in\mathcal{R}$. For every coordinate $i$, it holds that $O_{r,i}\cap
O_{r,i}^{\textit{inv}}\neq\emptyset$.

Putting everything together, we have shown the following result.

######  Proposition 19.

Let $\mathcal{K}$ be a set of symmetry, inversion, hierarchy and intersection
rules. There exists a coordinate-wise octagon embedding $\gamma$ which
satisfies $\mathcal{K}$, and which only satisfies those symmetry, inversion,
hierarchy and intersection rules which are entailed by $\mathcal{K}$, and
which does not satisfy any asymmetry, mutual exclusion and composition rules.

###  B.4 Capturing Rules: Compositions

We will consider octagons of the following form ($i+j\leq m$):

$\displaystyle A_{i,j,m}$
$\displaystyle=\text{CH}\\{(i,0),(i,i+j),(m-j,m),(m,m),(m,0)\\}$
$\displaystyle=\mathsf{Octa}(i,m,0,m,-m,j,i,2m)$

For the ease of presentation, in the following we will sometimes write rules
in terms of the relational operators and set inclusions. For instance, a rule
such as $r_{1}(X,Y)\wedge r_{2}(Y,Z)\rightarrow r(X,Z)$ will be written as
$r_{1}\circ r_{2}\subseteq r$.

######  Lemma 17.

Let $\mathcal{K}$ be a set of extended composition rules. Assume that any
extended composition rule entailed by $\mathcal{K}$ is either a trivial rule
of the form $r\subseteq r$ or a regular rule. Let $\mathcal{R}$ be the set of
relations appearing in $\mathcal{K}$. There exists an assignment
$\tau:\mathcal{R}\rightarrow\mathbb{N}$ such that whenever $r$ appears in the
body of a rule from $\mathcal{K}$ which has $s$ in the head
($r,s\in\mathcal{R}$) it holds that $\tau(r)<\tau(s)$.

###### Proof.

Let us consider a dependency graph $G=(\mathcal{R},E)$ where the nodes of the
graph correspond to the set of relations $\mathcal{R}$ and there is an edge
$(r,s)\in E$ iff $\mathcal{K}$ contains a rule with $r$ in the body and $s$ in
the head. If this graph is free from cycles, then we can straightforwardly
construct a suitable assignment $\tau$ using topological sort.

To conclude the proof, we show by contradiction that $G$ is always free from
cycles. Suppose $G$ did contain a cycle $(r_{1},r_{2}),\ldots,(r_{k},r_{1})$.
Because $(r_{k},r_{1})\in E$, we know that there is some rule of the form

$\displaystyle t_{1}\circ\ldots\circ r_{k}\circ\ldots\circ t_{l}\subseteq
r_{1}$

Because $(r_{k-1},r_{k})\in E$ we know that there is a rule which has $r_{k}$
in the head and $r_{k-1}$ in the body. We thus also have that $\mathcal{K}$
must entail a rule which has $r_{1}$ in the head and $r_{k-1}$ in the body.
Continuing this argument, we find that $\mathcal{K}$ entails a rule with
$r_{1}$ oin the body and $r_{1}$ in the head. This is a contradiction because
we had assumed that any extended composition rule entailed by $\mathcal{K}$ is
regular. It follows that $G$ cannot have any cycles. ∎

Let $\mathcal{K}$ be a set of regular composition rules, and assume that any
extended composition rule entailed by $\mathcal{K}$ is either a trivial rule
of the form $r\subseteq r$ or a regular rule. We construct an embedding
capturing the rules in $\mathcal{K}$ as follows. Let us consider assignments
$\alpha$ from $\mathcal{R}$ to pairs $(i,k)$ with $1\leq i\leq k$ and
$k\leq|\mathcal{R}|+1$. Let $\mathcal{A}$ be the set of all such assignments.
We consider embeddings with one coordinate for each of these assignments. Let
us write $\alpha_{i}$ for the assignment associated with coordinate $i$. We
furthermore write $O_{r,i}$ for the $i\textsuperscript{th}$ coordinate of the
octagon representing relation $r$. We define these octagons as follows. First,
for $r\in\mathcal{R}$, with $\alpha_{i}(r)=(j,k)$, we define:

$\displaystyle X_{r,i}=\begin{cases}A_{j,1,k}&\text{if $j<k$}\\\
\\{(k,k)\\}&\text{otherwise}\end{cases}$

Let us write $\mathsf{DC}(\mathcal{K})$ for the deductive closure of
$\mathcal{K}$. More precisely, $\mathsf{DC}(\mathcal{K})$ is the set of all
extended composition rules which can be entailed from $\mathcal{K}$ and which
are not trivial rules of the form $r\subseteq r$. We can then consider the
following recursive definition, which we know to be well-defined thanks to
Lemma 17 ($r\in\mathcal{R}$):

$\displaystyle O_{r,i}=\textit{cl}\\{$ $\displaystyle X_{r,i}\cup$
$\displaystyle\\{O_{s_{1},i}\,{\diamond}\,...\,{\diamond}\,O_{s_{k},i}\,|\,(s_{1}\,{\circ}\,...\,{\circ}\,s_{k}\subseteq
r)\in\mathsf{DC}(\mathcal{K})\\}\\}$

where the closure cl of a set of octagons $O_{1},\ldots,O_{k}$ with
$O_{i}=\mathsf{Octa}(x_{i}^{-},\allowbreak x_{i}^{+},\allowbreak
y_{i}^{-},\allowbreak y_{i}^{+},\allowbreak u_{i}^{-},\allowbreak
u_{i}^{+},\allowbreak v_{i}^{-},\allowbreak v_{i}^{+})$ is given by the
octagon $O^{*}=\mathsf{Octa}(x_{*}^{-},\allowbreak x_{*}^{+},\allowbreak
y_{*}^{-},\allowbreak y_{*}^{+},\allowbreak u_{*}^{-},\allowbreak
u_{*}^{+},\allowbreak v_{*}^{-},\allowbreak v_{*}^{+})$ with
$x_{*}^{-}=\min_{i}x_{i}^{-}$, $x_{*}^{+}=\max_{i}x_{i}^{+}$,
$y_{*}^{-}=\min_{i}y_{i}^{-}$, $y_{*}^{+}=\max_{i}y_{i}^{+}$,
$u_{*}^{-}=\min_{i}u_{i}^{-}$, $u_{*}^{+}=\max_{i}u_{i}^{+}$,
$v_{*}^{-}=\min_{i}v_{i}^{-}$ and $v_{*}^{+}=\max_{i}v_{i}^{+}$. In other
words, $\textit{cl}(O_{1},\ldots,O_{k})$ is the smallest octagon which
contains $O_{1},\ldots,O_{k}$.

Let us write $\gamma_{\mathcal{K}}$ for the octagon embedding defined above.
The following result immediately follows from the construction of
$\gamma_{\mathcal{K}}$.

######  Lemma 18.

It holds that $\gamma_{\mathcal{K}}$ captures every rule in $\mathcal{K}$.

We still need to show that $\gamma_{\mathcal{K}}$ only captures the extended
composition rules which are entailed by $\mathcal{K}$. We will first show this
for rules of the form $r_{1}\circ\ldots\circ r_{k}\subseteq\mathcal{R}$ where
all of the relations $r_{1},\ldots,r_{k},r$ are distinct. Let us consider such
a composition $r_{1}\circ\ldots\circ r_{k}$, where $k\leq|\mathcal{R}|-1$ and
$r_{i}\neq r_{j}$ for $i\neq j$. We associate with such a composition the
following assignment $\alpha_{i}$.

$\displaystyle\alpha_{i}(r)=\begin{cases}(j,k+1)&\text{if $r=r_{j}$}\\\
(k+1,k+1)&\text{otherwise}\end{cases}$

For the ease of presentation, we will write $A_{i,j,k+1}$ as $A_{i,j}$ in the
following. Furthermore, we will write $b_{u}^{+}(O)$ for the normalised
$y^{+}$ bound of an octagon $O$, i.e. $b_{u}^{+}(O)=\max\\{y-x\,|\,(x,y)\in
O\\}$. Similarly, we write $b_{x}^{-}(O)$ for $\min\\{x\,|\,(x,y)\in O\\}$ and
$b_{y}^{+}(O)$ for $\max\\{y\,|\,(x,y)\in O\\}$.

With each $s\in\mathcal{R}$, we associate a subset $\mathcal{R}_{s}$ of
$\\{r_{1},\ldots,r_{k}\\}$ as follows: $r_{j}\in\mathcal{R}_{s}$ if
$\mathcal{K}$ entails a rule with $r_{j}$ in the body and $s$ in the head. Let
us write $|\mathcal{R}_{s}|=n_{s}$ and
$\min\\{j\,|\,r_{j}\in\mathcal{R}_{s}\\}=j_{s}$, where we assume $j_{s}=k+1$
if $|\mathcal{R}_{s}|=\emptyset$.

######  Lemma 19.

It holds that $b_{u}^{+}(O_{s,i})\leq n_{s}$ and $b_{x}^{-}(O_{s,i})\geq
j_{s}$.

###### Proof.

We show the result by structural induction, taking advantage of the acyclic
nature of the rule base (i.e. Lemma 17). Let us first consider the base case
where there are no rules of the form $t_{1}\circ\ldots\circ t_{p}\subseteq s$
entailed by $\mathcal{K}$ (except for the trivial rule $s\subseteq s$). If
$s=r_{j}$, we have $\mathcal{R}_{j}=\\{r_{j}\\}$, due to the assumption about
there being no rules of the form $t_{1}\circ\ldots\circ t_{p}\subseteq s$
entailed by $\mathcal{K}$. Accordingly, we have
$b_{u}^{+}(O_{s,i})=b_{u}^{+}(A_{j,1})=1=n_{s}$ and
$b_{x}^{-}(O_{s,i})=j=j_{s}$. If $s\notin\\{r_{1},\ldots,r_{k}\\}$, we have
$n_{s}=0$ and $X_{s,i}=\\{(k+1,k+1)\\}$. It follows that
$b_{u}^{+}(O_{s,i})=0\leq n_{s}$ and $b_{x}^{-}(O_{s,i})=k+1=j_{s}$.

For the inductive case, assume that for every rule $t_{1}\circ\ldots\circ
t_{p}\subseteq s$ entailed by $\mathcal{K}$, apart from the trivial rule
$s\subseteq s$, the result is already known to hold for $t_{1},\ldots,t_{p}$.
If $n_{s}=0$, we must have $n_{t_{1}}=\ldots=n_{t_{p}}=0$. By induction we
thus have $b_{u}^{+}(O_{t_{1},i})=\ldots=b_{u}^{+}(O_{t_{p},i})=0$. From the
characterisation of composition, it then follows that
$b_{u}^{+}(O_{t_{1},i}\diamond\ldots\diamond O_{t_{p},i})=0$. Furthermore, we
have $X_{s,i}=\\{(k+1,k+1)\\}$, meaning $b_{u}^{+}(X_{s,i})=0$. We can thus
conclude $b_{u}^{+}(O_{s},i)=0$. Note that when $n_{s}=0$, the condition
$b_{x}^{-}(O_{s,i})\geq j_{s}$ is trivial as we then have $j_{s}=k+1$.

Now assume $n_{s}>0$. Note that $j_{t_{1}}\geq j_{s}$. By induction we have
$b_{x}^{-}(O_{t_{1},i})\geq j_{t_{1}}\geq j_{s}$. From the characterisation of
composition we also have $b_{x}^{-}(O_{t_{1},i}\diamond\ldots\diamond
O_{t_{p},i})\geq b_{x}^{-}(O_{t_{1},i})\geq j_{s}$. We clearly also have
$b_{x}^{-}(X_{s,i})\geq j_{s}$. We thus have $b_{x}^{-}(O_{s,i})\geq j_{s}$.
Since $\mathcal{K}$ only entails regular rules, we know that
$\mathcal{R}_{t_{i}}\cap\mathcal{R}_{t_{j}}=\emptyset$ for $i\neq j$. We thus
have $n_{s}\geq n_{t_{1}}+\ldots+n_{t_{p}}$. From the induction hypothesis we
know that $b_{u}^{+}(O_{t_{j},i})\leq n_{t_{j}}$. Furthermore, from the
characterisation of composition we know
$b_{u}^{+}(O_{t_{1},i}\diamond\ldots\diamond O_{t_{p},i})\leq
b_{u}^{+}(O_{t_{1},i})+\ldots+b_{u}^{+}(O_{t_{p},i})\leq
n_{t_{1}}+\ldots+n_{t_{p}}\leq n_{s}$. We clearly also have
$b_{u}^{+}(X_{s,i})\leq n_{s}$. We conclude $b_{u}^{+}(O_{s,i})\leq n_{s}$. ∎

######  Lemma 20.

Suppose $s\notin\\{r_{1},\ldots,r_{k}\\}$ and $j_{s}<k+1$. We have
$b_{x}^{-}(O_{s,i})>j_{s}$ unless
$\mathcal{R}_{s}=\\{r_{j_{s}},r_{j_{s}+1},\ldots,r_{j_{s}+n_{s}-1}\\}$ and
$\mathcal{K}\models r_{j_{s}}\circ r_{j_{s}+1}\circ\ldots\circ
r_{j_{s}+n_{s}-1}\subseteq s$.

###### Proof.

We show the result by structural induction, taking advantage of the acyclic
nature of the rule base (i.e. Lemma 17). Let us first consider the base case
where there are no rules of the form $t_{1}\circ\ldots\circ t_{p}\subseteq s$
entailed by $\mathcal{K}$ (except for the trivial $s\subseteq s$). If
$s=r_{j}$ we have $O_{s,i}=X_{j,1}$ and thus clearly
$b_{x}^{-}(O_{s,i})=j=j_{s}$. If $s\notin\\{r_{1},\ldots,r_{k}\\}$ we have
$b_{x}^{-}(O_{s,i})=k+1$ and the result is thus also satisfied.

For the inductive step, let us now assume that for every rule of the form
$t_{1}\circ\ldots\circ t_{p}\subseteq s$ entailed by $\mathcal{K}$ (apart from
the trivial rule $s\subseteq s$) the result is already known to hold for
$t_{1},\ldots,t_{p}$. Since we assumed $s\notin\\{r_{1},\ldots,r_{k}\\}$, we
can only have $b_{x}^{-}(O_{s,i})=j_{s}$ if there is some rule
$t_{1}\circ\ldots\circ t_{p}\subseteq s$ entailed by $\mathcal{K}$ such that
$b_{x}^{-}(O_{t_{1}}\diamond\ldots\diamond O_{t_{p}})=j_{s}$. Let us consider
such a rule. Because $\mathcal{K}$ only entails regular rules, it must be the
case that $\mathcal{R}_{t_{i}}\cap\mathcal{R}_{t_{j}}=\emptyset$ for $i\neq
j$. If $b_{x}^{-}(O_{t_{1},i})>j_{s}$ then we clearly have
$b_{x}^{-}(O_{t_{1},i}\diamond\ldots\diamond O_{t_{p},i})>j_{s}$. Let us
therefore assume that $b_{x}^{-}(O_{t_{1},i})=j_{s}$, which by induction
implies $\mathcal{R}_{t_{1}}=\\{r_{j_{s}},\ldots,r_{j_{s}+n_{t_{1}}-1}\\}$ and
$\mathcal{K}\models r_{j_{s}}\circ\ldots\circ r_{j_{s}+n_{t_{1}}-1}\subseteq
t_{1}$. From the characterisation of composition, we know that
$b_{x}^{-}(O_{t_{1},i}\diamond O_{t_{2},i})=b_{x}^{-}(O_{t_{1},i})$ can only
hold if $b_{x}^{-}(O_{t_{1},i})\geq
b_{x}^{-}(O_{t_{2},i})-b_{u}^{+}(O_{t_{1},i})$. From Lemma 19 we know that
$b_{u}^{+}(O_{t_{1},i})\leq n_{t_{1}}$. Since we moreover assumed
$b_{x}^{-}(O_{t_{1},i})=j_{s}$ we find $b_{x}^{-}(O_{t_{2},i})\leq
n_{t_{1}}+j_{s}$. From Lemma 19 we know that this means $j_{t_{2}}\leq
n_{t_{1}}+j_{s}$. Since
$\\{r_{j_{s}},\ldots,r_{j_{s}+n_{t_{1}}-1}\\}\cap\mathcal{R}_{2}=\emptyset$,
this is only possible if $j_{t_{2}}=j_{s}+n_{t_{1}}$. By the induction
hypothesis, this can only hold if
$\mathcal{R}_{t_{2}}=\\{r_{j_{s}+n_{t_{1}}},\ldots,r_{j_{s}+n_{t_{1}}+n_{t_{2}}-1}\\}$
and $\mathcal{K}\models r_{j_{s}+n_{t_{1}}}\circ\ldots\circ
r_{j_{s}+n_{t_{1}}+n_{t_{2}}-1}\subseteq t_{2}$. Continuing in the same way,
we find that $b_{x}^{-}(O_{t_{1},i}\diamond\ldots\diamond O_{t_{p},i})=j_{s}$
is only possible if $\mathcal{K}$ entails $r_{j_{s}}\circ\ldots\circ
r_{j_{s}+n_{t_{1}}-1}\subseteq t_{1}$, $r_{j_{s}+n_{t_{1}}}\circ\ldots\circ
r_{j_{s}+n_{t_{1}}+n_{t_{2}}-1}\subseteq t_{2}$, …,
$r_{j_{s}+n_{t_{1}}+\ldots+n_{t_{p-1}}}\circ\ldots\circ
r_{j_{s}+n_{t_{1}}+\ldots+n_{t_{p}}-1}\subseteq t_{p}$ and thus we also have
$\mathcal{K}\models r_{j_{s}}\circ r_{j_{s}+1}\circ\ldots\circ
r_{j_{s}+n_{s}-1}\subseteq s$. ∎

Let $s_{1}\circ\ldots\circ s_{m}\subseteq r$ be a rule which is entailed by
$\mathcal{K}$. Let us associate with each $s_{\ell}$ a set of relations
$\mathcal{R}_{\ell}\subseteq\\{r_{1},\ldots,r_{k}\\}$ as follows:
$r_{j}\in\mathcal{R}_{\ell}$ if $\mathcal{K}$ entails a rule with $r_{j}$ in
the body and $s_{\ell}$ in the head.

######  Lemma 21.

Let $r_{1},\ldots,r_{k},r\in\mathcal{R}$ be distinct relations and assume that
$\mathcal{K}\not\models r_{1}\circ\ldots\circ r_{k}\subseteq r$. Then
$O_{r_{1},i}\diamond\ldots\diamond O_{r_{k},i}\not\subseteq O_{r,i}$ for some
coordinate $i$ for $\alpha_{i}$ the assignment defined above.

###### Proof.

First note that $k<|\mathcal{R}|$ since $r_{1},\ldots,r_{k+1}$ were assumed to
be all distinct. We clearly have:

$\displaystyle O_{r_{1},i}\diamond\ldots\diamond O_{r_{k},i}$
$\displaystyle\supseteq A_{1,1}\diamond\ldots\diamond A_{k,1}=A_{1,k}$

In particular, we have that $(1,k+1)\in O_{r_{1},i}\diamond\ldots\diamond
O_{r_{k},i}$. To conclude the proof we show that $(1,k+1)\notin O_{r,i}$ and
in particular that $b_{u}^{+}(O_{r,i})<k$. Given that $\mathcal{K}\not\models
r_{1}\circ\ldots\circ r_{k}\subseteq r$ we find from Lemma 20 that
$b_{x}^{-}(O_{r,i})\geq 2$. Since we trivially have $b_{y}^{+}(O_{r_{,}i})\leq
k+1$, we obtain $b_{u}^{+}(O_{r_{,}i})\leq k-1$. ∎

Lemma 21 shows that $\gamma_{\mathcal{K}}$ does not capture any unwanted rules
of the form $r_{1}\circ\ldots\circ r_{k}\subseteq r$ where
$r_{1},\ldots,r_{k},r$ are distinct relations. We now show that the same is
true for rules where $r_{1},\ldots,r_{k},r$ are not necessarily distinct. Note
that when $r_{1},\ldots,r_{k},r$ are not all distinct, we always have
$\mathcal{K}\not\models r_{1}\circ\ldots\circ r_{k}\subseteq r$ (except for
the trivial rule $r\subseteq r$), given our assumption about $\mathcal{K}$.

######  Lemma 22.

Let $s_{1},\ldots,s_{l}\in\mathcal{R}$ be such that $s_{p}=s_{q}$ for some
$p\neq q$. There is a coordinate $i$ such that
$O_{s_{1},i}\diamond\ldots\diamond O_{s_{l},i}\not\subseteq O_{r,i}$ for any
relation $r\in\mathcal{R}$.

###### Proof.

Let $r_{1},\ldots,r_{k}$ be the unique relations among $s_{1},\ldots,s_{l}$,
i.e. we have $\\{r_{1},\ldots,r_{k}\\}=\\{s_{1},\ldots,s_{l}\\}$ with $k<l$.
Let us define the assignment $\alpha_{i}$ as follows:

$\displaystyle\alpha_{i}(r_{j})=(1,|\mathcal{R}|+1)$

and for $r\notin\\{r_{1},\ldots,r_{k}\\}$ we have

$\displaystyle\alpha_{i}(r)=(|\mathcal{R}|+1,|\mathcal{R}|+1)$

Clearly, we have that $b_{u}^{+}(O_{s_{1},i}\diamond\ldots\diamond
O_{s_{l},i})\geq\min(l,|\mathcal{R}|)$. To complete the proof, we show that
$b_{u}^{+}(O_{r,i})\leq\min(l-1,|\mathcal{R}|-1)$. Let us define
$\mathcal{R}_{s}$ and $n_{s}$ as before. We show that $b_{u}^{+}(O_{r,i})\leq
n_{s}$, from which the result follows since we clearly have
$n_{r}\leq\min(k,|\mathcal{R}|-1)\leq\min(l-1,|\mathcal{R}|-1)$.

In the base case where there are no non-trivial rules $t_{1}\circ\ldots\circ
t_{p}\subseteq r$ entailed by $\mathcal{K}$, we clearly have
$b_{u}^{+}(O_{r,i})=0$ if $r\notin\\{r_{1},\ldots,r_{k}\\}$ and thus $n_{s}=0$
(due to the assumption of there not being any rules $t_{1}\circ\ldots\circ
t_{p}\subseteq r$ entailed by $\mathcal{K}$). If
$r\in\\{r_{1},\ldots,r_{k}\\}$ we have $n_{r}=1$ and
$b_{u}^{+}(O_{r,i})=b_{u}^{+}(X_{r,i})=1$. For the inductive case, we find
$b_{u}^{+}(X_{r,i})\leq n_{r}$ as in the base case. If $t_{1}\circ\ldots\circ
t_{p}\subseteq r$ is entailed by $\mathcal{K}$ we know that
$n_{t_{1}}+\ldots+n_{t_{p}}\leq n_{r}$, since $\mathcal{K}$ only entails
regular (non-trivial) rules. By induction and the characterisation of
composition, we know that $b_{u}^{+}(O_{t_{1},i}\diamond\ldots\diamond
O_{t_{p},i})\leq
b_{u}^{+}(O_{t_{1},i})+\ldots+b_{u}^{+}(O_{t_{p},i})=n_{t_{1}}+\ldots+n_{t_{p}}\leq
n_{r}$. ∎

######  Lemma 23.

Let $s_{1},\ldots,s_{l},r\in\mathcal{R}$ be such that
$r\in\\{s_{1},\ldots,s_{l}\\}$ and $l\geq 2$. There is a coordinate $i$ such
that $O_{s_{1},i}\diamond\ldots\diamond O_{s_{l},i}\not\subseteq O_{r,i}$ for
any relation $r\in\mathcal{R}$.

###### Proof.

Let $r_{1},\ldots,r_{k}$ be the unique relations among $s_{1},\ldots,s_{l}$,
i.e. we have $\\{r_{1},\ldots,r_{k}\\}=\\{s_{1},\ldots,s_{l}\\}$ with $k\leq
l$. Let us consider the same assignment $\alpha_{i}$ as in the proof of Lemma
22. We then again find that $b_{u}^{+}(O_{s_{1},i}\diamond\ldots\diamond
O_{s_{l},i})\geq\min(l,|\mathcal{R}|)$ and $b_{u}^{+}(O_{s,i})\leq n_{s}$ for
each relation $s$. By construction, we have $b_{u}^{+}(X_{r,i})=0$. For each
non-trivial rule of the form $t_{1}\circ\ldots\circ t_{p}\subseteq r$ we have
$b_{u}^{+}(O_{t_{j},i})\leq n_{t_{j}}$ and $n_{t_{1}}+\ldots+n_{t_{p}}\leq
n_{r}$. Moreover, due to the fact that $\mathcal{K}$ only entails regular
(non-trivial) rules, we have $r\notin\mathcal{R}_{t_{j}}$, meaning that
$n_{t_{1}}+\ldots+n_{t_{p}}<n_{r}$. It follows that
$b_{u}^{+}(O_{t_{1},i}\diamond\ldots\diamond O_{t_{p},i})<n_{r}\leq
k\leq\min(l,|\mathcal{R}|)$. Given that $l\geq 2$ we also have
$b_{u}^{+}(X_{r,i})=1<\min(l,|\mathcal{R}|)$. We thus find
$b_{u}^{+}(O_{t_{1},i}<\min(l,|\mathcal{R}|)$, from which the result follows.
∎

######  Proposition 20.

Let $\mathcal{K}$ be a set of regular composition rules. Assume that any
extended composition rule entailed by $\mathcal{K}$ is either a trivial rule
of the form $r\subseteq r$ or a regular rule. There exists an octagon
embedding $\gamma$ which satisfies $\mathcal{K}$, and which only satisfies
those extended composition rules which are entailed by $\mathcal{K}$.

###### Proof.

The result follows directly from Lemmas 18, 21, 22 and 23. ∎

##  Appendix C Experimental Results

We conducted two experiments: link prediction in high dimension, to compare
with results previously published on this task, and link prediction in low
dimension. These experiments aim to compare the performances of octagon
embeddings with other region based embedding models.

###  C.1 Implementation Details

The octagon model was implemented using the PyKEEN
library555https://github.com/pykeen/pykeen. Octagon embeddings are learnt in
batches using the Adam optimizer and a Self-Adversarial Negative Sampling
(NSSA) loss, like BoxE and ExpressivE. Validation is performed every 10 epochs
and the best model over 1,000 epochs is used for testing. In all experiments,
octagons are initialised as narrow $u$-bands with wide $v$, $x$ and $y$
constraints. That is, $(u_{w})_{i}=0.1$ and
$(v_{w})_{i}=(x_{w})_{i}=(y_{w})_{i}=1$ for all $1\leq i\leq n$. The center of
$u$-bands is initialised randomly.

|  | dim. $n$ |  $L_{p}$-norm | margin $\lambda$ | neg. samples $|N|$ | learning rate | batch size
---|---|---|---|---|---|---|---
$uvxy$ | FB15k-237 | 1000 | 1 | 15 | 150 | $10^{-3}$ | 1024
$uvxy$ | WN18RR | 500 | 1 | 35 | 5 | $10^{-2}$ | 512
TransE | FB15k-237 | 40 | 1 | 4 | 50 | $10^{-3}$ | 256
TransE | WN18RR | 40 | 1 | 3 | 50 | $10^{-3}$ | 256
BoxE | FB15k-237 | 20 | 2 | 4 | 50 | $10^{-3}$ | 256
BoxE | WN18RR | 20 | 2 | 3 | 50 | $10^{-3}$ | 256
ExpressivE | FB15k-237 | 40 | 2 | 4 | 50 | $10^{-2}$ | 1024
ExpressivE | WN18RR | 40 | 2 | 3 | 50 | $10^{-2}$ | 512
$uvxy$ | FB15k-237 | 40 | 1 | 3 | 50 | $10^{-3}$ | 1024
$uvxy$ | WN18RR | 40 | 1 | 3 | 5 | $10^{-2}$ | 512
Table 2: Hyperparameters used in experiments. All configurations of the
octagon model share the same hyperparameters.

The full implementation, including configuration files to reproduce results
discussed in Section C.2, is available
online666https://github.com/vcharpenay/uvxy. Hyperparameters used in the
experiments are also reproduced in Table 2 for completeness. Some
hyperparameters (embedding dimension, number of negative samples and batch
size) alter the inductive power of a model. For a fair comparison, in high
dimension, we have set these hyperparameters with the same values as in prior
experiments on ExpressivE777https://github.com/AleksVap/ExpressivE/, with one
exception: on WN18RR, we empirically observed that less negative samples gave
slightly better results. We therefore set $|N|=5$ (instead of $|N|=100$). In
low dimension, these hyperparameters have been taken from experiments done on
MuRE888https://github.com/ibalazevic/multirelational-poincare/, with the same
exception on WN18RR. To our knowledge, no result had been made available for
BoxE and ExpressivE in low dimension. Other hyperparameters that are rather
influenced by the model’s scoring function (margin, $L_{p}$-norm, learning
rate) have been chosen after a grid search. Possible values were
$\\{3,4,6,9,12,15,21,27,35,41\\}$ for the margin, $\\{1,2\\}$ for the
$L_{p}$-norm and $\\{10^{-2},10^{-3}\\}$ for the optimizer’s learning rate. In
low dimension, a search over $\\{256,512,1024\\}$ has also been performed for
the optimal batch size.

###  C.2 Discussion

| FB15k-237 | WN18RR
---|---|---
| H@1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10 | MRR
TransE | 23.3 | 37.2 | 53.1 | 33.2 | 01.3 | 40.1 | 52.9 | 22.3
BoxE | 23.8 | 37.4 | 53.8 | 33.7 | 40.0 | 47.2 | 54.1 | 45.1
ExpressivE | 24.3 | 36.6 | 51.2 | 33.3 | 46.4 | 52.2 | 59.7 | 50.8
$u$ | 22.8 | 37.2 | 53.2 | 33.0 | 00.4 | 40.4 | 52.0 | 21.6
$ux$ | 22.9 | 36.4 | 52.6 | 32.7 | 00.4 | 40.4 | 53.2 | 22.0
$uxy$ | 22.8 | 36.5 | 52.3 | 32.6 | 01.7 | 46.7 | 53.8 | 22.5
$uv$ | 23.0 | 35.7 | 51.1 | 32.3 | 01.9 | 42.4 | 52.1 | 23.2
$uv^{*}$ | 23.1 | 36.3 | 52.3 | 32.7 | 42.8 | 46.5 | 50.1 | 45.5
$uvxy$ | 22.8 | 35.6 | 50.6 | 32.0 | 04.8 | 43.5 | 53.4 | 25.5
$uvxy^{*}$ | 23.1 | 36.0 | 52.1 | 32.6 | 44.3 | 49.9 | 56.6 | 48.5
$u+v$ | 23.6 | 37.4 | 53.3 | 33.5 | 41.3 | 45.8 | 50.2 | 44.5
Table 3: Link prediction performances of region based embedding models
($n=1000$ on FB15k-237, $n=500$ on WN18RR). Configurations with ∗ use the
variant with attention weights.

Table 3 gives results in high dimension. Results for TransE, BoxE and
ExpressivE are not ours. They were respectively published in Sun et al.
(2019), Abboud et al. (2020) and Pavlovic and Sallinger (2023). Two results
are available for the $uv$ and $uvxy$ configurations: with and without
attention weights. Attention improves performance on all metrics but one:
Hits@10 on WN18RR in the $uv$ configuration is $2\%$ lower with attention.
Attention does however greatly increase Hits@1.

| FB15k-237 | WN18RR
---|---|---
| H@1 | H@3 | H@10 | MRR | H@1 | H@3 | H@10 | MRR
TransE | 18.3 | 30.5 | 46.2 | 27.5 | 03.0 | 33.8 | 52.8 | 21.3
MuRE | 22.7 | 34.6 | 49.3 | 31.5 | 42.9 | 47.4 | 52.8 | 45.9
BoxE | 17.9 | 29.0 | 43.9 | 26.5 | 41.7 | 45.5 | 49.6 | 44.5
ExpressivE | 18.7 | 30.4 | 46.0 | 27.6 | 43.4 | 48.9 | 55.5 | 47.5
$u$ | 19.9 | 32.7 | 48.6 | 29.4 | 02.0 | 34.4 | 49.7 | 20.3
$ux$ | 20.3 | 32.9 | 48.6 | 29.7 | 02.1 | 34.8 | 50.2 | 20.6
$uy$ | 20.1 | 32.9 | 48.6 | 29.5 | 02.0 | 32.8 | 49.4 | 19.7
$uxy$ | 20.5 | 33.3 | 48.9 | 29.9 | 02.3 | 34.2 | 50.1 | 20.5
$uv$ | 15.9 | 27.4 | 41.9 | 24.6 | 16.4 | 43.3 | 52.8 | 31.2
$uv^{*}$ | 19.0 | 30.7 | 45.6 | 27.8 | 16.4 | 43.3 | 52.8 | 31.2
$uvxy$ | 20.2 | 32.5 | 47.8 | 29.4 | 32.1 | 45.5 | 52.1 | 40.1
$uvxy^{\text{\textdagger}}$ | 20.2 | 32.0 | 47.6 | 29.2 | 37.3 | 43.9 | 49.3 | 41.7
$uvxy^{*}$ | 20.6 | 32.5 | 47.2 | 29.5 | 31.7 | 46.0 | 52.2 | 40.1
$u+v$ | 19.9 | 32.0 | 47.9 | 29.0 | 30.7 | 41.9 | 49.9 | 37.6
Table 4: Link prediction of region based embedding models in low dimension
($n=40$). Configurations with ∗ use the variant with attention weights.
Configurations with ${}^{\text{\textdagger}}$ use regular octagons at
initialisation (others use pseudo $u$-bands).

We evaluated more configurations in low dimension. Results for TransE, BoxE
and ExpressivE are also ours, those for MuRE were first published in Balazevic
et al. (2019a). Table 4 gives results for 40-dimensional models. Several
observations can be made. For instance, the performance of $uv$ and $uvxy$ in
low dimension is comparable to their performance in higher dimension. We also
observe that attention weights do not alter the performance of a model in low
dimension, contrary to higher-dimensional models. Conversely, full
$uvxy$-octagons outperform TransE, BoxE and ExpressivE on FB15k-237 in low
dimension but not in high dimension. From Table 4, we also note that $ux$ and
$uy$ give comparable results, with a small penalty for $uy$.

Two further results open up perspectives on learning octagon models. On
WN18RR, a different initialisation of octagons has a strong impact on the
learned embeddings: if initial octagons are regular octagons (instead of
pseudo $u$-bands), Hits@1 increases by $5\%$, at the expense of lower Hits@3
and Hits@10. More elaborate initialisation techniques may better take
advantage of the expressivity of octagons. Still on WN18RR, a model that mixes
a $u$ constraint in half of the coordinates and a $v$ constraint in the other
half achieves much higher Hits@1 than both $u$ and $uv$. This model is denoted
$u+v$ in Table 4. If we compare $u+v$ with BoxE, we get opposite conclusions
in low and high dimension. In low dimension, it has lower Hits@1 than BoxE but
comparable Hits@10; in high dimension, it has higher Hits@1 but lower Hits@10.
A more complex mixture of constraints may yield better performances.

## References

  * Abboud et al. [2020] Ralph Abboud, İsmail İlkan Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori.  BoxE: A box embedding model for knowledge base completion.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * Arakelyan et al. [2021] Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez.  Complex query answering with neural link predictors.  In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
  * Balazevic et al. [2019a] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales.  Multi-relational poincaré graph embeddings.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4465–4475, 2019.
  * Balazevic et al. [2019b] Ivana Balazevic, Carl Allen, and Timothy M. Hospedales.  TuckER: Tensor factorization for knowledge graph completion.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pages 5184–5193. Association for Computational Linguistics, 2019.
  * Bordes et al. [2011] Antoine Bordes, Jason Weston, Ronan Collobert, and Yoshua Bengio.  Learning structured embeddings of knowledge bases.  In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011, pages 301–306. AAAI Press, 2011.
  * Bordes et al. [2013] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2787–2795, 2013.
  * Dettmers et al. [2018] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel.  Convolutional 2d knowledge graph embeddings.  In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 1811–1818. AAAI Press, 2018.
  * Guo et al. [2018] Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo.  Knowledge graph embedding with iterative guidance from soft rules.  In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4816–4823. AAAI Press, 2018.
  * Guo et al. [2022] Qingyu Guo, Fuzhen Zhuang, Chuan Qin, Hengshu Zhu, Xing Xie, Hui Xiong, and Qing He.  A survey on knowledge graph-based recommender systems.  IEEE Trans. Knowl. Data Eng., 34(8):3549–3568, 2022.
  * Gutiérrez-Basulto and Schockaert [2018] Víctor Gutiérrez-Basulto and Steven Schockaert.  From knowledge graph embedding to ontology embedding? an analysis of the compatibility between vector space representations and rules.  In Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018, pages 379–388. AAAI Press, 2018.
  * Hogan et al. [2021] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann.  Knowledge Graphs.  Synthesis Lectures on Data, Semantics, and Knowledge. Morgan & Claypool Publishers, 2021.
  * Jackermeier et al. [2023] Mathias Jackermeier, Jiaoyan Chen, and Ian Horrocks.  Box2EL: Concept and role box embeddings for the description logic EL++.  CoRR, abs/2301.11118, 2023.