  Interactive graph search (IGS) uses human intelligence to locate the target
node in hierarchy, which can be applied for image classification, product
categorization and searching a database. Specifically, IGS aims to categorize
an object from a given category hierarchy via several rounds of interactive
queries. In each round of query, the search algorithm picks a category and
receives a boolean answer on whether the object is under the chosen category.
The main efficiency goal asks for the minimum number of queries to identify the
correct hierarchical category for the object. In this paper, we study the
average-case interactive graph search (AIGS) problem that aims to minimize the
expected number of queries when the objects follow a probability distribution.
We propose a greedy search policy that splits the candidate categories as
evenly as possible with respect to the probability weights, which offers an
approximation guarantee of $O(\log n)$ for AIGS given the category hierarchy is
a directed acyclic graph (DAG), where $n$ is the total number of categories.
Meanwhile, if the input hierarchy is a tree, we show that a constant
approximation factor of $(1+\sqrt{5})/2$ can be achieved. Furthermore, we
present efficient implementations of the greedy policy, namely GreedyTree and
GreedyDAG, that can quickly categorize the object in practice. Extensive
experiments in real-world scenarios are carried out to demonstrate the
superiority of our proposed methods.
