Source-linked AI summary
Learning Symmetric Collaborative Dialogue Agents with Dynamic Knowledge Graph Embeddings
He He, Anusha Balakrishnan, Mihail Eric, Percy Liang
TL;DR
Existing dialogue systems struggle to represent open-ended, pragmatic communication while retaining structured knowledge for collaborative tasks. The paper introduces a symmetric private-knowledge dialogue setting, collects 11K human-human dialogues, and proposes DynoNet with dynamic knowledge-graph embeddings. Evaluations report that DynoNet performs the task with humans efficiently and naturally and captures some human conversational strategy.
Problem
Open-ended collaborative dialogue requires richer states and pragmatic acts than predefined task-oriented states, while open-domain models lack structured dialogue state.
Method
DynoNet models dialogue state as a knowledge graph with recurrently updated node embeddings, adding nodes and propagating context as utterances arrive.
Results
DynoNet performs the task with humans efficiently and naturally and captures some strategic aspects of human-human dialogues.
Takeaways & Limitations
The symmetric collaborative setting and dataset support studying pragmatics and human strategies in dialogue, including more complex interactions such as negotiation.
Takeaways & Limitations
The model is mostly accurate for single-entity facts and existence questions but needs a more advanced attention mechanism for utterances involving multiple entities.
Abstract
from arXiv · showhide
We study a symmetric collaborative dialogue setting in which two agents, each with private knowledge, must strategically communicate to achieve a common goal. The open-ended dialogue state in this setting poses new challenges for existing dialogue systems. We collected a dataset of 11K human-human dialogues, which exhibits interesting lexical, semantic, and strategic elements. To model both structured knowledge and unstructured language, we propose a neural model with dynamic knowledge graph embeddings that evolve as the dialogue progresses. Automatic and human evaluations show that our model is both more effective at achieving the goal and more human-like than baseline neural and rule-based models.
1 Introduction
The paper introduces a symmetric collaborative dialogue setting that combines private structured knowledge with open-ended, strategically meaningful communication. It proposes DynoNet, a dynamic knowledge-graph model, and reports effective, natural human interaction alongside a large human-human dialogue corpus.
- Motivation: Existing task-oriented systems rely on predefined dialogue states and acts, while open-domain systems lack structured states for grounded tasks.The paper identifies a gap between structured grounding and open-ended language.
- Problem setting: Two agents with private item lists must communicate to identify their unique shared item, requiring pragmatic interpretation beyond literal information requests.The example illustrates conversational implicature and diverse semantics such as “most of” and “might be.”
- Approach: DynoNet represents dialogue state as a dynamically evolving knowledge graph whose node embeddings update with utterances and support attention-based generation.New nodes and contextual information propagate through the graph as dialogue proceeds.
- Results: DynoNet performs the task with humans efficiently and naturally and captures some strategic aspects of human-human dialogue.Evaluation included automatic measures, third-party ratings, and partner ratings against neural and rule-based baselines.
- Contributions: The work contributes a symmetric collaborative setting, a dialogue corpus, DynoNet, and evaluation methods spanning bot-bot chat and human judgments.The evaluations compare third-party and partner perspectives as well as neural and rule-based systems.
2 Symmetric Collaborative Dialogue
The paper defines a two-agent task in which private knowledge bases must be reconciled through dialogue, then describes crowdsourced data designed to elicit varied language and strategy. The resulting corpus contains diverse semantics, communication phenomena, and strategic behaviors relevant to flexible dialogue modeling.
- 2.1 Task Definition: Each agent has a private knowledge base of attributed items, and success requires both agents to identify and select their unique shared item.The formal agent maps its private knowledge base and dialogue history to an utterance or selection.
- 2.2 Data collection: Scenarios vary item counts from 5 to 12, attribute counts from 3 to 4, and attribute-value distributions from skewed to uniform.The schema contains 7 attributes and approximately 3K entities or attribute values.
- 2.2 Data collection: Workers were randomly paired on Amazon Mechanical Turk for five-minute tasks, with selection attempts restricted to once every 10 seconds.The interface supported the chat-based collaborative task, while over-time dialogues were logged as unsuccessful.
- 2.3 Dataset statistics: The corpus contains 11K dialogues, of which over 9K are successful, while unsuccessful cases usually result from a worker leaving prematurely.The collection lasted 13.5 hours.
- 2.3 Dataset statistics: Utterances include standard and open-ended types, with 7.4% classified as multitype and 30.9% containing more than one entity.Open-ended examples require richer logical forms than traditional slot-value representations.
- 2.3 Dataset statistics: The dataset exhibits coreference, dropped mentions, external-knowledge grouping, and cross-talk in 30% of utterances.These phenomena make dialogue non-linear and connect utterance meaning to conversational context.
- 2.3 Dataset statistics: People tend to mention attributes with fewer unique values first, because these attributes can exclude candidate items more quickly.This ordering behavior is presented as a strategic aspect of the task.
3 Dynamic Knowledge Graph Network
DynoNet represents open-ended dialogue with a dynamic graph that combines private knowledge, dialogue context, and recurrent message passing. An LSTM then generates utterances by attending to evolving node embeddings.
- Model overview: The model combines a dynamic knowledge graph, graph embeddings, and an utterance generator to represent open-ended dialogue states.The graph represents the agent’s private knowledge base and shared dialogue history, while graph embeddings integrate structured and unstructured context.
- Graph embedding: Utterance information updates embeddings of mentioned entities and propagates recursively to neighboring nodes through the knowledge-graph structure.Message passing uses relation-aware neighbor embeddings and element-wise max aggregation; the model experiments with depths K ∈ {0, 1, 2}.
- Dynamic knowledge graph: Each graph contains item, attribute, and entity nodes connected by relations from the agent’s private knowledge base and dialogue history.Graphs are updated over turns, adding nodes for entities mentioned in an utterance but absent from the private knowledge base.
- Graph embedding: Node representations concatenate structural features, dialogue-derived mention vectors, and embeddings from multiple message-passing depths.Structural features include node degree, node type, and whether the node was mentioned in the current turn; mention vectors retain or update contextual information by turn.
- Utterance embedding: An encoder LSTM converts each utterance into an embedding that updates relevant node representations, while entity abstraction uses type and current node information.The abstraction reduces dependence on entity identity by representing linked entities through their type embedding and current node embedding.
- Utterance generation: A decoder LSTM generates the next utterance from attention-weighted node embeddings and can copy entities from the graph into the output.The output distribution covers both vocabulary words and graph nodes, with node realizations such as “google” becoming “Google.”
4 Experiments
The experiments compare DynoNet with neural and rule-based baselines through automatic and human evaluations of dialogue quality, effectiveness, strategy, and partner satisfaction. DynoNet generally produces diverse, human-like, cooperative dialogue while retaining task effectiveness, though Rule is more correct and comparable in success.
- Evaluation setup: DynoNet is evaluated against StanoNet and Rule in bot-bot and bot-human settings using automatic and human measures.The evaluations cover fluency, correctness, cooperation, human-likeness, language variation, effectiveness, and strategy.
- Automatic evaluation: DynoNet has the lowest test loss and generates shorter but more diverse utterances than Rule.Language variation is measured with average utterance length Lu and unigram entropy H.
- Automatic evaluation: Neural models learn utterance-type distributions that more closely resemble human behavior, frequently informing and asking questions.Rule’s action choices are specified by rules, whereas StanoNet and DynoNet learn these discourse patterns.
- Automatic evaluation: Humans lead in overall success, while Rule is comparable to DynoNet and achieves higher selection success through less information-efficient behavior.Rule mentions almost twice as many entities as humans and DynoNet to achieve similar success rates.
- Strategy: DynoNet and StanoNet match humans’ starting strategy by favoring frequent entities and attributes with smaller domains.The analysis compares first-mentioned entity frequency and the number of unique values for first-mentioned attributes.
- Human evaluation: DynoNet receives especially strong partner-satisfaction and cooperation evaluations, but third-party correctness favors Rule because it always tells the truth.Partner correctness judgments are limited because evaluators cannot see the partner’s knowledge base, and DynoNet can generate false facts.
- Ablation studies: Ablations show that removing message passing or entity abstraction increases loss, supporting contextually defined structural node embeddings.The message-passing depth is reduced from K = 2 to K = 0 in the ablation, while entity abstraction removes entity embeddings from node and LSTM inputs.
5 Discussion and Related Work
The work addresses limitations of existing task-oriented and open-domain dialogue systems by combining a scalable collaborative setting, a new corpus, and dynamic knowledge-graph representations. The authors position the dataset and DynoNet as resources for studying pragmatics, human strategies, and more complex dialogue.
- Related work: Collaborative dialogues offer natural human conversations, diverse scenarios, and challenging phenomena while remaining easier to collect than many existing task-oriented datasets.Prior strategic dialogue datasets were smaller, and no full dialogue system had been built for those datasets.
- Related work: Handcrafted slots limit task-oriented systems’ scalability to new domains and require additional state labeling, while unstructured memory lacks structured knowledge.The paper contrasts POMDP-based systems with a Memory-Networks-based approach without domain-specific features.
- Limitations: DynoNet remains vulnerable to false or contradictory statements involving multiple entities and needs a more advanced attention mechanism.The paper reports mostly accurate single-entity facts and existence questions but identifies multi-entity generation as a limitation.
- Discussion: DynoNet combines knowledge-graph structure with flexible dialogue representations to address open-ended dialogue-state modeling.Its proposed representation is framed as an interface between traditional task-oriented dialogue and open-domain chat.
- Discussion: The dataset supports research on pragmatics and human dialogue strategies, with negotiation identified as a more complex direction.The authors describe the setting and corpus as a stepping stone toward studying complex dialogues.
A Knowledge Base Schema
The MutualFriends knowledge base represents items through attributes and entity values, while scenarios vary task complexity and value distributions. Human dialogues are collected under constraints and annotated with rule-based entity and utterance processing.
- Schema: Each MutualFriends item has values for attributes drawn from a schema containing name, school, major, company, hobby, time-of-day, and location preferences.Time-of-day has morning, afternoon, and evening values; location has indoors and outdoors values.
- Scenario generation: Scenarios vary the number of items from 5 to 12 and the number of attributes from 3 to 4.Attributes are sampled without replacement from the full attribute set.
- Scenario generation: Attribute-value distributions are generated with concentration parameters 0.3, 1, or 3, then sampled into two knowledge bases.Generation repeats until the knowledge bases contain exactly one unique common item.
- Data collection: Human participants are randomly paired, assigned separate knowledge bases, instructed to avoid brute-force tactics, and given five minutes to complete each dialogue.Successful dialogues earned workers $0.35, and utterances were logged with timing information.
- Processing: A rule-based lexicon links spans to entities by generating name variants, matching candidates, and selecting the highest-scoring candidate with a heuristic ranker.Linked entities are treated as single tokens, with surface forms sampled during generation.
- Processing: Utterances are heuristically categorized as inform, ask, answer, greeting, or apology using pattern matching.Ask detection uses question marks or question words, while inform detection identifies knowledge-base entities in non-ask utterances.
F Strategy
The study varies scenario complexity and attribute-value skewness to examine how these factors affect dialogue difficulty and strategy. Humans preferentially begin with attributes whose values are more skewed.
- Strategy and difficulty: Increasing the number of items or attributes increases dialogue length and completion time, indicating greater task difficulty.The experiment varies item count, attribute count, and value-distribution concentration.
- Human strategy: Humans tend to first mention attributes with more skewed, less uniform value distributions.Attributes are grouped as least uniform, medium, or most uniform after ranking their α values.
- Human strategy: For four-attribute scenarios, the two middle-ranked attributes are grouped together as medium rather than separated.Three-attribute scenarios assign one attribute to each distribution group.
G Rule-based System
The rule-based bot combines weighted entity selection with fixed dialogue actions, heuristic parsing, templates, and turn-taking limits. Its weights update based on partner mentions and related entities.
- Actions and weighting: The bot greets, informs or asks about entities, answers questions, and selects items using randomly sampled entity sets.Initial entity weights equal their counts in the knowledge base.
- Actions and weighting: Partner mentions increment or decrement weights for mentioned entities and related entities according to positive or negative evidence.Related entities are those in the same row or column.
- Selection and responses: When an item exceeds weight 1, the bot selects the highest-weighted item with probability 0.3.For received questions, it informs facts about the queried entities; otherwise it randomly chooses whether to inform or ask.
- Generation and parsing: All bot utterances use sentence templates, while partner utterances are parsed through entity linking and pattern matching.This design supports the rule-based system’s fixed action and interpretation pipeline.
- Turn-taking: The bot is limited to one entity-containing utterance or two entity-free utterances per turn, with delays between multiple utterances.These constraints prevent continuous generation and monologues.
I Additional Human-Bot Dialogue
In additional human-bot dialogues with more uniform value distributions, StanoNet and DynoNet still favor relatively high-frequency entities and appear more cooperative than Rule.
- Observed dialogue behavior: In scenarios with more uniform value distributions, StanoNet and DynoNet still begin with relatively high-frequency entities.The comparison is reported from another set of human-bot and human-human chats.
- Observed dialogue behavior: StanoNet and DynoNet appear more cooperative and mention entities relevant to the dialogue context more often than Rule.This observation is reported for the additional dialogue examples.
J Histograms of Ratings from Human Evaluations
Partner ratings distinguish DynoNet from the other systems, with DynoNet rated better overall and especially in cooperation. These ratings reflect how dialogue participants perceive their partners and what they consider human-like or fluent.
- DynoNet is rated better than all other systems by dialogue partners.
- Partner ratings provide insight into perceived human-likeness and fluency in this dialogue setting.
K Example Comments from Partner and Third-party Evaluations
Partner and third-party evaluations can diverge because they emphasize different aspects of the same dialogue. Partners focus more on cooperation and strategy, while third parties rely more on linguistic features, and their system differences are less significant.
- Partners judge dialogue from cooperation and strategy perspectives, whereas third parties emphasize linguistic features.Third-party features include length, spelling, and formality.
- Example human-bot chats include highlighted mutual friends, bold bot utterances, and item IDs for selected items.The first half of the human-Rule chat is shown because of space limits.
- Third-party ratings show less significant differences between systems than partner ratings.
- The evaluation compares ratings and human-likeness comments for the same dialogues from partners and third-party evaluators.Table 9 presents paired ratings and comments for each dialogue.