ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion
Authors: Aleksandar Pavlović
Emanuel Sallinger
Venue: ICLR 2023 notable top 25% (2023)
Keywords: knowledge graph embedding
knowledge graph completion
composition
hierarchy
geometric interpretation

Abstract: Knowledge graphs are inherently incomplete. Therefore substantial research has been directed toward knowledge graph completion (KGC), i.e., predicting missing triples from the information represented in the knowledge graph (KG). KG embedding models (KGEs) have yielded promising results for KGC, yet any current KGE is incapable of: (1) fully capturing vital inference patterns (e.g., composition), (2) capturing prominent patterns jointly (e.g., hierarchy and composition), and (3) providing an intuitive interpretation of captured patterns. In this work, we propose ExpressivE, a fully expressive spatio-functional KGE that solves all these challenges simultaneously. ExpressivE embeds pairs of entities as points and relations as hyper-parallelograms in the virtual triple space $\mathbb{R}^{2d}$. This model design allows ExpressivE not only to capture a rich set of inference patterns jointly but additionally to display any supported inference pattern through the spatial relation of hyper-parallelograms, offering an intuitive and consistent geometric interpretation of ExpressivE embeddings and their captured patterns. Experimental results on standard KGC benchmarks reveal that ExpressivE is competitive with state-of-the-art KGEs and even significantly outperforms them on WN18RR.

Published as a conference paper at ICLR 2023
EXPRESSIVE: A SPATIO-FUNCTIONAL EMBEDDING FOR KNOWLEDGE GRAPH COMPLETION
Aleksandar Pavlović & Emanuel Sallinger
Research Unit of Databases and Artificial Intelligence
TU Wien
Vienna, Austria
(aleksandar. pavisaaoddrr...oooii,, emanuel... sall e (eallinngr)@tuuieenn
ABSTRACT
Knowledge graphs are inherently incomplete. Therefore substantial research has been directed toward knowledge graph completion (KGC), i.e., predicting missing triples from the information represented in the knowledge graph (KG). KG em- bedding models (KGEs) have yielded promising results for KGC, yet any current KGE is incapable of: fully capturing vital inference patterns (e.g., composi- tion), (2) capturing prominent patterns jointly (e.g., hierarchy and composition), and (3) providing an intuitive interpretation of captured patterns. In this work, we propose ExpressivE, fully expressive spatio-functional KGE that solves all these challenges simultaneously. ExpressivE: embeds pairs of entities as points and relations as aaper-parallelorree design allows ExpressivE not only to capture rich set of inference patterns jointly but additionally display any supported inference pattern through the spatial relation of interpretation of ExpressivE embeddings and their captured patterns. Experimental results on standard KGC benchmarks reveal that ExpressivE is competitive with state-of-the-an KGEs and even significantly outperforms them on WNISRR.
in the virtual triple space R2d This model
offering intuitive and consistent geometric
INTRODUCTION
Knowledge graphs (KGs) are large collections of triples re(en, 6t) over relations ri E R. and entities Cb. G2 E E used for representing, storing, and processing information. Real-world KGs such as Freebase (Bollacker al. 2007) and WordNet (Miller 1995) lie at the heart of numerous applications such as recommendation (Cao et al.) 2019), question answering (Zhang al. 2018), information retrieval (Dietz et al. 2018), and natural language processing (Chen & Zaniolo 2017).
KG Completion. Yet, KGs inherently incomplete, hindering the immediate utilization of their stored knowledge. For example, 75% of the people represented in Freebase lack a nationality (West) et al. 2014). Therefore, much research has been directed toward the problem of automatically inferring missing triples, called knowledge graph completion (KGC). KG embedding models (KGEs) that embed entities and relations of KG into latent spaces and quantify the plausibility of unknown triples by computing scores based on these learned embeddings have yielded promising results for KGC (Wang et al. 2017). Moreover, they have shown excellent knowledge representation capabilities, concisely capturing complex graph structures, e.g., entity hierarchies (Nickel & Kiela 2017).
Inference Patterns. Substantial research has been invested understanding which KGEs can capture which inference patterns, as summarized in Table I For instance, KGEs such as TransE (Bordes) al. 2013) and RotatE, (Sun et al., 2019) can capture fundamental patterns such as composition. Recently, however, it was discovered that these two models can only capture a fairly limited notion of composition (Zhang et al. 2019 Abboud et al. 2020 Lu & Hu 2020 Gao et al. 2020), ef. also Appendix K.1 Thus, multiple extensions have been proposed to tackle some of these limitations, focusing, e.g., on modeling non-commutative composition (Lu & Hu 2020 Gao et al. 2020). Yet. while these extensions solved some limitations, the purely functional nature of TransE, RotatE, and any of their extensions still limits them to capture solely compositional definition, not general composition (see Table
T for the defining formulas, and cf. also Appendix K. I details).

---

Published as a conference paper at ICLR 2023
Therefore, capturing general composition is still open problem. Even more, composition patterss describe paths, which are fundamental for navigation within a graph. Hence, the ability to capture general composition is vital for KGEs. In contrast, approaches such as SimplE (Kazemi & Poole 2018), ComplEx (Trouillon et al. 2016), and BoxE (Abboud et al. 2020) have managed to capture other vital patterns, such as hierarchy, yet unable to capture any notion of composition.
Table 1:
This table lists patterns that several KGEs can capture. Specifically, / represents that the pattern is supported and X that not supported. Furthermore, "Comp. def." stands for compositional definition and "Gen. comp." for general composition.
Inference Pattern
ExpressivE
BoxE
RotatE
TransE
DistMult
ComplEx
Symmetry: rxX, () -
x
V
Anti-symmetry: x -X(
X
Inversion: ()X (5 (X,,))
/
/
X
Comp. def.: def.: (Y), r rx((,
x
/
X
X
Gen. comp.: (Y) ())
x
x
Hierarchy: rx(X.Y) - (Y)
x
Intersection: (,(X, () rx(())
Mutual exclusion: /1 Y) (tg())))))
Challenge. While the extensive research on composition (Bordes al. 2013 Sun et al. 2019 Zhang
et al. 2019 Lu & Huj (0200) and hierarchy (Yang et al., 2015a Trouillon et al. 2016 Kazemi &
Poole 2018 Abboud al. (020) highlights their importance, any KGE so far is incapable of: (I)
capturing general composition, (2) capturing composition and hierarchy jointly, and (3) providing an intuitive geometric interpretation of captured inference patterns.
Contribution. This paper focuses on solving all the stated limitations simultaneously. In particular:
We introduce the spatio-functiona embedding model ExpressivE. It embeds pairs of entities as points and relations as hyper-parale paper-parallelograms in the space R2dd, which we call the virtual triple space. The virtual triple space allows ExpressivE to represent patterns through the spatial relationship of paper-parallllggrmms. offering intuitive and consistent geometric interpretation ExpressivE embeddings and their captured patterns.
We prove that ExpressivE can capture any pattern listed in Table This makes ExpressivE the first model capable of capturing both general composition and hierarchy jointly.
We prove that our model fully expressive, making ExpressivE the first KGE that both supports composition and is fully expressive.
We evaluate ExpressivE on the two standard KGC benchmarks WNISRR (Dettmers et al. 2018 and FB15k-237 (Toutanova& & Chen 2015), revealing that ExpressivE is competitive with state-of-the-aa (SotA) KGES and even significantly outperforms them on WN18RR.
Organization. Section introduces the KGC problem and methods for evaluating KGEs. Section embeds ExpressivE in the context related work. Section Aaaiioonniitrodae iintroduces ExpressivE, the virtual triple space, and interprets model's parameters within it. Section 5 anallyes model's expressive power and inference capabilities. space complexity and Section Summarizzs work. The appendix contains all proofs of theorems.
experimental results together with our model's
2 KNOWLEDGE GRAPH COMPLETION
This section introduces the KGC problem and evaluation methods (Abboud et al. 2020). Let us first introduce the triple vocabulary T. consisting of a finite set of entities E and relations R. We call an expression of the form re(en, ex) a triple, where E R and eh, e, E. Furthermore, a finite set of triples over and KGC is
call
en the head and e, the tail of the triple. Now, a KG the problem of predicting missing triples. KGEs can be evaluated by means of an: (1) experimental evaluation on benchmark datasets, (2) analysis of the model's expressiveness, and (3) analysis of the inference patterns that the model can capture. We will discuss each of these points in what follows.
Experimental Evaluation. The experimental evaluation of KGEs requires a set of true and corrupted triples. True triples re(en, et) G are corrupted by replacing either en e, with any e, E E such
2

---

Published as a conference paper at ICLR 2023
that the corrupted triple does not occur in G. KGEs define scores over triples and are optimized to score true triples higher than false ones, thereby estimating a given triple's 's truth. A KGE's KGC performance is measured with the mean reciprocal rank (MRR), the average of inverse ranks (1/rank) and Hits@k, the proportion of true triples within the predicted triples whose rank is at maximum k.
Expressiveness. A KGE is fully expressive if for any finite set of disjoint true and false triples, parameter set can be found such that the model classifies the triples of the set correctly. Intuitively, a fully expressive model can represent any given graph. However, this is not necessarily correlated with its inference capabilities (Abboud et al. 2020). For instance, while a fully expressive model may express the entire training set, it may have poor generalization capabilities (Abboud et al. 2020). Conversely, a model that is not fully expressive may underfit the training data severely (Abboud et al. 2020). Hence, KGEs should be both fully expressive and support important inference patterns.
Inference Patterns. The generalization capabilities of KGEs are commonly analyzed using inference patterns (short: patterns). They represent logical properties that allow to infer new triples from the ones in G. Patterns are of the form & + 6, where we call de the body and the head of the pattern. For instance, composition ri (X, Y) A r2 Z) - rx(x, Z) is prominent pattern. Intuitively, states that if the body of the pattern is satisfied, then the head needs to be satisfied, i.e., if for some entities ex: Ey, Cg E E the triples Tı (ez. ey) and r2 re((e,ez) are contained in G. then also ry(Eg, ea) needs to be in G. Further patterns are listed in Table and and discussed in Section 5 Analyzing the patterns that a KGE supports helps estimate its inference capabilities (Abboud et al. 2020
RELATED WORK
As our work focuses on KGEs that intuitively represent inference patterns, we have excluded neural models that are less interpretable (Dettmers et al.) 2018 Socher et al., 2013) Nathani et al. 2019). We investigate relevant literature to embed ExpressivE in its scientific context below:
Functional Models. So far, solely a subset of translational models supports composition. We call this subset functional models, they embed relations as functions fr. K Kd and entities as vectors
ej E KKd over some field K. These models represent true triples (e(e,, ex) as é Sr, (e₂) ). Thereby,
they can capture composition patterns via functional composition. TransE (Bordes et al. 2013 the pioneering functional model, embedding relations r; as fr. (ex) = e사 te,, with Cr, E K". However, is neither fully expressive nor can it capture 1-N, N-1, N-N. nor symmetric relations. RotatE (Sun)
et al., 2019) embeds relations as rotations in complex space, allowing it to capture symmetry patterns but leaving it otherwise with TransE's limitations. Recently, was discovered that TransF and RotatE
may only capture a fairly limited notion of composition (Zhang et al.) 2019 Abboud et al. 2020 Lu
& Hu 2020 Gao et al. 2020), cf. also Appendix K. Therefore, extensions have been proposed to Tackle some limitations, focusing, e.g., on modeling non-commutative composition (Lu & Hu 2020
Gao et al. 2020). While these extensions solved some limitations, the purely functional nature of TransE, RotatE, and any of their extensions limits them to capture solely compositional definition and not general composition (see Table [ for the defining formulas and cf. also Appendix I. for details).
Therefore, capturing general composition is still an open problem. Even more, functional models incapable of capturing vital patterns, such as hierarchies, completely (Abboud et al.) 2022)).
Bilinear Models. Bilinear models factorize the adjacency matrix of graph with bilinear product of entity and relation embeddings. The pioneering bilinear model is RESCAL (Nickel et al. 2011). It embeds relations with full-rank d matrices M and entities with d-dimensional vectors. DistMuit (Yang et al. 2015a) constrains RESCAL's ''s relation matrix M to a diagonal matrix for efficiency reasons, limiting DistMult to capture symmetric relations only. HolE (Nickel et al.) 2016) solves this limitation by combining entity embeddings via circular correlation, whereas ComplEx (Trouillon) et al. 2016) solves this limitation by embedding relations with a complex- valued diagonal matrix. HolE and ComplEx have subsequently been shown to be equivalent (Hayashi & Shimbo, 2017). SimplE (Kazemi& & Poole. 20018) is based on canonical polyadic decomposition (Hitchcock) 1927).
TuckER (Balazevic et al. 2019) is based on Tucker decomposition (Tucker 1966) and extends the capabilities of RESCAL and SimplE (Balazevic et al.] (019). While all bilinear models, excluding DistMult, are fully expressive, they cannot capture any notion of composition.
Spatial Models. Spatial models define semantic regions within the embedding space that allow the intuitive representation of certain patterns. In entity classification, for example, bounded axis-aligned
3

---

Published as a conference paper at ICLR 2023
hyper-rectangles (boxes) represent entity classes, capturing class hierarchies naturally through the spatial subsumption of these boxes (Vilnis et al., 2018: Subramanian & Chakrabarti] [2118: Li et al. 2019). Also, query answering systems such Query2Box (Ren et al. (020) - have used boxes to represent answer sets due to their intuitive interpretation as sets of entities. Although Query2Box can be used for KGC, entity classification approaches cannot scalably be employed in the general KGC setting, as this would require an embedding for each entity tuple (Abboud et al.) (020). BoxE (Abboud al. 2020 is the first spatial KGE dedicated KGC. It embeds relations as pair of boxes and entities as a set of points and bumps in the embedding space. The usage of boxes enables BoxE to capture any inference pattern that can be described by the intersection of boxes in the embedding space, such as hierarchy. Moreover, boxes enable BoxE to capture I-N. N-7, and N-V relations naturally. Yet, BoxE cannot capture any notion of composition (Abboud et al., 2020).
Our Work. These research gaps, namely that any KGE cannot capture general composition and hierarchy jointly, have motivated our work. In contrast to prior work, our model defines for each relation a pyyee-pprallleoogaam, allowing us to combine the benefits of both spatial and functional models. Even more, prior work primarily analyzes the embedding space itself, while we propose the novel virtual triple space that allows to display any captured inference pattern including general composition - through the spatial relation of hyper- papeerrprralllloras....
4 EXPRESSIVE AND THE VIRTUAL TRIPLE SPACE
This section introduces ExpressivE, KGE targeted toward KGC with the capabilities of captur- ing rich set of inference patterns. ExpressivE embeds entities points and relations as hyper- parallelograms in the virtual triple space I2d More concretely, instead of analyzing our model the d-dimensional embedding space RR we construct the novel virtual triple space that grants Expres- sivE's parameters a geometric meaning. Above all, the virtual triple space allows us to intuitively interpret ExpressivE embeddings and their captured patterns, as discussed in Section 5
Representation. Entities Ej E E are embedded in ExpressivE via a vector ej E R representing points in the latent embedding space Rd Relations r; E R are embedded as hyper-parraleeograns in the virtual triple space 22 More specifically, ExpressivE assigns to relation r; for each of its arity positions p E {h. t} the following vectors: (1) a slope vector r? E IRdd (2) a center vector cf E Id, and (3) a width vector di E (R2o)4. Intuitively, these vectors define the slopes r. of the hyper-parallelogram boundaries, its center Ey and width df.. A triple ry (e( eq) is captured to be true in an ExpressivE model if its relation and entity embeddings satisfy the following inequalities:
(eh- c - -f O et) 3 de
(et - c - F 0 = d
(2)
Where -l represents the element-wise absolute value of vector œ. @ represents the Hadamard (i.e., element-wise) product and 3 represents the element-wise less or equal operator. It is very complex to interpret this model in the embedding space Rdd Hence, we construct followingly virtual triple space in Rdd that will ease reasoning about the parameters and inference capabilities of ExpressivE.
Virtual Triple Space. We construct this virtual space by concatenating the head and tail entity embeddings. In detail, this means that any pair of entities (ct, ex) E E x E defines a point in the virtual triple space by concatenating their entity embeddings Ch, Ct E Rd i.e., (enllee) E IR2d where || is the concatenation operator. A set of important sub-spaces of the virtual triple space are the 2-dimensional spaces, created from the j-th embedding dimension of head entities and the j-th dimension of tail entities - i.e., the j-th and (d + ji-th virtual triple space dimensions. We call them correlation subspaces, as they visualize the captured relation-specifii dependencies of head and tail entity embeddings will be discussed followingly. Moreover, we call the correlation subspace spanned by the j-th and (d + j)-th virtual triple space dimension the j-th correlation subspace.
Parameter Interpretation. Inequalities [ and 2 construct each an intersection of two parallel half- spaces in any correlation subspace of the virtual triple space. We call the intersection of two parallel half-spaces band, as they are limited by two parallel boundaries. Henceforth, we will denote with v(j) the j-th dimension of a vector v. For example, (ex()) ct ()) r(()) ex())) -1 = d)) defines a band in the j-th correlation subspace. The intersection of two bands results either in a band (if one band subsumes the other) a parallelogram. Since we interested in constructing ExpressivE
4

---

Published as a conference paper at ICLR 2023
embeddings that capture certain inference patterns, is sufficient consider parallelograms for these constructions. Figure Ia visualizes a relation parallelogram (green solid) and its parameters (orange dashed) in the j-th corretation subspace. In essence, the parallelogram is the result of the intersection of two bands (thick blue and magenta lines), where its boundaries' slopes are defined by r. the center of the parallelogram is defined by cf, and finally, the widths of each band are defined by d..
ei)
(i)
PF
rD
Identity Line
d
TA
rC
FB
40)
c 01
d'())
(i)
(i)
(a)
(b)
Figure 1: (a) Interpretation of relation parameters (orange dashed) as parallelogram (green solid)
in the j-th correlation subspace; (b) Multiple relation embeddings with the following properties:
Symmetry (rn). Anti-Symmetry (F TD. TE. FF), Inversion (rD - Hierarchy A (X.Y) +
rx(X, Y), Intersection (X, Y) A rx((, X, Y) = (x Y), Mutual Exclusion (e.g.. r Arg r = 0).
Since Inequalities T and solely capture dependencies within the same dimension, any two different dimensions * of head and tail entity embeddings are independent. Thus, relations are embedded hyper-paraalelogramms in the virtual triple space, whose edges are solely crooked in any j-th correlation subspace. Intuitively, the crooked edges represent relation-specific dependencies between head and tail entities and thus vital for the expressive power of ExpressivE. Note that each correlation subspace represents one dimension of the element-wiss Inequalities I and 2 Since the sum of all correlation subspaces represents all dimensions of Inequalities] [ and [2] is sufficient to analyze all correlation subspaces to identify the captured inference patterns of an ExpressivE model.
Scoring Function. Let (h.(h denote the embedding of triple r; (h,, t), i.c., Tri(h,t) (ehe htt r @ e with Ezy = (e-zley)) and a; ay = {afl
) for a E (c,r, r, d} and x. y E (h, t).
D(h, (2, Tri(h,t) Ø Wi, (rr(h, O w. - k, otherwise
Tr.,h)) 1 dhe
Equation states the typical distance function of spatial KGES (Abboud et al. 2020). where w; 20 d + is width-dependent factor and k = 0.5 O (w; 1) (w; Ø wa). If triple r:(h,t) t) is captured to be true by an ExpressivE embedding, i..., if (h. I dht then the distance correlates inversely with the syper-parallelogram'ss width, keeping low distances/gradieents within the parallelogram. Otherwise, the distance correlates linearly with the width penalize points outside larger parallelograms. Appendix function is defined as s(h, r., t) = =- 11, r., 2)..2. Following Abboud al. (2020). we optimize the adverarraaal negative sampling loss (Sun et al.) 2019) using the Adam optimizer (Kingma &
α provides further details on the distance function. The scoring
Ba 2015). We have provided more details on the training setup in Appendix M
KNOWLEDGE CAPTURING CAPABILITIES
This section analyzes ExpressivE's s expressive power and supported patterns. In what follows, we assume the standard definition of capturing patterns (Sun et al.) 2019 Abboud et al.) 2020). This means intuitively that a KGE captures pattern if set of parameters exists such that the pattern is captured exactly and exclusively. Appendix CemmdixxCooraa formalizes this notion for model.
5

---

Published as a conference paper at ICLR 2023
5.1 EXPRESSIVENESS
This section analyzes whether ExpressivE is fully expressive (Abboud et al., 2020). i.e., can capture any graph G over R and E. Theorem proves that this is the case by constructing for any graph G an ExpressivE embedding that captures any triple within G to be true and any other triple to be false. Specifically, the proof uses induction, starting with an embedding that captures the complete graph. ie., any triple over E' and R is true. Next, each induction step shows that we can alter the embedding to make an arbitrarily picked triple of the form re (x) with r; E R. Gj. Ck E E and ej F ex false. Finally, we add E * [ dimensions to make any self-loop - i.e., any triple of the form r=(e,, ez) with ry E R and ej E E- - false. The full, quite technical proof can be found in Appendix D
Theorem 5.1 (Expressive Power) ExpressivE can capture any arbitrary graph G over R and E if the embedding dimensionality d least in O(E) RR).
5.2 INFERENCE PATTERNS
This section proves that ExpressivE can capture any pattern from Table First, we discuss how ExpressivE represents inference patterns with at most two variables. Next, we introduce the notion of compositional definition and continue by identifying how this pattern is described in the virtual triple space. Then, we define general composition, building on both the notion of compositional definition and hierarchy. Finally, we conclude this section by discussing the key properties of ExpressivE.
Two- Variabee Patterns, Figure lb displays several one- mie-dimensional relation embeddings and their captured patterns in correlation subspace. Intuitively, ExpressivE represents: (1) symmetry patterns rn r (X,Y) > ri (Y, X) via symmetric hyper-parale papper-prallelorrmss (2) anti-symmetry patterns ri (i Y) + v X) via hyper-parallelogras that do not overlap with their mirror image, (3)
inversion patterns rı (X, Y) < (Y, via r2's hyper-parallelogram being the mirror image of ri 's. (4) hierarchy patterns T2 (X, Y) + T2(X, X Y) via T2 ceppe--prraleeogrrnn subsuming ri 's. (5) intersection patterns rı rx(X, Y) (2 = rs rx,X,Y Y) via r''s hyper- paraallellloog subsuming the intersection of ri 's and r2 's, and (6) mutual exclusion patterns ri (X,Y) Y) A ra Y) +
mutually exclusive hyper-parallelogrann capture any of these two-variable inference patterns in Theorem 5.2 (see Appendices F and G
of ri and We have formally proven that ExpressivE can
Theorem 5.2 ExpressivE captures (a) symmetry, (b) anti-symmeery, (c) inversion, (d) hierarchy, (e) intersection, and (f) mutual exclusion.
Compositional Definition. A compositional definition pattern is of the form (X, Ar2((, ra(X, Z), where we call rı and 122 the composing and ra the compositionally defined relation. In essence, this pattern defines a relation ra that describes the start and end entities of a path X 3 Y "3 Z. Since any two relations 71 and r2 can instantiate the body of a compositional definition pattern, any such pair may produce new compositionally defined relation Ta. Interestingly. compositional definition translates analogously into the virtual triple space: Intuitively, this means that the embeddings of any two relations 71 and r2 define for ra convex region which we call the compositionally defined region that captures ri (X, X Y) A rY, Z) + [X Z). leading to Theorem 5.3 (proven in Appendix E Based on this insight, ExpressivE captures compositional definition patterns by embedding the compositionally defined relation with the compositionally defined region, defined by the relation embeddings of 1ı and r2. We have formally proven that
ExpressivE can capture compositional definition in Theorem 5.4 (see Appendices Fland and G
Theorem 5.3 Let F2, Fd E R be relations, $1, 82 be their ExpressivE embeddings, and assume rx Y) Ar, Z) + ra(X, Z) holds. Then there exists region sa in the virtual triple space R such that (i) 81, 82, and 8a capture ri (X, Y) A rY, (,2) 7) < ra( X, 7)) and (ii) sa is convex.
General Composition. In contrast to compositional definition, general composition ri (X, Y) A ZY = (x 2) does not specify the composed relation r3 completely. Specifically, general composition allows the relation r3 to include additional entity pairs not described by the start and end entities of the path X 24, Y 22, Z. Therefore, to capture general composition, we need to combine hierarchy and compositional definition. Formally this means that express general composition as: (ri (X, Y) A r2 Z) + ra(X, 2), ra(X.Y) Y) + (x(, Y) We have proven that ExpressivE can capture general composition in Theorem 5.4 (see Appendices F and G for the full proofs).

---

Published as a conference paper at ICLR 2023
Theorem 5,4 ExpressivE captures compositional definition and general composition.
We argue that hierarchy and general composition are very tightly connected as hierarchies are hidden within general composition. If. for instance, 71 were to represent the relation that solely captures self- loops, then the general composition r (x, Y) r2 (Y. Z) = r3 r Z) would reduce to a hierarchy r2 (X, = (a Y). This hints at why our model is the first to support general composition, as ExpressivE can capture both hierarchy and composition jointly a single embedding space.
Key Properties. ExpressivE's way of capturing inference patterns has several interesting implications:
1. We observe that ExpressivE embeddings offer intuitive geometric interpretation: there is a natural correspondence between (a) relations in the KG - and - rregions (representing mathematical relations) in the virtual triple space, (b) relation containment, intersection, and disjointness in the KG and region containment, intersection, and disjointness in the virtual triple space, (c) symmetry, anti-symmetry, and inversion in the KG and - symmetry, anti-symmetry, and reflection in the virtual triple space, (d) compositional definition in the KG and the composition of mathematical relations in the virtual triple space.
2. Next, we observe that ExpressivE captures general composition pattern if the hyper- parallelogram the pattern's s head relation subsumes the compositionally defined region defined by its body relations. Thereby, ExpressivE assigns a novel spatial interpretation to general composition patterns, generalizing the spatial interpretation that is directly provided by set-theoretic patterns such as hierarchy, intersection, and mutual exclusion.
3. Finally, capturing general composition patterns through the subsumption of spatial regions allows ExpressivE provably capture composition patterns for /-N, N-7, and N-N relations. We provide further empirical evidence to this in Appendix
6 EXPERIMENTAL EVALUATION AND SPACE COMPLEXITY
In this section, we evaluate ExpressivE the standard KGC benchmarks WNI8RR (Dettmers et al. 2018) and FB15k-237 (Toutanoaa & Chen 2015) and report SotA results, providing strong empirical evidence for the theoretical strengths of ExpressivE. Furthermore, we perform an ablation study on ExpressivE's parameters to quantify the importance of each parameter and finally perform relation-wise performance comparison on WN18RE to provide an in-depth analysis of our results.
6.1 KNOWLEDGE GRAPH COMPLETION
Experimental Setup. As in Abboud et al. 2020). we compare ExpressivE to the functional models TransE (Bordes et al., 2013) and RotatE (Sun et al. 2019), spatial model BoxE (Abboud et al. 2020). and bilinear models Mist (Yang et al. 2015a). ComplEx (Trouillon et al. 2016). and TuckER (Balazevic et al. 2019). ExpressivE is trained with gradient descent for up to 1000 epochs. stopping the training if after 100 epochs the Hits @ 10 score did not increase by at least 0.5% for WNI8RR and 1% for FB 237. We use the model of the final epoch for testing. Each experiment was repeated 3 times to account for small performance fluctuations. In particular, the MRR values fluctuate by less than 0.003 between runs for any dataset. We maintain the fairness of our result comparison by considering KGEs with a dimensionality d < 1000 (Balazevic al., 2019: Abboud al. 2020). To allow direct comparison of ExpressivE's performance and parameter efficiency to its closest functional relative RotatE and spatial relative BoxE, we employ the same embedding dimensionality for the benchmarks as RotatE and BoxE. Appendix lists further setup details, hyperparameters, libraries (Ali et al., 2021), hardware details, definitions of metrics, and properties of datasets.
Table 2: Model sizes of ExpressivE, BoxF, and RotatE models of equal dimensionality.
Benchmark
Dimensionality
ExpressivE
BoxE
RotatE
WN18RR
500
467MB
930MB
930MB
FB 15k-237
1000
366MB
687MB
687MB
Space Complexity, For a d-dimensional embedding, RotatE and BoxE have (2 E + R)),, whereas ExpressivE has ([ + 6) Rl)d parameters, where E is the number of entities and R the number
7

---

Published as a conference paper at ICLR 2023
0.016) ExpressivE almost halves the number of parameters for d-dimensional embedding compared to BoxE and RotatE. Table[]lists the model sizes of trained ExpressivE, BoxE, and RotatE models of the same dimensionality, empirically confirming that ExpressivE almost halves BoxE's and RotatE's sizes.
of relations. Since R << E in most graphs, (e.g.. FB15k-237: R
Table KGC performance of ExpressivE and SotA KGEs on FB15k-237 and WN18RE The table shows the pest-published results of the competing models per family, specifically: TransE and RotatE (Sun et al. 2019). BoxE (Abboud et al.] 2020). DistMult and ComplEx (Ruffinelli et al. 2020
aang
al.
bb), and TuckER (Balazevic al. 2019).
Family
Model
WN18RR
FB15k-237
Bilinear Func. Spatial
H@ @
H@3
H@ 10
MRR
H@
H@3
H@ 10
MRR
Base ExpressivE
.464
.522
.597
.508
.243
.366
.512
.333
Func. ExpressivE
.407
.519
.619
.482
.256
.387
.535
.350
BoxE
.400
.472
.541
.451
.238
.374
.538
.337
RotatE
.428
.492
.571
.476
.241
.375
.533
.338
TransE
.013
.401
.529
.23
.233
.372
.531
.332
DistMult
.531
.422
.531
.343
ComplEx
.547
.475
.536
.348
TuckER
.443
.482
.526
.470
.266
.394
.544
.358
Benchmark Results. We use two versions of ExpressivE in the benchmarks, one where the width parameter dhe learned and one where dh = 0, called Base ExpressivE and Functional ExpressivE E. Tables 2 and BandBrevver reveal that Functional ExpressivE, with only half the number of parameters of BoxE and RotatE, performs best among spatial and functional models on FB15k-237 and is competitive with TuckER, especially in MRR. Even more, Base ExpressivE outperforms all competing models significantly on WN18RR. The significant performance increase Base ExpressivE on WN18RR is likely due to WN 8RR containing both hierarchy and composition patterns in contrast FB FB15k-237 (similar to the discussion of Abboud et al. (. We will empirically investigate the reasons for ExpressivE's performances on FB 15k-237 and WNISRR in Section 6.2 and Section 6.3
Discussion. Tables and reveal that ExpressivE is highly parameter efficient compared to related spatial and functional models while reaching competitive performance on FB 5k-237 and even new SotA performance on WN18RR, supporting the extensive theoretical results of our paper.
6.2 ABLATION STUDY
This section analyses how constraints on ExpressivE's parameters impact its benchmark performances. Specifically, we analyze the following constrained ExpressivE versions: (1) Base ExpressivE. which represents ExpressivE without any parameter constraints, (2) Functional ExpressivE, where the width parameter dhe of each relation r; zero, (3) EqSlopes ExpressivE, where slope vectors are constrained to be equal i.e., ht ht for any relations r; and rk: (4) NoCenter ExpressivE, where the center vector cht of any relation r; is zero, and (5) OneBand ExpressivE, where each relation is embedded by solely one band instead of two i.e., OneBand ExpressivE captures triple ri ri(en, ex) to be true its relation and entity embeddings only satisfy Inequality
Table Ablation study on ExpressivE's parameters.
Model
WN18RR
FB15k-237
H@]
H@3
H@ 10
MRR
H@
H@3
H@ 10
MRR
Base ExpressivE
.464
.522
.97
.508
.243
366
.522
333
Func. ExpressivE
.07
.519
.619
.42
.256
.387
.535
.350
EqSlopes ExpressivE
.254
.155
528
.353
.237
.361
.100
.328
NoCenter ExpressivE
.457
.514
.591
.501
.224
.349
.494
.314
OneBand ExpressivE
.435
.480
.538
.470
.230
.352
.491
.318
8

---

Published as a conference paper at ICLR 2023
Ablation Results. Table 4 provides the results of the ablation study on WN18RR and FB15k- 237. It reveals that each component of ExpressivE is vital as setting all slopes rhe to be equal (EqSlopes ExpressivE) or removing the center tht (NoCenter ExpressivE), width the (Functional ExpressivE), band (OneBand ExpressivE) results in performance losses at least one benchmark. Interestingly, Functional outperforms Base ExpressivE on FB15k-237. Since Functional ExpressivE sets dhe 0, the relation embeddings reduce from papper-pralleeogran to function. Intuitively, this means that Functional ExpressivE loses the spatial capabilities of Base ExpressivE such as the ability to capture hierarchy, while it maintains functional capabilities, such the ability capture compositional definition. Table 4 reveals that the performance of ExpressivE increases when we remove its spatial capabilities, depicted by the performance gain of Functional over Base ExpressivE. This result hints at FB1 1.5k-33 not containing many hierarchy patterns. Thus, FB1 2 cannot exploit the added capabilities of Base ExpressivE, namely the ability to capture general composition and hierarchy. In contrast, the significant performance gain of Base ExpressivE over Functional ExpressivE on WN18RR is likely due to WNI8RR containing many composition and hierarchy patterns (AAbboud et al. 2020), cf. Appendix 12
exploiting Base ExpressivE's added capabilities.
6.3 WN18RR PERFORMANCE ANALYSIS
This section analyses the performance of ExpressivE and its closest spatial relative BoxE (Abboud al. 2020) and functional relative RotatE (Sun et al. 2019) on WNI8RR. Table Dists the MRR of ExpressivE, RotatE, and BoxE for each of the 11 relations of WN1 WN18RR. Bold values represent the best and underlined values represent the second-best results across the compared models.
Table 5: Relation-wise MRR comparison of ExpressivE, RotatE, and BoxE on WN18RR.
Relation Name
ExpressivE
RotatE
BoxE
member_meree
0.233
0.199
0,226
hypernym has jus__artt
0.189
0.162
0.159
0.198
0.187
0.168
instance _yyeeryym
0.352
0.326
0.425
synset dorertddomnnnnmee domainntopiccoooeo of
0.363
0.384
0.323
0.288
0.333
0.360
0.123
0.188
0.189
also_sec derivationallly_rlltee from similar_ta to verb group
0.649
0.631
0.517
0.956
0.943
0.902
1.000
1.000
1.000
0.972
0.843
0.876
Results. ExpressivE performs very well on many relations, where either only BoxE or only RotatE produces good rankings, empirically confirming that ExpressivE combines the inference capabilities of BoxE (hierarchy) and RotatE (compositional definition). Additionally, ExpressivE does not only reach similar performances as RotatE and BoxE if only one of them produces good rankings but even surpasses both of them significantly on relations such as verb __ropp also see, and hypernym. This gives strong experimental evidence that ExpressivE combines the inference capabilities of func- tional and spatial models, even extending them by novel capabilities (such as general composition), empirically supporting our extensive theoretical results of Section
7 CONCLUSION
In this paper, we have introduced ExpressivE, KGE that (i) represents inference patterns through spatial relations of hyper-pare aapeerpprallelograms. offering intuitive and consistent geometric interpretation of ExpressivE embeddings and their captured patterns, (ii) can capture a wide variety of important inference patterns, including hierarchy and general composition jointly, resulting in strong benchmark performances (iii) is fully expressive, and (iv) reaches competitive performance on FB 15k-237, even outperforming any competing model significantly the performance of ExpressivE on further datasets, particularly focusing on the relation between constrained ExpressivE versions and dataset properties.
WNISRR. In the future, we plan to analyze

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We have made our code publicly available in a GitHub repository It contains, in addition to the code of ExpressivE, setup file to install the necessary libraries and ReadMe.md file containing library versions and running instructions to facilitate the reproducibility of our results. Furthermore, we have provided all information for reproducing our results including the concrete hyperparameters. further details of our experiment setup, the used libraries (Ali et al. metrics, properties of datasets, and more in Appendix M We have provided the complete proofs for our extensive theoretical results in the appendix and stated the complete set of assumptions we made. Specifically, each theorem states any necessary assumption, and each proof starts by listing any property we assume without loss of generality. We have proven Theorem 5.1 in Appendix [
2021). hardware details, definitions of
Theorem 5.3 in Appendix and Theorems 5.2 and [5.4 Appendices a
ACKNOWLEDGMENTS
We are grateful to Maximilian Beck for helpful discussions and feedback. This work has been funded by the Vienna Science and Technology Fund (WWTF) [0044379/VRG188033))
REFERENCES
Ralph Abboud, ismail iIkan Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori. Boxe: box embedding model for knowledge base completion. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Farahnaz Akrami, Mohammed Samiul Saeef, Qingheng Zhang, Wei Hu, and Chengkai Li. Re- alistic re-evaluation of knowledge graph completion methods: An experimental study. In Pro- ceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIG- MOD '20 pp. 1995-2010, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 450367356. doi: 11144//31144.3380000
http:://t//// /0tp::::////0...000000.1.11
331 08184644 .115443338555 3380599
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Sahand Sharifzadeh, Volker Tresp, and Jens Lehmann. PyKEEN 1.0: Python Library for Training and Evaluating Knowledge Graph Embeddings. Journal of Machine Learning Research, 22(82):1 -6, 2021.
Ivana Balazevic, Carl Allen, and Timothy M. Hospedales. Tucker: Tensor factorization for knowledge graph completion. CoRR, abs/1901 00959099, 2019.
Kurt D. Bollacker, Robert P. Cook, and Patrick Tufts. Freebase: A shared database of structured general human knowledge. In Proceedings of the Twenty-Secone AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pp. 1962-1963 AAAI Press, 2007.
Antoine Bordes, Nicolas Usunier, Alberto Marefa-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), 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, pp- 2787-2795, 2013.
Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua. Unifying knowledge graph learning and recommendation: Towards better understanding user preferences. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, WWW '19, pp. 151-161, New York, NY, USA, 2019. Association for Computing Machinery.
Muhao Chen and Carlo Zaniolo. Learning multi-faceted knowledge graph embeddings for natural language processing. In Proceedings of the Twenty-iixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 5169-5170, 2017.
10

---

Published as a conference paper at ICLR 2023
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), Proceedings of the Thirty-Second AAAI Conference 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, pp. 1811-1818. AAAI Press, 2018.
Laura Dietz, Alexander Kotov, and Edgar Meij. Utilizing knowledge graphs for text-centric infor- mation retrieval. In Kevyn Collins-Thompseee Thompson, Qiaozhu Mei, Brian D. Davison, Yiqun Liu, and Emine Yilmaz (eds.). The s1 International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR 2018, Ann Arbor, MI, USA, July 08-12, 2018, pp. 1387-1390. ACM, 2018.
Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M. Suchanek. Fast rule mining in ontological knowledge bases with amie+. The VLDB Jourmal, 24(6):007-730, dec 2015. ISSN 1066-8888. doi: 10. 10:1007/40078--055-0094441 URL /ttp:http.::/ol..r///00.00 100778-015-0300
Luis Antonio Galárraga, Christina Teffiouii, Katja Hose, and Fabian Suchanek. Amie: Association rule mining under incomplete evidence in ontological knowledge bases. In Proceedings of the 22nd International Conference World Wide Web, WWW '13 pp. 413-422, New York. NY, USA, 2013. Association for Computing Machinery. ISBN 978 155320355.. doi: (D.1145/2488388.24888888
URL wwtp:ttpps//. //doi org/ 10. 11 45/ 2882288888888 8w0.8888844888888 2488425
Chang Gao, Chengjie Sun, Lili Shan, Lei Lin, and Mingjiang Wang. Rotate3d: Representing relations as rotations in dinee-dimensional space for knowledge graph embedding. In Mathieu d' Aquin, Stefan Dietze, Claudia Hauff, Edward Curry, and Philippe Cudré-Mauroux (eds.), CIKM '20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020, pp. 385-394, ACM, 2020.
Katsuhiko Hayashi and Masashi Shimbo. On the equivalence of holographic and complex embeddings for link prediction. In Proceedings the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 554-559, Vancouver, Canada, July 2017. Association URL //atsss:/cct acc antho logy
for Computational Linguistics. doi: 10. 1/153////11172208..
org/P17-2083
Frank I.. Hitchcock. The expression of tensor or a polyadic sum of products. Journal of Mathematics and Physics, 6(1-4):164-19) 1927.
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), ), Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 4389- 2018
Diederík Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Alexandre Lacoste, Alexandra Luccioni, Victor Schmidt, and Thomas Dandres. Quantifying the carbon emissions of machine learning. arXiv preprint arXiv:1910.09700 2019.
Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smoothing the geometry of probabilistic box embeddings. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Haonan Lu and Hailin Hu. Dense: An enhanced non-abelian group representation for knowledge graph embedding. CoRR, Abs/2008.04544, 2020.
George A. Miller. Wordnet: A lexical database for english. Commun. ACM, 38(11):39-41, nov 1995.
11

---

Published as a conference paper at ICLR 2023
Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. Learning attention- based embeddings for relation prediction in knowledge graphs. In Anna Korhonen, David R. Traum. and Lluís Märquez (eds.). Proceedings of the 57th Conference of the Association for Computational Linguisties, ACI. 2019, Florence, Italy July 28- August 2, 2019, Volume I: Long Papers, pp. 4710-4723. Association for Computational Linguistics, 2019.
Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems
30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6338 6347, 2017. URL htt.httss:://prrceeeeeie http://oooceennnnnnn..errrrrrrre neurips cc/ 2017 htw.h/aahhhhaaaaeaaaa
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. three- way model for collective learning on multi-relational data. Lise Getoor and Tobias Scheffer (eds.), Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 July 2, 2011, pp. 809-816. Omnipress, 2011.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowledge graphs. In Dale Schuurmans and Michael P. Wellman (eds.), Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 1955- 1961. AAAI Press, 2016.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You CAN teach an old dog new tricks! on training knowledge graph embeddings. In 8th International Conference on Learning Representa- tions, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. Openkeview.net, 2020.
Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. Reasoning with neural tensor networks for knowledge base completion. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013, Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 926-934, 2013.
Sandeep Subramanian and Soumen Chakrabarti. New embedded representations and evaluation protocols for inferring transitive relations. In Kevyn Collins- Dellins-Thompson, Qiaozhu Mei, Brian D. Davison, Yiqun Liu, and Emine Yilmaz (eds.), The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR 2018, Ann Arbor, MI, USA, July 08- 12. 2018, pp. 1037-1040. ACM, 2018
Zhiqing Sun, Zhi-Hong Deng, Jian Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning. ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2071-2080. JMLR.org, 2016.
Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3): 279-311, 1966.
12

---

Published as a conference paper at ICLR 2023
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. In Iryna Gurevych and Yusuke Miyao (eds.). Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Melbourne, Australia, July 15-20, 2018, Volume Long Papers, pp. 263-272. Association for Computational Linguisties, 2018.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and upplications. IEEE Transactions on Knowledge and Data Engineering, 29(12): 3724-2743, 2017.
Robert West, Evgeniy Gabrilovich, Kevin Murphy, Shaohua Sun, Rahul Gupta, and Dekang Lin. Knowledge base completion via search-based question answering. In Proceedings of the 23rd International Conference on World Wide Web, WWW 14, pp. 515-526. New York, NY, USA, 2014. Association for Computing Machinery.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015a.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the Third International Conference Learning Representations, ICLR, 2015b.
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.). Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 2731-27444 2019.
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. Variational reasoning for question answering with knowledge graph. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.). Proceedings of the Thirty-Secona 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, pp.
AAAI Press, 2018.
13

---

Published as a conference paper at ICLR 2023
A OVERVIEW OF THE APPENDIX
This appendix contains detailed proofs, analyses, and descriptions of our experimental setup. Sec- tion B gives an overview of the used notations. Section[[speciferr the complete formal definitions for all used terms. Section D contains detailed proof of Theorem 5.1 i.e., showing that ExpressivE fully expressive. Section E proves Theorem [.3] developing technical machinery to support further proofs in this appendix. FentionnsFanGpppaae 5.4 proving ExpressivE's inference capabilities. [aatiinn[orovee that ExpressivE can capture more than one step composition. Section provides additional empirical evidence for ExpressivE's theoretical capabilities, specifically investigating ExpressivE's performance stratified by cardinalities, captured composition patterns, and reasoning steps. Section explores the main goals and properties of ExpressivE's s distance function introduced in Section 4 Section K further discusses ExpressivE's functional and spatial nature, comparing ExpressivE's inference capabilities with those of spatial and functional models. Section [ further analyses the trade-off discovered in Section 6 between high expressive power and low degrees of freedom. Finally, Section Miciion[M]a provides further details on experimental setup, benchmark datasets, and evaluation metrics.
additional propositions and proofs for Theorems 5.2
Jectionnexploress
B NOTATION
In this section, we give brief overview of the most important notations we use:
non-bold symbols represent scalars
bold symbols represent vectors, sets or tuples
represents vector of solely zeros (the same semantics apply 0.5, 1, and 2)
Z represents the elementwise division operator
represents the elementwise (Hadamard) product operator
represents the elementwise greater or equal operator
represents the elementwise greater operator
3 represents the elementwise less or equal operator
... represents the elementwise less operator
x! represents the elementwise absolute value
represents the concatenation operator
v(j) rrepreeent the j-th dimension of a vector v
C FORMAL DEFINITIONS
In this section, we formally introduce the notions capturing a pattern an ExpressivE model that informally discussed in Section [ Furthermore, will introduce some additional notations, which will help us simplify the upcoming proofs and present them intuitively.
Knowledge Graph. A tuple (G, E, R) is called knowledge graph, where R is finite set of relations, E is a finite set of entities, and G C E x R x is finite set of triples. W.l.o.g.. we assume that any relation is non-empty since assigning an empty hyper-parallelogram an empty relation would be trivial, just adding unnecessary complexity to the proofs.
ExpressivE model. A tuple M (E, o 8, p) is called ExpressivE model, where C 2 is finite of entity embeddings, or 22 is finite of center embeddings. 2nd is finite of width embeddings, and p C 23 is finite set of slope vectors.
Linking Embeddings to KGs. An ExpressivE model and KG linked via the following assignment functions: The entity assignment function f. + e assigns an entity embedding en E to each entity e, E. Based fa, the virtual assignment function f. E E Rdd defines
14

---

Published as a conference paper at ICLR 2023
for any pair of entities (eh, E E a virtual entity pair embedding fo(e,, = (fe(ee))
fe fe(e))
where represents the concatenation operator. Furthermore, the relation assignment function 2d x 22 x R2d assigns a phyper-arralllograan to each relation rt. In more detail, this means that (ra) = (cht dhe r4 where cf = |c |c]] are two concatenated center embeddings with cf, of E o, where dh (d) (ld))) are two concatenated width embeddings with d'. de E ó, and where r = (r I are two concatenated slope vectors with ri; r E p. Intuitively, (ri defines a hyper paralllaralll in the virtual triple space Rdd as described in Section
fh (r;)) R - R2d
Model Configuration. We call an ExpressivE model M together with a concrete relation assignment function fx a relation configuration m = (M, fx) and it additionally has a concrete virtual assignment function fu, we call it complete model configuration
(M, fr.
Definition of Truth. A triple (e), et) holds in some m, with r. E R and en et E E iff In- equalities [ and 2 hold for the assigned embeddings of h, and r. This means more specifi- cally that Inequalities and 2 need to hold for fuleh, (t) = (fe(ea))lf((())===== ( (enllet) and (chlcc) dh = (dl d)), and r (rfllr?). At an intu- itive level, this means that a triple ri(en, ex) is true in some complete model configuration m iff the virtual pair embedding (e ex) of entities en and e₁ lies within the hyper-paralleloggam of relation defined by (ri).
fir (che, dhe r with ct
Simplifying Notations. Therefore, to simplify the upcoming proofs, we denote with fulen, et) e frr that the virtual pair embedding fulen, et) E R2dd of an entity pair (ex, eq) E E x E lies within the hyper-paralleeograa
fr (r:) C IR2d x R2d 2d of some relation r; E Rn the virtual triple space. Accordingly, for sets of virtual pair embeddings P := (fu(Ch, ( (e(ee, et,)), we denote with P C (r;) that all virtual pair embeddings of P lie within the hyper-parallelogran of the relation rÜ Furthermore, we denote with (e Eq) & (r,) that a virtual pair embedding fo ee) does not lie within the hyper- aaper-parallelogran of a relation ri and with P & (ri) we
denote that an entire set of virtual pair embeddings P does not lie within the apper-paraleelogamn of a relation r;-
Capturing Inference Patterns. Based on the previous definitions, we define capturing patterns formally: A relation configuration m, captures a pattern yb exactly if for any ground pattern ΦB, A A... dB... = Φи within the deductive closure of to and for any instantiation of fe and fo the following conditions are satisfied:
if ΦH is a triple and if mn captures the body triples to be true - i.e., fo (args((B,)) fn. (rel ))...... fo flo (args( E fr (rel(()....)) - then m, also captures the head triple to be true- i.e., (o(r))((6)) )) E (rel(()))
if Φb I. then mn captures at least one of the body triples to be false i.e. there is some j E (1....,m) m such that fo ((rrgs((0))) )) & (rel((p))).
where args() is the function that returns the arguments of triple and rel() the function that returns the relation of the triple. Furthermore, a relation configuration m& captures a pattern ti exactly and exclusively if (1) m, exactly captures vi and (2) m, does not capture any positive pattern e (i.e., o E {symmetry, inversion, hierarchy, intersection, composition) }) such that &b H 6 except where the body of Φ is not satisfied over mi,.
Discussion. In the following, some intuition of the above definition of capturing a pattern is provided. Capturing pattern exactly is defined straightforwardly by adhering to the semantics of logical implication á = ΦB = ΦH, i.e., relation configuration mn needs to be found such that for any complete model configuration m over mp the body Φn of the pattern is satisfied, then its head du can be inferred.
Capturing a pattern exactly and exclusively imposes additional constraints. Here, we do not solely aim at capturing pattern but additionally showcasing that a pattern can be captured independently from any other pattern. Therefore, some notion of minimality/cxclusivenss of pattern is needed. As in Abboud et al. (020)), we define minimality by means of solely capturing those positive patterns ó that directly follow from the deductive closure of the pattern v except for those ø that are captured trivially, i.e., except for those ò where their body is not satisfied over the constructed mn-
As presented in Section S
we can express any supported pattern by means of spatial relations of the corresponding relation hyper-paraleeoogram in the virtual triple space. Therefore, we formulate
15

---

Published as a conference paper at ICLR 2023
exclusiveness intuitively the ability to limit the intersection of syper-parallelograms to only those intersections that directly follow from the captured pattern & for any known relation T2 E R. which is in accordance with BoxE's 's notion of exclusiveness (Abboud et al. 2020).
Note that our definition of capturing patterns solely depends on relation configurations. This is vital for ExpressivE to be able to capture patterns in a lifted manner, i.e., ExpressivE shall be able to capture patterns without the need of grounding them first. Furthermore, being able to capture patterns in lifted way is not only efficient but also natural as we aim at capturing patterns between relations. Thus it would be unnatural if constraints on entity embeddings were necessary to capture such relation-specific patterns.
As outlined in the previous paragraphs, our definition is in accordance with the literature, focuses on efficiently capturing patterns, and gives us formal foundation for the upcoming proofs, which will show that ExpressivE can capture various logical patterns.
D PROOF OF FULLY EXPRESSIVENESS
In this section, prove Theorem 5.1 We will show by induction that ExpressivE is fully expressive. We will first only consider self-loop- free triples, i.e., triples of the form ry re(e,, C₁) with ej eg E E, ry E R and j + k and later remove unwanted self-loops from the constructed model configuration.
Since our proof is highly technical, we will first give some general intuition and then formally state our proof. In the base case, we consider an ExpressivE model that captures the complete graph G over the entity vocabulary E and the relationship vocabulary R, i.e., the graph that contains all triples from the universe. In the induction step, we prove that we can adjust our ExpressiVE model make any arbitrary self-loop-free triple of G false while maintaining the truth value of any other triple in the universe.
In the induction step, we make triples re(ey, et)) false by translating the entity embeddings of ej and eg such that a syper-arralllograae can separate pairs of entity embeddings that shall be true from those that shall be false. Afterward, we translate and shear r;'s hyper- peper-paralleeogram to match such separating shape.
Finally, after the induction step. we add separate dimension for any possible self-loop, i.e., triple of the form ri (e;; e,) such that we can make any self-loop false. Thereby, we show that ExpressivE can make any triple false and thus that ExpressivE can capture any graph G over R and E.
Our proof shares some common ideas with the fully expressiveness proof of BoxE (Abboud et al., 2020). yet differs dramatically in many aspects. BoxE embeds relations with two axis-aligned boxes and entities with two separate embedding vectors, which greatly simplifies the fully expressiveness proof of BoxE, as the two entity embeddings are independent of each other. This grants BoxE some flexibility for adapting model configuration yet imposes substantial restrictions, such as that BoxE cannot capture any notion of composition patterns. Our model does not have these restrictions and uses only one embedding vector per entity instead, pushing the complexity of our model to the relation embeddings by representing relations however, has the consequence that we cannot casily change entity embeddings without moving and sheering relation embeddings as well when we want make solely one triple false and preserve the truth value of any other triple. In the following proof, we will explain the complex adjustment of relation embeddings and many more novel aspects of our proof in more detail.
hyper-parallelogram in the virtual triple space. This,
We start our proof by making the following assumptions without loss of generality:
1. Any relation r; E R. and entity ej E E is indexed with 0 < |R| 1 and 0 < < E 11
2. The dimensionality of each relation and entity embedding vectors is equal to E * R Furthermore, v(i,,) represents the dimension i |E| + of the vector v. Intuitively, the dimensions of v1,,, o),..., vii. E corresponds to the dimensions reserved for relation
Tt-
3. The slope vectors of relation ri e are positive, i.c.. r rf > 0.
4. Any entity embedding is positive, i.e., for any entity 6 E E holds that e 0.
5. For any pair of entities Cky Cbg E E holds that ex, (i, km) 2 ek (i, kn) m, with >
16

---

Published as a conference paper at ICLR 2023
Building these assumptions, prove fully expressiveness by induction as follows:
Base Case, We initialize graph as the whole universe over and R and construct a complete model configuration
(M, fn. fe) with dimensionality E R such that G' is captured and all
assumptions are satisfied. Concretely, we specify for any dimension (i, k1) with 0 I S [ - and
0 S k1 I E 1 the embedding values of entity embeddings with index h1 to set Ck₁ (i. k1) =
and with index 1₂ * k to Ck2 (t, k1) = 1. Furthermore, we specify for any dimension (i, k) with 0 S R and 0 <
E the embedding of relation r to c
(i
r (i, k) 1, (i,
and d k)) k)) 4. As can be shown easily the constructed
complete model configuration satisfies all assumptions and makes any triple over R and E true.
Note that in particular, any self-loop is also captured be true in the constructed complete model configuration.
Induction step. In the induction step, we adjust the entity and relation embeddings of the complete model configuration such that single triple r. re ex) is made false without affecting the truth value of any other triple within the graph G. We denote any adjusted embedding with an asterisk v and the old value of the embedding with and perform the following adjustments:
1. Increase any slope vector ri (i, k) == (i, k) + Art with Ar > 0 such that:
ey k)
kb) c (i, Arim S - di (1, k)
2. Since (i, k) is by assumption the largest value in dimension (i, k), we can specify the following values:
Artur Artex(i,
Ar. == (ri((x(i,k)) m)
with Ar.hh < Armer.
3. Using this definition, we increase all entity embeddings eg with jr + j in dimension (i, R)) by:
c)((t,))==e)(( Ar.
4. Furthermore, we increase all entity embeddings ej with j' j in dimension (1, k) by:
e Armes
5. For any relation with index ب i', we adjust any head band in dimension (i, by moving its center downwards and growing the band upwards. This means formally that we update the following embeddings:
= (i, + Armaz
d (i, = (t, k) +
d (1,k) = (i, - (i, Mar mar
2
6. We adjust any tail band in dimension (i, k) by moving its center downwards and growing the band upwards. This means formally that we update the following embeddings:
8 (i, + Armez
(1,kk) (i,kk)
(7,kk) = (i,))))) - r/ (i, A) mar 8
2
17

---

Published as a conference paper at ICLR 2023
7. For any relation with index i, adjust any head band in dimension (i. k) by moving its center downwards and growing the band upwards. This means formally that we update the following embeddings:
= (Art + ())r Armun
di (1, k) = (i, +
(i, k)) = (i, Art mar -ri(i, Ar maa
2
In the induction step, we adjust the slope vectors T. the entity embeddings (Step 2 and the width and center embeddings (Step Intuitively, by changing the slope vector of relation hyper- parallelograms, we sheer the hyper-parallelograms Furthermore, we translate any desired entity embeddings more than the undesired entity embedding of e, This allows us to draw a separating ryper-parallelogeen between the point defined by (ej, cx) and any other pair of entities that shall remain within relation r;. Finally, we must move the sheered papee--prallelograms into the correct position and stretch it to make all desired triples true.
Our next goal is to show this behavior formally. We will first show that the initially true triple Ce(e).e)) C&) ) is false, then continue by showing that the truth value of any other triple is preserved.
Since the induction steps perform only adjustments in dimension (i, k), we only have to consider the dimension (i, k) for any embedding vector in the following inequalities. Please note that to state the inequalities concisely, we have omitted the notation (i, k) from any embedding vector v in the following incqualities. For instance, will denote (i, k) with rf henceforth.
Let == (Ar: + Ar) + Armer then we can show that our induction step makes ri(ej, ex) false as follows:
ej rfc ct
Arim
S
-
(4)
ej ee - ct + Arto - Armaz Art Armar Art Armax
r Ar + +r! Ar.
8
d
(5)
2
2
Cj Artb (r) Art)(ex + Artuar
(c
Art Armax
(6)
r Ar Armman
- (d
+ 2
2
ej r e
C < - d
(7)
Inequality 4 follows directly from Induction Step I Next, in Inequality 5 we add many terms that
eliminate each other and apply Arthh - Arrnax (rt m) - Artex AmAr.. Finally, in Inequality 6 we restructure the terms such that we can substitute the terms for the adjusted embedding vectors defined in Steps] 17 Through this substitution,
obtain Inequality 7 which reveals that the adjusted embeddings e ex do not lie within the adjusted hyper-paran syper-parallelogram of relation r;. Therefore, we have shown that the adjustments of the complete model configuration listed in Steps have made the triple ri(e, ex) false, as required.
Next, we need to show that the truth value of any other self-loop-free triple re (e ew) with j' o k' is not altered after the induction step. We start by showing that any triple (e (xr) that is true in m remains true after the induction step. Since what follows is highly technical proof, we give some intuition now. We make case distinction of any possible true triple in G and perform the following steps. First, we assume that the triple is true and therefore instantiate Inequalities [and] with the embeddings prior to the induction step. Note that it is solely necessary to consider Inequality []] as the proofs work vice versa for Inequality 2 Thus, we solely consider Inequality [ henceforth Next, we add terms that eliminate each other and adjustment terms such that we can substitute our inequality with the adjusted embedding values v*. Finally, we show that Inequality [ is satisfied for the adjusted embedding values. Note that Inequality []] defines two inequalities, specifically en - ct rf @ e, 3 di and e,, - ci r @ e, m -dp Therefore, we denote with (<) the proof for the first inequality and with (>) the proof for the second inequality. Thereby, will show that if
18

---

Published as a conference paper at ICLR 2023
assume the triple ry(ey, (et)) to be true in the complete model configuration prior to the induction step, we can follow that ry (ey', exr) stays true after the adjustments of the induction step. To provide the complete formal side of our proof, we consider the following 12 cases:
1. Case i' = =, = j.kk' = j.k' *A #k: k:
(<) Let + + Artua and let a= (Armar - (1 - - -errrrArd r!Ar"
Note that is positive since a Ar,m + Artuar holds. Therefore, perform the following transformations:
Ej reej c/ S di
(8)
ej r c - di
(9)
oj + Arth (rf + Art) + Ar
(c Ar Armee
(10)
r Ar mav 22 S d + 2
oj r ej
4 h+
< d h
(11)
Let a == (Armmex -Arth) (Ar) +r²) Arah Armar and let
Ar)
Armax Note that a is positive since (1) a = mAri(Ar) + + 1), (2) we initialize r in the
base case to in any dimension and (3) any induction step may only increase rf. Therefore, can perform the following transformations:
ej
riej
C
(12)
ej riej
c
h
+
8
8
d
(13)
2
2
oj Ar (rf Art) + Arth))
(c Art mar
(14)
r Ar
mar
mar
(d + 2
e r ej
44 2 d h*
(15)
2. Case 1' i,j' # -
As can be seen easily this case describes the triple r.(e,, ex), which shall be made false in the induction step. We have shown that the induction step changes the triples truth value to false in Inequalities and therefore omitted the case here.
3. Case i' = i, j,k + j.k' 4 l:
(<) Let s = (Ary + Ar:m + Ar and let == Artew + s - Artth Note that is positive since a Ari + m( + Art + r()) holds. Therefore, we can perform the following transformations:
ej riew ct < di
(16)
ej rfew ci a ArtArmaa ArtArmar + Ar/ maz r Ar Anmoz < di
(17)
ej+ + Arib - (r) + Art)(ew + Armaz)
(c) ArArmma
(18)
r Dr m
mar
< d
2
e - r e
h
< d
(19)
19

---

Published as a conference paper at ICLR 2023
(>) Let := Arth Arjew and let = (Ar) + Ar)m Armur Note that a is positive
since Arp 2 Arjew holds. Therefore, we can perform the following transformations:
ej - -ee cf 2
d
(20)
ej - new ci Ar mar
Armar + ArAraaz
r Ar mar
8
2
-
(21)
2
2
ej + Arp0 - (rf + (rw)(ew + Arthar)
- (c Art Arman
r Amaa
2
(d.
9
(22)
2
2
0j r eid
C 2 dh
(23)
4. Case 1/
+::
(<) Leta Ar and let 8 : (Ar! + Arr) since we initially assumed ej > 0 and since assumed in Step 1 Art > 0. Therefore, we can perform the following transformations:
+ Armua Note that a is trivially positive
ej' Mee h S dh
(24)
e -reee ci - a Art A mar
A Ar.ar
mar r Armar
(25)
Ar maz + 8 8 85885 dh
eg + Armea - (rt + (ri) + Arth)) - (c Ari Armmn
(26)
+ Ar
< th +
8
2
2
9 r cj
c
h+
<
d:
(27)
(>) Let a = Armea - Arie, + Arim(Ar) + r() and let 8 = ( + r Ar + Armar.
Note that is positive since Armar Arjej 0. Therefore, we can perform the following transformations:
e---reep - c 2
dx
(28)
ey ey-riee - c/ ArA A Arma r Am.en
(29)
A Ar.aar
2
eg' + Ariuar - (rf + Art)(ez + Arth) - (c
Art Ar
(30)
r Arr max
+
8
2 - (d
+ 8 2
2
Ej + ej
c 2 di
(31)
5. Case /' = -,''' + J, k/ # j.kk'= k:
(<) Lets = (Arg + +r() + Armar and let a a= s Ariex - Armaz Note that a is positive since (rk + m(Ar} + r))) holds. Therefore, we can perform the following transformations:
ey' rfen c
<
di
(32)
max ArtAr max ey' rfer -c²- -a+ Art mar
r A 1
maz
(33)
r A
maz
S d
eg' + Armaaz - - + Arr) + Armar)
(c A Ar maz
(34)
r Arrmau moxt +
< dh
8
2
b r e c
h d
(35)
20

---

Published as a conference paper at ICLR 2023
(>) := (Ar) + rf) + Arquar Using this definition, we can perform the following
transformations:
r c 2
-
di
(36)
ej' reeu- ct + Arman Armar + Ar Ar!
AriAr Aree
(37)
Ar/ r Ar max
2
2
eg + Arquar (rt + (rk) + Art
(c Ar
max
(38)
つ A 1 max
d
8
2
2
cj. r Ck
C/
hx
2
d
(39)
Case 1/ = i, # J, # j, + k:
(<) Let (Ar! + r Ar + Armaaz and let := Armer + Ar/eg. Note that is
positive since a (ex + mm + +r)) holds. Therefore, we can perform the following transformations:
e ree
ch S
di
(40)
eg' new - c/ -a-++a Arj Ar maz + r A max
(41)
r Ar maz
di
eg' + Artaaz - -r] + Art)(ew + Armazz
- (c
Ar
ワ Ar ! max
+
8
< d
(42)
2
2
cÿ r e/
C
h=
d
(43)
(>) a Armar - Artew and let s: = (Ari + Artn m + Armar Therefore, we can perform the following transformations:
e r
c 2 dx
(44)
ey' - -ree ci +a++AriAn maR Ar max + r Ar
Amr
(45)
A 2
d
2
ej' + Arruaz - -ri + (rr) + Arqua)
11 Art Ar
maz
A mar
2
8
2
(d)
+ 2
(46)
ej r e
ch
d
(47)
7. Case il fi,j' = j,k +i,k' = k:
<<) Let s == Arim + Armaar and let a := Art Note that a is positive since a Arim(1 + r2))) holds. Therefore, we can perform the following transformations:
ej -
ej-reee reee - c/ < d:.
(48)
Ej rhen -ch -a + r Armaaz r/y Armar < dh
(49)
ej + Arub. ub r (ex + Armary (c , Armaz + ()) < d +
8
(50)
2
r et c < di
(51)
Let := Ar.e and let s == r Arim + Artea Note that a is trivially positive since A Lb is positive. Therefore, we can perform the following transformations:
21

---

Published as a conference paper at ICLR 2023
e
c 2 - d/
(52)
Ej rrex c + a + Dr mmma
r Ar
max
8 z di
(53)
2
2
ej + Arth th - (ex + Art max
(c ト Ar i
maz
+
2
8
2 - (d + 2
(54)
oj o Ek
cf h+
d. h*
(55)
Case i' -i," +
As can be seen easily this case generates the same inequalities as the previous case, except that k' = k. Therefore, no relevant difference has be considered, which is why we omit this case.
9. Case (i' + i.j' * j.k j. k,k* + k):
(<)
Let := r Am + ArTur. Using this definition we can make the following transforma-
tions:
ey e
cp S
db
(56)
ej' r ej + 8 < d
(57)
Ej' + Armaz rf + Art (c) r Ar.
mar
- h
g
(58)
2
ej r ej
(59)
(>) Let = Armar + r (Armaz - Arr and let 5 == r Ar + Armer Note that a is positive since Armar > Ar Ar Therefore, we can perform the following transformations:
ej' r-j
c
(60)
ej' e
c +a+
h
2 2 d
(61)
ej' + Armaaz mas rr + Ar
(c) r Arman
max
+ 2)
(d
(62)
2
cj r
t*
ej
2
d
(63)
10. Case il i + j, # J k:
<<) Let s == Artm + Armer and let a := 8 Armar, Note that a is positive since Ar/m holds. Therefore, we can perform the following transformations:
Eg' r - c S d
(64)
ej' r eyex c/ aa- Armaz + Armuzz - r Armar + r Armas < <d
(65)
ej' + Armaz (e + Armaz) (ch r Armaa + [g) < dh
+
(66)
2
ey + et
o S di
(67)
(>) Let s Arrrm + Armax and a == Armar, Note that a is trivially positive since Ar. Armar is positive. Therefore, we can perform the following transformations:
e r
Ck
h
2
d
(68)
e r
cy + a + r A Ar r Ar mar
8
2
d
(69)
2
2
ey' + Armax - T (ex + Armmar - (c) - r Ar Max
+
2) 2
8.
+ 8
(70)
e r
t+
ex
c
h+
2 d+t
(71)
22

---

Published as a conference paper at ICLR 2023
11. Case i' + Hi," / j. j.
As can be seen easily this case generates the same inequalities as the previous case, except that k' = k. Therefore, no relevant difference has to be considered, which is why we omit this case.
12. Case i' # i = j,k = j,k' # k:
<<) Let == , Ar + Armur and let Arquaz Ar.hh Note that is positive since Ar.m. Therefore, we can perform the following transformations:
ej B c/. - c
(72)
- r e - d a - - < d
(73)
ej + Art - (e + Art (ch r Ar max + 2 S d
8
(74)
2
ej r cp d:
(75)
(>) Let = Ar + Artuaz and Ar Arimr Note that a is trivially posi- live since we assumed any parameter to be positive. Therefore, we can perform the following transformations:
Ej
r ej
cx d
2
(76)
e k
c
+ a
2 dh
(77)
8''
Cj Artob
re + Art
(cp r Dr :
mar
2 hah
+ 8
2
(78)
ej
t* ej
c
h+
2
di
(79)
We have shown in any of the twelve discussed cases that if a triple ry (ey, with i' + or j' + j or k' A k was true in the model configuration prior to the induction step, then it is still true in the adjusted model configuration after the induction step. Hence, to show that ExpressivE can capture any self-loop-free graph, it remains to show that any triple that was false remains false after the induction step.
To verify that initially false tripe (e ex) remains false we solely need to show that the embeddings of ry', Ey' and ex do not satisfy at least one of the Inequalities or 2 We have to consider the following cases:
1. Case K' * h: Any changes to the dimension v(i, k) do not affect the dimension v(i', R.). Therefore, if (ey' ew) for K' * k was false before the induction step, it remains false after the induction step, we solely alter dimension (i, k).
2. Case K' k, 1' = i: In this case j' + needs hold as the triple r: e4) was initially assumed to be true. We can easily show that in this case any triple remains false as follows:
Let = (Ar: + Ar/mm + Armaz then we can show that our induction step makes (e))
false as follows:
ej' rick c S
di
(80)
ej' riex - cf + (
1 Ar Art
+ r
(81)
< n
e,' Araax_ - (rf + (rr) Armaz
(c+ Art A
max
(82)
r A x
mar
5
d
5 r ex
c
ha
<
dh
(83)
Since we started with the complete graph, any triple that is false was made false by an induction step. We have seen that if we apply our algorithm to make re(eg, ex) false, then Inequality 7 holds.
23

---

Published as a conference paper at ICLR 2023
Since we assume that r,(e),e)) was false prior to the current induction step and Inequality describes how induction steps make triples false, we can follow that Inequality 80 needs to hold prior to this induction step. Next, we add in Inequality [T terms that eliminate each other. Finally, in Inequality [82 we restructure the terms such that we can substitute them for the adjusted embedding vectors deñned in T7 Through this substitution, we obtain Inequality [83] which reveals that the adjusted embeddings of e; and e do not lie within the adjusted hyper-parallelogram of relation Tú. Therefore, we have shown that the adjustments of the complete model configuration stated in Steps 77 preserve the false triples of this case to remain false.
3. Case i' o i: Any changes to the dimension v(i, Ae) do not affect the dimension v(i', k²). Therefore, if Ty (ey ex² for i' # i was false before the induction step, it remains false after the induction step, as we solely alter dimension (i', k).
Hence, we have shown that we can make any self-loop-free triple false in the induction step while preserving the truth value of the remaining triples in G. To show fully expressiveness, it remains to show that we can capture any graph G' even with self-loops. We started our proof in the base case with a complete graph, which means that any self-loop was initially true. Furthermore, we have shown in Inequalities 15 and 72 that any true self-loop remains true after the induction step and that therefore any constructed complete model configuration captures any self-loop to be true. Since there are only [R] E possibilities to generate triples of the form ri(e,, e,,) for any r; E R and e; E and since require just a single dimension where the embedding of the entity pair ej. is outside of r.'s hyper-parallelogee
to make the triple ri (ej, eÿ) false, we can simply add a dimension per self-loop our embeddings, whose sole purpose to exclude one undesired self-loop r((eg, Therefore, ExpressivE can represent any possible graph G in a complete model configuration of O([R] [E]) dimensions, and our model is thus fully expressive in O(R) |E]) dimensions.
E PROOF OF COMPOSITIONALLY DEFINED REGION
In this section, we prove Theorem 5.3 which will serve as further machinery for successive appendices. Since we are going to prove Theorem 5.3 by proving a more specific Theorem, we need to extend the notion of when a compositional definition pattern holds in the virtual triple space first such that we can employ it later in our proof. Definition E describes when a compositional definition pattern holds in dependence of the spatial regions its relations in the virtual triple space. The definition employs the notion of logical implication, i.e., if the body of a pattern is satisfied, then its head can be inferred.
Definition E.1 (Truth of Compositional Definition in the Virtual Triple Space) Let TI (X) A r2 Z) <> ra(X, Z) be a compositional definition pattern over some relations T1, Ta, E R and over arbitrary entities X,Y, E E. Furthermore, let Sh. be a relation assignment function defined over 11 and r2. Moreover, let sa be the spatial region of ra in the virtual triple space. The compositional definition pattern holds for the regions of the relations in the virtual triple space, i.e., for fn (r1), fn(22) and sa, if: (=) for any entity assignment function fo and virtual assignment function fo over fe if fo(X,Y) E fn(ri) and fY 7) the region sa Td- (4) For any entity assignment function fe and virtual assignment function fo over fe if fo(X. Z) is within the region sa Ta, then there exists an entity assignment fY) such
72) E fr((2), then fx(X, Z)) must be within
that f.(X,Y) E (r) and fY, Z) fn (T2).
Recall that Theorem 5.3 (reformulated in the definitions of Appendix C and Definition E.1 states that if ó = rx( A (Y, Z) + ra(X, Z) is compositional definition pattern defined over relations ri, r1, ra E R and if fn a relation assignment function that is defined over rı and r2, then there exists convex region sa for ra in the virtual triple space 2ddd such that & holds for (r1), fn (r2) and &d- In particular, we are not only interested in proving the existence of the compositionally defined region sa, but we will even identify a system of inequalities that describes the shape of sa- Specifically, Theorem E.2 concretely characterizes the shape of 8a, which we prove subsequently.
Theorem E.2 Let rx(X)Y) A (Y = ra(X, Z) be a compositional definition pattern over some relations 72. R and over arbitrary entities X.Y, Z E. Furthermore, let fn. be a relation assignment function that is defined over TT and T2 such that for any E {1, f (r,) (che, dhe rhh) with che = (c)), dhet- (df])d)), and th (r((lr?) Moreover, let
24

---

Published as a conference paper at ICLR 2023
the slope vectors be positive, L... r = 0 for E (1.2). If Inequalities 84 define the region sa of
ra in the virtual triple space, then rı (x,(X, Y) A (Y, & ra(X, Z) holds for fn f1((2) and
a in the virtual triple space.
(x (x- 2rir2 c2rl = +d
(84)
(zr2 + 02 or - = +
(85)
(= (x-wr/1) - crr - =dr
(86)
(=+ (ct - 0r =r
(87)
(a - (((1-riri--o - cri -+1 =dri
(88)
(z(1 r/r2)) - < 1 3 d3r2
(89)
+ ra(X, Z) be a compositional definition pattern over some relations Pd R and over arbitrary entities X, Z E. Furthermore, let fx. be relation as- signment function that is defined over 71 and r2 such that for any i E (1, 2). fn = (che, dh r!h) (dhl)d?) Ild)), and r = (r) Moreover, let the slope vectors be posi- tive, ie.. r - 0 for E {1,2].
Proof Let
with cf = -c,: [|c]), dhe
What want show is that if Inequalities 84 89 define the region of ra in the virtual triple space, then (X A r2( Z) + ra(X, Z) holds in the virtual triple space, i.., for any entity assignment function fe and virtual assignment function fo over fe if fx E (rir) and fo(Y, E (12)). then (X, Z) must be within the region of ra. To prove this, we will construct system of inequalities first that describes ra and satisfies the compositional definition pattern. Afterward, we will show that the constructed system of inequalities has the same behavior as Inequalities 89 proving Theorem E.2
(+) First, we choose an arbitrary entity assignment function fe and virtual assignment function fo over fe. We will henceforth denote the assigned entity embeddings with fe (X) = æ. fe = y, and (Z) = z to state our proofs concisely. Next, we assume that the left part of r1 (X, AY, Z) + ra(X, Z) is true, i.e., that (X, Y) E (ri and fo, 2) E fr (r2) hold. This means concretely that we can instantiate the following inequalities from Inequalities
et - -y 30
(90)
x ct rf
(91)
y - 1 r -
(92)
- 1 1 ox 0x+d==0
(93)
y - 2 r
<0
(94)
y 2 r 02 20 ~0
(95)
(96)
o r y 0
(97)
Our next goal is to construct system of inequalities that makes ra(X, (X, - the right part of the pattern - true, i.e., that defines the region of r사 such that f. (X, Z) lies within it. To reach this goal, substitute Inequalities 97 into each other to receive system of inequalities that (1) has the same behavior as the initial set and (2) does not contain the entity embedding y. Since we have the beginning assumed that the slope vectors positive, other as follows:
substitute Inequalities 97 into each
1.
95 in
91
and
94
in
90
leading to
98
2.
95 in
92
and
94
in
leading to
99
3.
93
in 97
92 in
leading
100
4.
91
in
96
and
90 in
97
leading
101
25

---

Published as a conference paper at ICLR 2023
5.
90
in
92 and
93 in
91
leading
102
6.
94
in
96
and 97 in
leading to
103
7.
90
in
91
leading to 104
8.
93 in
92
leading
105
9.
94 in
95
leading
106
10.
97
in 96
leading to
107
These substitutions result in system of inequalities with the same behavior the initial system of
inequalities. We have listed the result of these substitutions in Inequalities 98 107
( - -r - -
(98)
(2r² + c2 -rr ct) =d +
(99)
- crr - = + 1z-ar (=-
(100)
( (c z)r or - 0
(101)
- - -ri-ch"-drr1 +
(102)
(x(1 - r4r1)) 22
d
(103)
d 1 d
(104)
d 1 d
(105)
d d'
(106)
d 1 d'
(107)
Note that Incqualities 98 103 are equivalent to Inequalities 8 84 and that Inequalities 104 107 are tautologies since any width embedding de is positive by the definition of the ExpressivE. model. Therefore, Inequalities 107 and Inequalities
84 89 have the same behavior,
required. It
remains to show that Inequalities 98 107 define a region 8a containing f. Z) 2 if fx, (X,Y), Y)
fn (r1) and (Y. Z) E (r2). This is trivially true since Inequalities 98 107 directly follow from Inequalities 90 97 which are instantiations of Inequalities' 1 repressentng fo [X, Y) E (rir and fY, Z) (T2).
Reading the proof bottom-up proves the other direction (+), ie.. if fe is in sd, then there exists entity assignment fY) y such that fx Y) fx (r1) and fo 7) (r())) Thereby, we have successfully shown that if Inequalities 84 describe the region sa of relation ra in the virtual triple space, then r, (X, Y) r2 Z) ra Z) holds for (rir)). fn. (r2), and sa in the virtual triple space.
We have proven Theorem defined region for positive slope vectors. The proof works vice versa for any other sign of slope vectors, except that the substitutions of Inequalities 97 may vary due the different signs of slope vectors. Note that by proving Theorem E.2 we have also proven Theorem 5.3 i.c., that there exists a convex region that describes the compositionally defined region sd since (1) we have characterized the compositionally defined region and thereby implicitly proven its existence and since (2) Inequalities 84 89 trivially form a convex region.
B22 in this section, i.e., that Inequalities 89 define the compositionally
F DETAILS ON CAPTURING PATTERNS EXACTLY
Before we prove the inference capabilities of ExpressivE in this section, we formally define the considered patterns in Definition F.I
Definition F.1 In accordance with Sun el al. 2019); Abboud et al. 2020 we define the following
inference patterns:
Patterns of the form (X,Y) = ri rY, X) with R are called symmetry patterns.
26

---

Published as a conference paper at ICLR 2023
Patterns of the form rı (X,Y) = (Y) with rı Rare called anti-symmetry patterns.
Patterns of the form r1 (X,Y) < XY, with r1, r2 E Rand rı + 12 are called inversion patterns.
Patterns of the form ri (X, (), Arz 2) rx(X,2) with F1, r2, R Rand ri + r2 + T3
are called general composition patterns.
Patterns of the form (X, Y), 2) + ra(X, Z) T,,2.Ta Randr, & r2 # rd are called compositional definition patterns.
Patterns of the form rı (x,YY) = r2(X,Y) with 11, E R and # 12 are called
hierarchy patterns.
Patterns of the form ri (X, Y) A A2(,X + ra(X, Y) with 22,72,33 E R and Tı # 12 #
Ty are called intersection patterns.
Patterns of the form rı (X, Y) A r2(X, + 1. with r1, E R and ri # 12 are called mutual exclusion patterns.
With all definitions in place, we prove the exactness part of Theorems 5.2 and 5.4 i.e., that ExpressivE captures all patterns from Table I exactly. Specifically, we do not solely prove that ExpressivE. captures the patterns of Table exactly, but that ExpressivE captures these patterns exactly iff its relation hyper-parallelograms meet the properties intuitively described in Section [ Next, in Section G we prove that ExpressivE captures patterns exactly and exclusively. For the upcoming proofs, we employ the definitions and formal specifications of Sections C and
Proposition F. (Symmetry (Exactly)) Let my (M, fn) be relation configuration and rı R be a symmetric relation, i.e. Ti ri(X, ()=Y))++> + rY,, (X, X) holds for any entities X, Y E E. Then mn captures (X,Y)= > ri (Y, X) exactly iffri relation hyper-parailelogram fn(rr) ) is symmetric across the identity line of any correlation subspace.
Proof + For the first direction, what is to be shown is that if r1 r1's relation hyper-parallelogram Jn (r:) is symmetric across the identity line of any correlation subspace, then my captures ri(X, = rY, X) exactly. We show this by contradiction. Thus, we first assume that r 's corre- sponding relation tyyper-prralelogeee relation subspace s,. Now to the contrary, we assume that m, does not capture ri (X, Y) = ri (Y, X) exactly. Then, due to the symmetry of the ayper-parallelogrmm across the identity line in any correla- tion subspace 8;, for any virtual assignment function fo it holds that if fo (C eyy E fx((r) for arbitrary entities Ez2 Cy E E, then fo (Cy, ex) E fr. (r1). Yet, by the definition of capturing patterns exactly, this means that mn captures ri (X,Y) ri (Y, exactly. This contradiction the initial assumption that my does not capture ri ri(XY) + (Y, exactly, proving the + part of the proposition.
fi (r1) of ma is symmetric across the identity line for any cor-
For the second direction, what is to be shown is that if m& captures rı (x, = rY,Y exactly, then ri 's relation ayper-parallelogram fr. (r1) symmetric across the identity line of any correlation subspace. We show this by contradiction. Thus, we first assume that mn captures (X, = (Y, exactly, i.e., for any instantiation of fe and fo over fc if (e ey) e f (ri). then fe Cx) ) E (r,r). Now to the contrary, we assume that 's corresponding relation syper-parallelogram (n1) ) of mn is not symmetric across the identity line in at least one correlation subspace Then, since fa (ri) an instantiation of fo and fe such that (e ey) E (T1 and fe ex) & fn (r1) for some entities ez, Cy E. Yet, by the definition of capturing patterns exactly, this means that my does not capture rı (X, Y) = ri (Y, X) exactly. This is contradiction to the initial assumption that mp captures r (X, Y) rz XY, exactly, proving the + part of the proposition.
+
) is not symmetric across the identity line in 8;, there is
Proposition F2 (Anti-Symmetry (Exactly) Let mn = (M. be a relation configuration and T1 R be anti-symmetric relation, i.e., (x. Y) = (Y, holds for any entities X,Y E. Then my captures rx(X)) + -Ti (Y, X) exactly iffri 's relation hyper papalllarallelogram fr(rr) is not symmetric across the identity line in at least one correlation subspace.
27

---

Published as a conference paper at ICLR 2023
Proposition F2 can be proven analogously to Proposition F.I Therefore, its proof has been omitted.
Proposition F.3 (Inversion (Exactly)) mn = (M, fn) be a relation configuration and r1, 12 E R be relations where ri ri(X, Y) 4> T2 X) holds for any entities X,Y Y E E. Then mn captures ri (x( Y) + r2(Y, X) exactly iff fn (r() is the mirror image across the identity line of Jn (r²) for any correlation subspace.
Proof + For the first direction, what is to be shown is that if the relation syper-parallelograan fi (r1) is the mirror image across the identity line of fr. (T2) for any correlation subspace, then mn captures ri (X, Y) + r2(Y, X) exactly. We show this by contradiction. Thus, we first assume that ri corresponding relation hyper- parallleelll fn (r1) of mn is the mirror image across the identity line of (12) for any correlation subspace s,. Now to the contrary,
assume that m& does not capture T1 (X, Y) + T2 X) exactly. Then, due to (r1) being the mirror image of f (F2) in any correlation subspace 8; for any virtual assignment function fo it holds that if (Cg, Cy) E fr (r1) for arbitrary entities Ez, Cy E E, then fey C.y) E (12). Yet, by the definition of capturing patterns exactly, this means that mn captures (X,Y) + 72 (Y, X) exactly. This is a contradiction to the initial assumption that mn does not capture Ti (X, Y) + re (Y, X) exactly, proving the + part of the proposition.
< For the second direction, what is to be shown is that if my captures rı (X,Y) @ r2(Y, exactly, then the relation syper-parallelogram (r1) is the mirror image across the identity line of fn (r2) for any correlation subspace. We show this by contradiction. Thus, we first assume that m, captures r1 (x.Y) Y) + r2(Y, exactly, i.e., for any instantiation of fe and fo over fe if fe(ew: E (r1), then fo ex) E (12).. Now to the contrary, we assume that rr corresponding relation hyper- paeelparallloogram fn (r.) of mp is not the mirror image across the identity line of fa (r2) for at least one correlation subspace 8;. Then, since fn (ri) ) is not the mirror image across the identity line of (r2) in 8,, there is an instantiation of fo and fe such that (ex, E (r1) and fe(ey, Ex) & fr (r2) for some entities Ez₁ Cy E. Yet, by the definition of capturing patterns exactly, this means that my does not capture Ti (X( Y) + r22 X) exactly. This is contradiction to the initial assumption that m, captures 71 (X, Y) + XY,
exactly, proving the = part of the proposition.
Proposition F.4 (Hierarchy (Exactly)) Let mn (M, fn) be a relation configuration and T2,72 E R be relations where Ti (X) = (2(X, holds for any entities X,Y Y E E. Then my captures (X, = "X, Y) exactly iff fn (11) is subsumed by ft (T2) for any correlation subspace.
Proof = For the first direction, what is to be shown is that if the relation hyper-parallelogram fr (r.) is subsumed by fn (r2) for any correlation subspace, then my captures ri (X, Y) > r2(X, Y) exactly. We show this by contradiction. Thus, we first assume that ri 's corresponding relation hyper-paralleeooran fn (r1) of mn is subsumed by fr (T2) for any correlation subspace st. Now to the contrary, we assume that mn does not capture Ti (x, = r2(X, exactly. Then, due fr (r1) being subset of (12) in any correlation subspace 8i, for any virtual assignment function fo it holds that if fo (ea, E (r1) for arbitrary entities ezy ey E E, then (e ey) E fn (r2). Yet, by the definition of capturing patterns exactly, this means that mn captures Ti (X, Y) + (2 Y) exactly. This is a contradiction to the initial assumption that mn does not capture (X, Y) > r2 YY, exactly, proving the + part of the proposition.
< For the second direction, what is to be shown is that if m, captures r (X,Y) Y) + rx(X, Y) exactly, then the relation syper-parallelogree We show this by contradiction. Thus, we first assume that m. captures ri (X,Y) * (X) exactly, i.e., for any instantiation of fa and fo over fc if (e,, eyy E fn (r1). then fe ex) E fh (r2). Now to the contrary. we assume that r1 's corresponding relation hyper- parallelolllom (r1) of m. is not subsumed by fn (r2) for at least one correlation subspace s, Then, since fr (ri) is subsumed by Sn (T²) in 8;, there is an instantiation of fu and fe such that (e2, E fn (ri) and fo (ez, Cy) & fi. (r2) for some entities cz, By E E. Yet, by the definition of capturing patterns exactly, this means that m. does not capture r (xX Y) r2( (X, Y) exactly. This is a contradiction to the initial assumption that m, captures r, (X, Y) = r2 (X, Y) exactly, proving the + part of the proposition.
fr (r1) is subsumed by fn (r2) for any correlation subspace.
28

---

Published as a conference paper at ICLR 2023
Proposition F5 (Intersection (Exactly)) Let mn (M,f)) be relation configuration and T1, 22,22,30 T3 E be relations where 1i (X. (X) ra(X, Y) holds for any entities X.Y E E. Then my captures (X,Y) A r2(X, = Tx(X, Y) exactly iff the intersection of fn (T1) and In (12) is subsumed by Jn (ra) for any correlation subspace.
Proof + For the first direction, what is to be shown is that if the intersection of fn (r1) and fr (12) subsumed by fix (ra) for any correlation subspace, then m. captures r (X, Y) A r2 + (X(,, Y) exactly. We show this by contradiction. Thus, we first assume that the intersection of fh (r1) and fix (12) of m, is subsumed by fa (rs) for any correlation subspace 8,. Now to the contrary, we assume that m/ does not capture rı rx(, Y) A (2,, Y) = rr(X. Y) exactly. Then, due to the intersection of fa (r1) and (12) being a subset of Jn (ra) in any correlation subspace 8; for any virtual assignment function fo it holds that if (em, Ey) E J (r1) and fe Ey) E fn (r22 for arbitrary entities Eg, by E E, then fe (ex, ey) E (1ssss) Yet, by the definition of capturing patterns exactly, this means that me captures 71 (X, Y) A T2 (X, Y) = rx Y) exactly. This is contradiction to the initial assumption that my does not capture Ti (X,Y) Y) A 12 (2 = YY exactly, proving the = part of the proposition.
< For the second direction, what is to be shown is that if m. captures ri (X) A A = rx(X, Y) exactly, then the intersection of fi (r1) and fr (12) is subsumed by (rs) for any correlation subspace. We show this by contradiction. Thus, we first assume that mn captures rx(X,) Y) A Y2 = ra(X,Y) Y) exactly, i.e., for any instantiation of fa and fu over Sa if fe(e,, ey) E (ri) and fe (e)) E fr(2), then fo Cy) E fr (rs). Now to the contrary. we assume that the intersection of fr (r1) and fn (T2) is not subsumed by fr (T3) for at least one cor- relation subspace s; Then, since the intersection of fa (r1) and (r is not subsumed by fn (rs) in S;, there is an instantiation of fo and fe such that fo (Ca, ey) E fr (r1) and fe Gy) E fi (r2) but (e ey) & fr (Ts) for some entities ez; Cy E E. Yet, by the definition of capturing patterns exactly, this means that my does not capture ri rx( A (X,Y)) - ra(X, Y) exactly, This is contradiction to the initial assumption that m& captures ri (X,Y) Ara ( Y) - (x(
exactly, proving the < part of the proposition.
Proposition F66 (Mutual Exclusion (Exactly)) Let mn (M, fr) be relation configuration and T2 E R be relations where ri( A 1x, Y) + 1 holds for any entities X,Y E E. Then my captures Ti (X,Y) A Ar2(X, Y) + exactly iff (ri) and fn (12) do not intersect in at least one correlation subspace.
Proof + For the first direction, what is to be shown is that if the relation hyper-parallelograms fh (r, and fn (12) do not intersect in at least one correlation subspace, then mn captures r (X, Y)Λ r2(,, Y)= + I exactly. We show this by contradiction. Thus, we first assume that fn (rr) and Sn (r2) of mn do not intersect in at least one correlation subspace 8;. Now to the contrary, we assume that mn does not capture (X, Y) A YY, = 1 exactly. Then, since fi (r1) and fn (r2) do not intersect in at least one correlation subspace 8, for any virtual assignment function fo it holds that if (e,,, Byy) E fn (r1) for arbitrary entities ex, By E, then fo eyy & fr (r2). Yet, by the definition of capturing patterns exactly, this means that m& captures rn (X, Y) A Az XX Y) = 1 exactly. This is contradiction to the initial assumption that my does not capture TI (X, Y) Y) + 1 exactly, proving the + part of the proposition.
+ For the second direction, what is to be shown is that if m& captures r exactly, then the relation exper-paralleelorame correlation subspace. We show this by contradiction. Thus. we first assume that mn captures Tn (X, A (Y) + I exactly, i.c., for any instantiation of fa and fo over fa if fe ey) E fh (ri). then fe ey) & (12) and if (C,,, e④) E fr (r2), then fe ey) g fr (ri). Now to the contrary. we assume that r 's corresponding relation hyper-parallelogram fr (r(()) of mn intersects with fa (r2) in any correlation subspace. Then, since fn (r.) intersects with fn (T2) in any correlation subspace, there is an instantiation of fa and fe such that fo (ez; ey) E (r(rr)
ri (X, Y) A (x, + 1 Sn (r1) and f (r2) do not intersect in at least one
and fe e.) E fr( for some entities ex, Ey E E. Yet, by the definition of capturing patterns exactly, this means that m, does not capture 11 (X AX,, = exactly. This is contradiction to the initial assumption that m, captures ri (X, Y) A To (X, = 1 exactly, proving the < part of the proposition.
29

---

Published as a conference paper at ICLR 2023
I's E R be relations and let my Proposition E.7 (General Composition (Exactly)) Let 22,s'
(M. fn) be a relation configuration, where fh is defined over T1, 22, and T3- Furthermore let Ta be the composite relation of ri and r2. i.e., (X) A (2 Z) + Ta(X, Z) holds for any entities X, Y, 7 E E. Then mn captures Ti rx(X, (x,Y) A (Y, 2) + ra (X, 7) iff the relation hyper- parallelogram I (ra) subsumes the compositionally defined region sa defined by In (r1) and f (T2) for any correlation subspace.
Proof = For the first direction, assume that the compositionally defined region defined by fh (T1) and (r2) is subsumed by fn (ra) for any correlation subspace. What is to be shown is that ma captures (X, Y) A r2(V, 2) = V3 X Z) exactly. Our proof for this direction is based on the following three results:
1. For an auxiliary relation r. E R, there exists convex region sa in the virtual triple space such that ri (X,Y) (r2 2 correlation subspace (Theorem
+ ra(X, 2) holds for fn (r1). (r2),, and sd in any
2. fa((1) subsumes sa iff m& captures ra (X, = rr((X Y) exactly (Proposition F.4
3. (x Y) r2(Y 2) = rx(X, Z) logically follows from (ri(X, A (2 Z) +
2)( 2), Ta(X, + Y)).
For (1), observe that based on Theorem E.2 we know that we can define an auxiliary relation ra E R with area sa such that ri (X, Y) A r2 Y, Z) <> ra(X, Z) holds for fn (r1). (12), and 8d, i.e., such that Sd is the compositionally defined region of fn (r1) and fn (r2). For (2), as shown in Proposition F.4, mn captures ra ra(X. Y) = (x, exactly iff fn (T3) subsumes ra's area sd- Therefore, we have shown that if fa (ra) subsumes 8a, and if sa is the compositionally defined region of fn (r1) and fn (r2), then ra(X; Y) = ra((X Y) and rı (X, A r2(Y, Z) < ra (x(X, Z) holds for fn (r1), fn (r2), fi (Tz) and sa- Together with the fact that fn is only defined over T1. r2, and r3, we can infer that my exactly captures any pattern - sollcy consisting of T1, 72, and r3. that follows from 1 = {ri (X, Y) A (Y, 2) + TX(X, 2), ra(XX
(X Y) For (3), by logical deduction, the following statement holds: 3 -= (r((X, A rY, Z) = ra ( (X,Y). Since ri ri(X, Y) 12 Z) = (X, Z) (i) solely consists of rı, r2, and r's and (ii) follows from bs we have proven that my captures (X, Y) A TY, 2) + rx(X, (X, 2) exactly if (ra) subsumes 8a. proving the + part of the proposition.
< For the second direction, what is to be shown is that if my captures rı (X,Y) A2, + (X Z) exactly, then the compositionally defined region defined by (ri) and (12) is sub- sumed by fr (ra) for any correlation subspace. We prove this by contradiction. Thus assume that mn captures rı (X, Y) A AY, Z) + rss (X, Z) exactly, i.e. for any instantiation of fe and fo over fe if (e(, E fr (r1) and fo fe e E fr (12), then ee() E fn (rs). Now to the contrary, we assume that r3's 's corresponding relation hyper- apper-parallelogram fn (r3) of mn does not subsume the compositionally defined region sa in at least one correlation subspace. The follow- ing three points will be used to construct a counter-example: (1) we have shown in Theorem E.2 that we can define
auxiliary relation rd E R with area sa such that rI (X, Y) A rY, 2) +
ra(X, 2) holds for fn (T1), fn (r2), and sd, (2) TI (X, Y) A (Y, Z) = (X Z) logically fol- lows from (X,(X, Y) A r2 (Y, Z) + ra(XX Z), Ya(X,
r3 (x( Y), stating together with Point (1) and Proposition F4 that r3y needs to subsume ra's area sa such that mn can capture ri rx, Y) A rY, Z)= = ra Z) exactly, and (3) we have initially assumed that fa (ra) does not subsume 8a. From (1)-() we can infer that there exists an instantiation of fa and Se such that (n Eyy) fn (r:) and f (ey, ez) E (ra) but fo(en) e2) & fn (ra) for some entities ex, Cyy Ez E E. Yet, by the definition of capturing patterns exactly, this means that m, does not capture (X Y) A (Y, Z)- + r3(X, Z) exactly. This a contradiction to the initial assumption that mn captures ri (x( Y) A (Y, Z) = rx(X, 7) exactly, proving the = part of the proposition.
Proposition E8 (Compositional Definition (Exactly) Let TI, T2, E R be relations and let m. = (M, fn) be relation configuration, where Sn is defined over 12, and Ta. Furthermore let ra be the compositionally defined relation of rı and r2, i.e., ri A (Y, Z) + ra( (X, Z) holds for any entities X, Y, Z E E. Then m. captures r rx(X. Y) A (Y, Z) ra(XX, Z) iff the relation fr (ra) and fn (12) for any correlation subspace.
sepeer-prraleeograan
) is equal to the compositionally defined region Sa defined by fr. (r.)
30

---

Published as a conference paper at ICLR 2023
The proof for Proposition F.8 is straightforward, Proposition F.8 can be proven analogously to Proposition F.7 with the sole difference that instead of defining relation embedding fi that subsumes the compositionally defined region sd. define the compositionally defined relation ra whose embedding Sn (ra) is equal to the compositionally defined region &d-
Propositions F.1
F.5 F.4, and H.6 together prove the exactness part of Theorem 5.2 i.e.,
that ExpressivE can capture symmetry, anti-symmetry, inversion, intersection, hierarchy, and mutual exclusion exactly. Propositions F.7 and F.8 prove the exactness part of Theorem [5.4] i.e., that ExpressivE can capture general composition exactly. Now remains to show that ExpressivE can capture all these patterns exactly and exclusively, which is shown Section G
G DETAILS ON CAPTURING PATTERNS EXCLUSIVELY
This section proves that ExpressivE can capture all inference patterns Theorems 5.2 and exxecty and exclusively. By the definition of capturing pattern &b exactly and exclusively, this means that we need to construct relation configuration my such that (1) ma captures vé and (2) mA does not capture any positive pattern & such that v /e ø. Note that we have shown in Propositions F. F.7 that we can construct a relation configuration my that captures the following patterns by constraining the following geometric properties of m, 's relation hyper-parallelonn parallloograms:
1. For symmetry and inversion patterns, the mirror images across the identity line of hyper- parallelograms in any correlation subspace need to be constrained (Propositions F. and
2. For hierarchy and intersection patterns the intersections of hyper-parrlleloograns any correlation subspace need to be constrained (Propositions F.4 and F.5).
3. For general composition patterns the compositionally defined region needs be subsumed in any correlation subspace.
Since symmetry, inversion, hierarchy, intersection, and composition are all positive patterns of our considered language of patterns, suffices to analyze the mirror images (M), intersections (I), and compositionally defined regions (C) of each relation patterns have been captured. Furthermore, for the upcoming proofs, Definition G.1 defines head and tail intervals.
to check which positive
Definition G.1 (Head and Tail Intervals) Let ri E R be a relation and mp = (M, fn.) be a relation configuration. We call an interval a head interval H H.mms and respectively tail interval Tramm, of ri and mp for arbitrary entities en, er. E E. viriual assignment functions S and complete model configuration m over mn and fo the following property holds: if m captures triple Ti (ee, et) to be true, then (ex) E Hrama and fo E Trams.
Using the Definition G. and the insights provided by (M), (I), and (C), will followingly prove that ExpressivE captures each considered pattern exactly and exclusively.
Proposition G.1 (Symmetry (Exactly and Exclusively)) Let m. (M. fn) be a relation con- figuration and rı E R be a symmetric relation, i.e., Ti (X, Y) + (Y, holds for any entities X,Y E E. Then my can capture r (X,Y) = rY,Y, exactly and exclusively.
Proposition G.2 (Anti-Symmetry (Exactly and Exclusively)) Let mn (M, fn) be relation configuration and T E be an anti-symmelric relation, i.e., ri (X,Y) Y)= -r -min--iaa- (Y,X) holds for any entities X, Y E E. Then m& can capture ri (X, Y) 3 -mi (Y, X) exactly and exclusively.
The proofs for Propositions G.I and G.2 are straightforward, as the only positive pattern that contains only one relation is symmetry. Furthermore, since (i) Propositions F.I and F.2 have shown that there is a relation configuration that can capture symmetry'anti-symeen symmetry exactly and (ii) a hyper- parallelogram cannot be symmetric and anti-symmetric simultancously, we have shown that there a relation configuration that captures commetry/anti-symment exactly and exclusively, proving Propositions G.1 and G.2
31

---

Published as a conference paper at ICLR 2023
Proposition G.3 (Inversion (Exactly and Exclusively)) Let m, (M, fu.) be relation configu- ration and 1i, T2 E R be relations where T1(X,Y) Y) + r2 holds for any entities X,Y E E. Then m& can capture (X, + r2 X) exactly and exclusively.
The proof for Proposition G.3 straightforward. as the only positive patterns that contain at most two relations are symmetry, hierarchy, and inversion. Furthermore, since (i) Proposition Fa3 shown that there is relation configuration that can capture inversion exactly and (ii) is simple show that a sypeerpprralelograa
can be the mirror image of another hyper- hyper-paralle parallelogram without one of them subsuming the other (hierarchy) or one of them being symmetric across the identity line (symmetry), we have shown that there is relation configuration that captures inversion exactly and exclusively, proving Proposition
G.3
Proposition G.4 (Hierarchy (Exactly and Exclusively)) Let m. = (M, be a relation config- uration and r2 R be relations where ri (X,Y) = (x, holds for any entities X, Y E. Then m& can capture 1 (X, Y) = r2 Y) exactly and exclusively.
The proof for Proposition G.4 is straightforward, as the only positive patterns that contain at most two relations are symmetry, hierarchy, and inversion. Furthermore, since (i) Proposition FF.4haa shown that there is relation configuration that can capture hierarchy exactly and (ii) it is simple to show that a hyper- paraallellloo can subsume another hyper-pann pyper-parallelogran without one of them being the mirror image across the identity line of the other (inversion) one of them being symmetric across the identity line (symmetry), we have shown that there is a relation configuration that captures hierarchy exactly and exclusively, proving Proposition G.4
Proposition G.5 (Intersection (Exactly and Exclusively)) Let mn = (M, fn) be a relation con- figuration and r1, T2, Va E R be relations where ri (X, Y) A r2(X, (XY) + ra(X, Y) holds for any entities X,Y E E. Then my can capture r1 Y) A)2 Y) = r2 Y) exactly and exclusively.
Proof What is to be shown is that my can capture intersection (71 A))
exactly and exclusively. We have already shown that m, capture (X,Y) YY ra Y) exactly in Proposition F.5 Now, to show that my can capture intersection exactly and exclusively, we construct instance of my such that (1) my captures intersection (X, Y) (2, Y) = r3 (x, and (2) m, does not capture any positive pattern & such that ri (X.Y) A r2 (2 Y) (Y) +
Table 6: One-dimensional relation embeddings a relation configuration m. that captures intersec- tion (i.e., ri (X, Y) r2(X, = ra(X, Y)) exactly and exclusively.
ch
dh
r²
c
d
ph
F1
-6
2
F22
11.5
3
5
11
3
3
F33
9.5
9
1
3
Figure 2 visualizes the hyper-parallelograms defined by the one-dimensional relation embeddings
of Table 6 In particular, it displays the hyper-parallelograas of r1, T2, r3- As can be easily seen
in Figure 2 (and proven using Proposition F.5), the relation configuration my described by Table 6
captures r1 (X, Y) (X. = rs (X Y) exactly, as fr. (rs) subsumes the intersection of fn (r1)
and fn. (r²).
Now it remains show that my does not capture any positive pattern & such that rı (X, Y) A T2(X, Y) = rx(X, Y) I o. To show this, we will show that (M) the mirror image of any relation hyper-parallelogram is not subsumed by any other relation symmetry nor inversion pattern is captured) and (C) the compositionally defined region defined by any pair of unwanted composition pattern is captured). We do not need to show that (I) no unwanted relation hyper-pus paper-paralllograms intersect, as by the nature of the intersection pattern, fr. (r1). fr. (r2). and f (ra) should intersect.
(i.e., no unwanted
is not subsumed by any relation hyper-pane apper-parallelogram (i.e., no
32

---

Published as a conference paper at ICLR 2023
et
4
3.5
3
(T
Identity Line
2.5
fn
2
1.5
fn
0.5
Eh
4.5
4
33.5
-3
-2.5
-2
-15
-1
-0.5
0.5
1.5
2
2.5
0.5
Figure 2: Visualization of the relation configuration my described by Table 6
For (M), observe in Figure 2 that all syper-parallelograms fx (r1). fr (12). and fa (rs) ) of my on the same side the identity line. Thus, the mirror images fa (r1)). fix (T2). and fx (rs) across the identity line must be the other side. Therefore, we have shown (M), i.e., that relation hyper-parallelograms subsume the mirror image of any other relation hyper-parallelogram and thus that m, does not capture any unwanted symmetry nor inversion pattern.
For (C), observe in Figure that for the displayed relation configuration m,, the head intervals of any relation hyper-paralleoogram of m& contain only negative values and the tail intervals contain only positive values. Thus, for any pair (r;,ry) E {r1, F2, r3)2 there is no virtual assignment function fo such that m over m and fo captures r=(2, y) and ry. 2) for arbitrary entities x, y, 2 E E. Therefore, no pair of relations ry) defines a compositionally defined region. Thus, we have shown (C) that no compositionally defined region subsumed by any relation syper-parallelogran (as no compositionally defined region exists) and thus that m. does not capture any unwanted general composition pattern.
By Proposition F.5 and by proving (M) and (C), we have shown that the constructed relation configuration m& of Table captures the intersection pattern ri (X, Y) r2(X, X) + (x and does not capture any positive pattern & such that (X, Y) A Y) rx( Φ. This means by the definition of capturing patterns exactly and exclusively that m. captures intersection (ri (X,(X, Y) (2(X, Y) rx(X, Y)) exactly and exclusively, proving the proposition.
Proposition G.6 (General Composition (Exactly and Exclusively)) Let F1, 12,12, R be rela- tions and lel m. = (M, , fn) be a relation configuration, where fn. is defined over r1, and ra- Furthermore let r3 be the composite relation of r and r2, Le., (X, Y) A (Y, 7) = r3 (X, (X, 7)
holds for all entities X, Y, E E. Then mp can capture T (X,Y) Y) (Y, Z) = r3 (x 2) exactly and exclusively.
Proof What is to be shown is that my can capture general composition (r1 (r,(X, Y) A (Y, 7) ra(X, Z)) exactly and exclusively. We have already shown that my can capture ri (X, Y) (Y, Z) = ra (X, Z) exactly in Proposition F.7 Now, to show that m& capture general composi- tion exactly and exclusively, we construct an instance of my such that (I) my captures general compo- sition and (2) m4 does not capture any positive pattern such that (X,Y) Ar, Z) = rx Z) # Φ.
Figure visualizes the paper--pralllllgraas defined by the one-dimensional relation embeddings r1, T2, T3, and the compositionally
of Table 7 In particular, it displays the defined region sa of auxiliary relation ra such that rı (X,Y) A (Y, 2) ra(X, 2) holds for
33

---

Published as a conference paper at ICLR 2023
Table One-dimensional relation embeddings of relation configuration m& that captures general composition (i.e., 1i (X, Y) A r2(Y, 2) = rx(X, Z)) and that captures compositional definition (i.e., ri( Y) r2 Z) & ra(X, 2)) exactly and exclusively.
ch
d
rtt
c
d'
rh
T1
2
8
5
3
F2
35
2
5
Td
76
10
10
14
2
2.5
T3 46
11
19
6
4
(r1), (r2), and sa- As be easily seen in Figure (and proven using Theorem E.2 and Proposition F.7). the relation configuration m, described by Table 7 rı(X, (A,Y)) Ar > ra(X, Z) exactly, as fa (ra) subsumes the compositionally defined region 8d-
10 Ct
fn((3)
9
8
fn
fn((r) sd
5
Identity Line
fn(r1)
2
Ch
3
Figure 3: Visualization of the relation configuration ma described by Table 7
Now it remains to show that my does not capture any positive pattern & such that ri YY, A rY,Y, Z) (X, Z) /4 Φ. To show this, we will show that (M) the mirror image of any relation hyper- paper--arallelogram is not subsumed by any other relation hyper-parallelograan (i.e., no unwanted symmetry nor inversion pattern captured), (I) no relation eyper-parallelorraan each other (i.e., no unwanted hierarchy nor intersection pattern is captured), and (C) solely the compositionally defined region sa defined by fn (r1) and fn (r2) is subsumed by fn (rs) and no other compositionally defined region is subsumed by any other relation hyper- syper-parallelogram (i.c., unwanted composition pattern is captured).
intersect with
For (M), observe in Figure 3 that all syper-paralleloggamss fr. (r1), fr. (r2), and fr. (ra) of m.
on the same side the identity line. Thus, the mirror images fa 1. fi (r2). and fr (rs) across the identity line must be the other side. Therefore,
have shown (M), i.c., that relation hyper-pe pprelealaalllloramss subsume the mirror image of any other relation hyper prper-parallelogram and thus that m. does not capture any unwanted symmetry nor inversion pattern.
34

---

Published as a conference paper at ICLR 2023
For (I), observe in Figure 3 that no relation hyper-paralleeograms fr. (r1), fn (rz), and (rs) of my intersect with each other. Thus, we have shown (I), i.e. that m, does not capture any unwanted hierarchy nor intersection pattern.
For (C), observe in Figure 3 that for the displayed relation configuration m.. the following head
and tail intervals can be define:: (i) Hm,, [-4, 0) and T,, [1. 3]. (ii) Hr,,m, = [1.3]
and T, T,,.m. = [6, 9]. and (iii) Hra.m. = 1, 1] and Tyg.ma = [4, 10]. The tail intervals solely overlap with the head intervals for Try,ma and Hra.m, i.e. T, Tr,.ma H Hry.m, = 0, (ri,ry)
(ri. r2, r3]² (2). Thus, for any pair (ra,ry) E {ri, T3) (r1. there is no virtual assignment function fo such that m over my and fo captures r1 y) and ry 2)) for arbitrary entities x; y, 2 E E. Therefore, (ri, r2) is the only pair of relations that defines a compositionally defined region, i.e., no other pair of relations defines compositionally defined region. Thus, we have shown (C) that no other compositionally defined region is subsumed by any other relation (as no other compositionally defined region exists) and thus that no unwanted composition pattern is captured by m.
By Proposition F.7 and by proving (!), (M), and (C), we have shown that the constructed relation configuration m, of Table capturess the general composition pattern rx(, A TY 2) = Tx Z) and does not capture any positive pattern such that ri (X, Ar2 (Y, Z) = ra(X, 2) لا ø. This means by the definition of capturing patterns exactly and exclusively that mp captures general composition (r1 (X, Y) A (Y, Z) rx(X, Z)) exactly and exclusively, proving the proposition. D
Proposition G.7 (Compositional Delinition (Exactly and Exclusively)) Let T2, ra E R be re- lations and let m = (M, fi.) be a relation configuration, where fn is defined over r1, T2, T2, and ra- Furthermore, let ra be the compositionally defined relation of and r2, i.e. r1(X. Y) (Y, Z) + ra(X, Z) holds for all entities X, Y, 2,Z= E E. Then mn can capture ri (X,Y)Arz(K Z) + ra (X, Z) exactly and exclusively.
The proof for Proposition G.7 is straightforward, as it can be proven analogously to Proposition G.6 with the only difference that instead of defining a relation embedding f'r (ra) that subsumes the compositionally defined region, we define the compositionally defined relation ra whose embedding fh (ra) equal to the compositionally defined region sd. We have stated the relation embeddings for ra in Table 7 and also visualized fn (ra) in Figure 3
Finally, the sum of Propositions G.1 G.7 proves Theorems 5.2 and 5.4 Thus, we have theoretically shown that ExpressivE can capture any pattern from Table 1 exactly and exclusively.
H EXTENDED COMPOSITIONS
This section provides theoretical evidence that ExpressivE is not limited to capturing a single composition pattern. Specifically, we prove that ExpressivE can capture more than one application of a composition patter. The following theoretical result is empirically backed up by further experimental results of Appendix I.3
Let T2, T3, 21,23 E R be relations and let my = (M, fn) be a relation configuration, where fh. is defined over TI, T2 T3, 71,2, and 1222,3. Furthermore, let r rx(X, Y) (Y + TX,, , 2) and (X, Arrrs(Y, 2) * 21,2,3X, Z) hold for all entities X,Y, Z E E. Then mn can capture ri (X,Y)Ar2(1 Z) = (X, Z) and 2 (x,Y) (Y,Y))rr(YY Z) = 112233 Z) exactly and exclusively.
Proposition H.1
Proof What is to be shown is that my can capture Φ1 := rx, A r2((Y + r1, Z) and Φ2 := TT,2(X, X, Y) A rr(Y, Z) + (X, Z) exactly and exclusively. To show that there is an m. that captures Φ1 and Φ2 exactly and exclusively, we construct an instance of mn such that (I) m& captures Φ1 and d2 exactly, and (2) m. does not capture any positive pattern &e such that
(ói A d2) A v.
Figure visualizes the hyper-parallelogramt defined by the one-dimensional relation embeddings of Table In particular, it displays the hyper- paper--arallelograms of 71, r2, T1,2, T3, T1,2,3, and the nd compositionally defined regions of 2g.3. ad (1,2),3 ad (2,3))3 of auxiliary relation rf.2 r2.3 (1,2,33 and pdر (1.(2.3) such that ri (X,Y) A (Y, e (X, 2), r2 r2(X A ra(Y, 2) < r
35

---

Published as a conference paper at ICLR 2023
Table 8: One-dimensional relation embeddings of relation configuration my that captures two general compositions (i.e., r1(X, Y) A r2(Y, Z) + r1,2(X, Z) and r1,2(X, A ra(Y, Z) = (X,,, Z)) exactly and exclusively.
d
c
d'
y
6
2
5
72
35
5
2
71,2
-66
11
6
19
6
4
73
45
5
20
0
1,,
215
20
20
22
8
r1,((X A r2(3 < rd (X,)), and (X 2) <> n.d 1I.(..3) (X, (X,Z) Z) hold for fh (ri), fr (r2). (ra). fn(r1,2), fr (11,2,a). si,2 2, sd (1.2).3 and stt 12,3),) Note that from Φ1 and together with the auxiliary relation r 11,233) defined above - follows that (,, Y) (1, ( (X,, Y) = f1,2,3(X, Y), and nd (2. (X, + (,,, Y) need to be satisfied. Thus, as can be easily seen in Figure 4 (and proven using Theorem E.2 and Proposition F.7). the relation configuration m, described by Table 8 captures Φ1 and Φ exactly, fr. (11,2) subsumes the compositionally defined region ii,2 and fn. (11,2,3) subsumes the compositionally defined regions sd ,1,2),3 and sd 1,(2,3)
12 el
11
(Sn(rs)
fn(12))))
12,3)))
8
2,3
10
2),3
(1(,2)
$1.2
d
f1((2)
7
Identity Line
4-
fn((r))
2
en
-7
6
-5
22
7
Figure 4: Visualization of the relation configuration m, described by Table S
Now it remains to show that m& does not capture any positive pattern á such that (ør A (2) / sh. To show this, we will show that (M) the mirror image of any relation hyper-parallelogee is not subsumed by any other relation pyrae-para (i.e., unwanted symmetry inversion pattern
36

---

Published as a conference paper at ICLR 2023
is captured), (I) no relation hyper- papre-pprallelograms intersect with each other (i..., unwanted hierarchy
nor intersection pattern is captured), and (C) solely that s S fn (T1,2) and (s(1.2) (1,2),3 ,3 U Us (,(33)) S
fi (f1,2.3) are satisfied, and no other compositionally defined region is subsumed by any other relation pyper-paralleloggam (i.e., no unwanted composition pattern is captured).
For (M), observe in Figure 4 that all hyper-parallelograms fn (r1). fn (r2). fn (ra). (n((1,2), and Jn (f1,2,3) of my are on the same side of the identity line. Thus, the mirror images of any of these hyper-parallelogramm across the identity line must be the other side. Therefore, we have shown (M), i.c., that no relation tyyper-praalllogee
subsume the mirror image of any other relation syper-parallelogram and thus that m, does not capture any unwanted symmetry nor inversion pattern.
For (I), observe in Figure 4 that no relation hyper- paralelaral (r1). fn (12), fr (ra), fi (11,2), and fa (r1,2,3) of m. intersect with each other. Thus, we have shown (I), i... that my does not capture any unwanted hierarchy nor intersection pattern.
For (C), recall Definition G.I describing head and tail intervals. We observe in Figure 4 that for the dis-
played relation configuration my. the following head and tail intervals can be defined: (i) H mm,, = [-4,0] and T, mm 3], (ii) Hy,m,,
[1,3] 3] and mm. [6, 9]. (iii) H m = [-
and T mm, = [4, 9.7]. (iv) H Hr..m, = [7,9] and T mm. = [10, 12). (v) H Hr m. = [-
and Tra.aa.m. [9.8, 12), and (vi) H mg...m. -1,,3] and T,g mm = [9.8, 12 The tail inter-
vals solely overlap with the head intervals for the pairs ((),, (r2, ra), (11,2, (rI, r r2,)), i.e. Tra.m. n nHr..ma = 0, ry) E r3)? (((1, (12, ra), (T1,2, r3), (11, (2))) Thus, for any pair (r..ry) E (r1.72, r3)2 \ ((11, r2), (r2, (11,2, rs), (11. r2a)) there is no virtual assign- ment function fo such that m over mn and fo captures rz(2, y) and (v, for arbitrary entities r, y. E E. Therefore, {(r1, r2), (T2, ra), (11,2,7a), (ri,rgs) are the only pairs of relations that define a compositionally defined region, i.e., no other pair of relations defines a compositionally de- fined region. Thus we have shown that (1) m& captures Φ1 and Φ2 exactly - since s S (r1.2) and (2) the only other existing compositionally defined region 2,3 is disjoint with any other relation hyper-parallelogeee parallelograms. By (1) and (2), we have shown (C) that other compositionally defined region (specifically s s²,2) is subsumed by any other relation and thus that no unwanted composition pattern is captured by m
and (sg) (1, Us4 (2,3()))) E fn (1122,))
By proving that the constructed m. captures á1 and d22 exactly and by (I), (M), and (C), we have shown that the constructed relation configuration my of & captures Φi and d2 and does not capture any positive pattern v/ such that (ø) A (22) /f th. This means by the definition of capturing patterns exactly and exclusively that m, captures d1 and Φ2 exactly and exclusively, proving the proposition.
I ADDITIONAL EXPERIMENTS
This section presents additional experiments, providing further empirical evidence for our theoretical results. Specifically, Section [.I studies the benchmark performances of ExpressivE and its closest relatives on WNISRR stratified by the cardinality of each relation, providing empirical evidence that ExpressivE performs well on 1-1, 1-N, N-1, and N-N relations. Section 1.2 provides empirical evidence that ExpressivE can capture general composition and provides empirical support for a link between ExpressivE's 's significant performance gain on WNI8RR and inference capabilities. Finally, Section I.3 discusses empirical results, revealing that ExpressivE can reason over more than one step of composition patterns.
1.1 CARDINALITY EXPERIMENTS
This section provides empirical evidence for theoretical result that ExpressivE performs well on 1-N, N-1, and N-N relations.
Experiment Setup. Following the procedure of Bordes al. (2013). we have categorized the relations of WN18RR into four cardinality classes, specifically 1-1, I-N, N-1, and N-N. As in Bordes et al. (013), have classified relation E R by computing:
37

---

Published as a conference paper at ICLR 2023
Mrt the averaged number of head entities h E per tail entity E E, appearing in triple
r(h, t) of WN18RR.
Myb the averaged number of tail entities E per head entity E, appearing a triple r(h, t) of WN18RR.
Following the soft classification of Bordes et al. (0013. relation is:
1-1 if (Art & 1.5 and (4rh Σ 1.5
1-N if Prt I 1.5 and Prhh 2 1.5
if Prt 2 1.5 and Prhh $ 1.5
N-N prt 2 1.5 and ply. 2 1.5
Table 9: MRR of ExpressivE, RotatE, and BoxE on WN18RR stratified by cardinality classes (1-1,
I-N, N-1, N-N). The best results are bold, and the second-best are underlined.
Task
Predicting Head
Predicting Tail
Cardinality
1-1
1-N
N-1
N-N
1-1
I-N
N-1
N-N
ExpressivE
0.976
0.290
0.105
0.941
0.976
0.141
0.327
0.938
RotatE
0.833
0.294
0.103
0.930
0.875
0.107
0.288
0.925
BoxE 0.877
0.272
0.146
0.883
0.893
0.147
0.246
0.884
Results. Table 9 summarizes the performance results of ExpressivE and its closest spatial relative BoxE and functional relative RotatE on WN18RR, stratified by the four cardinality classes defined previously. It reveals that ExpressivE almost exclusively reaches SotA or close-to-Sott. performance on I-N, N-1, and N-N relations. In particular, ExpressivE outperforms both RotatE and BoxE consistently N-N relations, which are often considered the most complex relations to capture in KGC with regard cardinalities. Thus, Table provides empirical results supporting our thcoretical claim that ExpressivE capture 1-1, 1-N, N-1, and N-N relations well.
1.2 GENERAL COMPOSITION AND LINK TO PERFORMANCE GAIN
This section provides empirical evidence for the thcoretical result of Appendices F and G that ExpressivE can capture general composition exactly and exclusively. Even more, the experiments of this section give evidence for direct link between the support of general composition and ExpressivE's performance gain on WN18RR. In the following, we first discuss our experiments' preparation and setup details, followed by the considered hypotheses and final results.
Pattern Identification. Our first goal, to provide empirical evidence for the discussed points, was to identify patterns occurring in WN18RR, To reach this goal, have analyzed patterns mined with a GitHub repository" [ To identify the most relevant patterns, we have similar the discussion of (Galáragaa et al. 2013 2015) sorted the patterns dB1 A... A d.m + r(X, Y) by their head
AMIE+ (Galárraga et al. 2015) from WN18RR by Akrami et al. (2020) that were provided
coverage h(p), which is formally deñned (Galárraga al. 2013):
B h(p) M(x,,) ) E E² ((x,,)) v) E EGA 12 2 (21, 22) G A..... A @ (2 2x) E G))
1((z, v) E E² r(z, v) E GH
On an intuitive level, the head coverage hp))) represents the ratio of true triples implied by the pattern p given knowledge graph (G, E, R).
Pattern Selection. To analyze the most relevant patterns in the following experiments, we have selected any patterns whose head coverage is greater than 15% (as inspection of the head coverage of AMIE shows a very low number of inferred triples contained in the test set below that). From these patterns, we have left out any pattern with the head relation similar to, as ExpressivE, BoxE, and RotatE already have an MRR of on this relation, thus further stratifying _similar, to 's test
38

---

Published as a conference paper at ICLR 2023
triples will not reveal novel information. This procedure leads to the following set of patterns, where relations r- represent the inverse counterpart of relations r E R:
S1 = verb_ parb_group(YYX] = _veb (ertb_rooupxX)
C2 = derivaatonalllg_rrateed (otntteddooommXXXXYY (X,Y) A
C3 = dervantionallyreeteeeeffoomm (Y, ; _eeb peerb_group(X, 2)
derivationnally_reatted.. '(Y,)) _erb grtubbrroup(... Z)
C4 = deriuatioonally_rrltteddd A A
(Y, + _verb carbb_rouup_... Z)
C5 = olso_see , Y) _lso alsoolsssseeeeeee see (Y, YY _also__see (x, Z)
C. = also see X, Y) also_sss see ZY = _also seel X, Z)
S see (Y, X) = also__seel seel (X,Y)
Cs = hypernym(XX, Y)
synset__ symset_domain domain _twpai_ttopcceaaa___eiee_ee_eee of
of (Y,Z) _syseet____ ficet__domiin_o ceptaaiinttpici... topic_ofpXp
Experimental Setup. For each of these patterns p we have computed all triples that (i) can be derived by from the data known to our model and (ii) are known to be true in the KG. yet unseen to our models. Thus, for each pattern / we have computed the set 8p, containing all triples that (i) can be derived with from the training set and (ii) are contained in the test set of WN18RR We have used each the computed sets of triples sp to evaluate the performance of ExpressivE, BoxE, and RotatE on the corresponding pattern p.
Hypotheses. Note that (as discussed Appendix K. compositional definition ri (x, Y) A rY, Z) + (X, Z) defines the triples of the composite relation F3 completely, whereas gen- eral composition rı (X(, Y) A (2 + ra(X, Z) allows Ta to contain more triples than those that the compositional definition pattern can directly infer. Thus, if ExpressivE captures general composition and if RotatE captures compositional definition, we expect the following behavior:
H1. RotatE will perform well solely on relations occurring as the head of maximally one composition pattern, RotatE solely supports compositional definition.
H2. ExpressivE will perform well even when a relation is defined by multiple composition patterns and/or multiple other patterns since ExpressivE supports general composition.
Table 10: MRR of ExpressivE, RotatE, and BoxE WN18RR stratified by patterns Si-Cs. S,
represents a [Slymmetry pattern, C [C]omposition pattern (i E (1,...,8)).
Head Rel.
verb group
also see
syn_dto syn_ dto
Model
S
C2
C3
C₁
C's
Cg 0.907
S 0.985
Cs
Base Exp.
1.000
1.000
1.000
1.000
0.818
0.621
RotatE 0.865
0.760
0.760
0.760
0.771
0.893
0.975
0.599
BoxE 0.906
0.801
0.806
0.806
0.632
0.645
0.727
0.547
Results. Table 10 lists for each pattern Si to Css the performances of BoxE, RotatE, and ExpressivE Sp. where {SI..... Cs} and where S; represents symmetry pattern and C, represents composition pattern. Table providds evidence for both hypotheses:
Evidence for H1. In the case of the relation is only one pattern that has synnet____ domain ttppt_topi_______ of as its head relation, specifically the composition pattern Cs. RotatE achieves comparable performance to ExpressivE on sc, as RotatE is capable of defining _ssssst______.m _synset_ddomainn providing evidence for H1.
lopptttoopo_oooooooo (_sy_dtto), there
syyset__dmmain
of using compositional definition,
39

---

Published as a conference paper at ICLR 2023
Evidence for H2. Yet, when relation is defined via multiple patterns, RotatE's performance decreases drastically on most composition patterns compared to ExpressivE's performance, can be seen for the patterns C2. C3. Ca. and Cs. giving evidence for H2.
Conclusion Thus, these experiments provide empirical evidence for (1) ExpressivE can capture general composition, as ExpressivE and RotatE perform as expected by HI and H2 under the assumption that ExpressivE captures general composition and that RotatE captures compositional definition. Furthermore, the experiments also provide evidence for (2) ExpressivE's 's ability to capture general composition contributes to the performance gain on WN18RR, as ExpressivE consistently outperforms RotatE and BoxE on the predicted triples of composition patterns.
1.3 MULTIPLE STEPS OF COMPOSITION
In this section, we provide empirical evidence for the theoretical results of Appendix H how well ExpressivE supports more than one step of composition pattern, our first goal was to identify multi-step patterns (i.e., patterns that can be "chained" in multiple steps) occurring in WNI8RR. We now recall parts of Appendix [.2 for the self-comtainedness of this section readers who have read that section can skip ahead to the "experimental setup" paragraph. To reach the goal of identifying multi-step patterns occurring in WN18RR, we have analyzed patterns mined with
To evaluate
AMIE+ (Galárraga et al. 2015) from WN18RR by /Akrami et al. (2020) that were provided in
GitHub repository | To identify the most relevant patterns, we have similar to the discussion of
(Galárraga et al. 2013 2015) sorted the patterns p
ΦBi A... A 6Bm + rxX, Y) by their head
coverage hp), which is formally defined as (Galárraga et al. 2013):
h(p) [(x,y) y) E E r(x, v) E GA
... ... Ze(081 (21, 22) E G GA.... A Q (#k-1; 2x)) E G
((zz, v) E E²
r r(x, v) E G)|
On an intuitive level, the head coverage h(p) represents the ratio of true triples implied by the pattern p on given knowledge graph (G, E, R).
Next, we present the four multi-step patterns with head coverage of at least 15%, as discussed in Appendix I.2]
R1 (X)) A
synset fortt_dommmnnttee toopi_tppppppo (Y, +
of, 2)
Rg = also see(X, Y) A also see see(Y, Z) also_sse(_X, Z)
R3 = also see [, K Y) also_seee''""s__________a_aa_e sse (Y, Z) = aaso__see__ (X, Z)
R4 = also_see' _se (X,Y) A also see 1 |Y, 2) + alsoa_sssaa0o_oa see X, 2)
The relation _also_seee of R3 and R4 represents the inverse relation of ___sl__ssee
Experimental Setup. For each of the selected multi-step patterns p E (R,, R2, Ra, Ra we have generated three datasets, the 1-Step, 2- 2-Steps, and 3-Steps sets. Specifically, we have generated for each p a j-Step(s) set by computing all triples that (i) can be derived by p in j steps from the data known our model and (ii) are known to be true in the KG, yet unseen to model. Thus, have computed for each p a j-Step(s) set, containing all triples that (i) can be derived with p by applications on the training set and (ii) are contained in the test set of WN18RR. The performance of ExpressivE on the computed datasets is summarised in Table II
Results. We report the performance of most two steps of R//R//R4 as after applying R R4 twice on the training set; no new triples are derived. Similarly, no new triples are derived after at most three steps of R2 on the training set. We can that the performance of ExpressivE increases by a large margin when more than one step of reasoning is considered, depicted by the performance gain of the 2-Steps and 3-Steps set over the 1-Step set. Interestingly, small exception for this is R1, where we see slightly worse behavior inspection of the results shows that this is due to single triple. In total, Table TT provides empirical evidence that ExpressivE can capture chained composition patterns and thus perform more than one step of reasoning.
40

---

Published as a conference paper at ICLR 2023
Table 11: ExpressivE's MRR on WNI8RR in dependence the number of reasoning steps. Hyphens represent that no new triples can be inferred with additional steps.
1-Step
2-Steps
3-Steps
4-Steps+
R1
0.627
0.621
R2
0.720
0.804
0.818
R3
0.768
0.907
R4
0.716
0.922
J DETAILS OF THE DISTANCE FUNCTION
In this section, we give additional details on the distance function of Equation
3 As in Section 4 let
(h,t) denote the embedding of triple ri rh,,, t), i.c. (r.(h.t) = (Eht c r een) with
Ewy- = (e=lley) and a ay (a aa for a E {c,r,d) and æ, y E (h, t).
The distance function D E R E 2d of Equation 3 measuring the distance of entity pair embeddings (points) to relation embeddings (hyper-paralleloogaams) - split into two parts:
Tru(h,)) 2 w; for points inside the corresponding relation hyper- parallelogram, i.e., (bb,)) 3 dj.
Di(h, ri, r),t)
Do,h,rs, = (h.t) 2 - k for points outside the corresponding relation hyper- parallelogram, i.e., (b,,), di.
Intuition. As briefly explained in Section the general idea splitting the distance function is to assign high scores to entity pair embeddings within hyper-paraa hyper-parallelogram and low scores to entity pair embeddings outside the hyper--aralleelnn
Specifically, if triple rh, t) is captured to be true by ExpressivE embedding. i.e., if Tr: (h.4) dh then the distance correlates inversely with the hyper-parallee ppper-parallelogram's width - through the width-dependent factor w; - keeping low Otherwise, the distance correlates
distances/gradieets for points within the byper-paralleloe again through the width- detth-eeeendntt factor w. linearly with the width to penalize points outside larger parallelograms.
K EXPREsSIVE's TWO NATURES
In this section, analyze functional and spatial models in more detail and outline how ExpressivE combines the capabilities of both model families. ExpressivE has two natures, specifically:
ExpressivE has functional nature (in the spirit of functional models such TransE and RotatE), allowing it to capture functional composition, discussed in detail in Appendix K.
ExpressivE has a spatial nature (in the spirit of spatial models such as BoxE), allowing it to capture hierarchy, discussed in detail in Appendix K.2
The combination of the functional and spatial nature is precisely the reason that allows ExpressivE to capture hierarchy and composition patterns jointly. In the following, review the inference capabilities of spatial and functional models and discuss how ExpressivE combines both the spatial and functional nature.
K.1 ANALYSIS OF FUNCTIONAL MODELS
We recall the definition of functional models provided in Section 3 which states that functional models basically embed relations as functions fr, : IKd + IKd and entities as vectors ej E K over some field KK These models represent true triples re(en, et) space.
(cx) in the embedding
Our analysis has revealed that the root cause that functional models cannot capture general composi- tion patterns lies within the functional nature of these models. essence, these models employ mainly functions to embed relations. This allows them employ functional composition fra = fr, fr, to
41

---

Published as a conference paper at ICLR 2023
capture composition patterns. Yet, employing functional composition defines the composite relation rd completely and thus represents a more restricted pattern that we call compositional definition (X, A (Y, Z) + 2)..
In contrast, general composition TI Y), A (2( its composite relation r3- This means that in the case of general composition, the composite relation r3 may contain more triples than those that are directly inferable by compositional definition patterns. Due to this notion of extensibility, we can describe general composition as combination of compositional definition and hierarchy, i.e., a general composition pattern defines its composite relation r3 as a superset (hierarchy component) of the compositionally defined relation ra- This explains why no KGE has managed to capture general composition, as any SotA KGE that supports some notion of composition cannot represent hierarchy and vice versa (as will be discussed in Appendix K. . yet both are essential to support general composition. Therefore, to capture general composition, ExpressivE combines hierarchy and compositional definition patterns, as discussed in more detail in Section 5.2
= ra 2) does not completely define
K.2 ANALYSIS OF SPATIAL MODELS
Spatial models embed relation R via spatial regions in the embedding space. Furthermore, they embed an entity ea E E in the role of a head and tail entity with two independent embeddings ea E K" and ea E K A triple r(en, et) true for spatial models if the embeddings of the entities ej. and et lie within the respective spatial regions of the relation Thus, spatial models may capture hierarchy patterns via the spatial subsumption of the regions defined by the relations. However. since there is no relation between ex and eg. spatial models such as BoxE (Abboud et al. (0200) cannot capture composition.
ExpressivE embeds relations as regions (spatial nature). Yet to achieve the functional nature, it cannot use two independent entity embeddings in the typical embedding space as we discussed above. The solution and key difference to BoxE is to define the virtual triple space, which is formed by concatenating head and tail entity embeddings of the same embedding space (as described in detail in Section 4). More specifically,, any line through the virtual triple space defines a function between head and tail entity embeddings of the same space the key to the functional nature:
Functional nature. Regions in this virtual triple space establish a mathematical relation between head and tail entities of the same space, by which composition can be captured.
Spatial nature. At the same time, regions can subsume each other, by which as is intuitive - hierarchy patterns can be captured.
Finally, it is precisely the combination of the functional and spatial nature that allows ExpressivE to capture general composition, as described in detail in Section 5.2
L TRADE-OFF: EXPRESSIVE POWER VS. DEGREES OF FREEDOM
This section discusses the trade-off between higher expressive power and lower degrees of freedom, observable in the results of Table 3 Specifically, this trade-off manifests in Table 3 benchmark results in the following way:
Functional ExpressivE has lower expressive power compared Base ExpressivE it effectively loses the ability to capture hierarchy patterns. The effect of the reduced expressive power of Functional ExpressivE can be seen in the performance drop on WN I 8RR over Functional ExpressivE in Table 3 However, since Functional ExpressivE uses fewer parameters than Base ExpressivE, it has lower degree of freedom, making less likely to stop in a local minimum than Base ExpressivE as can be seen on Functional ExpressivE's performance on 151-5-237 in Table
Base ExpressivE E has the full expressive powers the high degree of freedom heightening the chance of ending in local minimum. Table 33 reveals the significant performance increase of Base ExpressivE over Functional ExpressivE on WNISRR, giving evidence that the expressive power is helpful, but the downside being that its higher degrees of freedom
42

---

Published as a conference paper at ICLR 2023
may make it likelier stop in local optimum, manifesting in its performance drop Functional ExpressivE on FB15k-237.
Further analyzing this trade-off establish link between dataset properties and the necessary expressive power of KGE will be subject for interesting future work.
M EXPERIMENTAL DETAILS
This section discusses our experiment setup, benchmark datasets, and evaluation metrics in detail. The concrete experiment setups, including details of our implementation, used hardware, learning setup, and chosen hyp hyperparameters, are discussed in Subsection M.I] Subsection [M. lists properties of the used benchmark datasets and Subsection M.3
lists properties of the used ranking metrics.
M.1 EXPERIMENT SETUP AND EMISSIONS
Implementation Details. We have implemented ExpressivE: in PyKEEN 1.7 (Ai et al. which is Python library that uses the MIT license and supports many benchmark KGs and KGES. Thereby, we make ExpressivE comfortably accessible to the community for future benchmarks and experiments. We have made our code publicly available addition to the code of ExpressivE, a setup file to install the necessary libraries and ReadMe. md file containing library versions and running instructions to facilitate the reproducibility of our results.
2021) D,
GitHub repository It contains, in
Training Setup. Each model was trained and evaluated on one of 4 GeForce RTX 2080 GPUs of our internal cluster. Specifically, the training process uses the Adam optimizer (Kingma & Ba 2015 to optimize the self-adversarial negative sampling loss (Sun et al. 2019). ExpressivE is trained with gradient descent for up to 1000 epochs with early stopping, finishing the training after 100 epochs the Hits @ 10 score did not increase by at least 0.5% for WNI8RR and 1 1% for FB15k-237. We have increased the patience for OneBand ExpressivE to 150 epochs for FBI 153-237, as it converges slower than the other ablation versions of ExpressivE. We use the model of the final epoch for testing. Each experiment was repeated three times to account for small performance fluctuations. In particular, the MRR values fluctuate by less than 0.003 between dataset. We performed hyperparameter tuning over the learning rate X, embedding dimensionality number of negative samples neg. loss margin 7, adversarial temperature a, and minimal denominator D man Specifically, two mechanisms were employed to implicitly regularize the pyper-parallelogrmm: (1) the hyperbolic tangent function tanh was element- wise applied to each entity embedding ep- slope vector r.. and center vector c², projecting them into the bounded space [- 1, 1]d, and (2) the size of each hyper-pune paeeerrallllogrmm is limited by the novel Dmn parameter. In the following, we will briefly introduce the D Din parameter and its function.
for Base and Functional ExpressivE any
Minimal Denominator Dmnn
As can be easily shown, Equations 108 describe the relation hyper- parallelogram's center, and Equations 109 110 its corners the virtual triple space.
h +
c ph
r c + ct
center,"
and
center! 1 - r
(108)
cornA center + dh + r
d + d plp!
and
cornA centert
(109)
r!
dh r
corn center = r dh d rh
cornB center 1 r
and
(110)
Note that the denominator of each term is equal to (1 r Since a small denominator in Equations 109 and 110 produces large corners and, therefore, a large hyper-parallelogram. we have introduced the hyperparameter Dmin allowing ExpressivE tune the maximal size of its hyper- parallelograms. In particular, Dmnn. constrains the relation embeddings such that (1 - r 3 D D thereby constraining the maximal size of hyper- parallallalelogram as required.
"haps://gituu..cmm// Alcks Vap/FxpressivE.
43

---

Published as a conference paper at ICLR 2023
Hyperparameter Optimization. Following Abboud et al. (2020), have varied the learning rate by À E {a 10 -0- l E {1,2,5} A b E (-2, -4, 5, -]}. the margin m by integer values between 3 and 24 inclusive, the adversarial temperature by {1, 3, 4), and the number of negative samples by neg E (50, 100, 150). Furthermore, we have varied the novel minimal denominator parameter by mén {0, 0.5, 1). We have tuned the hyperparameters of ExpressivE manually within the specified ranges. Finally, to allow direct performance comparison of ExpressivE its closest spatial relative BoxE and its closest functional relative RotatE, we chose for each benchmark the embedding dimensionality and negative sampling strategy of the best- best-performing RotatE and BoxE model (Abboud et al., 2020 Sun al. 2019). Concretely we chose sels-aaversarial negative sampling (Sun et al.] (019) and the embedding dimensionalities listed in Table 12 The best performing hyperparameters for ExpressivE on each benchmark dataset are listed in Table 12 We have used the hyperparameters of Table 12 for any considered version of ExpressivE
namely Base,
Functional, EqSlopes, NoCenter, and OneBand ExpressivE -, which are described in the ablation study of Section 6.2
Table 12: Hyperparameters for the best-performing ExpressivE models on WNISRR and FB F51--2377.
Embedding Dimensionality
Learning Rate
Adversarial Temperature
Negative Samples
Batch Size
Minimal Denominator
Dataset
Margin
WNISRR
500
3
1 10-3
2
100
512 1024
0 0.5
FB 15k-2733
1000
10
150
C02 Emission Related to Experiments. The computation of the reported experiments took below 200 GPU hours. On an RTX 2080 (TDP of 215W) with carbon efficiency of 0,432 kg/kWh (based on the OECD's 2014 yearly carbon efficiency average), 200 GPU hours correspond to a rough CO2 emission of 18.58 kg -e. The estimations were conducted using the MachineLearning Impact calculator (Lacoste et al.; 2019).
M.2 BENCHMARK DATASETS
This section briefly discusses some details of the standard KGC benchmark datasets WNISRE (Dettmers al. 2018) and FB15k- 15k-237 (Toutanova & Chen 2015). In particular, Table 13 lists the following characteristics of the benchmark datasets, namely their number of: entities ET relation types R training. testing, and validation triples. Both WN18RR and FB15k-237 provide training, lesting, and validation splits, which were directly used in our experiments.
Table 13: Benchmark dataset characteristics.
Dataset
[
|R|
Training Triples
Validation Triples
Testing Triples
FB 15k-237
14,541
237
272,115
17,535
20,466
WN18RR
40,943
11
86,835
3,034
3,034
We have not found licenses for FB15k-237 nor WNISRR. WNISRR is subset WNI8 (Bordes et al. 2013), whose license is also unknown, yet FB15k-237 is subset of FB15k (Bordes et al. 2013
that uses the CC BY 2.5 license.
M.3
METRICS
We have evaluated ExpressivE by measuring the ranking quality of each test set triple ry re(en, ex) over all possible head e/, and tail et: rz(ch, ex) for all e/, E E and re(en, et) for all et E. The mean reciprocal rank (MRR), and Hits@ are the standard evaluation metrics for this evaluation (Bordes) al. 2013). In particular, we have reported the filtered metrics (Bordes et al. 2013). i.e., where all triples that occur in the training, validation, and testing set (except the test triple that shall be ranked) removed from the ranking, as ranking these triples high does not represent faulty inference. Furthermore, the filtered MRR, Hits@ I, Hits @ 3, and Hits @ 10 are the most widely used metrics for evaluating KGEs (Sun al. 2019
Trouillon et al. 2016
Balazevic al. 2019 Abboud et al. 2020).
44

---

Published as a conference paper at ICLR 2023
Finally, we will briefly discuss the definitions of these metries: the MRR represents the average of inverse ranks (1 (L/rank), and Hits@ k represents the proportion of true triples within the predicted triples whose rank is at maximum k.
45


Reviews:
[{"review_id": "uwmazZLg4uW", "reviewer": "Reviewer_kHNH", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel spatial KGC model that can capture many inference patterns, including compositional and general compositional. In specific, the authors define each entity as points in the vector space, and each relation as hyper-parallelograms in the virtual triple space, which is constructed by the concatenation of head and tail entity vectors and the jth and (d+j)th dimensions bring a correlation subspaces. Thus, the intersection of two parallel half-spaces constitute a band and two bands form a parallelogram to post constraints on the triple. Furthermore, the authors provide proof on the proposed model's capacity in modeling various types of inference patterns. In experiments, the results on two widely used datasets show improvements.", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strengths:\n1. The paper is well motivated and presented.\n2. The proposed method is insightful and elegant.\n3. The experiments demonstrate the effectiveness.\n\nWeaknesses:\n\nI didn't see any weaknesses of the paper, except some minor questions:\n\n1) Will the proposed method bring too much expressiveness, and thus weaken the generalization ability to capture more inference pattersn using limited data?\n\n2) In the section parameter interpretation, why does the intersection of two bands result in another band?\n\n3) In Section Scoring Function, please provide more explanation of why k keeps the function continuous.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "UM9EZqpqFI", "reviewer": "Reviewer_MZLX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a spatio-functional embedding model named ExpressivE, which has the benefits of both region-based and functional models. Compared to present methods, ExpressivE can (1) fully capture vital inference patterns, (2) capture prominent logical rules jointly, and (3) provide an intuitive interpretation of captured patterns. The following experiments on the KGC benchmarks showed the great performance of ExpressivE.", "summary_of_the_review": "This paper solves previous KGC embedding methods' incapability of several inference patterns.\nThe proposed methods are both powerful and explainable.\nThe article is valuable and worth being accepted.", "strength_and_weaknesses": "Pros\n- This paper can fully capture vital inference patterns(e.g., capturing both general composition and hierarchy jointly), which is meaningful for KGC.\n-  Interpreting multiple inference patterns within the virtual triple space is interesting.\n- The analysis of ExpressivE's expressive power is convincing.\n- The experiment results(especially on WN18RR) are satisfied.\n\nCons\n- Currently, there are no critical problems in this paper for me.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "GQbEAa1AEJt", "reviewer": "Reviewer_cMBH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a knowledge graph completion model that is fully expressive and can capture some inference patterns. The most important inference pattern that the proposed model is able to capture is general composition. This is mainly because many existing models cannot capture composition. The experiments show the model is competitive with the state-of-the-art on FB15k-237 and outperforms the baselines on WN18RR. ", "summary_of_the_review": "**Questions**\n\n\"Vital\" inference patterns: I would like the authors to elaborate more on why the set of inference patterns in Table 1 is considered vital. Also, what are some of the patterns that the proposed model cannot capture (limitations of the proposed model)?\n\nReading through the main paper, I do not seem to get what is the main property of ExpressivE that causes it to be able to capture composition. The proposed mode is similar to the class of models that BoxE belongs to. Why BoxE cannot model composition but ExpressivE can. Can the authors elaborate more on this with intuitions?\n\nCan the authors elaborate more on whether ExpressivE can model $r_1(X, Y) \\land r_2(Y,Z) -> r_3(X, Z)$ and $r_3(X, Y) \\land r_4(Y, Z) -> r5(X, Z)$? This is more challenging as there are multiple steps of reasoning needed to be done to be able to capture a composition of multiple steps.\n\n**Minor**\n\nSome references in the appendix to the Theorems seem to be broken.", "strength_and_weaknesses": "**Strengths**\n\nMany existing papers have tried to model inference patterns and one that many baselines fail to capture is general composition.\n\n**Weaknesses**\n\n\nDatasets: Recent works [1, 2] show that previous existing KG completion benchmarks have quality issues. For instance, [1] has shown that a large percentage of relations in FB15K-237 could be covered by a trivial frequency rule. Also, there are recent KGs available in ogbl-biokg and wikikg datasets that are of larger scale and closer to practical cases. \n\n[1] Tara Safavi and Danai Koutra. CoDEx: A Comprehensive Knowledge Graph Completion Benchmark, EMNLP 2020.\n\n[2] Genet Asefa Gesese, Mehwish Alam, and Harald Sack. LiterallyWikidata - A Benchmark for Knowledge Graph Completion Using Literals, SEMWEB 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5Ve7V8mLJ29", "reviewer": "Reviewer_KcUq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new geometry-based knowledge graph embedding method named ExpressivE, which represents entities as points and relations as hyper-parallelograms. Extensive theoretical analyses show that ExpressivE is fully expressive and is capable of capturing various inference patterns. Experiments demonstrate that ExpressivE achieves competitive performance.", "summary_of_the_review": "This paper proposes a novel geometry-based knowledge graph embedding model for knowledge graph completion. It has many theoretical merits and obtains competitive results. However, I think this paper can be greatly improved if some concerns about the Strength And Weaknesses can be properly addressed, and I am open to raising my score if the authors manage to do it.\n\n======Update After Rebuttal======\nI am satisfied with the authors' response and raise my score accordingly.", "strength_and_weaknesses": "## Strength\n1. The idea of using hyper-parallelograms to design a new KGE model seems novel and interesting to me.\n2. The proposed model has many good properties and the authors provide rigorous theoretical proof for them.\n3. The model performs well while using only half the parameters compared with the previous state-of-the-art methods.\n4. The authors did a good job of introducing the background and related work.\n5. This paper is clearly written and well organized.\n\n## Weakness \n1. **Abstract**  \n    The authors claim that ExpressivE can capture prominent *logical rules* jointly. However, the term *logical rules* never appears again in the main text. So what does this claim mean?\n2. **Motivation**  \n    The main motivation of this work is to capture general composition and the authors claim that the ability to capture it is vital for KGE models to reason over graphs. However, is there any evidence to support this claim? I admit that it'd be better if a model can capture general composition, but there may not exist a strong connection between this ability and the final KGC performance.\n3. **Method**  \n    3.1 What does the term $\\mathbf{w}_i$ in Equation (3) stand for?    \n    3.2 The authors list some key properties of ExpressivE on Page 7, while there lacks necessary support for them. For example, the authors may want to give some graphic examples to show the intuitive geometric interpretation. Experimental results for 1-n, n-1, and n-n relations should be provided to support the third properties.\n4. **Experiments**  \n    4.1 I am confused about the worse performance of Base ExpressivE compared with Functional ExpressivE on FB15k-237. Even if FB15k-237 does not contain many hierarchy patterns, I expect that the base version of ExpressivE performs no worse than the functional one, since the width can be learned to be zero. Otherwise, the proposed method can only perform well on knowledge graphs with some special properties, which will significantly limit its applicability.    \n    4.2 It'd be better conduct experiments to show that ExpressivE can indeed model general composition, since it is the main contribution of this work.\n5. **Reproducibility**    \n    The authors claim that they have included the supplementary material via a link in an OpenReview comment. However, I cannot find the link.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%