Interactive Graph Search Made Simple

Interactive graph search (IGS) has proven to be a useful information retrieval paradigm in a diverse set of applications. Robust IGS algorithms are notoriously difficult to design because they are deeply rooted in graph theory. The current state-of-the-art algorithms either fail to achieve an optimal number of interaction rounds or rely on interfaces demanding tedious user inputs. Furthermore, previous research has paid little attention to the underlying computation bottleneck, which is currently dealt with using primitive implementations. This work remedies the above issues altogether. Utilizing novel findings on the problem characteristics, we develop an algorithmic framework for IGS that requires a designer to fill in the details for only two ''black-box'' operations. Our framework, when instantiated with surprisingly simple black-box implementations, yields optimal algorithms not only in all the scenarios explored before but also in new scenarios never studied. We accompany our framework, designed to minimize interaction rounds, with a new algorithm designed to reduce the CPU time complexity significantly. Extensive experiments on both real and synthetic data confirm both the efficacy and efficiency of the proposed techniques.