Geometric Models for (Temporally) Attributed Description Logics

Abstract

In the search for knowledge graph embeddings that could capture ontological knowledge, geometric models of existential rules have been recently introduced. It has been shown that convex geometric regions capture the so-called quasi-chained rules. Attributed description logics (DL) have been de ned to bridge the gap between DL languages and knowledge graphs, whose facts often come with various kinds of annotations that may need to be taken into account for reasoning. In particular, temporally attributed DLs are enriched by speci c attributes whose semantics allows for some temporal reasoning. Considering that geometric models and (temporally) attributed DLs are promising tools designed for knowledge graphs, this paper investigates their compatibility, focusing on the attributed version of a Horn dialect of the DL-Lite family. We rst adapt the de nition of geometric models to attributed DLs and show that every satis able ontology has a convex geometric model. Our second contribution is a study of the impact of temporal attributes. We show that a temporally attributed DL may not have a convex geometric model in general but we can recover geometric satis ability by imposing some restrictions on the use of the temporal attributes.

-

Knowledge graph embeddings are popular latent representations of knowledge graphs (KG). In the search for KG embeddings that could capture ontological knowledge (i.e., schema of KG), geometric models of existential rules have been recently introduced [ 14 ]. Such models have several advantages. Notably, they ensure that facts which are valid in the embedding are logically consistent and deductively closed w.r.t. the ontology, and they can also be used to nd plausible missing ontology rules. It has been shown that convex geometric regions capture the so-called quasi-chained rules, a fragment of rst-order Horn logic. Attributed description logics (DL) have been de ned to bridge the gap between DL ontology Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). languages and KG, whose facts often come with various kinds of annotations that may need to be taken into account for reasoning. In particular, they were introduced as a formalism for dealing with the meta-knowledge present in KG, such as temporal validity, provenance, language, and others [ 17, 18, 8 ]. As time is of primary interest in KG, attributed DLs have been enriched with temporal attributes, whose semantics allows for some temporal reasoning over discrete time [ 23 ]. Considering that geometric models and (temporally) attributed DLs are promising tools designed for KG, this paper investigates their compatibility, focusing on the attributed version of a Horn dialect of the DL-Lite family.

Our contributions are as follows: { We adapt the notion of geometric models for ((temporally) attributed) DLs; in particular, we use an arbitrary linear map to combine the individual geometric interpretations instead of restricting ourselves to vector concatenation, and de ne satisfaction of concept or role inclusions directly based on geometric inclusion relationship between the regions that interpret the concepts or roles. { We show that every satis able attributed DL-LitehHorn ontology has a convex geometric model but there are satis able temporally attributed DL-LitehHorn ontologies without such a model. { We exhibit restrictions on the use of temporal attributes that guarantee that temporally attributed DL-LitehHorn ontologies have a convex geometric model.

We de ne attributed DLs and geometric models in Section 2. Then, in Section 3, we study the relationship between satis ability and the existence of convex geometric models in DL-LitehHorn . We then extend our analysis for temporally attributed DL-LitehHorn in Section 4. In Section 5, we discuss related works and we conclude in Section 6. Omitted proofs are given in [ 9 ]. 2

Geometric Models for Attributed Description Logics In this section, we recall the framework of attributed DLs and de ne geometric models in this context. 2.1

Attributed DLs

We introduce attributed DLs by de ning attributed DL-Lite [ 8 ], focusing on the DL-LitehHorn dialect. The notions presented here can be easily adapted to other attributed DLs, e.g. E L, as in [ 17, 18 ]. Let NC, NR, and NI be countably in nite and mutually disjoint sets of concept, role, and individual names. We assume that NI is divided into two sets, called Ni and Na, and we refer to the elements in Na as annotation names. We consider an additional set NU of set variables and a set NV of object variables. The set S of speci ers contains the following expressions: { set variables X 2 NU; { closed speci ers [a1 : v1; : : : ; an : vn]; and { open speci ers ba1 : v1; : : : ; an : vnc, where ai 2 Na and vi is either an individual name in Na, an object variable in NV, or an expression of the form X:a, with X a set variable in NU and a an individual name in Na. We use X:a to refer to the ( nite, possibly empty) set of all values of attribute a in an annotation set X. A ground speci er is a closed or open speci er built only over Na. X : S

(P v Q); where S 2 S is a closed or open speci er, X 2 NU is a set variable, and P; Q are role expressions built according to the following syntax:

Q := P j :P (1) (2) (3) (4) X1 : S1; : : : ; Xn : Sn

k ( l Bi v C); i=1 where k; n 1, S1; : : : ; Sn 2 S are closed or open speci ers, X1; : : : ; Xn 2 NU are set variables, and Bi; C are concept expressions built according to:

C := B j ?; where P is as in Equation (2), A 2 NC and S 2 S. Role expressions of the form P are called roles and concept expression of the form B are basic concepts. We further require that all object variables are safe, that is, if they occur on the right side of a concept/role inclusion or in a speci er associated with a set variable occurring on the right side then they must also occur on the left side of the inclusion (or in a speci er associated with a set variable occurring on the left).

A DL-LitehHo;r@n ontology is a set of DL-LitehHo;r@n assertions, role and concept inclusions. We say that an inclusion is positive if it does not contain negation or ?. Also, we say that a DL-LitehHo;r@n ontology is ground if it does not contain variables. To simplify notation, we omit the speci er bc (meaning \any annotation set") in role or concept expressions. In this sense, any DL-LitehHorn axiom is also a DL-LitehHo;r@n axiom. Moreover, we omit pre xes of the form X : b c, which state that there is no restriction on X.

Semantics. An interpretation I = ( iI ; aI ; I ) of an attributed DL consists of a non-empty domain iI of individuals, a non-empty domain aI of annotations, and a function I . Individual names a 2 Ni are interpreted as elements aI 2 iI and individual names a 2 Na are interpreted as elements aI 2 aI . To interpret annotation sets, we use the set I := f aI aI j is niteg of all nite binary relations over aI . Each concept name A 2 NC is interpreted as a set AI iI I of elements with annotations, and each role name R 2 NR is interpreted as a set RI iI iI I of pairs of elements with annotations. Each element (pair of elements) may appear with multiple di erent annotations. I satis es a concept assertion A(a)@[a1 : v1; : : : ; an : vn] if (aI ; f(a1I ; v1I ); : : : ; (aIn; vnI )g) 2 AI . Role assertions are interpreted analogously. Expressions with free set or object variables are interpreted using variable assignments Z mapping object variables x 2 NV to elements Z(x) 2 aI and set variables X 2 NU to nite binary relations Z(X) 2 I . For convenience, we also extend variable assignments to individual names, setting Z(a) = aI for every a 2 Na. A speci er S 2 S is interpreted as a set SI;Z I of matching annotation sets. We set XI;Z := fZ(X)g for variables X 2 NU. The semantics of closed speci ers is de ned as: { [a: v]I;Z := ff(aI ; Z(v))gg where v 2 Na [ NV; { [a: X:b]I;Z := ff(aI ; ) j (bI ; ) 2 Z(X)gg; { [a1 : v1; : : : ; an : vn]I;Z := fSin=1 Fig where fFig = [ai : vi]I;Z for all 1 i

SI;Z therefore is a singleton set for variables and closed speci ers. For open speci ers, however, we de ne ba1 : v1; : : : ; an : vncI;Z to be the set: fF

I j F

G for fGg = [a1 : v1; : : : ; an : vn]I;Z g: Now given A 2 NC, R 2 NR, and S 2 S, we de ne: (A@S)I;Z := f j ( ; F ) 2 AI for some F 2 SI;Z g; (R@S)I;Z := f( ; ) j ( ; ; F ) 2 RI for some F 2 SI;Z g: Further DL expressions are de ned as: (R @S)I;Z := f( ; ) j ( ; ) 2 (R@S)I;Z g, :P I;Z := ( iI iI )nP I;Z , 9P I;Z := f j there is ( ; ) 2 P I;Z g, (B1uB2)I;Z := B1I;Z \ B2I;Z , ?I;Z := ;. I satis es a concept inclusion of the form (3) if, for all variable assignments Z that satisfy Z(Xi) 2 SiI;Z for all 1 i n, we have (dik=1 Bi)I;Z CI;Z . Satisfaction of role inclusions is de ned analogously. An interpretation I satis es an ontology O, or is a model of O, if it satis es all of its axioms. As usual, j= denotes the induced logical entailment relation.

For ground speci ers fS; T g S, we write S ) T if T is an open speci er, and the set of attribute-value pairs a : b in S is a superset of the set of attribute-value pairs in T . 2.2

Geometric Models

We now de ne the geometric interpretations of attributed relations. Let m be an integer and f : Rm Rm 7! R2 m be a xed but arbitrary linear map satisfying the following: (i) the restriction of f to Rm

0 m (ii) the restriction of f to f g (iii) f (Rm f0gm) \ f (f0gm 0 m is injective; f g

Rm is injective;

Rm) = f02 mg; where 0m denotes the vector (0; : : : ; 0) with m zeros. Intuitively, individuals will be interpreted as vectors from Rm and f will be used to combine two vectors to interpret pairs of individuals.

De nition 1 (Geometric Interpretation). An m-dimensional f -geometric interpretation of (NC; NR; Ni; Na) assigns { to each A 2 NC and ground S 2 S a region (A@S) { to each R 2 NR and ground S 2 S a region (R@S) { to each a 2 Ni a vector (a) 2 Rm.

Rm, R2 m, and Moreover, for all fS; T g S and E 2 NC [ NR, if S ) T then (E@S) (E@T ). We say that is convex if, for every E 2 NC [ NR, every ground S 2 S, every v1; v2 2 (E@S), and every 2 [0; 1], if v1; v2 2 (E@S) then (1 )v1 + v2 2 (E@S).

The interpretation of ground complex concept or role expressions is as follows. Assume all speci ers occurring in expressions below are ground, R 2 NR, P is a role, and B; Bi are basic concepts. Then, { { { { { (?) := ;. ((9dPin=)1:=Bif) : =j9T0in;=f1( (;B0i)),2 (P )g, We may omit \of (NC; NR; Ni; Na)" when we speak about m-dimensional f geometric interpretations. The interest of geometric interpretations is that concept and role assertions translate into membership in geometric regions and ground concept or role inclusions translate into geometric inclusions.

De nition 2 (Satisfaction of Ground Axioms). An m-dimensional f -geometric interpretation satis es

We are ready for the rst theorem which establishes that our more general notion of geometric models still has the same properties of the geometric models originally proposed [ 14 ].

Theorem 3. Let be an m-dimensional f -geometric interpretation. For every linear map f 0 satisfying (i)-(iii), the m-dimensional f 0-geometric interpretation 0 de ned as: { 0(a) := (a), for all a 2 Ni; { 0(A@S) := (A@S), for all A 2 NC and ground S 2 S; and is such that j= i

0 j= , for all ground axioms .

Proof (Sketch). This result follows from the fact that there is an isomorphism between the regions in and 0.

To de ne when a geometric interpretation is a model of a (possibly not ground) DL-LitehHo;r@n ontology, we need to de ne when such an interpretation satis es non-ground concept or role inclusions. To do so, we use a standard interpretation built from the geometric interpretation. Given a ground speci er S and an annotation name ?, we de ne FS? = f(a; b) j a: b occurs in Sg [ f(?; ?) j if S is openg. Given an m-dimensional f -geometric interpretation , a subset Da of Na and an annotation name ? 2 Na n Da, we de ne an interpretation I( ; Da?) as follows.

{ iI( ;Da?) = Rm and, for all a 2 Ni, aI( ;Da?) = (a); { aI( ;Da?) = Na and for all a 2 Na, aI( ;Da?) = a; { AI( ;Da?) = f( ; FS?) j 2 (A@S); S built on Dag, for all A 2 NC; { RI( ;Da?) = f( ; ; FS?) j f ( ; ) 2 (R@S); S built on Dag, for all R 2 NR.

The next proposition shows that and I( ; Da?) satisfy the same ground axioms built using only annotation names from Da. It follows in particular that satis es all ground axioms of an ontology O i I( ; N?O) does, where NO is the set of annotation names from Na that occur in O.

Theorem 4. Let be an m-dimensional f -geometric interpretation. Let be a ground axiom, i.e., is either a concept/role assertion or a ground concept/role inclusion. Let D be the set of annotation names that occur in and let D be a subset of Na such that D D. Let ? be an annotation name that does not occur in D. Then, the following holds: j= i I( ; D?) j= .

Proof (Sketch). The proof relies heavily on the de nition of FS? and the requirement that (E@S) (E@T ) when S ) T in De nition 1.

We are now ready to de ne geometric models of DL-LitehHo;r@n ontologies. De nition 5 (Geometric Model). Let O be a DL-LitehHo;r@n ontology, and let NO be the set of annotation names from Na that occur in O and ? an annotation name that does not occur in O. An m-dimensional f -geometric interpretation is a model of O if I( ; N?O) is a model of O. 3

Satis ability and Convex Geometric Models We start by recalling some de nitions and results on geometric interpretations of an ontology containing existential rules [ 14 ]. An existential rule is an expression of the form B1 ^ ^ Bn ! 9X1; : : : ; Xj :H where n 0, the Bi's and H are atoms built from sets of predicates, constants and variables, and the Xi's are variables. A negative constraint is a rule whose head is ?. An existential rule or negative constraint is quasi-chained if for all 1 i n, j(vars(B1) [ [ vars(Bi 1)) \ vars(Bi)j 1, where vars(B) denotes the variables that occur in B. It is easy to see that a DL-LitehHorn ontology without negative role inclusions can be translated into a quasi-chained ontology. Negative role inclusions are not quasi-chained: their translation to rules is indeed of the form P1(x; y) ^ P2(x; y) ! ? where the body atoms share two variables. A (standard) model M of an existential rules ontology K is a set of facts that contains all facts from K and satis es all existential rules from K. In this setting, for every fact , 2 M i M j= .

Given a set R of relation names and a set X of constants and labelled nulls, a m-dimensional geometric interpretation of (R; X) assigns to each k-ary relation R from R a region (R) Rk:m and to each object o from X a vector (o) 2 Rm. Tuples of individuals are interpreted using vectors concatenation, which plays the role of the linear map f we use to interpret a pair of individuals: for every R 2 R and o1; : : : ; ok 2 X, j= R(o1; : : : ; ok) if (o1) (ok) 2 (R). The authors de ne

( ) = fR(o1; : : : ; ok) j R 2 R; o1; : : : ; ok 2 X; j= R(o1; : : : ; ok)g:

Proposition 3 in [ 14 ] states that if K is a quasi-chained ontology and M is a nite model of K, then K has a convex geometric model such that ( ) = M. This transfers to the DL setting as follows. Let O be a quasi-chained DL ontology and J be a nite model of O such that J = Ni, and aJ = a for every a 2 Ni (which implies that for every concept A, if 2 AJ , then J j= A( ), and similarly for roles). Then O has a convex geometric model such that

fE(t) j j= E(t)g = fE(t) j J j= E(t)g; 4

Adding Time In this section, we discuss the ability of convex geometric models to capture temporally attributed DLs. We show that we need to restrict the expressivity of the temporal ontology to get a convex geometric model.

We introduce temporally attributed DLs by de ning temporally attributed DL-LitehHorn , called DL-LitehHo;rTn;@, as in [ 23 ]. The description logic DL-LitehHo;rTn;@ is de ned as a multi-sorted version of DL-LitehHo;r@n , where time points and intervals are seen as datatypes. Time points are elements of NT, and time intervals are elements of N2 . These sets and the set of (abstract) individual names NI are

T mutually disjoint. Time points are represented in a discrete manner by natural numbers, and we assume that elements of NT (N2T) are (pairs of) numbers. A pair of numbers k; ` in N2T is denoted [k; `].

The annotation names: time; before; after; until; since; during; between 2 Na are called temporal attributes and have their own semantics. Basically, time is used to mark a point in time and before and after refer to some point in the past and in the future, respectively. The temporal attributes until and since refer to all points in the past and all point in the future (e.g. since 2020 the KR conference became an annual event). Finally, during is an interval which represents a period of time (it refers to all points in the interval) and between is an interval of uncertainty for when an event happened. The value type of time; before; after; until; since is NT, while the value type of during; between is N2 . We write valtype(a) to refer to T the value type of the annotation name a. Object variables are now taken from pairwise disjoint sets Var(Na), Var(NT), and Var(N2T).

Annotation set speci ers are de ned as in Section 2.1 with the di erence that for each ai 2 Na and each vi in attribute value pair ai : vi we require compatibility between the value type of its attribute, that is: { vi 2 valtype(ai) [ Var(valtype(ai)), or { vi = [v; w] with valtype(ai) = N2T and v; w in NT [ Var(NT), or { vi = X:b with X 2 NU, b 2 Na, and valtype(ai) = valtype(b).

A time-sorted interpretation I = ( iI ; aI ; I ) is an interpretation with a domain aI that is a disjoint union of IA [ IT [ 2IT , where IA is the abstract domain of annotations, IT (the temporal domain) is a nite or in nite interval, and 2IT = IT IT . We interpret individual names in Ni as elements in iI ; annotation names in Na as elements in IA; time points t 2 NT as tI 2 IT ; and intervals [t; t0] 2 N2T as [t; t0]I = (tI ; t0I ) 2 2IT . A pair ( ; ) 2 IA aI is well-typed, if: 1. 2. 3.

= aI for an attribute `a' of value type NT and = aI for an attribute `a' of value type N2T and = aI for an attribute `a' of value type Na and 2 2 2

IT ; or 2IT ; or I .

A Let I be the set of all nite sets of well-typed pairs. The function I maps concept names A 2 NC to AI iI I and role names R 2 NR to RI iI iI I . The semantics of terms is given by variable assignments, which for a time-sorted interpretation I is de ned as a function Z that maps { set variables X 2 NU to nite binary relations Z(X) 2 I , and { object variables x 2 Var(NI) [ Var(NT) [ Var(N2T) to elements Z(x) 2 IT [ 2IT (respecting their types). For (set or object) variables x, we de ne xI;Z := Z(x), and for abstract individuals, time points, or time intervals a, we de ne aI;Z := aI . The semantics of speci ers is as in Section 2.1 with the di erence that values can also be time points and intervals: { [a: v]I;Z := ff(aI ; vI;Z )gg, with v 2 valtype(a) [ Var(valtype(a)); { [a: [v; w]]I;Z := ff(aI ; (vI;Z ; wI;Z ))gg, with valtype(a) = N2T, and v; w 2 NT [ Var(NT).

We are now ready to formally de ne the semantics of temporal attributes. De nition 7. Consider a temporal domain IT and a domain iI of individuals and a domain aI of annotations, and let (Ii)i2 IT be a sequence of (non-temporal) interpretations with domains iI and aI , such that, for all a 2 NI, we have aIi = aIj for all i; j 2 IT . We de ne a global interpretation for (Ii)i2 IT as a time-sorted interpretation I = ( iI ; aI ; I ) as follows. Let aI = aIi for all a 2 NI. For any nite set F 2 I , let FI := F \ ( IA IA) denote its abstract part without any temporal attributes. For any A 2 NC, 2 iI , and F 2 I with F n FI 6= ;, we have ( ; F ) 2 AI if and only if ( ; FI ) 2 AIi for some i 2 IT , and the following conditions hold for all (aI ; x) 2 F : { if a = time, then ( ; FI ) 2 AIx , { if a = before, then ( ; FI ) 2 AIj for some j < x, { if a = after, then ( ; FI ) 2 AIj for some j > x, { if a = until, then ( ; FI ) 2 AIj for all j x, { if a = since, then ( ; FI ) 2 AIj for all j x, { if a = between, then ( ; FI ) 2 AIj for some j 2 [x], { if a = during, then ( ; FI ) 2 AIj for all j 2 [x], where [x] for an element x 2 pair of numbers x, and j 2 analogously.

2IT denotes the nite interval represented by the I . For roles R 2 NR, we de ne ( ; ; F ) 2 RI

T De nition 8 (Temporal Geometric Interpretation). A temporal mdimensional f -geometric interpretation with temporal domain T is a sequence ( j )j2 T of m-dimensional f -geometric interpretations. An m-dimensional f geometric interpretation is global for ( j )j2 T and Da Na if I( ; (Da [ NT [ N2T)?) is global for (I( j ; Da?))j2 T .

Let NO denote the union of all elements in Na, NT, and N2T occurring in O. De nition 9 (Geometric Model). Let O be a DL-LitehHo;rTn;@ ontology. An f -geometric interpretation is an m-dimensional f -geometric model of O if it is global for a sequence ( j )j2 T of m-dimensional f -geometric interpretations and NO, plus I( ; N?O) satis es O.

Example 10 shows that even if temporal speci ers are only of the form time and during, convex geometric models may not exist for satis able DL-LitehHo;rTn;@ ontologies. and let be a convex f -geometric model of O. Let = 0:5 (a) + 0:5 (b). By the convexity of (R@[time: 1]) and (R@[time: 2]), we have that so I( ; N?O) j= R( ; )?O@)[tj=imAe:(1]).anHdenIc(e ;IN( ?;)Nj=?O)?OR6j)=(j=;9RR)@@@[[t[tidimmuerei:n:21g]]:. u[I1t;Af2o]vl]lov?w.AsT,thhwaiest O I( ; N?O) j= R( ; )@[during: [1; 2]]. Since I( ; N also have that I( ; N means that I( ; N?O) is not a model of O. /

To overcome this problem, we introduce a restriction on the speci ers allowed on roles. We introduce atemporal speci ers. An atemporal speci er is a speci er S that can only be interpreted as a set SI;Z I of matching annotation sets that do not contain any temporal attribute.

To show that convex geometric models can capture some DL-LitehHo;rTn;@ ontologies, we use concept inclusions with conjunctions on the left-hand side, which can be expressed in DL-LitehHorn . The following example shows that adding conjunction in role inclusions may however lead to satis able ontologies not having a convex model, even for plain DLs.

Example 11. Assume role conjunctions are allowed in the ontology. Let O = fR1 u R2 v R3; 9R1 v A; 9R3 u A v ?; R1(a; a); R1(b; b); R2(a; b); R2(b; a)g and let be a convex f -geometric model of O. Let convexity of (R1) and (R2), we have that = 0:5 (a) + 0:5 (b). By the f ( ; ) 2 (R1) and f ( ; ) 2 (R2); hence f ( ; ) 2 (R1 u R2): Then since is a model of R1 uR2 v R3, f ( ; ) 2 (R3) so 2 (9R3). Moreover, since is a model of 9R1 v A, and 2 (9R1), 2 (A). Hence 6j= 9R3 uA v ? so is not a model of O. /

We now state the main result of this section, which states that, under certain conditions, satis able DL-LitehHo;rTn;@ ontologies have a convex geometric model. The need of Condition (i) is already illustrated by Example 10 whereas Condition (ii) ensures that the underlying logic is Horn (that is, it does not have disjunctions which can be expressed with the temporal attributes before, after and between). Theorem 12. Let O be a satis able DL-LitehHo;rTn;@ ontology without negative role inclusions and such that (i) all speci ers attached to a role in O are atemporal, and (ii) before, after and between do not occur in O. Then O has a convex geometric model.

Related Work Traditionally, most KG embedding models are time-unaware. These models embed both entities and relations in a low-dimensional latent space based on some regularities of target KG. They can be used as approximate reasoning methods [ 25, 24 ] for completing KG without using the schema. Typical embedding models include the translation based models, such as TransE [ 7 ] and bilinear models, such as ComplEx [ 29 ] and SimplE [ 16 ]. From the expressiveness perspective, TransE and DisMult have been shown to be not fully expressive; however, CompleEx and SimplE are fully expressive. Gutierrez-Basulto and Schockaert [ 14 ] use geometric models to study the compatibility between TBox/ontology and KG embeddings. They show that bilinear models (inc. ComplEx and SimplE) cannot strictly represent relation subsumption rules. Wiharja et al. [ 30 ] show that many well known KG embeddings based on KG completion methods are not impressive, when schema aware correctness is considered, despite good performance reported in silver standard based evaluations. Currently, more and more applications are involving dynamic KG, where knowledge in practice is time-variant and consists of sequences of observations. For example, in recommendation systems based on KG, new items and new user actions appear in real time. Accordingly, temporal KG embedding models incorporate time information into their node and relation representations. We next discuss how temporal information is taken into account in KG embeddings and how it has been used in combination with classical DLs. Temporal Knowledge Graph Embeddings. Temporal KG embedding models can be seen as extensions of static KG embedding models. A basic approach is to collapse the dynamic graph into a static graph by aggregating the temporal observations over time [ 19 ]. This approach, however, may lose large amounts of information. An alternative approach is to give more weights to snapshots that are more recent [ 28 ]. Another alternative approach to aggregating temporal observations is to apply decomposition methods to dynamic graphs. The idea is to model a KG as an order 4 tensor and decompose it using CP or Tucker, or other decomposition methods to obtain entity, relation, and timestamp embeddings [ 12 ]. In addition to aggregation based approaches, there are approaches extending static KG embedding, such as TransE, by adding a timestamp embedding into the score function [ 15, 21 ]. Jiang et al. [ 15 ] only use such timestamps to maintain temporal order, while using Integer Linear Programming to encode the temporal consistency information as constraints. Ma et al. [ 21 ] extend several models (Tucker, RESCAL, HolE, ComplEx, DistMult) by adding a timestamp embedding to their score functions. These models may not work well when the number of timestamps is large. Furthermore, since they only learn embeddings for observed timestamps, they cannot generalize to unseen timestamps. Dasgupta et al. [ 11 ] fragments a temporally-scoped input KG into multiple static subgraphs with each subgraph corresponding to a timestamp. There are also approaches of applying random walk models for temporal KG. E.g., Bian et al [ 6 ] use metapath2vec to generate random walks on both the initial KG and the updated nodes and re-compute the embeddings for these nodes. These approaches mainly leverage the temporal aspect of dynamic graphs to reduce the computations. However, they may fail at capturing the evolution and the temporal patterns of the nodes. Another natural choice for modeling temporal KG is by extending sequence models to graph data. E.g., Garc a-Duran [ 13 ] extend TransE and DistMult by combining the relation and timestamp through a character LSTM, so as to learn representations for time-augmented KG facts that can be used in conjunction with existing scoring functions for link prediction. Ma et al. [ 21 ] argue that temporal KG embeddings could also be used as models for cognitive episodic memory (facts we remember and can recollect) and for semantic memory (current facts we know) can be generated from episodic memory by a marginalization operation.

Temporal Description Logics. In the DL literature, there are several approaches for representing and reasoning temporal information [ 20, 33, 5 ]. Schmiedel [ 27 ] was the rst to propose an extension of the description logics (the F LEN R DL in this case) with an interval-based temporal logic, with the temporal quantier at, the existential and universal temporal quanti ers sometime and alltime. Artale and Franconi [ 2, 3 ] considered a class of interval-based temporal description logics by reducing the expressivity to keep the property of decidability of the logic proposed by Schmiedel [ 27 ]. Schild proposed ALCT [ 26 ], extending ALC with point-based modal temporal connectives from tense logic [ 10 ], including existential future ( ), universal future ( ), next instant ( ),until (U ), re exive until (U). Wolter and Zakharyaschev studied the ALCM DL and showed that it is decidable in the class of linear, discrete and unbounded temporal structures [ 31 ]. They also showed that the ALCM DL (extending the ALCM DL with global roles) is undecidable [ 32 ]. Temporal operators can be used in a temporal ABox as well, allowing the use of next instant ( ') and until ('U ) with ABox assertions [ 4 ]. Ozaki et al. [ 22, 23 ] propose temporally attributed DLs, which allows the use of absolute temporal information in both TBoxes and ABoxes. They show that the satis ability of ground ELH@T ontologies is ExpTime-complete, and that the satis ability of ground ELH@T ontologies without the temporal attributes between, before and after is PTime-complete. 6

Conclusion We investigate how geometric models can (or cannot) be used to capture rules about annotated data expressed in the formalism of attributed DLs. We show that every satis able attributed DL-LitehHorn ontology has a convex geometric model and that this is also the case when allowing the use of temporal attributes under some restrictions. There is still a long way to make this result practical since we still require an embedding technique that would construct such a model. In this direction, we highlight the work of Abboud et al. [ 1 ], where relations are mapped to convex regions in the format of hyper-rectangles.

Acknowledgements. We thank Bruno Figueira Lourenco for his contribution on the proof of Theorem 3. Ozaki is supported by the Norwegian Research Council, grant number 316022.

References

1. Ralph Abboud , I_smail I_lkan Ceylan, Thomas Lukasiewicz , and Tommaso Salvatori . Boxe: A box embedding model for knowledge base completion . In Proceedings of NeurIPS , 2020 .

2. A. Artale and E. Franconi . A computational account for a description logic of time and action . In Proceedings of KR , 1994 .

3. A. Artale and E. Franconi . A temporal description logic for reasoning about actions and plans . Journal of Arti cial Intelligence Research , 9 , 1998 .

4. Alessandro Artale , Roman Kontchakov, Carsten Lutz, Frank Wolter, and Michael Zakharyaschev . Temporalising tractable description logics . In Proceedings of TIME , 2007 .

5. Alessandro Artale , Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev . A cookbook for temporal conceptual data modelling with description logics . ACM Trans. Comput. Log. , 15 ( 3 ): 25 :1{ 25 : 50 , 2014 .

6. Ranran Bian , Yun Sing Koh, Gillian Dobbie, and Anna Divoli . Network embedding and change modeling in dynamic heterogeneous networks . In Proceedings of the of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval , pages 861 { 864 , 2019 .

7. Antoine Bordes , Nicolas Usunier, Alberto Garcia-Duran, Jason Weston , and Oksana Yakhnenko . Translating embeddings for modeling multi-relational data . In Advances in neural information processing systems , pages 2787 { 2795 , 2013 .

8. Camille Bourgaux and Ana Ozaki . Querying attributed DL-Lite ontologies using provenance semirings . In Proceedings of AAAI , 2019 .

9. Camille Bourgaux , Ana Ozaki, and Je Z. Pan . Geometric models for (temporally) attributed description logics , 2021 . arXiv: 2108 .12239 [cs.LO].

10. J.P. Burgess . Basic tense logic . In D. Gabbay and F. Guenther, editors, Handbook of Philosophical Logic , page 89 { 133 . 1984 .

11. Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha Talukdar. HyTE: Hyperplane-based temporally aware knowledge graph embedding . In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing , 2018 .

12. Cristobal Esteban , Volker Tresp, Yinchong Yang, Stephan Baier , and Denis Krompass . Predicting the co-evolution of event and knowledge graphs . In Proceedings of FUSION , 2016 .

13. Alberto Garc a-Duran, Sebastijan Dumancic , and Mathias Niepert . Learning sequence encoders for temporal knowledge graph completion . In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing , 2018 .

14. V ctor Gutierrez-Basulto and Steven Schockaert. From knowledge graph embedding to ontology embedding? an analysis of the compatibility between vector space representations and rules . In Proceedings of KR , 2018 .

15. Tingsong Jiang , Tianyu Liu, Tao Ge, Lei Sha, Baobao Chang , Sujian Li , and Zhifang Sui . Towards time-aware knowledge graph completion . In Proceedings of COLING , 2016 .

16. Seyed Mehran Kazemi and David Poole . Simple embedding for link prediction in knowledge graphs . In Proceedings of NeurIPS , 2018 .

17. Markus Krotzsch, Maximilian Marx, Ana Ozaki, and Veronika Thost . Attributed description logics: Ontologies for knowledge graphs . In Proceedings of ISWC , 2017 .

18. Markus Krotzsch, Maximilian Marx, Ana Ozaki, and Veronika Thost . Attributed description logics: Reasoning on knowledge graphs . In Proceedings of IJCAI , 2018 .

19. David Liben-nowell and Jon Kleinberg. The link-prediction problem for social networks . J. AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY , 2007 .

20. Carsten Lutz , Frank Wolter, and Michael Zakharyaschev . Temporal description logics: A survey . In Proceedings of TIME , 2008 .

21. Yunpu Ma , Volker Tresp, and Erik A Daxberger. Embedding models for episodic knowledge graphs . Journal of Web Semantics , 59 , 2018 .

22. Ana Ozaki , Markus Krotzsch, and Sebastian Rudolph . Happy ever after: Temporally attributed description logics . In Magdalena Ortiz and Thomas Schneider, editors, Proceedings of DL , 2018 .

23. Ana Ozaki , Markus Krotzsch, and Sebastian Rudolph . Temporally attributed description logics . In Description Logic, Theory Combination , and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday , 2019 .

24. Je Z. Pan , Yuan Ren, and Yuting Zhao . Tractable approximate deduction for OWL . Arti cial Intelligence , 235 : 95 { 155 , 2016 .

25. Je Z. Pan and Edward Thomas. Approximating OWL-DL Ontologies . In Proceedings of AAAI , 2007 .

26. K.D. Schild . Combining terminological logics with tense logic knowledge bases . In Proceedings of EPIA , 1993 .

27. A. Schmiedel . A temporal terminological logic . In Proceedings of AAAI , 1990 .

28. Umang Sharan . Temporal-relational classi ers for prediction in evolving domains . In In Proceedings of the IEEE International Conference on Data Mining , 2008 .

29. Theo Trouillon , Christopher R. Dance , Eric Gaussier, Johannes Welbl, Sebastian Riedel , and Guillaume Bouchard . Knowledge graph completion via complex tensor factorization . J. Mach. Learn. Res. , 18 :130:1{ 130 : 38 , 2017 .

30. Kemas Wiharja , Je Z. Pan , Martin J. Kollingbaum , and Yu Deng . Schema Aware Iterative Knowledge Graph Completion . Journal of Web Semantics , 2020 .

31. F. Wolter and M. Zakharyaschev . Satis ability problem in description logics with modal operators . In Proceedings of KR , 1998 .

32. F. Wolter and M. Zakharyaschev . Modal description logics: Modalizing roles . In Fundamentae Informaticae , pages 411 { 438 , 1999 .

33. Frank Wolter and Michael Zakharyaschev . Temporalizing description logics . Frontiers of Combining Systems , 2 : 379 { 402 , 1999 .