Adapting nucleus sampling for interpretable multi-hop logical reasoning over knowledge graphs

Multi-hop logical reasoning is crucial for numerous real-world applications, including recommendation systems, question answering, and medical diagnosis. Multi-hop logical query answering on incomplete knowledge graphs has received significant interest as it explores the model’s capabilities for complex query reasoning, which encompasses queries leveraging logical conjunctions (∧), disjunctions (∨), negation (¬), and existential quantification (∃). Previous embedding-based methods struggle to adapt to out-of-distribution query structures and require training with complex queries. To generate answers for complicated queries, some research efforts have focused on end-to-end optimization, while others have leveraged pre-trained neural link predictors. However, the plausibility scores of triplets in neural link predictors fluctuate significantly. Moreover, the search space grows exponentially. These two factors pose significant challenges that traditional optimization techniques struggle to overcome. In this work, we propose an adapting nucleus sampling method for multi-hop logical query answering, namely NSCLQ. By traversing the knowledge graph within the query computation graph, NSCLQ is capable of reasoning over query answers and solving combinatorial optimization problems through adaptive dynamic sampling. Specifically, by utilizing an adaptive scoring function to determine the likelihood that entities e_i and e_j are linked through relationship r , the reasoning process of NSCLQ not only enhances interpretability but also effectively reduces the search space. Experiments performed on three datasets demonstrate that NSCLQ achieves statistically significant improvements over state-of-the-art methods in complex logical query answering.