# Time in a Box: Advancing Knowledge Graph Completion with Temporal Scopes

Ling Cai<EMAIL_ADDRESS>UC Santa Barbara ,  Krzysztof Janowicz  UC Santa
Barbara ,  Bo Yan  UC Santa Barbara ,  Rui Zhu  UC Santa Barbara and  Gengchen
Mai  Stanford University

(2021)

###### Abstract.

Almost all statements in knowledge bases have a temporal scope during which
they are valid. Hence, knowledge base completion (KBC) on temporal knowledge
bases (TKB), where each statement may be associated with a temporal scope, has
attracted growing attention. Prior works assume that each statement in a TKB
must be associated with a temporal scope. This ignores the fact that the
scoping information is commonly missing in a KB. Thus prior work is typically
incapable of handling generic use cases where a TKB is composed of temporal
statements with/without a known temporal scope. In order to address this
issue, we establish a new knowledge base embedding framework, called TIME2BOX,
that can deal with atemporal and temporal statements of different types
simultaneously. Our main insight is that answers to a temporal query always
belong to a subset of answers to a time-agnostic counterpart. Put differently,
time is a filter that helps pick out answers to be correct during certain
periods. We introduce boxes to represent a set of answer entities to a time-
agnostic query. The filtering functionality of time is modeled by
intersections over these boxes. In addition, we generalize current evaluation
protocols on time interval prediction. We describe experiments on two datasets
and show that the proposed method outperforms state-of-the-art (SOTA) methods
on both link prediction and time prediction.

Temporal Knowledge Base, TIME2BOX, Link Prediction, Time Prediction

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
11th Knowledge Capture Conference; December 2–3, 2021; Virtual Event,
USA.††booktitle: Proceedings of the 11th Knowledge Capture Conference (K-CAP
’21), December 2–3, 2021, Virtual Event, USA††price: 15.00††isbn:
978-1-4503-8457-5/21/12††doi: 10.1145/3460210.3493566††ccs: Computing
methodologies Knowledge representation and reasoning††ccs: Computing
methodologies Temporal reasoning

##  1\. Introduction

A knowledge base (KB) such as Wikidata and DBpedia stores statements about the
world around us. A KB is typically represented as a set of triples in the form
of $(s,r,o)$ – short for (subject, relation, object), encoding the association
between entities and relations among them. A statement is often temporally
scoped, which indicates during which time period it is valid. Two examples are
(Albert Einstein, educatedAt, ETH Zurich, 1896 - 1900) and (Albert Einstein,
academicDegree, Doctor of Philosophy in Physics, 1906). The former specifies
the time period during which Albert Einstein studied at ETH, and the latter
points out the specific date when he obtained his degree. Graphs that contain
a substantial amount of such time-aware statements are often called temporal
knowledge base (TKB) in the machine learning literature. Each statement in a
TKB is associated with a validity time as (s, r, o, $t^{*}$)111$t^{*}$ could
be a time instant or time interval.

Due to the ever-changing state of the world and missing data, TKBs usually
contain inaccurate and incomplete information similar to KBs. The sparsity of
TKBs necessitates temporal knowledge base completion (TKBC), namely inferring
missing statements from known statements. Temporal link prediction task is
proposed to evaluate a TKBC model by testing its performance on answering
incomplete temporal queries of the form (s, r, ?o, $t^{*}$) or (?s, r, o,
$t^{*}$).

Despite recent success stories on time-agnostic KBC, research on TKBC is still
in its early age and is facing new challenges. The validity time period of a
statement is often missing in a KB. As a result, it is difficult to
distinguish whether statements in a KB are atemporal (e.g., (Albert Einstein,
instanceOf, Human)) or time-dependent (e.g., (United States of America,
instanceOf, Historical Unrecognized State222According to Wikidata that
statement holds true during 1776-1784.)). This leads to the question of which
statements should be part of a TKB in the first place. Prior works restrict
TKBs to a collection of statements where the validity time period for each
statement must be available. However, in WIKIDATA114k, a dataset from
Wikidata, for instance, 85.1% of all statements are temporal, 56.2% of the
temporal statements are missing their validity time information and are
excluded in previous studies while only 247,393 out of 1,660,824 statements
(i.e., 14.9%) are truly atemporal333For all the statements, we first
categorize predicates into two groups – atemporal predicates and temporal
predicates. If a predicate has ever been involved in a statement that has
temporal scoping, it belongs to temporal predicates; otherwise, it is an
atemporal predicate. Atemporal statements are those associated with atemporal
predicates.. As the number of temporal statements with missing validity
information is substantial, excluding them from a TKB will significantly
reduce the amount of information that could be useful in TKB studies.

Retaining these temporally scoped statements leads to several challenges that
need to be addressed. For instance, how to design a TKBC model to handle
statements with and without known temporal scoping from the data
representation perspective and model design perspective? Clearly, the
conventional representation in prior TKBC in the form of (s, r, o, t)444t
denotes a time point falls short. An ideal TKBC model should be more flexible
to address cases when the validity information of different types (i.e., point
in time, right-open interval (known start time), left-open interval (known end
time), closed interval) is presented in a TKB or even no validity information
is available for a statement.

The second challenge is how to predict the temporal scope of a statement as it
is often missing in TKBs. This task is referred to as time interval
prediction, which amounts to answering incomplete queries of the form (s, r,
o, $?I$). How to generate a predicted time interval and evaluate it require
further investigation. This problem has only been addressed very recently by
Jain et al. (2020). However, at times their evaluation protocols fail to
distinguish one predicted interval from another since they do not consider the
gap between the predicted and the gold interval in case of no overlap. For
instance, the same metric scores are assigned to two predictions [1998, 1999]
and [1998, 2010] when a gold interval [2011, 2020] is considered.

In this paper, we present a novel TKBC embedding framework, called TIME2BOX,
which relies on the intuition that the answer set in a temporal query
$(s,r,?o,t*)$ is always a subset of answers of its time-agnostic counterpart
$(s,r,?o)$. As illustrated in Fig. LABEL:fig:time_reasoning_process, there are
four correct answer entities to a query (Albert Einstein, employer, ?o).
However, when time information is specified (e.g., Albert Einstein, employer,
?o, 1933) as shown in Fig. 1(b), the number of positive answers becomes three.
With more temporal information being available (e.g., Albert Einstein,
employer, ?o, [1933, 1955]), the answer set shrinks further (see Fig. 1(c)).
Therefore, we propose to model a statement in a TKB by imitating the process
of answering its corresponding temporal query$(s,r,?o,t^{*})$, which can be
achieved in two steps – finding answer entities to its atemporal counterpart
(s, r, ?o) by using KBC methods and then picking out entities to be true to
the temporal query from preceding answers by including time. We implement this
idea by using box embeddings (Vilnis et al., 2018; Patel and Sankar, 2020),
especially inspired by QUERY2BOX (Ren et al., 2019), which is originally used
for answering conjunctive queries (Mai et al., 2019). Boxes, as containers,
can naturally model a set of answers they enclose. The filtering functionality
of time can be naturally modeled as intersections over boxes similarly to Venn
diagrams (Venn, 1880). Meanwhile, performing an intersection operation over
boxes would still result in boxes, thus making it possible to design a unified
framework to deal with statements/queries of different types.

(a) Modeling an atemporal statement (b) Modeling a timestamp-based statement
(c) Modeling an interval-based statement

Figure 1. Illustration of TIME2BOX reasoning process. In each figure, the
upper part shows entities and relations in the KB space and the latter
illustrates their correspondences in the embedding space. In all figures, the
final boxes are shaded regions in orange and answer entities are in the boxes.
Note that we omit the edges between Albert Einstein and associated entities in
Fig.1(b) and 1(c) for simplicity. Fig.1(a) shows that for an atemporal query,
the reasoning process picks out all possible answers from the whole entity
space and encloses them into a time-agnostic box. In Fig.1(b) a time-aware box
is added to enclose entities that are relevant to Albert Einstein in 1933.
Then the intersection between time-agnostic and time-aware boxes consists of a
new box, which contains entities that satisfy both requirements. When more
validity information is available, Fig.1(c) shows that more time-aware boxes
can be added and the intersection box that contains correct answers would
shrink further. By doing so, TIME2BOX is flexible enough to handle different
types of queries.

Our main research contributions are listed as follows:

  * •

We propose a box-based knowledge graph embedding TKBC framework (TIME2BOX)
that can represent and model statements with different types of validity
information (i.e., unknown temporal scoping, left/right-open intervals and
closed intervals).

  * •

We introduce a new evaluation metrics $gaeIOU$ for interval evaluation by
taking the gap between a gold interval and a predicted interval into
consideration if no overlap between them exists.

  * •

Extensive experiments on two datasets - WIKIDATA12k and WIKIDATA114k - show
that TIME2BOX yields the state-of-the-art (SOTA) results in link prediction
and outperforms SOTAs in time prediction by significant margins.

TIME2BOX code is available in Github555https://github.com/ling-cai/Time2Box.

##  2\. Related Work

##### Knowledge Base Completion

KBC has been extensively studied in the past (Bordes et al., 2013; Lin et al.,
[n. d.]; Yang et al., 2014; Trouillon et al., 2016; Sun et al., 2019). The
core insight of these methods is to embed entities and relations in a KB into
low-dimensional vectors, which can be utilized in downstream tasks, such as
link prediction. These methods can be roughly classified into two groups:
transformation-based models and semantic matching energy based models.
Transformation-based models treat a relation as a transformation operator. Two
well-known assumptions are translation (e.g., TransE (Bordes et al., 2013))
and rotation (e.g., RotatE (Sun et al., 2019)). For instance, TransE assumes
that for a statement (s, r, o), the object embedding can be derived by
translating the subject embedding operated by the relation embedding in the
embedding space. As such, the presence of a statement in a KG is measured by
the distance between the object embedding and the subject embedding after
transformation. Semantic matching energy based methods determine the existence
of a statement by a score calculated from a function of learned entity and
relation embeddings in the latent space (Yang et al., 2014; Trouillon et al.,
2016). For instance, DistMult (Yang et al., 2014) uses a 3-way inner product
as the scoring function. In addition to these basic triple-based methods,
other studies have focused on exploiting higher-order structural information
in a KG (e.g., paths, neighbours), such as PTransE (Lin et al., [n. d.]),
R-GCN (Schlichtkrull et al., 2018), and TransGCN (Cai et al., 2019). All KBC
models ignore the temporal scoping of statements, and thus are unable to
address temporal statements. However, these models are the foundations for
TKBC.

##### Temporal Knowledge Base Completion

Recently, there has been a surge of interest in taking validity information
into consideration as KB statements are usually time-dependent. There are two
lines of works on temporal link prediction. The first branch focuses on so-
called dynamic knowledge bases (i.e., event KBs (ICEWS) (Boschee et al.,
2015)), where each statement is associated with a timestamp. The insight
behind this branch is that knowledge in KBs evolves over time and historical
statements/events drive the occurrence of new events. Therefore, their focus
is more on extrapolation – predicting unseen entity relationships over time by
modeling temporal dependencies of statements/events in KBs (Trivedi et al.,
2017; Xu et al., 2019; Jin et al., 2020; Deng et al., 2020). The most well-
known model is Know-Evolve (Trivedi et al., 2017), which assumes that the
occurrence of facts/events can be modeled as a multivariate temporal point
process.

Unlike the first branch that assumes timestamp-based statements/facts, a TKB
in the second branch can associate a statement with time instants or time
intervals as its validity information. Moreover, the goal of this line of work
is more about interpolation – filling in missing components in TKGs
with/without explicitly modeling the temporal dependencies between statements.
Recent works follow a common paradigm, that is, to encode time as embeddings
and then incorporate them into time-agnostic KBC models (Leblay and Chekol,
2018; García-Durán et al., 2018; Goel et al., 2020; Ma et al., 2019; Lacroix
et al., 2019; Jain et al., 2020). Leblay and Chekol (2018) investigated
several extensions of existing KBC models by directly fusing time embeddings
with relation embeddings, including TTransE, TRESCAL, etc. Goel et al. (2020)
proposed to learn time-varying entity embeddings by replacing a fraction of
embedding weights with an activation function of learned frequencies. Unlike
previous work, which view time as numeric values, García-Durán et al. (2018)
concatenated the string representation of the relation and the time, and fed
them into an LSTM to obtain time-aware relation representations, which were
used in TransE (TA-TransE) and DistMult(TA-DM) afterwards. More recently,
Lacroix et al. (2019) presented the TKBC problem as a four-way tensor
completion problem, and proposed TNTComplEx, which was extended from the time-
agnostic ComplEx (Trouillon et al., 2016). Jain et al. (2020) augmented
TNTComplex with three more time-dependent terms as analogy to the idea of
approximating joint distributions by low-order marginals in graph models and
incorporated soft ordering and span constraints as temporal inductive biases.
Our work belongs to the latter group. However, our proposal is more flexible
as we can deal with cases when $t^{*}$ is a time instant, a (left/right-open)
interval, closed interval or even missing, while prior works can only handle
one timestamped representation of the form ($s$, $r$, $o$, $t$).

##  3\. Preliminaries

###  3.1. Temporal Knowledge Bases

Prior TKBC methods typically work on TKBs in which each statement has to be
associated with validity information. Thereby, for statements that do not have
known temporal scopes, they either exclude them from a TKB in the beginning or
assume that these statements hold all the time (Lacroix et al., 2019).
However, there are limitations in both ways. As discussed in Section 1,
excluding them from a TKB will significantly reduce the amount of information
that could be beneficial in TKBC studies as the number of such statements is
substantial. For the latter, their assumption would be problematic since a lot
of them may only hold for a certain time period. For instance, the statement
(Warsaw, country, Russian Empire) holds during the time interval [1815-07-09,
1916-11-04]. Following the open-world assumption (OWA), we argue that TKBs are
an extension to KBs insofar as the lack of temporal scoping for any given
statement does not imply it holding indefinitely.

In the following, we use $t$ and $I_{st}^{et}=[st,et]$ to denote a time point
and a time interval, respectively. The symbol $-$ will stand for unknown
temporal validity. There are five types of statements in such a TKB: (1) ($s$,
$r$, $o$) for a statement without a known temporal scope; (2) ($s$, $r$, $o$,
$t$) for a timestamped statement which holds at a point in time $t$; (3) ($s$,
$r$, $o$, $I^{-}_{st}$) for a right-open interval-based statement, in which
only the time when the statement starts to hold is known; (4) (s, r, o,
$I^{et}_{-}$) for a left-open interval-based statement, in which only the time
when the statement ceases to hold is known; and (5) ($s$, $r$, $o$,
$I^{et}_{st}$) for a statement which is temporally scoped by a closed interval
$I_{st}^{et}$. Then a TKB is denoted as $\mathcal{G}=\bigcup_{(s,r,o,t^{*})}$,
namely the union of statements of the five types, where $s,o\in E$ represent
entities, $r\in R$ denotes a relation and
$t^{*}\in\\{t,I_{st}^{-},I_{-}^{et},I_{st}^{et},None\\}$ denotes different
types of valid time or no valid time available.

###  3.2. The TKBC Problem

Link prediction and time prediction are two main tasks used to evaluate a TKBC
model. Statements in TKBs are split into training, validation, and test sets,
used for model training, parameter tuning and model evaluation, respectively.

##### Link prediction

Queries used in this task are of the form ($s$, $r$, $?o$, $t^{*}$).
Performance is evaluated on the rank of a given golden, i.e., ground truth,
answer in the list of all the entities sorted by scores in a descending order.
Then MRR (mean reciprocal rank), MR (mean rank), HITS@1, HITS@3 and HITS@10
are computed from the ranks over all queries in the test set. However a query
may be satisfied by multiple answer entities. Thus another correct answer may
be ranked over the given golden answer. In such cases, a KBC/TKBC model should
not be penalized. A traditional strategy used in KBC is to filter out those
correct answers that are already in the training and validation sets before
calculating metrics. This strategy can be directly applied to queries of the
form ($s$, $r$, $?o$) or ($s$, $r$, $?o$, $t$). However, it may not be
sufficient for queries of the form (s, r, ?o, I), as there may exist other
answers that are true during a time period within the interval $I$. For
example, suppose two statements – (Albert Einstein, employer, Princeton
University, [1933, 1955]) and (Albert Einstein, employer, Leiden University,
[1920, 1946]), both Princeton University and Leiden University are correct
answers during the period [1933, 1946]. One naive way to solve this problem is
to discretize the interval $I$ to a sequence of time points $t$s and then to
convert (s, r, ?o, I) into timestamped queries of the form (s, r, ?o, t) so
that the same filtering process can be performed on each timestamped query.
Finally, the ranks over them are averaged to be the rank for a time interval-
based query. This idea is well-aligned with the proposal by (Jain et al.,
2020).

##### Time prediction

Time prediction queries in TKBs are of the form (s, r, o, ?I). Despite the
fact that the validity information could be a point in time or a time
interval, a point in time can be viewed as a special time interval, in which
start time and end time coincide. Thus, time prediction boils down to time
interval prediction. Its performance is evaluated by the overlap between a
gold interval and a predicted interval or the closeness between those in case
of no overlap. We describe the existing evaluation protocols and propose a
generalized evaluation metric in Section 5.

##  4\. Method

The key insight of TIME2BOX lies in an intuition that the answer set of a
temporal query ($s$, $r$, $?o$, $t^{*}$) is always a subset of answers of its
time-agnostic counterpart ($s$, $r$, $?o$) and set size decreases by adding
more temporal constraints. As illustrated in Fig. 1(a), four object entities
satisfy the atemporal query (Albert Einstein, employer, ?o) while three
entities are the correct answers when the query is restricted to the year of
1993 (see Fig. 1(b)) and only one entity is correct when another time
information is further added in the statement, shown in Fig.1(c). Inspired by
this observation, we propose to model a temporal statement ($s$, $r$, $o$,
$t^{*}$) by imitating the process of answering its corresponding temporal
query ($s$, $r$, $?o$, $t^{*}$), which can be achieved through two steps: 1)
finding a set of answer entities that are true for the corresponding atemporal
query by using any KBC model and 2) imposing a filtering operation enforced by
time to restrict answers afterwards. In following sections, we take a time
instant-based statement as example to formalize our idea in a KB space and a
vector space, respectively.

###  4.1. Formalization in a KB Space

For a statement (s, r, o, t) in a TKB, the first step of TIME2BOX, as shown in
Fig. 1(a), is to project the subject $s$ to a set of object entities that are
true to its corresponding atemporal query in the form of (s, r, ?o) enforced
by the relation $r$. This is a prerequisite for any statement and can
theoretically be addressed by any KBC method. Formally, the relation projector
is defined as:

Relation Projector – $\mathbf{OP_{r}}$: Given the subject entity $s$ and the
relation $r$, this operator obtains:
$S_{r}=\\{o^{\prime}\mid(s,r,o^{\prime})\in\mathcal{G}^{N}\\}$.
$\mathcal{G}^{N}$ is the time-agnostic counterpart of $\mathcal{G}$.

Then time information is used to filter out entities that are incorrect during
the time of interest from the answer set $S_{r}$. This can be achieved by
first projecting the subject $s$ to a set of object entities that co-occur
with $s$ in statements at a given time point (as shown in blue edges in Fig.
1(b)) and then finding the intersection over them and $S_{r}$ (see the three
entities in red in Fig. 1(b)). Accordingly, the two involved steps are defined
as:

Time Projector – $\mathbf{OP_{t}}$: Given the subject $s$ and the timestamp
$t$, this operator obtains: $S_{t}=S_{t}=\\{o^{\prime}\mid o^{\prime}\in
E~{}and~{}(s,r^{\prime},o^{\prime},t)\in\mathcal{G}~{}and~{}r^{\prime}\in
R\\}$.

Intersection Operator – $\mathbf{OI}$: Given $S_{r}$ and $S_{t}$, this
operator obtains the intersection $S_{inter}=\\{o\mid
o\in(S_{r}~{}and~{}S_{t})\\}$.

In fact, such a modeling process also fits to left/right-open interval-based
statements directly. For a left/right-open interval-based statement, we only
consider the known endpoint time in such an interval as we follow the open-
world assumption. However, for an atemporal statement, we only need one
relation projector to obtain $S_{r}$, which is the final set consisting of
correct answer entities to its query form. For a closed interval-based query,
one commonly used approach is to randomly pick one timestamp within the
interval and to associate it with (s, r, o). Then it can be modeled the same
way as an instant-based statement. At training, a timestamp is always randomly
picked from the interval to ensure that all the timestamps in the interval are
used. In addition to the common strategy, TIME2BOX allows sampling of a sub-
time interval within the given interval so that two time constraints (i.e.,
start time and end time) can be imposed by using two time projectors, as shown
in Fig. 1(c)666Alternatively, one could also enumerate all the timestamps
within the interval and use different $\mathbf{OP_{t}}$ to project the subject
to multiple sets of entities, each of which is specific for one timestamp.
Subsequently, an intersection operator again is performed over all the sets of
entities obtained from $\mathbf{OP_{r}}$ and $\mathbf{OP_{t}}$ in the previous
step. However, in spite of its efficiency, this practice is hard to implement
in mini-batch training manner since time intervals in different statements
usually have varying duration and thus contain different number of
timestamps..

###  4.2. Implementation in a Vector Space

In order to implement this idea in a vector space, two key points are 1) how
to model a set of answers returned by a KBC model and 2) how to instantiate
two projectors and one intersection operator.

Prior KBC models are incapable of directly representing a set of answer
entities in a vector space. Instead, they usually represent entities and
relations as single points in the vector space and model point-to-point
projections, e.g., TransE. Inspired by QUERY2BOX (Ren et al., 2019), which is
used to deal with complex queries that involve conjunctions, existential
quantifiers, and disjunctions, we introduce the idea of boxes in the vector
space and thus name the proposed framework TIME2BOX. The reasons for adopting
boxes are three-fold. First, boxes are containers that can naturally model a
set of answer entities they enclose. Second, finding the intersection set
among sets of entities amounts to finding the intersected area over boxes
similar to the concept of Venn diagram. Third, the result of performing an
intersection operation over boxes is still a box, which makes it possible to
deal with statements of different types in a unified framework.

In TIME2BOX, each entity $e\in E$, relation $r\in R$, and timestamp $t\in T$
($T$ is the set of all discrete timestamps in a TKB) are initialized as vector
embeddings $\mathbf{e}\in\mathbb{R}^{d}$, $\mathbf{r}\in\mathbb{R}^{d}$, and
$\mathbf{t}\in\mathbb{R}^{d}$. $S_{r}$, $S_{t}$, and $S_{inter}$ refer to sets
of entities and thus are modeled by boxes, represented as box embeddings in
the vector space. In the following, we first introduce the definition of box
embeddings and then introduce main components of modeling and reasoning.

####  4.2.1. Box Construction and Reasoning

##### Box embeddings:

Mathematically, they are axis-aligned hyper-rectangle in a vector space, which
can be determined by the position of the box (i.e., a center point) and its
length (i.e., offsets). Formally, in a vector space $\mathbb{R}^{d}$, a box
can be represented by $\mathbf{b}$=(Cen($\mathbf{b}$), Off($\mathbf{b}$)),
where $\text{Cen}(\mathbf{b})\in\mathbb{R}^{d}$ is its center point and
$\text{Off}(\mathbf{b})\in\mathbb{R}_{\geq 0}^{d}$ specifies the length/2 of
the box in each dimension. If an entity belongs to a set, its entity embedding
is modeled as a point inside the box of the set. The interior of a box in the
vector space can be specified by points inside it:

(1)
$box_{\mathbf{b}}=\\{\mathbf{e}\in\mathbb{R}^{d}:\text{Cen}(\mathbf{b})-\text{Off}(\mathbf{b})\preceq\mathbf{e}\preceq\text{Cen}(\mathbf{b})+\text{Off}(\mathbf{b}))\\}$

where $\preceq$ denotes element-wise inequality.

##### Projection operators in a vector space

In previous work, relations are commonly assumed to be projectors that
transform a subject embedding to an object embedding in terms of points in a
vector space, e.g., TransE (Bordes et al., 2013) and RotatE (Sun et al.,
2019). Here we adopt a similar idea but take both relations and timestamps as
projectors ($\mathbf{OP_{r}}$ and $\mathbf{OP_{t}}$) to project a subject to a
set of entities in $S_{r}$ – represented as a time-agnostic box
$\mathbf{b}_{S_{r}}$ and to a set of entities in $S_{t}$ – represented as a
time-aware box $\mathbf{b}_{S_{t}}$, respectively, which are illustrated in
Fig. LABEL:fig:time_reasoning_process.

The center of a box can be defined as the resulting embedding after applying a
projection operator ($\mathbf{OP_{r}}$ or $\mathbf{OP_{t}}$) on the subject
embedding. The centers of $\mathbf{b}_{S_{r}}$ and $\mathbf{b}_{S_{t}}$ can be
formulated as below:

(2) $\displaystyle
Cen(\mathbf{b}_{S_{r}})=\mathbf{e}\odot\mathbf{r};~{}~{}Cen(\mathbf{b}_{S_{t}})=\mathbf{e}\otimes\mathbf{t}$

where $\odot\mathbf{r}$ and $\otimes\mathbf{t}$ are projectors
$\mathbf{OP_{r}}$ and $\mathbf{OP_{t}}$, respectively. Theoretically,
projection operators could be instantiated by any projector in existing KBC
models, such as element-wise addition in TransE (Bordes et al., 2013) ,
element-wise product in DistMult (Yang et al., 2014) , and Hadamard product in
RotatE (Sun et al., 2019). Even though $\mathbf{OP_{r}}$ and $\mathbf{OP_{t}}$
can be different, we choose the same projector for both and implement two
TIME2BOX models by taking element-wise addition and element-wise product as
operators by following TransE and DistMult, respectively. Accordingly, these
two models are named as TIME2BOX-TE and TIME2BOX-DM.

Ideally, the size of the box $\mathbf{b}_{S_{r}}$ should be determined by both
the subject entity and the relation, since the box contains all object
entities that satisfy a query in the form of (s, r, ?o). The same applies to
$\mathbf{b}_{S_{r}}$. However, as the entity space is usually large in a KB,
introducing entity-specific parameters would result in high computational
cost. Therefore, in practice, $\text{Off}(\mathbf{b}_{S_{r}})$ and
$\text{Off}(\mathbf{b}_{S_{t}})$ are only determined by the relation $r\in R$
and the timestamp $t\in T$, respectively. Put differently, the size of
$\mathbf{b}_{S_{r}}$ and $\mathbf{b}_{S_{t}}$ are initialized based on $r$ and
$t$, which are learned through training.

##### Intersection Operators in a vector space

An intersection operator aims to find the intersection box
$\mathbf{b}_{inter}=\text{(Cen}(\mathbf{b}_{inter}),\text{Off}(\mathbf{b}_{inter}))$
of a set of box embeddings
$\mathbf{B}=\\{\mathbf{b}_{S_{r}},\mathbf{b}_{S_{t}1},...,\mathbf{b}_{S_{t}n}\\}$
obtained from the previous step. The intersection operator should be able to
deal with $\mathbf{B}$ of different sizes, as required in Fig.
LABEL:fig:time_reasoning_process. Thus, both $\text{Cen}(\mathbf{b}_{inter})$
and $\text{Off}(\mathbf{b}_{inter})$ are implemented by using attention
mechanisms. Following the idea in Bahdanau et al. (2014), the center point
$\text{Cen(}\mathbf{b}_{inter}\text{)}$ is calculated by performing element-
wise attention over the centers of boxes in $\mathbf{B}$. This can be
formulated as follows:

(3)
$\text{Cen}(\textbf{b}_{inter})=\sum_{i}\text{softmax}(\text{NN}(\text{Cen}(\mathbf{b}_{i}))\odot\text{Cen}(\mathbf{b}_{i})$

where NN is a one-layer neural network and $\mathbf{b}_{i}\in\mathbf{B}$.

Since the intersection box $\mathbf{b}_{inter}$ must be smaller than any of
the box in $\mathbf{B}$, we use element-wise min-pooling to make sure the new
box must be shrunk and perform DeepSets (Zaheer et al., 2017) over all the
Off($\mathbf{b}_{i}$) ($\mathbf{b}_{i}\in\mathbf{B}$) to downscale
$\mathbf{b}_{inter}$ (Ren et al., 2019). This can be written as below:

(4)
$\text{Off(}\mathbf{b}_{inter}\text{)}=\text{Min}(\textbf{Off})\odot\sigma(\text{DeepSets}(\textbf{Off}))$

where
$\text{DeepSets(}\\{\mathbf{x_{1}},\mathbf{x_{2}},...,\mathbf{x_{n}}\\}\text{)}=\text{MLP}(1/n)\cdot\sum_{i}^{n}\text{MLP(}\mathbf{x_{i}}\text{)}$,
$\sigma$ denotes the sigmoid function, and
$\textbf{Off}=\\{\text{Off}(\mathbf{b}_{i}):\mathbf{b}_{i}\in\mathbf{B}\\}$.

###  4.3. Optimization Objective

For a query, TIME2BOX aims to pull correct entity embedding into the final box
$\mathbf{b}_{inter}$ while pushing incorrect entity embedding far away from
it. The distance-based loss proposed by Sun et al. (2019) satisfies this need
:

(5)
$Loss=-log\;\sigma(\gamma-D(\mathbf{o},\mathbf{b}_{inter}))-\frac{1}{k}\sum_{i=1}^{k}log\;\sigma(D(\mathbf{o}^{\prime},\mathbf{b}_{inter})-\gamma)$

where $\sigma$ is the sigmoid function, $\gamma$ is a fixed margin,
$\mathbf{o}$ is the embedding of a positive entity to the given query, and $k$
is the number of negative samples $\mathbf{o^{\prime}}$.
$D(\mathbf{o},\mathbf{b}_{inter})$ measures the distance between entity
$\mathbf{o}$ and the final box $\mathbf{b_{inter}}$. With the size of a box
being considered, the distance is divided into two parts: outside distance
$D_{outside}(\mathbf{o},\mathbf{b}_{inter})$ and inside distance
$D_{inside}(\mathbf{o},\mathbf{b}_{inter})$. For cases when $\mathbf{o}$ is
outside of $\mathbf{b}_{inter}$, the former refers to the distance of an
entity embedding $\mathbf{o}$ to the boundary of the box $\mathbf{b}_{inter}$,
and the latter calculates the distance between the box’s center
$Cen(\mathbf{b}_{inter})$ and its boundary. This can be formalized as below:

(6) $D(\mathbf{o},\mathbf{b}_{inter})=\alpha\cdot
D_{inside}(\mathbf{o},\mathbf{b}_{inter})+D_{outside}(\mathbf{o},\mathbf{b}_{inter})$

where $\alpha\in[0,1]$. When $\alpha=0$, it means that a positive entity is
required to be in a $\mathbf{b}_{inter}$, but its distance to the center is
not as important. $D_{inside}(\mathbf{o},\mathbf{b}_{inter})$ and
$D_{outside}(\mathbf{o},\mathbf{b}_{inter})$ are written as:

$\displaystyle D_{inside}(\mathbf{o},\mathbf{b}_{inter})$
$\displaystyle=\|\text{Cen}(\mathbf{b}_{inter})-\text{Min}(\mathbf{b}_{max},\text{Max}(\mathbf{b}_{min},\mathbf{o}))\|_{1}$
$\displaystyle D_{outside}(\mathbf{o},\mathbf{b}_{inter})$
$\displaystyle=\|\text{Max}(\mathbf{o}-\mathbf{b}_{max},\mathbf{0})+\text{Max}(\mathbf{b}_{min}-\mathbf{o},\mathbf{0})\|_{1}$

where
$\mathbf{b}_{min}=\text{Cen}(\mathbf{b}_{inter})-\text{Off}(\mathbf{b}_{inter})$
and
$\mathbf{b}_{max}=\text{Cen}(\mathbf{b}_{inter})+\text{Off}(\mathbf{b}_{inter})$
are embeddings of the bottom left corner and the top right corner of
$\mathbf{b}_{inter}$, respectively.

Compared to answering atemporal queries, finding correct answers to temporal
ones is more challenging. Therefore, the loss function should reward more in
the optimization direction that is capable of correctly answering temporal
queries. For a given query $q_{i}$, we use $\frac{1}{n_{q_{i}}}$, where
$n_{q_{i}}$ is the number of correct answers to $q_{i}$ that appear in
training as a weight to adjust the loss. The core idea here is that time-aware
queries often are satisfied with fewer answers, and, thus, are harder to
answer compared to atemporal queries.

###  4.4. Time Negative Sampling

Entity negative sampling is widely used in KBC. For a positive sample
$(s,r,o)$, negative samples are constructed by replacing $o$ with other
entities $o^{\prime}$, ensuring that $(s,r,o^{\prime})$ must not appear in
training set. In this paper, we adopt this strategy so that the model is able
to learn the association between entities, relations, and time occurring in a
positive sample by distinguishing the correct answers from the negative
samples. Moreover, for time-aware statements, we perform time negative
sampling, which corrupts a statement $(s,r,o,t)$ by replacing $t$ with a
number of timestamps $t^{\prime}$. This is important for statements where only
start time or end time is available. As shown in Fig.
LABEL:fig:time_reasoning_process, the proposed architecture cannot distinguish
those statements from time instant-based statements. But time negative
sampling can mitigate this issue to some degree. The following is used for
time negative sampling concerning different types of statements ($st$ and $et$
are short for start and end time):

(7) $T^{\prime}=\begin{cases}\\{t^{\prime}\in
T:(s,r,o,t^{\prime})\notin\mathcal{G}\\}&(s,r,o,t)\\\ \\{t^{\prime}\in
T:(s,r,o,t^{\prime})\notin\mathcal{G},t^{\prime}<st\\}&(s,r,o,I_{st}^{-})\\\
\\{t^{\prime}\in
T:(s,r,o,t^{\prime})\notin\mathcal{G},t^{\prime}>et\\}&(s,r,o,I_{-}^{et})\\\
\\{t^{\prime}\in T:(s,r,o,t^{\prime})\notin\mathcal{G},t^{\prime}\notin
T^{et}_{st}\\}&(s,r,o,I_{st}^{et})\\\ \end{cases}$

where $T^{et}_{st}$ denotes a set of time points within the interval
$I_{st}^{et}$.

###  4.5. Time Smoothness Regularizer

Time is continuous. We may expect that neighboring timestamps would have
similar representations in the vector space. Following Lacroix et al. (2019),
we penalize time difference between embeddings of two consecutive timestamps
by using $L_{2}$:

(8)
$\Lambda(T)=\frac{1}{|T|-1}\sum_{i=1}^{|T|-1}\|\mathbf{t}_{i+1}-\mathbf{t}_{i}\|_{2}^{2}$

During the training step, for batches with temporal statements, we add this
regularizer with a weight scalar $\beta$ to the loss function in Eq. 5, where
$\beta$ specifies the degree of penalization.

##  5\. Evaluation metrics IN Time prediction

##### Time Interval Evaluation

$gIOU$ (Rezatofighi et al., 2019) and $aeIOU$ (Jain et al., 2020) are two
evaluation metrics recently adopted in time interval prediction. Both are
built on Intersection Over Union that is commonly used for bounding box
evaluation in Computer Vision.

The idea of $gIOU$ is to compare the intersection between a predicted interval
and a gold interval against the maximal extent that the two intervals may
expand. It can be formulated as below:

(9) $\begin{split}gIOU(I^{gold},I^{pred})=\frac{D(I^{gold}\bigcap
I^{pred})}{D(I^{gold}\bigcup I^{pred})}-\\\ \frac{D(I^{gold}\biguplus
I^{pred}\setminus(I^{gold}\bigcup I^{pred}))}{D(I^{gold}\biguplus
I^{pred})}\in(-1,1]\end{split}$

where $I^{gold}\bigcap I^{pred}$ is the overlapping part of two intervals,
$I^{gold}\biguplus I^{pred}$ denotes the shortest contiguous interval (hull)
that contains both $I^{gold}$ and $I^{pred}$. As shown in Fig. 2, if
$I^{gold}=[2011,2016]$ and $I^{pred}=[2009,2013]$, then $I^{gold}\bigcap
I^{pred}=[2011,2013]$ and $I^{gold}\biguplus I^{pred}=[2009,2016]$.
$D(I)=I_{max}-I_{min}+1$ is the number of time points at a certain granularity
(e.g., year in this paper) during the time interval $I$.

Compared to $gIOU$, affinity enhanced IOU, denoted as $aeIOU$, provides a
better evaluation in case of non-overlapping intervals and outputs scores in
$[0,1]$. It can be written as follow:

(10) $aeIOU(I^{gold},I^{pred})=\begin{cases}\frac{D(I^{gold}\bigcap
I^{pred})}{D(I^{gold}\biguplus I^{pred})}&D(I^{gold}\bigcap I^{pred})>0\\\
\frac{1}{D(I^{gold}\biguplus I^{pred})}&otherwise\end{cases}$

However, we notice that $aeIOU$ cannot tell some cases apart. As illustrated
in Fig. 2, $aeIOU$ results in the same scores for ⑤, ⑥, and ⑦ when compared to
the gold interval$[2011,2016]$. Intuitively one would assume that ⑦ is better
than the others and ⑥ is the least desirable. The former has a one-year
intersection between ⑦ and the gold. For the latter, the gap between ⑤ and the
gold is smaller than that between ⑥ and the gold, despite the fact that
neither ⑤ and ⑥ overlaps with the gold. Its failure lies in that it does not
consider the gap between the gold and the predicted interval in case of no
overlap.

Figure 2. Evaluation Comparison between aeIOU and gaeIOU on different
predicted intervals. Suppose a gold interval is [2011, 2016], seven possible
predicted intervals are represented as rectangles in black. Intersections
between the predicted and the gold are in pink and gaps are in orange if no
overlap exists. Notably, gaeIOU is able to distinguish these predictions while
aeIOU fails to do so.

In the following, we take both the hull and the intersection/gap between a
gold interval and a predicted interval into the design of the metric. The
intuition is that when the size of the hull remains the same, the metric score
of a predicted interval decreases with a larger gap to the gold in case of no
overlap and increases with a larger intersection. $aeIOU$ is therefore
generalized to $gaeIOU$ as below:

(11) $gaeIOU(I^{gold},I^{pred})=\begin{cases}\frac{D(I^{gold}\bigcap
I^{pred})}{D(I^{gold}\biguplus I^{pred})}&D(I^{gold}\bigcap I^{pred})>0\\\ \\\
\frac{D^{\prime}(I^{gold},~{}I^{pred})^{-1}}{D(I^{gold}\biguplus
I^{pred})}&otherwise\end{cases}$

where
$D^{\prime}(I^{gold},~{}I^{pred})=max(I^{gold}_{min},I^{pred}_{min})-min(I^{gold}_{max},I^{pred}_{max})+1$
is the length of the gap.

Accordingly, the Property ($P$) that a good evaluation metric must satisfy can
be rewritten as: if predicted intervals (partially) overlap with the gold
interval with the same size, then the prediction having a smaller hull with
the gold interval should be awarded more by $M$; if there is no overlap, the
prediction that has a smaller hull and a narrower gap with the gold should be
scored higher by $M$. It can be formalized as below:

Property P: In case of $D(I^{gold}\bigcap I^{pred1})=D(I^{gold}\bigcap
I^{pred2})\neq 0$, $M(I^{gold},I^{pred1})>M(I^{gold},I^{pred2})$ if and only
if $D(I^{gold}\bigcup I^{pred1})<D(I^{gold}\bigcup I^{pred2})$.
In case of non-overlapping, $M(I^{gold},I^{pred1})>M(I^{gold},I^{pred2})$ if
and only if $D(I^{gold}\bigcup I^{pred1})\cdot D^{\prime}(I^{gold}\bigcap
I^{pred1})>D(I^{gold}\bigcup I^{pred2})\cdot D^{\prime}(I^{gold}\bigcap
I^{pred2}))$.

It follows that $gaeIOU$ satisfies Property P, whereas $aeIOU$ does not
satisfy it; see Fig. 2.

##  6\. Experiment

Our goal here is to evaluate TIME2BOX in both link prediction and time
prediction tasks. For a test sample $(s,r,?o,t^{*})$, we replace $?o$ with
each entity $o^{\prime}\in E$ and use
$log\sigma(\gamma-D(\mathbf{o^{\prime}},\mathbf{b}_{inter}))$, a variation of
the inverse distance used in Eq. 5, as scores for link prediction. Entities
that have higher scores are more likely to form new links. Likewise, in terms
of time prediction, for a query $(s,r,o,?I)$, we first replace $I$ with each
timestamp $t\in T$ and calculate its score. Then we use the greedily
coalescing method proposed in Jain et al. (2020) to generate time intervals as
predictions.

###  6.1. Datasets

We report experimental results using two TKBC datasets, which both are rooted
in Wikidata. WIKIDATA12k is a widely used benchmark dataset in TKBC where each
statement is associated with a time “interval” (Dasgupta et al., 2018). Such
an “interval”, in fact, could be a time instant, where start time and end time
are the same, a left/right-open interval, or a closed interval. Note that this
dataset excludes statements that do not have known temporal scopes in
Wikidata, although they may be time-dependent and useful in TKBC, as discussed
in Section 1. The other dataset is a subset of WIKIDATA432k proposed by
Lacroix et al. (2019), which is the only TKB dataset where the start time, end
time, or both of a statement can remain unspecified. Although this dataset is
more appropriate for a TKBC problem, there are two limitations. First, it
poses a computational burden as it contains 432k entities and 407 relations,
consisting of 7M tuples in the training set. Second, there are several
mistakes in the temporal information. For instance, 2014 was written as 2401.
We extract a subgraph, named as WIKIDATA114k, and correct temporal information
by checking it against Wikidata. More details about data pre-processing and
statistics are in Appendix A (All Appendices are available online777Link to
online Appendices.). Since our focus is on generic knowledge bases, we do not
consider event-based datasets, such as ICEWS14 and ICEWS05-15, in which each
statement is associated with a timestamp.

###  6.2. Baselines and Model Variants

In the following experiments, we regard TIME2BOX-TE as our main model, in
which both the relation operator and the time projector are instantiated as an
element-wise addition. It is denoted as TIME2BOX in resulting tables. We
compare it against two SOTAs in TKBC: TNT-Complex and TIMEPLEX base model by
using the implementation in Jain et al. (2020), both of which are based on the
time-agnostic KBC model: ComplEx (Trouillon et al., 2016).

In addition to comparison with existing SOTAs, we also conduct an ablation
study, in which several variants of the proposed model are compared: (1)
TIME2BOX-SI, short for Sample Interval: for a closed interval-based statement,
this variant randomly samples a sub time interval from a given interval at
each training step and train it as shown in Fig. 1(c). (2) TIME2BOX-TR:
previous works in TKBC often explicitly fused relations with time information
to obtain time-aware relations and empirically demonstrated its effectiveness
(Jain et al., 2020; Lacroix et al., 2019; García-Durán et al., 2018). We also
explicitly model the association between relations and time as a new point
$p_{rt}=\mathbf{r}+\mathbf{t}$ in the vector space and incorporate it into Eq.
3 to help locate the intersection box. (3)TIME2BOX-DM: this variant implements
the relation and time projectors as an element-wise product in real space as
DistMult does. (4) TIME2BOX-TNS: this variant is used to test the effect of
time negative samples, in which we replace a number of entity negative samples
with time negative samples, as introduced in Section 4.4.

All these models are trained on statements in training set and evaluated by
answering queries where either the object or the time information is missing.
Hyper-parameter settings are introduced in Appendix B and comparison of
parameters used in different models is summarized in Table 11 in Appendix F.
Moreover, we notice there are several limitations in current experimental
setups of SOTAs and we detail them in Appendix C.

###  6.3. Main Results

Datasets | WIKIDATA12k | WIKIDATA114k
---|---|---
Metrics | MRR | MR | HITS@1 | HITS@10 | MRR | MR | HITS@1 | HITS@10
TNT-Complex | 31.77 | 415 | 19.24 | 51.74 | 49.25 | 638 | 41.02 | 66.99
TIMEPLEX base | 34.55 | 302 | 21.91 | 53.25 | 49.99 | 337 | 41.25 | 66.10
TIME2BOX-TR | 34.99 | 102 | 24.79 | 56.32 | 50.25 | 85 | 41.73 | 67.13
TIME2BOX-DM | 35.90 | 139 | 25.52 | 56.74 | 48.84 | 284 | 41.09 | 64.33
TIME2BOX-SI | 36.79 | 100 | 27.16 | 56.43 | 50.42 | 139 | 41.65 | 67.58
TIME2BOX-TNS | 37.25 | 100 | 27.41 | 57.31 | 50.55 | 185 | 41.77 | 67.78
TIME2BOX | 37.30 | 101 | 27.38 | 57.36 | 50.49 | 168 | 41.69 | 67.91

Table 1. Link prediction evaluation across two datasets.

##### Link Prediction Task

We report main results of link prediction in Table 1. TIME2BOX and all its
variants consistently outperform or are on a par with the performance on SOTAs
in terms of MRR, MR, HITS@1 and HITS@10. On WIKIDATA12k, TIME2BOX outperforms
TIMEPLEX base by around 3 points in terms of MRR and over 5 points in HITS@1.
On WIKIDATA114k, TIME2BOX is slightly better than two SOTAs in general for
MRR, HITS@1 and HITS@10. In addition, we notice that TIME2BOX beats SOTAs by
large margins in time interval-based link prediction, as shown in Table 8 in
Appendix D. Our method improves around 20 and 7 HITS@1 points in terms of
half-open interval-based link prediction and closed interval-based link
prediction on WIKIDATA12k, respectively. On WIKIDATA114k TIME2BOX improves
around 6 and 4 HITS@1 points, respectively.

Another critical observation in Table 1 is the substantial improvements of
using TIME2BOX in terms of MR on both datasets. TIME2BOX returns an MR of 100
and 139 on WIKIDATA12k and WIKIDATA114k, respectively and TIMEPLEX base
obtains 302 and 337 for MR on both datasets. It indicates that TIME2BOX is
capable of giving a fair rank for a gold answer to any test query on average.
This is likely because of the idea of using boxes to constraint the potential
answer set. As a time-agnostic box is optimized towards embracing entities
satisfying atemporal queries of the form ($s,r,?o$) in the learning process,
boxes implicitly manage to learn common characteristics of the satisfied $?o$.
Therefore, TIME2BOX is less likely to output extremely bad predictions.
Examples in Section 6.4 exemplify this hypothesis.

##### Time Prediction Task

Table 2 and Table 3 summarizes the results for two datasets. On both datasets,
TIME2BOX and its variants consistently outperform SOTAs by significant
margins. Specifically, TIME2BOX improves over TIMEPLE by about 5.56, 7.25, and
4.87 points with respect to gIOU@1, aeIOU@1, and gaeIOU@1, respectively, on
WIKIDATA12k. As for WIKIDATA114k, despite subtle improvements in link
prediction, the advancement of TIME2BOX is more pronounced in time prediction,
which shows that it gains 8.7, 5.87, and 4.66 points on gIOU@1, aeIOU@1, and
gaeIOU@1, respectively. Furthermore, the improvements on gaeIOU@10 are much
more notable with gains of 15.81 and 11.07 points on the two datasets,
respectively.

Datasets | WIKIDATA12k
---|---
Metrics | gIOU@1 | gIOU@10 | aeIOU@1 | aeIOU@10 | gaeIOU@1 | gaeIOU@10
TNT-Complex | 31.44 | 55.18 | 18.86 | 40.94 | 11..01 | 29.51
TIMEPLEX base | 35.63 | 60.86 | 18.60 | 37.75 | 12.61 | 32.63
TIME2BOX-TR | 39.63 | 67.83 | 23.47 | 44.64 | 15.87 | 41.53
TIME2BOX-DM | 38.78 | 62.44 | 21.91 | 41.55 | 14.94 | 37.14
TIME2BOX-SI | 39.68 | 65.30 | 23.66 | 42.16 | 16.09 | 38.54
TIME2BOX-TNS | 42.30 | 70.16 | 25.78 | 50.04 | 17.41 | 47.54
TIME2BOX | 41.20 | 68.53 | 24.70 | 46.05 | 16.98 | 43.08

Table 2. Time prediction evaluation on WIKIDATA12k.

Datasets | WIKIDATA114k
---|---
Metrics | gIOU@1 | gIOU@10 | aeIOU@1 | aeIOU@10 | gaeIOU@1 | gaeIOU@10
TNT-Complex | 27.94 | 48.31 | 16.18 | 35.32 | 7.31 | 23.68
TIMEPLEX base | 29.31 | 57.68 | 18.56 | 36.70 | 12.53 | 32.47
TIME2BOX-TR | 37.49 | 67.95 | 25.05 | 49.02 | 15.41 | 45.72
TIME2BOX-DM | 35.88 | 66.62 | 24.33 | 48.03 | 14.89 | 44.48
TIME2BOX-SI | 34.02 | 62.89 | 23.10 | 44.74 | 14.07 | 40.05
TIME2BOX-TNS | 37.31 | 66.91 | 25.07 | 48.18 | 15.57 | 44.66
TIME2BOX | 38.01 | 71.29 | 24.42 | 50.07 | 15.88 | 47.77

Table 3. Time prediction evaluation on WIKIDATA114k.

###  6.4. Qualitative Study

Table 4 showcases examples of timestamp-based link prediction on WIKIDATA12k.
The comparison between TIMEPLEX base and TIME2BOX reveals that TIME2BOX is
able to learn common characteristics of entities by adopting boxes. For
instance, the predicted top 10 returned by TIME2BOX are possible affiliations
(e.g., institutes, colleges, universities) in the first query and are
countries in the second query. By contrast, TIMEPLEX base returns a mixture of
entities with distinct classes for both queries. Furthermore, Table 5 shows an
example of time interval-based link prediction, in which TIME2BOX is able to
consistently output correct predictions across time and precisely discern the
changes of objects over time (i.e., the correct answer shifts from Russian
Empire to Ukrainian People’s Republic in 1916), while TIMEPLEX base fails.
This can be attributed to the ability of TIME2BOX to capture the order of
timestamps and the idea of temporal boxes as a constraint over potential
answer entities. Hence, answer entities that are true in two consecutive years
can be enclosed in the intersection of temporal boxes.

Query Example 1: (Yury Vasilyevich Malyshev, educatedAt, ?o, 1977)
---
TIMEPLEX base | TIME2BOX
| 1\. Bauman Moscow State Technical University,
---
2\. Gold Star,
3\. Communist Party of the Soviet Union,
4\. Order of Lenin,
5\. S.P. Korolev Rocket and Space Corporation Energia,
6\. Hero of the Soviet Union,
7\. Gagarin Air Force Academy,
8\. Balashov Higher Military Aviation School of Pilots,
9\. Ashok Chakra,
10\. Heidelberg University
| 1\. Bauman Moscow State Technical University,
---
2\. Gagarin Air Force Academy,
3\. S.P. Korolev Rocket and Space Corporation Energia,
4\. Saint Petersburg State Polytechnical University,
5\. University of Oxford,
6\. Saint Petersburg State University,
7\. Steklov Institute of Mathematics,
8\. Leipzig University,
9\. Heidelberg University,
10\. Moscow Conservatory
Query Example 2: (Pedro Pablo Kuczynski, countryOfCitizenship,?o, 2015)
TIMEPLEX base | TIME2BOX
| 1\. doctor honoris causa,
---
2\. President of Peru,
3\. Minister of Economy and Finance of Peru,
4\. Grand Cross of the Order of the Sun of Peru,
5\. President of the Council of Ministers of Peru,
6\. World Bank,
7\. Serbia,
8\. Royal Spanish Academy,
9\. Meurthe-et-Moselle,
10\. Norwegian Sportsperson of the Year
| 1\. France,
---
2\. Germany,
3\. United States of America,
4\. Austria,
5\. Romania,
6\. United Kingdom,
7\. Poland,
8\. Kingdom of Italy,
9\. Russian Soviet Federative Socialist Republic,
10\. Russian Empire

Table 4. Examples of timestamp-based link prediction on WIKIDATA12k. Top 10
entities predicted by TIMEPLEX base and TIME2BOX are numbered, where 1 denotes
Top One. Correct answers are in bold.

| Query Example: (Kyiv, country, ?o, [1905, 1919])
---|---
|  | Gold Answers: (1)[1905, 1916]->Russian Empire; (2)[1917, 1919]->Ukrainian People’s Republic
---
year | Timplex | TIME2BOX
1905 | Soviet Union | Russian Empire
1906 | Soviet Union | Russian Empire
1907 | Russian Empire | Russian Empire
1908 | Soviet Union | Russian Empire
1909 | Ukrainian Soviet Socialist Republic | Russian Empire
1910 | Soviet Union | Russian Empire
1911 | Russian Empire | Russian Empire
1912 | Ukrainian Soviet Socialist Republic | Russian Empire
1913 | Soviet Union | Russian Empire
1914 | Ukrainian Soviet Socialist Republic | Russian Empire
1915 | Soviet Union | Russian Empire
1916 | Ukrainian People’s Republic | Russian Empire
1917 | Ukrainian People’s Republic | Ukrainian People’s Republic
1918 | Ukrainian People’s Republic | Ukrainian People’s Republic
1919 | Ukrainian People’s Republic | Ukrainian People’s Republic

Table 5. An example of interval-based link prediction on WIKIDATA12k. For time
interval-based link prediction, the current strategy is to discretize
intervals to timestamps and average ranks for each timestamp-based prediction
result as the final evaluation. Only top 1 predictions are shown here.

###  6.5. Model Variation Study

In this section, we report on observations of results about different model
variations, which are shown in Table 1, 2 and 3. Compared to TIME2BOX-DM,
which adopts element-wise product as operators, element-wise addition
projectors (TIME2BOX) perform better in link prediction and time prediction on
both datasets. Moreover, we observe that explicitly modeling association
between time and relation (i.e., TIME2BOX-TR) does not significantly improve
the performance of TIME2BOX framework, although it speeds up the convergence
at training, indicating that intersection operators are good enough to learn
the association between time and relations implicitly. As for different time-
aware strategies incorporated in TIME2BOX-SI and TIME2BOX-TNS, we find that on
both datasets TIME2BOX-SI does not outperform TIME2BOX, indicating that using
one sample strategy (i.e., Fig. 1(b)) is better at modeling time interval-
based statements in TIME2BOX. In addition, we find that by incorporating time
negative samples, the performance on time prediction can be further improved
on WIKIDATA12k, although TIME2BOX-TNS is not superior to TIME2BOX in link
prediction.

##  7\. Conclusion

In this work, we presented a box-based temporal knowledge graph (TKBC)
completion framework (called TIME2BOX) to represent and model statements with
different types of validity information (i.e., no time, known start time,
known end time, instant, both start and end time) in a vector space. We argued
that a TKBC problem can be solved in two steps. First by solving an atemporal
KBC problem and then narrowing down the correct answer sets that are only true
at the time of interest. Therefore, we introduced time-agnostic boxes to model
sets of answers obtained from KBC models. Time-aware boxes are used as a
filter to pick out time-dependent answers. TIME2BOX outperforms existing TKBC
methods in both link prediction and time prediction on two datasets -
WIKIDATA12k and WIKIDATA114K. By investigating the model performance on
statements with different types of validity information, we found that the
improvement of TIME2BOX largely attributes to its better ability to handle
statements with interval-based validity information. In the future, we will
explore how to incorporate spatial scopes of statements into KGE models, such
that KBC can benefit from both spatial and temporal scopes of statements.

###### Acknowledgements.

This work was partially supported by the NSF award 2033521, “KnowWhereGraph:
Enriching and Linking Cross-Domain Knowledge Graphs using Spatially-Explicit
AI Technologies”.

## References

  * (1)
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014\.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ (2014).
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating embeddings for modeling multi-relational data.  _Advances in neural information processing systems_ 26 (2013), 2787–2795.
  * Boschee et al. (2015) Elizabeth Boschee, Jennifer Lautenschlager, Sean O’Brien, Steve Shellman, James Starz, and Michael Ward. 2015.  ICEWS Coded Event Data.
  * Cai et al. (2019) Ling Cai, Bo Yan, Gengchen Mai, Krzysztof Janowicz, and Rui Zhu. 2019.  TransGCN: Coupling Transformation Assumptions with Graph Convolutional Networks for Link Prediction. In _K-CAP 2019_. 131–138.
  * Dasgupta et al. (2018) Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha Talukdar. 2018.  Hyte: Hyperplane-based temporally aware knowledge graph embedding. In _EMNLP_.
  * Deng et al. (2020) Songgaojun Deng, Huzefa Rangwala, and Yue Ning. 2020\.  Dynamic Knowledge Graph based Multi-Event Forecasting. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1585–1595.
  * García-Durán et al. (2018) Alberto García-Durán, Sebastijan Dumančić, and Mathias Niepert. 2018.  Learning Sequence Encoders for Temporal Knowledge Graph Completion. In _EMNLP_. Association for Computational Linguistics, Brussels, Belgium, 4816–4821.
  * Goel et al. (2020) Rishab Goel, Seyed Mehran Kazemi, Marcus Brubaker, and Pascal Poupart. 2020.  Diachronic embedding for temporal knowledge graph completion. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 3988–3995.
  * Jain et al. (2020) Prachi Jain, Sushant Rathi, Mausam, and Soumen Chakrabarti. 2020.  Temporal Knowledge Base Completion: New Algorithms and Evaluation Protocols. In _EMNLP_. Association for Computational Linguistics, Online, 3733–3747.
  * Jin et al. (2020) Woojeong Jin, Meng Qu, Xisen Jin, and Xiang Ren. 2020\.  Recurrent Event Network: Autoregressive Structure Inference over Temporal Knowledge Graphs. In _EMNLP_. 6669–6683.
  * Lacroix et al. (2019) Timothée Lacroix, Guillaume Obozinski, and Nicolas Usunier. 2019.  Tensor Decompositions for Temporal Knowledge Base Completion. In _ICML_.
  * Leblay and Chekol (2018) Julien Leblay and Melisachew Wudage Chekol. 2018.  Deriving Validity Time in Knowledge Graph. In _Companion Proceedings of the The Web Conference 2018_ _(WWW ’18)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1771–1776.
  * Lin et al. ([n. d.]) Yankai Lin, Zhiyuan Liu, Huan-Bo Luan, Maosong Sun, Siwei Rao, and Song Liu. [n. d.].  Modeling Relation Paths for Representation Learning of Knowledge Bases. In _EMNLP_.
  * Ma et al. (2019) Yunpu Ma, Volker Tresp, and Erik A Daxberger. 2019.  Embedding models for episodic knowledge graphs.  _Journal of Web Semantics_ 59 (2019), 100490.
  * Mai et al. (2019) Gengchen Mai, Krzysztof Janowicz, Bo Yan, Rui Zhu, Ling Cai, and Ni Lao. 2019\.  Contextual graph attention for answering logical queries over incomplete knowledge graphs. In _K-CAP 2019_. 171–178.
  * Patel and Sankar (2020) Dhruvesh Patel and Shib Sankar. 2020.  Representing joint hierarchies with box embeddings.  _Automated Knowledge Base Construction_ (2020).
  * Ren et al. (2019) Hongyu Ren, Weihua Hu, and Jure Leskovec. 2019.  Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings. In _ICML_.
  * Rezatofighi et al. (2019) Hamid Rezatofighi, Nathan Tsoi, JunYoung Gwak, Amir Sadeghian, Ian Reid, and Silvio Savarese. 2019\.  Generalized intersection over union: A metric and a loss for bounding box regression. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 658–666.
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018.  Modeling relational data with graph convolutional networks. In _European Semantic Web Conference_. Springer, 593–607.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019\.  Rotate: Knowledge graph embedding by relational rotation in complex space.  _arXiv preprint arXiv:1902.10197_ (2019).
  * Trivedi et al. (2017) Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. 2017\.  Know-evolve: deep temporal reasoning for dynamic knowledge graphs. In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_. 3462–3471.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction. ICML.
  * Venn (1880) John Venn. 1880\.  I. On the diagrammatic and mechanical representation of propositions and reasonings.  _The London, Edinburgh, and Dublin philosophical magazine and journal of science_ 10, 59 (1880), 1–18.
  * Vilnis et al. (2018) Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. 2018\.  Probabilistic embedding of knowledge graphs with box lattice measures.  _arXiv preprint arXiv:1805.06627_ (2018).
  * Xu et al. (2019) Chengjin Xu, Mojtaba Nayyeri, Fouad Alkhoury, Hamed Shariat Yazdi, and Jens Lehmann. 2019\.  Temporal knowledge graph embedding model based on additive time series decomposition.  _arXiv preprint arXiv:1911.07893_ (2019).
  * Yang et al. (2014) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2014.  Embedding entities and relations for learning and inference in knowledge bases.  _arXiv preprint arXiv:1412.6575_ (2014).
  * Zaheer et al. (2017) Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J Smola. 2017.  Deep Sets. In _NIPS_. 3394–3404.

##  Appendix A Data Statistics

##### Generation of WIKIDATA114k

We extracted a sport-centric subgraph from WIKIDADA432k. We first picked out
statements where the relation memberOfSportsTeam appears and obtained an
entity set from those statements. Then we find all the statements that
entities obtained from the previous step participate in as our initial
subgraph. Finally, we ensure that each entity/relation is associated with at
least 5 statements and the time period is restricted to [1883, 2023] for
temporal statements, which encloses most of the temporal statements in the
initial subgraph. This results in 1.7 million statements with 114k entities
and 126 relations, and thus named as WIKIDATA114k. See Table 6 for data
statistics.

| WIKIDATA12k | WIKIDATA114k
---|---|---
#entities | 12,544 | 114,351
#relations | 24 | 126
time period | [19, 2020] | [1883, 2023]
train | #all | 32,497 | 1,670,969
#time instant | 14,099 | 175,637
#start time only | 4,089 | 44,809
#end time only | 1,273 | 2,164
#full time interval | 13,035 | 402,135
#no time | 0 | 1,046,224
valid | #all | 4,051 | 11,720
#time instant | 1,857 | 1,177
#start time only | 322 | 342
#end time only | 76 | 11
#full time interval | 1,796 | 2,655
#no time | 0 | 7,535
#test | #all | 4,043 | 11,854
#time instant | 1,844 | 1,219
#start time only | 324 | 306
#end time only | 56 | 15
#full time interval | 1,819 | 2,790
#no time | 0 | 7,524
Table 6. Statistics of these datasets used.

##  Appendix B Hyperparameter Settings

We tune models by the MRR on the validation set. Grid search is performed over
negative samples $k$ = [16, 32, 64, 128], learning rate $lr=$ [0.003, 0.002,
0.001], batch size $b=$ [1500, 2000, 2500, 3000, 3500]; dimension $d=$ [200,
300, 400], and weight for time smoothness regularizer $\beta=$ [0.0, 0.1,
0.001, 0.0001], as shown in Table 7.888Experiments are terminated after 10000
steps. We find that effects of different hyperparameters are minimal except
for learning rate as the trained model usually converge to similar MRRs as
long as they are trained thoroughly. We also observe that time smoothness
regularizer is useful in learning time embeddings on WIKIDATA12k while failing
to improve the model on WIKIDATA114k. This may be due to data sparsity with
regard to time. As the time span of WIKIDATA114k is much smaller, time
information is intensive and thus models are capable of learning temporal
order between timestamps implicitly.

| #negative samples | # learning rate
---|---|---
| 16 | 32 | 64 | 128 | 0.003 | 0.002 | 0.001
MRR | 36.02 | 36.68 | 37.06 | 37.30 | 36.64 | 36.82 | 37.30
MR | 97 | 100 | 98 | 101 | 126 | 103 | 101
HITS@1 | 25.96 | 26.81 | 27.25 | 27.38 | 26.83 | 26.73 | 27.38
| #batch size | # dimension
| 2000 | 2500 | 3000 | 3500 | 200 | 300 | 400
MRR | 36.71 | 36.87 | 37.30 | 36.78 | 36.12 | 36.88 | 37.30
MR | 100 | 114 | 101 | 100 | 106 | 101 | 101
HITS@1 | 26.59 | 26.88 | 27.38 | 26.77 | 25.98 | 26.88 | 27.38
Table 7. Effects of hyper-parameters on WIKIDATA12k

##  Appendix C Experimental Setup

Upon inspection on implementations of TKBC models, we find there are two
common issues.

First, SOTAs only learn time embeddings for timestamps that appear in training
set, which would be problematic at testing. For instance, suppose a sorted
(ascending) list of timestamps occurring in training set is [1540, 1569, 1788,
1789, 1790], SOTAs only learn embeddings for these timestamps, while ignoring
intermediate timestamps. As a result, they cannot answer queries when the
associated time is not in the list, such as (s, r, ?o, 1955). This problem
would be even worse regarding time interval generation. As when we need to
grow a time point to a time interval by extending it to the left or the right,
we may jump from one year to a year far away from it. For instance, from 1569
to 1540 (left) or 1788 (right). This is not reasonable and thus may severely
affect the evaluation on time prediction. In order to address this issue, we
enumerate all the time points in the time span of the training set with a
fixed granularity (i.e., year) and use them for all models at training
periods.

The other issue is about the evaluation of link prediction task on time
interval-based statements (including closed interval-based and left/right-open
interval-based statements). In existing works, the evaluation boils down to
assessing the correctness of answering a timestamp-based query by randomly
picking one timestamp from a set of timestamps within the time interval and
then measuring the performance on the newly generated query (i.e., the
timestamp-based query). However, this is problematic. For closed interval-
based samples, the evaluation results may vary from randomly sampled
timestamps and thus may not be stable. For left/right-open interval-based
statements, it is more severe. For instance, for a left-open interval-based
test sample (Albert Einstein, educatedAt, ?o, [-, 1905]), Lacroix et al.
(2019) randomly pick a year before 1905, say 1000, and evaluate whether a
model can output the correct answer (University of Zurich) to the new query
(Albert Einstein, educatedAt, ?o, 1000). Clearly, there is no correct answer
at all since he was born in 1879. Therefore, the evaluation on such test
samples may not be plausible. In order to address these issues, for a closed
interval-based sample, we enumerate all the time points in the interval and do
evaluation on each time point separately. Then we use the average performance
over them as the overall evaluation. For the latter, we only consider the
known endpoint in an interval, namely $(s,r,?o,st)$ for right-open cases and
$(s,r,?o,et)$ for left-open cases.

##  Appendix D Link Prediction Performance by types of validity information

Table 8 shows the comparison between different methods in terms of different
types of validity information.

Datasets | WIKIDATA12k
---|---
Types | Time Interval (O) | Time Interval (C) | Time Instant | No Time
Methods | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX
MRR | 46.74 | 51.48 | 25.30 | 28.44 | 41.11 | 43.13 | - | -
MR | 203 | 68 | 273 | 84 | 350 | 125 | - | -
HITS@1 | 19.21 | 41.05 | 11.54 | 18.5 | 32.6 | 33.30 | - | -
Datasets | WIKIDATA114k
Types | Time Interval (O) | Time Interval (C) | Time Instant | No Time
Methods | TIMEPLEX | TIME2BOX | TIMEPLEX | TIME2BOX | TIMEPLEX | TIME2BOX | TIMEPLEX | TIME2BOX
MRR | 22.63 | 22.43 | 17.72 | 18.85 | 20.81 | 21.32 | 67.85 | 68.40
MR | 346 | 168 | 155 | 147 | 176 | 193 | 430 | 172
HITS@1 | 4.98 | 11.21 | 3.94 | 8.35 | 11.07 | 11.16 | 61.52 | 60.30

Table 8. Link prediction evaluation by types of validity information. Time
Interval (O) denotes left/right-open interval-based statements, and Time
Interval (C) refers to closed interval-based statements.

##  Appendix E Time Prediction Performance by duration length

Table 9 and 10 compare the performance of TIMEPLEX and TIME2BOX on the time
prediction task across different duration lengths on two datasets. Test
samples are first classified into three groups by duration (du) and then
evaluate the performance of each group. For an interval $I$,
$du=I_{max}-I_{min}+1$. It shows that our improvements are more pronounced in
terms of shorter durations in general.

| WIKIDATA12k
---|---
Duration (du) | du=1 | 1<du<=5 | du>5
Method | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX
gIOU@1 | 30.29 | 38.09 | 39.51 | 43.68 | 47.4 | 46.99
aeIOU@1 | 20.84 | 28.34 | 15.86 | 22.95 | 18.23 | 13.20
gaeIOU@1 | 12.47 | 18.62 | 11.73 | 16.34 | 16.85 | 11.20

Table 9. Time prediction by duration on WIKIDATA12k

| WIKIDATA114k
---|---
Duration (du) | du=1 | 1<du<=5 | du>5
Method | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX | TIMEPLEX base | TIME2BOX
gIOU@1 | 28.75 | 37.03 | 29.77 | 38.36 | 27.99 | 39.07
aeIOU@1 | 25.80 | 34.16 | 16.52 | 21.54 | 7.09 | 9.94
gaeIOU@1 | 14.69 | 21.08 | 10.50 | 14.50 | 3.85 | 7.02

Table 10. Time prediction by duration on WIKIDATA114k

##  Appendix F Model Parameter Comparison

Table 11 summarizes the number of parameters used in each method.

Models | Number of parameters
---|---
TNTComplex | 2d($|E|$ \+ $|T|$ \+ 4$|R|$)
TIMEPLEX base | 2d($|E|$ \+ $|T|$ \+ 6$|R|$)
TIME2BOX | d($|E|$ \+ 2$|T|$ \+ 2$|R|$) + $4d^{2}$
Table 11. Number of parameters for each model


# Dealing with Abbreviations in the Slovenian Biographical Lexicon

Angel Daza1 Antske Fokkens1 Tomaž Erjavec2
1CLTL, Vrije Universiteit Amsterdam
2Department of Knowledge Technologies, Jožef Stefan Institute
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Abbreviations present a significant challenge for NLP systems because they
cause tokenization and out-of-vocabulary errors. They can also make the text
less readable, especially in reference printed books, where they are
extensively used. Abbreviations are especially problematic in low-resource
settings, where systems are less robust to begin with. In this paper, we
propose a new method for addressing the problems caused by a high density of
domain-specific abbreviations in a text. We apply this method to the case of a
Slovenian biographical lexicon and evaluate it on a newly developed gold-
standard dataset of 51 Slovenian biographies. Our abbreviation identification
method performs significantly better than commonly used ad-hoc solutions,
especially at identifying unseen abbreviations. We also propose and present
the results of a method for expanding the identified abbreviations in context.

##  1 Introduction

Abbreviations such as "b." for "born", or "gr." for "graduated" are a common
issue when dealing with digitized texts which use a large number of them for
space-saving reasons. They are also a known problem when processing technical
documents Park and Byrd (2001) and biomedical texts Jin et al. (2019). In this
paper, we examine the case of biographical dictionaries, i.e. collections of
biographies that have been digitized, and, in particular, the Slovenian
Biographical Lexicon.

To automatically extract facts from biographical texts, Digital Humanities
researchers normally rely on out-of-the-box NLP tools such as Stanza Qi et al.
(2020) or SpaCy.111https://spacy.io/ These tools are often adequate for
identifying sentences which are then used as input for higher-level downstream
tasks, for manual inspection, and for visualization purposes. However, out-of-
the-box tools are designed to work for the broadest possible text domains and
cover the most common cases. This impacts performance significantly when
dealing with domain-specific data, such as entries of biographical
dictionaries, and more so when they contain a lot of abbreviations. The
problem is even more pronounced when dealing with a relatively lower resource
language, such as Slovenian. The performance bottleneck occurs already at the
first step, i.e. tokenization: in order to perform good tokenization in
domain-specific texts, we need to have a reliable method for identifying
abbreviations such that the tokenizer does not split them wrongly, generating
faulty tokens and incomplete sentences. In this paper we:

  * •

Quantify the effect that abbreviations have on a downstream task such as NER
on Slovenian biographical texts.

  * •

Propose a method for abbreviation identification, apply it to raw texts and
compare it to straightforward baselines.

  * •

Analyze the feasibility of using contextually dependent word embeddings, in
particular, the SloBERTa Ulčar and Robnik-Šikonja (2021) language model, to
automatically expand abbreviations in text and improve readability.

  * •

Evaluate the performance of our methods on a new human-curated dataset with,
inter alia, gold tokens, sentences, named entities, and expanded
abbreviations.222https://github.com/angel-daza/abbreviation-detector

##  2 Related Work

Specific work addressing abbreviations is scarce. We think this is due to the
fact that it is addressed as a preprocessing step with tailored solutions for
each specific use case, involving regular expressions, or corpus-specific
rules Bollmann et al. (2011). A few papers try to construct methods for a
general solution to this problem. For instance, Park and Byrd (2001) propose a
pipeline system to induce acronyms, where every sequence of characters
(separated by spaces) is considered a candidate abbreviation if it satisfies
certain conditions. Żelasko (2018) proposes a more advanced approach based on
an LSTM classifier that uses morphosyntactic information about a sentence to
directly infer the correct expansion of an abbreviation in Polish. Direct work
on abbreviations also exists in the biomedical domain, including detection and
disambiguation Stevenson et al. (2009) as well as abbreviation expansion Jin
et al. (2019). Finally, Gorman et al. (2021) have recently developed an
English dataset to explore abbreviation expansion methods taking into account
the context.

Another common way to address the difficulty of domain-specific texts is text
normalization, which is the task of translating a domain-specific text into
more standard form (this can be at different levels such as lexical or
morphological) that is easier to process by general purpose NLP tools. This
approach is common when dealing with user generated text and social media
Pennell and Liu (2011); Baldwin et al. (2015); van der Goot (2019), and also
historical texts Scherrer and Erjavec (2013); Ljubesic et al. (2016); Bollmann
(2019).

One drawback of text normalization is that it is frequently implemented using
an Encoder-Decoder approach Robertson and Goldwater (2018); Bollmann et al.
(2019), which requires a big-enough parallel corpus to be trained and obtain
good-quality results. Another drawback is the fact that it generates a new
standard sentence, which is not a desired side effect if we want to preserve
word by word the original biographical text. In contrast to the normalization
task, we are interested in preserving the original text and only identifying
(and perhaps expanding) the abbreviations that are problematic for the NLP
tools.

##  3 Dataset

The Slovenian Biographical Lexicon (SBL) was published in 15 volumes
(1925–1991) and contains 5,047 biographies Ogrin et al. (2013). For the
experiments described in this paper, we have created the dataset SBL-51abbr
Erjavec et al. (2022), which consists of 51 randomly selected entries from
SBL333http://hdl.handle.net/11356/1588. The text of each entry is manually
tokenized and sentence segmented, marked with named entities, and lemmatized
words. It has also been automatically annotated with Universal Dependencies
PoS tags, morphological features and dependency parses using CLASSLA Ljubešić
and Dobrovoljc (2019),444https://pypi.org/project/classla/ a fork of the
Stanford Stanza pipeline Qi et al.
(2020),555https://stanfordnlp.github.io/stanza/ which is the state-of-the-art
tool for annotating Slovenian. Crucially for the envisaged use of the corpus,
the abbreviations in the corpus have been manually expanded so that the
expansions are in the correct inflected form. The curated dataset consists of
655 sentences (see Table 1). It is available in the canonical TEI encoding,
and derived plain text and CoNLL-U files. The plain-text file has
abbreviations and their expansions marked up with [[…]]((…)) respectively.
There are two CoNLL-U files, one with the text stream with abbreviations, and
one with the text stream with expansions. Note that only the one with
expansions has syntactic parses. Both CoNLL-U files have the expansions /
abbreviations and named entities marked up in IOB format in the last column.

We use this dataset as a gold standard to test the performance of our proposed
methods. We randomly split the available data into three portions: 70% for
training, 10% for development and 20% for testing.

Split | Sents | Abbrs | Unique | Unseen
---|---|---|---|---
Train | 458 | 1385 | 399 | 0
Dev | 66 | 236 | 130 | 33
Test | 131 | 420 | 181 | 70
$\Sigma$ | 655 | 2041 | 710 |
Table 1: Abbreviation statistics on the SBL-51abbr dataset. We count the total
number of abbreviations, the unique types and the number of unseen
abbreviations in the dev and test splits.

##  4 Impact of Abbreviations

We first quantify the impact that the high number of abbreviations in the
SBL-51abbr corpus has when processing the raw texts with CLASSLA Ljubešić and
Dobrovoljc (2019) and performing NER. We compare the performance on the
original texts (with all abbreviations) with a second scenario where
abbreviations were substituted with their gold expansions. Table 2 shows the
performance per class when processing the original version (the first row of
numbers per label), and right below is the performance when processing the
same texts but without any abbreviation. There is a significant boost all
across the board for the fully expanded texts, resulting on over 30 F1 points
of improvement on the macro average measure. This shows that having effective
methods for abbreviation identification and expansion can be beneficial.

Label | P | R | F1
---|---|---|---
PER | 68.75 | 22.45 | 33.85
76.80 | 65.31 | 70.59
DERIV-PER | 50.00 | 4.76 | 8.70
92.86 | 61.90 | 74.29
LOC | 85.29 | 39.73 | 54.21
82.32 | 92.47 | 87.10
MISC | 65.38 | 12.41 | 20.86
56.14 | 23.36 | 32.99
ORG | 23.53 | 14.81 | 18.18
22.06 | 55.56 | 31.58
macro_avg | 58.59 | 18.83 | 27.16
66.03 | 59.72 | 59.31
Table 2: NER scores when applied to the original sentences with abbreviations
(upper rows) vs sentences with all abbreviations expanded (lower rows).

##  5 Dealing with Abbreviations

Figure 1: We first train a classifier for identifying abbreviations
(SloBERTa+Neural linear layer) and then match each of the identified
candidates to use SloBERTa as a predictor for that slot. We only keep the
suggested expansion if it meets the requirements.

###  5.1 Baselines

Dictionary-based: to bypass tokenizer-specific noise, we split every document
by spaces to obtain a list of dirty tokens.666We call them dirty because they
will have punctuation attached to them. For example ”Hello world!” will be
tokenized as [’Hello’, ’world!’] instead of [’Hello’, ’world’, ’!’] which
would be the optimal tokenization. For each token, we first clean it, meaning
we remove all special characters except full stops. If the clean token does
not end with a full stop we skip it, otherwise we strip the full stop and
check if the entry exists in a large dictionary. We use two dictionaries: the
Hunspell dictionary,777https://github.com/hunspell/hunspell a popular tool
used for spelling correction, and GigaFida 2.0 Krek et al. (2020), a big
reference corpus of standard Slovene. Because dictionaries only contain
entries for complete words, we consider the token an abbreviation if no entry
exists.

Corpus-based: we tokenize the training corpus using CLASSLA and compute the
frequency for all token unigrams $t_{1}$ and bigrams $(t_{1},t_{2})$ in the
corpus. If a bigram contains a full stop as a second component or if a unigram
has a full stop as its last character,888We test for this case because, if the
tokenizer rightly recognized the abbreviation, then the full stop will still
be attached to it then we increase the count of $t_{1}$ in $\mathcal{A}$
otherwise we increase the count of $t_{1}$ in $\mathcal{B}$. We take all
$t_{1}$s that appear in both lists and calculate their probability to be an
abbreviation as:

$P(t_{1}=abbr)=\frac{freq(t_{1}\epsilon\mathcal{A})}{freq(t_{1}\epsilon\mathcal{A})+freq(t_{1}\epsilon\mathcal{B})}$
(1)

If the probability $P(t_{1}=abbr)\geq 0.8$ then $t_{1}$ is considered to be an
abbreviation, otherwise we skip it. This method will, of course, carry over
some of the tokenization mistakes. The reasoning behind this baseline is to
capture the number of times a given token appears before a full stop compared
to the total times it appears in the corpus. If it is the case that most of
the occurrences of such a token are immediately followed by a full stop, then
it is most likely an (unrecognized) abbreviation.

###  5.2 Abbreviation Classifier

We propose an automatic method for identifying abbreviations by fine-tuning a
classifier on top of the SLoBERTa language model Ulčar and Robnik-Šikonja
(2021). We again obtain the sequence of tokens by splitting the raw texts by
spaces. We treat each one of the dirty tokens as a separate input sequence to
SloBERTa. We train the classifier using the gold abbreviation labels to
predict if a token is an abbreviation or not (Figure 1, bottom).

###  5.3 Abbreviation Expansion

Once we have our text with abbreviation candidates identified, for each
candidate, we take the full sentence it appears in, mask it and let SloBERTa
predict the masked token. We take SloBERTa’s prediction to be a valid
expansion if one of the top 5 predicted candidates starts with the same letter
as the masked abbreviation, otherwise we leave the original abbreviation. This
way we are substituting each candidate in-context and thus approaching the
optimal scenario with the fully expanded sentences where NER performed much
better (see Table 2). A visualization of both the identification and expansion
steps of our method is given in Figure 1.

##  6 Results and Evaluation

###  6.1 Abbreviation Identification Baselines

We first present the results on the test set obtained by our proposed
baselines in Table 3. These baselines represent common pre-processing
approaches to dealing with abbreviations. We can see that the two dictionary
versions suffer from low recall, especially the GigaFida dictionary with only
20%. This behavior is expected since we are dealing with a domain-specific
(and partially historical) text. The second baseline behaves much better and
achieves an 85.34 F1 score. The Bigrams+Dict version mixes both approaches,
which improves the coverage of identified abbreviations, but unfortunately
lowers the high precision of the bigram approach.

Baseline | P | R | F1
---|---|---|---
GigaFida Dict | 89.36 | 20.00 | 32.68
Hunspell Dict | 80.81 | 71.19 | 75.70
Corpus Bigrams | 95.85 | 76.90 | 85.34
Bigrams+Dict | 73.27 | 95.95 | 83.09
Table 3: Abbreviation identification baseline results on the test set. They
show trade-offs between precision and recall. The bigrams method performs the
best.

###  6.2 Abbreviation Classifier

The baselines show a trade-off between good precision or good recall. In
contrast, Table 4 shows that our SloBERTa method significantly increases the
recall without hampering precision. We fine-tuned SloBERTa999We used the
default settings from HuggingFace https://huggingface.co/EMBEDDIA/sloberta for
5 epochs and pick the model that performs best on the development set. We
present the mean of 5 experiments with different random seeds together with
the standard deviation. The results demonstrate that this is a stable approach
for identifying abbreviations in text.

Split | P | R | F1
---|---|---|---
Dev | 95.91±0.75 | 97.91±1.9 | 96.89±0.9
Test | $93.94^{\pm 1.5}$ | 98.10±2.0 | 95.97±1.3
Table 4: Abbreviation identification results with our SloBERTa binary
classifier. Results on test are 10 points above the best baseline.

###  6.3 Abbreviation Expansion

We measure the success of our abbreviation expansion method by re-running the
NER tagger on the sentences with the expanded abbreviations as predicted by
SloBERTa (see Table 5). From the 420 abbreviations in the test set, 154 where
expanded following our heuristic and the rest of abbreviations in the
sentences were left untouched. We can compare these scores directly with our
analysis from Table 2 and see that even though our method for expanding is
quite basic, it already gets us closer to the ceiling scores (where all gold
expansions were substituted). Important gains can be seen in all categories
and the macro average score reached with the predicted expansions is 49.64 F1
which is 22 points above the 27.16 F1 obtained originally.

Label | P | R | F1
---|---|---|---
PER | 40.54 | 67.67 | 50.70
DERIV-PER | 78.57 | 55.00 | 64.71
LOC | 72.33 | 82.73 | 77.18
MISC | 34.34 | 27.64 | 30.63
ORG | 17.14 | 46.15 | 25.00
macro_avg | 48.59 | 55.84 | 49.64
Table 5: The NER results on the test set after applying SloBERTa-based
expansions show consistent improvements compared to the original sentences
(cf. Table 2)

##  7 Conclusions

In this paper we focused on the task of Named Entity Recognition to quantify
the impact of abbreviations in a text by comparing the performance of the
CLASSLA NER tagger on the same sentences with and without abbreviations. We
presented a gold-standard dataset consisting of 51 biographies in Slovenian (a
limited-resource language) in a specialized text domain. We also presented a
method for automatically identifying abbreviations and expanding them without
the need for a tokenizer. The biggest advantage of our method is that it can
be applied out-of-the-box for any language which has a large language model
available and does not need ad-hoc training data or large fixed dictionaries.
Our abbreviation identification classifier obtains better precision and better
recall when compared to other straightforward approaches to identify
abbreviations.

Finally, we presented a method that uses a pre-trained language model to
predict plausible expansions for the identified abbreviations. We notice that
our method is still simple but already achieves better results than directly
processing the original sentences with abbreviations. In future work we aim to
explore more sophisticated methods for abbreviation expansion that allow us to
further improve the readability of texts. We find our results encouraging for
researchers working with limited domains who may find a similar approach
helpful for improving performance in other tasks.

## Limitations

The results presented in this paper have been evaluated on the specific use
case of the Slovenian Biographical Lexicon. When considering to apply this
approach to other use cases, the following limitations should be taken into
account:

#### Good Use Case.

The SBL is a good use case in the sense that this is a domain with a high
density of abbreviations and thus a relatively high number of positive class
examples. This means that the relatively small dataset was comparatively rich
(i.e. another domain may require more data) and the potential of improving
results is relatively high (i.e. identifying abbreviations may have less
impact on downstream tasks in other domains).

#### Language Model Required.

A large language model is needed for this approach and may not be available
for many low or even medium resource languages. This is unfortunate, because
this research aims to support relatively low resource languages that must rely
on standard tools, because there are limited resources for creating new data
sets and models.

#### Expanding Abbreviations Remains Largely Unsolved.

The results for expanding abbreviations are still meagre. Even though the
current approach is simple, it may already represent an upperbound due to the
productive character of abbreviations in this domain, the rich inflection of
Slovenian, and the considerable effort required to obtain more training data.

## Acknowledgements

This work was partially supported by the EU Horizon 2020 project InTaVia:
In/Tangible European Heritage - Visual Analysis, Curation and Communication
(http://intavia.eu) under grant agreement No. 101004825.

## References

  * Baldwin et al. (2015) Timothy Baldwin, Marie Catherine de Marneffe, Bo Han, Young-Bum Kim, Alan Ritter, and Wei Xu. 2015.  Shared tasks of the 2015 workshop on noisy user-generated text: Twitter lexical normalization and named entity recognition.  In _Proceedings of the Workshop on Noisy User-generated Text_ , pages 126–135, Beijing, China. Association for Computational Linguistics.
  * Bollmann (2019) Marcel Bollmann. 2019.  A large-scale comparison of historical text normalization systems.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 3885–3898, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Bollmann et al. (2019) Marcel Bollmann, Natalia Korchagina, and Anders Søgaard. 2019.  Few-shot and zero-shot learning for historical text normalization.  In _Proceedings of the 2nd Workshop on Deep Learning Approaches for Low-Resource NLP (DeepLo 2019)_ , pages 104–114, Hong Kong, China. Association for Computational Linguistics.
  * Bollmann et al. (2011) Marcel Bollmann, Florian Petran, and Stefanie Dipper. 2011.  Rule-based normalization of historical texts.  In _Proceedings of the Workshop on Language Technologies for Digital Humanities and Cultural Heritage_ , pages 34–42, Hissar, Bulgaria. Association for Computational Linguistics.
  * Erjavec et al. (2022) Tomaž Erjavec, Petra Vide Ogrin, Jakob Lenardič, Mojca Mlinar Strgar, and Simona Frankl. 2022.  Annotated sample of the slovenian biographical lexicon SBL-51abbr 1.0.  Slovenian language resource repository CLARIN.SI.
  * Gorman et al. (2021) Kyle Gorman, Christo Kirov, Brian Roark, and Richard Sproat. 2021.  Structured abbreviation expansion in context.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 995–1005, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Jin et al. (2019) Qiao Jin, Jinling Liu, and Xinghua Lu. 2019.  Deep contextualized biomedical abbreviation expansion.  In _Proceedings of the 18th BioNLP Workshop and Shared Task_ , pages 88–96, Florence, Italy. Association for Computational Linguistics.
  * Krek et al. (2020) Simon Krek, Špela Arhar Holdt, Tomaž Erjavec, Jaka Čibej, Andraz Repar, Polona Gantar, Nikola Ljubešić, Iztok Kosem, and Kaja Dobrovoljc. 2020.  Gigafida 2.0: The reference corpus of written standard Slovene.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 3340–3345, Marseille, France. European Language Resources Association.
  * Ljubešić and Dobrovoljc (2019) Nikola Ljubešić and Kaja Dobrovoljc. 2019.  What does Neural Bring? Analysing Improvements in Morphosyntactic Annotation and Lemmatisation of Slovenian, Croatian and Serbian.  In _Proceedings of the 7th Workshop on Balto-Slavic Natural Language Processing_ , pages 29–34, Florence, Italy. Association for Computational Linguistics.
  * Ljubesic et al. (2016) Nikola Ljubesic, Katja Zupan, Darja Fišer, and Tomaž Erjavec. 2016.  Normalising slovene data: historical texts vs. user-generated content.  In _KONVENS_.
  * Ogrin et al. (2013) Petra Vide Ogrin, Simona Frankl, Mojca Mlinar Strgar, Izidor Cankar, Tomaž Erjavec, and Joahim Dokler, editors. 2013.  _Slovenski biografski leksikon, elektronski vir (Slovenian Biographical Lexicon, Digital Edition)_.  Slovenian Academy of Sciences and Arts.  http://www.slovenska-biografija.si/kolofon/sbl/.
  * Park and Byrd (2001) Youngja Park and Roy J. Byrd. 2001.  Hybrid text mining for finding abbreviations and their definitions.  In _Proceedings of the 2001 Conference on Empirical Methods in Natural Language Processing_.
  * Pennell and Liu (2011) Deana Pennell and Yang Liu. 2011.  A character-level machine translation approach for normalization of SMS abbreviations.  In _Proceedings of 5th International Joint Conference on Natural Language Processing_ , pages 974–982, Chiang Mai, Thailand. Asian Federation of Natural Language Processing.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020\.  Stanza: A python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108, Online. Association for Computational Linguistics.
  * Robertson and Goldwater (2018) Alexander Robertson and Sharon Goldwater. 2018.  Evaluating historical text normalization systems: How well do they generalize? In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 720–725, New Orleans, Louisiana. Association for Computational Linguistics.
  * Scherrer and Erjavec (2013) Yves Scherrer and Tomaž Erjavec. 2013.  Modernizing historical Slovene words with character-based SMT.  In _Proceedings of the 4th Biennial International Workshop on Balto-Slavic Natural Language Processing_ , pages 58–62, Sofia, Bulgaria. Association for Computational Linguistics.
  * Stevenson et al. (2009) Mark Stevenson, Yikun Guo, Abdulaziz Alamri, and Robert Gaizauskas. 2009.  Disambiguation of biomedical abbreviations.  In _Proceedings of the BioNLP 2009 Workshop_ , pages 71–79, Boulder, Colorado. Association for Computational Linguistics.
  * Ulčar and Robnik-Šikonja (2021) Matej Ulčar and Marko Robnik-Šikonja. 2021.  _Slovenian RoBERTa contextual embeddings model: SloBERTa 2.0_.  Slovenian language resource repository CLARIN.SI.  http://hdl.handle.net/11356/1397.
  * van der Goot (2019) Rob van der Goot. 2019.  MoNoise: A multi-lingual and easy-to-use lexical normalization tool.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 201–206, Florence, Italy. Association for Computational Linguistics.
  * Żelasko (2018) Piotr Żelasko. 2018.  Expanding abbreviations in a strongly inflected language: Are morphosyntactic tags sufficient? In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).