LLM-Powered Interactive Graph Search: A Scalable and Practical Approach

Interactive graph search (IGS) has emerged as a powerful paradigm for information retrieval across diverse applications. The goal of IGS is to identify the most appropriate (i.e., deepest) node within a hierarchy for an unknown object, typically leveraging human intelligence such as crowdsourcing as the oracle. Existing IGS algorithms usually rely on reachability queries, such as "is the target node reachable from node x ?", and assume that correct answers are always available. However, in practice, answering such queries is challenging due to the requirement for domain-specific knowledge, resulting in frequent errors in the oracle's responses. As a consequence, the reachability-query-based approaches would perform poorly. In this paper, we propose a practical solution to the IGS problem, leveraging the power of large language models (LLMs) to tackle the issue of reachability queries. Specifically, we formally analyze the inherent properties of real-world hierarchies with the notion of ambiguous nodes and overlapping nodes to debunk the difficulty of reachability queries. In addition, we develop a practical oracle based on LLMs that can answer reachability queries on (near) leaf nodes accurately. Building on the LLM oracle, we propose a similarity-based upward search algorithm, namely SuS, to address the IGS problem. We further enhance SuS with layer-wise search and fast initialization techniques. We evaluate SuS on two real-world datasets against four baseline methods, and the experimental results clearly demonstrate the superiority of our solution.