提出新方法提升知识图谱复杂查询的效率与可扩展性
Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering
- 用约束策略缩小变量搜索范围，降低数据复杂度
- 采用局部搜索近似求解循环查询，实现97%相对MRR
- 适合处理大规模知识图谱和复杂查询场景
复杂查询回答（CQA）是知识图谱中一项关键推理任务，旨在从不完整的知识图谱中回答一阶逻辑查询。现有神经符号方法虽表现优异，但存在显著复杂度瓶颈：数据复杂度随实体数量呈二次增长，循环查询的查询复杂度为NP难。为此，我们提出一种高效可扩展的符号搜索方法，包含两个核心组件：(1) 约束策略大幅缩减变量搜索域，降低数据复杂度；(2) 局部搜索算法近似求解NP难的循环查询。在多个CQA基准上的实验表明，对于树形查询，该方法在仅使用10%搜索空间的情况下，实现97%相对MRR并获得10倍速度提升。同时，在复杂循环查询和大规模知识图谱上也表现出稳健性能，有效缓解了效率与可扩展性挑战。代码已开源：https://github.com/HKUST-KnowComp/NLISA_KDD2026。
原文摘要 · Abstract (English)
Complex Query Answering (CQA) is a crucial reasoning task over Knowledge Graphs (KGs), which aims to answer first-order logical queries from incomplete KGs. While existing neural-symbolic methods achieve strong performance, they face significant complexity bottlenecks: quadratic data complexity scaling with the number of entities, and NP-hard query complexity for cyclic queries. Consequently, these approaches struggle to scale effectively to large knowledge graphs and complex queries. To address these limitations, we propose an efficient and scalable symbolic search method comprising two key components: (1) constraint strategies that drastically reduce the variable search domain, lowering data complexity; and (2) a local search algorithm that approximately solves NP-hard cyclic queries. Experiments on various CQA benchmarks demonstrate that, for tree-form queries, our method achieves 97% relative MRR with a 10$\times$ speedup using only 10% of the search space. Furthermore, it demonstrates robust performance on complex cyclic queries and large-scale KGs, effectively alleviating efficiency and scalability challenges. Our code is provided in https://github.com/HKUST-KnowComp/NLISA_KDD2026.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。