# Leveraging Pre-trained Language Models for Time Interval Prediction in Text-
Enhanced Temporal Knowledge Graphs

Duygu Sezen Islakoglu  Utrecht UniversityNetherlands<EMAIL_ADDRESS>,
Mel Chekol  Utrecht UniversityNetherlands<EMAIL_ADDRESS>and  Yannis
Velegrakis  Utrecht UniversityNetherlands<EMAIL_ADDRESS>
(2018)

###### Abstract.

Most knowledge graph completion (KGC) methods learn latent representations of
entities and relations of a given graph by mapping them into a vector space.
Although the majority of these methods focus on static knowledge graphs, a
large number of publicly available KGs contain temporal information stating
the time instant/period over which a certain fact has been true. Such graphs
are often known as temporal knowledge graphs. Furthermore, knowledge graphs
may also contain textual descriptions of entities and relations. Both temporal
information and textual descriptions are not taken into account during
representation learning by static KGC methods, and only structural information
of the graph is leveraged. Recently, some studies have used temporal
information to improve link prediction, yet they do not exploit textual
descriptions and do not support inductive inference (prediction on entities
that have not been seen in training).

We propose a novel framework called TEMT that exploits the power of pre-
trained language models (PLMs) for text-enhanced temporal knowledge graph
completion. The knowledge stored in the parameters of a PLM allows TEMT to
produce rich semantic representations of facts and to generalize on previously
unseen entities. TEMT leverages textual and temporal information available in
a KG, treats them separately, and fuses them to get plausibility scores of
facts. Unlike previous approaches, TEMT effectively captures dependencies
across different time points and enables predictions on unseen entities. To
assess the performance of TEMT, we carried out several experiments including
time interval prediction, both in transductive and inductive settings, and
triple classification. The experimental results show that TEMT is competitive
with the state-of-the-art.

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX††price:

##  1\. Introduction

Knowledge Graphs (KGs) are directed graphs that model real-world entities and
relationships as nodes and edges between them. They store knowledge, i.e.,
facts, in a structured and interpretable way, typically as triples of the form
$\langle$subject, relation, object$\rangle$, e.g. $\langle$Obama, presidentOf,
U.S.$\rangle$. They find a wide range of applications and have been used in
recommendation systems, question-answering systems, and many knowledge-
intensive systems, including virtual assistants and chatbots (Weikum et al.,
2021).

Knowledge graphs are often incomplete, meaning that some elements of the facts
are not available. To this end, KG completion (KGC) methods aim at finding
missing links between the entities. Most of the studies on KG completion have
focused on static knowledge graphs where the graph remains unchanged over time
(Ji et al., 2022). However, in real life, facts are not always valid
throughout time, but only in specific time periods. For instance, presidents
of a country are valid only throughout their term. To model this, triples in a
KG may have validity time intervals associated with them. This additional
information converts a triple into a quadruple form $\langle$subject,
relation, object, time interval$\rangle$, e.g. $\langle$Obama, presidentOf,
U.S., [2009, 2017]$\rangle$. A graph consisting of a set of such temporal
facts -quadruples- is referred to as a Temporal Knowledge Graph (TKG).

Figure 1. Text-Enhanced Temporal Knowledge Graph

Alike traditional KGs, temporal knowledge graphs suffer inherently from
incompleteness due to their dynamic nature. In particular, the temporal
information (validity time interval) is often missing after an automatic
knowledge graph construction. To this end, the temporal knowledge graph
completion (TKGC) task aims to predict a missing quadruple element, such as
time interval prediction $\langle$s, r, o, ?$\rangle$. The time interval
prediction task is useful for temporal question answering, automatic
construction, and verification of temporal knowledge graphs that have temporal
constraints (Weikum et al., 2021).

Textual descriptions of entities and relations can significantly enhance the
effectiveness of (temporal) knowledge graphs completion methods (Xie et al.,
2016) since they contain valuable information regarding semantic relationships
across entities. For instance, in a description of an entity there may be a
reference to some other entity, despite the absence of any type of
relationship (edge) in the knowledge graph among them. Unfortunately, most of
the existing works on temporal knowledge graph completion do not fully exploit
this additional information in downstream tasks. Furthermore, by considering
the semantics of the descriptions, one may gain insight into the validity time
of the facts. For instance, if an entity description contains elements from a
certain century or a period like Renaissance, facts involving that entity may
be valid for that period. Figure 1 illustrates a temporal knowledge graph with
entities that have textual descriptions associated with them. The fact that
Obama has been the 44th president, may increase the plausibility that his
presidency started in 2009.

The availability of textual descriptions in knowledge graphs provides an
excellent opportunity for exploiting the benefits that both knowledge graphs
and language models can offer. Recent works has shown that language models
store real-world knowledge in their parameters and can potentially be used as
knowledge graphs (Petroni et al., 2019; AlKhamissi et al., 2022), and that
textual information can improve link prediction for static knowledge graphs
(Li et al., 2021; Yao et al., 2019). Furthermore, it has been shown that
entity descriptions and pre-trained language models can model facts that
involve unseen entities (inductiveness) (Daza et al., 2021; Wang et al.,
2022). The ability to do inductive reasoning is crucial since most real-world
knowledge graphs are often continuously extended with new entities.
Unfortunately, most temporal knowledge graph completion mechanisms are
transductive, which means that they can only perform predictions on the
entities they have already seen during training, i.e., are part of their
training set.

We provide a novel method for temporal knowledge graph completion that
leverages the available textual and temporal information for time interval
prediction. This is achieved by encoding text and time separately and fusing
them to predict the plausibility score of a quadruple. As text encoder, we use
a pre-trained language model to get a contextualized triple embedding and to
generalize on unseen entities. We have implemented this idea in a framework
called TEMT (Text Encoder Meets Time)111The datasets and the source code are
available at https://github.com/duyguislakoglu/TEMT for time interval
prediction (Section 4). We enhance the two real-world temporal knowledge
graphs YAGO11k and Wikidata12k (Dasgupta et al., 2018) with textual names and
entity descriptions and generate inductive splits. Using these datasets, we
carry out experiments on transductive and inductive time interval prediction
tasks (Section 5). The results show that TEMT is competitive with state-of-
the-art approaches. In particular, the inductive time interval prediction
results show that TEMT is able to reason on unseen entities (even when both
the subject and object entities of a quadruple are unseen in training).

Figure 2. TEMT Framework

##  2\. Problem Statement

A temporal knowledge graph (TKG) is a directed graph
$\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T},\\\ \mathcal{Q})$ where
$\mathcal{E},\mathcal{R},\mathcal{T}$ are sets of entities, relations, time
points and $\mathcal{Q}$ represents the set of quadruples (or temporal facts)
in the format $\langle$subject $s$, relation $r$, object $o$, time interval
$t_{I}$$\rangle$ where $s,o\in\mathcal{E}$, $r\in\mathcal{R}$,
$t_{I}=[t_{start},t_{end}]$ and $t_{start}$, $t_{end}\in\mathcal{T}$. Note
that $t_{I}$ can also be a single time point if $t_{start}$=$t_{end}$.

Temporal knowledge graphs can be grouped into two types: event TKGs and
interval-based TKGs. The former refers to TKGs in which $t_{start}=t_{end}$
for every time interval of every quadruple, i.e., each triple $\langle$s, r,
o$\rangle$ in the graph is valid at a single time point. The format of time
points depends on the chosen time granularity, such as years, months, or days.
On the other hand, interval-based TKGs, which are the focus of this paper,
represent TKGs where each quadruple has a validity time interval
$t_{I}=[t_{start},t_{end}]$. An interval is called left-open if $t_{start}$ is
unknown, right-open if $t_{end}$ is unknown, and closed interval if both the
start and end points are known.

Text-enhanced temporal knowledge graphs are TKGs where each entity and
relation is associated with a name and each entity has some natural language
text that describes its meaning. This additional information provides a
context and attaches a semantic meaning to the facts, which can be informative
for predicting the validity time interval of the fact. An example of a text-
enhanced temporal knowledge graph is given in Figure 1. More formally, a text-
enhanced temporal knowledge graph is a directed graph
$\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{T},\mathcal{Q},\mathcal{N},\mathcal{D})$
where $\mathcal{E},\mathcal{R},\mathcal{T}$ are sets of entities, relations,
time points and $\mathcal{Q}$ represents the set of quadruples, $\mathcal{N}$
denotes the set of entity and relation names, and $\mathcal{D}$ denotes the
set of entity descriptions. We can split $\mathcal{Q}$ into three disjoint
sets as train, validation, and test sets. Formally,
$\mathcal{Q}=\mathcal{Q}_{train}\cup\mathcal{Q}_{val}\cup\mathcal{Q}_{test}$
where $\mathcal{Q}_{train}$ represents the set of train quadruples,
$\mathcal{Q}_{val}$ represents the set of validation quadruples and
$\mathcal{Q}_{test}$ represents the set of test quadruples. Similarly, we can
specify the set of entities as $\mathcal{E}_{train}$, $\mathcal{E}_{val}$ and
$\mathcal{E}_{test}$.

Time interval prediction is the task of predicting the validity time interval
of a triple. More formally, given a quadruple $\langle$s, r, o, ?$\rangle$
with unknown validity time interval, the objective is to predict a time
interval $t_{I}$. We can reformulate the question as follows: given training
and validation sets, $\mathcal{Q}_{train}$ and $\mathcal{Q}_{val}$, the time
interval prediction is to output $t_{I}$ for each test quadruple $\langle$s,
r, o, ?$\rangle$ $\in$ $\mathcal{Q}_{test}$.

In this paper, we focus on two variants of this problem: transductive time
interval prediction and inductive time interval prediction. Transductive time
interval prediction aims to predict $t_{I}$ for each test quadruple in
$\mathcal{Q}_{test}$ that does not contain any new entities, i.e.,
$\mathcal{Q}_{test}=\\{\langle s,r,o,?\rangle|s,o\in\mathcal{E}_{train}\\}$.
In other words, all entities in the test set are included in the training set,
i.e., $\mathcal{E}_{test}\subseteq\mathcal{E}_{train}$. Furthermore, inductive
time interval prediction aims to predict the time interval of facts where the
test set contains previously unseen entities. So for each quadruple in the
test set, the subject or the object (or both) does not appear in
$\mathcal{E}_{train}$. Therefore, the test quadruples
$\mathcal{Q}_{test}=\\{\langle
s,r,o,?\rangle|s\not\in\mathcal{E}_{train}\\}\cup\\{\langle
s,r,o,?\rangle|o\not\in\mathcal{E}_{train}\\}$.

##  3\. Pre-trained language models

We exploit the representational power of pre-trained language models to model
the semantics of facts and to deal with unseen entities. Language models
assign a probability to a word by taking into account the other words in a
sentence and can predict the next word given a sequence of words. This can be
done by learning a latent representation of words in a vector space. Moreover,
models such as bidirectional encoder representations from transformers (BERT)
(Devlin et al., 2019) do not only consider the previous words but also take
the subsequent words into account. BERT generates a contextual word embedding
where the representation of a word depends on the whole context.

A pre-trained language model (PLMs) is a language model that is trained on a
large text corpora including books, encyclopedias, and web data. PLMs can be
used for many downstream tasks such as question-answering and text
summarization. A pre-trained model, such as pre-trained BERT, can be further
fine-tuned for a specific task or can be used for feature extraction of a
sentence. However, since BERT is designed for word-level tasks and not
optimized for sentence-level tasks, it performs poorly in semantic textual
similarity tasks (Reimers and Gurevych, 2019). On the other hand, Sentence-
BERT (Reimers and Gurevych, 2019), a language model built on top of BERT, is
explicitly trained to generate sentence embeddings where semantically similar
sentences are closer in the embedding space. In the next section, we explain
how Sentence-BERT can be used to generate an embedding for a triple.

##  4\. The Framework

We materialize the idea of using pre-trained language models for temporal
knowledge graph completion into a framework called TEMT (Text Encoder Meets
Time). The framework that gives a plausibility score to a quadruple
$\langle$s, r, o, t$\rangle$ where t is a single time point. It models a
quadruple’s textual and temporal information independently via text and time
encoders, fuses them, and gets a plausibility score for time interval
prediction.

Figure 2 gives an overview of the TEMT framework. Note that TEMT is different
from embedding-based methods and it employs feature extraction. The text
encoder takes textual information of the triple and outputs the triple
embedding $e_{sro}$. The time encoder takes temporal information and outputs
the time point embedding $e_{t}$. These two representations are fused to
output a validity score.

###  4.1. Embedding Triples with a Text Encoder

The text encoder packs the names and descriptions of triple elements as a
single sentence and returns a vector. As our text encoder, we leverage a pre-
trained language model to benefit from its representation power. Our text
encoder is a pre-trained Sentence-BERT (Reimers and Gurevych, 2019)
model222The name of the model used is all-mpnet-base-v2.. Inspired by (Yao et
al., 2019), we form a single textual sentence $S_{sro}$ for a triple to feed
Sentence-BERT.

(1) $\displaystyle
S_{sro}=\mathcal{N}_{s}+\mathcal{N}_{r}+\mathcal{N}_{o}+(\mathcal{D}_{s}+\mathcal{D}_{o}),$

where $S_{sro}$ is a string concatenation of the names and descriptions of the
entities and relations, $\mathcal{N}$ refers to names and $\mathcal{D}$ refers
to entity descriptions. The text encoder then outputs
$e_{sro}\in\mathbb{R}^{\textit{d}}$ which we call triple embedding:

(2) $\displaystyle e_{sro}=TextEncoder(S_{sro})$

Our main motivation to leverage a language model as a text encoder is two-
fold. Firstly, the language model captures the interactions between the
subject, relation, and the object and outputs a semantically rich
contextualized embedding of the fact. Secondly, language models can model
unobserved entities and therefore support inductive reasoning.

###  4.2. Embedding Time Points with a Time Encoder

By the independent nature of time, we claim that the representation of time
information should be independent of the fact. Many previous works (Jain et
al., 2020; Leblay and Chekol, 2018) learn the time vectors within the same
space as entities and relations and use a scoring function that performs on
this vector space. However, this may not allow us to capture the possible
interactions between time points, for instance, consecutive years may not be
modeled correctly. Hence, in this work, following previous studies (Mavromatis
et al., 2021; Jia et al., 2021; Zhang et al., 2020), we use positional
encoding (Vaswani et al., 2017) to produce vector representations of time
points. In other words, the positional encoding method embeds time points into
a vector space. As such, our time encoder takes a time point and returns a
vector. Given some time point $t$ and a reference time point $t_{min}$, the
$j$-th component of a time point embedding for t is defined as follows:

(3) $\displaystyle
TimeEncoder(\textit{t},t_{min})[j]=\begin{cases}\sin\left(\frac{t-t_{min}}{10000^{i/d^{\prime}}}\right)&\text{if}\
j=2i\\\ \cos\left(\frac{t-t_{min}}{10000^{i/d^{\prime}}}\right)&\text{if}\
j=2i+1\end{cases}$

where the term $t-t_{min}$ refers to the position of $t$ relative to the
earliest time point $t_{min}$ in $\mathcal{T}$ and $d^{\prime}$ is the
dimension of the time point embedding. Intuitively, the time point embedding
can be thought of as a position in time. The time encoder requires a first
time point $t_{min}$ as a reference point, then the other time points will be
positioned relative to this reference point. For the sake of brevity, we omit
$t_{min}$ from the time encoder function and simply write as $TimeEncoder(t)$.
The time encoder outputs $e_{t}\in\mathbb{R}^{\textit{d'}}$ which we call time
point embedding.

(4) $e_{t}=TimeEncoder(\textit{t})$

We emphasize the two properties of positional encodings: each time point
corresponds to a unique vector and the vectors of close time points are closer
in the vector space. This enables us to model the dependencies across
different time points and the notion of ordering. Moreover, in contrast to
previous work, the time encoder can represent unobserved time points. Although
we do not focus on temporal inductiveness in this paper, the time encoder can
potentially be used for performing predictions on future or unseen time
points.

###  4.3. Fusing and Training

####  4.3.1. Fusing Triple and Time Point Embedding

In the previous sections, we introduced two functions, namely $TextEncoder$
and $TimeEncoder$, that allow us to produce embeddings of triples and time
points respectively. We are now ready to discuss how these embeddings, from
different spaces, can be combined (or fused) together. Similar to (Ostendorff
et al., 2019; Gu and Budhkar, 2021), by treating the textual and temporal
features as different modalities, TEMT combines triple and time embeddings
using a multi-layer perceptron (MLP). The fusion of these two embeddings
produces a time-aware representation of a quadruple. Formally, given a
quadruple $q$, the time-aware representation $e_{q}$ is obtained as follows:

(5) $\displaystyle e_{q}=(W_{1}v_{concat}+b_{1})\in\mathbb{R}^{{k}}$
$\displaystyle v_{concat}=[e_{sro};e_{t}]\in\mathbb{R}^{d+d^{\prime}}$

where [ ; ] denotes concatenation operation,
$W_{1}\in\mathbb{R}^{{kx(d+d^{\prime})}}$ and $b_{1}\in\mathbb{R}^{{k}}$
denote the learnable parameters and k is a new dimension and
$k<(d+d^{\prime})$.

The alternative option to fusing would be adding the time point to the triple
sentence $S_{sro}$ in Equation (1) and feeding the language model with this
sentence. However, it is shown that pre-trained language models are not good
at number representations (Rogers et al., 2020). Our preliminary analysis also
demonstrated that language models are not good at temporal reasoning such as
ordering events and interval arithmetic. In addition, they are not robust to
small perturbations in time information.

####  4.3.2. Quadruple Scoring Function

Although most methods use a fixed distance function for scoring triples or
quadruples, there are some methods such as ConvE (Dettmers et al., 2018) and
ConvKB (Nguyen et al., 2018) that learn the parameters for a scoring function.
Similarly, we employ a parametric scoring function to output a plausibility
score for a quadruple of a given TKG:

(6) $f(s,r,o,t)=W_{2}e_{q}+b_{2}$

where $W_{2}\in\mathbb{R}^{\textit{1 x k}}$ and $b_{2}\in\mathbb{R}$ are
learnable parameters of the final layer of the neural network. Before feeding
the input to this final layer, we use ReLU (Agarap, 2019) as an activation
function.

####  4.3.3. Negative Sampling

The model learns by distinguishing valid quadruples from incorrect quadruples.
To this end, TEMT employs two different types of negative sampling. The first
type is called entity-corrupted negative sampling. In this approach, the set
of negative quadruples $D^{-}_{\langle s,r,o,t\rangle}$ is created by
corrupting the subject or the object of a given quadruple ${\langle
s,r,o,t\rangle}$ as shown below:

$\displaystyle D^{-}_{\langle s,r,o,t\rangle}=\\{\langle
s^{\prime},r,o,t\rangle\not\in D^{+}|s^{\prime}\in\mathcal{E}\\}\cup\\{\langle
s,r,o^{\prime},t\rangle\not\in D^{+}|o^{\prime}\in\mathcal{E}\\}.$

where $D^{+}=\mathcal{Q}_{train}$ denotes the set of positive quadruples.

The second one is called time-corrupted negative sampling (Cai et al., 2021).
In this approach, the set of negative quadruples $D^{-}_{\langle
s,r,o,t\rangle}$ is created by corrupting the time point of a given quadruple
${\langle s,r,o,t\rangle}$ as the following:

$D^{-}_{\langle s,r,o,t\rangle}=\\{\langle s,r,o,t^{\prime}\rangle\not\in
D^{+}|t^{\prime}\in\mathcal{T}\\}.$

The way of sampling time-corrupted negatives depends on the time category of
the positive quadruple: $t^{\prime}<t_{start}$ if right-open interval,
$t^{\prime}>t_{end}$ if left-open interval, and
$t^{\prime}\notin[t_{start},t_{end}]$ if closed interval.

####  4.3.4. Training

Similar to (Bordes et al., 2013), we use the following margin-based ranking
loss for training:

(7) $\operatorname{\mathcal{L}}=\sum_{q_{p}\in D^{+}}\sum_{q_{n}\in
D^{-}_{q_{p}}}\max(0,f(q_{n})-f(q_{p})+\gamma)$

where $q_{p}$ is a positive quadruple, $q_{n}$ is a negative quadruple,
$\gamma$ is the margin value and f is the scoring function from Equation (6).
The model is trained to give higher scores to positive quadruples (with a
given margin $\gamma$) than negative quadruples.

##  5\. Experiments

###  5.1. The Datasets

We perform our experiments on two interval-based TKGs: YAGO11k and Wikidata12k
(Dasgupta et al., 2018). YAGO11k is created from YAGO3 knowledge graph
(Mahdisoltani et al., 2015) and Wikidata12k is a subgraph of a preprocessed
version of Wikidata (Leblay and Chekol, 2018). In both datasets, each fact has
a time interval attached to it and each entity has at least two edges.

Furthermore, ind-YAGO11k datasets and ind-Wikidata12k are inductive splits
that we generate from YAGO11k and Wikidata12k. The split process is discussed
in Section 5.1.2. The details of the four datasets are given in Table 1. We
enhance the datasets with the names and descriptions of entities and
relations. The next section provides the data pre-processing details.

Table 1. Dataset Statistics Dataset | Entity | Relation | Train | Valid | Test
---|---|---|---|---|---
YAGO11k | 10,623 | 10 | 16,408 | 2,050 | 2,051
Wikidata12k | 12,554 | 24 | 32,497 | 4,062 | 4,062
ind-YAGO11k | 10,623 | 10 | 12,330 | 3,726 | 4,453
ind-Wikidata12k | 12,554 | 24 | 27,330 | 6,354 | 6,937

####  5.1.1. Dataset Pre-processing

For Wikidata12k, the entity names and descriptions are taken from their
corresponding Wikipedia pages. For YAGO11k, the entity and relation names are
already available in the dataset. Similar to Wikidata12k, we extract the
entity descriptions for YAGO11k from Wikipedia pages. For both datasets, the
entity descriptions are limited to one sentence.

We fix the time granularity as ”year” and drop the months and days similar to
(Jain et al., 2020; Cai et al., 2021). For each quadruple in the training set
that has closed-interval, i.e., $\langle$s, r, o, [$t_{start}$,
$t_{end}$]$\rangle$, we get two training data points $\langle$s, r, o,
$t_{start}$$\rangle$ and $\langle$s, r, o, $t_{end}$$\rangle$. An alternative
would be to get all intermediate time points between $t_{start}$ and
$t_{end}$. However, this approach would result in over-sampling for long
relations. Lastly, for the cases where either $t_{start}$ and $t_{end}$ is
unknown, we only consider the known time point.

####  5.1.2. Dataset Preparation for Inductive Reasoning

To test TEMT’s ability to generalize on unseen entities, we design new splits
based on YAGO11k and Wikidata12k and refer to them as ind-YAGO11k and ind-
Wikidata12k, respectively. For inductive reasoning, the validation and test
sets should have some entities that are not in the training set. We employ the
algorithm from (Daza et al., 2021) to create the new splits. The algorithm
samples an entity and removes this entity from the graph $\mathcal{G}$ if this
removal does not result in any isolated node or any relation type with less
than 100 edges in the graph. The removed entity and its edges are then added
either to the validation set and or to the test set. Thus, each triple in the
test set has either a new subject or a new object. The test set has 1062 and
1255 unseen entities for YAGO11k and Wikidata12k, respectively.

The algorithm works in triple level therefore assumes that the underlying
graph is static by ignoring the validity time intervals. Therefore, each split
has different triples, not quadruples. As a last step, we attach the
corresponding time information to each triple to convert it to a quadruple.

###  5.2. Inference and Evaluation Metrics

Since TEMT is designed to score quadruples with time points, not with time
intervals, we obtain a score for each time point (in our case for each year)
in the test set during the inference time. Then we need to aggregate the
scores for each time point to output a time interval. We turn these scores
into probabilities using the softmax function. Given a quadruple $\langle
s,r,o,t\rangle$, its probability is computed as:

$\displaystyle P(t|s,r,o)={\mathit{softmax}(f({\langle
s,r,o,t\rangle}))=\frac{\mathit{exp}(f({\langle
s,r,o,t\rangle})}{\sum_{t^{\prime}\in\mathcal{T}}\mathit{exp}(f({\langle
s,r,o,t^{\prime}\rangle}))}}$

Then we use greedy-coalescing algorithm (Cai et al., 2021) that takes the list
of probabilities for each year and outputs $k$ most possible time intervals.

Figure 3. Time Prediction Evaluation Terms

For time interval prediction, we use some interval metrics that compare the
predicted interval $I_{p}=[t_{start}^{p},t_{end}^{p}]$ and the ground-truth
interval $I_{g}=[t_{start}^{g},t_{end}^{g}]$. Ideally, $I_{p}$ is completely
the same as $I_{g}$ or they have some overlap. If there is no overlap, at
least $I_{p}$ and $I_{g}$ should be close to each other. We use the following
interval metrics that take these into account.

The first metric is called gIOU (generalized intersection over
union)(Rezatofighi et al., 2019) and is defined as follows:

(8) $\displaystyle
gIOU\left(I_{p},I_{g}\right)=IOU\left(I_{p},I_{g}\right)-\frac{|gap(I_{p},I_{g})|}{|hull(I_{p},I_{g})|}$

where

$IOU\left(I_{p},I_{g}\right)=\frac{|overlap(I_{p},I_{g})|}{|I_{p}|+|I_{g}|-|overlap(I_{p},I_{g})|}$

$gap(I_{p},I_{g})$ is the gap between $I_{p}$ and $I_{g}$ and the hull is the
shortest interval that covers both $I_{p}$ and $I_{g}$. More formally,
referring to
$I_{p}=[t_{start}^{p},t_{end}^{p}],I_{g}=[t_{start}^{g},t_{end}^{g}]$, these
functions can be defined as follows:

$\displaystyle gap([t_{start}^{p},t_{end}^{p}],[t_{start}^{g},t_{end}^{g}])$
$\displaystyle~{}=[t_{end}^{p},t_{start}^{g}],$ $\displaystyle
hull([t_{start}^{p},t_{end}^{p}],[t_{start}^{g},t_{end}^{g}])$
$\displaystyle~{}=[t_{start}^{p},t_{end}^{g}]\text{ and }$ $\displaystyle
overlap([t_{start}^{p},t_{end}^{p}],[t_{start}^{g},t_{end}^{g}])$
$\displaystyle~{}=[t_{start}^{g},t_{end}^{p}]\text{.}$

Similarly $gap(I_{g},I_{p})$, $overlap(I_{g},I_{p})$ and $hull(I_{g},I_{p})$
can be defined and the length of an interval is defined as
$|[t_{start},t_{end}]|=t_{end}-t_{start}+1$. As an example, Figure 3
illustrates the terms used in the metrics. We demonstrate two scenarios when
the predicted interval overlaps with the gold interval (top figure) and when
it does not (bottom figure). In the case of the former, given
$I_{p}=[2002,2006]$ and $I_{g}=[2004,2008]$, we get the following: the
$hull(I_{p},I_{g})=[2002,2008]$, and the $overlap(I_{p},I_{g})=[2004,2006]$.
In the latter case, given $I_{p}=[2001,2003]$ and $I_{g}=[2005,2008]$, then
the $hull(I_{p},I_{g})=[2001,2008]$ and $gap(I_{p},I_{g})=[2003,2005]$.

The second metric is aeIOU (Jain et al., 2020), affinity enhanced intersection
over union. It is defined as follows:

(9) $\displaystyle
aeIOU\left(I_{p},I_{g}\right)=\begin{cases}\frac{|overlap(I_{p},I_{g})|}{|hull(I_{p},I_{g})|}&|overlap(I_{p},I_{g})|>0,\\\
\frac{1}{|hull(I_{p},I_{g})|}&\text{otherwise.}\end{cases}$

The drawback of aeIOU that it outputs the same scores for both $I_{p}$ and
$I_{p^{*}}$ if hull($I_{p}$, $I_{g}$) = hull($I_{p^{*}}$, $I_{g}$), ignoring
the fact that one of them can be closer to $I_{g}$. In order to address this
drawback, the study in (Cai et al., 2021) introduces a new metric called
gaeIOU (generalized aeIOU).

(10) $\displaystyle
gaeIOU\left(I_{p},I_{g}\right)=\begin{cases}\frac{|overlap(I_{p},I_{g})|}{|hull(I_{p},I_{g})|}&|overlap(I_{p},I_{g})|>0,\\\
\
\frac{|gap(I_{p},I_{g})|^{-1}}{|hull(I_{p},I_{g})|}&\text{otherwise.}\end{cases}$

Using the three metrics, in Section 5, we report time interval prediction
results based on gIOU@k, aeIOU@k, and gaeIOU@k. For each metric, @k denotes
the best result out of k possible intervals that greedy-coalescing algorithm
produces.

###  5.3. Experimental Setup

The dimension $d$ for the triple embedding $e_{sro}$ is 768 and the dimension
$d^{\prime}$ for time point embedding is 64. We set $k$, in Equation (5), to
64. We use 128 time-corrupted negative samples, as discussed in Section 4.3.
For all experiments, we train our model with Adam optimizer (Kingma and Ba,
2015) for 50 epochs with a learning rate of 0.001 and margin value $\gamma=2$.
For time interval prediction, we set the threshold for greedy-coalescing to
0.65. We report the effect of hyperparameters in A.3.

####  5.3.1. Model Variants

We use two different variants of TEMT, namely, TEMTN and TEMTND. The variant
TEMTN is trained without the entity descriptions but only with the entity and
relation names. In order to reflect this change, we modify Equation (1) as
$S_{sro}=N_{s}+N_{r}+N_{o}$. On the other hand, the variant TEMTND is trained
with both entity descriptions and names. Regarding the sequence length for the
language model, we keep the default setting in Sentence-BERT which is 128
tokens.

####  5.3.2. Baselines

In order to compare TEMT variants against the state of the art, we identify 4
different TKGC methods: HyTE (Dasgupta et al., 2018), TNT-ComplEx (Lacroix et
al., 2020), TIMEPLEX-base (Jain et al., 2020) and TIME2BOX-TNS (Cai et al.,
2021). TIMEPLEX has two variants: TIMEPLEX-base and TIMEPLEX. Unlike the other
baselines, TIMEPLEX relies on temporal constraints to improve its performance.
However, TIMEPLEX-base does not follow the same. Here, we report the results
of the latter. All of the baselines are transductive and do not use pre-
trained language models for learning entity and relation embeddings. To the
best of our knowledge, TEMT is the only method that supports inductive
reasoning for the task of time interval prediction. Lastly, following our
baselines, we only report on the test instances that contain known time points
which is compatible with our evaluation metrics. This means that we do not
report results on quadruples, in the test set, that contain unknown start or
end time points.

Table 2. Transductive Time Interval Prediction Experiment Results on YAGO11k and Wikidata12k Datasets. Results marked (*) are taken from (Cai et al., 2021), results marked (†) are reproduced by us, and the others are taken from (Jain et al., 2020). ”-” denotes unavailable results. Methods | gIOU@1 | aeIOU@1 | gaeIOU@1 | gIOU@10 | aeIOU@10 | gaeIOU@10
---|---|---|---|---|---|---
|  |  | YAGO11k |  |  |
HyTE | 15.96 | 5.41 | - | - | - | -
TNT-ComplEx | 20.78 | 8.40 | - | - | - | -
TIMEPLEX-base† | 23.77 | 12.62 | 6.92 | 48.30 | 34.63 | 26.63
TEMTN | 39.85 | 13.05 | 10.05 | 58.78 | 32.89 | 29.25
TEMTND | 38.60 | 13.48 | 9.61 | 60.65 | 34.33 | 30.34
|  |  | Wikidata12k |  |  |
HyTE | 14.55 | 5.41 | - | - | - | -
TNT-ComplEx | 36.63 | 23.35 | - | - | - | -
TIMEPLEX-base† | 39.44 | 26.14 | 17.23 | 69.00 | 46.82 | 42.98
TIME2BOX-TNS* | 42.30 | 25.78 | 17.41 | 70.16 | 50.04 | 47.54
TEMTN | 39.35 | 12.90 | 8.81 | 61.68 | 34.97 | 30.71
TEMTND | 43.52 | 17.13 | 12.58 | 65.84 | 42.00 | 38.43
Table 3. Inductive Time Interval Prediction Experiment Results on ind-YAGO11k
and ind-Wikidata12k Datasets.

.  Methods gIOU@1 aeIOU@1 gaeIOU@1 gIOU@10 aeIOU@10 gaeIOU@10 ind-YAGO11k
TEMTN 39.07 14.23 10.32 61.53 35.90 32.79 TEMTND 37.20 14.81 10.15 60.07 36.73
33.32 ind-Wikidata12k TEMTN 39.78 12.94 9.18 60.88 34.92 31.07 TEMTND 38.43
16.43 11.01 64.50 40.06 36.63

###  5.4. Transductive Time Interval Prediction

In this experiment, the task is to predict the validity time intervals of
facts in TKGs, namely predicting $\langle$s, r, o, ?$\rangle$. We compare the
TEMT variants with the baselines and report the transductive time interval
prediction results for YAGO11k and Wikidata12k in Table 2. For Wikidata12k, we
observe that TEMT variants show improvements in the gIOU@1 metric in
comparison with the baselines. For aeIOU@k and gaeIOU@k, which are more
stringent metrics as discussed in 5.2, TEMT variants are outperformed by the
baselines.

Assume that two facts have the same subject, relation, object, and have very
close time points. Since their triple embeddings are the same vectors and
their time point embeddings are very close to each other, TEMT outputs very
similar scores and this may harm TEMT’s performance. However, TEMT is
competitive with the state-of-the-art on the metrics gIOU@10, aeIOU@10 and
gaeIOU@10. Note that the results of TIME2BOX-TNS are taken from the paper (Cai
et al., 2021). We could not reproduce the results for Wikidata12k and test the
method on YAGO11k as neither the source code nor the details for pre-
processing the datasets is available. In addition, TIME2BOX-TNS does not
provide results for the YAGO11k dataset.

On the YAGO11k dataset, TEMT outperforms the baselines in all the metrics but
aeIOU@10. Notably, in the gIOU@1 metric, TEMT achieves 16% percentage points
more than the next best competitor TIME2BOX-TNS.

Comparing the variants, we observe that TEMTND performs better than TEMTN in
most cases. This observation supports the claim that entity descriptions
improve the context and, therefore, help to create more meaningful semantic
triple embeddings. We also observe that TEMT variants are better at capturing
the start and the end years compared to intermediate years, which possibly
hurts the time interval prediction performance. The possible explanation is
that the text corpora that the language model is trained on generally contain
either the starting date or end date. In addition, the textual descriptions of
entities may contain temporally irrelevant descriptions. For instance, for
time point 2000, we may get an entity description from Wikipedia that is
updated in 2020.

Table 4. Triple Classification Results on Test Set. Dataset | Accuracy (%)
---|---
YAGO11k | 89.12
Wikidata12k | 91.55
ind-YAGO11k | 88.64
ind-Wikidata12k | 89.82
Table 5. Best gaeIOU@1 results with different negative sample types. Negative Sample Type | YAGO11k | Wikidata12k | ind-YAGO11k | ind-Wikidata12k
---|---|---|---|---
Entity-corrupted | 2.49 | 8.63 | 2.22 | 7.51
Time-corrupted | 9.77 | 12.58 | 12.19 | 11.21
Table 6. Example predictions from Yago11k and Wikidata12k datasets. The descriptions of entities are not displayed although utilized in the inference. Triple | Gold answer | 1st prediction | 2nd prediction | 3rd prediction
---|---|---|---|---
Kaká member of sports team Hertha BSC | [2008, 2012] | [2008, 2014] | [2011, 2012] | [2004, 2011]
Ippling located in the administrative territorial entity Bezirk Lothringen | [1871, 1920] | [1860, 1920] | [1871, 2018] | [1919, 1920]
Paulo Lopes (footballer) plays for S.L. Benfica | [1997, 2002] | [1997, 2004] | [1999, 2000] | [2000, 2008]
Jeff Morrow is married to Anna Karen Morrow | [1947, 1993] | [1956, 1992] | [1959, 1960] | [1960, 2013]
Henry Clay is affiliated to Whig Party (United States) | [1833, 1852] | [1830, 1862] | [1817, 1847] | [1818, 1829]

###  5.5. Inductive Time Interval Prediction

In this experiment, we perform inductive time interval prediction on newly
generated inductive datasets ind-YAGO11k and ind-Wikidata12k. Since all our
baselines support only transductive reasoning, they cannot be compared with
TEMT. Hence, we exclude them from this experiment.

The inductive time prediction results are reported in Table 3. The results
show that TEMT’s performance on inductive datasets is very close to the
transductive setting (Table 2). This shows the generalization power of TEMT on
unseen entities by the usage of pre-trained language models given the fact
that ind-YAGO11k and ind-Wikidata12k have 1062 and 1255 unseen entities in
test set, respectively. Another observation is that we do not see any
significant drop in performance although the models are trained on $\sim$
4,000 fewer training points than YAGO11k and $\sim$ 5,000 fewer training
points than Wikidata12k.

Moreover, similar to Section 5.4, TEMTND variant performs better in most
cases. This indicates that the context that entity descriptions provide helps
the model to capture the semantics of a triple better. Note that TEMT is also
applicable to a fully inductive setting where there is no overlap between
train and test set entities, which we leave as future work.

###  5.6. Fine-grained Analysis

####  5.6.1. Triple Classification

We investigate the representation power of triple embeddings by performing
triple classification experiment. The motivation is to make sure that our text
space is also meaningful like our time space. With this experiment, we predict
whether a triple is correct or not. To this end, we train an MLP classifier
(Pedregosa et al., 2011) with triple embeddings ($e_{sro}$). A.1 includes the
details of the datasets created and the training settings for this experiment.

We report the triple classification results in Table 4. The results illustrate
the effectiveness of the text encoder thus support the claim that the triple
embeddings are semantically meaningful and potentially capture the structural
information. Moreover, it also indicates that TEMT can handle atemporal
statements, which are common in real-world knowledge graphs.

####  5.6.2. The Effect of Negative Sampling

In Table 5, we compare the time prediction performance of TEMTND variant on
two negative sampling approaches discussed in Section 4.3. The results show
that time-corrupted negative sampling strategy is more suitable for our
problem. A further analysis on the effect of the number of negative samples
can be found in Appendix A.2.

####  5.6.3. Time Prediction Diagnosis

Table 6 illustrates some examples for time interval prediction experiment on
both YAGO11k and Wikidata12k datasets. “Triple” column represents some triples
from the test set and the “Gold answer” column represents their correct
validity time interval. The table covers the triples that occurred in
different centuries and that have varying durations. The next columns report
the TEMTND predictions for the corresponding triple.

We showcase that TEMTND is able to output the intervals that are close to
ground-truth intervals. For instance, in the first row, TEMT successfully
predicts the starting point but output a longer interval than the ground-
truth. In the second row, the ending time point is predicted correctly with an
earlier starting point from the gold answer. Another observation is that the
predictions are mostly a subset of the gold interval so it shows that the
textual information helps to predict the time period of facts.

##  6\. Related Work

###  6.1. Knowledge Graph Completion

There have been numerous studies on static knowledge graph completion methods
(Ji et al., 2022). These methods can be roughly divided into two: knowledge
graph embedding (KGE) methods and text-based methods. Knowledge graph
embedding methods represent entities and relations with low-dimensional
vectors. They can be broadly classified into three different types:
translational (Bordes et al., 2013), semantic matching (Yang et al., 2015),
and deep learning (Dettmers et al., 2018) methods. A common approach for KGE
methods is to learn a function to score the plausibility of a triple. These
methods perform well on many downstream tasks such as link prediction.
However, they only utilize the structure of a graph and cannot easily be
adapted to use additional information such as the textual descriptions of
entities and relations. Text-based methods utilize textual information in
knowledge graphs to infer missing links and we discuss them in Section 6.3.

###  6.2. Temporal Knowledge Graph Completion

Although the majority of prior research has focused on static KGs, there has
been a growing interest in exploring evolving knowledge graphs (Cai et al.,
2022). In this section, we discuss interval-based TKG completion methods. A
common approach for these methods is to incorporate time into the scoring
functions of static KGE methods. For instance, HyTE (Dasgupta et al., 2018)
learns to assign a hyperplane for each time point, which can be interpreted as
a static snapshot of the TKG. It learns the temporal embeddings of entities
and relations for each hyperplane by applying a translational scoring function
from TransE (Bordes et al., 2013). Since the hyperplanes for the time points
are learned independently, HyTE is not able to model the dependencies between
them. Moreover, both TNT-ComplEx (Lacroix et al., 2020) and TIMEPLEX (Jain et
al., 2020) are based on ComplEx (Trouillon et al., 2016) and learn complex-
valued embeddings for entity, relation and time instants. TNT-ComplEx extends
ComplEx by adding a new factor and solve a tensor completion problem. On the
other hand, TIMEPLEX adds multiple time-dependent components to the scoring
function and also takes into account additional learned features such as
temporal constraints. TIME2BOX (Cai et al., 2021) extends the idea of box
embeddings (Ren et al., 2020) by introducing time-aware boxes and allows both
atemporal and temporal facts. Unlike TEMT, these models do not benefit from
external information such as textual descriptions of entity and relations.
Furthermore, these models are transductive so they cannot predict on unseen
entities.

###  6.3. Text-enhanced (Temporal) Knowledge Graph Completion

In this section, we discuss text-based methods introduced in 6.1. Text-based
methods incorporates the names and the descriptions of entities and relations
(namely text-enhanced knowledge graphs). Some recent works on text-enhanced
static knowledge graphs employ pre-trained language models for static KGC (Yao
et al., 2019; Daza et al., 2021; Li et al., 2021; Wang et al., 2022; Alam et
al., 2022). The textual descriptions of entities and relations are fed into
language models, that store real-world knowledge in their parameters, to
obtain a rich contextual representation of the entities (or relations).
However, these text-based methods do not model the dynamics in which the
relations between entities hold in a time interval.

Only a few works focus on combining language models and temporal knowledge
graphs. As an example, ECOLA (Han et al., 2022) jointly optimizes an objective
function for language model and temporal knowledge graph embedding by
combining the loss functions. In contrast to TEMT, which extracts
entity/relation names and descriptions from Wikipedia pages, ECOLA retrieves
textual information from news articles that correspond to specific dates.
Additionally, ECOLA does not focus on time interval prediction. Moreover,
similar to TEMT, a recent method called SST-BERT (Chen et al., 2023) combines
the semantics of entities/relations and temporal aspects to output a
plausibility score. However, this model utilizes relation paths with a primary
focus on relation prediction whereas TEMT focuses on time prediction.

##  7\. Conclusion

In this work, we propose TEMT, a model for text-enhanced temporal knowledge
graph completion. TEMT captures semantic relationships and temporal
dependencies between facts. Our empirical evaluation in both transductive and
inductive time interval prediction tasks demonstrates the effectiveness of
TEMT. TEMT outperforms state-of-the-art methods on the YAGO11k dataset and
achieves competitive results on the Wikidata12k dataset. In particular, to the
best of our knowledge, TEMT is the first method that is capable of performing
inductive time interval prediction.

As a future work, we plan to investigate other pre-trained language models
(such as RoBERTa (Liu et al., 2019)), and time encoding methods. In addition,
we also plan to incorporate structural information into TEMT’s fusing
function.

## References

  * (1)
  * Agarap (2019) Abien Fred Agarap. 2019.  Deep Learning using Rectified Linear Units (ReLU).  arXiv:1803.08375 [cs.NE]
  * Alam et al. (2022) Mirza Mohtashim Alam, Md Rashad Al Hasan Rony, Mojtaba Nayyeri, Karishma Mohiuddin, M. S. T. Mahfuja Akter, Sahar Vahdati, and Jens Lehmann. 2022.  Language Model Guided Knowledge Graph Embeddings.  _IEEE Access_ 10 (2022), 76008–76020.  https://doi.org/10.1109/ACCESS.2022.3191666 Conference Name: IEEE Access.
  * AlKhamissi et al. (2022) Badr AlKhamissi, Millicent Li, Asli Celikyilmaz, Mona Diab, and Marjan Ghazvininejad. 2022.  A Review on Language Models as Knowledge Bases.  https://doi.org/10.48550/ARXIV.2204.06031
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating Embeddings for Modeling Multi-relational Data. In _Advances in Neural Information Processing Systems_ , C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (Eds.), Vol. 26. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2013/file/1cecc7a77928ca8133fa24680a88d2f9-Paper.pdf
  * Cai et al. (2022) Borui Cai, Yong Xiang, Longxiang Gao, He Zhang, Yunfeng Li, and Jianxin Li. 2022.  Temporal Knowledge Graph Completion: A Survey.  _CoRR_ abs/2201.08236 (2022).  arXiv:2201.08236 https://arxiv.org/abs/2201.08236
  * Cai et al. (2021) Ling Cai, Krzysztof Janowicz, Bo Yan, Rui Zhu, and Gengchen Mai. 2021.  Time in a Box: Advancing Knowledge Graph Completion with Temporal Scopes. In _Proceedings of the 11th on Knowledge Capture Conference_ (Virtual Event, USA) _(K-CAP ’21)_. Association for Computing Machinery, New York, NY, USA, 121–128.  https://doi.org/10.1145/3460210.3493566
  * Chen et al. (2023) Zhongwu Chen, Chengjin Xu, Fenglong Su, Zhen Huang, and Yong Dou. 2023.  Incorporating Structured Sentences with Time-enhanced BERT for Fully-inductive Temporal Relation Prediction.  arXiv:2304.04717 [cs.CL]
  * Dasgupta et al. (2018) Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha Talukdar. 2018.  HyTE: Hyperplane-based Temporally aware Knowledge Graph Embedding. In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, Brussels, Belgium, 2001–2011.  https://doi.org/10.18653/v1/D18-1225
  * Daza et al. (2021) Daniel Daza, Michael Cochez, and Paul Groth. 2021.  Inductive Entity Representations from Text via Link Prediction. In _Proceedings of the Web Conference 2021_. ACM, Ljubljana Slovenia, 798–808.  https://doi.org/10.1145/3442381.3450141
  * Dettmers et al. (2018) Tim Dettmers, Minervini Pasquale, Stenetorp Pontus, and Sebastian Riedel. 2018.  Convolutional 2D Knowledge Graph Embeddings. In _Proceedings of the 32th AAAI Conference on Artificial Intelligence_. 1811–1818.  https://arxiv.org/abs/1707.01476
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. 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)_. Association for Computational Linguistics, Minneapolis, Minnesota, 4171–4186.  https://doi.org/10.18653/v1/N19-1423
  * Gu and Budhkar (2021) Ken Gu and Akshay Budhkar. 2021.  A Package for Learning on Tabular and Text Data with Transformers. In _Proceedings of the Third Workshop on Multimodal Artificial Intelligence_. Association for Computational Linguistics, Mexico City, Mexico, 69–73.  https://doi.org/10.18653/v1/2021.maiworkshop-1.10
  * Han et al. (2022) Zhen Han, Ruotong Liao, Beiyan Liu, Yao Zhang, Zifeng Ding, Jindong Gu, Heinz Köppl, Hinrich Schütze, and Volker Tresp. 2022.  Enhanced Temporal Knowledge Embeddings with Contextualized Language Representations.  https://doi.org/10.48550/ARXIV.2203.09590
  * Jain et al. (2020) Prachi Jain, Sushant Rathi, Mausam, and Soumen Chakrabarti. 2020.  Temporal Knowledge Base Completion: New Algorithms and Evaluation Protocols. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. Association for Computational Linguistics, Online, 3733–3747.  https://doi.org/10.18653/v1/2020.emnlp-main.305
  * Ji et al. (2022) Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. 2022.  A Survey on Knowledge Graphs: Representation, Acquisition, and Applications.  _IEEE Transactions on Neural Networks and Learning Systems_ 33, 2 (feb 2022), 494–514.  https://doi.org/10.1109/tnnls.2021.3070843
  * Jia et al. (2021) Zhen Jia, Soumajit Pramanik, Rishiraj Saha Roy, and Gerhard Weikum. 2021.  Complex Temporal Question Answering on Knowledge Graphs. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_ (Virtual Event, Queensland, Australia) _(CIKM ’21)_. Association for Computing Machinery, New York, NY, USA, 792–802.  https://doi.org/10.1145/3459637.3482416
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Yoshua Bengio and Yann LeCun (Eds.).  http://arxiv.org/abs/1412.6980
  * Lacroix et al. (2020) Timothée Lacroix, Guillaume Obozinski, and Nicolas Usunier. 2020.  Tensor Decompositions for Temporal Knowledge Base Completion. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=rke2P1BFwS
  * 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_ (Lyon, France) _(WWW ’18)_. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1771–1776.  https://doi.org/10.1145/3184558.3191639
  * Li et al. (2021) Mengyao Li, Bo Wang, and Jing Jiang. 2021.  Siamese Pre-Trained Transformer Encoder for Knowledge Base Completion.  _Neural Processing Letters_ 53, 6 (Dec. 2021), 4143–4158.  https://doi.org/10.1007/s11063-021-10586-8
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  arXiv:1907.11692 [cs.CL]
  * Mahdisoltani et al. (2015) Farzaneh Mahdisoltani, Joanna Asia Biega, and Fabian M. Suchanek. 2015.  YAGO3: A Knowledge Base from Multilingual Wikipedias. In _CIDR_.
  * Mavromatis et al. (2021) Costas Mavromatis, Prasanna Lakkur Subramanyam, Vassilis N. Ioannidis, Soji Adeshina, Phillip R. Howard, Tetiana Grinberg, Nagib Hakim, and George Karypis. 2021.  TempoQR: Temporal Question Reasoning over Knowledge Graphs.  _CoRR_ abs/2112.05785 (2021).  arXiv:2112.05785 https://arxiv.org/abs/2112.05785
  * Nguyen et al. (2018) Dai Nguyen, Dat Quoc Nguyen, Tu Nguyen, and Dinh Phung. 2018.  A convolutional neural network-based model for knowledge base completion and its application to search personalization.  _Semantic Web_ 10 (08 2018), 1–14.  https://doi.org/10.3233/SW-180318
  * Ostendorff et al. (2019) Malte Ostendorff, Peter Bourgonje, Maria Berger, Julian Moreno-Schneider, Georg Rehm, and Bela Gipp. 2019.  Enriching BERT with Knowledge Graph Embeddings for Document Classification.  arXiv:1909.08402 [cs.CL]
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ 12 (2011), 2825–2830.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. 2019.  Language Models as Knowledge Bases?. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. Association for Computational Linguistics, Hong Kong, China, 2463–2473.  https://doi.org/10.18653/v1/D19-1250
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.  https://arxiv.org/abs/1908.10084
  * Ren et al. (2020) Hongyu Ren, Weihua Hu, and Jure Leskovec. 2020.  Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=BJgr4kSFDS
  * 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 _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. 658–666.  https://doi.org/10.1109/CVPR.2019.00075
  * Rogers et al. (2020) Anna Rogers, Olga Kovaleva, and Anna Rumshisky. 2020.  A Primer in BERTology: What we know about how BERT works.  _CoRR_ abs/2002.12327 (2020).  arXiv:2002.12327 https://arxiv.org/abs/2002.12327
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction. In _International conference on machine learning_. PMLR, 2071–2080.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is All you Need. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * Wang et al. (2022) Liang Wang, Wei Zhao, Zhuoyu Wei, and Jingming Liu. 2022.  SimKGC: Simple Contrastive Knowledge Graph Completion with Pre-trained Language Models. In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Association for Computational Linguistics, Dublin, Ireland, 4281–4294.  https://doi.org/10.18653/v1/2022.acl-long.295
  * Weikum et al. (2021) Gerhard Weikum, Xin Luna Dong, Simon Razniewski, Fabian Suchanek, et al. 2021\.  Machine knowledge: Creation and curation of comprehensive knowledge bases.  _Foundations and Trends® in Databases_ 10, 2-4 (2021), 108–490.
  * Xie et al. (2016) Ruobing Xie, Zhiyuan Liu, Jia Jia, Huanbo Luan, and Maosong Sun. 2016.  Representation Learning of Knowledge Graphs with Entity Descriptions.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 30, 1 (March 2016).  https://doi.org/10.1609/aaai.v30i1.10329 Number: 1.
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding Entities and Relations for Learning and Inference in Knowledge Bases. In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , Yoshua Bengio and Yann LeCun (Eds.).  http://arxiv.org/abs/1412.6575
  * Yao et al. (2019) Liang Yao, Chengsheng Mao, and Yuan Luo. 2019.  KG-BERT: BERT for knowledge graph completion.  _arXiv preprint arXiv:1909.03193_ (2019).
  * Zhang et al. (2020) Xuchao Zhang, Wei Cheng, Bo Zong, Yuncong Chen, Jianwu Xu, Ding Li, and Haifeng Chen. 2020.  Temporal Context-Aware Representation Learning for Question Routing. In _Proceedings of the 13th International Conference on Web Search and Data Mining_ (Houston, TX, USA) _(WSDM ’20)_. Association for Computing Machinery, New York, NY, USA, 753–761.  https://doi.org/10.1145/3336191.3371847

Table 7. Time prediction performance with respect to the number of negative samples. | gIOU@1 | aeIOU@1 | gaeIOU@1 | gIOU@10 | aeIOU@10 | gaeIOU@10
---|---|---|---|---|---|---
|  |  | YAGO11k |  |  |
# Entity-corrupted |  |  |  |  |  |
16 | 14.67 | 1.37 | 0.34 | 42.82 | 4.73 | 2
32 | 21.29 | 0.65 | 0.24 | 44.72 | 3.14 | 1.78
64 | 22.61 | 5.35 | 2.49 | 39.29 | 11.55 | 7.34
128 | 4.77 | 0.46 | 0.1 | 35.09 | 1.52 | 0.68
# Time-corrupted |  |  |  |  |  |
16 | 44.24 | 11.36 | 9.05 | 58.71 | 32.45 | 28.38
32 | 41.17 | 12.78 | 9.77 | 59.54 | 33.38 | 29.39
64 | 39.50 | 13.14 | 9.59 | 60 | 34.02 | 30.03
128 | 38.60 | 13.48 | 9.61 | 60.65 | 34.33 | 30.34
|  |  | ind-YAGO11k |  |  |
# Entity-corrupted |  |  |  |  |  |
16 | 26.96 | 4.8 | 2.22 | 40.52 | 10.81 | 6.69
32 | 32.75 | 1.96 | 1.08 | 47.55 | 6.99 | 4.73
64 | 11.99 | 1.29 | 0.33 | 33.01 | 2.11 | 1.11
128 | 3.28 | 0.22 | 0 | 20.72 | 0.39 | 0.06
# Time-corrupted |  |  |  |  |  |
16 | 47.47 | 14.39 | 12.19 | 61.64 | 36.23 | 33
32 | 41.89 | 15.31 | 11.51 | 62.08 | 37.50 | 34.17
64 | 41.79 | 14.12 | 10.71 | 63.70 | 37.61 | 34.6
128 | 37.20 | 14.81 | 10.15 | 60.07 | 36.73 | 33.32

##  Appendix A Appendix

###  A.1. Triple Classification Evaluation Setting

For the datasets, we convert the list of quadruples in the training and the
test sets into triples by removing time intervals. For each training triple,
we corrupt the head or tail randomly and create one negative example (that
does not belong to the training set) to avoid class imbalance. We remove the
test triples that exist in the training or validation set to prevent any
information leakage. For each test triple, we create one negative example that
does not appear in train, validation or test set. The sizes of the training
sets are 32,690 for YAGO11k, 64,980 for Wikidata12k, 24,558 for ind-YAGO11k
and 54,646 for ind-Wikidata12k. The sizes of the test sets are 4,100 for
YAGO11k, 5,530 for Wikidata12k, 8,880 for ind-YAGO11k and 13,872 for ind-
Wikidata12k. We create the sentences by following Equation (1) and extract the
features using our text encoder (namely Sentence-BERT). We set L2
regularization term alpha = 0.05 and perform maximum 1000 iterations. We keep
the default values of the MLP classifier in (Pedregosa et al., 2011) for the
other settings.

###  A.2. Effect of Number of Negative Samples

We conduct an empirical study to see how sampling types discussed in 4.3.3
affect the performance of TEMT. We analyze different number of entity-
corrupted and time-corrupted negative samples on YAGO11k and ind-YAGO11k
datasets. The results are reported in Table 7. We performed the same
experiments on Wikidata12k and ind-Wikidata12k as well, however, we do not
include their results here, for the sake of brevity.

The results in Table 7 show that the entity-corrupted negative sampling
performs worse than the time-corrupted negative sampling for both datasets.
Since the time interval prediction also requires the model to distinguish
facts with different time points, this difference is expected. Moreover, in
time-corrupted cases, the number of negative samples does not result in
marginal changes in gaeIOU@1 metric, which is the most stringent metric.

###  A.3. Ablation Study

We explore the effect of various hyperparameters on the performance of TEMT.
This also allows us to choose the optimal parameters that are discussed in
Section 5.3. To this end, we carry out a number of experiments. The results
are shown in Table 8. We report gaeIOU@1 results of different hyperparameters
on the validation set of Wikidata12k. Although we do not observe a significant
difference among the results, the setting where d’=64, learning rate=0.001,
margin=2, and threshold=0.65 gives the best results.

Table 8.  Results of hyperparameter analysis on the Wikidata12k dataset. $d^{\prime}$ | gaeIOU@1 | learning rate | gaeIOU@1
---|---|---|---
32 | 11.76 | 0.001 | 11.86
64 | 11.94 | 0.002 | 11.52
128 | 11.77 | 0.003 | 11.74
256 | 11.78 | 0.01 | 11.36
margin | gaeIOU@1 | threshold | gaeIOU@1
1 | 12.26 | 0.4 | 10.29
2 | 12.33 | 0.5 | 11.56
5 | 11.18 | 0.65 | 11.87
7 | 10.97 | 0.7 | 11.66


# Contractible complexes and non-positive immersions

William Fisher  Trinity College, Cambridge<EMAIL_ADDRESS>
(Date: October 2022)

###### Abstract.

We provide examples of contractible complexes which fail to have non-positive
immersions and weak non-positive immersions, answering a conjecture of Wise in
the negative.

##  1\. Introduction

In [7], Wise introduced the following property of 2-complexes.

######  Definition 1.1 (Non-positive immersions).

A map $Y\to X$ of CW-complexes is an _immersion_ if it is locally injective,
written $Y\looparrowright X$.

A 2-complex $X$ is said to have _non-positive immersions_ (NPI) if for every
immersion $Y\looparrowright X$ of a compact, connected 2-complex $Y$ into $X$,
we have either $\chi(Y)\leq 0$ or $\pi_{1}Y=1$.

One also may consider the stronger notion of _contracting_ NPI which says for
every immersion $Y\looparrowright X$ of a compact, connected 2-complex $Y$
either $\chi(Y)\leq 0$ or $Y$ is contractible. We will also say that $X$ has
_weak_ NPI (WNPI) if $\chi(Y)\leq 1$ for every compact, connected
$Y\looparrowright X$. Despite the terminology, one should note that the use of
“weak” here denotes only a weakening of the stronger contracting NPI property.
By Hurewicz, one in fact has that contracting NPI is equivalent to having NPI
and weak NPI.

The motivation for studying what classes of contractible complexes have NPI
and WPNI comes from a famous conjecture of Whitehead [6].

######  Conjecture 1.2 (Whitehead).

Every subcomplex of an aspherical 2-compex $X$ is aspherical.

In addressing this conjecture, it thus makes sense to look for properties of
complexes inherited by subcomplexes which imply asphericity. In particular,
the property of having WNPI implies the complex $X$ is aspherical [7, Theorem
3.4] and is inherited by subcomplexes. Passing to universal covers, one is
then lead to a conjecture of Wise [7].

######  Conjecture 1.3 (Wise).

Every contractible complex $X$ has (weak) non-positive immersions.

An affirmative answer to the WNPI variant of Conjecture 1.3 would imply
Conjecture 1.2. Indeed, assuming all contractible complexes to have WNPI, then
given an aspherical 2-complex $X$ with sub-complex $Y$, we can consider the
contractible universal cover $\hat{X}\to X$ of $X$. $Y$ is then covered by a
sub-complex $\hat{Y}\subseteq\hat{X}$. Since $\hat{X}$ has WNPI, it follows
that so does $\hat{Y}\looparrowright\hat{X}$. Thus $\hat{Y}$, and hence $Y$,
is aspherical.

Due to work of Howie, one can also deduce Conjecture 1.2 from the NPI variant
of Conjecture 1.3. By [7, Theorem 3.3], if $X$ has NPI, then $\pi_{1}X$ is
locally indicable. Since NPI is inherited by subcomplexes, Conjecture 1.3 in
the NPI form implies a positive answer to [2, Question 2], which implies
Conjecture 1.2.

The purpose of this note is to provide examples of contractible complexes
which fail to have WNPI and NPI, answering both forms of Conjecture 1.3 in the
negative.

After this work was completed, the author learned that Chemtov and Wise have
also constructed a family of counterexamples to Conjectures 1.3 using
different techniques [1].

### Acknowledgements

This research was supported by the Trinity College Summer Studentship Scheme.
The author is also grateful to Henry Wilton for many helpful comments and
discussions.

##  2\. Examples

The contractible complexes searched come from a family introduced by
Miller–Schupp [4]. They showed that balanced presentations of the form

(1) $\langle a,b\,|\,w,\,ba^{n}b^{-1}a^{-(n+1)}\rangle$

where $n\geq 1$ and $w$ is a word with exponent sum $1$ in $b$ represent the
trivial group, and hence have contractible presentation complexes.

To begin, we remark the following lemma.

######  Lemma 2.1.

Suppose $X$ is a 2-complex failing to have WNPI. Then there exits a 2-complex
$X^{\prime}$ homotopy equivalent to $X$ failing to have NPI.

###### Proof.

Suppose $Y\looparrowright X$ with $\chi(Y)\geq 2$. Then consider the natural
immersion $Y\vee S^{1}\looparrowright X\vee D^{2}$ given by sending $Y$ via
$Y\looparrowright X$ and $S^{1}$ to the boundary of $D^{2}$. Then letting
$X^{\prime}=X\vee D^{2}$ we have $X^{\prime}\simeq X$ and $\chi(Y\vee
S^{1})\geq 1$, yet $\pi_{1}(Y\vee S^{1})\neq 1$. ∎

Thus failure of the WNPI variant of Conjecture 1.3 implies failure of the NPI
variant as well. As such, the goal of this section will be to present
contractible complexes failing to have WNPI.

The case of $n=1$ and $w=ab^{2}ab^{-1}$ as in (1) fails to have WNPI as shown
by Figure 1. Figure 1 gives a combinatorial description of the immersion by
showing the commuting diagram of 1-skeleta and attaching maps of 2-cells
induced by the immersion $Y\looparrowright X$. Magenta is used to denote the
images of cells under the various maps, and Figure 2 shows the links of all
appearing vertices. Note that $Y\looparrowright X$ since the induced maps on
links are injective and in this example $\chi(Y)=2$. Section 3 gives a brief
description of how this example, and others in this section, were generated.

An exhaustive analysis of presentation complexes with $n=1$ and $w$ a word of
length $\leq 6$ was also conducted, and those $w$ proved to fail WNPI are
summarized in Table 1. One can show that having NPI and WNPI is invariant
under Nielsen equivalence of the attaching words of the 2-cells. In fact, NPI
and WNPI depend only on the isomorphism class of the group pair, which, up to
identifying all free groups of a given rank, corresponds to the
$\mathrm{Aut}(\pi_{1}X_{(1)})$-orbit of the set of conjugacy classes of
$\langle w_{1}\rangle,\dots,\langle w_{n}\rangle$ where $w_{1},\dots,w_{n}$
are the attaching words of the 2-cells of $X$. As such, only one
representative $w$ of each such orbit is shown in Table 1.

$w$ |  $ab^{2}ab^{-1}$, $a^{-1}b^{2}a^{-1}b^{-1}$, $a^{2}b^{-1}ab^{2}$, $ab^{-1}a^{-2}b^{2}$, $a^{2}b^{2}a^{-1}b^{-1}$
---|---
Table 1. $w$ for which presentation complex of (1) with $n=1$ is known to fail
WNPI.

We remark that the case of $w=b$ is still open. Testing however shows that
there exist immersions $Y\looparrowright X$ with $\chi(Y)=1$ and $Y$ having no
free faces, making the example resistant to current approaches for proving NPI
and WNPI.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$e_{4}$$e_{8}$$e_{7}$$e_{3}$$e_{1}$$e_{2}$$e_{5}$$e_{6}$$b^{-1}$$a$$a$$b$$a^{-1}$$a$$b$$b^{-1}$$v$$b$$a$$\alpha$$e_{6}$$e_{1}^{-1}$$e_{4}^{-1}$$e_{3}$$e_{2}$$\beta$$e_{2}^{-1}$$e_{5}$$e_{8}$$e_{4}$$e_{1}$$\alpha$$e_{4}^{-1}$$e_{8}$$e_{3}$$e_{5}$$e_{8}$$\alpha$$e_{5}^{-1}$$e_{2}$$e_{6}^{-1}$$e_{6}^{-1}$$e_{1}^{-1}$$\beta$$e_{3}^{-1}$$e_{7}$$e_{2}$$e_{6}^{-1}$$e_{2}^{-1}$$\alpha$$e_{3}^{-1}$$e_{7}$$e_{5}$$e_{4}^{-1}$$e_{7}$$\alpha$$b^{-1}$$a$$b$$b$$a$$\beta$$a^{-1}$$b$$a$$b^{-1}$$a^{-1}$

Figure 1. Failure of WNPI for the presentation complex of $\langle
a,b\,|\,ab^{2}ab^{-1},\,bab^{-1}a^{-2}\rangle$.

$e_{8}$$\bar{e_{4}}$$e_{1}$$\bar{e_{5}}$$\mathrm{Lk}(Y,v_{1})=$$e_{7}$$e_{3}$$\bar{e_{8}}$$e_{4}$$\mathrm{Lk}(Y,v_{2})=$$e_{2}$$e_{5}$$\bar{e_{7}}$$\bar{e_{3}}$$\mathrm{Lk}(Y,v_{3})=$$\bar{e_{1}}$$\bar{e_{6}}$$\bar{e_{2}}$$e_{6}$$\mathrm{Lk}(Y,v_{4})=$$a$$b$$\bar{a}$$\bar{b}$$\mathrm{Lk}(X,v)=$

Figure 2. Links of the vertices of complexes in the immersion
$Y\looparrowright X$ given by Figure 1.

##  3\. Generating immersions

The goal of this section is to give a brief summary of how the examples of
Section 2 were generated.

To start, an important tool for algorithmically generating immersions into a
complex is the notion of folding. For graphs, this notion was popularized by
Stallings’ [5] and takes a morphism $f:G\to H$ and factors it as

$G\to\bar{G}\looparrowright H$

where $G\to\bar{G}$ is surjective and $\pi_{1}$-surjective, and
$\bar{G}\looparrowright H$ is an immersion. Moreover, this factorization is
the most “general” possible factorization through an immersion.

This can be generalized to 2-complexes. Recall that a morphism of complexes in
this setting is assumed be _combinatorial_ , i.e. it sends $n$-cells
homeomorphically to $n$-cells. Given this, the appropriate generalization of
folding of graphs is given by [3, Lemma 4.1].

######  Lemma 3.1.

Any morphism of 2-complexes $\phi:A\to B$ with $A$ finite factors as

$A\to\bar{A}\looparrowright B$

where $A\to\bar{A}$ is surjective and $\pi_{1}$-surjective. Furthermore, if
$A\to B$ factors through an immersion $\psi:Z\looparrowright X$, then
$\bar{A}\looparrowright B$ factors uniquely through $\psi$.

Moreover, this factorization can be efficiently algorithmically computed. This
allows one to algorithmically produce immersions into a complex $X$ from
combinatorial maps $Y\to X$. The next ingredient then is to produce maps $Y\to
X$ whose folding produces complexes with large Euler characteristic. Given
that we can always remove _isolated edges_ , i.e. edges not adjacent to any
2-cell of $Y$, to increase the Euler characteristic, we introduce the
following definition.

######  Definition 3.2.

Given a 2-complex $X$, a _facial piece_ is an immersion $Y\looparrowright X$
where $Y$ is finite, connected and $Y$ has no isolated edges.

We now describe a method for generating a forest of facial pieces with non-
decreasing Euler characteristics. To describe the roots of this forest, we
need one more definition.

######  Definition 3.3.

Given a 2-complex $X$, a _characteristic map_ for the face $F$ of $X$, denoted
$D_{X}(F)$, is a morphism of 2-complexes $D\to X$ where $D$ is a disc and
$D\to X$ glues the interior of $D$ homeomorphically onto the interior of $F$.

We will occasionally abuse notation and write $D_{X}(F)\to X$ for this map,
viewing $D_{X}(F)$ as the disc $D$.

The forest $\mathcal{G}(X)$ of “primitive” facial pieces of $X$ is defined
inductively as follows:

  1. (1)

The root nodes of $\mathcal{G}(X)$ are given by the folded maps of the
characteristic maps $D_{X}(F)$ for each face $F$ of $X$ and orientation of
$D_{F}(X)$.

  2. (2)

Given a node $Y\looparrowright X\in\mathcal{G}(X)$, its children are
constructed as follows: For each face $F$ of $X$ and orientation, we have a
characteristic map $D_{X}(F)\to X$ and can consider the map

(2) $Y\amalg D_{X}(F)\to X.$

Now, consider all possible factorizations of (2) through a wedge

$Y\vee D_{X}(F)\to X$

at some vertex of $Y$ and $D_{X}(F)$. For each such map, consider the folded
representative $C\looparrowright X$. If $C$ still has one more face than $Y$,
we keep the map $C\looparrowright X$. If the isomorphism class of
$C\looparrowright X$ does not already occur in $\mathcal{G}(X)$, then
$C\looparrowright X$ becomes a child of $Y\looparrowright X$.

######  Remark 3.4.

Note that the order in which the faces and wedges are enumerated in step 2
changes the exact parent/child structure of $\mathcal{G}(X)$, since maps with
already occurring isomorphism class are discarded. However, the isomorphism
classes appearing in $\mathcal{G}(X)$ and their depth (see below) are
independent of this choice.

Traversing this forest gives a sequence of facial pieces of non-decreasing
Euler characteristic, as the next proposition shows. For $Y\looparrowright
X\in\mathcal{G}(X)$ we define $\operatorname{depth}(Y\looparrowright X)$ to be
the length of the shortest path between $Y\looparrowright X$ and a root node
of $\mathcal{G}(X)$.

######  Proposition 3.5.

For every $Y\looparrowright X\in\mathcal{G}(X)$, we have that

(3) $\operatorname{depth}(Y\looparrowright X)=\\#\\{\textnormal{2-cells of
}Y\\}-1$

and if $Z\looparrowright X\in\mathcal{G}(X)$ is a descendent of
$Y\looparrowright X$ with $\operatorname{depth}(Z\looparrowright
X)\leq\operatorname{depth}(Y\looparrowright X)$, then $\chi(Z)\leq\chi(Y)$.

###### Proof.

(3) is clear from construction of $\mathcal{G}(X)$ by induction. Indeed, if
$Y\looparrowright X$ is a child of $Y^{\prime}\looparrowright X$, then $Y$ is
the result of folding a complex with exactly one more face than $Y^{\prime}$,
yet by construction is assumed to still have one more face than $Y^{\prime}$.
Thus

$\\#\\{\textnormal{2-faces of }Y\\}=\\{\textnormal{2-faces of
}Y^{\prime}\\}+1$

as desired.

For the second claim, by induction, it suffices to assume that
$Y\looparrowright X$ is a child of $Z\looparrowright X$. In this case, we have
that $Y$ is a folding of $Z\vee D$ for some disc $D$. Since $Y_{(1)}$ is then
a folding of $(Z\vee D)_{(1)}$, we get that

$\operatorname{rk}\pi_{1}Y_{(1)}\leq\operatorname{rk}\pi_{1}(Z\vee
D)_{(1)}=1+\operatorname{rk}\pi_{1}Z_{(1)}.$

Hence

$\displaystyle\chi(Y)$
$\displaystyle=1-\operatorname{rk}\pi_{1}Y_{(1)}+\\#\\{\textnormal{2-faces of
}Y\\}$
$\displaystyle\geq-\operatorname{rk}\pi_{1}Z_{(1)}+1+\\#\\{\textnormal{2-faces
of }Z\\}$ $\displaystyle=\chi(Z)$

as required. ∎

Folding as in Lemma 3.1 and traversal of $\mathcal{G}(X)$ as above was
implemented111https://github.com/willfisher/npi-and-folding in Python and used
to find the examples of contractible complexes that fail variants of NPI.
Serialized versions of all examples referenced in this paper can be found at
this repository.

## References

  * [1] Max Chemtov and Daniel Wise.  Nonpositive towers in bing’s neighbourhood.  arXiv preprint arXiv:2210.01395, 2022.
  * [2] James Howie.  Aspherical and acyclic 2-complexes.  Journal of the London Mathematical Society, 2(3):549–558, 1979\.
  * [3] Larsen Louder and Henry Wilton.  One-relator groups with torsion are coherent.  Mathematical Research Letters, 27(5):1499–1511, 2020.
  * [4] CE Miller and Paul E Schupp.  Some presentations of the trivial group.  Contemporary Mathematics, 250:113–116, 1999.
  * [5] John R Stallings.  Topology of finite graphs.  Inventiones mathematicae, 71(3):551–565, 1983.
  * [6] John Henry Constantine Whitehead.  On adding relations to homotopy groups.  Annals of Mathematics, pages 409–428, 1941.
  * [7] Daniel T Wise.  Coherence, local indicability and nonpositive immersions.  Journal of the Institute of Mathematics of Jussieu, 21(2):659–674, 2022.