Interactive Graph Search for Multiple Targets on DAGs

Download PDF

Abstract

Interactive graph search (IGS) over DAGs aims to find a hidden target by asking interactive questions as few as possible. IGS is useful for many applications, e.g., facilitating supervised learning tasks by harnessing labeled data, image categorization, and product classification. However, most of the existing IGS methods only work for either single target search on DAGs or multiple targets search on simple trees . To overcome the gap, it motivates us to study a challenging and yet not solved problem of multiple targets search over DAGs. We analyze the new problem in-depth and propose a key concept of uncertain candidates. Based on it, we design an effective gain function to determine the best vertex to be asked questions and shrink the search space of potential targets greatly. Leveraging our uncertain candidates and gain function, we develop a unified k-EIS framework to search both single target and multiple targets. We analyze all algorithm complexities and theoretically show that our solution can significantly improve existing DFS-treebased methods by asking 𝑂(𝑛) questions to 𝑂(log2 𝑛) questions in worst cases. To further improve IGS for multiple targets, we propose an advanced solution by dividing the whole DAG into 𝑘 disjoint subgraphs with single targets and then tackling each subgraph one by one independently. Extensive experiments on real-world datasets validate that our proposed k-EIS framework can save lots of questions to search exact targets against four state-of-the-art IGS competitors.