Interactive Machine Comprehension with Dynamic Knowledge Graphs

Xingdi Yuan

Abstract

Interactive Machine Reading Comprehension (iMRC) presents a challenge where agents must navigate a partially observable document to answer questions. Unlike static MRC, iMRC requires effective memory to track information across navigation steps. This paper introduces dynamic knowledge graphs as a structured inductive bias for agent memory. By constructing and updating graphs on-the-fly, agents can better capture semantic relationships. Experimental results on the iSQuAD dataset demonstrate that graph-aided agents significantly outperform baselines, with ensemble models achieving up to an 18.5% relative improvement in F1 score.

Introduction

Standard Machine Reading Comprehension (MRC) assumes full observability, where a model processes an entire context to extract an answer. However, real-world information seeking is often interactive and incremental. In iMRC, an agent starts with a question and a hidden document, revealing only one sentence at a time through actions like next, previous, or keyword searches (Ctrl+F).

The primary bottleneck in iMRC is memory. Recurrent neural networks or simple observation queues often struggle to maintain long-term dependencies or structural relationships between distant sentences. This work explores whether structured representations, specifically dynamic knowledge graphs, can serve as a more effective memory mechanism for navigating textual environments.

Methodology: Dynamic Knowledge Graphs as Memory

The proposed architecture equips a Reinforcement Learning (RL) agent with a Graph Updater and a specialized Encoder. As the agent explores the document, the Graph Updater incrementally builds a representation of the text seen so far.

Overview of the iMRC agent architecture, illustrating the interaction between the Information Gathering and Question Answering modules.

The authors evaluate four types of graph construction:

  1. Word Co-occurrence: A rule-based approach connecting words within the same sentence to link concepts across the document.
  2. Relative Position: A rule-based method encoding word order and distance to capture a loose structural prior.
  3. Semantic Role Labeling (SRL): A parser-based approach that identifies "who did what to whom," creating a high-level semantic map of events.
  4. Continuous Belief: A trainable neural approach using contrastive learning to maintain a latent graph state that can reconstruct current observations.

These graphs are processed using a Relational Graph Convolutional Network (R-GCN). The resulting graph embeddings are then fused with text embeddings using a context-query attention mechanism, allowing the Action Generator to make informed decisions based on both immediate observations and structured historical context.

Experimental Setup and Datasets

The models were tested on iSQuAD, an interactive variant of the SQuAD dataset. The environment offers two difficulty modes: Easy (where the agent can search for any word in the question or current sentence) and Hard (where the agent can search for any word in the entire vocabulary). The agents were also tested with varying numbers of "memory slots" to evaluate how structural bias compensates for limited raw memory.

Key Results and Discussion

The inclusion of dynamic knowledge graphs consistently improved performance across all configurations. As shown in the results table, graph-based agents outperformed the iMRC baseline, particularly in scenarios with limited memory.

Experimental results comparing the baseline iMRC model with various graph-based agents across different memory slot configurations and difficulty levels.

The Power of Structure and Ensembles

A key finding is that the ensemble of different graph types provides the most significant gains, nearly doubling the improvement of any single graph type. This suggests that rule-based, parser-based, and learned graphs capture complementary information. Furthermore, even when the agent was provided with a larger observation queue (5 slots), the addition of a graph still yielded a >8% improvement, proving that the structure of memory is as vital as its capacity.

Limitations in Large Action Spaces

While graph-based agents excelled in most settings, the "Vocab" action space in Hard Mode remains a challenge. When the agent must choose a search query from a 20,000+ word vocabulary, the sparse rewards make exploration difficult, leading to a performance drop compared to more constrained action spaces.

Conclusion

This research demonstrates that dynamic knowledge graphs provide a powerful inductive bias for agents in partially observable textual environments. By moving beyond flat text buffers to structured semantic maps, agents can more effectively navigate complex documents. Future work will focus on scaling these methods to multi-word queries and open-domain web navigation, potentially bridging the gap between sandbox iMRC and real-world information retrieval.

Summary updated

Abstract

Xingdi Yuan. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. 2021.
BibTeX
@inproceedings{yuan2021interactive,
  author = {Xingdi Yuan},
  title = {{Interactive Machine Comprehension with Dynamic Knowledge Graphs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=3PBOeP1pWWr},
}
Figure