





















Abstract: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 this https URL.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2505.08155 [cs.AI] |
| (or arXiv:2505.08155v4 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2505.08155 arXiv-issued DOI via DataCite |
From: Weizhi Fei [view email]
[v1]
Tue, 13 May 2025 01:24:09 UTC (754 KB)
[v2]
Sat, 17 May 2025 04:54:02 UTC (755 KB)
[v3]
Tue, 20 May 2025 12:09:36 UTC (755 KB)
[v4]
Mon, 25 May 2026 16:05:45 UTC (493 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。