Using Local Knowledge Graph Construction to Scale Seq2Seq Models to Multi-Document Inputs

Angela Fan, Claire Gardent, Chloé Braud, Antoine BordesEMNLP 2019 · DOI

TL;DR

This paper tackles the challenge of synthesizing information from vast, multi-document web sources for tasks like question answering and summarization. They propose constructing a local knowledge graph from query-specific web results, linearizing it into a sequence, and feeding it to Seq2Seq models. This approach significantly compresses information and improves performance over traditional methods.

What Problem Does This Paper Address?

Modern NLP tasks, especially those involving open-domain question answering and multi-document summarization, often require processing immense amounts of text from diverse web sources. Current methods typically rely on extractive techniques (like TF-IDF) to select relevant text snippets, which are then fed into Seq2Seq models. However, these models struggle to handle the sheer volume of information, often limited to a few thousand words, leading to information loss and suboptimal performance. The core problem is effectively distilling and synthesizing knowledge from noisy, redundant, and lengthy web inputs for abstractive generation.

Methods

The authors introduce a novel approach centered around constructing a local knowledge graph for each query. This process involves:

  1. Coreference Resolution and Open Information Extraction (OIE): Sentences from web search results are processed to identify entities and their relationships, forming triples (subject, predicate, object).
  2. Graph Construction: These triples are used to build a graph where subjects and objects become nodes, and predicates become directed edges. Nodes and edges are assigned weights based on their frequency of appearance.
  3. Merging and Filtering: To reduce redundancy and noise, nodes and edges are merged if they represent similar concepts. TF-IDF overlap with the query is used to filter out irrelevant information, such as HTML tags.
  4. Linearization: The constructed graph is then linearized into a structured sequence format (subject, object, predicate) to be compatible with standard Seq2Seq models.
  5. Attribute Embeddings: To retain crucial graph information lost during linearization, the authors incorporate Graph Weight (GW) and Query Relevance (QR) embeddings alongside word and position embeddings. These are learned through gating mechanisms to allow the model to dynamically weigh their importance.
  6. Hierarchical Attention: To handle the potentially long linearized graph sequences, they employ a hierarchical top-k attention mechanism. This allows the model to focus on the most relevant parts of the graph based on the query.
  7. Memory-Compressed Attention (MCA): To scale Seq2Seq models to encode the entire linearized graph (which can still be thousands of tokens), they adapt the MCA mechanism for the encoder, enabling efficient processing of longer sequences.
  8. Multi-task Training: The models are trained using multi-task learning, including knowledge graph completion, to leverage the benefits of language modeling.

Datasets

The paper evaluates its approach on two existing datasets:

  • ELI5 (Explain Like I'm Five): A dataset for long-form question answering, featuring complex questions and multi-sentence explanatory answers. It provides the top 100 web search results for each question.
  • WikiSum CommonCrawl: A dataset for multi-document summarization, specifically for generating Wikipedia lead paragraphs from cited article references and queried web content.

Key Insights and Ideas

  • Knowledge Graphs as an Effective Compression Mechanism: Constructing a local knowledge graph dramatically reduces the input size (by an order of magnitude) while retaining more relevant information than traditional TF-IDF extraction. This compression is crucial for enabling Seq2Seq models to process the entirety of the information.
  • Graph Attributes are Crucial: Simply linearizing a graph isn't enough. Incorporating graph attribute embeddings (like node/edge weights and query relevance) significantly improves performance, allowing the model to understand the structure and importance of information.
  • Hierarchical Attention for Focused Processing: The hierarchical attention mechanism is key to making sense of the linearized graph, enabling the model to pinpoint the most relevant information without being overwhelmed by the sequence length.
  • Robustness to Search Result Ordering: The graph-based approach is shown to be more robust to the ordering of web search results, suggesting that the inherent structure of the graph is more important than the precise ranking of individual documents.

Key Results

  • Improved Performance: The proposed graph-based approach consistently outperforms baselines on both ELI5 and WikiSum datasets, achieving statistically significant improvements in ROUGE scores. For instance, on ELI5, the graph-based model with E-MCA achieved a ROUGE-1 score of 30.0, outperforming TF-IDF baselines. On WikiSum, it reached 36.5 ROUGE-L.
  • Answer Token Coverage: The graph construction method retains more answer tokens compared to TF-IDF extraction, even when the graph input is compressed to match the length of TF-IDF extracted text.
  • Human Evaluation: Human evaluations favored the graph-based model over a multi-task baseline, with 57.4% of evaluations preferring the graph approach.

Limitations and Future Work

  • Scalability of Graph Construction: While the graph construction significantly compresses input, encoding the entire linearized graph still requires models to handle sequences of up to 10K tokens, pushing the limits of Transformer attention. The MCA mechanism helps, but further scaling is always a consideration.
  • Graph Network Integration: The authors note that they leave the incorporation of graph neural networks (GNNs) for future work, suggesting this could be a promising avenue for directly modeling graph structures.
  • Focus on Local Graphs: The current approach builds local knowledge graphs per query. Future work could explore how to integrate these local graphs into a broader, global knowledge base or how to leverage external knowledge graphs.
  • Interpretability: While the paper demonstrates interpretable attention on subgraphs, further work could explore deeper interpretability of the graph construction and modeling process.

Summary updated

BibTeX
@inproceedings{fan2019using,
  author = {Angela Fan and Claire Gardent and Chloé Braud and Antoine Bordes},
  title = {{Using Local Knowledge Graph Construction to Scale Seq2Seq Models to Multi-Document Inputs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2019},
  doi = {10.18653/v1/d19-1428},
}
Figure