Human conversations naturally evolve around related entities and connected concepts, while may also shift from topic to topic. This paper presents ConceptFlow, which leverages commonsense knowledge graphs to explicitly model such conversation flows for better conversation response generation. ConceptFlow grounds the conversation inputs to the latent concept space and represents the potential conversation flow as a concept flow along the commonsense relations. The concept is guided by a graph attention mechanism that models the possibility of the conversation evolving towards different concepts. The conversation response is then decoded using the encodings of both utterance texts and concept flows, integrating the learned conversation structure in the concept space. Our experiments on Reddit conversations demonstrate the advantage of ConceptFlow over previous commonsense aware dialog models and fine-tuned GPT-2 models, while using much fewer parameters but with explicit modeling of conversation structures. The rapid advancements of language modeling and natural language generation (NLG) techniques have enabled fully data-driven conversation models, which take user inputs (utterances) and directly generate natural language responses (Shang et al., 2015; Vinyals & Le, 2015; . On the other hand, the current generation models may still degenerate dull and repetitive contents (Holtzman et al., 2019; Welleck et al., 2019) , which, in conversation assistants, lead to irrelevant, off-topic, and non-useful responses that would damage user experiences (Tang et al., 2019; Zhang et al., 2018; Gao et al., 2019) . A promising way to address this degeneration challenge is to model conversations with the help of knowledge, for example, open-domain knowledge graph (Ghazvininejad et al., 2018) , commonsense knowledge base (Zhou et al., 2018a) , or background documents (Zhou et al., 2018b) . Recent research leverages these prior knowledge by grounding the conversation utterances to the external knowledge and integrating them as additional semantic representations; then response can be generated by conditioning on both the text inputs and the grounded semantics (Ghazvininejad et al., 2018; Zhou et al., 2018a; b) . Integrating external knowledge as a semantic representation of the utterance and an additional input to the conversation model effectively improves the quality of generated responses (Ghazvininejad et al., 2018; Logan et al., 2019; Zhou et al., 2018a) . On the other hand, human conversations do not stay still on the same set of grounded semantics; instead, our dialog dynamically flows in the semantic space: we shift our discussions from one concept to another, chat about a group of related entities, and may switch dialog topics entirely (Fang et al., 2018) . Limiting the usages of knowledge only to the grounded ones, effective as they are, does not leverage semantics' full potential in modeling human conversations. This work presents ConceptFlow, (Conversation generation with Concept Flow), which leverages the commonsense knowledge graph to model the conversation flow in the latent concept space. Given a conversation utterance, ConceptFlow starts from the grounded knowledge, which in our case are the commonsense concepts appearing in the utterance, and extends to multi-hop concepts along the commonsense relations. Then the conversation flow is modeled in the extended concept graph using a new fine-grained graph attention mechanism, which learns to encode the concepts using central or outer graph. Mimicking the development conversation topic flow, the graph attentions guild the concept flow by attending on different directions in the concept flow. The encoded latent concept flow is integrated to the response generation with standard conditional language models: during decoding, each token, word or concept, is sampled from ConceptFlow's context vector, which combines the encodings of the utterance texts and the latent concept flow. This enables ConceptFlow to explicitly model the conversation structure when generating responses. Our experiments on a Reddit conversation dataset (Zhou et al., 2018a ) and a commonsense knowledge graph, ConceptNet (Speer & Havasi, 2012) , demonstrate the advantage of ConceptFlow. In both automatic and human evaluation, ConceptFlow performs significantly better than various seq2seq based generation models (Sutskever et al., 2014) , as well as previous methods that also leverage commonsense knowledge graph but as static memories (Zhou et al., 2018a; Ghazvininejad et al., 2018; Zhu et al., 2017) . Notably, ConceptFlow also outperforms two fine-tuned GPT-2 systems (Radford et al., 2019) , despite using much fewer parameters-Effective modeling of conversation structure can reduce the need of large parameter space. We also provide extensive analyses and case studies to investigate the advantage of modeling conversation flow in the latent concept graph. Our analyses show that many of Reddit discussions are naturally aligned with the paths in the commonsense knowledge graph; expanding the latent concept graph multiple hops away from the initial grounded concepts significantly improves the coverage on the ground truth response. Our ablation study further confirms the effectiveness of our graph attention mechanism in selecting useful latent concepts and concepts appearing in golden responses, which help generate more relevant, informative, and less repetitive responses. This section presents our Conversation generation with latent Concept Flow (ConceptFlow). As shown in Figure 1 , the ConceptFlow models the conversation flow along commonsense relations between concepts to generate meaningful responses. Given a user utterance X = {x 1 , ..., x m } with m words, conversation generation models often use an encoder-decoder architecture to generate a response Y = {y 1 , ..., y n }. Typically, the encoder represents the user utterance X as a representation set H = { h 1 , ..., h m }. This is often done with a Gated Recurrent Unit (GRU): where the x i is the embedding of word x i . The decoder generates t-th response word according to the previous t − 1 generated words y <t = {y 1 , ..., y t−1 } and the user utterance X: The t-th token y t is generated according to the t-step decoder context representation s t : where c t−1 is the context embedding of t − 1-th time, y t−1 is the t − 1-th generated word embedding and s t−1 is the decoder output representation of t − 1-th time. This part introduces the flow concept candidate construction, the latent concept flow encoding, and the conditional conversation decoder to generate response. ConceptFlow constructs a latent concept graph G for knowledge grounded conversation generation. The latent concept graph G starts from the grounded concepts (zero-hop concepts G 0 ), which appear in the conversation utterance and grounded by entity linking. Besides the grounded concepts, ConceptFlow grows zero-hop concepts G 0 with one-hop concepts G 1 and two-hop concepts G 2 . G 0 and G 1 form the central concept graph G central , which is closely related to the current conversation topic. G 1 and G 2 construct an outer concept graph G outer , which models outer conversation flow. Latent concept flow consists of related concepts that can help understand the conversation. Next, we model conversation flow from zero-hop concepts, to one-hop concepts and then to two-hop concepts. This part describes the latent concept flow encoding of central flow concepts and outer flow concepts. Central Flow Encoding. The central flow concept models the concept flow from zero-hop concepts to one-hop concepts using the interactions between zero-hops and one-hops. A multi-layer Graph Neural Network (GNN) (Sun et al., 2018 ) is used to encode concept e ∈ G central in central concept graph. The l-th layer representation e l i of concept e i is calculated by a single-layer feed-forward network (FFN) over three states: where • is the concatenate operator. e l−1 j represents the concept e j 's representation of (l − 1)-th layer. p l−1 represents user utterance representation of (l − 1)-th layer. The l-th layer user utterance representation is updated with the grounded concepts G 0 : The f ej −>ei r ( e l−1 j ) aggregates the concept semantics of the relation r specific neighbor concept e j . It uses attention weight α ej r to control concept flow from e i : where • is the concatenate operator and r is the relation embedding of r. The attention weight α ej r is computed over all concept e i 's neighbor concepts according to the relation weight score and the Page Rank score (Sun et al., 2018) : where PageRank(e l−1 j ) is the page rank score to control propagation of embeddings along paths starting from e i (Sun et al., 2018) and p l−1 is the (l − 1)-th layer user utterance representation. The 0-th layer concept representation e 0 for concept e is initialized with the pre-trained concept embedding e and the 0-th layer user utterance representation p 0 is initialized with the m-th hidden state h m from the user utterance representation set H. The result GNN encodings establishes the central concept flow between zero-hop and one-hop concepts using attentions. Outer Flow Encoding. The outer flow models the concept flow from one-hop concepts to two-hop concepts. Given a concept e i from the one-hop concepts G 1 , all neighbor concepts e k ∈ G 2 are weighted to form the subflow g ei 's representation g ei : where • is the concatenate operator. The e i and e k are embeddings for e i and e k , respectively. The attention score β e k is calculated to weight and aggregate concept triple (e i , r, e k ) to get g ei : where r is the relation between the concept e i and its neighbor concept e k . The w r , w h and w t are learnable parameters. The outer concept flow models more diverse developments of the conversation and guides the flow with the subgraph encoding to more possible directions. This part presents how to generate the response Y using the latent concept flow. Context Representation with ConceptFlow. The t-th time output representation s t of decoder is calculated by updating the t − 1-th step output representation s t−1 with context representations: where y t−1 is the t−1-th step generated token y t−1 's embedding. The context representation c t−1 is the concatenation of the text-based representation c text t−1 and the concept-based context representation c c text t−1 reads the user utterance representations H with the attention score a j t−1 (Bahdanau et al., 2014) : where the attention a j t−1 weights over user utterance representations: The concept-based representation c is a combination of central concept flow encodings and outer flow encodings: where the attention b ei t−1 weights over central concept representations: The attention z g t−1 weights over outer flow representations: Generating Words and Concepts. The conversation generator utilizes the t-th time output representation s t to decode t-th words in response from the word vocabulary and the concept vocabulary: where w is the word embedding for word w, e i is the central concept representation for concept e i and e k is the two-hop concept e k 's embedding. The generation probability of word w is calculated over word vocabulary. The generation probability of concept is separated into two parts: central concept e i 's probability over G 0,1 and outer concept over G 2 . The σ * is a gate used to control the token generation from these three probability distributions: to choose words (σ * = 0), central concepts (σ * = 1) and outer concepts (σ * = 2) when generating the response. Then we minimize the cross entropy loss L and optimize all parameters end-to-end: where the y * t is the ground truth tokens for words or concepts. Metrics. A wide range of evaluation metrics are included from three evaluating aspects: relevance, diversity and novelty. PPL (Serban et al., 2016) , Bleu (Papineni et al., 2002) , Nist (Doddington, 2002) , ROUGE (Lin, 2004) and Meteor (Lavie & Agarwal, 2007) are used for relevance and repetitiveness; Dist-1, Dist-2 and Ent-4 are used for diversity, which is same with the previous work Zhang et al., 2018) . Zhou et al. (2018a) 's concept PPL favors concept grounded models and is reported in Appendix A.1. The Precision, Recall and F1 Score to generate golden concepts (those appear in the ground truth response) are used to evaluate the quality of learned latent concept flow. Baselines. Six baselines are compared in our experiments. Seq2Seq (Sutskever et al., 2014 ) is the basic encoder-decoder for the language generation task. MemNet (Ghazvininejad et al., 2018) and CopyNet (Zhu et al., 2017 ) utilize extra knowledge in two different ways: maintain a memory to store and read concepts; copy concepts for the response generation. Both MemNet and CopyNet provide solutions to store and incorporate knowledge for conversation generation. The Commonsense Knowledge Aware Conversation Generation Model (CCM) (Zhou et al., 2018a ) leverages a graph attention mechanism to model local graphs, which further considers the graph structure for the improvement. The three models above use grounded graph as still knowledge and do not explicitly model conversation flow. GPT-2 (Radford et al., 2019) , the pre-trained model that achieves the state-of-the-art in lots of language generation tasks, is also compared in experiment. We fine-tune the 124M GPT-2 in two ways: concatenate all conversations together and train like a language model (GPT-2 (lang)); extend the GPT-2 model with encode-decoder architecture and supervised with response data (GPT-2 (conv)). Implement Details. The zero-hop concepts are initialized by matching the keywords in post to concepts in ConceptNet, the same with CCM (Zhou et al., 2018a) . Then zero-hop concepts are extended to their neighbors to form central concept graph. The outer concept flow usually contains lots of noise because of the large number of two-hop concepts. To select more related concepts for the conversation generation to reduce the computation cost, ConceptFlow first randomly selects 10% training data to train an initial version. Then we use the initial version's learned graph attention to select the top-100 two-hop concepts on all the rest data, and then conduct standard train, develop, and test process with the pruned graph. More details of this concept selection step can be found in Appendix C. TransE (Bordes et al., 2013) embedding and Glove (Pennington et al., 2014) embedding are used to initialize the representation of concepts and words, respectively. Adam optimizer with learning rate of 0.0001 is used to train the model. This section presents the quality of generated responses from the ConceptFlow, the ablation study for the roles of different modules, and case studies to evaluate the ConceptFlow. Automatic Evaluation. The relevance, diversity, and novelty of generated responses with different evaluation metrics are presented in Table 1 and Table 2 . In Table 1 , all the evaluation metrics compare the relevance between the generated response and the golden response. Our model outperforms all previous models by large margins. Responses generated by our model are on-topic and cover more necessary information. In Table 2 , Dist-1, Dist-2, and Ent-4 measure the word diversity of generated response, whereas the rest of metrics measure the repetitiveness comparing to the user utterance to avoid dull copying the input. Our model also presents a convincing balance to generate novel and diverse responses. GPT-2 (lang) performs more diversely, but ConceptFlow performs more novelty and more on-topic than both GPT-2 versions, perhaps due to its different decoding strategy. Human Evaluation. The human evaluation mainly focuses on two testing scenarios: appropriateness and informativeness, which are important for conversation systems. Appropriateness indicates if the response is on-topic for the given utterance. Informativeness indicates the ability to provide new information instead of copying from the utterance (Zhou et al., 2018a) . All responses of sampled 100 case are selected from four best methods: CCM, GPT-2 (conv), ConceptFlow and Golden Response. The responses are scored from 1 to 4 by five judges. The model performance is listed in Table 3 . The human evaluation is divided into two parts: Average Score and Best@1 ratio, where Best@1 ratio indicates the fraction of judges consider the corresponding response as the best. ConceptFlow outperforms all baseline models on all scenarios. This convincing result demonstrates the advantage of explicitly modeling conversation flow with semantics: ConceptFlow outperforms GPT-2 with one-third parameters. More details of human evaluation are presented in Appendix D. This part studies the effectiveness of the learned latent ConceptFlow. Figure 2 shows golden concept coverage, effectiveness for golden concept selection and perplexity of response generation of four different strategies to select latent concepts. Base only considers central concept graph. Random, Gold, and Full add two-hop concepts in three different ways: Random selects concepts randomly, Gold selects all golden concepts with random negatives, and Full is our method that selects by learned graph attentions. As shown in Figure 2 (a), Random has almost the same coverage with Base, while ConceptFlow (Full) performs better than Random by a large scale. This confirms the concept selection in ConceptFlow effectively selects more meaningful outer concepts for conversation generation. Then the effectiveness of two-hop concept selection strategies is presented in Figure 2 (b). Full outperforms all models with Precision, Recall and F1. The ConceptFlow filters unrelated concepts and chooses underlying concepts to enhance the central graph understanding. The high-quality latent concept flow leads to ConceptFlow's advanced performances in Figure 2 (c). Interestingly, ConceptFlow even outperforms Gold in Perplexity, even Gold includes all two-hop concepts from the golden response. This shows that the "negatives" selected by ConceptFlow, even not directly appear in the target response, are also only topic and related, thus provide more meaningful information than Gold's random negatives. More results are presented in Appendix A.2. Natural language generation (NLG) has achieved promising results with the sequence-to-sequence model (Sutskever et al., 2014) and helped build end-to-end conversation systems (Shang et al., 2015; Vinyals & Le, 2015; . Recently, pre-trained language models, such as ELMO (Devlin et al., 2019) , BERT (Peters et al., 2018) and GPT-2 (Radford et al., 2016) , further improve the NLG performance with large-scale unlabeled data. Nevertheless, the degenerating irrelevant, off-topic, and non-useful response is still one of the main challenges in conversational generation (Tang et al., 2019; Zhang et al., 2018; Gao et al., 2019) . Some work focuses on conversation generation with unstructured texts (Ghazvininejad et al., 2018; Vougiouklis et al., 2016; Xu et al., 2016; Long et al., 2017) , while others extract knowledge with Convolutional Neural Network (CNN) (Long et al., 2017) or store knowledge with memory network (Ghazvininejad et al., 2018) to generate better conversation response. The structured knowledge graphs include rich semantics about concepts and relations. Lots of previous studies focus on domain-targeted dialog system based on domain-specific knowledge base Zhu et al., 2017; Gu et al., 2016) . To generate the response with a large-scale commonsense knowledge base, Zhou et al. (2018a) and Liu et al. (2018) utilize graph attention and knowledge diffusion to select knowledge semantics for better user post understanding and response generation. Different from previous research, ConceptFlow models the conversation flow explicitly with the commonsense graph and presents a novel attention mechanism using Graph Neural Network to guide the conversation flow in the latent concept spaces. In this paper, we present ConceptFlow, which models the conversation flow explicitly as transitions in the latent concept space in order to generate more meaningful responses. Our experiments on the Reddit conversation dataset illustrate the advantages of ConceptFlow over previous conversational systems that also use prior knowledge, as well as our fine-tuned GPT-2 systems, though the latter uses much more parameters. Our studies confirm the source of this advantage mainly derive from the high quality and high coverage latent concept flow, which is effectively captured by ConceptFlow's graph attentions. Our human evaluation demonstrates that ConceptFlow generates more appropriate and informative responses by explicit modeling of the latent conversation structure. Wenya Zhu, Kaixiang Mo, Yu Zhang, Zhangbin Zhu, Xuezheng Peng, and Qiang Yang. Flexible end-to-end dialogue system for knowledge grounded conversation. arXiv preprint arXiv:1709.04264, 2017. A SUPPLEMENTARY RESULTS Post actually i stayed at the building right next to the lighthouse . i believe it was a boiler room . another group was already sleeping at the lighthouse . CCM i 'm not sure if you 're joking , but i 'm not sure if you 're talking about the lighthouse . i 'm not sure if it was a blanket or a blanket . GPT-2 (conv) i 'm pretty sure it was a room with a door . ConceptFlow good luck , i 'm sure there are some good things in the house . i think it 's to get their parents to care for them . predators do n't give a crap . they target young animals because they are the weakest . CCM i think they are the weakest . they do n't give a shit about their children . GPT-2 (conv) i 'm sure they do n't care about their kids . i have a friend who does n't care about the parents at all . it 's a great way to get a job at once a year . give him time ? you know he hit . 162 last year right ? red sox could n't wait to get rid of him , i do n't think he will be coming out of it CCM i think he 'll be fine . i think he 'll be fine . i think he 'll be a good starter for the next few seasons . GPT-2 (conv) i think he 'll be fine . he 's a great player , but he 's not a great player . ConceptFlow he 's not going to give up the money , but the media will just ignore him . Post there 's an offline mode for steam , and it works fine for me . Post at this point it may be more beneficial for him to keep playing as much as he can before the next season . trick his body into thinking he is still in the season . CCM i think he 's just going to be a great player . GPT-2 (conv) i 'm sure he 'll be fine . he 's a great player , but he 's not a top 10 player . he 's been playing the same game for the last two years . he 's been playing the same way . Post no i 've never felt like i had friends whoops CCM i 'm sorry , i feel you . GPT-2 (conv) i 've never felt like i had friends whoops . i 've never felt like i 've had friends whoops . ConceptFlow you 're gonna have to call your friend ! Post i 've known how to change the music , it does n't feel natural . thanks for the advice though . i 'm not sure if you 're joking , but i 'm not sure if you 're being sarcastic or not . i 'm not sure if you 're being sarcastic or not , but i 'm not sure if you 're being sarcastic or not . i 'm pretty sure it 's just a video . GPT-2 (conv) i 've been playing with a lot of different music and it 's always been the same . ConceptFlow i did n't even notice the natural sound . i 'll check it out ! Post are milan and inter no longer top clubs given that they currently do n't have the finances to compete with the best ? CCM milan is n't a top club , but they are n't top clubs . they are n't the only ones who are n't in the world . GPT-2 (conv) i think they are . they are a club that has been in the top 4 for a long time . the best part of the team is the way they are , and we do n't want to play the best team in the country . With the concept graph growing, more concepts are considered and a concept selector is needed for concept filter. The concept selector aims to select related two-hop concepts based on the sum of attention scores for each time t over entire two-hop concepts: where s t is the t-th time decoder output representation and e k denotes the concept e k 's embedding. Then top-k concepts are reserved to construct the two-hop concept graph G 2 with central concept graph. Moreover, central concepts are all reversed because of the high correlation to the conversation topic and acceptable computation complexity. For human evaluation, 100 cases with four responses from CCM, GPT-2 (conv), ConceptFlow and Golden Response are sampled and listed in an Excel file with randomly sort. A group of human judges are asked to score each response with 1 to 4 based on the quality of appropriateness and informativeness respectively, without knowing any clues of the source of response, thus the impartiality and objectivity of the evaluation can be guaranteed. To further demonstrate the consistency among human judges, the agreement of human evaluation for CCM, GPT-2 (conv) and ConceptFlow are presented in Table 9 . For each case, the result scores from two baseline models is compared with ConceptFlow and is divided into three categories: win, tie and loss. Then human evaluation agreement is indicated by Fleiss' Kappa. All agreement values fall into the fair level of agreement, which confirms the quality of human evaluation. E DATA STUDY To determine the gown deep of concept graph for conversation generation, some statistics are presented in Table 10 . The two-hop deep concept graph covers more than 61% golden concepts appearing in the response with acceptable computational efficiency. With growing to the three-hop, the number of concepts is increased dramatically with only about one extra golden concept for each case, thus the outer concept ends in two-hop concepts because of the close connection with the topic and the endurable computation complexity.
This paper presents ConceptFlow that explicitly models the conversation flow in commonsense knowledge graph for better conversation generation. The paper proposes a system for generating a single-turn response to a posted utterance in an open-domain dialog setting using the diffiusion into the neighbors of the grounded concepts.