복잡한 논리적 질의를 위한 신경망 기반 확장 가능한 심볼릭 검색 프레임워크 (다중 자유 변수)

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

복잡한 질의 응답(CQA)은 불완전한 지식 그래프(KG)에 대한 기본적인 지식 표현 및 추론 작업입니다. $k$개의 자유 변수를 갖는 존재적 1차 논리 질의(즉, $ ext{EFO}_k$ 질의)에 대한 답변을 찾는 것은 중요한 과제이지만, KG의 엔터티 집합 $\mathcal{E}$에서 가능한 답변 튜플 $\mathcal{E}^k$를 순위화해야 하므로 어려운 문제입니다. $k$가 증가함에 따라 이 문제는 빠르게 해결 불가능해집니다. 따라서 기존의 벤치마크 및 방법은 개별 변수에 대한 부분적인 순위를 사용하지만, 이러한 부분적인 순위는 실제 튜플의 전체적인 순위를 제대로 반영하지 못합니다. $\text{EFO}_1$ 질의에 대한 신경망 기반 심볼릭 검색을 바탕으로, 우리는 $\mathcal{E}^k$를 나열하지 않고도 전체 순위를 근사하는 예산 기반 프레임워크인 Neural Scalable Symbolic Search (NS3)를 제안합니다. NS3는 (i) 필요한 후보 집합을 얻기 위해 부분 질의에 대한 답변을 찾고, (ii) 여러 자유 변수를 병합하여 도메인이 가지치기되고 동적 예산 $B$에 의해 제어되는 하이퍼 노드를 생성하고, (iii) $\text{EFO}_k$ 질의를 예산을 고려한 축소된 도메인에서의 $\text{EFO}_{k-1}$ 질의로 점진적으로 줄입니다. 세 개의 표준 KG 데이터셋에서 NS3는 전체 순위 성능을 크게 향상시키면서도 높은 부분적인 정확도를 유지합니다. 또한, 기존의 $\text{EFO}_1$ 데이터셋을 $k=3$으로 확장하여 다변수 질의에 대한 체계적인 평가를 가능하게 하는 새로운 전체 순위 벤치마크를 공개합니다. 저희 코드는 https://github.com/HKUST-KnowComp/NS3_KDD2026 에서 제공됩니다.

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.