Unsupervised Learning of Deterministic Dialogue Structure with Edge-Enhanced Graph Auto-Encoder

Yajing Sun, Yong Shan, Chengguang Tang, Yue Hu, Yinpei Dai, Jing Yu, Jian Sun, Fei Huang, Luo SiAAAI 2021 · OpenReview

Abstract

It is important for task-oriented dialogue systems to discover the dialogue structure (i.e. the general dialogue flow) from dialogue corpora automatically. Previous work models dialogue structure by extracting latent states for each utterance first and then calculating the transition probabilities among states. These two-stage methods ignore the contextual information when calculating the probabilities, which makes the transitions between the states ambiguous. This paper proposes a conversational graph (CG) to represent deterministic dialogue structure where nodes and edges represent the utterance and context information respectively. An unsupervised Edge-Enhanced Graph Auto-Encoder (EGAE) architecture is designed to model local-contextual and global-structural information for conversational graph learning. Furthermore, a self-supervised objective is introduced with the response selection task to guide the unsupervised learning of the dialogue structure. Experimental results on several public datasets demonstrate that the novel model outperforms several alternatives in aggregating utterances with similar semantics. The effectiveness of the learned dialogue structured is also verified by more than 5% joint accuracy improvement in the downstream task of low resource dialogue state tracking.

Introduction

In task-oriented dialogue systems, such as those used for booking flights or restaurant reservations, understanding the underlying logical flow is crucial. Traditionally, these structures were hand-crafted by developers, a process that is both labor-intensive and difficult to scale across diverse domains. Recent research has pivoted toward unsupervised methods to automatically discover these structures from dialogue corpora.

However, existing unsupervised approaches, such as Variational Recurrent Neural Networks (VRNNs), typically follow a two-stage process: clustering utterances into latent states and then calculating transition probabilities between those states. A significant drawback of this approach is the neglect of session-specific context, which leads to ambiguous transitions. For instance, a user saying "I would like Italian food" might lead to different system responses depending on whether the price range or area has already been established in that specific session.

Deterministic Dialogue Structure

To address the ambiguity in probabilistic models, this paper introduces a Conversational Graph (CG) where transitions are deterministic. The core innovation lies in treating context not just as a node property, but as a dynamic edge feature.

Comparison between probabilistic transitions in VRNN (a) and deterministic transitions in the proposed model (b).

As shown in Figure 1, while a probabilistic model might assign split probabilities to multiple potential next states, the proposed model uses context-aware edges to resolve this ambiguity, ensuring a more accurate and deterministic representation of the dialogue flow.

Proposed Architecture: EGAE

The framework consists of two primary modules: the Semantics Understanding Module (SUM) and the Structure Induction Module (SIM).

The overall architecture of the proposed framework, featuring the Semantics Understanding Module and the Structure Induction Module.

Semantics Understanding Module (SUM)

The SUM acts as the perception layer, utilizing a pre-trained BERT model to encode utterances and their immediate contexts into high-dimensional vectors. It constructs session-specific sub-graphs that capture the local progression of a single conversation, effectively mapping how one turn leads to the next within a specific session.

Structure Induction Module (SIM)

The SIM serves as the reasoning layer, integrating local information into a global Conversational Graph. The key component is the Edge-Enhanced Graph Auto-Encoder (EGAE). Unlike standard Graph Auto-Encoders that focus solely on updating node features, the EGAE explicitly updates edge features. This allows the model to learn that the relationship between two semantic states is defined by the specific context of the dialogue.

To guide this unsupervised learning process, the authors employ a self-supervised Response Selection task. By training the model to identify the correct next response from a set of candidates, the system learns meaningful representations of dialogue structure without requiring manual labels.

Experimental Results

The model was evaluated on several benchmark datasets, including CamRest676, DSTC2, and the Schema-Guided Dialogue (SGD) dataset.

Clustering and Structural Discovery

The proposed model demonstrated a significant leap in clustering performance. On the CamRest676 dataset, the Calinski-Harabasz (CH) index—a measure of cluster quality—rose from 6.47 for the VRNN baseline to 639.39. This indicates that the model is far more effective at aggregating utterances with similar semantic and structural roles.

Downstream Impact: Dialogue State Tracking

The practical utility of the learned structure was tested in a low-resource Dialogue State Tracking (DST) scenario using the WOZ 2.0 dataset. When the discovered structure was integrated into a state-of-the-art DST model (SUMBT) with only 10% of the training data, the Joint Accuracy improved by 6.36%. This suggests that the global structural understanding provided by the Conversational Graph helps the model better track user goals when data is scarce.

Conclusion

This research presents a novel approach to unsupervised dialogue structure induction by modeling deterministic transitions through an Edge-Enhanced Graph Auto-Encoder. By treating context as an edge feature, the model resolves the ambiguities inherent in previous probabilistic methods. Future work will focus on handling the noise present in human-to-human dialogues and developing methods to dynamically determine the optimal complexity of the discovered graphs.

Summary updated

Abstract

It is important for task-oriented dialogue systems to discover the dialogue structure (i.e. the general dialogue flow) from dialogue corpora automatically. Previous work models dialogue structure by extracting latent states for each utterance first and then calculating the transition probabilities among states. These two-stage methods ignore the contextual information when calculating the probabilities, which makes the transitions between the states ambiguous. This paper proposes a conversational graph (CG) to represent deterministic dialogue structure where nodes and edges represent the utterance and context information respectively. An unsupervised Edge-Enhanced Graph Auto-Encoder (EGAE) architecture is designed to model local-contextual and global-structural information for conversational graph learning. Furthermore, a self-supervised objective is introduced with the response selection task to guide the unsupervised learning of the dialogue structure. Experimental results on several public datasets demonstrate that the novel model outperforms several alternatives in aggregating utterances with similar semantics. The effectiveness of the learned dialogue structured is also verified by more than 5\% joint accuracy improvement in the downstream task of low resource dialogue state tracking.
BibTeX
@inproceedings{sun2021unsupervised,
  author = {Yajing Sun and Yong Shan and Chengguang Tang and Yue Hu and Yinpei Dai and Jing Yu and Jian Sun and Fei Huang and Luo Si},
  title = {{Unsupervised Learning of Deterministic Dialogue Structure with Edge-Enhanced Graph Auto-Encoder}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=40HW4kvCcXy},
}
Figure