Efficient Example-Guided Interactive Graph Search

We study the problem of interactive graph search (IGS). Given a query entity
$\varphi$
, the goal is to identify the target concept in a directed acyclic graph (DAG) concept hierarchy
$H$
, which best describes
$\varphi$
, through interactions with an oracle. In each interaction, a question in the form of “Does
$\varphi$
belong to concept
$u?$
” is asked and the oracle can only answer either YES or NO. The efficiency of an IGS algorithm is measured by the number of questions asked, to identify the target concept, which is referred to as query cost. In theory aspect, we propose the Target-Sensitive IGS (TS-IGS) algorithm that achieves a query cost complexity of
$O(\log n. \log\frac{L}{\log n}+d\cdot\log_{d}n)$
, where
$L$
is the length of the path from the root of
$H$
to the target concept. When
$L\in O(\log n)$
, our TS-IGS matches the known lower bound [1]. In practice aspect, we propose an algorithm called Example-Guided IGS (EG-IGS) that exploits the knowledge of entities and asks promising questions guided by examples similar to
$\varphi$
. We prove that EG-IGS achieves a finer-grained query cost bound than that of TS-IGS, and is extremely efficient in practice. Extensive experiments on six real-world datasets (including images, texts, and gene sequences) show that our EG-IGS outperforms all the existing competitors by up to two orders of magnitude in terms of query cost, and is robust in various settings. To further demonstrate the real feasibility of our EG-IGS technique, we develop a fully-automatic Amazon product categorization demo system with GPT-3.5 serving as the oracle.