Abstract
Answering complex questions over massive Knowledge Graphs (KGs) is a significant challenge due to the computational intensity of reasoning over large subgraphs. We present SQALER (Scaling Question Answering by Leveraging Edge Relations), a framework that decouples multi-hop reasoning from logical refinement. By operating on a coalesced graph representation, SQALER achieves high scalability and state-of-the-art performance on complex reasoning benchmarks, handling graphs with millions of entities efficiently.
Introduction
Knowledge-Based Question Answering (KBQA) involves retrieving answers to natural language queries from structured Knowledge Graphs. While Graph Neural Networks (GNNs) have shown promise in this domain, they face severe scalability bottlenecks. In large-scale KGs like Freebase, even a small neighborhood around a query entity can contain tens of thousands of edges. Since GNN complexity typically scales with the number of edges, processing these subgraphs often leads to prohibitive memory and time requirements.
Methodology
SQALER addresses the scalability bottleneck by splitting the QA process into two distinct stages: relation-level multi-hop reasoning and edge-level logical refinement.
1. Relation-Level Model (Multi-Hop Reasoning)
The core innovation of SQALER is the use of a coalesced graph representation ($\tilde{\mathcal{G}}_Q$). In this representation, all edges sharing the same relation type are merged into a single abstract edge. This drastically reduces the search space, as the model now scales with the number of unique relation types rather than the total number of edges.
A BERT-based encoder-decoder architecture acts as a "knowledge seeker." The encoder processes the natural language question, while the decoder predicts the sequence of relations required to reach the answer. This stage identifies a set of candidate answer nodes ($\tilde{\mathcal{A}}_Q$) with high efficiency.
2. Edge-Level Model (Logical Reasoning)
After identifying candidate answers, SQALER extracts a highly specific, minimal subgraph. A standard GNN-based edge-level model ($\psi$) is then applied to this subgraph to perform precise logical operations, such as intersections or filtering, to determine the final answer set ($\mathcal{A}_Q$).
The authors demonstrate that this two-stage approach maintains the expressive power necessary to answer any Existential Positive First-Order (EPFO) query.
Experimental Evaluation
SQALER was evaluated across several benchmarks, including MetaQA, WebQuestionsSP (WebQSP), and Compositional Freebase Questions (CFQ).
Key Results
- State-of-the-Art Performance: SQALER achieved 76.1% Hits@1 on WebQSP, surpassing previous state-of-the-art models. On MetaQA, the relation-level model alone achieved near-perfect accuracy (99.9%).
- Scalability: In stress tests, SQALER maintained high throughput on graphs with up to 1,000,000 entities, whereas baseline models like GRAFT-Net failed due to memory constraints at 10,000 entities.
- Compositional Generalization: On CFQ, SQALER reached 67.1% mean accuracy, matching SOTA semantic parsers without requiring explicit training on SPARQL queries.
- Robustness: The model remained effective even on incomplete KGs, outperforming specialized baselines when 50% of edges were removed.
Conclusion
SQALER provides a scalable and effective framework for KBQA by decoupling the search for relation paths from fine-grained logical reasoning. By leveraging graph coalescing, it enables complex reasoning over enterprise-scale knowledge bases that were previously inaccessible to GNN-based methods. Future work includes exploring the model's performance on KGs with extremely high relation-type diversity and improving robustness against KG misinformation.
Summary updated