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