An Online Question Answering System based on Sub-graph Searching

Shuangyong SongarXiv 2021 · OpenReview

TL;DR

This paper tackles the challenge of slow response times in large-scale knowledge graph-based Question Answering (QA) systems. They propose an offline sub-graph indexing approach that restricts online search to smaller, relevant sub-graphs, significantly speeding up answer retrieval for entity-based questions while improving coverage.

What Problem Does This Paper Address?

Online Question Answering (QA) systems, especially those relying on vast knowledge graphs (KGs), face a critical trade-off between answer accuracy and response speed. Searching an entire KG for every user query is computationally expensive, leading to slow response times that degrade user experience. This is particularly problematic for entity-based QA, where identifying specific entities and their relationships is key. The paper aims to bridge this gap by enabling fast and accurate entity-based QA within a real-time online system.

Methods

The core innovation lies in an offline sub-graph extraction and indexing mechanism. Instead of searching the entire KG online, the system pre-processes the KG to create smaller, focused sub-graphs.

Here's a breakdown of their approach:

  • Offline Sub-graph Extraction:
    • They first identify "high-frequency entities" by analyzing historical user question logs. This focuses the system on entities that are most likely to be queried.
  • For each high-frequency entity, they extract a sub-graph from the complete KG. This sub-graph includes the entity and all entities directly linked to it. This is a key difference from some prior work that might perform this extraction in real-time.
  • Lucene Indexing: These extracted sub-graphs are then indexed using Lucene. This allows for efficient retrieval of relevant sub-graphs during online query processing.
  • Online QA:
    • When a user query arrives, entities are recognized.
  • The system then uses the Lucene index to quickly retrieve the relevant sub-graph(s) associated with these entities.
  • Answer generation is then restricted to operate within these smaller sub-graphs, significantly reducing the search space and computation.
  • They opt for a pattern-based answer generation method over more complex models like RNNs to maintain speed.

Datasets

  • Question Log Dataset: An anonymous online user question log collected from April 1, 2020, to April 31, 2020. This dataset contains 95.4 million user questions, which are de-duplicated to yield 28.6 million diverse questions.
  • High-Frequency Entities: 33,242 high-frequency entities (occurring more than 10 times) were identified from the question logs.
  • Knowledge Graph Source: Sub-graphs for these high-frequency entities are extracted from Wikipedia.

Key Insights and Ideas

  • Shifting the Computational Burden Offline: The most significant insight is moving the computationally intensive sub-graph extraction process offline. This allows the online system to focus on rapid retrieval and answer generation within a constrained search space.
  • The Power of "High-Frequency" Focus: By prioritizing sub-graphs around frequently asked entities, the system can achieve high coverage for common queries without needing to index the entire KG.
  • Sub-graph as a Search Constraint: Restricting answer generation to the sub-graph level is a clever way to maintain accuracy while drastically improving speed. It leverages the localized nature of many entity-based questions.
  • Practical Application in a Real System: The paper demonstrates the successful integration of this approach into Alibaba's existing online QA chat system (AliMe), highlighting its real-world applicability.

Key Results

  • Coverage Improvement: The sub-graph searching mechanism increased the coverage of the AliMe Chat system from 4.18% to 4.98%, a 19.14% increase.
  • Speed Improvement: The system achieves a speed of 18.2ms per QA, which is fast enough to meet online QA requirements.
  • Qualitative Example: The paper shows examples where the system correctly answers questions like "Which team Jianlian Yi belongs to?" and "Is T-MAC a scoring champion?" by leveraging the sub-graph approach.

Limitations and Future Work

  • Limitations:
    • The paper notes that questions containing more than one entity are handled by a separate method (referencing [3]) and are not treated with the sub-graph searching method. This suggests the current sub-graph approach might be primarily focused on single-entity questions.
  • While the sub-graph extraction is offline, the definition of "high-frequency" and the size of the extracted sub-graphs are parameters that could influence performance.
  • Future Work:
    • The authors plan to incorporate product knowledge graphs and service knowledge graphs into the main part of their QA system, suggesting an expansion beyond general knowledge graphs like Wikipedia. This indicates a move towards more domain-specific and specialized QA.

Summary updated

Abstract

Knowledge graphs (KGs) have been widely used for question answering (QA) applications, especially the entity based QA. However, searching an-swers from an entire large-scale knowledge graph is very time-consuming and it is hard to meet the speed need of real online QA systems. In this pa-per, we design a sub-graph searching mechanism to solve this problem by creating sub-graph index, and each answer generation step is restricted in the sub-graph level. We use this mechanism into a real online QA chat system, and it can bring obvious improvement on question coverage by well answer-ing entity based questions, and it can be with a very high speed, which en-sures the user experience of online QA.
BibTeX
@misc{song2021online,
  author = {Shuangyong Song},
  title = {{An Online Question Answering System based on Sub-graph Searching}},
  year = {2021},
  eprint = {2107.13684},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.13684},
}
Figure