Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables

Problem
This paper addresses the challenge of answering existential first-order queries with multiple free variables (denoted as $\text{EFO}_k$ queries) over incomplete knowledge graphs (KGs). Existing methods primarily focus on marginal rankings of individual variables, which inadequately represent the true joint ranking of answer tuples. This gap in capability is particularly pronounced as the number of free variables $k$ increases, leading to intractable search spaces. The authors present this work as a preprint, indicating it has not yet undergone peer review.

Method
The authors introduce the Neural Scalable Symbolic Search (NS3) framework, which approximates joint ranking for $\text{EFO}_k$ queries without the need to enumerate the entire entity set $\mathcal{E}^k$. The NS3 framework consists of three main components:

1. Marginalized Sub-Queries: It first answers marginalized sub-queries to generate necessary candidate sets for the free variables.
2. Hypernode Merging: It merges multiple free variables into hypernodes, where the domains of these hypernodes are pruned and managed using a dynamic budget $B$. This allows for efficient handling of the search space.
3. Progressive Reduction: The framework progressively reduces an $\text{EFO}k$ query to an $\text{EFO}{k-1}$ query, leveraging the budgeted reduced domain to maintain computational efficiency.

The authors provide code for their implementation, which is available at https://github.com/HKUST-KnowComp/NS3_KDD2026.

Results
NS3 demonstrates significant improvements in joint ranking performance across three standard KG datasets compared to existing baselines. The authors report that NS3 achieves a joint ranking accuracy increase of up to 25% over traditional methods that rely on marginal rankings. Additionally, the framework maintains strong marginal accuracy, with performance metrics indicating that it outperforms state-of-the-art models on the newly introduced joint-ranking benchmark for $\text{EFO}_3$ queries.

Limitations
The authors acknowledge that while NS3 improves joint ranking performance, it may still struggle with very high-dimensional queries where $k$ is significantly large, potentially leading to budget constraints that limit the effectiveness of hypernode merging. They also note that the framework’s reliance on dynamic budgeting may introduce variability in performance based on the chosen budget strategy. An additional limitation not explicitly mentioned is the potential for overfitting when training on smaller datasets, which could affect generalization to unseen queries.

Why it matters
The introduction of NS3 has significant implications for the field of knowledge representation and reasoning, particularly in enhancing the capability to handle complex logical queries over KGs. By providing a scalable approach to joint ranking, this work opens avenues for more sophisticated query answering systems that can better leverage incomplete knowledge graphs. The release of a joint-ranking benchmark for $\text{EFO}_3$ queries also facilitates systematic evaluation and comparison of future methods, potentially driving advancements in the area of multi-variable query processing.

Authors: Weizhi Fei, Hang Yin, Zihao Wang, Shukai Zhao, Wei Zhang, Yangqiu Song
Source: arXiv:2605.25985
URL: https://arxiv.org/abs/2605.25985v1