# TedBR: Target-Oriented Dialog with Bidirectional Reasoning on Knowledge Graph
## 1 Introduction  
Recently, dialog agents have been classified into three categories: open-domain [1; 2; 3; 4], task-oriented [5; 6], and target-oriented dialog systems [7; 8; 9; 10; 11; 12]. Open-domain and task-oriented dialog systems focus on chit-chat dialog and task fulfillment, whereas their conversational guidance remains passive rather than active. However, target-oriented dialog systems aim to proactively introduce new topics and guide the dialog toward a predefined target topic. Specifically, when given a source and target topic expressed as two brief utterances, the target-oriented dialog (TOD) agent must generate a transitional response that connects the two topics seamlessly. Due to their purposeful and flexible nature, target-oriented dialog agents possess a wide range of applications, spanning conversational recommendation [13], psychotherapy [14], and education [15]. A typical example of a target-oriented dialog scenario is demonstrated in Table 1 as follows: the source topic is \"1 like going to concerts\", and the target topic is \"I usually have to take a break during the week\". In this scenario, the dialog agent is expected to generate an appropriate transition response that links the source topic \"concert\" to the target topic \"work\", and the transition is \"I want to relax completely after a week's work is done\". The transition response helps to seamlessly shift the focus of the conversation from the initial topic to the target topic. In the domain of target-oriented dialog, the mainstream approach to address the topic transitions issue is using reasoning techniques based on a knowledge graph (KG). These methods can be categorized into two main types: supervised learning [10; 16; 17] and reinforcement learning [18; 19]. Reinforcement learning (RL) methods employ a policy-based agent incrementally, extending its reasoning path until it reaches the target entity. The agent's state is typically defined as a tuple consisting of the query and the current entity, and its action involves traversing the knowledge graph by following the outgoing edges of the current entity. RL-based approaches heavily depend on the reward design strategy [20; 21], so reward shaping and action dropout have been proposed to improve path searching and model learning. On the other hand, supervised-based methods heavily rely on costly annotations of reasoning signals [22]. These methods can be further divided into generating an entity path that connects the initial query to the target entity and ranking entities based on their relevance to the user's context. While the mainstream methods mentioned above work well, there are still a couple of issues: (1) the current external knowledge graph, especially the common sense graph, has millions of nodes, affecting the efficiency and effectiveness of multi-hop reasoning; (2) current methods do not fully take into account the impact of the source and target information, leading to a dialog that feels unnatural or inefficient. Our approach tackles this problem by using bidirectional reasoning. To this end, we propose **TodBR** (**T**arget-**or**i**ented **d**ialog with **B**idirectional **R**easoning on Knowledge Graph), aiming to effectively support the target-oriented process through bidirectional reasoning on a knowledge graph enclosing the target topic. Our approach considers two distinct perspectives when addressing the task setting: forward reasoning, which explores the path from source entities to target entities, and backward reasoning, which follows the reverse path from target entities to source entities. Our solution draws inspiration from bidirectional graph search algorithms like bidirectional BFS and DFS. While existing methods predominantly focus on forward reasoning, it is feasible to jointly model the two reasoning processes, as both topic entities and target entities are known at the start of the dialog. The bidirectional reasoning mechanism effectively reduces the search space and enhances the reasoning efficiency.