History Semantic Graph Enhanced Conversational KBQA
with Temporal Information Modeling

Specifically, we define the history semantic graph to be $\mathcal{G}=<\mathcal{V},\mathcal{E}>$, where $\mathcal{V}=set(e)\cup set(tp)$, $\mathcal{E}=set(p)$, and $e,tp,p$ denote entity, entity type and predicate, respectively. We define the following rules to transform the actions defined in Table 4 to the KG triplets:

• •

  For each element $e_{i}$ in the operator result of $set\rightarrow find(e,p)$, we directly add <$e_{i},p,e$> into the graph.

• •

  For each element $e_{i}$ in the operator result of $set\rightarrow find\_reverse(e,p)$, we directly add <$e,p,e_{i}$> into the graph.

• •

  For each entity $e_{i}\in\mathcal{V}$, we also add the <$e_{i},IsA,tp_{i}$> to the graph, where $tp_{i}$ is the entity type of entity $e_{i}$ extracted from Wikidata knowledge graph.

• •

  For the $find$ and $find\_reverse$ actions that are followed by $filter\_type$ or $filter\_multi\_types$ action for entity filtering, we would add the element in the filtering result to the graph, which prevents introducing unrelated entities into the graph.

It is worth mentioning that we choose to transform these actions because they directly model the relationship between entities and predicates. Besides, as the conversation proceeds and new logical forms are generated, more KG triplets will be added to the graph and the graph will grow larger. However, the number of nodes involved in the graph is still relatively small and is highly controllable by only keeping several recent KG triplets. Considering the $O(N^{2})$ computational complexity of Transformer encoders Vaswani et al. (2017), it would be more computationally efficient to model conversation history using history semantic graph than directly concatenating previous utterances.

Given constructed history semantic graph $\mathcal{G}$, we first initialize the embeddings of nodes and relations using BERT, i.e., $\texttt{BERT}(e_{i}/p_{i})$, where $e_{i}$ and $p_{i}$ represent the text of node and relation, respectively. Then we follow TransformerConv Shi et al. (2020) and update node embeddings as follows:

$$H=\textrm{TransformerConv}(E,\mathcal{G})$$

(1)

where $E\in\mathbb{R}^{(|\mathcal{V}|+|\mathcal{E}|)\times d}$ denotes the embeddings of nodes and relations.

As the conversation continues and further inquiries are raised, individuals tend to focus more on recent entities, which is also called Focal Entity Transition phenomenon Lan and Jiang (2021). To incorporate this insight into the model, we introduce temporal embedding to enable the model to distinguish newly introduced entities. Specifically, given the current turn index $t$ and previous turn index $i$ in which entities appeared, we define two distance calculation methods:

• •

  Absolute Distance: The turn index of the previous turn in which the entities were mentioned, i.e., $D=t$.

• •

  Relative Distance: The difference in turn indices between the current turn and the previous turn in which the entities were mentioned, i.e., $D=t-i$.

For each method, we consider two approaches for representing the distance: unlearnable positional embedding and learnable positional embedding. For unlearnable positional encoding, the computation is defined using the following sinusoid function Vaswani et al. (2017):

$$\left\{\begin{array}[]{l}e_{t}(2i)=sin(D/10000^{2i/d}),\\ e_{t}(2i+1)=cos(D/10000^{2i/d}),\end{array}\right.$$

(2)

where $i$ is the dimension and $D$ is the absolute distance or relative distance.

For learnable positional encoding, the positional encoding is defined as a learnable matrix $E_{t}\in\mathbb{R}^{M\times d}$, where $M$ is the predefined maximum number of turns.

Then we directly add the temporal embedding to obtain temporal-aware node embeddings.

$$\bar{h}_{i}=h_{i}+e_{t},$$

(3)

where $h_{i}$ is the embedding of node $e_{i}$.

As the conversation progresses, user’s intentions may change frequently, which leads to the appearance of intention-unrelated entities in history semantic graph. To address this issue, we introduce token-level and utterance-level aggregation mechanisms that allow the model to dynamically select the most relevant entities. These mechanisms also enable the model to model contextual information at different levels of granularity.

• •

  Token-level Aggregation: For each token $x_{i}$, we propose to attend all the nodes in the history semantic graph to achieve fine-grained modeling at token-level:

  	$\displaystyle x^{t}_{i}$	$\displaystyle=\textrm{MHA}(x_{i},\bar{H},\bar{H}),$		(4)
  	$\displaystyle\bar{x}_{i}$	$\displaystyle=x^{t}_{i}+x_{i},$

  where MHA denotes the multi-head attention mechanism and $\bar{H}$ denotes the embeddings of all nodes in the history semantic graph.

• •

  Utterance-level Aggregation: Sometimes the token itself may not contain semantic information, e.g., stop words. We further propose to incorporate history information at the utterance-level for these tokens:

  	$\displaystyle x^{u}_{i}$	$\displaystyle=\textrm{MHA}(x_{\textrm{[CLS]}},\bar{H},\bar{H}),$		(5)
  	$\displaystyle\bar{x}_{i}$	$\displaystyle=x^{u}_{i}+x_{i},$

  where $x_{\textrm{[CLS]}}$ denotes the representation of the [CLS] token.

Then, history-semantic-aware token embeddings are forwarded as input to the encoder of Transformer Vaswani et al. (2017) for deep interaction:

$\displaystyle h^{(enc)}$

$\displaystyle=\textrm{Encoder}(\bar{X};\theta^{(enc)}),$

(6)

where $\theta^{(enc)}$ are encoder trainable parameters.

The goal of entity detection is to identify mentions of entities in the input. Previous studies Shen et al. (2019) have shown that multiple entities of different types in a large KB may share the same entity text, which is a common phenomenon called Named Entity Ambiguity. To address this issue and inspired by Kacupaj et al. (2021), we adopt a type-aware entity detection approach using BIO sequence tagging. Specifically, the entity detection vocabulary is defined as $V^{(ed)}=\{O,\{B,I\}\times\{TP_{i}\}_{i=1}^{N^{(tp)}}\}$, where $TP_{i}$ denotes the $i$-th entity type label, $N^{(tp)}$ stands for the number of distinct entity types in the knowledge graph and $|V^{(ed)}|=2\times N^{(tp)}+1$. We leverage LSTM Hochreiter and Schmidhuber (1997) to perform the sequence tagging task:

	$\displaystyle h^{(ed)}$	$\displaystyle=\textrm{LeakyReLU}(\textrm{LSTM}(h^{(enc)};\theta^{(l)})),$		(8)
	$\displaystyle p_{t}^{(ed)}$	$\displaystyle=\textrm{Softmax}(W^{(ed)}h_{t}^{(ed)}),$

where $h^{(enc)}$ is the encoder hidden state, $\theta^{(l)}$ are the LSTM trainable parameters, $h_{t}^{(ed)}$ is the LSTM hidden state at time step $t$, and $p_{t}^{(ed)}$ is the probability distribution over $V^{(ed)}$ at time step $t$.

Once we detect the entities in the input utterance, we perform entity linking to link the entities to the entity slots in the predicted logical form. Specifically, we define the entity linking vocabulary as $V^{(el)}=\{0,1,...,M\}$ where $0$ means that the entity does not link to any entity slot in the predicted logical form and $M$ denotes the total number of indices based on the maximum number of entities from all logical forms. The probability distribution is defined as follows:

	$\displaystyle h^{(el)}$	$\displaystyle=\textrm{LeakyReLU}(W^{(el_{1})}[h^{(enc)};h^{(ed)}]),$		(9)
	$\displaystyle p_{t}^{(el)}$	$\displaystyle=\textrm{Softmax}(W^{(el_{2})}h_{t}^{(el)}),$

where $W^{(el_{1})},W^{(el_{2})}$ are trainable parameters, $h_{t}^{(el)}$ is the hidden state at time step $t$, and $p_{t}^{(el)}$ is the probability distribution over the tag indices $V^{(el)}$ at time step $t$.

We conduct experiments on CSQA (Complex Sequential Question Answering) dataset ¹¹1https://amritasaha1812.github.io/CSQA Saha et al. (2018). CSQA was built based on the Wikidata knowledge graph, which consists of 21.1M triples with over 12.8M entities, 3,054 entity types and 567 predicates. CSQA dataset is the largest dataset for conversational KBQA and consists of around 200K dialogues where training set, validation set and testing set contain 153K, 16K and 28K dialogues, respectively. Questions in the dataset are classified as different types, e.g., simple questions, logical reasoning and so on.

To evaluate HSGE, We use the same metrics as employed by the authors of the CSQA dataset as well as the previous baselines. F1 score is used to evaluate the question whose answer is comprised of entities, while Accuracy is used to measure the question whose answer is a number or a boolean number. Following Marion et al. (2021), we don’t report results for “Clarification” question type, as this question type can be accurately modeled with a simple classification task.

We compare HSGE with the latest five baselines that include D2A Guo et al. (2018), S2A+MAML Guo et al. (2019), MaSP Shen et al. (2019), OAT Marion et al. (2021) and LASAGNE Kacupaj et al. (2021).

To show the effectiveness of each component, we create two ablations by directly removing history semantic graph (HSG) and temporal information modeling (TIM), respectively. As shown in Table 2, HSGE outperforms all the ablations across all question types, which verifies the importance of each model component.

It is worth mentioning that after removing HSG, the performance of our method on some question types that require reasoning (i.e., Logical Reasoning, Quantitative Reasoning (Count)) drops significantly. We think that the reason might be the utilization of graph neural network on HSG empowers the model with great reasoning ability, which further benefits model performance.

In context-aware encoder, we design two distance calculation methods (i.e., absolute distance and relative distance) for temporal information modeling, as well as two information aggregation granularities (i.e., token-level and utterance-level aggregation) for semantic information aggregation. To study their effects, we conduct experiments by fixing one setting while changing the other. And the comparison result is shown in Figure 4.

From the results, it is obvious that we can get the following conclusions: (1) Token-level aggregation method performs better than utterance-level aggregation method. This is because the token-level aggregation allows the model to incorporate context information at a finer granularity and the information unrelated to the target token can be removed. (2) Absolute distance method performs better than relative distance method. The reason may be that although both distance calculation methods can provide temporal information, absolute distance is more informative since the model can derive relative distance using absolute distance while the opposite is not true.

One of the most widely used methods for context modeling is to directly concatenate history conversations Liu et al. (2020). To analyze its effectiveness, we remove HSG and observe the performance of seven representative question types using the concatenation of history conversations as input, which is shown in Figure 5.

As we can see, at the initial stages of concatenation turn number increase, the performances on some question types increase a little while remaining unchanged or even decreasing on others, leading to an almost unchanged overall performance. It is reasonable because history turns contain useful semantic information, which leads to performance gain. However, as more conversation turns are introduced into the model, more noisy tokens will also be introduced into the model, which leads to performance degradation. Besides, the introduction of more context tokens will also lead to an increase in computational cost with the $O(N^{2})$ complexity.

It is worth noting that the best setting of concatenation method still performs worse than HSGE. It is mainly because we use attention mechanism to dynamically select the most related entities from the HSG, which achieves effective history modeling while avoiding introducing noisy information. And as we only extract entities and predicates from history conversations, the size of the graph is relatively small and the increase in computational cost as the conversation progresses is marginal.

Entity ambiguity refers to the situation where there exist multiple entities with the same text and type in the Wikidata knowledge graph. For example, we cannot distinguish multiple people called “Mary Johnson” because we have no more information other than entity text and entity type. We believe that incorporating other contextual information such as entity descriptions may help solve this problem Mulang et al. (2020).

We follow Shen et al. (2019); Kacupaj et al. (2021) and produce golden logical forms by leveraging BFS to search valid logical forms for questions in training data. This can sometimes lead to wrong golden actions such as two actions with different semantic information but accidentally sharing the same execution result. This may misguide our model during training.