# TedBR: Target-Oriented Dialog with Bidirectional Reasoning on Knowledge Graph
## 3 Methods
### Bidirectional Reasoning Decoder  
The bidirectional reasoning module generates a keyword sequence as cue words to give an \"intermediate\" utterance. Bidirectional graph scoring is utilized to fuse graph node representations based on the dialog context representations, as shown in Figure 3.  
**Graph Encoding** To encode the topic entities in the dialog graphs and obtain representations for concepts and relations, we employ multi-layer GCN encoders [44]. Inspired by the TransE [45] model, we also update the concept embedding by subtracting the corresponding relation embedding from each neighboring concept embedding to obtain the relation representation. At the \((l+1)\)th layer, we update the embedding of each entity  
Figure 3: The bidirectional reasoning process. by aggregating its neighbors \(\mathcal{N}_{i}\), which consist of pairs of concepts and relations that are connected to \(v_{i}\):  
\[h_{i}^{(l+1)}=\sigma\left(W_{s}^{(l)}h_{i}^{(l)}+\sum_{(j,r)\in N_{i}}\frac{1}{| \mathcal{N}_{i}|}W_{n}^{(l)}\left(h_{j}^{(l)}-h_{r}^{(l)}\right)\right), \tag{5}\]  
In the above equation, \(h_{i}^{(l)}\), \(h_{j}^{(l)}\) and \(h_{r}^{(l)}\) represent the embeddings of node \(v_{i}\) node \(v_{j}\), and the relations between \(v_{i}\) and \(v_{j}\) at layer \((l)\)th, \(W_{s}^{(l)}\) and \(W_{n}^{(l)}\) are specific trainable parameter matrices for layer \(l\)th; \(\sigma\) is a non-linear active function. The relation embedding is also updated at the \((l+1)\)th layer via \(h_{r}^{(l+1)}=W_{R}^{(l)}h_{r}^{(l)}\). After \(L\) iterations, we are able to obtain \(\left\{h_{v_{1}}^{(L)},\ldots,h_{v_{|V|}}^{(L)}\right\}\), a set of concept representations, and \(\left\{h_{r_{1}}^{(L)},\ldots,h_{r_{|R|}}^{(L)}\right\}\), a set of relation representations. **Bidirectional Reasoning** We employ bidirectional reasoning to compute concept distributions on graphs. This approach incorporates neighboring information and the current decoder state to adjust the weight of the bidirectional concept (source and target entities) in the graph at each decoding step. Initially, a score of 1 is assigned to source and target concepts, while others are given a score of 0. Subsequently, the information regarding the scored concepts is disseminated throughout the graph to update unvisited concepts in both directions. For an unvisited concept \(v_{i}\in V\), \(score(v)\) is computed by aggregating the evidence from its visited neighboring concepts \(\mathcal{N}_{i}^{in}\):  
\[ \begin{split}& R\left(v_{j},r,v_{i}\right)=\sigma([h_{j}^{(L)};h_{ r}^{(L)};h_{i}^{(L)}]W_{relation}s_{t}),\\ & score(v_{i})=\sum_{(v_{j},r)\in\mathcal{N}_{i}^{in}}\frac{1}{ \left|\mathcal{N}_{i}^{in}\right|}\left(\gamma\cdot score(v_{j})+R\left(v_{j},r,v_{i}\right)\right),\end{split}  \tag{6}\]  
Here, in the triple relevance \(R\left(v_{j},r,v_{i}\right)\), \(v_{j},v_{i}\) denote nodes (or concepts) in the graph; \([h_{j}^{(L)};h_{r}^{(L)};h_{i}^{(L)}]\) denote the representations of nodes \(v_{j},v_{i}\) at the \(L\)-th layer of a neural network. \(W_{relation}\) is the weight matrix relating the triple \(v_{j},r,v_{i}\), \(s_{t}\) is the current decoder state at decoding step, and \(\sigma\) is the Sigmoid activation function. In concept score update function \(score(v_{i})\), \(v\) is a node or concept in the graph, \(\mathcal{N}_{i}^{in}\) is a set of visited neighboring concepts for \(v\), and \(\gamma\) is a discount factor. This equation updates the concept score by aggregating information from its visited neighboring concepts. After \(L\)-hop interactions, the distribution over the concepts is as follows:  
\[P(V\mid s_{t},\mathcal{G})=softmax_{v\in V}(score(v)). \tag{7}\]  
Here, \(P(V\mid s_{t},\mathcal{G})\) represents the distribution over concepts in the graph \(\mathcal{G}\) given the current decoder state and \(s_{t}\) at decoding step \(t\). In other words, it is the probability of each concept in the graph being the next element in the sequence being generated.