MADNet: Maximizing Addressee Deduction Expectation for Multi-Party Conversation Generation
Authors: Jia-Chen Gu
Chao-Hong Tan
Caiyuan Chu
Zhen-Hua Ling
Chongyang Tao
Quan Liu
Cong Liu
Venue: EMNLP 2023 Main (2023)
Keywords: Dialogue System
Multi-Party Conversation
Addressee Deduction
Latent Edge
Expectation-Maximization
TL;DR: To study the issue of scarcity of addressee labels in MPCs, MADNet is proposed that maximizes addressee deduction expectation in heterogeneous graph neural networks for MPC generation.

Abstract: Modeling multi-party conversations (MPCs) with graph neural networks has been proven effective at capturing complicated and graphical information ﬂows. However, existing methods rely heavily on the necessary addressee labels and can only be applied to an ideal setting where each utterance must be tagged with an “@” or other equivalent addressee label. To study the scarcity of addressee labels which is a common issue in MPCs, we propose MADNet that maximizes addressee deduction expectation in heterogeneous graph neural networks for MPC generation. Given an MPC with a few addressee labels missing, existing methods fail to build a consecutively connected conversation graph, but only a few separate conversation fragments instead. To ensure message passing between these conversation fragments, four additional types of latent edges are designed to complete a fully-connected graph. Besides, to optimize the edge-type-dependent message passing for those utterances without addressee labels, an Expectation-Maximization-based method that iteratively generates silver addressee labels (E step), and optimizes the quality of generated responses (M step), is designed. Experimental results on two Ubuntu IRC channel benchmarks show that MADNet outperforms various baseline models on the task of MPC generation, especially under the more common and challenging setting where part of addressee labels are missing.

MADNet:
Maximizing Addressee Deduction Expectation for Multi-Party Conversation Generation
Jia-Chen Gu Chao-Hong Tan'; Caiyuan Chu², Zhen-Hua Ling
Chongyang Tao Quan Liu Cong Liu
National Engineering Research Center of Speech and Language Information Processing, University of Science and Technology of China, Hefei, China
1IFLYTEK Research, Hefei, China
SPeking University, Beijing, China
*State Key Laboratory of Cognitive Intelligence
(gujc, zhling @ustc. edu en, cht @n@mail ust edu. cn, chongyangtao@pku.cc edu, cn, (cychu2, quanliu, congliu2 (ooooggllleeilleeeeeeke @iflytek.com
Abstract
88b ol you to US: HOW very soon nOw
12h1 or beal in Ltbnk calerize chargge Uaiiiing more
Modeling multi-party conversations (MPCs) with graph neural networks has been proven ef- fective at capturing complicated and graphical information flows. However, existing methods rely heavily on the necessary addressee labels and can only be applied to an ideal setting where each utterance must tagged with an "@" or other equivalent addressee label. To study the scarcity of addressee labels which is common issue in MPCs, we propose MADNet that maximizes addressee deduction expectation in heterogeneous graph neural networks for MPC generation. Given MPC with a few addressee labels missing, existing methods fail to build a consecutively connected conversation graph, but only few separate conversation fragments instead. To ensure message passing between these conversation fragments, four additional types of latent edges are designed to complete a fully-connected graph. Besides, to optimize the edge-type- dependent message passing for those utter- ances without addressee labels, an Expectation- Maximization-bar method that iteratively generates silver addressee labels (E step), and optimizes the quality of generated responses (M step), is designed. Experimental results two Ubuntu IRC channel benchmarks show that MADNet outperforms various baseline models on the task of MPC generation, especially un- der the more common and challenging setting where part of addressee labels missing.
Us
thomi
comsalent with
Uk
goesd sunch of osde have the ctoing poserthes
tham anything dise on the pet mp
did fie an updanod version what worn woloome
Ur
(a) An MPC instance with few addressee labels (@)) miesing
Interlocutor
Fragooet
Utterance
Reply + Replied by
Speak Spoken-by
Address Addressed-br
The graphical information flow and fragments estabished HeterMPC
Figure 1: (a) A randomly sampled MPC instance from Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) where few addressee labels, i.c., "@", are missing. (b) Illustration of the graphical information flow and conversation fragments of the instance above established in HeterMPC (Gu et al., 2022). Here, the bidirectional edges are merged for simplicity.
2020). Thanks to breakthroughs in sequence mod- eling (Sutskever et al., 2014; Vaswani et al., 2017) and pre-trained language models (PLMs) (Radford et al., 2019; Devlin et al., 2019; Lewis et al., 2020), rescarchers have proposed various effective models for conversations between two participants (Serban et al., 2016; Wen et al., 2017; Zhang et al., 2020). Recently, researchers have paid more attention to a more practical and challenging scenario involving more than two participants, which is well known as multi-party conversations (MPCs) (Ouchi and Tsuboi, 2016: Zhang et al., 2018: Le et al., 2019; Hu et al., 2019; Wang al., 2020; Gu et al., 2021, 2022). Unlike two-party conversations, utterances in an MPC can be spoken by anyone and address anyone else in this conversation, constituting a graphical information flow.
1 Introduction
The development of intelligent dialogue systems that are able to engage in conversations with humans, has been one of the longest rumning goals in artificial intelligence (Kepuska and Bo- houta, 2018; Berdasco et al., 2019; Zhou et al.,
"Equal contribution. "Corresponding author.

---

Encoding MPC contexts with either homoge- neous (Hu al., 2019) or heterogeneous (Gu et al., 2022) graph neural networks (GNNs) has been proven effective at modeling graphical informa- tion flows. These methods rely heavily on the necessary addressee labels and can only be applied to an ideal setting where each utterance must be tagged with an "@" or other equivalent addressee label, establish consecutively connected graph. However, interlocutors in MPCs do not always strictly obey the talking rule of specifying their addressees in each utterance, as shown by a randomly sampled MPC instance in Figure ((a). Statistics show that addressees of 55% of the utterances in the Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) are not specified. In this common case, the expected conversation graph in previous work became fragmented (Hu et al., 2019; Gu al., 2022) as shown in Figure I(b). Therefore, nodes without direct connections cannot exchange information between each other through one-hop message passing. Despite disconnected nodes can instead be accessed indirectly via other detours through multi-hop passing, inevitable information loss and passing lateney will affect generation performance significantly. But this common issue has not been studied in previous work.
the expectation steps iteratively generate silver addressce labels by considering the addressee of an utterance as a discrete latent variable. On the other hand, the maximization steps selects the addressee with the highest probability from the addressee distribution and optimize the generative dialogue model. As the number of EM iterations increases, the accuracy of the latent addressee distribution well the quality of generated responses be improved simultaneously. Compared with previous methods, MADNet can be applied more common and challenging MPC scenarios, indicating its generalization and robustness.
To measure the effectiveness of the proposed method, evaluate the performance two benchmarks based on Ubuntu IRC channel. One was released by Ouchi and Tsuboi (2016) where a few addressee labels were missing. The other was released by Hu et al. (2019) where addressee labels were provided for each utterance. Experimental results show that MADNet outperforms previous methods by significant margins, achieving new ofte-of-the-art performance for MPC generation especially in the more common and challenging setting where a few addressee labels are missing.
In summary, our contributions in this paper are three-fold: 1) To the best of our knowledge, this paper makes the first attempt to explore the issue of missing addressee labels and to target more common MPC scenarios. 2) A fully-connected heterogeneous graph architecture along with EM training is designed to help deduce the addressee of an utterance for improving MPC generation. 3) Experimental results show that our proposed model achieves new statc-of-the-ar performance of MPC generation conditioned on incomplete addressce labels on two Ubuntu IRC benchmarks.
In light of the above issues, we propose MADNet that maximizes addressec deduction expectation in heterogeneous graph neural networks to mitigate performance degradation and to enhance model robustness, for MPC generation conditioned on incomplete addressee labels. Given an MPC with a few addressee labels missing, existing methods fail to build consecutively connected conversation graph, but only few separate conversation frag- ments instead (Hu et al., 2019; Gu et al.. 2022). To ensure message passing between these conversation fragments, four additional types of latent edges are designed to complete a fully-connected graph. this way, nodes without direct connections can also directly interact with each other, and be distinguished from existing edges by param- eterization. Furthermore, sige-type-dependee message passing has been verified effective at MPC modeling (Gu et al., 2022). In order to optimize edge characterization and message pass- ing for utterances without addressee labels, a hard Exppecation-Maxxiiizaioon-- Maximization--aaeer approach (Brown et al., 1993; Shen et al., 2019; Min et al., 2019) is designed for addressee deduction. On the one hand,
2 Related Work
Multi-Party Conversation Existing methods on building dialogue systems can be generally catego- rized into generation-based (Serban et al., 2016;
Wen et al., 2017: Young et al., 2018; Zhang et al., 2020) or retrieval-based approaches (Wu et al., 2017; Zhou et al., 2018; Tao et al., 2019; Gu et al., 2020). In this paper, we study MPC generation, where in addition to utterances. in- terlocutors are also important components who play the roles of speakers or addressees. Previous methods have explored retrieval- based approaches for MPCs. For example, Ouchi and Tsuboi

---

(2016) proposed the dynamic model which updated speaker embeddings with conversation streams, Zhang et al. (2018) proposed speaker interaction RNN which updated speaker embeddings role- sensitively. Wang et al. (2020) proposed to track the dynamic topic in conversation. Gu et al. (2021) proposed jointly learning "who says what to whom" in unified framework by designing self-supervised tasks during pre-training. On the other hand, Hu al. (2019) explored generation- based approaches by proposing a graph-structured network (GSN). At its core was an utterance- level graph-structure conversation context using homogeneous GNNs. Gu et al. (2022) proposed HeterMPC to model the complicated interactions between utterances and interlocutors with a heterogeneous graph (Sun and Han, 2012), where two types of nodes and six types of edges were designed to model heterogeneity. Contemporaneous to our work, Li and Zhao (2023) focus on predicting the missing addressee labels in pre-training instead, but still only target at the ideal setting during fine-tuning where each utterance must be tagged with the addressee label.
our knowledge, this paper makes the first attempt to extend to more common MPC scenarios and explore the issue of missing addressee labels by maximizing addressee deduction expectation for MPC generation.
Preliminaries
Problem Formulation The task of response generation in MPCs to generate an appropriate sponse F given the conversation history, the speaker of a response, and which utterance the response is going to reply to. This can be formulated as:
encoder that encoded the
argmax lngg
[rl
(1)
arginax Σ (ogP(r)
Here, G is a heterogeneous graph, c is the context of dialogue history, is the model parameters. The speaker and addressee of the response are known and its contents are masked. The response tokens generated in auto-regressive way. and r<i stand for the 1-th token and the first (1 (t-11 1) tokens of response respectively. |r] the length of r.
This algorithm is used to find local maximum likelihood parameters statistical model in cases where the equations cannot be solved directly (Dempster et al., 1977; Dayan and Hinton, 1997; Do and Batzoglou, 2008). Rather than sampling a latent variable from its conditional distribution, a hard EM approach which takes the value with the highest posterior probability as prediction is designed (Brown et al., 1993). This approach has been proven effective at improving the performance of various NLP tasks such as dependency parsing (Spitkovsky et al., 2010), machine translation (Shen et al., 2019), question answering (Min et al., 2019) and diverse dialogue generation (Wen et al., 2023). In this paper, study whether considering addressees latent variable and deducing with hard EM is useful for modeling conversation structures and improving MPC generation performance.
Expectation-Maxiniie
Next, we briefly present the key process of the HeterMPC baseline (Gu et al., 2022) to avoid lengthy method descriptions, which shares the GNN backbone with our method. Readers can also refer to Gu et al. (2022) for more details.
Graph Construction Given MPC instance composed of M utterances and I interlocutors, heterogeneous graph G(V, E) is constructed. Specifically, V is a set of M + I nodes. Each node denotes either an utterance or an interlocutor. E = {<p.4) pp=11pp44111 is set of directed edges, where each edge 6p.4 describes the connection from node to node q. Six types of meta relations in HeterMPC (Gu et al., 2022) and four additional types of latent edges proposed in this paper are introduced to describe directed edges between nodes, which will be elaborated Section 4.1. 1. It is notable that bp.q is set to NULL if there is no connection between two nodes, so that interactions between them can only be conducted indirectly via detours through multi-hop passing.
Compared with GSN (Hu et al., 2019) and HeterMPC (Gu et al., 2022) that are the most relevant to this work, a main difference should be highlighted. These methods target only on ideal setting where addressee labels of all utterances are necessary, while the proposed method is suitable for more common conversation sessions where a few addressee labels are missing. To the best of
Node Initialization Each node is represented as vector, and two strategies are designed initialize the node representations for utterances and interlocutors respectively. Utterances are first encoded individually by stacked Transformer

---

Interlocutor
Us
Utterance
Reply Replied-by
Speak + Spoken-by
Address Addressed-by
Latent-reply Latent-replied-by
Latent-address Latent-addressed-by
Illustration of edges utterances with addressee labels, e.g., U2
(b) Illustration of edges utterances without addressee labels, e.g.. U?
Illustration edges utterances (a) with and (b) without addressee labels respectively in a fully- connected MPC graph for the instance Figure 1.
Figure 2:
layers that be initialized by PLMs, e.g. encoder of BART (Lewis al., 2020), to derive the contextualized and utterance-level representations. On the other hand, interlocutors in a conversation are indexed according to their speaking order and the embedding vector for each interlocutor is derived by looking up an order-based interlocutor embedding table (Gu et al., 2020) that is updated during learning.
4 Methodology
In this section, we first describe how to construct fully-connected conversation graph to ensure message passing between conversation fragments. Then, the expectation and maximization steps for addressee deduction defined. Finally, an addressee initialization method is designed for better convergence of the EM algorithm.
4.1 Fully-Connected Graph Construction
Node Updating The initialized node representa- tions are updated by feeding them into the built graph for absorbing context information. Het- crogeneous attention weights between connected nodes and message passing over the graph are manner.
Six types of meta relations (reply, replied-by, speak, spoken-by, address, addressed-by) are introduced in HeterMPC (Gu et al., 2022) to describe directed edges between nodes. However, given an MPC with few addressee labels missing, existing methods usually return several separate conversation fragments.
calculated in Parameters are introduced maximize feature distribution differences for modeling heterogene- ity (Schlichtkrull et al., 2018; Zhang et al., 2019; Hu et al., 2020). After collecting the information from all source nodes to target node, node- type-dependent feed-forward network followed by residual connection (He al., 2016) is employed for aggregation. To let each utterance token also have access to graph nodes, an additional Transformer layer is placed for utterance nodes specifically. After completing an iteration, the outputs of utterance and interlocutor nodes are employed as the inputs of the next iteration.
To build consecutively connected conversation graph and ensure message passing between these conversation fragments, additional latent edges are required for completing a fully-connected conversation graph. this paper, four additional types of latent edges are designed to establish the dependency of utterance nodes all other nodes in an MPC graph for conversation contextualization as shown in Figure 2. There two types of them employed to characterize latent relationships between two disconnected utterance nodes. detail, latent-reply characterizes directional edges from latter utterances to previous ones which are ordered by their appearance in an MPC, and vice versa for latent-replied-i another two types of latent edges are employed to characterize the relationships between ut- terance node and interlocutor node. In detail, latent-address characterizes directional edges from utterance nodes to interlocutor nodes, and vice versa for aihent-addressed-by. By this means, both utterances that do not reply to directly and
Decoder It follows the standard implementation of Transformer decoder (Vaswani et al., 2017) for generation, and can be initialized by PLMs, e.g. decoder of BART (Lewis et al., 2020). In each decoder layer, masked self-attention operation is performed where each token cannot attend future (okens avoid information leakage. Then, cross- attention operation over the node representations output by the graph encoder is performed to incorporate graph information for decoding.
On the other hand,

---

Expectation Stop
Generative Model
U+
Pir|Gur - u)
Assume U. replles to Us
Assume repiles Us
Assume U, repliss to
Argmax
Gur LX
U2
replies
U. replesto
Maximization Step
Figure 3: Illustration the EM training process for the instance in Figure where the expectation and maximization steps performed alternately.
interlocutors that do not address to directly also useful for capturing the semantics contained in graph nodes and for modeling complicated interactions between nodes.
which simplifies Eq. (2) as:
P(r|Gu, SUy, ,;,,;; P(Gu, vuyle,r:0 r: Σ GU; C;
4.2
EM for Addressee Deduction
Maximization Step After deriving the approxi- mate probability distribution the latent addressec variable, we maximize the expected log-likelihood with respect to O:
Figure illustrates the EM training process, where the expectation and maximization steps are per- formed alternately. The addressee of an utterance without a golden addressee label is modeled as discrete latent variable.
(e. P(r, G|c,
Expectation Step Given the observed MPC in- stances with model parameters frozen, the condi- tional distribution of the latent addressee variable is calculated during the E steps. Here, specific addressce corresponds to a determined MPC graph. To derive the probability distribution of the latent addressee variable, a set of latent graphs are fed into the generative model respectively to calculate the probabilities of generating response under these latent graphs P(r|Gu, >Uy: c), where Gu,-U, is graph assuming Ug replies to Uy. The derived probability distribution of generating response under these latent graphs serves as the posterior of selecting the latent variable. The latent addressee distribution of the latent variable is estimated by applying Bayes' rule as:
P(Gr,-0,ler:00 log P(r, GU
(4)
Hard EM A hard EM method (Min et al.. 2019) that selects the addressee with the highest probability as the silver label is adopted as:
U, = argmax P(Gu,-u,le, r; r) jii, (5) Uj
and the maximization step is approximated log P(r, Gr, c; 0). Once the silver addressee label is determined this round, its corresponding MPC graph is employed for regular training by minimizing the negative log-likelihood loss of responses.
4.3 Addressee Initialization
P(Gu, v0, c, r; 0)
The initialization of addressce labels is crucial to EM for addressee deduction, it helps converge to optimal model parameters. Thus, an addressee initialization method is designed for utterances without addressee labels before EM training, to select the most probable one as initialization.
P(r|Gu, c, c; P
Σi P(r|Gu, c; (0o00PPPP0) P(Gu,-uj
(2) A uniform prior for every context c as P(Gu,-U, = 1/(i 1) is assumed,

---

The encoder and decoder of the model are initialized with PLMs. e.g., BART, which is pre- trained on texts in the general domain. First, domain adaptation is conducted based on the fully- connected graph constructed in Section 4.1, with the learning objective of minimizing the negative log-likelihood loss of responses on the task training set. By this means, the representation space can be adapted to the task domain and capture the conversation semanties. Then, for specific utterance without an addressee label, each previous utterance is assumed to be the replied utterance respectively by setting the corresponding utterance- utterance edges to reply and replied-by, as well as edges to address
2020), as well as (2) graph-based models including GSN (Hu et al., 2019) and HeterMPC (Gu et al., 2022). Readers can refer to Appendix A.2 for implementation details of these baseline models.
5.3 Metries
To ensure all experimental results were comparable, we used exactly the same automated and human evaluation metrics as those used in previous work (Hu et al., 2019; Gu et al., 2022). Hu et al. (2019) used the evaluation package released by Chen al. (2015) including BLEU-1 BLEU-4, METEOR and ROUGE,, which was also used in this paper. Human evaluation was conducted to measure the quality of the generated responses in terms of three independent aspects: 1) relevance, 2) fluency and 3) informativeness. Each judge was asked to give three binary scores for response, which were further summed up to derive the final score ranging from 0 to 3.
setting the and addressed-by. This process is illustrated in the left part of Figure 3. The probability of generating a response under an assumed graph is calculated following Eq. (2). Finally, the one with the highest probability following Eq. (5) is chosen as the initialization for the first round of M step.
5,4 Implementation Details
5 Experiments
The corresponding parameters of MADNet fol- lowed those in HeterMPC (Gu et al., 2022) for fair comparison. Model parameters were ini- tialized with pre-trained weights of bart-base released by Lewis et al. (2020). The Adam method (Loshchilov and Hutter, 2019) was em- ployed for optimization. The learning rate was initialized as 6.25e-5 and was decayed linearly down O. The max gradient norm was clipped down 1.0. The batch size was gradient accumulation steps. The maximum utterance length was set to 50. The number of layers for initializing utterance representations was set to 3, and the number of layers for heterogencous graph iteration was set to 3. The number of decoder layers was set to 6. The strategy of greedy search was performed for decoding. The maximum length of responses for generation was also set 50. All experiments were run on single Tesla A100 GPU. The number of EM iterations was set to 2. The number of epochs in each M step was set to 4, and the learning rate was fixed to 5c-7. Each iteration took about 9 and 6 hours for each E step and M step respectively. The validation set was used to select the best model for testing. All code was implemented in the PyTorch framework2 and is published help replicate our results.
5.1 Datasets
We evaluated our proposed methods on two Ubuntu IRC benchmarks. One was released by Ouchi and Tsuboi (2016), in which the addressee labels for part of the history utterances were missing. Here, we adopted the version shared in Le et al. (2019). The conversation sessions were separated into three categories according the session length (Len-5, Len-10 and Len-15). In this paper, the subset of session length 5 was employed due to the limitation of computing resources. The other dataset where addressee labels were provided for each utterance was adopted following previous work (Hu et al., 2019; Gu et al., 2022). Both datasets were popularly used in the field of multi- party conversations (Zhang et al., 201 8; Wang et al.. 2020; Gu et al., 2021). Appendix A.1 presents the statistics of the two benchmarks.
128 with
5.2 Baseline Models
We compared our proposed model with as many MPC generative models as possible. Considering that there are only few research papers in this field, several recent advanced models were also adapted
provide sufficient comparisons following Gu et al. (2022). Finally, we compared with (1) non graph- graph-based based models including GPT- 2 (Radford et al., 2019) and BART (Lewis et al.,
hhtps://githubbco https///iitubb.om//yiilnooooooo www.e/oooooooocoooocpppooooa
e hhtpss//pyytrrch.org

---

Metrics
BLEU-1 BLEU-2 BLEU-3
BLEU-4 METEOR ROUGE,
Models
GSN (Hu al., 2019)
6.32
2.28
1.10
0.61
3.27
7.39
GPT-2 (Radford et al., 2019)
9.12
3,40
1,93
1.39
3.28
8.92
BART (Lewis et al., 2020)
11.13
3.95
2.11
1.44
4.45
10.20
HeterMPC (Gu et al., 2022)
11.40
4.29
2.43
1.74
4.57
10.44
MADNet
11.82
4.58
2.65
1.91
4.90
10.74t
MADNet w/o. EM for addressee deduction
11.62
4.48
2.59
1.88
4.80
10.63
MADNet w/o. latent-reply and latent-replied-by
11.76
4.43
2.47
1.74
4.83
10.67
MADNet w/o. latent-address and latent-addreesee-byy
11.54
4.44
2.57
1.87
4.72
10.52
Table Evaluation results and ablations the test set of Ouchi and Tsuboi (2016) in terms of automated evaluation. Numbers in bold denoted that the results achieved the best, and those marked with f denoted that the improvements were statistically significant (I-test with p- p-value 0.05) comparing with the best performing baseline.
Metries
BLEU-1 BLEU-2 BLEU-3 BLEU-4 METEOR ROUGE,
Models
GSN (Hu et al., 2019)
10.23
3,57
1.70
0.97
4.10
9.91
GPT-2 (Radford al., 2019)
10.37
3.60
1.66
0.93
9.53
BART (Lewis et al., 2020)
11.25
4.02
1.78
0.95
4.46
9.90
HeterMPC (Gu et al., 2022)
12,26
4.80
2.42
1.49
4.94
11.20
MADNet
12.73
5.12
2.64
1.63
5.31
11.74
MADNet w/o. latent-reply and latent-replied-by
12.54
4.91
2.53
1.59
5.20
11.60
MADNet w/o. latent-ade latent-address address and theet--dddressedbae
12.45
4.92
2.52
1.55
5.18
11.60
Table Evaluation results and ablations the test of Hu al. (2019) in terms of automated evaluation. Results except ours are cited from Gu et al. (2022). Note that EM for addressee deduction was not adopted on this dataset, since addressee labels were provided each utterance.
5.5 Evaluation Results
ponent of our proposed method, ablation tests were conducted as shown the last few rows of Table and Table First, EM for addressee deduction was removed on the dataset of Ouchi and Tsuboi (2016). The drop in performance illustrated that accurate addressee labels were crucial to the graphical information flow modeling in MPCs. In addition, EM was an effective solution addressee deduction. Furthermore, the latent-reply and latent-replied-by edges, or latent-address and antent-addressed-by edges were removed respectively. The drop in performance illustrated the importance of modeling interactions between indirectly related utterances, and those between utterances and interlocutors for better conversation contextualization.
our experiments, BART was selected to initialize MADNet following Gu et al. (2022).
Automated Evaluation Table and Table present the evaluation results of MADNet and previous methods the test sets. Each model four times with identical architectures and different random initializations, and the best out them was reported. The results show that MADNet outperformed all basclines terms of all metrics. Specifically, MADNet outperformed the best performing baseline. i.e., HeterMPC by 0.42% BLEU-1, 0.29% BLEU-2, 0.22% BLEU- 3, 0.17% BLEU-4, 0.33% METEOR and 0.30% ROUGE, the test set of Ouchi and Tsuboi (2016). Additionally, MADNet outperformed HeterMPC by 0.47% BLEU-11, 0.32% BLEU-2, 0.22% BLEU-3, 0.14% BLEU-4, 0.37% METEOR and 0.54% ROUGE, on the test set of Hu et al. (2019). These results illustrated the effectiveness of our proposed method in modeling MPC structures, and the importance of message passing between the utterance and interlocutor nodes in MPC graph.
Human Evaluation Table 3 presents the human evaluation results on a randomly sampled test set of Ouchi and Tsuboi (2016). 200 samples were evaluated and the order of evaluation systems were shuffled. Three graduate students were asked score from 0 to 3 (3 for the best) and the average scores were reported. It can be seen that MADNet achieved higher subjective quality scores than the selected baseline models.
To further verify the effectiveness of each com-

---

Mctrics
Metries
Score
Accuracy BLEU-4 METEOR ROUGE,
Models
Models
HeterMPC
1.33
5.03
11.35
Human
2.09
HeterMPC
37.4
1.29
4.94
11.23
GSN (Hu et al., 2019)
1.20
HeterMPCpree
44.8
1.32
4.96
11.32
BART (Lewis et al., 2020)
1.54
MADNet
50.1
1.51
5.17
11.65
MADNet,ror
100.0
1.63
5.31
11.74
MPI (Gu et al., 2022)
1.62
MADNet
1.79
Table Accuracy of addressee deduction and automated evaluation results the modified dataset of Hu et al. (2019). rand, prec and orac were abbreviations of random, preceding and oracle respectively.
Table 3:
Human evaluation results of MADNet and some selected systems on a randomly sampled test set Ouchi and Tsuboi (2016).
5.6 Analysis
10.5
ROUSE:
10.4
Accuracy of addressee deduction. A key as- pect of the proposed method is to deduce the addressee information which in turn improves the performance of response generation. Therefore, the accuracy of addressee deduction evaluated with respect a set of baselines to explore its impact on response generation. To do that, a modified dataset of Hu et al. (2019) was constructed. Specifically, the golden addressee label of the last utterance of the conversation history was masked to derive the modified dataset.* Results of five selected methods on this modified dataset were compared as shown in Table 4: (1) HeterMPC, (2) each utterance whose addressee label was masked was randomly assigned pre- vious ulterance as its reply-to utterance and fed it to HeterMPC, denoted as HeterMPPyand: (3) each utterance whose addressee label was masked was assigned its preceding utterance as its reply- to utterance and fed it to HeterMPC, denoted as HeterMPPPree. (4) MADNet and (5) MADNet with the oracle addressee labels, i.e., MADNet the original Hu et al. (2019) dataset. Results show that the prediction of addressees significantly affects the performance of MPC generation. Seriously wrong predictions might even hurt performance. can be seen that the addressee deduction with EM in MADNet outperformed the heuristic methods of random selection by margin of 12.7% accuracy, and of selecting its preceding utterance by margin of 5.3% accuracy. As result, the generation performance was improved benefiting from ac- curate addressee predictions. It notable that the prediction addressee achieved only 50.19 % accuracy, which shows that this task is still difficult
10.3
4.7
4.6
directly
4.5
1.67
1.66
Iterations
Figure 4: Performance of MADNet under different
numbers of EM iterations on the validation set of Ouchi and Tsuboi (2016).
and there is lot of room for further improvement.
Number of EM iterations. Figure 4 illustrated how the performance of MADNet changed with respect to different numbers of EM iterations on the validation set of Ouchi and Tsuboi (2016). It can be seen that the performance of MADNet proved as the number of EM iterations increased the beginning terms of METEOR and ROUGEz, showing the effectiveness of employing EM for addressee deduction. Then, the performance was stable with more EM iterations. The reason might be that models have selected as many optimal addressee labels possible.
im-
Case Study. A case study was conducted by randomly sampling an MPC instance as shown Table Given the conversation graph, the response to generate addressed I.1, so the information relevant to I.1 should be collected. It can be seen from this instance that the addressee label was only available for the third utterance, and the established conversation graph was very fragmented due the lack of addressee labels. Conditioned on an inconsecutively connected graph, previous methods hardly capture the context semantics and can only
"The dataset of Hu et al. (2019) was adopted here, since the golden addressec labels were provided for cach utterance and can be used for evaluation.

---

Speaker
Unterance
Addressee
Limitations
1.1
perhaps but not everyone uses that ask him for his history log think
1.2
Although the proposed method has shown great performance to alleviate the scarcity of addressec labels which is a common issue in multi-party conversations, we should realize that the proposed method still can be further improved. For example, to derive the probability distribution of the latent addressee variable, substitute that the probabil- ity of generating a response under the assumed graph is considered its approximation. This assumption has shown its empirical improvement in our experiments, and the theoretical analysis will be part of our future work to help derive more accurate probability distribution. In addition, a set of latent graphs are required and fed into the generative model to calculate the probabilities of generating response under these latent graphs, which consumes much computation resources. Thus, optimization of the expectation steps with less computation is worth studying. Besides, benchmarking the baselines and evaluating the proposed method on other appropriate datasets to make it more representative of as many MPC scenarios as possible will be part of our future work.
for people who do the phased update percentages are a considered ok
1.3
L1
1.1
true
1.3 (Deduced)
first thought might related https launchpad ubuntu source unity scopes upi 0 15 (Human)
do n know how that not sure what you want do with the (GSN)
1.3
not sure if you can get a silo that m not aware any other (BART)
1.1
m not sure if you can get that to work for you but think
good (HeterMPC)
1thikk it's a bit of corner case for people who do n have the phased update (MADNet)
Table 5: The response generation results of a test sample. "I." is abbreviation of "interlocutor". We kept original texts without manual corrections.
generate generic responses such as "i m not sure For MADNet, the missing addressce label of the fourth utterance was deduced 1.3, which appropriate considering the MPC context. Given the deduced addressee label, the message of "phased update" in the third utterance can be passed the fourth utterance. Furthermore, the response to generate was about to reply to the fourth utterance, and this important message can further captured for response generation.
Acknowledgements
This work was supported by the Opening Founda- tion of State Key Laboratory of Cognitive Intel- ligence, iFLYTEK anonymous reviewers for their valuable comments.
We thank
6 Conclusion
References
We present MADNet to maximize addressee de- duction expectation to study the issue of scarcity of addressee labels in multi-party conversations. Four types of latent edges are designed model interactions between indirectly related utterances, and those between utterances and interlocutors for conversation contextualizatio.. Furthermore, an EM-based approach is designed to deduce silver addressee labels and optimize the quality of generated responses. Experimental results show that the proposed MADNet outperforms previous methods by significant margins on two benchmarks of MPC generation. especially shows better generalization and robustness the more common and challenging setting where a few addressce labels are missing.
Ana Berdasco, Gustavo López, Ignacio Díaz-Oreiro. Luis Quesada, and Luis A. Guerrero. 2019. User experience comparison of intelligent personal assistants: Alexa, google assistant, siri and cortana.
In 13th International Conference on Ubiquitous Computing and Ambient Intelligence, UCAml 2019, Toledo, Spain, December 2-5, 2019, volume 31 of MDPI Proceedings, page 51. MDPI.
Peter F. Brown, Stephen Della Pictra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estima- tion. Comput. Linguistics, 19(2):263-311
Xinlei Chen, Hao Fang. Tsung- Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C. Lawrence Zitnick. 2015. Microsoft COCO captions: Data collection and evaluation server. CoRR, abs/ 504.000355..

---

Peter Dayan and Geoffrey E. Hinton. 1997. Using expectation-mxximiaatioo for reinforcement learning. Neural Compur. 9(2):271 1-788.
2019, Macao, China, August 10-16, 2019, pages 5010-5016.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020. Heterogeneous graph transformer. In WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pages 2704-2710. ACM/ IW3C2.
Arthur P Dempster. Nan M Laird, and Donald B Rubin. 1977. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), (91:1112
Jacob Devlin, Ming-Wo Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLI 2019. Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pages 4171 186..
Veton Kepuska and Gamal Bohouta. 2018. Next- generation of virtual personal assistants (microsoft cortana, apple siri, amazon alexa and google home). In IEEE 8th Annual Computing and Communication Workshop and Conference, CCWC 2018, Las Vegas, NV, USA, January 8-10, 2018, pages 99-103, IEEE.
Ran Le, Wenpeng Hu, Mingyue Shang, Zhenjun You, Lidong Bing. Dongyan Zhao, and Rui Yan. 2019. Who is speaking to whom? learning to identify utterance addressee in multi- party conversations. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Procexsing, SMNIL-IJCNIA 2019, Hong Kong. China, November 3-7, 2019, pages 1909-199 1919.
Chuong B Do and Serafim Batzoglou. 2008. What is the expectation maximization algorithm? Nature biotechnology, 26(8):897-899
Jia-Chen Gu. Tianda Li, Quan Liu, Hua Ling, Zhiming Su, Si Wei, and Xiaodan Zhu. 2020. Speaker-aware BERT for multi-turn response selection in retrieval-base
chatbots. In CIKM '20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020, pages 2041- 2044.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy. Veselin Stoyanov, and Luke Zettlemoyer. 2020. BART: denoising sequence-to-sequenee pre-training for natural language generation, translation, and comprehension. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pages 7871-7880. Association for Computational Linguisties.
Jia Cha- Gu, Chao-Hong Tan, Chongyang Tao, Zhen- Hua Ling, Huang Hu, Xiubo Geng, and Daxin Jiang. 2022. HeterMPC: A heterogeneous graph neural network for response generation in multi- party conversations. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), ACI. 2022, Dublin, Ireland, May 22-27, 2022, pages 5086 5097. Association for Computational Linguistics.
Yiyang Li and Hai Zhao. 2023. EM pre-training for multi-party dialogue response generation. Proceedings of the 61st Anmual Meeting of the Association for Compulational Linguistics (Volume I: Long Papers), ACL 2023, Toronto, Canada, July 9- 14, 2023, pages 92-103. Association for Computational Linguistics.
Ma-Chen Gu. Chongyang Tao, Zhen-Hou Ling, Can Xu, Xiubo Geng, and Daxin Jiang. 2021. MPC- BERT: A pre-trained language model for multi- party conversation understanding. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 Ith International Joint Conference on Natural Language Processing. ACL/JCCNLP 2021, (Volume 1: Long Pupers). Virtual Event, August 1-6, 2021, pages 3682-3692. Association for Computational Linguistics.
Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR 2019. New Orleans, LA, USA, May 6-9, 2019. OpenReview.net.
Sewon Min, Danqi Chen, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2019. A discrete hard EM approach for weakly supervised question answering. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2079, pages 2851-2864. Association for Computational Linguistics.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV. USA, June 27-30, 2016, pages 770-778. IEEE Computer Society.
Wenpeng Hu, Zhangming Chan, Bing Liu, Dongyan Zhao, Jinwen Ma, and Rui Yan. 2019. GSN: A graph-structured network for
Hiroki Ouchi and Yuta Tsuboi. 2016. Addressee and response selection for multi-party conversation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP
Proceedings of the multi-party dialogues. International Joint Conference on Artificial Intelligence, IJCAI

---

2016, Austin, Texas, USA, November 1-4, 2016, pages 2133-2143.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017, Attention is all you need. In Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Newral Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998-6008.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAl blog. 188):
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolutional networks. In The Semantic Web 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings, volume 10843 of Lecture Notes in Computer Science, pages 593 607. Springer.
Weishi Wang. Steven C. Hoi. and Shafiq R. Joty. 2020. Response selection for multi-party conversations with dynamic topic tracking. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 6581- 6591.
Tsung-Hsien Wen, David Vandyke, Nikola Mrksic, Milica Gasic, Lina Maria Rojas-Barahona. Pei- Hao Su, Stefan Ultes, and Steve J. Young. 2017. A network-based end-to-end trainable task- oriented dialogue system. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2017, Valencia, Spain, April 3-7, 2017, Volume 1: Long Papers, pages 438
Julian Vlad Serban, Alessandro Sordoni, Yoshua Bengio. Aaron C. Courville. and Joelle Pineau. 2016. Building end-to-end dialogue systems using generative hierarchical neural network models. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 3776-3784.
Tianxiao Shen, Myle Ott, Michael Auli, and Mare' Aurelio Ranzato. 2019. Mixture models for diverse machine translation: Tricks of the trade. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June
Yuqiao Wen, Yongchang Hao. Yanshuai Cao, and Lili Mou. 2023. An equal-size hard EM algorithm for diverse dialogue generation. In The Eleventh Inter- national Conference on Learning Representations, ICLR.
2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages PMLR.
Yu Wu, Wei Wu, Chen Xing, Ming Zhou, and Zhoujun Li. 2017. Sequential matching network: A new architecture for multi-turn response selection in retrieval- chatbots. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguisties. ACL 2017, Vancouver, Canada. July August 4, Volume 1: Long Papers, pages 496-505.
Valentin Spitkovsky, Hiyan Alshawi, Daniel Jurafsky, and Christopher D. Manning. 2010. Viterbi training improves unsupervised dependency parsing. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning, CoNLL 2010, Uppsala, Sweden, July 15-16, 2010, pages 9- 17. ACI..
Tom Young, Erik Cambria, It Chaturvedi, Hao Zhou, Subham Biswas, and Minlie Huang. 2018 Augment- ing end-to-end dialogue systems with commonsense knowledge. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI- 18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposian Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 4970-4977.
Yizhou Sun and Jiawei Han. 2012. Mining Het- ergennous Information Networks: Principles and Methodologies. Synthesis Lectures on Data Mining and Knowledge Discovery. Morgan & Claypool Publishers.
Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014. Sequence sequence learning with neural networks. Advances Neural Information Processing Sys- tems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 3104-3112.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh Chawla. 2019. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage. AK, USA, August 4-8, 2019, pages 793- 803. ACM.
Chongyang Tao, Wei Wu, Can Xu, Wenpeng Hu, Dongyan Zhao, and Rui Yan. 2019. One time of interaction may not be enough: Go deep with an wewpaattiiooovveieittrrrtee
network for response selection dialogues. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume Long Pupers, pages 11.
Rui Zhang, Honglak Lee, Lazaros Polymenakos, and Dragomir R. Radev. 2018. Addressee and response selection in multi-party conversations with speaker interaction mns.. In Proceedings of the Shirry-Scoond AAAI Conference on Artificial Intelligence, (AAAI- 18), the 30th innovative Applications of Artificial

---

Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (FAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 5690-5697.
utterances and the response were concatenated with a special [SEP] token as input for encoding. (2) BART (Lewis et al., 2020) was a denoising autoencoder using a standard Tranformer-bane architecture, trained by corrupting text with an arbitrary noising function and learning to recon- struct the original text. In our experiments, concatenated context started with 
 and sepa- rated with 
 were fed into the encoder, and response were fed into the decoder. (3) GSN (Hu et al., 2019) made the first attempt to model an MPC with homogeneous graph. The core of GSN was an utterance-level graph-structured encoder. (4) HeterMPC (Gu et al., 2022) achieved the state-of-ther
Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao. Jingjing Liu, and Bill Dolan. 2020. DIALOGPT: Large-scale generative pre-training for conversational response generation. In Proceedings of the 58th Annual Meeting of the Association for Compulational Linguistics: System Demonstrations, ACL 2020, Online, July 5-10, 2020, pages 270-278. Association for Computational Linguistics.
Li Zhou, Jianfeng Gao, Di Li, and Heung-Yen Yeung Shum. 2020. The design and implementation of xiaoice, an empathetic social chatbot. Comput. Linguistics. 46(1):53-93.
performance on MPCs. It proposed to model the complicated interactions between utterances and interlocutors in MPCs with heterogeneous graph, where two types of graph nodes and six types of edges are designed model heterogeneity. Two versions of HeterMPC were provided that were initialized with BERT and BART respectively. The latter was adopted in this paper which showed better performance.
Xiangyang Zhou, Lu Li. Daxiang Dong, Yi Liu, Ying Chen, Wayne Xin Zhao, Dianhai Yu, and Hua Wu. 2018. Multi-turn response selection for chatbots with deep attention matching network. In Proceedings of the 56th Annual Meeting the Association for Computational Linguistics, ACI. 2018, Melbourne, Australia, July 15-20, 2018, Volume 1: Long Papers, pages 1118-1127,
A Appendix
A.1 Datasets
Datasets
Train
Valid
Test
Ouchi and Tsuboi (2016)
461,120 28,570 32,668
Hu al. (2019) 311,725 5,000 5,000
Table 6: Statistics of the two benchmarks evaluated in this paper.
A.2 Baseline Models
We compared our proposed model with as many MPC generative models as possible. Considering that there are only few research papers in this field, several recent advanced models were also adapted provide sufficient comparisons. We followed previous work (Hu et al., 2019; Gu et al.. 2022) that the tags speakers and addressees were both used if they were available when establishing the performance of baselines. based Finally, we compared with (1) non-graph- graph-based models including GPT-2 (Radford et al., 2019) and BART (Lewis et al., 2020), as well as (2) graph- based models including GSN (Hu al., 2019) and HeterMPC (Gu al., 2022) follows.
(1) GPT-2 (Radford al., 2019) was uni- directional pre-trained language model. Following its original concatenation operation, all context


Reviews:
[{"review_id": "JsTSfEuKGj", "reviewer": "Reviewer_SdPB", "summary": "", "questions": "Question A: The graph neural network architecture is not clear enough. Can you provide more details of your Graph Neural Network model (for example, using math formulas to explain the exact computational steps)?\n\nQuestion B: How many utterances are there without addressee labels in the dataset released by Ouchi and Tsuboi (2016)?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable suggestions! We are so excited to receive many encouraging reviews and constructive suggestions. We will try our best to respond to the raised issues and will implement the suggested improvements in our revision.\n\n\n1.Re: **reliability of evaluation metric**\n\nThanks for your advice. As we described in Section 5.3, to ensure all experimental results were comparable, we used exactly the same automated and human evaluation metrics as those used in previous work (Hu et al., 2019; Gu et al., 2022). More detailed human evaluation as you suggest such as inter-annotator agreement might provide more comprehensive evaluation towards “multiple good answers”, which will be part of our future work.\n\n\n2.Re: **more details of the graph neural network model**\n\nDue to page limitations, we briefly describe in Section 3 the key process of graph construction, node initialization, node updating, and decoder of the baseline, i.e., HeterMPC (Gu et al., 2022), which shares the graph neural network backbone with our method. In order to avoid lengthy method descriptions and to help readers quickly understand the contributions of our proposed method, only some key computational steps are present in this paper. Thanks for your advice, we will describe more details of the graph neural network model as much as the number of pages allows. Readers can also refer to HeterMPC (Gu et al., 2022) for more details.\n\n\n3.Re: **number of utterances without addressee labels in the Ouchi and Tsuboi (2016) dataset**\n\nAs we described in line 69-71, statistics show that addressees of 55% of the utterances in the Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) are not specified, illustrating that the scarcity of addressee labels is a common issue.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. MADNet achieves SOTA results in terms of both automatic and human evaluation.\n2. The proposed EM method for addressee deduction is interesting and effective.\n3. The paper is well written, the contributions are clearly described, and the model choices are well supported by ablation studies.", "reasons_to_reject": "No major weaknesses. The only concern is the reliability of evaluation metrics. In conversation generation, there can be multiple \"good answers\" which have very low lexical overlap (all automatic evaluation metrics used in the paper are based on lexical overlap.) with the ground truth. In this case a low score may not necessarily indicate a bad generation. Human evaluation on the other hand is a more reliable method. The authors need to report inter-annotator agreement to show the human evaluation results are robust and consistent.", "questions_to_authors": "Question A: The graph neural network architecture is not clear enough. Can you provide more details of your Graph Neural Network model (for example, using math formulas to explain the exact computational steps)?\n\nQuestion B: How many utterances are there without addressee labels in the dataset released by Ouchi and Tsuboi (2016)?", "paper_topic_and_main_contributions": "This paper proposes MADNet, a graph-neural-network-based multi-party conversation generation model that is applicable in more realistic settings where addressee labels of utterances can be missing. Previous models require the presence of addressee labels for all utterances.\nThe contributions are as follows:  \n1. The authors proposed MADNet which achieved SOTA results on two existing datasets.\n2. The authors explored a more realistic setting for multi-party conversation generation where some addressee labels of utterances are missing\n3. The authors proposed to use EM training to deduce the addressee of an utterance, which is approved effective. ", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HHvludKgyJ", "reviewer": "Reviewer_dY2D", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable suggestions! We are so excited to receive many encouraging reviews and constructive suggestions. We will try our best to respond to the raised issues and will implement the suggested improvements in our revision.\n\n\n1.Re: **choice of datasets**\n\nAs we described in Section 5.1, to ensure all experimental results were comparable, we used exactly the same dataset as those used in previous work (Hu et al., 2019; Gu et al., 2022), and an additional Ubuntu-based dataset (Ouchi and Tsuboi, 2016) in which the addressee labels for part of the history utterances were missing. These datasets were both popularly used in the field of multi-party conversations (Ouchi and Tsuboi, 2016; Zhang et al., 2018; Le et al., 2019; Wang et al., 2020; Gu et al., 2021). Furthermore, as we described in line 69-71, statistics show that addressees of 55% of the utterances in the Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) are not specified. These statistics illustrate that the scarcity of addressee labels is a common issue, thus the Ouchi and Tsuboi (2016) dataset is very suitable for the experimental setting studied in this paper. Thanks for your advice, benchmarking the baselines and evaluating the proposed method on other appropriate datasets to make it more representative of as many multi-party conversation scenarios as possible will be part of our future work.\n\n\n2.Re: **computational overhead**\n\nAs we discussed in the section of Limitation, we have been aware that computational complexity optimization of the proposed method is indeed an issue worth further investigation. In detail, a set of latent graphs, each of which assumes the current utterance replies to one of the utterances in the previous conversation history as shown in Figure 3, are required and fed into the generative model to calculate the probabilities of generating a response under these latent graphs. This process typically consumes much computation resources. Thanks for your advice, more analysis of computational complexity will be included in the revision.\n\n\n3.Re: **performance of using EM**\n\nOn the one hand, as shown in Table 1, after removing EM for addressee deduction, the drop in performance illustrated that accurate addressee labels were crucial to the graphical information flow modeling in MPCs. Thus, EM was an effective solution to addressee deduction.\n\nOn the other hand, as shown in Table 4, the accuracy of addressee deduction was directly evaluated with respect to a set of baselines to explore its impact on response generation. Results show that the prediction of addressees significantly affects the performance of MPC generation. It can be seen that the addressee deduction with EM in MADNet outperformed the heuristic methods. As a result, the generation performance was improved benefiting from accurate addressee predictions with EM. \n\nThus, the use of EM algorithm really works for improving the MPC generation performance.\n\n\n4.Re: **human evaluation**\n\nAs we described in Section 5.3, to ensure all experimental results were comparable, we used exactly the same automated and human evaluation metrics as those used in previous work (Hu et al., 2019; Gu et al., 2022). Thanks for your advice, more details of human evaluation will be included in the revision. Besides, evaluating the proposed method and various baselines using an improved human evaluation protocol for more comprehensive evaluation will be part of our future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* They address an interesting problem - missing addressee labels are common in real multi-party conversation datasets, but existing models require complete labels. This work makes models more robust.\n* The proposed solution is methodically sound and innovative - using Expectation-Maximization to estimate missing labels is a clever application of a standard technique. \n", "reasons_to_reject": "1. They only experiment on Ubuntu IRC datasets. Testing on more diverse MPC datasets would strengthen the generality of the results.\n3. The computational overhead of running Expectation-Maximization during training is not discussed in detail. This could be a practical limitation.\n5. In Table 1 and 2, MADNET w/o the EM algorithm already performs quite well -- so, is the use of EM algorithm really helping?\n1. Human Evaluation is totally wrong. \n    1. What questions were asked to the user for human evaluation, what each of the levels in the scale meant. The UI used for human evaluation also needs to be shared. Without these details, human evaluation numbers are all useless.\n    1. Don't average different aspects.\n    2. Don't use 0-1 scale. Use a likert scale with more levels and proper meaning for each level.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper is addressing the problem of missing addressee labels in multi-party conversation (MPC) datasets. In MPCs, each utterance is addressed to a specific person, but often the addressee labels indicating who each utterance is addressing are missing in the datasets. The authors propose a model called MADNet that estimates the missing addressee labels using an Expectation-Maximization (EM) approach. They also add latent edges between utterances and interlocutors to keep the conversation graph fully connected even with missing labels.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "E8VsBIzbGO", "reviewer": "Reviewer_wap4", "summary": "", "questions": "1.Could you provide details examples of the address labels and show some good case and bad case?\n2.why choose ubuntu dataset for experiments. I think it may be not a proper dataset for address labels tasks. Do you have any statistics for the address labels in ubuntu and other datasets?\n3. address labels could be various, e.g.  city, street, etc.  Do you consider this difference?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable suggestions! We are so excited to receive many encouraging reviews and constructive suggestions. We will try our best to respond to the raised issues and will implement the suggested improvements in our revision.\n\n\n1.Re: **analysis of addressee labels**\n\nQuantitative and qualitative analysis of addressee labels were conducted in Section 5.5. \n\nIn detail, the quantitative accuracy of addressee deduction was directly evaluated with respect to a set of baselines to explore its impact on response generation. Results show that the prediction of addressees significantly affects the performance of MPC generation. It can be seen that the addressee deduction with EM in MADNet outperformed the heuristic methods. As a result, the generation performance was improved benefiting from accurate addressee predictions.\n\nOn the other hand, the qualitative case study was conducted as shown in Table 5. It can be seen that the established conversation graph was very fragmented due to the lack of addressee labels. Conditioned on an inconsecutively connected graph, previous methods hardly capture the context semantics and can only generate generic responses. For MADNet, the missing addressee label can be appropriately deduced considering the MPC context. Given the deduced addressee label, some important message can be passed accordingly and further be captured for response generation.\n\nThanks for your advice, more analysis and examples of addressee labels will be included in the revision.\n\n\n2.Re: **choice of datasets**\n\nAs we described in Section 5.1, to ensure all experimental results were comparable, we used exactly the same dataset as those used in previous work (Hu et al., 2019; Gu et al., 2022), and an additional Ubuntu-based dataset (Ouchi and Tsuboi, 2016) in which the addressee labels for part of the history utterances were missing. These datasets were both popularly used in the field of multi-party conversations (Ouchi and Tsuboi, 2016; Zhang et al., 2018; Le et al., 2019; Wang et al., 2020; Gu et al., 2021). Furthermore, as we described in line 69-71, statistics show that addressees of 55% of the utterances in the Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) are not specified. These statistics illustrate that the scarcity of addressee labels is a common issue, thus the Ouchi and Tsuboi (2016) dataset is very suitable for the experimental setting studied in this paper. Thanks for your advice, benchmarking the baselines and evaluating the proposed method on other appropriate datasets will be part of our future work.\n\n\n3.Re: **difference of addressee labels**\n\nIt is necessary to clarify that addressee labels mentioned in this paper do not mean the locations such as city, street, etc. As we described in Figure 1(a) which is a real-world conversation example in the Ubuntu dataset and Table 5 which presents a case study, addressee labels are mostly showcased by the “@” tags. Thus addressee are typically the interlocutors that appear in the previous conversation history.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Despite its importance, address labels are missing in the existing multi-turn conversation datasets, which limited the further research progress in this track. This paper provide a method to augment the address labels in the generated datasets, and proved the effectiveness. The paper is well organized and easy to follow.", "reasons_to_reject": "There could be more analysis to the address labels with case study. .ubuntu may be not a proper dataset for address labels tasks. ", "questions_to_authors": "1.Could you provide details examples of the address labels and show some good case and bad case?\n2.why choose ubuntu dataset for experiments. I think it may be not a proper dataset for address labels tasks. Do you have any statistics for the address labels in ubuntu and other datasets?\n3. address labels could be various, e.g.  city, street, etc.  Do you consider this difference?", "paper_topic_and_main_contributions": "This paper makes the first attempt to explore the issue of missing addressee labels and to target on more common MPC scenarios. They proposed a fully-connected heterogeneous graph architecture along with EM training is designed to help deduce the addressee of an utterance for improving MPC generation. Experimental results show that the proposed model achieves a new state-of-the-art performance of MPC generation on two Ubuntu IRC benchmarks.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XmQTKVRxJa", "reviewer": "Reviewer_JM8Y", "summary": "", "questions": "1. Have you considered any other evaluation metrics besides BLEU, METEOR, and ROUGE-L, which are commonly used in the literature?\n2. Can you provide more details on the computational complexity of the proposed method and how it scales with the size of the input data?\n3. Can you try to use LLMs in comparison to your work?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable suggestions! We are so excited to receive many encouraging reviews and constructive suggestions. We will try our best to respond to the raised issues and will implement the suggested improvements in our revision.\n\n\n1.Re: **choice of datasets**\n\nAs we described in Section 5.1, to ensure all experimental results were comparable, we used exactly the same dataset as those used in previous work (Hu et al., 2019; Gu et al., 2022), and an additional Ubuntu-based dataset (Ouchi and Tsuboi, 2016) in which the addressee labels for part of the history utterances were missing. These datasets were both popularly used in the field of multi-party conversations (Ouchi and Tsuboi, 2016; Zhang et al., 2018; Le et al., 2019; Wang et al., 2020; Gu et al., 2021). Furthermore, as we described in line 69-71, statistics show that addressees of 55% of the utterances in the Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) are not specified. These statistics illustrate that the scarcity of addressee labels is a common issue, thus the Ouchi and Tsuboi (2016) dataset is very suitable for the experimental setting studied in this paper. Thanks for your advice, benchmarking the baselines and evaluating the proposed method on other appropriate datasets to make it more representative of as many multi-party conversation scenarios as possible will be part of our future work.\n\n\n2.Re: **computational complexity**\n\nAs we discussed in the section of Limitation, we have been aware that computational complexity optimization of the proposed method is indeed an issue worth further investigation. In detail, a set of latent graphs, each of which assumes the current utterance replies to one of the utterances in the previous conversation history as shown in Figure 3, are required and fed into the generative model to calculate the probabilities of generating a response under these latent graphs. This process typically consumes much computation resources. Thanks for your advice, more analysis of computational complexity will be included in the revision.\n\n\n3.Re: **evaluation metrics**\n\nThanks for your advice. As we described in Section 5.3, to ensure all experimental results were comparable, we used exactly the same automated and human evaluation metrics as those used in previous work (Hu et al., 2019; Gu et al., 2022). Evaluating the proposed method and various baselines using more other automated evaluation metrics might shed light on comprehensive evaluation, which will be part of our future work.\n\n\n4.Re: **comparison with LLM**\n\nThanks for your advice. In fact, we have already studied the application of LLMs to multi-party conversations, which aims at evaluating if LLMs show great performance on this task as comprehensively as possible. Some preliminary results and conclusions have been obtained but not yet finalized. This part of work is still in progress, and hopefully will be released to the community soon.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. A new method called MADNet for generating multi-party conversations using graph neural networks, even when addressee labels are missing.\n2. A novel approach to maximizing addressee deduction expectation by designing additional latent edges in the graph.\n3. An extensive evaluation of MADNet on the Ubuntu IRC channel benchmarks, showing that it outperforms various baseline models in terms of both automatic and human evaluations.\n4. A detailed analysis of the impact of different design choices on the performance of MADNet, providing insights for future research in this area.", "reasons_to_reject": "1. The paper only evaluates the proposed method on two benchmarks, which may not be representative of all possible multi-party conversation scenarios. \n2. The paper does not provide a detailed analysis of the computational complexity of the proposed method, which may be a concern for large-scale applications.", "questions_to_authors": "1. Have you considered any other evaluation metrics besides BLEU, METEOR, and ROUGE-L, which are commonly used in the literature?\n2. Can you provide more details on the computational complexity of the proposed method and how it scales with the size of the input data?\n3. Can you try to use LLMs in comparison to your work?", "paper_topic_and_main_contributions": "This paper proposes a new method for generating multi-party conversations using graph neural networks, even when addressee labels are missing. By maximizing addressee deduction expectation and designing additional latent edges, MADNet outperforms various baseline models. It uses an Expectation-Maximization (EM) algorithm to iteratively generate silver addressee labels and optimize the quality of generated responses. In particular, the paper uses a Hard EM method that selects the addressee with the highest probability as the silver label. The maximization step is approximated as log P (r, GU_i→U_j|c; θ). Once the silver addressee label is determined in this round, its corresponding MPC graph is employed for regular training by minimizing the negative log-likelihood loss of responses", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oLV6WX6Ygc", "reviewer": "Reviewer_rqCf", "summary": "", "questions": "* Do you have qualitative examples of responses generated by MADNet in each ablation scenario? Contrasting them with complete responses, would help readers grasp the practical significance of the ablations. Similarly, providing a qualitative analysis / example responses of how the performance evolves with different number of EM iterations would also help.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable suggestions! We are so excited to receive many encouraging reviews and constructive suggestions. We will try our best to respond to the raised issues and will implement the suggested improvements in our revision.\n\n\n1.Re: **problem significance and novelty**\n\nFirst, the scarcity of addressee labels is a common issue in multi-party conversations. In detail, as we described in line 69-71, statistics show that addressees of 55% of the utterances in the Ubuntu IRC dataset (Ouchi and Tsuboi, 2016) are not specified. \n\nSecond, existing methods rely heavily on the complete and necessary addressee labels, and can only be applied to an ideal setting where each utterance must be tagged with an “@” or other equivalent addressee label. As illustrated in Figure 1, given an MPC with a few addressee labels missing, existing methods fail to build a consecutively connected conversation graph, but only a few separate conversation fragments instead. Therefore, nodes without direct connections cannot exchange information between each other through one-hop message passing. Inevitable information loss and passing latency will affect generation performance significantly. But this common and challenging issue has not been studied in previous work.\n\nThird, empirical experiments in Section 5.4 and case study in Section 5.5 show that existing methods cannot handle the addressed problem. Besides, these results illustrated the effectiveness of our proposed method MADNet in modeling MPC structures and message passing between the utterance and interlocutor nodes in an MPC graph.\n\nIn summary, as we highlight at the end of the Section of related work, existing methods target only on an ideal setting where addressee labels of all utterances are necessary, while the proposed method is suitable for more common conversation sessions where a few addressee labels are missing. To the best of our knowledge, this paper makes the first attempt to extend to more common MPC scenarios and to explore the issue of missing addressee labels by maximizing addressee deduction expectation for MPC generation. Thanks for your advice, we will clarify the significance of the problem and the novelty of the method in our revision.\n\n\n2.Re: **choice of employing EM for addressee deduction**\n\nAddressee labels are an important component of the MPC context, and the empirical experiments show that the missing part of addressee labels will affect the generation performance in turn. Intuitively, it is natural to model the addressee of an utterance without a golden addressee label as a discrete latent variable, and to employ EM for addressee deduction and response generation. In addition, Equations (2)-(5) in Section 4.2 further provide a robust theoretical grounding for the choice of employing EM. Thanks for your advice, comparisons with alternative approaches to addressing the scarcity of addressee labels and to mitigating their effect on MPC generation will be part of our future work.\n\n\n3.Re: **qualitative examples**\n\nThe current submission has presented the quantitative results of various ablation and analysis experiments. Thanks for your advice, more qualitative examples of these corresponding experiments will be included in the revision to help readers better understand the effectiveness of each component of the proposed method.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Effective Addressee Deduction: The paper's proposes an interesting incorporation of Expectation-Maximization (EM) for accurate addressee deduction. The experiments demonstrate the effectiveness of the approach in both automated evaluation metrics (BLEU, METEOR, ROUGE) and human evaluation.\n* Comprehensive Experimental Analysis: The paper's experiments include evaluations on two diverse benchmarks, showcasing the generalizability of their approach. Comparative analysis includes both non-graph-based (GPT-2, BART) and graph-based (GSN, HeterMPC) models, and is strong enough to highlight MADNet's effectivness.\n* Ablation Studies: The ablation experiments conducted to analyze the contributions of different model components (e.g., latent-reply, latent-address edges) provide valuable insights into the proposed approach. The authors have done a good job of systematically isolating these components, to demonstrate their individual impact on response generation, which support the modeling choices.\n* Human Evaluation and Real-World Applicability: The paper incorporates human evaluation, assessing the quality of generated responses in terms of relevance, fluency, and informativeness.", "reasons_to_reject": "* Problem Significance and Novelty: The paper failed to establish a clear and compelling case for the significance of the addressed problem, specifically the challenges posed by multi-party conversation context. While the proposed EM-based addressee deduction is innovative, the paper did not thoroughly demonstrate the real-world impact of accurate addressee prediction in enhancing response quality. \n* The paper should provide a robust theoretical grounding for the choice of employing EM for addressee deduction. While EM is a well-established optimization technique, its application in the specific context of multi-party conversation graphs requires lacks solid justification. Comparisons with alternative approaches, such as more advanced graph neural networks or hierarchical attention mechanisms, would bolster the methodological choices and theoretical foundation of MADNet.", "questions_to_authors": "* Do you have qualitative examples of responses generated by MADNet in each ablation scenario? Contrasting them with complete responses, would help readers grasp the practical significance of the ablations. Similarly, providing a qualitative analysis / example responses of how the performance evolves with different number of EM iterations would also help.", "paper_topic_and_main_contributions": "The paper presents MADNet, an approach for multi-party conversation generation, addressing the issue of missing addressee labels. The authors propose constructing a fully-connected graph for effective context aggregation, employ an EM algorithm for addressee deduction, and initialize addressees using domain adaptation. The claims are validated empirically and showcase MADNet's superiority in generating responses for multi-party conversations, particularly under scenarios with incomplete addressee information.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a multi-party conversation generation model that is speaker-aware and works when speaker annotation is missing.

Reviewers appreciated the realistic setting where speaker labels could be missing. There was strong consensus on the soundness of the paper.

Some of the critical suggestions include:
- Better details on the human evaluation setup.
- Improved description of the graph-neural network.
- Enhanced discussion on complexity analysis.
- Baselines suggested by reviewers.

These changes should be incorporated in the revision as promised by the authors.
Decision: Accept-Main