# Graph-Based Applications

### Dynamic Knowledge Graph for Multi-domain dialogue State Tracking

In fact, the (domain, slot) pairs are not independent. For example, if a user requested a train for 3 people, then the number of people for hotel reservation may also be 3.

1. $(s, r_{v}, s’)$ : slot $s, s’$具有相同的取值集合，即 $V^{s}=V^{s’}$，这里的$V$仅代表slot value有限的情况。

For example, in MultiWOZ 2:0/2:1 dataset, domain-slot pairs (restaurant, book day) and (hotel, book day) have this relationship.

2. $(s, r_{s}, s’)$ : slot s的取值集合是$s’$的子集。

For example, in MultiWOZ 2:0/2:1 dataset, value sets of (restaurant, name), (hotel, name), (train, station) and (attraction, name) are subsets of the value set of (taxi, destination).

3. $(s, r_{c}, s’)$ : slot s的informed value v与slot $s’$的informed value $v’$ 存在关联，即使$V^{s}, V^{s’}$ 不存在交集，这种关系并没有显式地在ontology中给出。

For example, in MultiWOZ 2:0/2:1 dataset, the price range of a reserved restaurant is correlated with the star of the booked hotel.

4. $(s, r_{i}, v)$ : 用户已告知的slot $s \in S^{d}$ 的value $v \in V^{s}$。

Graph Definition 图包含两种节点：$\{M,N\}$，M代表(domain, slot) pair节点，记作$M_{d,s}$，N代表value值节点，记作 $N_{v}$。同样，图中包含两种边。一种边描述的是第4种关系：如果一个问题$Q_{d,s}$ 对应答案$v \in V^{s}$，那么$N_{v}$就会被添加到图中，且连接到$M_{d,s}$。默认情况下$M_{d,s}$会连接到一个特殊的_not mentioned_节点。另一种边描述的是前3种关系，由于第3种关系在ontology中没有显式地给出，所以作者做了简化处理，直接将M中所有的(domain, slot) 节点相互连接，然后使用注意力的方式读取。

Attention Over the Graph

1. The first step is to propagate the embedding of $N_{v}$ to its linked $M_{d,s}$, so that the embedding of $M_{d,s}$ depends on the value prediction from previous turns.
$$g_{d, s}=\eta\left(w^{d}+w^{s}\right)+(1-\eta) \sigma\left(\Theta_{4} \cdot W_{v,:}^{\bar{v}}\right)$$
其中$g_{d,s}$就是$M_{d,s}$新的embedding，实际作者使用的是简化式：$g_{d, s}=w^{d}+w^{s}+W_{v,:}^{\bar{v}}$。

2. The second step is to propagate information between nodes in M.
$$\alpha^{g}=\operatorname{Att}_{\beta_{4}}\left(G, B^{c \top} \cdot \alpha^{b}\right)$$
其中$G \in \mathbb{R}^{|M| * D^{w}}$ 由$g_{d,s}$拼接而成，$B^{c \top} \cdot \alpha^{b}$ 代表针对于$d,s$的context vector。

The attention scores can be interpreted as the learned relationships between the current (domain, slot) node and all other (domain, slot) nodes.

$$p_{t}^{v}= Softmax ( \text{BiLinear}_{\Phi_{1}} ( B^{q}, (1 - \gamma ) B^{c^{\top}} \cdot \alpha^{b}+\gamma z_{d, s} ) )$$

Some utterances such as “book a taxi to Cambridge station” do not need information in the graph, while some utterances such as “book a taxi from the hotel to the restaurant” needs information from other domains.

### Graph Convolutional Network with Sequential Attention for Goal-Oriented Dialogue Systems

1. 知识库KB
2. 对话历史
3. 当前用户utterance