Noisy Interactive Graph Search: An Uncertainty-Based Approach with Online Modeling of Latent Expertise and Difficulty

Interactive graph search (IGS) has emerged as a powerful information retrieval paradigm for various applications. Given a hierarchy and an oracle that typically relies on human intelligence, IGS aims to identify the most precise concept for an unknown object while minimizing interaction costs. Most existing algorithms simplify the problem by assuming a perfect oracle that always provides correct answers. Others adopt an idealized noisy oracle that models noises as explicit error rates specified in advance and locate the target with Bayesian inference guided by a node-wise querying strategy. However, in real-world scenarios, the oracle inevitably makes mistakes and prior knowledge of the oracle is often limited. Moreover, the node-wise querying strategy that lacks holistic awareness of the search state and ignores the global hierarchical structure usually yields suboptimal queries. To address these challenges, we introduce IGS-RTA. We first formulate the problem based on search uncertainty, explicitly accounting for the randomness of the search state and hierarchical relations. We then propose a querying strategy that maximizes the expected uncertainty decrement. Our rigorous theoretical analysis establishes a logarithmic upper bound on the query complexity. In addition, to adapt to noisy settings with limited prior knowledge, we analyze oracle expertise and task difficulties, which characterize two groups of meta-factors that influence real query answering. We model their relationships using a probabilistic graphical model and design techniques to estimate these latent factors online. We evaluate IGS-RTA on two real-world datasets against six baselines. Results show that IGS-RTA improves search accuracy by up to 52% while reducing monetary costs by up to 8×.