{'fraction_non_alphanumeric': 0.03363936307559891, 'fraction_numerical': 0.014094104145746664, 'mean_word_length': 4.870526315789474, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DialoKG: Knowledge-Structure Aware Task-Oriented Dialogue Generation

Task-oriented dialogue generation is challenging since the underlying knowledge is often dynamic and effectively incorporating knowledge into the learning process is hard. It is particularly challenging to generate both human-like and informative responses in this setting. Recent research primarily focused on various knowledge distillation methods where the underlying relationship between the facts in a knowledge base is not effectively captured. In this paper, we go one step further and demonstrate how the structural information of a knowledge graph can improve the system's inference capabilities. Specifically, we propose DialoKG, a novel task-oriented dialogue system that effectively incorporates knowledge into a language model. Our proposed system views relational knowledge as a knowledge graph and introduces (1) a structure-aware knowledge embedding technique, and (2) a knowledge graph-weighted attention masking strategy to facilitate the system selecting relevant information during the dialogue generation. An empirical evaluation demonstrates the effectiveness of DialoKG over state-of-the-art methods on several standard benchmark datasets.


Introduction
Traditional task-oriented dialogue systems are designed to achieve specific goals such a restaurant reservation, hotel booking and car navigation. These systems are often empowered by external domain-or task-specific knowledge that enables them to generate informative dialogues (Eric et al., 2017;Qin et al., 2019;He et al., 2020b). The external knowledge in these systems is usually incorporated in the form of structured knowledge triples (Zhou et al., 2018;Liu et al., 2018a) or unstructured documents (Ye et al., 2020;Ghazvininejad et al., 2018). Figure 1 depicts a knowledge-grounded dialogue about reserving a hotel. Recent research primarily concentrated on various knowledge filtering methods for selecting relevant knowledge Kim et al., 2020;. These approaches treat the knowledge triples independently and leverage Pointer Networks and copy mechanisms to generate knowledge-grounded dialogues (Vinyals et al., 2015;Gu et al., 2016;Sukhbaatar et al., 2015;Raghu et al., 2021;Chaudhuri et al., 2021). Typically, these systems generate a template or sketch-response during training and learn to fill in the slots with knowledge graph entries. Such systems face two issues when they try to generate dialogues in a multi-domain setting. Firstly, they are unable to capture the underlying semantics of a knowledge graph, such as the relationship between entity and relation. This leads frequently to in-  correct and inappropriate dialogue generation . Secondly, they lack the ability to encode dynamic knowledge in a multi-domain setting, resulting in noisy dialogues (Madotto et al., 2020). Generally, integrating a knowledge base into the learning process and generating correct and coherent dialogues at the same time is a challenging task.
In this paper, we propose a novel task-oriented dialogue system, named DialoKG that employs structural information of the knowledge graph into a language model (LM) for generating informative dialogues (see Figure 2a). For this purpose, we exploit GPT-2 (Radford et al., 2019) -a language model developed based on a stack of Transformer decoders (Vaswani et al., 2017). Specifically, we introduce a novel structure-aware multiple embedding layer-based knowledge embedding technique that constructively embeds the underlying relationship between the knowledge triples . DialoKG interprets the knowledge as a knowledge graph; therefore, separate embedding layers for word token, entity, triple and token type enable the system to capture the graph features (e.g., subject, relation and object). This enables the system to generate correct and human-like dialogues and prevents generating erroneous responses such as "4 miles is located at 792 Bedoin Street Starbucks away". Furthermore, the ability to correctly capture the relationship in the knowledge graph eliminates the need for template-based or sketch-based response generation.
In order to guide the decoder on relevant parts of the knowledge graph, we propose a new knowledge attention masking method. For constructing the knowledge attention mask, in each dialogue turn, a weighted graph is computed in two steps: 1) Entity weights are computed using a pre-trained language model that estimates the importance of an entity for the given utterance, and 2) relation weights are computed based on the concept of graph convolution networks (GCN) (Kipf and Welling, 2017). Both steps take the user utterance into consideration, i.e., the obtained weighted graph is question specific. A set of triples is then selected based on the most relevant entities and relations of the weighted graph to construct a knowledge attention mask for the language model. This allows the masked language model to focus on relevant graph triples. We hypothesise that this leads to the generation of more accurate responses and enhance the model's capabilities of understanding the domain and task.
To assess the performance of DialoKG, we conduct experiments on three public benchmarks: SMD (Eric et al., 2017), CamRest (Wen et al., 2017) and Multi-WOZ 2.1 (Budzianowski et al., 2018). We evaluate the system generated responses using both human and automatic metrics. Furthermore, we analyse impact of the individual components on the overall performance to verify the effectiveness. Our experimental results show that DialoKG outperforms state-of-the-art models in knowledge-grounded dialogue generation and can generate human-like responses. We made our code publicly available 1 .

Problem Definition
DialoKG aims to generate informative responses given a dialogue history, a question and a knowledge base. We define the dialogue history H as a set of turns between two speakers, such that H = {U 1 , S 1 , .., U t , S t }, where U i and S i are the sequences of words in turn i. We assume that the knowledge is stored in a multi-relational knowledge graph G. Here, G is a set of triples T such that T ⊆ E × R × E, where E is the set of entities and R the set of relations. A triple T ∈ G is denoted as (s, r, o) in which s ∈ E and o ∈ E denote the subject and object entities, respectively, and r ∈ R is the relation between them. We use the terms "Knowledge Graph" and "Graph" interchangeably throughout this paper. Furthermore, we denote the user utterance of the current dialogue turn as Q. A GPT-2 (Radford et al., 2019) language model is used in this paper to generate responses. However, any Transformer decoder-based LM can be used. Formally, the probability distribution of generating a response by the language model is defined as: Here, S t is the generated response in turn t and n is the maximum length of the generated response.

Knowledge and Dialogue Embedding
DialoKG takes a knowledge graph G, dialogue history H, and the current user utterance Q together as input and constructs a single input sequence as depicted in Figure 3. The first part of the sequence contains graph related information (i.e., subject, relation, and object) and the latter part dialogue specific information such as dialogue history (H) and the current user utterance (Q). Knowledge Specific Embedding. To infuse structural information, DialoKG employs entity embedding, triple embedding and type embedding, besides the usual word token and positional embedding. Such an embedding technique allows the system to encode the knowledge graph structure. To do this, knowledge graph triples are linearized into a sequence as input, as depicted in Figure 3. To facilitate order invariance of the knowledge embedding, we shuffle the order of the graph triples in the input sequence during training. In the token embedding layer [S], [R] and [O] are special tokens to separate subject, relation and object of a triple from each other in the sequence. Entity and triple embedding layers embed entity and triple-level information of the word token. For instance, ENT1 in the entity embedding layer indicates that the corresponding words in the token embedding layer are related to the first subject, which is starbucks in this case. Likewise, T1 and T2 in the triple embedding layer indicate that the corresponding words in the token embedding layer are related to the first and second triple, respectively. Finally, the type embedding indicates that the corresponding tokens are from the knowledge graph as opposed to the dialogue history.
Dialogue Specific Embedding. The dialogue specific part of the input sequence is separated from the knowledge specific part by a [SEP] token in the token embedding layer. Furthermore, the user utterance/question (Q) of the current turn is separated by a [Q] token from the dialogue history. The type embedding layer stores information about whether the corresponding utterance is from the user or system. This way, the decoder can use information about typical dialogue turn patterns.  normalizes the embedding representation of layers, which restricts the weights of the learning network from exploding.
We argue that the proposed design pattern of forming a single sequence and specifying each item in the input sequence further with additional embedding layers can improve the system's understanding of the task and domain.

Knowledge Attention Mask Construction
To notify the decoder about the relevant KG triples for answering the current user question, a knowledge graph weighted-attention mask is constructed. Prior to the construction of the knowledge attention mask, a weighted-knowledge graph, G w is first computed by a Graph Weight Computer module, where the entity and relation weights are computed independently. We discuss the components of the Graph Weight Computer module below.
Entity Weight Estimator. A pre-trained language model RoBERTa , is used to compute the entity weights, similar to (Yasunaga et al., 2021). Each entity E i ∈ E of graph G is concatenated with the user utterance Q to obtain the probability score from the language model.
In Equation 2, LM head • LM enc represents the probability of the entity E i computed by the language model. We consider E iw as the weight of the entity E i , which represents the relevance of the entity for the given user utterance Q.
Relation Weight Estimator. We follow (Kipf and Welling, 2017;Vashishth et al., 2019) and leverage the concept of GCN to obtain the relation weight. In contrast to the previous works, our proposed relation weight estimator transforms the input graph into an undirected graph, where the relations are considered as nodes of a graph. This transformation technique allows the relation estimator to obtain a score for each relation. The graph transformation is demonstrated in Figure 4a. The relation weight is computed as follows: Here, D −1 (A + I) computes the row-normalized adjacency matrix, where D and A are respectively the degree matrix and adjacency matrix of the graph G as depicted in Figure 4b and I is the identity matrix. Let d g = |E| + |R| be the total number of entities and relations in the graph G, then D, A, I ∈ R dg×dg . A feature vector X ∈ R dg×1 is obtained by computing the cosine similarity between the embedding of knowledge graph entries (entities and relations) and the embedding of question. Furthermore, a relation mask M r ∈ R dg×1 is constructed by setting a value of 1 and 0 to the positions that correspond to relations and entities, respectively, to attend to the values that correspond to the relations only. Finally, values that correspond to the entities inĤ are masked out by multiplying with M r to obtain final relation weights R w ∈ R dg×dg . The computed weighted-graph assists the model to focus on the task by constructing a knowledge attention mask. We use the normalized score of R w and E w for constructing the knowledge attention mask. To filter-out irrelevant knowledge triples, we obtain the top-k entities and relations from the weighted graph as denoted asÊ andR respectively. Here, k is a hyper-parameter which we chose from a range of [0, max(|E|, |R|)], based on the validation score. Finally, based on the selectedÊ andR, the knowledge attention mask is constructed as follows: Here r i , s i and o i corresponds to the relation, subject and object entity of triple T i . Any position that corresponds to the value of −∞ results in 0 after computing the softmax during the attention computation (discussed in the next sub-section). The final mask M ∈ R n×n is obtained by appending the mask for the dialogue related sequence with the knowledge attention mask where n is sequence length. Padding is added to adjust the dimension of the metrics.

Decoder
A Transformer (Vaswani et al., 2017) based GPT-2 (Radford et al., 2019) model is used for generating the response. The attention, computed in each of GPT-2's heads is formalized as follows: where, Attn(·) computes the masked attention, H i is the i-th head, d k =d m /h. Here, d m is the dimension of the model where h the number of heads. Q, K and V are query, key and value where The objective of the model is to minimize the negative log-likelihood L for next-token prediction. For a dialogue dataset D = {D 1 , D 2 , ..., D j }, we formally define L as follows: where n is the maximum response length and H j , Q j , G j ∈ D j . Top-k sampling (Fan et al., 2018) decoding is used to generate the next word token at each time step, during the inference.

Data
We evaluate DialoKG on three publicly available knowledge-grounded and task-oriented dialogue datasets: Stanford Multi-Domain dataset (SMD) (Eric et al., 2017), Cam-Rest (Wen et al., 2017) and Multi-WOZ 2.1 (MWOZ) (Budzianowski et al., 2018). SMD consists of three domains: weather, navigation, and calendar. MWOZ contains five domains: train, hotel, restaurant, taxi and attraction. We use the splits provided with the datasets for train, validation, and test. Each dialogue is provided with a knowledge base. Table 1 shows the statistics of the benchmark datasets.

Hyper-parameter Settings
Throughout this paper, we use the GPT-2 (Radford et al., 2019) model with 117M parameters. AdamW (Loshchilov and Hutter, 2019) with = 1e-8 and learning rate of 6.25e-5 is employed as optimizer. GELU (Hendrycks and Gimpel, 2016) is used as activation function. The best hyperparameters for each dataset were found using grid search and based on the results on the validation set. We run all experiments on a distributed training setting with 10 GPUs, each with 12 GB of memory. More implementation details can be found in Appendix A.

Evaluation Metrics
Automatic Metrics. Following the baseline models, we use BLEU (Papineni et al., 2002) and Entity F1 score (Eric et al., 2017) as automatic evaluation metrics. The Entity F1 score represents the model's capability of generating knowledge grounded responses. It computes the F1 score between the set of entities present in the ground truth and system-generated responses. Several studies (Novikova et al., 2017;Liu et al., 2016) on evaluation metrics suggest that word-overlap based metrics such as BLEU are insufficient for evaluating natural language generation (NLG) systems. Hence, we use MoverScore (Zhao et al., 2019)   addition metric to evaluate the semantic similarity between the system generated response and the ground truth. We compute both MoverScore and BLEU scores on the sentence level.

Human Evaluation.
To assess the quality of the system-generated responses, we conduct a human evaluation based on the following criteria: 1) Naturalness: how human-like and fluent the generated responses are, and 2) Correctness: how correct the knowledge-grounded responses are. We asked three annotators (two from Computer Science (CS) and one from a non-CS background) who are not part of this research work to evaluate the quality of the system-generated responses. We randomly sampled 90 dialogues in total from the benchmark datasets and asked annotators to evaluate the system-generated responses given the ground truth response and the knowledge graph triples on a scale of [1,5] (higher is better). The inter-annotator agreement score (Cohen's kappa κ) of the annotated data is 0.82. The human evaluation process is explained in detail in Appendix D.

Baselines
We compare DialoKG with the following state-of-the-art methods: GLMP (

Quantitative Results
We conduct both quantitative and qualitative analyses to assess system-generated responses. Table 2 summarizes the performance of DialoKG with respect to the baseline models. It is evident that DialoKG outperforms the baseline models significantly in Entity F1 score on CamRest, which contains mostly knowledge-grounded dialogues about restaurant reservations. A high Entity F1 score of 75.6 on CamRest shows DialoKG's ability to generate knowledge-grounded with high accuracy. Although DialoKG achieves an improved Entity F1 score on the MWOZ dataset, it has a lower BLEU score since MWOZ often contains lengthy responses. However, the high MoverScore across all datasets demonstrates that DialoKG can generate highly semantically similar responses. Domainwise results are reported in Appendix B due to space limitation.

Qualitative Results
We obtain human evaluation scores (naturalness and correctness) for the closest three models. Re-

Model Naturalness Correctness
EER (He et al., 2020c) 3.27 3.61 FG2Seq (He et al., 2020b) 3.33 3.87 CDNet (Raghu et al., 2021) 3.53 3.94 DialoKG 4.33 4.01  sults in Table 3 show that our proposed dialogue system can generate more human-like responses. An improved score is also achieved in terms of correctness, reflecting DialoKG's ability to generate highly accurate dialogues. Furthermore, Figure 5 shows the distribution of human evaluation scores. The figure allows a better direct comparison of the individual score levels. Details about the annotation process are reported in Appendix D.

Ablation Study
We conducted an ablation study to investigate the contribution of major components of DialoKG. The results on CamRest in Table 4 demonstrates that the ses2seq approach achieves the lowest scores, which represents the DialoKG model without the embedding layers: entity embedding, triple embedding, and type embedding. Inclusion of the entity and triple embedding layers significantly improved model's performance in both BLEU and Entity F1 scores. The type embedding further improved Di-aloKG's performance. The significant difference in results shows the effectiveness of the proposed embedding technique. Finally, we observed a remarkable improvement in DialoKG's overall performance after the inclusion of knowledge attention mask. Question-aware weighted-graph computation used to construct knowledge attention mask, helped the model focus on the task at the inference time.

Effectiveness of Knowledge Embedding
The proposed graph embedding technique works best in combination with the knowledge attention mask. The graph embedding design allows DialoKG to handle disconnected graphs and  triples. This makes DialoKG suitable for largescale graphs, where a cosine-similarity based triple selection may be used to fit the graph triples inside the model's input capacity. The entity and triple embedding layers allow the model to preserve the structural information of a particular triple even though triples from different parts of the input sequence are selected based on the top-k entities and relations to construct the knowledge attention mask. Overall, the graph embedding technique improves the Entity F1 score by 5.4, 9.0, and 3.7 points on SMD, CamRest, and MWOZ, respectively. This indicates the effectiveness of the proposed embedding techniques for capturing graph triples.

Impact of Knowledge Attention Mask
To understand the effect of the knowledge-graph weighted attention mask, we experiment with the triple selection process described in DialoKG's approach. Table 5 shows the performance of Di-aloKG with selected top-k entities and relations on the SMD dataset. We observe that DialoKG achieves the best performance on SMD when the top 7 entities and relations are chosen to construct the knowledge mask. Consider the question "Do you have any local coffee shops?" the ground truth is "There is Coupa, it s just 6 miles away but there is heavy traffic on our way". The ground truth contains traffic information in addition to the distance and name of the coffee shop. Selecting a high number of entities and relations increases the chance of generating such additional information related to the subject of the question. However, choosing too many entities harms the model since it is more likely to add irrelevant noise (see Table 5). For MWOZ, six entities and seven relations, and for CamRest, seven entities and five relations result in the best performance.
5 Case Study Figure 6 shows two cases from the MWOZ dataset given a subset of the knowledge graph. In Case Figure 6: Case study: comparison between ground truth and system-generated responses.
1, we observe that in answering the user question, DialoKG correctly picked Rice House that serves cheap and Chinese food. However, in this case, multiple correct answers exist, e.g. Charlie Chan also falls into the same category of restaurant. Despite generating the correct answer based on the given knowledge and the user question, DialoKG receives a low Entity F1 score since the generated response entity does not match the ground truth. In Case 2, where the baseline systems focus on imitating the ground truth, DialoKG generates a fluent and engaging response. Despite generating a meaningful and semantically similar sentence, it obtained a BLEU score of 0.0 because of the low overlap with the ground truth response. However, a high MoverScore in both cases indicates DialoKG's ability to generate a semantically similar response.
Overall, we observe that DialoKG can generate human-like, engaging, and informative responses in a multi-turn dialogue setting.

Influence of Dialogue History
Dialogue history is particularly crucial since it gives the model the context for generating the response. In some cases where the entity information is missing in the current user utterance, the dialogue context provides the model with enough information to perform the inference and generate the correct response. For instance, for the question, What is the food type they serve?, the name of the restaurant is not given in the question, but the system can infer it from the dialogue history. However, from the experiments, we found that too much dialogue context may inject noisy and irrelevant information to answer the current question, in particular for knowledge-grounded responses in MWOZ. To quantify this, we selected different numbers of dialogue turns as history for the model's input depending on the characteristics of the dataset and visualised the result in Figure 7.

Related Work
Task-Oriented Dialogue Systems. Recent dialogue systems mainly leverage Memory Pointer Networks (Sukhbaatar et al., 2015;Madotto et al., 2018;, Copy mechanisms (Gu et al., 2016;Chaudhuri et al., 2019) and similarity-based knowledge distillation techniques Raghu et al., 2021) for the knowledge selection and dialogue generation task. In this research direction, learning to generate template responses and fill in the slot is a common practice . Dialogue history and knowledge entities are stored in shared memory, facilitating these systems to apply copy mechanisms over the memory space. A multi-level memory architecture is proposed by (Gangi Reddy et al., 2019) that handles the dialogue history and knowledge entries separately.
Knowledge-Structure Aware Dialogue Generation. Recently, several knowledge-grounded dialogue systems have attempted to capture structural knowledge to improve the performance of dialogue generation. A sequence-to-sequence model is proposed by (Liu et al., 2018b) that employs global and local attention to understand structural information. Several studies found GCN to be effective for modeling graph-based data. Hence, they construct a graph from a document (Moghe et al., 2020) or the interaction between two speakers  for generating informative dialogues. In a different approach, an enhanced entity representation is proposed by (He et al., 2020c) by considering the entity information and the structural and relational information of the knowledge entries. In contrast to the previous works, our proposed approach represents the graph's structural information such as entities and triples through multiple embedding layers.

Language Model Based Dialogue Generation.
Pre-training a language model with dialogue datasets Bao et al., 2020;Gu et al., 2021) and fine-tuning an already pre-trained model for various dialogue-related sub-tasks such as dialogue state tracking, action decision and response generation (Hosseini-Asl et al., 2020;Wu et al., 2020a;Galetzka et al., 2021) has received much attention in recent years. Recently, (Madotto et al., 2020) proposed a new method to embed the knowledge into the language model parameters. However, the authors noticed that the generated dialogues are sometimes noisy and requires high fine-tuning costs. Despite the success of language model-based approaches, integrating structured knowledge into the dialogue generation process remains a challenging task. Unlike the previous approaches, we designed a structure-aware embedding method and exploit GPT-2 to generate dialogues.

Conclusion
We have presented DialoKG, a novel knowledgegrounded task-oriented dialogue system improving the state-of-the-art across multiple benchmark datasets. DialoKG focuses on capturing the underlying semantics of the knowledge graph and pays attention to the relevant graph triples to understand the task and generate correct and human-like responses. The key contributions of DialoKG include 1) Knowledge embedding technique, that embeds the structural information of a knowledge graph effectively, and 2) Knowledge graphweighted attention masking, which guides the masked language model to attend to the relevant knowledge entries for generating correct and informative responses. Finally, we showed DialoKG's ability to generate accurate, diverse, and humanlike dialogues through quantitative and qualitative analysis. We performed an ablation study and studied the effect of dialogue history, knowledge embedding and knowledge attention masking. Top entities 7 5 7 Epochs 40 25 30 For both training and evaluation, we use a batch size of 4. Hyper-parameters used during the inference are reported in Table 7. We used 12 NVIDIA TitanX GPUs, each with 12GB of memory to train models. It took 30, 18 and 45 minutes to train on SMD, CamRest and MWOZ data.

B Results
We report the domain-wise results for SMD and MWOZ in Table 8 and Table 9 respectively. Baseline model's results are reported from (Raghu et al., 2021) and (Madotto et al., 2020 Figure 9 shows the interface of the annotation tool used to obtain human annotation scores. The interface displays a set of knowledge triples, a user utterance, the ground truth response, and a systemgenerated response for each point. Given the information displayed on the annotation tool, we asked the annotators to rate the system-generated responses against the ground-truth on a scale of [1,5] (higher is better). We explained the participants about the purpose of this research. The first two participants are male (over 30 years old), and the third participant is female (more than 35 years old), both with several years of experience in the domain.

E Example System Outputs
We show conversations performed by DialoKG on SMD and MWOZ 2.1 dataset in Figure 10 and Figure 11, respectively. The example conversations demonstrate that DialoKG can perform accurate and engaging conversations.