Abstract

Existing methods for complex logical query answering over knowledge graphs fall into two categories. The first category relies on explicitly engineered logical operators, which suffer from pronounced error accumulation when handling complex query structures. The second category directly delegates reasoning to Large Language Models (LLMs), often leading to disorganized reasoning trajectories and logical hallucinations. To address these issues, we propose Structure-aware Query Tree Optimization (StruQTO), a structure-centric approach that foregrounds query-structure dependencies for complex logical querying. StruQTO parses a First-Order Logic (FOL) query into a Query Computation Tree (QCT) and conducts local-independence analysis among substructures based on variable-dependency patterns, thereby constructing a Structured Chain-of-Thought (SCoT) that is strictly aligned with the original logical expression. The method explicitly distinguishes weakly coupled and strongly coupled substructures, guiding the LLM to execute reasoning in the query’s true logical order while tightly constraining variable binding and set-theoretic operations throughout inference. Experiments on two public benchmarks, FB15K-237 and NELL-995, show that StruQTO achieves competitive or superior performance across a wide range of complex query patterns, with particularly notable improvements on structurally complex and negation-related queries. Ablation studies further validate the contributions of QCT construction and local-independence analysis to the overall performance gains.