Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables
2026-05-25 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors study a hard problem called Complex Query Answering, where the goal is to find the best answers that involve multiple variables from incomplete knowledge graphs. Existing methods usually look at each variable separately, which doesn’t give a good overall ranking when considering all variables together. They propose a new approach called NS3 that smartly combines and narrows down possible answers without checking everything exhaustively, making the problem more manageable. Their method improves how well the system ranks joint answers and they also provide a new test set for evaluating queries with up to three variables.
Complex Query AnsweringKnowledge GraphExistential First-Order QueriesJoint RankingMarginal RankingNeural Symbolic SearchEFO_k QueriesHypernodesCandidate PruningKnowledge Representation
Authors
Weizhi Fei, Hang Yin, Zihao Wang, Shukai Zhao, Wei Zhang, Yangqiu Song
Abstract
Complex Query Answering (CQA) is a fundamental knowledge representation and reasoning task over incomplete knowledge graphs (KGs). Answering existential first-order queries with $k$ free variables (i.e., $\text{EFO}_k$ queries) is a crucial yet challenging problem, as it requires ranking answer tuples in $\mathcal{E}^k$, where $\mathcal{E}$ denotes the entity set of a KG. This quickly becomes intractable as $k$ grows. Consequently, existing benchmarks and methods rely on marginal rankings over individual variables; however, marginal rankings are a poor proxy for the true joint ranking of tuples. Building on neural symbolic search for $\text{EFO}_1$ queries, we propose Neural Scalable Symbolic Search (NS3), a budgeted framework that approximates joint ranking without enumerating $\mathcal{E}^k$. NS3 (i) answers marginalized sub-queries to obtain necessary candidate sets, (ii) merges multiple free variables into hypernodes whose domains are pruned and controlled by a dynamic budget $B$, and (iii) progressively reduces an $\text{EFO}_k$ query to an $\text{EFO}_{k-1}$ query over a budgeted reduced domain. Across three standard KG datasets, NS3 substantially improves joint ranking performance while retaining strong marginal accuracy. We further release a joint-ranking benchmark that extends existing $\text{EFO}_1$ datasets to $k=3$, enabling systematic evaluation of multi-variable queries. Our code is provided in https://github.com/HKUST-KnowComp/NS3_KDD2026.