[table]capposition=top [figure]capposition=bottom

# TempoQR: Temporal Question Reasoning over Knowledge Graphs

Costas Mavromatis1, Prasanna Lakkur Subramanyam2, Vassilis N. Ioannidis3, Soji
Adeshina3, Phillip R. Howard4, Tetiana Grinberg4, Nagib Hakim4, George
Karypis3 Corresponding Author<EMAIL_ADDRESS>Work done while interning
at Amazon Web Services.Work done while interning at Intel.

###### Abstract

Knowledge Graph Question Answering (KGQA) involves retrieving facts from a
Knowledge Graph (KG) using natural language queries. A KG is a curated set of
facts consisting of entities linked by relations. Certain facts include also
temporal information forming a Temporal KG (TKG). Although many natural
questions involve explicit or implicit time constraints, question answering
(QA) over TKGs has been a relatively unexplored area. Existing solutions are
mainly designed for simple temporal questions that can be answered directly by
a single TKG fact. This paper puts forth a comprehensive embedding-based
framework for answering complex questions over TKGs. Our method, called
temporal question reasoning (TempoQR), exploits TKG embeddings to ground the
question to the specific entities and time scope it refers to. It does so by
augmenting the question embeddings with context, entity and time-aware
information via three specialized modules. The first computes a textual
representation of a given question, the second combines it with the entity
embeddings for entities involved in the question, and the third generates
question-specific time embeddings. Finally, a transformer-based encoder learns
to fuse the generated temporal information with the question representation,
which is used for answer predictions. Extensive experiments show that TempoQR
improves accuracy by 25–45 percentage points on complex temporal questions
over state-of-the-art approaches and it generalizes better to unseen question
types.

##  1 Introduction

A knowledge graph (KG) is a set of facts that are known to be true in the
world or in a specific domain. The facts are usually represented as tuples
(subject, relation, object), where the subject and object correspond to KG
entities. Certain KGs include additional attributes such as temporal
information forming a temporal knowledge graph (TKG). In TKGs, each fact is
associated with a timestamp or time interval, and is represented as (subject,
relation, object, timestamp) or (subject, relation, object, [start_time,
end_time]), respectively.

Knowledge Graph Question Answering (KGQA) attempts to answer a natural
question using the KG as a knowledge base (Lan et al. 2021). Natural questions
often include temporal constraints, e.g., “Which movie won the Best Picture in
1973?” and to aid temporal question answering, TKGs are utilized. The first
step is to identify and link the entities, relations and timestamps of the
questions to the corresponding ones in the TKG, e.g., “Which movie won the
Best Picture in 1973?” to (Best Picture, WonBy, ?, 1973). This problem is
known as entity linking (Kolitsas, Ganea, and Hofmann 2018).

Recently, (Saxena, Chakrabarti, and Talukdar 2021) proposed CronKGQA that
solves QA over TKGs by leveraging TKG embedding methods, e.g., TComplEx
(Lacroix, Obozinski, and Usunier 2020). TKG embedding methods learn low-
dimensional embeddings for the entities, relations and timestamps by
minimizing a link prediction objective attuned at completing facts of the form
(subject, relation, ?, timestamps) and (subject, relation, object, ?).
CronKGQA answers the mapped question (Best Picture, WonBy, ?, 1973) as a link
prediction task over the TKG. CronKGQA performs very well on simple questions
that are answerable by a single TKG fact (Hits@1 of 0.988). However, on more
complex questions, that involve additional temporal constraints and require
information from multiple TKG facts (e.g., “Which movie won the Best Picture
after The Godfather?”), CronKGQA performs poorly (Hits@1 of 0.392).

‘The Godfather’Best PictureMarlon Brando‘The Sting’‘Forrest Gump’Tom
Hanks‘Apocalypse Now’won,1972won,1994won,1973actor,1972actor,1979actor,1994

(a) The underlying TKG.

‘The Godfather’Best PictureMarlon Brando‘The Sting’‘Forrest Gump’Tom
Hanks‘Apocalypse Now’(0.2)(0.3)(0.25)(0.1)(0.15)

(b) Context-aware question representation.

‘The Godfather’Best PictureMarlon Brando (0.05)‘The Sting’‘Forrest Gump’Tom
Hanks (0.05)‘Apocalypse Now’(0.4)(0.4)(0.1)

(c) Entity-aware question representation.

‘The Godfather’Best PictureMarlon Brando (0.0)’The Sting’‘Forrest Gump’Tom
Hanks (0.0)‘Apocalypse Now’ (0.05)(0.2)(0.75)1972

(d) Time-aware question representation.

Figure 1: (a) The underlying TKG for the question “Which movie won the Best
Picture after The Godfather?”; Answer: ‘The Sting’. (b) The context-aware
question representation (dashed arrows) scores higher (numbers in parentheses)
movie entities. (c) The representation is grounded to the entity ‘Best
Picture’ and gives higher scores to movies that won the Best Picture. (d) The
representation is grounded to the correct time scope (after year 1972) and
gives higher scores to the movies that won the Best Picture after 1972, i.e.,
‘The Sting’.

To effectively handle both simple and complex temporal questions, we design a
new method called temporal question reasoning (TempoQR). TempoQR exploits TKG
embeddings to ground the question to the specific entities and time scope the
question refers to. To illustrate the key idea of our approach, consider the
question “Which movie won the Best Picture after The Godfather?” which
involves the TKG entities ‘Best Picture’ and ‘The Godfather’. The high-level
approach of TempoQR is shown in Figure 1. The first reasoning step is to
understand the context of the question (context-aware step). The context of
the question here involves a movie (“Which movie…”). The next step is to
ground the question to the entities it refers to (entity-aware step). The
question refers to a movie that has won the Best Picture. Finally, the
question needs to be grounded with certain temporal constraints (time-aware
step). The movie won the Best Picture after The Godfather, i.e., after 1972.

TempoQR performs the above reasoning steps using three specialized modules.
First, it uses the question’s text to generate a representation of the
question by employing a language model (LM). Next, it fuses the text-derived
representations with KG entity representations to ground the question to the
entities it refers to. Third, it extracts from the TKG question-specific
temporal information to enhance the question’s representation with two
complementary approaches. The first _retrieves_ the relevant information from
the underlying TKG based on the annotated entities of the question. The second
_infers_ temporal information by solving a link prediction problem obviating
the need to access the TKG. A dedicated information fusion layer combines the
context, entity and time-aware information together to a final question
representation. We empirically show that TempoQR is able to model temporal
constraints of the question and outperforms other time-unaware methods for
complex questions (25–45 percentage points improvement at Hits@1). Our
contributions are summarized below:

  * •

We solve complex temporal question answering by learning context, entity and
time-aware question representations.

  * •

We develop two different approaches to recover question-specific temporal
information.

  * •

We achieve state-of-the-art performance on temporal complex questions and
provide additional strong baselines.

##  2 Related Work

KGQA approaches typically leverage KG pre-trained embeddings (Bordes et al.
2013; Yang et al. 2014; Trouillon et al. 2017) to answer the questions
(Saxena, Tripathi, and Talukdar 2020). Such approaches perform well for simple
questions that can be easily mapped to incomplete facts in the KG but are
challenged by complex questions.

Addressing the limitations of the aforementioned approaches, (Miller et al.
2016; Xu et al. 2019; Zhou, Huang, and Zhu 2018; Qiu et al. 2020; He et al.
2021) enhance the question representation to address complex questions. Such
methods employ logical reasoning (Miller et al. 2016; Xu et al. 2019; Zhou,
Huang, and Zhu 2018; Qiu et al. 2020; He et al. 2021) or leverage available
side information in the form of text documents (Sun et al. 2018; Sun, Bedrax-
Weiss, and Cohen 2019; Xiong et al. 2019; Han, Cheng, and Wang 2020).
Nevertheless, these approaches are not suited for handling temporal
constraints.

TempQuestions (Jia et al. 2018a) was introduced to benchmark the reasoning
capabilities of existing with temporal constraints. Recently, additional
benchmarks have been developed (Jin et al. 2021; Souza Costa, Gottschalk, and
Demidova 2020; Chen, Wang, and Wang 2021; Neelam et al. 2021) that model
temporal information in various domains (including both KG and text data).
(Jia et al. 2018b) and (Jia et al. 2021) are methods that tackle the temporal
QA problem over KGs. However, they mostly employ hand crafted rules to handle
temporal information which is not flexible for incomplete KGs. By leveraging
TKG embeddings, CronKGQA (Saxena, Chakrabarti, and Talukdar 2021) provides a
learnable reasoning process for temporal KGQA, which does not rely on hand-
crafted rules. Although CronKGQA performs extremely well for answering simple
questions, it is challenged by complex questions that require inference of
certain temporal constraints. Our work is motivated by this limitation.

##  3 Background

A TKG $\mathcal{K}:=(\mathcal{E},\mathcal{R},\mathcal{T},\mathcal{F})$
contains a set of entities $\mathcal{E}$, a set of relations $\mathcal{R}$, a
set of timestamps $\mathcal{T}$, and a set of facts $\mathcal{F}$. Each fact
$(s,r,o,\tau)\in\mathcal{F}$ is a tuple where $s,o\in\mathcal{E}$ denote the
subject and object entities, respectively, $r\in\mathcal{R}$ denotes the
relation between them, and $\tau\in\mathcal{T}$ is the timestamp associated
with that relation.

###  3.1 TKG embeddings

Given a TKG $\mathcal{K}=(\mathcal{E},\mathcal{R},\mathcal{T},\mathcal{F})$,
TKG embedding methods typically learn $D$-dimensional vectors
$\mathbf{e}_{\epsilon},\mathbf{v}_{r},\mathbf{t}_{\tau}\in\mathbb{R}^{D}$ for
each $\epsilon\in\mathcal{E}$, $r\in\mathcal{R}$ and $\tau\in\mathcal{T}$.
These embedding vectors are learned such that each valid fact
$(s,r,o,\tau)\in\mathcal{F}$ is scored higher than an invalid fact
$(s^{\prime},r^{\prime},o^{\prime},\tau^{\prime})\notin\mathcal{F}$ through a
scoring function $\phi(\cdot)$, i.e.,
$\phi(\mathbf{e}_{s},\mathbf{v}_{r},\mathbf{e}_{o},\mathbf{t}_{\tau})>\phi(\mathbf{e}_{s^{\prime}},\mathbf{v}_{r^{\prime}},\mathbf{e}_{o^{\prime}},\mathbf{t}_{\tau^{\prime}})$.
Please see (Kazemi et al. 2020) for notable TKG embedding methods.

TComplEx. TComplEx (Lacroix, Obozinski, and Usunier 2020) is an extension of
the ComplEx (Trouillon et al. 2017) KG embedding method designed for TKGs.
TComplEx represents the embeddings as complex vectors in $\mathbb{C}^{D/2}$
and the scoring function $\phi(\cdot)$ is given by

$\displaystyle\begin{split}\phi(\mathbf{e}_{s},\mathbf{v}_{r},\bar{\mathbf{e}}_{o},\mathbf{t}_{\tau})=\text{Re}(\langle\mathbf{e}_{s},\mathbf{v}_{r}\odot\mathbf{t}_{\tau},\bar{\mathbf{e}}_{o}\rangle)\end{split}$
(1)

where $\text{Re}(\cdot)$ denotes the real part, $\bar{(\cdot)}$ is the complex
conjugate of the embedding vector and $\odot$ is the element-wise product.

TComplEx employs additional regularizers to improve the quality of the learned
embeddings such as enforcing close timestamps to have similar embeddings
(closeness of time). The embedding learning procedure makes TComplEx a
suitable method for inferring missing facts such as $(s,r,?,t)$ and
$(s,r,o,?)$ over an incomplete TKG. Throughout the manuscript, we generate TKG
embeddings via TComplEx due to its aforementioned benefits.

Type | Example Questions
---|---
Simple Time |  When did {Stoke$\\}_{s}$ have {Tom Holford$\\}_{o}$ in their team
Simple Entity |  Which movie won the {Best Picture$\\}_{s}$ in {1973$\\}_{\tau}$
Before/After |  Which movie won the {Best Picture$\\}_{s}$ after {The Godfather$\\}_{o}$
First/Last |  Name the award that {Sydney Chapman$\\}_{s}$ first received
Time Join |  Name a teammate of {Thierry Henry$\\}_{s}$ in {Arsenal$\\}_{o}$

Table 1: Different types of temporal questions.
$\\{\cdot\\}_{s},\\{\cdot\\}_{o},\\{\cdot\\}_{\tau}$ correspond to annotated
entities $s,o\in\mathcal{E}$ and timestamps $\tau\in\mathcal{T}$.

###  3.2 QA over TKGs

Given a TKG $\mathcal{K}=(\mathcal{E},\mathcal{R},\mathcal{T},\mathcal{F})$
and a natural language question $q$, the task of QA over a TKG (TKGQA)
(Saxena, Chakrabarti, and Talukdar 2021) is to extract an entity
$\epsilon^{\prime}\in\mathcal{E}$ or a timestamp $\tau^{\prime}\in\mathcal{T}$
that correctly answers the question $q$. The entities $\epsilon\in\mathcal{E}$
and timestamps $\tau\in\mathcal{T}$ of the question are annotated, i.e.,
linked to the TKG. Please refer to Table 1 for examples of such questions.

Note that a question, e.g., “Which movie won the Best Picture in 1973”, could
be answerable by a single TKG fact, i.e., (Best Picture, WonBy, The Sting,
1973). Thus, a common solution for TKGQA is to infer the relation ‘WonBy’ by
the question’s context and solve the problem as link prediction, i.e., (Best
Picture, $q$, ?, 1973).

CronKGQA. CronKGQA (Saxena, Chakrabarti, and Talukdar 2021) is a typical
method that solves TKGQA as a link prediction task. The idea is to use the
question as a ‘virtual relation’ in the scoring function $\phi(\cdot)$.

Suppose $s$ and $\tau$ are respectively the annotated subject and timestamp in
a given question (e.g., ‘Best Picture’ and ‘1973’) and $o^{\ast}$ is the
correct answer (e.g., ‘The Sting’). CronKGQA learns a question representation
$\mathbf{q}$ such that
$\phi(\mathbf{e}_{s},\mathbf{q},\mathbf{e}_{o^{\ast}},\mathbf{t}_{\tau})>\phi(\mathbf{e}_{s},\mathbf{q},\mathbf{e}_{o^{\prime}},\mathbf{t}_{\tau})$
for all incorrect entities $o^{\prime}\neq o^{\ast}$, where
$\mathbf{e}_{s},\mathbf{e}_{o^{\ast}},\mathbf{e}_{o^{\prime}},$ and
$\mathbf{t}_{\tau}$ are pre-trained TKG embeddings, e.g., with TComplEx. Note
that if either $s$ or $\tau$ is not present in the question, a random one from
the TKG (dummy) is used. The methodology is modified accordingly when the
answer is a timestamp $\tau^{\ast}$ by giving the maximum score to
$\phi(\mathbf{e}_{s},\mathbf{q},\mathbf{e}_{o},\mathbf{t}_{\tau^{\ast}})$,
where $\tau^{\ast}$ is the correct timestamp and $s,o$ are the annotated
subject and object.

CronKGQA is designed for simple temporal questions that can be transformed to
link predictions over TKGs. This limits the applicability of CronKGQA to more
complex questions that involve additional temporal constraints, e.g.,
‘Before/After’, ‘First/Last’ and ‘Time Join’ questions of Table 1. This is
confirmed by the experiments presented in (Saxena, Chakrabarti, and Talukdar
2021), where CronKGQA achieves a 65% performance improvement over non-TKG
embedding methods for simple questions, but only a 15% improvement for complex
questions as the ones here.

##  4 Method: TempoQR

TempoQR leverages pre-trained TKG embeddings of entities and timestamps that
encode their temporal properties, i.e., TComplEx. Although TKG embeddings are
designed for simple questions, our method overcomes this shortcoming by
incorporating additional temporal information in the question representation
$\mathbf{q}$ to better handle constraints. We design TempoQR by following the
human reasoning steps to answer temporal questions; see also Figure 1. In the
following subsections, we describe in detail the architecture of TempoQR.

###  4.1 Context-aware question representation.

Given a question’s text, we use pre-trained LMs, e.g., Bert (Devlin et al.
2019), to encode the question’s context into an embedding vector. The [CLS]
token is inserted into the question, e.g., “[CLS] Which movie won the Best
Picture after The Godfather?”, which is transformed to a tokenized vector
$\mathbf{q}_{0}$. Then, we compute a representation for each token as

$\mathbf{Q}_{B}=\mathbf{W}_{B}\textsc{BERT}(\mathbf{q}_{0})\;,$ (2)

where
$\mathbf{Q}_{B}:=[\mathbf{q}_{B_{\text{CLS}}},\mathbf{q}_{B_{1}},\ldots,\mathbf{q}_{B_{N}}]$
is a $D\times N$ embedding matrix where $N$ is the number of tokens and $D$
are the dimensions of the TKG embeddings. $\mathbf{W}_{B}$ is a $D\times
D_{B}$ learnable projection matrix where $D_{B}$ is the output the dimension
of the LM ($D_{B}=768$ for BERT($\cdot$)).

###  4.2 Entity-aware question representation.

We utilize the TKG entity embeddings to ground the question to the specific
entities it involves. Inspired by other approaches (Zhang et al. 2019; Févry
et al. 2020) that compute entity-aware text representations, we replace the
token embeddings of the entities and timestamps of $\mathbf{Q}_{B}$ with their
pre-trained TKG embeddings. Specifically, the $i$th column of the entity-aware
token embedding matrix $\mathbf{Q}_{E}$ is computed as

$\mathbf{q}_{E_{i}}=\begin{cases}\mathbf{W}_{E}\mathbf{e}_{\epsilon},&\text{if
token $i$ is linked to an entity $\epsilon$,}\\\
\mathbf{W}_{E}\mathbf{t}_{\tau},&\text{if token $i$ is linked to a timestamp
$\tau$.}\\\ \mathbf{q}_{B_{i}},&\text{otherwise,}\\\ \end{cases}$ (3)

where $\mathbf{W}_{E}$ is a $D\times D$ learnable projection. As a result, the
token embedding matrix
$\mathbf{Q}_{E}:=[\mathbf{q}_{E_{\text{CLS}}},\mathbf{q}_{E_{1}},\ldots,\mathbf{q}_{E_{N}}]$
incorporates additional entity information from the TKG. This enriches the
question with entity information from the TKG.

###  4.3 Time-aware question representation.

A question may refer to a specific time scope which the answer needs to be
associated, e.g., “after The Godfather” refers to “after 1972”. We develop two
alternatives that recover such temporal information. The first approach
_retrieves_ the question-specific time scope from the TKG based on the
annotated entities. We call this approach _hard-supervised_ , since it
accesses available facts in the TKG. The second approach _infers_ question-
specific temporal information based on the question’s representation. We term
this approach _soft-supervised_ , since it may recover missing temporal facts
by operating in the embedding space.

Hard Supervision: Retrieval from the TKG facts. We utilize the annotated
entities of the question to retrieve the relative time scope from the
underlying TKG. For the example question “Which movie won the Best Picture
after The Godfather?”, the entities ‘Best Picture’ and ‘The Godfather’ appear
together in a TKG fact with timestamp 1972. Hence, the time embedding of 1972
can be utilized to further enhance the question representation.

First, we identify all facts that involve the annotated entities of the
question. These facts involve specific timestamps which we collect together
(retrieved timestamps). In some cases, we may retrieve multiple timestamps,
but we only keep the _start_ and _end_ timestamps after we sort them (since we
aim at recovering a question-specific time scope). We recover two temporal
embeddings $\mathbf{t}_{1}$ and $\mathbf{t}_{2}$ that correspond to the TKG
embedding for start and end timestamps, respectively. We term this method
TempoQR-Hard.

Soft Supervision: Inference in the TKG embedding space. Instead of retrieving
timestamps from the TKG, we may directly obtain time embeddings by utilizing
$\phi$ to infer missing temporal information. We generate a time-aware
question embedding $\mathbf{q}_{\text{time}}$ as

$\mathbf{q}_{\text{time}}=\mathbf{W}_{T}\mathbf{q}_{B_{\text{CLS}}},$ (4)

where $\mathbf{q}_{B_{\text{CLS}}}$ corresponds to the [CLS] token embedding
of $\mathbf{Q}_{B}$ and $\mathbf{W}_{T}$ is a $D\times D_{B}$ learnable
projection matrix. The time-aware $\mathbf{q}_{\text{time}}$ is used as a
‘virtual relation’ in the scoring function $\phi$. TComplEx assigns a score to
a timestamp $\tau$ that potentially completes a fact $(s,r,o,?)$ as

$\begin{split}\big{\langle}\text{Re}(\mathbf{e}_{s})\odot\text{Re}(\mathbf{u}_{ro})-\text{Im}(\mathbf{e}_{s})\odot\text{Im}(\mathbf{u}_{ro}),\text{Re}(\mathbf{t}_{\tau})\big{\rangle}&+\\\
\big{\langle}\text{Re}(\mathbf{e}_{s})\odot\text{Im}(\mathbf{u}_{ro})+\text{Im}(\mathbf{e}_{s})\odot\text{Re}(\mathbf{u}_{ro}),\text{Im}(\mathbf{t}_{\tau})\big{\rangle}&,\end{split}$
(5)

where $\mathbf{u}_{ro}=\mathbf{v}_{r}\odot\bar{\mathbf{e}}_{o}$. Thus, the
real Re($\cdot$) and imaginary Im($\cdot$) part of the time embedding
$\mathbf{t}_{\tau}$ can be approximated by

$\begin{split}\text{Re}(\mathbf{t}_{\tau})\approx\text{Re}(\mathbf{e}_{s})\odot\text{Re}(\mathbf{u}_{ro})-\text{Im}(\mathbf{e}_{s})\odot\text{Im}(\mathbf{u}_{ro}),&\\\
\text{Im}(\mathbf{t}_{\tau})\approx\text{Re}(\mathbf{e}_{s})\odot\text{Im}(\mathbf{u}_{ro})+\text{Im}(\mathbf{e}_{s})\odot\text{Re}(\mathbf{u}_{ro}).\end{split}$
(6)

We follow the same computations to infer the real and imaginary part of the
desired (soft-supervised) time embeddings. Here, we treat
$\mathbf{q}_{\text{time}}$ as a relation embedding $\mathbf{v}_{r}$ and the
annotated entities as subject $s$ and object $o$ interchangeably to generate
$\mathbf{t}_{1}$ and $\mathbf{t}_{2}$, respectively. If either $s$ or $o$ is
not present, we use dummy ones. We term this method TempoQR-Soft.

Note here that the difference of hard and soft supervision relies on the
available facts given during QA, i.e., access to the TKG. Moreover, soft-
supervision may generalize better since it infers the temporal information in
the embedding space. In Section (6), we demonstrate the benefits and
limitations of each approach.

Fusing temporal information. After obtaining time embeddings $\mathbf{t}_{1}$
and $\mathbf{t}_{2}$, we leverage them to enhance the question representation
with temporal information. Specifically, we compute the $i$th collumn of the
time-aware token embedding matrix $\mathbf{Q}_{T}$ as

$\mathbf{q}_{T_{i}}=\begin{cases}\mathbf{q}_{E_{i}},&\text{if token $i$ is not
an entity,}\\\ \mathbf{q}_{E_{i}}+\mathbf{t}_{1}+\mathbf{t}_{2},&\text{if
token $i$ is an entity.}\\\ \end{cases}$ (7)

with
$\mathbf{Q}_{T}:=[\mathbf{q}_{T_{\text{CLS}}},\mathbf{q}_{T_{1}},\ldots,\mathbf{q}_{T_{N}}]$.
Our intuition for summing the entity and time embeddings together follows the
motivation of how transformer-based LMs, e.g., BERT use positional embedding
for tokens (Vaswani et al. 2017). Here, time embeddings can be seen as entity
positions in the time dimension. $\mathbf{Q}_{T}$ contains text, entity and
time-aware information. Next, we propose an information fusion layer to
combine this information altogether into a single question representation
$\mathbf{q}$.

###  4.4 Answer Prediction

Following (Févry et al. 2020), we use an information fusion layer that
consists of a dedicated learnable encoder $f(\cdot)$ which consists of $l$
Transformer encoding layers (Vaswani et al. 2017). This encoder allows the
question’s tokens to attend to each other, which fuses context, entity and
time-aware information together. The final token embedding matrix $\mathbf{Q}$
is calculated as

$\mathbf{Q}=f(\mathbf{Q}_{T}),$ (8)

where the columns of the embedding matrix correspond to the initial tokens
$\mathbf{Q}:=[\mathbf{q}_{{\text{CLS}}},\mathbf{q}_{1},\ldots,\mathbf{q}_{N}]$.
As a final question representation, we use the embedding of the [CLS] token
$\mathbf{q}:=\mathbf{q}_{{\text{CLS}}}$.

The final score of an entity $\epsilon\in\mathcal{E}$ being the answer is
given by

$\displaystyle\begin{split}\max\;\big{(}&\phi(\mathbf{e}_{s},\mathbf{P}_{E}\mathbf{q},\mathbf{e}_{\epsilon},\mathbf{t}_{\tau}),\\\
&\phi(\mathbf{e}_{o},\mathbf{P}_{E}\mathbf{q},\mathbf{e}_{\epsilon},\mathbf{t}_{\tau})\big{)},\end{split}$
(9)

where $s,o$ and $\tau$ are the annotated subject, object and timestamp,
respectively, and $\mathbf{P}_{E}$ is a $D\times D$ learnable matrix specific
for entity predictions. Here, we treat the annotated subject and object
interchangeably, and the $\max(\cdot)$ function ensures that we ignore the
scores when $s$ or $o$ is a dummy entity.

In addition, the final score of an timestamp $\tau\in\mathcal{T}$ being the
answer is given by

$\phi(\mathbf{e}_{s},\mathbf{P}_{T}\mathbf{q},\mathbf{e}_{o},\mathbf{t}_{\tau}),$
(10)

where $s,o$ are annotated entities in the question and $\mathbf{P}_{T}$ is a
$D\times D$ learnable matrix specific for time predictions. During training,
the entity and time scores are concatenated and transformed to probabilities
by a softmax function. The model’s parameters are updated to assign higher
probabilities to the correct answers by minimizing a cross entropy loss.

Model | Hits@1 | Hits@10
---|---|---
Overall | Question Type | Answer Type | Overall | Question Type | Answer Type
Complex | Simple | Entity | Time | Complex | Simple | Entity | Time
BERT | 0.243 | 0.239 | 0.249 | 0.277 | 0.179 | 0.620 | 0.598 | 0.649 | 0.628 | 0.604
RoBERTa | 0.225 | 0.217 | 0.237 | 0.251 | 0.177 | 0.585 | 0.542 | 0.644 | 0.583 | 0.591
EmbedKGQA | 0.288 | 0.286 | 0.290 | 0.411 | 0.057 | 0.672 | 0.632 | 0.725 | 0.850 | 0.341
EaE | 0.288 | 0.257 | 0.329 | 0.318 | 0.231 | 0.678 | 0.623 | 0.753 | 0.688 | 0.698
CronKGQA | 0.647 | 0.392 | 0.987 | 0.699 | 0.549 | 0.884 | 0.802 | 0.992 | 0.898 | 0.857
EntityQR | 0.745 | 0.562 | 0.990 | 0.831 | 0.585 | 0.944 | 0.906 | 0.993 | 0.962 | 0.910
TempoQR-Soft | 0.799 | 0.655 | 0.990 | 0.876 | 0.653 | 0.957 | 0.930 | 0.993 | 0.972 | 0.929
TempoQR-Hard | 0.918 | 0.864 | 0.990 | 0.926 | 0.903 | 0.978 | 0.967 | 0.993 | 0.980 | 0.974

Table 2: Comparison against other methods.

##  5 Experimental Setting

Datasets. CronQuestions (Saxena, Chakrabarti, and Talukdar 2021) is a temporal
QA benchmark based on the Wikidata TKG proposed in (Lacroix, Obozinski, and
Usunier 2020). The WikiData TKG consists of 125k entities, 203 relations, 1.7k
timestamps (timestamps correspond to years), and 328k facts. In this TKG,
facts are represented as (subject, relation, object, [start_time, end_time]).
CronQuestions consists of 410k unique question-answer pairs, 350k of which are
for training and 30k for validation and for testing. Moreover, the entities
and times present in the questions are annotated. CronQuestions includes both
simple and complex temporal questions ( Table 1 for examples).

Incomplete WikiData TKG. To illustrate how methods perform under incomplete
TKGs, we provide a setting where the given WikiData TKG is corrupted at the
time dimension. Specifically, for a fact (subject, relation, object,
[start_time, end_time]) $\in\mathcal{F}$, we remove the associated timestamps
with probability $p$. If the timestamps are removed, the fact becomes
(subject, relation, object, no_time). Here, ‘no_time’ denotes that there is no
timestamp associated with (subject, relation, object) and we treat it as a
special timestamp.

We used the corrupted TKG to perform two experiments. In the first experiment,
we substitute the original TKG with the corrupted one during the QA task. This
affects only TempoQR-Hard since this is the only method that uses a TKG during
QA. The second configuration is to substitute the original TKG with the
corrupted one throughout the process. This means that TComplEx embeddings are
generated on a corrupted TKG and, thus, may not encode important temporal
information. All TKGQA embedding-based methods are affected by this
configuration.

Additional Complex Questions. Although CronQuestions includes different
question types, we manually create additional complex types. The idea is to
evaluate how different methods perform on complex questions that were unseen
during training but include the same keywords (and temporal constraints) with
the training questions. We create (i) ‘before & after’ questions that include
both ‘before’ and ‘after’ constraints and (ii) ‘before/after & first/last’
questions that include both ‘before/after’ and ‘first/last’ constraints. We
describe the details of generating these QA pairs in the Appendix.

###  5.1 Model Configuration

We learn TKG embeddings with the TComplEx method, where we set their
dimensions $D=512$. During, QA the pre-trained LM’s parameters and the TKG
embeddings are not updated. We set the number of transformer layers of the
encoder $f(\cdot)$ to $l=6$ with 8 heads per layer. We also observed the same
performance when setting $l=3$ with 4 heads per layer. The model’s parameters
are updated with Adam (Kingma and Ba 2014) with a learning rate of 0.0002. The
model is trained for 20 maximum epochs and the final parameters are determined
based on the best validation performance. The model is implemented with
Pytorch (Paszke et al. 2019). For reproducibility, our code is available at:
https://github.com/cmavro/TempoQR.

$0$$0.2$$0.4$$0.6$$0.8$$50$$60$$70$$80$$90$$100$Hits@1
(%)Before/After$0$$0.2$$0.4$$0.6$$0.8$$50$$60$$70$$80$$90$$100$First/Last$0$$0.2$$0.4$$0.6$$0.8$$50$$60$$70$$80$$90$$100$Time
JoinTempoQR-HardTempoQR-SoftEntityQRCronKGQA

(a) Corrupted TKG for QA only.

$0$$0.1$$0.2$$0.3$$0.4$$0.5$$20$$40$$60$$80$$100$Hits@1
(%)Before/After$0$$0.1$$0.2$$0.3$$0.4$$0.5$$20$$40$$60$$80$$100$First/Last$0$$0.1$$0.2$$0.3$$0.4$$0.5$$20$$40$$60$$80$$100$Time
Join$0$$0.1$$0.2$$0.3$$0.4$$0.5$$60$$70$$80$$90$$100$Simple Entity/Time

(b) Corrupted TKG for both Pre-training and QA.

Figure 2: Performance comparison when the underlying TKG is corrupted. x-axis
corresponds to the probability $p$ of a fact to be corrupted.

###  5.2 Baseline methods and TempoQR variations

Pre-trained LMs. BERT (Devlin et al. 2019) and RoBERTa (Liu et al. 2019) are
two well-established pre-trained LMs. To evaluate these models, we generate
their LM-based question embedding and concatenate it with the annotated entity
and time embeddings, followed by a learnable projection. The resulted
embedding is scored against all entities and timestamps via dot-product.

EaE and EntityQR. Entity as Experts (EaE) (Févry et al. 2020) is an entity-
aware method similar to TempoQR. The key differences are that EaE does not
utilize a TKG embedding-based scoring function for answer prediction and that
it does not fuse additional temporal information as in Section 4.3. As a
baseline, we experiment with EaE combined with TComplEx scoring function.
Since this baseline is similar to TempoQR without the steps of Section (4.3),
we call it EntityQR.

CronKGQA and EmbedKGQA. CronKGQA is the TKGQA embedding-based method described
in Section 3.2. EmbedKGQA (Saxena, Tripathi, and Talukdar 2020) is similar to
CronKGQA, but designed for regular KGs. In (Saxena, Chakrabarti, and Talukdar
2021), EmbedKGQA is implemented for TKGQA as follows. Timestamps are ignored
during pre-training and random time embeddings are used during the QA task.

CronKGQA and EntityQR with hard and soft supervision. CronKGQA and EntityQR
are extended to incorporate additional temporal information by the algorithmic
steps in Section 4.3, which generate time embeddings $\mathbf{t}_{1}$ and
$\mathbf{t}_{2}$ for TempoQR. Recall that TempoQR generates $\mathbf{t}_{1}$
and $\mathbf{t}_{2}$ by either accessing the TKG or by inferring them in the
embedding space. For CronKGQA and EntityQR, we generate $\mathbf{t}_{1}$ and
$\mathbf{t}_{2}$ in the same way, but we employ them directly to the TComplEx
scoring function as follows. We modify (9), which scores an entity to be the
answer, as

$\displaystyle\begin{split}\max\;\big{(}&\phi(\mathbf{e}_{s},\mathbf{P}_{E}\mathbf{q},\mathbf{e}_{\epsilon},\mathbf{t}_{1}+\mathbf{t}_{2}),\\\
&\phi(\mathbf{e}_{o},\mathbf{P}_{E}\mathbf{q},\mathbf{e}_{\epsilon},\mathbf{t}_{1}+\mathbf{t}_{2})\big{)},\end{split}$
(11)

to replace the embedding of a dummy timestamp $\mathbf{t}_{\tau}$ (if no time
is annotated in the question) with $\mathbf{t}_{1}+\mathbf{t}_{2}$. Based on
how $\mathbf{t}_{1}$ and $\mathbf{t}_{2}$ are generated (hard or soft
supervision), we term the methods CronKGQA-Hard and EntityQR-Hard or CronKGQA-
Soft and EntityQR-Soft, respectively.

##  6 Results

###  6.1 Main Results

Table 2 shows the results of our method compared to other baselines on
CronQuestions. First, by comparing EntityQR to CronKGQA, we see that grounding
the question to the entities it refers (entity-aware step) significantly helps
for answering complex questions. In this case, the absolute improvement for
complex questions is 17% and 10% at Hits@1 and Hits@10, respectively.
Furthermore, comparing TempoQR to EntityQR, we see the benefit of adding
temporal information to the question (time-aware step). The absolute
improvement of TempoQR-Soft over EntityQR is 9% at Hits@1 for complex
questions, while the respective improvement of TempoQR-Hard is more than 30%.
Moreover, TempoQR-Hard outperforms TempoQR-Soft by 25% at Hits@1 when the
answer is a time. This confirms that TempoQR-Hard provides accurate temporal
information by retrieving it from the TKG, while TempoQR-Soft sometimes cannot
infer as accurate information from the embedding space.

We also highlight that methods that score possible answers with the TComplEx
function (TempoQR, EntityQR and CronKGQA) answer 99% of the simple questions
correctly. The other methods (BERT, RoBERTa, EmbedKGQA and EaE) cannot answer
correctly more the 35% (Hits@1) and 76% (Hits@10). Similarly, BERT, RoBERTa,
EmbedKGQA and EaE have 35%-65% and 11%-40% worse overall accuracy for Hits@1
and Hits@10, respectively, compared to TempoQR, EntityQR and CronKGQA.

| Complex Questions | All
---|---|---
| Before/ | First/ | Time |
| After | Last | Join |
CronKGQA | 0.256 | 0.371 | 0.511 | 0.647
EntityQR | 0.540 | 0.493 | 0.833 | 0.745
CronKGQA-Soft | 0.341 | 0.375 | 0.671 | 0.672
EntityQR-Soft | 0.430 | 0.468 | 0.766 | 0.708
TempoQR-Soft | 0.670 | 0.570 | 0.894 | 0.799
CronKGQA-Hard | 0.379 | 0.445 | 0.942 | 0.728
EntityQR-Hard | 0.442 | 0.470 | 0.955 | 0.748
TempoQR-Hard | 0.714 | 0.853 | 0.978 | 0.918

Table 3: Hits@1 for different complex type questions.

$2$$4$$6$$8$$10$$0$$20$$40$$60$Hits@$k$ (%)Before &
After$2$$4$$6$$8$$10$$0$$20$$40$$60$Before/After & First/LastTempoQR-
HardTempoQR-SoftEntityQRCronKGQA

Figure 3: Evaluation for unseen complex types during inference. x-axis
corresponds to $k$ of Hits@$k$.

###  6.2 Ablation Study

Table 3 shows how soft and hard supervision affect the performance of various
methods for different question types. First, we see that both supervision
approaches have a positive effect on CronKGQA, where the performance is
improved by 2.5% and 6% over the original method (CronKGQA-Soft and CronKGQA-
Hard, respectively, compared to CronKGQA). The same does not happen for
EntityQR, where its performance drops (EntityQR-Soft and EntityQR-Hard
compared to EntityQR). This is an effect of over-using TKG embeddings, since
EntityQR-Soft and EntityQR-Hard use this information multiple times for answer
prediction.

Moreover, TempoQR-Hard performs much better for ‘first/last’ questions
compared to soft-supervision (27% absolute improvement). Since TempoQR-Hard
always retrieves the start and end timestamps of the question entities, this
provides more accurate temporal information to “When was the first/last time…”
questions. On the other hand, this does not equally benefit ‘before/after’
questions; the improvement of hard-supervision over soft-supervision is only
3%. This indicates that both approaches handle such questions in a similar
manner. Finally, TempoQR-Soft performs 8% worse in ‘time join’ questions
compared to TempoQR-Hard. This indicates that might be some room for
improvement for inferring more accurate time embeddings with soft-supervision.

###  6.3 Robustness over Corrupted TKGs

Figure 2(a) shows the results when the given TKG is corrupted during the QA
phase. TempoQR-Hard is the only method that depends on the quality of the TKG
during QA and is greatly affected by a corrupted TKG. When a lot of facts are
corrupted ($p=0.8$) it performs similar to EntityQR, which does not use any
additional temporal information. For ‘before/after’ questions, it performs
worse than TempoQR-Soft even when the facts are corrupted by a probability
$p=0.2$. Finally, TempoQR-Hard is more robust for ‘first/last’ and ‘time join’
questions, where it better handles the non-corrupted timestamps of the facts.

Figure 2(b) shows the results when a corrupted TKG is given for both TKG
embedding and QA. We can see that methods that rely on TKG embeddings
(TempoQR-Hard, TempoQR-Soft) are greatly affected, since they perform similar
to each other as well to EntityQR when the corruption probability $p$ is
large, e.g., $p=0.5$. CornKGQA is the least affected by a corrupted TKG, but,
still, its performance is much lower. The largest performance drop is observed
for TempoQR-Hard for ‘first/last’ questions, which indicates that it cannot
generalize well to such questions under a corrupted TKG. Finally, depending on
the information that is corrupted, some methods benefit over others, i.e.,
compare TempoQR-Hard to EntityQR for $p=0.33$ at ‘time join’ questions.

###  6.4 Unseen Question Types

Figure 3 shows the performance for unseen question types during training. As
we can see, TempoQR-Soft performs the best for both generated question types.
Since it learns to handle temporal constraints in the embedding space, it
generalizes better than TempoQR-Hard which simply uses the TKG to answer such
questions. In general, neither of these methods seems to be able to tackle
unseen questions effectively, i.e., Hits@1 is below 20% for all the methods.
This is also confirmed since the performance of the methods only increases
when $k$ is increased, i.e., the return more possible answers. This motivates
the need for extending these methods in a way that ensures better performance
for unseen questions.

##  7 Conclusion

This paper puts forth a comprehensive embedding framework specialized in
answering complex questions over TKGs. The benefit of TempoQR comes by
learning context, entity and time-aware question representations. The latter
relies either on hard or soft supervision. Extensive experiments confirmed the
benefits of each step performed in our method. TempoQR outperforms existing
methods for complex questions by 25–45%. The limitations and advantages of
hard and soft supervision are also showcased. Future research includes
extending existing methods to generalize better to unseen question types.

## References

  * Bordes et al. (2013) Bordes, A.; Usunier, N.; Garcia-Duran, A.; Weston, J.; and Yakhnenko, O. 2013.  Translating embeddings for modeling multi-relational data.  _Advances in neural information processing systems_ , 26.
  * Chen, Wang, and Wang (2021) Chen, W.; Wang, X.; and Wang, W. Y. 2021.  A Dataset for Answering Time-Sensitive Questions.  _arXiv preprint arXiv:2108.06314_.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _ACL_.
  * Févry et al. (2020) Févry, T.; Soares, L. B.; FitzGerald, N.; Choi, E.; and Kwiatkowski, T. 2020\.  Entities as Experts: Sparse Memory Access with Entity Supervision.  In _EMNLP_.
  * Han, Cheng, and Wang (2020) Han, J.; Cheng, B.; and Wang, X. 2020.  Open Domain Question Answering based on Text Enhanced Knowledge Graph with Hyperedge Infusion.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , 1475–1481. Online: Association for Computational Linguistics.
  * He et al. (2021) He, G.; Lan, Y.; Jiang, J.; Zhao, W. X.; and Wen, J.-R. 2021.  Improving Multi-Hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , WSDM ’21, 553–561. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450382977.
  * Jia et al. (2018a) Jia, Z.; Abujabal, A.; Saha Roy, R.; Strötgen, J.; and Weikum, G. 2018a.  Tempquestions: A benchmark for temporal question answering.  In _Companion Proceedings of the The Web Conference 2018_ , 1057–1062.
  * Jia et al. (2018b) Jia, Z.; Abujabal, A.; Saha Roy, R.; Strötgen, J.; and Weikum, G. 2018b.  Tequila: Temporal question answering over knowledge bases.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management_ , 1807–1810.
  * Jia et al. (2021) Jia, Z.; Pramanik, S.; Saha Roy, R.; and Weikum, G. 2021.  Complex Temporal Question Answering on Knowledge Graphs.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, 792–802.
  * Jin et al. (2021) Jin, W.; Khanna, R.; Kim, S.; Lee, D.-H.; Morstatter, F.; Galstyan, A.; and Ren, X. 2021.  ForecastQA: A Question Answering Challenge for Event Forecasting with Temporal Text Data.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , 4636–4650.
  * Kazemi et al. (2020) Kazemi, S. M.; Goel, R.; Jain, K.; Kobyzev, I.; Sethi, A.; Forsyth, P.; and Poupart, P. 2020.  Representation Learning for Dynamic Graphs: A Survey.  arXiv:1905.11485.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A Method for Stochastic Optimization.  arXiv:1412.6980.
  * Kolitsas, Ganea, and Hofmann (2018) Kolitsas, N.; Ganea, O.-E.; and Hofmann, T. 2018.  End-to-End Neural Entity Linking.  arXiv:1808.07699.
  * Lacroix, Obozinski, and Usunier (2020) Lacroix, T.; Obozinski, G.; and Usunier, N. 2020.  Tensor Decompositions for Temporal Knowledge Base Completion.  In _ICLR_.
  * Lan et al. (2021) Lan, Y.; He, G.; Jiang, J.; Jiang, J.; Zhao, W. X.; and Wen, J.-R. 2021.  Complex Knowledge Base Question Answering: A Survey.  _arXiv preprint arXiv:2108.06688_.
  * Liu et al. (2019) Liu, Y.; Ott, M.; Goyal, N.; Du, J.; Joshi, M.; Chen, D.; Levy, O.; Lewis, M.; Zettlemoyer, L.; and Stoyanov, V. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _ArXiv_ , abs/1907.11692.
  * Miller et al. (2016) Miller, A.; Fisch, A.; Dodge, J.; Karimi, A.-H.; Bordes, A.; and Weston, J. 2016\.  Key-Value Memory Networks for Directly Reading Documents.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , 1400–1409. Austin, Texas: Association for Computational Linguistics.
  * Neelam et al. (2021) Neelam, S.; Sharma, U.; Karanam, H.; Ikbal, S.; Kapanipathi, P.; Abdelaziz, I.; Mihindukulasooriya, N.; Lee, Y.-S.; Srivastava, S.; Pendus, C.; et al. 2021.  SYGMA: System for Generalizable Modular Question Answering OverKnowledge Bases.  _arXiv preprint arXiv:2109.13430_.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Kopf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., _Advances in Neural Information Processing Systems 32_ , 8024–8035. Curran Associates, Inc.
  * Qiu et al. (2020) Qiu, Y.; Wang, Y.; Jin, X.; and Zhang, K. 2020.  Stepwise Reasoning for Multi-Relation Question Answering over Knowledge Graph with Weak Supervision.  In _Proceedings of the 13th ACM International Conference on Web Search and Data Mining_ , WSDM ’20. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450368223.
  * Saxena, Chakrabarti, and Talukdar (2021) Saxena, A.; Chakrabarti, S.; and Talukdar, P. 2021.  Question Answering over Temporal Knowledge Graphs.  In _ACL_.
  * Saxena, Tripathi, and Talukdar (2020) Saxena, A.; Tripathi, A.; and Talukdar, P. 2020.  Improving Multi-hop Question Answering over Knowledge Graphs using Knowledge Base Embeddings.  In _ACL_.
  * Souza Costa, Gottschalk, and Demidova (2020) Souza Costa, T.; Gottschalk, S.; and Demidova, E. 2020.  Event-QA: A dataset for event-centric question answering over knowledge graphs.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 3157–3164.
  * Sun, Bedrax-Weiss, and Cohen (2019) Sun, H.; Bedrax-Weiss, T.; and Cohen, W. W. 2019.  PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text.  _ArXiv_ , abs/1904.09537.
  * Sun et al. (2018) Sun, H.; Dhingra, B.; Zaheer, M.; Mazaitis, K.; Salakhutdinov, R.; and Cohen, W. 2018.  Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , 4231–4242. Brussels, Belgium: Association for Computational Linguistics.
  * Trouillon et al. (2017) Trouillon, T.; Dance, C. R.; Éric Gaussier; Welbl, J.; Riedel, S.; and Bouchard, G. 2017.  Knowledge Graph Completion via Complex Tensor Factorization.  _JMLR_.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017.  Attention is All You Need.  In _NIPS_.
  * Xiong et al. (2019) Xiong, W.; Yu, M.; Chang, S.; Guo, X.; and Wang, W. Y. 2019.  Improving Question Answering over Incomplete KBs with Knowledge-Aware Reader.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , 4258–4264. Florence, Italy: Association for Computational Linguistics.
  * Xu et al. (2019) Xu, K.; Lai, Y.; Feng, Y.; and Wang, Z. 2019.  Enhancing Key-Value Memory Neural Networks for Knowledge Based Question Answering.  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)_ , 2937–2947. Minneapolis, Minnesota: Association for Computational Linguistics.
  * Yang et al. (2014) Yang, B.; Yih, W.-t.; He, X.; Gao, J.; and Deng, L. 2014.  Embedding entities and relations for learning and inference in knowledge bases.  _arXiv preprint arXiv:1412.6575_.
  * Zhang et al. (2019) Zhang, Z.; Han, X.; Liu, Z.; Jiang, X.; Sun, M.; and Liu, Q. 2019.  ERNIE: Enhanced Language Representation with Informative Entities.  arXiv:1905.07129.
  * Zhou, Huang, and Zhu (2018) Zhou, M.; Huang, M.; and Zhu, X. 2018.  An Interpretable Reasoning Network for Multi-Relation Question Answering.  In _COLING_.

##  8 Appendix

###  8.1 CronQuestions Statistics

Additional statistics of the CronQuestions dataset are shown in Table 4.
Simple Reasoning questions contains Simple Entity and Simple Time questions,
while Complex Reasoning contain Before/After, First/Last, and Time Join
questions. Entity Answer questions contain Simple Entity, Before/After,
First/Last, and Time Join questions, while Time Answer questions contain
Simple Time and First/Last.

| Train | Dev | Test
---|---|---|---
Simple Entity | 90,651 | 7,745 | 7,812
Simple Time | 61,471 | 5,197 | 5,046
Before/After | 23,869 | 1,982 | 2,151
First/Last | 118,556 | 11,198 | 11,159
Time Join | 55,453 | 3,878 | 3,832
Simple Reasoning | 152,122 | 12,942 | 12,858
Complex Reasoning | 197,878 | 17,058 | 17,142
Entity Answer | 225,672 | 19,362 | 19,524
Time Answer | 124,328 | 10,638 | 10,476
Total | 350,000 | 30,000 | 30,000

Table 4: Number of questions in our dataset across different types of
reasoning required and different answer types.

###  8.2 Generation of Additional Complex Questions

We create ‘before & after’ questions that include both ‘before’ and ‘after’
constraints, e.g., “Which movies won The Best Picture after The Godfather and
before Forrest Gump?”. Additionally, we create ‘before/after & first/last’
questions that include both ‘before/after’ and ‘first/last’ constraints, e.g.,
“Which is the last movie to win Best Picture after The Godfather?”. For both
new complex types, we end up with 261 QA pairs that are only used for
inference (unseen during training). We also provide the QA pairs in the
submission files.

The two evaluation datasets were created as follows. The ‘before & after’
dataset was generated by identifying all before/after questions in the
original CronQuestions dataset which contained the ‘position held’ relation.
These questions were then filtered to a subset derived from 14 templates which
could be easily modified to contain both before and after conditions while
remaining syntactically correct. For example, the template ‘Who held the
position of tail after head’ was included in this set because it can be
converted into a before & after question by adding ‘ and before tail2’ to the
end of the sentence. All of the new before & after questions were created in
this manner by adding either ‘ and before tail2’ or ‘ and after tail2’ for
questions which originally contained after or before conditions
(respectively).

The ‘tail2’ and answer entities for these questions were selected by first
identifying all answer entities from the original question which have a start
time in the TKG which is strictly greater (less) than that of the start time
of the 1head’ entity for questions containing an after (before) condition.
These entities were then sorted in ascending order of their closeness in time
to the 1head’ entity. The entity containing the third-closest distinct start
time to that of the ‘head’ entity was selected as the ‘tail2’ entity while all
other entities containing a start date between that of the ‘head’ and ‘tail2’
entities were used as answer entities.

The ‘before/after & first/last’ questions were generated using a similar
process. For questions originally containing an ‘after’ condition, we also add
the word ‘first’ prior to the ‘tail’ relation. Likewise, we add the word
‘last’ prior to the ‘tail’ relation for questions which originally contained a
‘before’ condition. The answer set is then filtered to only contain the entity
which has the closest start date in time to that of the ‘head’ entity.

###  8.3 Variants of TempoQR

Difference with TComplEx. TComplEx is a TKG embedding scoring function
(decoder) and can only answer questions that involve a single fact, e.g.,
$(s,r,?,\tau)$, with a provided TKG relation $r$. TempoQR handles questions
that involve multiple facts and does not rely on a specific relation $r$. The
main contribution here is to encode semantic and temporal information from
multiple facts to a single question representation $q$, which can be used as a
virtual relation (Sec. 4.2 and 4.3). For scoring answers using $q$, different
decoders can be implemented via Eq.(9) and (10), e.g., the TComplEx or a dot
product decoder. For TempoQR-Soft, Eq.(6) should be adapted according to the
decoder.

We also include the following Table to directly compare TComplEx with TempoQR
and to evaluate the performance with other decoders for complex temporal
questions (H@1). The TComplEx model is implemented via Eq.(1) by providing the
ground-truth relation $r$ of each question. The first row of the Table shows
that TempoQR vastly outperforms TComplEx since the latter cannot handle
complex questions. Moreover, the second row shows that our method is
competitive across different decoders, such as the dot-product
$\phi_{\text{dot}}$.  Model$\rightarrow$ TComplEx CronKGQA TempoQR-Soft
TempoQR-Hard Decoder$\downarrow$ $\phi_{\text{TComplEx}}$ 0.022 0.392 0.655
0.864 $\phi_{\text{dot}}$ Not applicable 0.248 0.366 0.721

Ensemble of Hard and Soft Supervision. When we add time embeddings of both
approaches and measure the H@1(%) for complex questions, the ensemble improves
by 2.1 points over TempoQR-Hard for ‘before/after’ questions where TempoQR-
Hard cannot retrieve the accurate time from the TKG. For ‘first/last’ and
‘time join’ question, the soft supervision introduces noise and actually
decreases the performance compared to TempoQR-Hard by 1.9 and 6.7 points,
respectively.

###  8.4 Fusion of Time Embeddings

TempoQR-cat and TempoQR-att. TempoQR-cat and TempoQR-att are variations of
TempoQR with different fusion implementations compared to the one in Section
4.3. In TempoQR-cat, we substitute the sum operator in (7)
$\big{(}\mathbf{q}_{T_{i}}=\mathbf{q}_{T_{i}}+\mathbf{t}_{1}+\mathbf{t}_{2}\big{)}$
by concatenating the entity and time embeddings followed by a learnable
projection. In TempoQR-att, we append the time embeddings to the embedding
matrix as new tokens of the sentence. This is equivalent to transforming the
given sentence from, e.g., “Which movie won the Best Picture after The
Godfather” to “Which movie won the Best Picture after The Godfather, 1972” and
applying EntityQR. We use TempoQR-att with hard-supervision only.

| Complex Questions | Simple Questions
---|---|---
| Before/ | First/ | Time | Simple | Simple
| After | Last | Join | Entity | Time
Soft Super. |  |  |  |  |
TempoQR-cat | 0.605 | 0.518 | 0.794 | 0.985 | 0.867
TempoQR | 0.670 | 0.570 | 0.894 | 0.991 | 0.987
Hard Super. |  |  |  |  |
TempoQR-cat | 0.692 | 0.847 | 0.866 | 0.989 | 0.940
TempoQR-att | 0.683 | 0.835 | 0.871 | 0.989 | 0.881
TempoQR | 0.714 | 0.853 | 0.978 | 0.992 | 0.988

Table 5: Hits@1 for fusion strategies.

Table 5 shows the results for different strategies of fusing time embeddings
with hard or soft supervision. As we can see, our implementation of summing
entity and time embeddings (TempoQR) performs the best. We note that this is
typically the way transformer-based architectures combine token and positional
embeddings. Moreover, TempoQR-cat and TempoQR-att perform much worse for ‘time
join’ and ‘simple’ questions. This means that a lot of important time
information is ignored by their projection and attention layer, respectively.
Whereas, by summing the time embeddings, we ensure that all the information is
encoded.

###  8.5 Training Size

Figure 4 shows the performance for complex questions for different training
sizes. As the training size reduces, both TempoQR-Hard and TempoQR-Soft
perform worse. We observe a slightly faster performance drop for TempoQR-Hard.

$0$$20$$40$$60$$80$$100$$40$$50$$60$$70$$80$$90$% Training DataHits@1
(%)TempoQR-HardTempoQR-Soft

Figure 4: Evaluation for different training size.

###  8.6 Is Time All We Need?

In this experimental configuration, the goal is to evaluate TempoQR-Hard with
different ways that generate time embeddings. First, we use TComplEx
embeddings for the (i) start and end timestamps (Section 4.3) (TComplEx-
Start&End) and (ii) a randomly sampled timestamp between the start and end
timestamp (TComplEx-Sampled). The second approach is instead of using TComplEx
embeddings to use positional embeddings as in (Vaswani et al. 2017). The
positional embedding are generated based on each timestamp’s identifier and
are ensured to preserve the ordering of the timestamps in the embedding space.
We use positional embeddings of the start and end timestamp for TempoQR-Hard
(PosEmb-Start&End). Finally, we generate completely random time embeddings,
which we use them for the start and end timestamps (RandEmb-Start&End). This
ensures that all time embeddings are well-separated. In all cases, the time
embeddings are not updated during QA.

TempoQR-Hard | Before/ | First/ | Time
---|---|---|---
Time Embeddings | After | Last | Join
TComplEx-Sampled | 0.602 | 0.516 | 0.919
TComplEx-Start&End | 0.714 | 0.853 | 0.978
PosEmb-Start&End | 0.724 | 0.832 | 0.976
RandEmb-Start&End | 0.713 | 0.868 | 0.976

Table 6: Hits@1 for different time embeddings of TempoQR-Hard.

Table 6 shows the results for differently generated time embeddings for
TempoQR-Hard. As we can see, using the start and end timestamps is a key
decision that provides the best results (TComplEx-Sampled has the lowest
performance). Table 6 indicates is that the time embeddings themselves do not
play an important role. What TempoQR-Hard needs is to be able to associate
given questions with different times. This is confirmed since RandEmb have the
perform equally with TComplEx embeddings. Here, the random embeddings are
nothing more than a unique identifier for each timestamp. They also perform
the best for ‘first/last’ questions, since the timestamps are well-separated
in the embedding space. On the other hand, PosEmb perform the best for
‘before/after’ questions. This happens because the timestamp ordering is
preserved in the embedding space and allows for better ‘before/after’
reasoning.


# Channel Selection for Wi-Fi 7 Multi-Link Operation via Optimistic-Weighted
VDN and Parallel Transfer Reinforcement Learning

Pedro Enrique Iturria-Rivera, , Marcel Chenier2, Bernard Herscovici2,
Burak Kantarci, and Melike Erol-Kantarci, 2NetExperience., Ottawa, Canada
Emails:{pitur008, burak.kantarci<EMAIL_ADDRESS>{marcel,
<EMAIL_ADDRESS>1School of Electrical Engineering and Computer
Science, University of Ottawa, Ottawa, Canada

###### Abstract

Dense and unplanned IEEE 802.11 Wireless Fidelity (Wi-Fi) deployments and the
continuous increase of throughput and latency stringent services for users
have led to machine learning algorithms to be considered as promising
techniques in the industry and the academia. Specifically, the ongoing IEEE
802.11be EHT —Extremely High Throughput, known as Wi-Fi 7— amendment propose,
for the first time, Multi-Link Operation (MLO). Among others, this new feature
will increase the complexity of channel selection due the novel multiple
interfaces proposal. In this paper, we present a Parallel Transfer
Reinforcement Learning (PTRL)-based cooperative Multi-Agent Reinforcement
Learning (MARL) algorithm named Parallel Transfer Reinforcement Learning
Optimistic-Weighted Value Decomposition Networks (oVDN) to improve intelligent
channel selection in IEEE 802.11be MLO-capable networks. Additionally, we
compare the impact of different parallel transfer learning alternatives and a
centralized non-transfer MARL baseline. Two PTRL methods are presented: Multi-
Agent System (MAS) Joint Q-function Transfer, where the joint Q-function is
transferred and MAS Best/Worst Experience Transfer where the best and worst
experiences are transferred among MASs. Simulation results show that oVDNg
–only the best experiences are utilized– is the best algorithm variant.
Moreover, oVDNg offers a gain up to $3\%$, $7.2\%$ and $11\%$ when compared
with VDN, VDN-nonQ and non-PTRL baselines. Furthermore, oVDNg experienced a
reward convergence gain in the $5$ GHz interface of $33.3\%$ over oVDNb and
oVDN where only worst and both types of experiences are considered,
respectively. Finally, our best PTRL alternative showed an improvement over
the non-PTRL baseline in terms of speed of convergence up to 40 episodes and
reward up to $135\%$.

Index Terms — Multi-Link Operation, Channel Selection, Reinforcement Learning,
Wi-Fi 7, VDN

##  I Introduction

R ecent IEEE 802.11 Wireless Fidelity (Wi-Fi) documentation introduces a new
standard named 802.11be EHT –Extremely High Throughput– or Wi-Fi 7, which will
become the replacement for the former 802.11ax amendment. The release of the
final draft is expected by May, 2024 [1] adding to the new set of
modifications a modulation rate increase up to 4096 QAM, channel bandwidth up
to 320 MHz and more importantly the addition of Multi-Link Operation (MLO) and
Multiple Resource Units (MRU) capabilities [2]. These new features will allow
Wi-Fi technology to adapt to the continuously increasing demand in terms of
throughput and low-latency services such as Virtual Reality, Live Streaming
and Ultra-High Definition video in dense deployments.

Figure 1:  Instead of utilizing one Multi-Agent System (MAS) where each agent
provides a joint action selection for all interfaces, in the context of MLO,
we divide it in three MASs. Each MAS provides an action selection per
interface and parallel transfer learning is leveraged to improve learning.

In this work, with the aid of Fig. 1 we raise the following question: Is it
beneficial to transfer knowledge in a parallel fashion among MASs? To do so,
we propose dividing a complex problem in less complex ones to enable the
utilization of Parallel Transfer Reinforcement Learning (PTRL) methods. Thus,
we study PTRL to improve channel selection in the context of MLO in IEEE
802.11be. MLO adds an extra dimension to channel selection in IEEE 802.11
networks since it permits that Multi-Link Devices (MLD)s such as terminals and
Access Points (APs) use their available interfaces for multi-link
communications. This means that not only channel selection should be performed
concurrently in one interface, say $2.4$ GHz; but this procedure needs to be
repeated for the rest of the interfaces. Specifically, we propose leveraging
Multi-Agent Reinforcement Learning (MARL) and PTRL to optimize channel
selection in IEEE 802.11be MLO-capable networks. MARL has been brought to the
attention of the wireless networks research community due its realistic
approach [3]. In addition, transfer learning has also proven its applicability
and positive implications in improving learning convergence and Key Importance
Metrics (KPIs) in wireless networks-based on RL multi-agent solution [4].
However, in this work, we utilize a less explored area of transfer learning
called parallel transfer learning that proposes concurrent knowledge transfer
without the source/target paradigm of the well-known sequential transfer
learning. More specifically we put our interests on parallel transfer
reinforcement learning among Multi-Agent Systems (MASs). To enable Machine
Learning (ML)-based technology and others in Wi-Fi, a project named OpenWiFi
[5] propose disaggregating the Wi-Fi technology stack by utilizing open source
software for the Access Point (AP) firmware operating system. Such technology
enables the integration with diverse cloud-based services in the form of ML-
based applications such as the one proposed in this work.

The rest of this paper is organized as follows. Section II presents the
existing works related to parallel transfer learning and RL-based channel
selection in Wi-Fi. In Section III a brief system model is described. Section
IV introduces the proposed scheme Parallel Transfer Reinforcement Learning
Optimistic-Weighted VDN (referred as oVDN) and its design considerations,
including the PTRL methods and the Markov Decision Process (MDP).
Additionally, section V presents a study over the proposed scheme’s
performance. Finally, section VI concludes the paper.

##  II Related work

Channel selection algorithms in Wi-Fi have been of great interest in the
recent literature. However, channel selection in IEEE 802.11be MLO has not
been studied due its novelty. In addition, to the best of our knowledge, this
is the first work that tackles Parallel Transfer Reinforcement Learning among
MASs and applies such technique in the context of channel selection in IEEE
802.11be. Below, we list some of the works related to parallel transfer
learning and channel selection.

In [6] the authors utilized parallel transfer learning among intelligent
agents to coordinate electrical vehicle charging to prevent transformer
overload in smart grid scenarios. This work introduces, for the first time,
parallel transfer learning and discusses the advantages over the sequential
transfer learning techniques. Moreover, the same authors present in a later
work [7] a survey study where possible alternatives to employ parallel
transfer learning is considered. On the other hand, channel selection has been
studied in the previous Wi-Fi standards where only Single Link Operation is
considered. For instance, in [8], the authors study channel selection for a
single user utilizing a Deep Q-Network agent. In this work, at the beginning
of each time slot, the user selects a channel and receives a reward based on
how successful the transmission was. Additionally, in [9], a Q-Learning based
algorithm is utilized in the selection of the channel/subframe in LTE-Wi-Fi
scenarios. In the previous work, the authors measure the effectiveness of the
algorithm based on the channel utilization and channel utilization fairness
among the APs. In the next section, we present the description of the system
model utilized in this work.

##  III System Model

In this work, we utilize an IEEE 802.11be network with a predefined set of
$\mathcal{N}$ APs and $\mathcal{P}$ stations attached per AP. All APs are MLO-
capable with a number of available interfaces $n_{f}$. All APs and stations
support up to a maximum of 16-SU multiple-input multiple-output (MIMO) spatial
streams. The path loss model corresponds to the enterprise model described in
[10]. In addition, we consider an adaptive control rate based on Signal-to-
Interference-Noise Ratio (SINR) with a maximum 4096 QAM modulation rate.

##  IV Parallel Transfer Reinforcement Learning Optimistic Weighted VDN (oVDN)

In this section, we discuss the details and considerations taken in the design
of the Parallel Transfer Reinforcement Optimistic Weighted VDN (oVDN)
architecture.

###  IV-A Value Decomposition Networks (VDN)

Several MARL algorithms can been found throughout the literature. According to
[11] MARL can be classified either as Independent Learning (IL), Centralized-
Training Decentralized Execution (CTDE) or Centralized Learning (CL) depending
on how action selection and training is performed among agents. In some
challenges, IL has shown good performance such as in [12], however instability
is typically observed due the concurrent exploration/training of the agents
[13]. On the other side, CL assumes complete access to the agents’ information
and hence, it becomes a single agent problem. However, CL approaches are not
realistic and can present several issues in terms of increasing action and
state space. Finally, CTDE approaches allow to have middle ground between the
two previously described techniques with an independent action selection and a
centralized training step. Value Decomposition Networks (VDN) is proposed in
[14] and can be classified as a fully-cooperative CTDE algorithm that lies
between Independent Q-Learning and Centralized Q-Learning. VDN builds upon the
assumption that the multiagent system joint action-value function can be
decomposed into individual agent’s value functions as:

$Q_{tot}(\\{\bm{h}^{1},...,\bm{h}^{n}\\},\\{\bm{a}^{1},...,\bm{a}^{n}\\})\approx\sum_{n=1}^{|\mathcal{N}|}\bar{Q}^{n}(h^{n},a^{n})$
(1)

where $\bar{Q}$ corresponds to the $n^{th}\in\mathcal{N}$ (the agents are
considered to be APs in this work) agent’s policy that only depends on its
individual observation history, $\\{\bm{h}^{1},...,\bm{h}^{n}\\}$ and
$\\{\bm{a}^{1},...,\bm{a}^{n}\\}$ corresponds to the tuple of histories and
actions of the $n^{th}$ agent, respectively. As mentioned previously, VDN
assumes full cooperation among agents which allows to define a team reward.
Thus, the team reward can be decomposed as:

$\displaystyle r_{tot}=\sum_{n=1}^{|\mathcal{N}|}r^{n}(h^{n},a^{n})$ (2)

Then, from the perspective of one agent (say $n=1$) the additive joint
Q-function can be defined as:

$\begin{split}Q_{tot}(\bm{s},\bm{a})=\mathbb{E}[\sum_{t=1}^{\infty}\gamma^{t-1}r_{tot}(\bm{s}_{t},\bm{a}_{t})|\bm{s}_{1}=\bm{s},\bm{a}_{1}=\bm{a}]\\\
=\mathbb{E}[\sum_{t=1}^{\infty}\gamma^{t-1}r^{1}(h_{t}^{1},a_{t}^{1})|\bm{s}_{1}=\bm{s},\bm{a}_{1}=\bm{a}]+\\\
\sum_{n=2}^{|\mathcal{N}|}\mathbb{E}[\sum_{t=1}^{\infty}\gamma^{t-1}r^{n}(h_{t}^{n},a_{t}^{n})|\bm{s}_{1}=\bm{s},\bm{a}_{1}=\bm{a}]\\\
=:\tilde{Q}_{tot}^{1}(\bm{s},\bm{a})+\sum_{n=2}^{|\mathcal{N}|}\tilde{Q}_{tot}^{n}(\bm{s},\bm{a})\\\
\approx\bar{Q}_{tot}^{1}(h^{1},a^{1})+\sum_{n=2}^{|\mathcal{N}|}\bar{Q}_{tot}^{n}(h^{n},a^{n})\end{split}$
(3)

where $\gamma$ corresponds to the discount factor. Finally, it can be seen
that the last equation on (3) corresponds to Equation 1.

Figure 2: Overview of the oVDN algorithm

###  IV-B Optimistic Weighted VDN

In [15], the authors propose two weighting schemes for the QMIX algorithm
[16]. The QMIX algorithm, similar to VDN is a fully cooperative algorithm that
performs value function factorization among the agents. Instead of using an
additive approach as mixing strategy, QMIX use hypernetworks that enforce
monotonic Q-function behavior. However, QMIX assumes equal importance among
actions which can lead to optimal policy failure. To solve the previous issue,
the authors propose the Optimistically-Weighted QMIX that enables the
assignation of weights per Q-function and consequently take better joint
actions. The aforementioned issue also affects VDN due the equally weighted
assumption in its additive approach. The weighting parameter can be defined as
follows:

$\displaystyle
w(o,\bm{a})=\begin{cases}1&Q_{tot}(\bm{s},\bm{a};\theta^{\prime})<y_{i},\\\
\alpha&otherwise\\\ \end{cases}$ (4)

where $y_{i}=r_{i}+\gamma Q_{tot}(s,a;\theta)$, $\theta$ the target policy,
$\theta^{\prime}$, the evaluation policy and $\alpha\in(0,1]$ a predefined
weight. It can be seen that this technique downweights the contribution of
those actions that are considered suboptimal.

###  IV-C Multi-Agent Parallel Transfer Reinforcement Learning (MA-PTRL)

Transfer Reinforcement Learning is a technique employed to accelerate
convergence and improve learning in RL. The idea comes from human psychology
where learned actions or concepts can be utilized to speed up the acquisition
of new knowledge [17]. In the context of multi-agent RL, transfer learning
typically happens in a sequential and unidirectional flow, from agents defined
as source or teacher agents towards agents with some or minimal knowledge
named target or student agents. Evidently, in some scenarios, the assumption
of the existence of source-target-agent relationship is not known; in other
words there is no hint which agent is the source or the target. To address the
previously mentioned issue, Parallel Transfer Reinforcement Learning (PTRL) in
intra-multi-agent systems is introduced in [6] where source and target agents
run concurrently. Thus, knowledge transfer occurs in a parallel and
bidirectional way. Consequently, it removes the need of having a set of
previously trained source agents, as required by sequential RL.

In this work, to the best of our knowledge, we introduce for the first time
PTRL for cooperative inter-multi-agent systems. We identify two PTRL types:
Intra-PTRL that corresponds to the scenario where agents in a MAS concurrently
transfer knowledge and inter-PTRL where transfer learning occurs concurrently
among MAS systems. Employing this technique can have several benefits and
direct implications on the definition of the RL problem such as reduction of
the action and state space as well as convergence and learning improvement.
However, the MASs involved in any PTRL application must have an inner
relationship to obtain the expected behavior as needed in sequential transfer
learning. Moreover, a careful design must be taken in the MDP definition to
avoid negative transfer. For example, we realize that scaling rewards among
MAS systems do have an impact on the effectiveness of Multi-Agent Parallel
Transfer Reinforcement Learning (MA-PTRL). In the next subsection, we
introduce the PTRL methods used in this work.

1 Let $\mathcal{M}$ be the set of multiagent VDN systems. For each
$m^{th}\in\mathcal{M}$ VDN, initialize the agents’ target and evaluation
recurrent policies $\theta$ and $\theta^{\prime}$, respectively. Set initial
hyperparameters and set experience buffers $\mathcal{D}$ and
$\mathcal{D}_{ep}$.

2 for  _environment step $t\leftarrow 1$ to $T$_ do

3 $\textbf{u}_{t}=\\{\\}$

4 for  _each VDN $m$ _ do

5 for  _each agent $i$ _ do

6 Observe state $s^{m,i}_{t}=\\{a^{m,i}_{t},i^{m}\\}$ and append to
$\tau^{m,i,a}_{t}=\tau^{m,i,a}_{t-1}\cup\\{(s^{m,i}_{t},u^{m,i}_{t-1})\\}$

7

8 $\epsilon^{m,i}_{t}=\epsilon^{m,i}_{t}-\epsilon_{d}$ if
$\epsilon^{m,i}_{t}-\epsilon_{d}>\epsilon_{min}$ else $\epsilon_{min}$

9 Select joint action:

10 $None$

11

12

13 end for

14 $\textbf{u}_{t}=\textbf{u}_{t}\cup\textbf{u}^{m,a}_{t}$

15 end for

16 Execute $\textbf{u}_{t}$ in the environment for  _each VDN $m$ _ do

17 for  _each agent $i$ _ do

18 Observe next state $s^{m,i}_{t+1}$ and reward $r^{m,i}$

19 end for

20
$\mathcal{D}^{m}=\mathcal{D}^{m}\cup\\{(\textbf{o}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{o}^{m}_{t+1})\\}$
$\mathcal{D}^{m}_{ep}=\mathcal{D}^{m}_{ep}\cup\\{(\textbf{o}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{o}^{m}_{t+1})\\}$

21 end for

22 if  _$t$ mod $n_{steps}=0$_ then

23

24 for  _each VDN $m$ _ do

25

26 # (1) Transfer $Q_{tot}$ among MAS.

27
$\bm{y}_{B}=r_{B}+\gamma(\bm{Q}^{m}_{B,tot}+\sigma\frac{1}{2}\sum_{n}^{\mathcal{M}\setminus
m}\bm{Q}^{n}_{B,tot})$

28
$\mathcal{L}(\theta^{m})=\sum_{b=1}^{B}(\bm{w}(\bm{o}_{b},\bm{u}_{b})([\hat{Q}^{m}_{b,tot}+\sigma\frac{1}{2}\sum_{n}^{\mathcal{M}\setminus
m}\hat{Q}^{n}_{b,tot}]-y_{b})^{2}$

29 $\theta^{m}\leftarrow\theta^{m,^{\prime}}$

30 for  _each VDN $n$ $\in\\{\mathcal{M}\setminus m$}_ do

31 # (2) Transfer best and worst experiences among MAS.

32
$\\{(\textbf{s}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{g}=\texttt{sort}_{g}(\mathcal{D}^{n}_{ep},n_{g})$

33
$\\{(\textbf{s}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{b}=\texttt{sort}_{b}(\mathcal{D}^{n}_{ep},n_{b})$

34
$\mathcal{D}^{m}=\mathcal{D}^{m}\cup\\{(\textbf{s}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{g}\cup\\{(\textbf{s}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{b}$

35

36 end for

37 if  _$\mathcal{D}^{m} >B_{s}$_ then

38 Randomly sample a batch of transitions $\bm{B}$ with size $B_{s}$ from
$\mathcal{D}^{m}$

39 for  _each batch $b\in\bm{B}$ _ do

40
$\bm{Q}^{m}_{\\{1..|\mathcal{M}|\\}_{b}}=\pi^{m}(\tau^{m}_{b},u^{m}_{b};\theta^{m,^{\prime}})$

41 $Q^{m}_{b,tot}=\mu(\bm{Q}^{m}_{\\{1..|\mathcal{M}|\\}_{b}})$

42
$\bm{\hat{Q}}^{m}_{\\{1..|\mathcal{M}|\\}_{b}}=\pi^{m}(\tau^{m}_{b},u^{m}_{b};\theta^{m})$

43 $\hat{Q}^{m}_{b,tot}=\mu(\bm{\hat{Q}}^{m}_{\\{1..|\mathcal{M}|\\}_{b}})$

44 end for

45 Reset all $D_{ep}$ buffers

46 end if

47

48 end for

49

50 end if

51

52 end for

Algorithm 1 Parallel Transfer Reinforcement Learning Optimistic-Weighted VDN
(oVDN)

###  IV-D Parallel Transfer Learning (PTRL) Methods

PTRL is a challenging technique due its inherent online characteristic.
Despite the benefits previously mentioned, the lack of source-target task
relationship enforce a careful transfer design. Differently from other works,
we utilize PTRL to improve convergence and alleviate the action/state space
large dimensionality that a centralized multi-agent RL problem definition
could suffer.

Let’s consider the existence of $\mathcal{M}$ MASs that will concurrently
transfer knowledge among them. As observed in Figure 2 and Algorithm 1, we
utilize two PTRL techniques in the context of cooperative MARL: (1) MAS Joint
Q-function Transfer and (2) MAS Best/Worst Experience Transfer. Each of the
previously mentioned techniques can be summarized as follows:

MAS Joint Q-function Transfer: As the name indicates the average joint
Q-functions ($Q_{tot}$) of the set $\\{\mathcal{M}\setminus m\\}$ are used in
the training stage of each individual MAS. Thus, the loss function for the
$m^{th}$ MAS can be written as follows:

$y=r+\gamma(Q^{m}_{tot}+\sigma\frac{1}{|\mathcal{M}\setminus
m|}\sum_{i}^{\mathcal{M}\setminus m}Q^{i}_{tot})$ (5)

$\mathcal{L}=w(o,u)([\hat{Q}^{m}_{tot}+\sigma\frac{1}{|\mathcal{M}\setminus
m|}\sum_{i}^{\mathcal{M}\setminus m}\hat{Q}^{i}_{tot}]-y)^{2}$ (6)

where $\sigma$ is a tunable transfer weight, $Q_{tot}$ and $\hat{Q}_{tot}$ are
target and evaluation Q-functions, respectively. Transferring the Q-function
values can help to improve convergence since it suggests a consensus on the
set of actions that are being selected by the MASs comprising the PTRL scheme.

MAS Best/Worst Experience Transfer: This approach relies on the nature of
offline RL algorithms that utilize an experience replay as part of their
policy training. Intuitively, best and worst experiences contribute to the
final agent’s action selection policy due the fact that the best action will
receive higher rewards than worst ones. Specifically, we gather during each
episode, for each $m^{th}$ MAS, $n_{e}$ number of sample experiences and store
them in a temporal buffer $\mathcal{D}_{ep}$. As indicated in Equations
(7)-(8), we sort $(n_{g},n_{b})<n_{e}$ samples ranking the best and worst
experiences based on the ones with higher and lower rewards, respectively.

$\\{(\textbf{s}^{m}_{t},\textbf{u}^{m}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{g}=\texttt{sort}_{g}(\mathcal{D}^{m}_{ep},n_{g})$
(7)
$\\{(\textbf{s}^{m}_{t},\textbf{u}^{m}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{b}=\texttt{sort}_{b}(\mathcal{D}^{m}_{ep},n_{b})$
(8) $\mathcal{D}^{\mathcal{M}\setminus m}=\mathcal{D}^{\mathcal{M}\setminus
m}\cup\\{(\textbf{s}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{s}^{m}_{t+1})\\}_{g}\cup\\{(\textbf{s}^{m}_{t},\textbf{u}^{m,a}_{t},r^{m}_{t},\textbf{s}^{s}_{t+1})\\}_{b}$
(9)

where $\textbf{s}_{t}^{m}$ , $\textbf{s}_{t+1}^{m}$, $r_{t}^{m}$ and
$\textbf{u}_{t}^{m}$ corresponds to the state, next state, team reward and
joint action, respectively. Finally, we append both experiences to the global
buffer as indicated by Equation (9).

###  IV-E State space selection

The state space is defined as follows:

$s_{(t,f)}^{n}=\\{a_{(t-1),f}^{n},h_{(t-2),f}^{n},AP_{id}^{n}\\}$ (10)

where $a_{(t-1),f}^{n}$ corresponds to the last action taken,
$h_{(t-2),f}^{n}$ the history action taken before it and the $AP_{id}$
corresponds to the ID of $n^{th}$ AP. The first two terms help to alleviate
partial observability via the utilization of the Gated Recurrent Unit (GRU)
layer in the Q-function as observed in Figure 2. The previous definition
refers to the action space of a single agent in any of the MASs of our
algorithm.

Figure 3: MCS ECDFs comparison per interface frequency of three variants of
transfer: oVDN, oVDNb and oVDNg, indicating transfer best and worst, only best
and only worst experiences, respectively. Figure 4: MCS ECDFs comparison per
interface frequency of the non-PTRL and our proposal using best experience
transfer.

###  IV-F Action space selection

In this subsection, we present the proposed general action space:

$a_{(t,f)}^{n}=\\{1,...,c_{(max,f)}\\}$ (11)

where $c_{(max,f)}$ corresponds to the maximum number of channels per
interface frequency, and $f\in\\{2.4,5,6\\}$ GHz indicates the frequency of
each of the MASs utilized in this work. As specified before, the current
definition indicates the action space of a single agent of any of the defined
MASs. Finally, the action space’s size corresponds to $|a_{t,f}|!$.

###  IV-G Reward function

The general reward function for the $m^{th}$ MAS can be defined as follows:

$r_{t}^{m}=min(\texttt{mcs}_{f}^{1},...,\texttt{mcs}_{f}^{|\mathcal{N}|})$
(12)

where $\texttt{mcs}\in\\{0,1,...,13\\}$ indicates the corresponding mapped
Modulation Code Selection (MCS) index given the measured SINR. The SINR
comprises the effect of all APs and stations considered during the
simulations. The mentioned mapping is done according the IEEE 802.11be that
employs a similar MCS-SINR mapping as IEEE 802.11ax. In addition we scale the
reward to $[-1,1]$.

Figure 5: Gain $\Theta$ comparison per AP and interface frequency (a) oVDNg
and VDN, (b) oVDNg and VDN-nonQ, (c) oVDNg and non-PTRL. The blue and red area
indicates what technique offers the best performance.

A special consideration is taken in the context of channel selection in IEEE
802.11be for the MA-PTRL proposed scheme regarding the definition of the
rewards. Evidently, Q-functions depend on the rewards acquired during the
interaction of the environment and as discussed in subsection IV-D,
Q-functions are used as part of the information transferred. Thus, different
reward’s scales can provoke that some of the MASs comprising the MA-PTRL
algorithm can impose their action selection policy. Specifically, we realize
that MCS selection according the SINR ranges varies depending the interface
frequency and channel bandwidth. Thus, we scale the rewards received by each
MASs. Notice that this consideration must only be taken when there is a
scaling difference between MASs’ rewards in any PTRL use case.

##  V Performance evaluation

Simulations are performed using the flow-level simulator Neko 802.11be[18].
The bidirectional communication between the environment simulated in Neko and
the Pytorch-based RL scheme is performed via the ZMQ broker library.

###  V-A Simulation Settings

RL parameters and simulation settings are described in Table I and II,
respectively. Furthermore, we consider the scenario where there are
$|\mathcal{N}|\sim\mathcal{U}(25,40)$ users attached to each AP and the AP’s
locations are unknown, thus solely relying on RF feedback from the
environment. In addition, $80\%$ of the users are positioned randomly in a
radius $r\sim[1-8]$ m and $20\%$ within a radius of $r\sim[1-3]$ m. In the
next subsection, we will discuss the performance results of the proposed
scheme.

TABLE I: Reinforcement Learning Settings. Parameter | Value
---|---
Training steps | $1.5\mathrm{e}{4}$
Initial $\epsilon$ | 1
$\epsilon$ decay steps |  $500$ steps
$\epsilon$ minimum | $5\mathrm{e}{-2}$
Buffer $(\mathcal{D})$ size | $2\mathrm{e}{3}$
Batch size | $64$
Learning rate | $8\mathrm{e}{3}$
Discount factor $(\gamma)$ | $0.99$
Recurrent Layer hidden dimension | $64$
MultiLayer Perceptron hidden dimension | $64$
Weight initializer | Orthogonal
Deep Q-Network structure | Double Q-networks
Optimistic Weight $\alpha$ | $0.1$
Number of MASs |  $3,(2.4,5,6)$ GHz
Reduced buffer $(\mathcal{D}_{ep})$ size | $50$
Best/Worst transferred experiences |  $20\%|\mathcal{D}_{ep}|$
Transfer weight $(\sigma)$ | 1
TABLE II: Network Settings

Parameter | Value
---|---
IEEE protocol | 802.11be
Channel Bandwidth |  $20$ MHz/$40$ MHz/$80$ MHz/$160$ MHz
Carrier Frequency ($f_{c}$) |  $2.437$ GHz/$5.230$ GHz/$6.295$ GHz
Max Modulation/Max Modulation Coding Scheme | 4096 QAM/MCS 13
Number of APs per MAS $(\mathcal{N})$ | 5
Number of Stations per AP |  $N_{A}\sim\mathcal{U}(25,40)$
Max Spatial Streams | 16
Propagation Loss Model |  $P_{l}(d)=40.05+20\text{log}(f_{c}/2.4)+20\text{log}(\text{min}(d,10))+$
| $(d>10)*35\text{log}(d/10)+7W$
AP/STA Noise Figure |  $7$ dB
AP/STA Transmission Power |  $20$/$15$ dBm
CCA threshold | -82 dBm
Packet Error Rate |  $10$%

###  V-B Simulation Results

We present the performance results of our proposed scheme in terms of MCS
ECDF, ECDF gain and convergence, among the baselines and the best PTRL
variant. Figure 3 shows the MCS ECDFs of three difference variants based on
what type of experiences are being transferred. The results show that the ECDF
of the scenario, where only the best experiences are transferred (oVDNg),
contributes more positively to the channel selection and thus, higher MCS is
obtained. Interestingly, only transferring worst examples offers a better
performance over transferring both types of experiences. The reason behind
this behavior could be explained by the fact that we utilize a fix number of
worst and bad experiences and a weighted approach could be the best
alternative to use. Additionally, in Fig. 4, we present the results in terms
of MCS ECDFs for the centralized baseline and the best transfer variant
(oVDNg). It can be seen that our parallel transfer solution offers an
important improvement in terms of MCS over the non-parallel baseline in two
interfaces (2.4 and 5 GHz) with MCS in the range of $(10-13)$ over $(8-11)$
and a slight degradation in the 6 GHz interface.

Figure 6: Reward convergence for oVDN, oVDNg and oVDNb (a) $2.4$ GHz, (b) $5$
GHz and (b) $6$ GHz  Figure 7: Reward convergence for oVDNg, VDN and oVDNb (a)
$2.4$ GHz, (b) $5$ GHz and (b) $6$ GHz

In Fig. 5, we illustrate the obtained gain per AP and interface frequency of
oVDNg over three baselines: VDN, VDN-nonQ and non-PTRL, indicating both type
of experience transfer, absence of Joint Q-function transfer and the non-PTRL
case, respectively. The gain $\Theta(G_{X},G_{Y})$ corresponds to the area
difference among ECDFs as follows:

$\begin{split}\Theta(G_{X},G_{Y})&=\int\\{G_{Y}(x)-G_{X}(x)\\}dx\\\
&=\int\\{[1-G_{Y}(x)]-[1-G_{X}(x)]\\}dx\\\ &=\mu_{X}-\mu_{Y}\end{split}$ (13)

where $G_{Y}$ and $G_{X}$ correspond to the ECDFs of the compared variants and
$\mu_{X}$, $\mu_{Y}$ are their means. The upper blue colored area indicates
where the oVDNg performs better than the baselines and the red area otherwise.
Consequently, we observe that the oVDNg offers a gain up to $3\%$, $7.2\%$ and
$11\%$ when compared with (a) VDN, (b) VDN-nonQ and (c) non-PTRL baselines,
respectively.

Additionally, we present in Fig. 6 a comparison in terms of convergence per
frequency interface among oVDN’s PTRL variants. In (a) and (c) the behavior is
similar among the studied techniques, however in (b) where we show the reward
convergence of the 5GHz interface, we observe an improvement of $33.3\%$ of
oVDNg over oVDNb and oVDN, respectively. Finally, in Fig. 7, we can see the
convergence behavior of our best performer PTRL algorithm oVDNg, VDN and a
non-PTRL alternative. Evidently, our proposal outperforms the non-PTRL
baseline in terms of speed of convergence up to 40 episodes and reward up to
$135\%$. The previous results can be explained due the non-PTRL or centralized
variant’s action space size. For instance, as discussed in subsection IV-F,
the action space size of each MASs in the PTRL algorithm corresponds to
$|a_{f}|^{N},f\in\\{2.4,5,6\\}$, meanwhile the centralized to $|a_{2.4}\times
a_{5}\times a_{6}|^{N}$, where $a$ indicates the set of possible actions, the
$\times$ operator corresponds to the Cartesian product and $N$ the number of
agents. Thus, if $|a_{f}|=3$, PTRL offers a reduction of action space in the
order of $9^{N}$ which is quite considerable, especially when $N$ increases.

To sum up, we can foresee the advantages that can potentially offer a PTRL
approach among MASs such as oVDNg. As observed in our presented results,
faster convergence and better action selection are some of the most immediate
benefits. When decomposition of a MAS problem is feasible, we advise to
utilize PTRL to accelerate and improve RL performance since typically MARL
suffers from slow convergence and non-optimal action selection.

##  VI Conclusions

In this paper, we presented a Parallel Transfer Reinforcement Learning (PTRL)
and cooperative optimistic-weighted VDN algorithm to improve radio and
Reinforcement Learning (RL) related metrics such as Modulation Code Selection
(MCS) and convergence speed in IEEE 802.11be channel selection. To the best to
our knowledge, we studied for the first time, PTRL techniques in the context
of knowledge transfer among Multi-Agent Systems (MASs). Specifically, we
proposed two techniques named: MAS Joint Q-function Transfer and MAS
Best/Worst Experience Transfer. The previous techniques consist in
transferring the joint Q-Function of cooperative MARL algorithms such as VDN
and transfer the best and worst experiences during each episode. Moreover, we
presented a modification to the VDN algorithm taken from another technique
named QMix that allows to weight the contribution of each agent to the joint
Q-function. Furthermore, we presented the simulation results of our proposed
scheme and analyze how each PTRL method affects its behavior. Results showed
that the oVDNg offers an important improvement in terms of MCS over the non-
parallel baseline in two interfaces ($2.4$ and $5$ GHz) with MCS in the range
of $(1013)$ over $(811)$. Additionally, we present a metric gain to calculate
the MCS improvement. We observed that the oVDNg variant offers a gain up to
$3\%$, $7.2\%$ and $11\%$ when compared with VDN, VDN-nonQ and non-PTRL
baselines. In terms of convergence speed among oVDN alternatives, we show a
reward convergence gain in the $5$GHz interface of $33.3\%$ over oVDNb and
oVDN. Finally, our best PTRL alternative showed an improvement over the non-
PTRL baseline in terms of speed of convergence up to 40 episodes and reward up
to $135\%$. As future work, we intend to generalize PTRL to other cooperative
MARL techniques.

##  VII Acknowledgment

This research is supported by Mitacs Accelerate Program and NetExperience Inc.

## References

  * [1] IEEE 802.11, “Official IEEE 802.11 Working Group Project Timelines.” [Online]. Available: https://www.ieee802.org/11/Reports/802.11_Timelines.htm
  * [2] A. Garcia-Rodriguez, D. Lopez-Perez, L. Galati-Giordano, and G. Geraci, “IEEE 802.11be: Wi-Fi 7 Strikes Back,” _IEEE Communications Magazine_ , 2021.
  * [3] P. E. Iturria-Rivera, H. Zhang, H. Zhou, S. Mollahasani, and M. Erol-Kantarci, “Multi-Agent Team Learning in Virtualized Open Radio Access Networks (O-RAN),” _Sensors_ , vol. 22, no. 14, 2022.
  * [4] P. E. Iturria-Rivera, M. Chenier, B. Herscovici, B. Kantarci, and M. Erol-Kantarci, “Cooperate or not Cooperate: Transfer Learning with Multi-Armed Bandit for Spatial Reuse in Wi-Fi,” 2022. [Online]. Available: https://arxiv.org/abs/2211.15741
  * [5] TIP, “OpenWiFi Release 2.4 GA,” 2022. [Online]. Available: https://openwifi.tip.build/
  * [6] A. Taylor, I. Dusparic, and E. Galván-López, “Transfer learning in multi-agent systems through parallel transfer,” _Proceedings of the 30th International Conference on Machine Learning_ , 2013.
  * [7] A. Taylor, I. Dusparic, M. Gueriau, and S. Clarke, “Parallel Transfer Learning in Multi-Agent Systems: What, when and how to transfer?” in _Proceedings of the International Joint Conference on Neural Networks_ , 2019\.
  * [8] S. Wang, H. Liu, P. H. Gomes, and B. Krishnamachari, “Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networks,” _IEEE Trans. Cogn. Commun. Netw._ , 2018.
  * [9] Y. Kishimoto, X. Wang, and M. Umehira, “Reinforcement learning based joint channel/Subframe selection scheme for fair LTE-WiFi coexistence,” in _Proceedings - 2020 16th International Conference on Mobility, Sensing and Networking, MSN 2020_ , 2020.
  * [10] IEEE P802.11, “TGax Simulation Scenarios,” IEEE, Tech. Rep., 2015. [Online]. Available: https://mentor.ieee.org/802.11/dcn/14/11-14-0980-16-00ax-simulation-scenarios.docx
  * [11] S. Gronauer and K. Diepold, “Multi-agent deep reinforcement learning: a survey,” _Artificial Intelligence Review_ , 2022.
  * [12] C. S. de Witt, T. Gupta, D. Makoviichuk, V. Makoviychuk, P. H. S. Torr, M. Sun, and S. Whiteson, “Is independent learning all you need in the starcraft multi-agent challenge?” 2020. [Online]. Available: https://arxiv.org/abs/2011.09533
  * [13] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” in _Advances in Neural Information Processing Systems_ , 2017.
  * [14] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, and T. Graepel, “Value-decomposition networks for cooperative multi-agent learning based on team reward,” 2018.
  * [15] T. Rashid, G. Farquhar, B. Peng, and S. Whiteson, “Weighted QMIX: Expanding Monotonic Value Function Factorisation,” in _34th Conference on Neural Information Processing Systems (NeurIPS 2020)_ , 2020.
  * [16] T. Rashid, M. Samvelyan, C. S. De Witt, G. Farquhar, J. Foerster, and S. Whiteson, “QMIX: Monotonic value function factorisation for deep multi-agent reinforcement Learning,” in _35th International Conference on Machine Learning, ICML 2018_ , 2018.
  * [17] M. E. Taylor and P. Stone, “Transfer learning for reinforcement learning domains: A survey,” _Journal of Machine Learning Research_ , 2009.
  * [18] Á. López-Raventós and B. Bellalta, “IEEE 802.11be Multi-Link Operation: When the best could be to use only a single interface,” in _19th Mediterranean Communication and Computer Networking Conference (MedComNet)_ , 2021.