GSN: A Graph-Structured Network for Multi-Party Dialogues

1 Introduction

Most existing dialogue systems are sequence-to-sequence (seq2seq) models [Luan et al., 2016; Serban et al., 2016]. Since a dialogue generally lasts for several turns, a dialogue session with multiple utterances can often be modeled as a sequence of "sequences" (i.e., utterances). A representative framework is the hierarchical recurrent encoder-decoder framework HRED [Serban et al., 2016; Serban et al., 2017]. In HRED, a recurrent neural network (RNN) encoder encodes the tokens in each utterance, and a context RNN encodes the temporal structure of the utterances. The entire dialogue session is then organized as a sequence.

Although HRED is effective in modeling sequential dialogue sessions, it falls short for dialogues involving more than two interlocutors. Table 1 shows a real conversation of 3 people (pi) in the Ubuntu forum. Utterances 3 and 4 both respond to utterance 2, represented as a graph in Figure 1. We see that utterances can occur in parallel with each other. This is beyond the expressive power of sequence models. This paper generalizes sequence-based representation of two-party dialogues to a graph-based representation of multi-party dialogues. Two-party sequence representation is a special case.

The proposed model, called GSN (graph-structured network), models the information flow in a graph-structured dibackward pass. We use their concatenation, i.e., [-→ si,t; ←- si,1], as the hidden state si,t at time t. Note that each word in the utterance indicates a state and a time step.

∗Equal Contribution.

†Contact Author

After encoding by W-E, a session with utterances {1, ..., m} is represented with S = {si, i ∈ {1, ..., m}}, where si = si,n is the last hidden state of W-E.

3.2 Utterance-level Graph-Structured Encoder (UG-E)

The HRED model is a hierarchical sequence-based word and utterance-level RNN. It predicts the hidden state of each utterance at time step t by encoding the sequence of all utterances appeared so far. Due to graph structures in real dialogues, RNN is no longer suitable for modeling the information flow of utterances. For instance, in Figure 1, HRED cannot handle utterances 3 and 4 properly because they are not logically sequential, but are "in parallel." The UG-E comes to help.

UG-E & Information Flow Over Graph

To model a graph structure and its information flow, we propose a new RNN with dynamic iterations. Given a session S, only the information in the preceding nodes/vertices i′ of each node i will flow to i in an iteration (i.e., there is a directed edge from each i′ to i). Then the state of node (utterance) i is updated and the updated state is used in the next iteration. In each iteration, all updates in a session are done in parallel. In this way, the encoding information and gradients can flow fully over the graph after some iterations. For instance, in the session in Figure 1 (or 4(b)), although the information flow of one iteration is from one node's preceding nodes to the node, the information in 1 can flow to 3 after two iterations.

UG-E's basic operation is illustrated in Figure 3. For example, given a session S = (s1, s2, s3, s4), in the l-th iteration, the state of the i-th utterance can be calculated by:

where ϕ is the collection of preceding nodes of the current node i in the direction of the information flow; ∆sl-1 I|i is the

2 ProblemFormulation

Utterances in a structured dialogue session can be formulated as a directed graph G(V, E), where V is a set of m vertices {1, ...,m} and E = {ei,j}mi,j=1 is a set of directed edges. Each vertex i is an utterance represented as a vector si learned by an RNN. If utterance j is a response to utterance i, then there is an edge from i to j with ei,j = 1; otherwise ei,j = 0. Our goal is to generate the (best) response ¯r that maximizes the conditional likelihood given the graph G:

where P (r|G) is modeled with the proposed GSN.

This model can be further enhanced by considering the speaker information, which introduces an adjacency matrix U = {ui,j}mi,j=1 , with ui,j = 1 if utterances i and j are from the same speaker and j is after i; ui,j = 0 otherwise.

3 Graph-Structured Neural Network (GSN)

Figure 2 gives the overall framework of GSN, which has three main components: a word-level encoder (W-E), an utterancelevel graph-structured encoder (UG-E), and a decoder. UG-E is the core of GSN. To make Figure 2 concise, we omitted some connecting lines and attentions. '⊗' is a special multiplication operator, called the update operator (see below). '·' denotes the mathematical matrix multiplication.

3.1 Word-level Encoder (W-E)

Given an utterance i = (wi,1, wi,2, ..., wi,n), W-E encodes it into an internal vector representation. We use a bidirectional recurrent neural network (RNN) with LSTM units to encode each word wi,t, t ∈ {1, ..., n} as a hidden vector si,t:

where e wi,t is the embedding of word wi,t at time step t, -→ si,t is the hidden state for the forward pass LSTM and ←- si,t for the updating information, which is calculated by Eq. 5 below; η is the updating coefficient indicating how much the new information (from the preceding nodes) should be added to the current state of the i-th utterance (node). Inspired by [Sabour et al., 2017], we design an alpha-weight as the updating coefficient. We use a non-linear "squashing" function (i.e., SQH(·)) to give vectors with a small norm a weight close to α, but a large norm a weight close to 1:

where α > 0 is a hyperparameter (it should be greater than 0 to provide enough updating rate from the very beginning); ∆sl-1 I|i is the updating information and is produced based on the state of the current utterance sl-1 i and the state of the preceding utterance sl-1 i′ :

where '⊗', the update operator, computes the updating information. Inspired by the updating operation hidden in Gated Recurrent Units (GRU) [Cho et al., 2014], ⊗ is defined as:

whereW,Wx andWr are parameters to be learned. σ is the sigmoid function.

Bi-directional Information Flow

In Figure 4(a), utterances 3 and 4 are two responses to utterance 2. It is obvious that utterance 2 can help generate a better state for utterance 4 and vice versa. However, the algorithm introduced above only allows the information and gradients to flow over the forward direction of the graph (as shown by the purple arrows in Figure 4(a)). Hence the information in utterance 3 cannot flow to utterance 4.

To tackle this problem, we propose a Bi-directional Information Flow (BIF) algorithm, which also uses backward information flow (as shown by the orange arrows in Figure 4(a)). In order to allow information to flow thoroughly, we push the information to flow backward first and then forward to ensure that the information can flow from one node to one's sibling nodes, i.e., backward to parent and forward to siblings. In our example above, the information of utterance 3 can flow to utterance 4 through utterance 2 after one backward flow and one forward flow, illustrated in Figure 4(a).

Speaker Information Flow

Representing speaker information in the latent embedding space is a popular method to enhance dialogue generation. However, this method lacks the ability to model the speaker and the dynamic changes of the speaker's ideas in a given session, especially when the speaker only speaks a few times because there may not be enough data to train those embeddings to represent the speaker and the changes since this method usually requires large data to train [Li et al., 2016; Qian et al., 2017; Zhang et al., 2018b].

Since the changes in speaker utterances reflect the changes in his/her mind, we propose to create an edge for every pair of utterances from the same speaker following the chronological order of the utterances. Thus there should be hidden edges among all utterances of the same user (e.g., the edge from utterances 1 to 3 in Figure 4(b)). We employ the same ⊗ operation to process the hidden edges, but due to different parameters, we use ⊛ to denote it:

We add the speaker information to Eq. 3:

where η and ∆sl-1 I|i are the same as those in Eq. 3; λ is also calculated with Eq. 4 with input ∆s′l-1 I|i instead of ∆sl-1 I|i .

3.3 Reformulation as Matrix Operations

So far, we have presented the proposed model. For computation, we reformulate it as matrix operations (also see UG-E in Figure 2) and give the pseudo-code in Algorithm 1. Recall the session S = (s1, s2, s3, s4), which is used to build the graph G(V,E) in Figure 4(a). We build a state matrix S with the vertices of the graph G (also the session S) as the diagonal elements, and all the other elements are set to 0 (we name this process the Building State Matrix function, denoted by BSM(S)). We then use the "@" relation (a speaker responding to another speaker) as the connection between two vertices to build the edge matrix E (shown in Figure 2). Recall the speaker information modeling in Section 3.2 and the utterance speaker adjacency matrix U. The main operation of Eq. 8 can be formalized by:

where ∆E = {∑mj=1 ∆Ei,j}mi=1 and ∆U = {∑mj=1 ∆Ui,j}mi=1 are two vectors, m is the length of the given session; ⊙ denotes the Hadamard product; η and λ can be calculated by:

This is just the forward information flow. We can obtain the backward information flow operation by changing Eq. 9:

To obtain ∆E and ∆U in Eq. 10, we need to change the direction of the sum, i.e., ∆E = {∑mj=1 ∆Ej,i}mi=1 and ∆U = {∑mj=1 ∆Uj,i}mi=1 . S, E, and U can be very sparse. But the proposed method can be well organized and the sparse matrices can be addressed by sparse matrix operations. The pseudo-code is given in Algorithm 1 in Appendix 1 .

3.4 Decoder

As shown in Figure 2, we illustrate a session {i}mi=1 with the corresponding encoding state denoted by S. To generate a response to an utterance i, the decoder calculates a distribution over the vocabulary and sequentially predicts word rk using a softmax function:

where f(·) is the tanh function. rk-1 is the word generated at the (k-1)-th time step, obtained from a word look-up table. hk = GRU(hk-1, rk-1) is the hidden state variable of a GRU at time step k. h0 = Si,i, and ck is the attention-based encoding of utterance i at decoding time step k and it is calculated by ck = ∑nj=1 exp(ej,k)si,j ∑mj=1 exp(ej,k) , where si,j is the encoder hidden state at time step j for utterance i, and ej,k = hkWasi,j scores the match degree of hk and si,j .

4 Experiments

4.1 Experimental Setups

Data Preparation

Our experiment uses the Ubuntu Dialogue Corpus 2 [Lowe et al., 2015] as it is the only benchmark corpus with annotated multiple interlocutors. It is also large with almost one million multi-turn dialogues, over seven million utterances and 100 million words. Each record contains a response utterance with its speaker ID and posting time.

1 https://morning-dews.github.io/Appendix/IJCAI2019 GSN.pdf

2 http://dataset.cs.mcgill.ca/ubuntu-corpus-1.0/

To build the training and testing datasets, we extract all utterances with response relations indicated by the "@" symbol in the corpus. For example, "A @ B" means that the utterance is addressed to Speaker B by Speaker A. Utterances from Speaker A and Speaker B are encoded into vector representations and used to construct the state matrix introduced in Section 3.3 as vertices. A directed edge is installed from A to B and used to build the edge matrix described in Sec. 3.3.

Following the baselines, we take the last utterance in each given session as the utterance to be generated 3 (i.e., the output target) and the other utterances in the session as the input. Finally, we extracted 380k sessions (about 1.75M utterances) as the experiment corpus and each session has 3 to 10 utterances and 2 to 7 interlocutors. We randomly divide the corpus into the training, development (with 5k q/a pairs), and test (with 5k q/a pairs) sets. We report the results on the test set. In testing, following the graph structure, the system knows which utterances to respond to. This is reasonable as this is also the case in a human dialogue, i.e., before responding, we know which preceding utterances to rely to.

It is important to note here that GSN is a general model that works well for both graph-structured (multi-party) and sequential (two party) dialogues as we will see shortly.

Baselines

We use a seq2Seq model and a hierarchical or HRED model as the baselines. HRED has been shown superior to other state-of-the-art models [Sutskever et al., 2014].

HRED model: We use HRED [Serban et al., 2016], the latest HRED model. Since HRED cannot deal with structured sessions, we convert each graph-structured dialogue session to a set of dialogue sequences by extracting every possible forward path from the first utterance to the last utterance of the session by following the "@" relationship and regarding each path (a sequence) as a dialogue sequence/session.

Seq2Seq model: We use the same sequential sessions extracted for HRED. Since the last utterance in each new session is the target utterance to be generated and the others are the input utterances, all the input utterances are concatenated into a long utterance as the input. Seq2seq modeling with attention is performed as in [Bahdanau et al., 2014; Sutskever et al., 2014] on the concatenated utterance.

Baselines with speaker information: We tried 3 methods of adding speaker information to baselines, using trainable speaker embedding (SE) [Li et al., 2016; Qian et al., 2017] as speaker information: a) concatenating SE with each word in the utterance; b) using SE as the prefix of the utterance; c) using SE as the prefix of the utterance and addressees SE as the suffix. For seq2seq (respectively, HRED), c) (b)) is the best, we report the corresponding results in Table 2.

Our GSN Model: There are multiple ways to implement the proposed GSN model. Since the objective of this paper is not to explore all possible ways, we use GRU units for all recurrent neural networks. For fairness, we adopt this setting for all baselines as well. We set α in Eq. 4 to 0.25.

3 GSN can generate responses all the way through a dialogue as GSN can gather the dialogue information to any graph node with the help of the dynamic iteration and information flow mechanisms.

Benefited from dynamic iterations, GSN is very flexible in generating responses for any utterance in a given session. However, to be consistent with the baselines, only the last utterance in each session is used as the target in training and testing. The code of our model can be found here 4 .

4.2 Training Details of Our GSNModel

We share the word embedding between the word-level encoder and the decoder and limit the shared vocabulary to 30k. The number of hidden units is set as 300 and the word embedding dimension is set as 300. We have 2 layers for both word-level encoder and decoder. The network parameters are updated using the Adam algorithm [Kingma and Ba, 2014] with the learning rate of 0.0001. All utterances are clipped to 30 words. We run all experiments on a single GTX Titan X GPU, and training takes 25 epochs.

4.3 Results and Analysis

Automated Evaluation

We use two kinds of metrics in automated evaluation: 1) Following [Fu et al., 2017; Havrylov and Titov, 2017], we use the evaluation package of [Chen et al., 2015], which includes BLEU 1 to 4, METEOR and ROUGEL. 2) We also use embedding-based metrics [Forgues et al., 2014] which can cover the weaknesses of the BLEU's.

Table 2 shows the evaluation results. The first three rows are for the baselines. The three rows in the middle are for our GSN model using only the information flow over the graph structure, and the last three rows are also for our GSN model but with the addition of the speaker information flow. From Table 2, we can make the following observations:

• (1). GSN (row 11, with the speaker information flow after 3 iterations) markedly outperforms the baselines (rows 2 and 5) by up to 2.27 BLEU points (BLEU 1).
• (2). With-speaker (W-speaker) versions of GSN also clearly outperform the no-speaker versions, indicating the importance of the speaker information flow. To further verify whether the improvement is due to adding more connections or adding the speaker edges, we conducted experiments by adding some random edges with different percentages until full connections

4 https://github.com/morning-dews/GSN-Dialogues

among nodes (using No-speaker setting with 3 iterations). The results showed a clear drop with the increase of randomly added edges and received very poor result for full connection, which further shows the usefulness of the proposed speaker information modeling method. As the results are very poor, they are not shown here.

• (3). We also use the exist embedding-based persona method to arm baselines (W-speaker) for a fair comparison with GSN W-speaker version. We can see from Table 2 the gain is limited, and our method still outperforms the baselines.
• (4). The results of GSN improve as the number of iterations increases, which indicates the importance of the dynamic iterations. With more iterations, more utterances will be modeled by GSN. Only after two iterations, our models with the speaker information flow (row 10) already outperforms both two baselines in 4 out of 6 evaluation metrics. Even for the no-speaker versions (row 7), our model beats the best baseline in 4 out of 6 evaluation metrics.

The BLEU scores had a tiny increase in the 4th iteration (around 0.1% for GSN W-speaker, and 0.3 % for GSN Nospeaker). For other metrics, e.g., METEOR and ROUGEL, there is little change. The 5th iteration is similar, but the scores decrease from the 6th iteration. We thus choose 3 iterations.

Embedding-based metrics: Based on the embedding-based metrics, our model also outperforms the baselines. Our model gets 0.770 / 1.040 / 0.651 for the three embedding-based metrics (Embedding Average Score / Embedding Greedy Score / Embedding Extrema Score), which are all better than the scores of the best baseline model (HRED), 0.515 / 0.905 / 0.325. See the details in Appendix1 , which also includes a case study with examples.

Sequential data and graph data: To verify the generic nature of the GSN model, we conduct an ablation experiment with only sequential data (sessions with only two interlocutors) or graph data (remaining sessions with more than two interlocutors). The results are shown in Table 3. We see that GSN significantly outperforms the strong HRED baseline in both sequential and graph settings. From both Tables 3 and 2, we can see that GSN improves in the sequential case mainly because of the additional encoding iterations.

Tables 3 and 2 also show that the proposed iterative graphstructured encoder UG-E and the graph-based speaker information flow are effective. GSN is thus a good generalization of the sequence-based models, and a desirable system for both graph-structured (multi-party) and sequential (two-party) dialogue response generation.

Human Evaluation

We also conducted human evaluation to measure the quality of responses generated by all methods. We evaluate based on "naturalness", which includes 1) grammaticality, 2) fluency and 3) rationality. We randomly sampled 100 utteranceresponse pairs, shuffled the order of systems, and asked three Ph.D. students to rate the pairs in terms of model quality on 0 to 4 scales (4 for the best) and we report their average scores. More details can be found in Appendix1 .

Table 4 shows that GSN (with the speaker information flow after only 1 iteration or the no-speaker version after 3 iterations) outperforms the best baseline (HRED), indicating that GSN generates more natural responses. The reason that our model (with the speaker information flow and just one iteration, column 5 in Table 4) outperforms three iterations of our model's no-speaker version (column 4 in Table 4) is because the model (with the speaker information flow) can generate a more consistent response for the speaker. The generated utterances are more preferred by humans.

5 RelatedWork

Existing dialogue models follow the sequential information flow [Shang et al., 2015; Wen et al., 2017; Tao et al., 2019]. Recent progresses in seq2seq models [Sutskever et al., 2014; Luong et al., 2015] have inspired several efforts [Li et al., 2019; Young et al., 2018] to build dialogue systems.

Although seq2seq models have achieved good results for dialogue generation, they regard all input utterances as a long sequence, which greatly increases the complexity of the model in passing information and computing gradients. As an improved solution, the HRED models [Serban et al., 2016] tackle this problem by constructing the sequential flow at the utterance level. However, this setting is insufficient for modeling dialogues that have more than 2 interlocutors, which need a graph-based model.

For multi-party dialogues, prior work have employed retrieval-based approaches [Zhang et al., 2018a; Meng et al., 2018]. No graph modeling method has been proposed, although graph-based methods have been used for other NLP tasks, e.g., Graph Convolutional Networks for classification [Kipf and Welling, 2016] and semantic role labeling [Marcheggiani and Titov, 2017], Gated Graph Neural Networks for generation from AMR graphs and syntax-based neural machine translation [Beck et al., 2018]. Different from these works, we propose a generation model by formulating the complex dialogue problem using a graph-based solution. Also importantly, compared to seq2seq and HRED, GSN not only can encode graph structured information flows, but also sequential ones.

6 Conclusion

In this paper, we proposed a general graph-structured neural network GSN to model both graph-structured (multi-party) and sequential (two-party) dialogues. The core of the model is an utterance-level graph-based encoder (UG-E), which is a generalization of the conventional sequence-based encoder. For the response generation in multi-party conversations, the speaker information is also modeled in the graph. As our results showed, GSN is general and is suitable for both multiparty and two-party dialogues.

The current GSN relies on clear addressee information. Our future work will try to automatically identify the conversation structure and decide who to respond to. Dynamic routine and attention can be leveraged to achieve this goal.

Acknowledgements

This work was partially supported by National Key Research and Development Program of China (No.2017YFC0804001), National Science Foundation of China (No. U1604153, No. 61876196, No. 61672058), Alibaba Innovative Research Fund. Rui Yan was supported by CCF-Tencent Open Research Fund and Microsoft Research Asia Collaborative Research Program.