Capturing Knowledge Graphs and Rules with Octagon Embeddings

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 e for each entity e and a scoring function sr for each relation r such that sr(e, 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 sr(e, f) = -d(e + r, f), where r ∈ Rn is an embedding of the relation r, e, f ∈ Rn are entity embeddings of the same dimension and d is a distance metric. Note that sr(e, f ) achieves its maximal value of 0 iff e + r = f . We can thus say that the embedding fully supports the triple (e, r, f) when sr(e, f ) = 0. If r1 + r2 = r3 we have that sr1 (e, f ) = 0 and sr2 (f , g) = 0 together imply sr3 (e, g) = 0. In this sense, we can say that the embedding captures the following rule:

This correspondence between knowledge graph embeddings and symbolic rules is appealing. For instance, if we already know that (1) is valid, we can impose r1 + r2 = r3 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., 2019], 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´errez-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 Xr ⊆ R2n . We say that a triple (e, r, f) is captured by the embedding if e ⊕ f ∈ Xr, where ⊕ 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 Xr. For instance, we say that the embedding captures the rule r1(X, Y )∧r2(X, Y ) → r3(X, Y ) iff Xr1 ∩Xr2 ⊆ Xr3 . To model rules of the form (1), we can characterise relational composition as follows:

We then say that (1) is captured iff Xr1 ⋄ Xr2 ⊆ Xr3 . 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. 1

2 Preliminaries

Let E and R be sets of entities and relations respectively. We consider knowledge graph embeddings in which each entity e ∈ E is represented by a vector e ∈ Rn and each relation r ∈ R is represented by a region Xr ⊆ R2n . 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 e ⊕ f ⊆ Xr. 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.

Coordinate-wise region embeddings. Region based embeddings were first studied from a theoretical point of view in [Guti´errez-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 Xr which can be described using n two-dimensional regions Xir :

1 An extended version of this paper with supplementary materials can be found at https://arxiv.org/abs/2401.16270.

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

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 Xir are parallelograms. An important drawback of parallelograms is that they are not closed under composition: if Xir1 and Xir2 are parallelograms, then it may be that Xir1 ⋄Xir2 is not a parallelogram, with ⋄ 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:

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:

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:

An advantage of cross-coordinate models is that they can rely on simpler two-dimensional regions. For instance, the regions Air and Bir 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:

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

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

Other types of rules can be modelled in a similar way. For instance, a rule such as r1(X, Y ) ∧ r2(X, Y ) → r(X, Y ) is captured by a region based embedding if Xr1 ∩ Xr2 ⊆ Xr.

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 Xr1 ⋄ . . . ⋄ Xrk ⊆ Xr holds iff ∑ki=1 u-ri ≥ u-r and ∑ki=1 u+ri ≤ 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 r1(X, Y )∧r2(Y, Z) → r(X, Z) is satisfied, we also have that r2(X, Y ) ∧ r1(Y, Z) → 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 (7). It holds that (x1, . . . , x2n, z1, . . . , z2n) ∈ Xr1 ⋄ Xr2 iff there are y1, . . . , y2n ∈ R such that for every i ∈ {1, . . . , n} we have:

This is the case iff for every i ∈ {1, . . . , n} we have:

While Xr1 ⋄ Xr2 constrains the pairs (xi, zi) and (xn+i, zn+i), any region Xr3 rather constrains the pairs (xi, zn+i) and (xn+i, zi). It is thus not possible to have Xr1 ⋄ Xr2 ⊆ Xx3 , unless in trivial cases where Xr1 = ∅, Xr2 = ∅, or (if infinite bounds are allowed) Xr3 = R4n . In all these trivial cases, the embedding also captures other rules, e.g. if Xr1 = ∅ then all rules of the form r1(X, Y ) ∧ r4(Y, Z) → r5(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 Xr = [Or 1 , . . . ,Orn ] to denote that relation r is defined using the octagons Or 1 , . . . ,Orn , in the sense that (x1, . . . , xn, y1, . . . , yn) ∈ Xr iff (xi, yi) ∈ Or i for each i ∈ {1, . . . , n}. Clearly, if Xr = [Or 1 , . . . ,Orn ] and Xs = [Os 1 , . . . ,Osn ] then we have Xr ∩Xs = [Or 1 ∩Os 1 , . . . , Orn ∩Osn ] and Xr ⋄Xs = [Or 1 ⋄Os 1 , . . . ,Orn ⋄ Osn ]. 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 Octa(x-i , x+i , yi , y+ i , u-i , u+i , vi , v+ i ) to denote the octagon defined in (6). Note that the eight parameters are not independent. For instance, we have that Octa(x-, x+, y-, y+, u-, u+, v-, v+) = Octa(x-, x+, y-, y+, u-, u+,max(v-, x- + y-), v+). Indeed, if x ≥ x- and y ≥ y-, we also have x+y ≥ x- +y-, meaning that the bound x + y ≥ v- can be strengthened to x + y ≥ max(x- + y-, v-). We call the parameters (x-, x+, y-, y+, u-, u+, v-, 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. 2

Proposition 1. Consider the following set of parameters:

2 All proofs can be found in the supplementary materials.

Then Octa(x-, x+, y-, y+, u-, u+, v-, v+) = Octa(x-1 , x+1 , y1 , y+ 1 , u-1 , u+1 , v1 , v+ 1 ). Furthermore, if we have x-1 > x+1 , y1 > y+ 1 , u-1 > u+1 or v1 > v+ 1 then Octa(x-, x+, y-, y+, u-, u+, v-, v+) = ∅. Otherwise, the set of parameters (x-1 , x+1 , y1 , y+ 1 , u-1 , u+1 , v1 , v+ 1 ) is normalised.

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 Octa(x-1 , x+1 , y1 , y+ 1 , u-1 , u+1 , v1 , v+ 1 ) and Octa(x-2 , x+2 , y2 , y+ 2 , u-2 , u+2 , v2 , v+ 2 ) is the following octagon:

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

Proposition 2. Let O1 = Octa(x-1 , x+1 , y1 , y+ 1 , u-1 , u+1 , v1 , v+ 1 ) and O2 = Octa(x-2 , x+2 , y2 , y+ 2 , u-2 , u+2 , v2 , v+ 2 ) be non-empty octagons with normalised parameters. Then O1 ⋄ O2 = Octa(x-3 , x+3 , y3 , y+ 3 , u-3 , u+3 , v3 , v+ 3 ), where:

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

Then clearly we have (x, y) ∈ O iff (y, x) ∈ Oinv , hence the relation encoded by Oinv 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. ∀x ∈ [x-, x+] . (x, x) ∈ O, iff the following conditions are satisfied:

From the definition of composition, it straightforwardly follows that a non-empty octagon with normalised coordinates is transitive, i.e. satisfies O ⋄O ⊆ O, iff the following conditions are satisfied:

• u- ≤max(y- -x+, 2u-, v- - v+);
• u+ ≥min(y+ -x-, 2u+, v+ - v-);
• v- ≤max(x- + y-, u- + v-, v- -u+);
• v+ ≥min(x+ + y+, u+ + v+, v+ -u-).

We can also show the following.

Proposition 3. Let O = Octa(x-, x+, y-, y+, u-, u+, v-, v+) and assume that these parameters are normalised. It holds that O ⋄ O = O iff one of the following conditions is satisfied:

• O = ∅;
• O = [x-, x+] × [y-, y+] with x+ ≥ y- and x- ≤ y+;
• O = {(x, x) | x ∈ [x-, x+]};
• u- = 0, u+ > 0, v- < v+, v- - x+ ≤ x-, x+ ≤ v+ - x-, v- - y+ ≤ y-, y+ ≤ v+ - y- and u+ = min(y+ - x-, v+ - v-);
• u- < 0, u+ = 0, v- < v+, v- - x+ ≤ x-, x+ ≤ v+ - x-, v- - y+ ≤ y-, y+ ≤ 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) ⋄O for m ≥ 2 and O(1) = O. We then have the following result.

Proposition 4. If v- < v+ then there exists some m ≥ 1 such that O(m) ⋄ 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 γ. Such an embedding represents each entity e ∈ E as the vector γ(e) ∈ Rn and each relation r ∈ R as the region γ(r) ⊆ R2n . We say that γ is an octagon embedding if it is a coordinate-wise model in which γ(r) is defined in terms of octagons, for each r ∈ R.

4.1 Capturing Knowledge Graphs

With each region based embedding γ we can associate the knowledge graph Gγ = {(e, r, f) | γ(e) ⊕ γ(f) ∈ γ(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 G ⊆ E × R × E there exists an embedding γ such that G = Gγ. 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 (5) this is still not possible as the following proposition reveals.

Proposition 5. Let Xr be a hexagon region of the form (5) and let e, f ∈ Rn . If e ⊕ f ∈ Xr and f ⊕ e ∈ Xr then we also have e ⊕ e ∈ Xr .

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 G ⊆ E ×R× E be a knowledge graph. There exists an octagon embedding γ such that G = Gγ .

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 rules 3 :

Asymmetry:

r(X, Y ) → ¬r(Y, X)

(11)

Let us define the inverse region Xinv r as follows:

Note that when Xr = [O1, . . . ,On] then Xinv r = [Oinv 1 , . . . , Oinv n ] with Oinv i 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 γ captures or satisfies (10) iff γ(r) ⊆ γ(r)inv ; (11) iff γ(r) ∩ γ(r)inv = ∅; (12) iff γ(r1) ⊆ γ(r2)inv ; (13) iff γ(r1) ⊆ γ(r2); (14) iff γ(r1) ∩ γ(r2) ⊆ γ(r3); (15) iff γ(r1) ∩ γ(r2) = ∅; and (16) iff γ(r1) ⋄ γ(r2) ⊆ γ(r3). For a set of rules K and a rule ρ, we write K |= ρ to denote that ρ is entailed by K in the usual sense. We also write γ |= ρ to denote that the embedding γ captures the rule ρ.

3 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 r1(X, Y ) ≡ r2(Y,X). We consider inversion as a rule, since the equivalence can be straightforwardly recovered by two inversion rules.

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

Proposition 7. There exists a consistent set of hierarchy, intersection and mutual exclusion rules K such that every convex embedding of the form (3) or (7) which satisfies K also satisfies some hierarchy rule which is not entailed by K.

We can show the same result when only hierarchy, intersection and asymmetry rules are permitted. Note that Proposition 7 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 K be a set of symmetry, inversion, hierarchy and intersection rules. There exists a coordinate-wise octagon embedding γ which satisfies K, and which only satisfies those symmetry, inversion, hierarchy and intersection rules which are entailed by 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 K = {r1(X, Y ) ∧ r1(Y,Z) → r2(X,Z), r2(X, Y ) ∧ r2(Y,Z) → r3(X,Z)}. It holds that every octagon embedding γ which satisfies K also satisfies some composition rule which is not entailed by 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 R is an expression of the form:

where k ≥ 1 and r1, . . . , rk+1 ∈ R. Such a rule is called regular if we have ri ̸= rj for i ̸= 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 K be a set of regular composition rules. Assume that any extended composition rule entailed by K is either a trivial rule of the form r ⊆ r or a regular rule. There exists an octagon embedding γ which satisfies K, and which only satisfies those extended composition rules which are entailed by 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 playsForTeam(X, Y ) ∧ playsForTeam-1 (Y,Z) ∧ playsSport(Z,U) → 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 e⊕ f lies in Xr 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 Xr = [Or 1 , . . . , Orn ], where Or i = Octa(x-i , x+i , , yi , y+ i , , u-i , u+i , , vi , v+ i , ). Let us write x- = (x-1 , . . . , x-n ) and similar for x+, y-, y+, u-, u+, v- and v+. Octagon embeddings impose the following four constraints on an entity pair (e, f):

We will refer to the regions defined by these four constraints as bands. We can straightforwardly use the sigmoid function σ to convert the constraints into soft scores. For the uconstraint we can use the following "distance" to the u-band:

where we write uc = (u+ +u-)/2 and uw = (u+ -u-)/2. The functions distx, disty and distv are defined analogously. Note that e ⊕ f ∈ Xr iff distx(e, r, f) ≥ 0.5, disty(e, r, f) ≥ 0.5, distu(e, r, f) ≥ 0.5 and distv(e, r, f) ≥ 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 uatt, as follows:

where we write ⊙ for component-wise multiplication. Weighted variants of distx, disty and distv 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.

As in BoxE and ExpressivE, coordinate-wise scores are aggregated to a scalar by taking their negated norm. We define dist(e, r, f ) = distx(e, r, f ) ⊕ disty (e, r, f ) ⊕ distu(e, r, f ) ⊕ distv(e, r, f) and score triples as follows (and similar for the weighted variant):

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]:

where α = softmax(s(e1, r, f1) ⊕ . . . ⊕ s(en, r, fn), the margin λ is a hyperparameter, and N = {(e1, r, f1), . . . , (en, r, fn)} 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 distv and disty 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 difference 4 . 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 supplementary materials.

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 5 . Including the x and y constraints also improves performances 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. As Table 1 shows, uvxy outperforms BoxE on all metrics. Further analysis can be found in the supplementary materials.

4 An analysis of the impact of attention weights can be found in the supplementary materials.

Octagon embeddings slightly underperform ExpressivE in most cases. 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) or 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 RelatedWork

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., 2019] 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. Tensor decomposition models also have important theoretical limitations when it comes to capturing rules [Guti´errez-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.

5 This result still holds without attention weights: on WN18RR, uvxy achieves a H@1 of 39.6, H@3 of 45.9, H@10 of 50.7 and MRR of 43.8 without trainable attention weights.

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 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. 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´esocentre Clermont-Auvergne of the Universit´e Clermont Auvergne. Steven Schockaert was supported by grants from EPSRC (EP/W003309/1) and the Leverhulme Trust (RPG-2021-140).