Name
Abstract | ||
|---|---|---|
AbstractInteractive graph search leverages human intelligence to categorize target labels in a hierarchy, which is useful for image classification, product categorization, and database search. However, many existing interactive graph search studies aim at identifying a single target optimally, and suffer from the limitations of asking too many questions and not being able to handle multiple targets.To address these two limitations, in this paper, we study a new problem of budget constrained interactive graph search for multiple targets called kBM-IGS problem. Specifically, given a set of multiple targets T in a hierarchy and two parameters k and b, the goal is to identify a k-sized set of selections S, such that the closeness between selections S and targets T is as small as possible, by asking at most a budget of b questions. We theoretically analyze the updating rules and design a penalty function to capture the closeness between selections and targets. To tackle the kBM-IGS problem, we develop a novel framework to ask questions using the best vertex with the largest expected gain, which provides a balanced trade-off between target probability and benefit gain. Based on the kBM-IGS framework, we first propose an efficient algorithm STBIS to handle the SingleTarget problem, which is a special case of kBM-IGS. Then, we propose a dynamic programming based method kBM-DP to tackle the MultipleTargets problem. To further improve efficiency, we propose two heuristic but efficient algorithms, kBM-Topk and kBM-DP+. Experiments on large real-world datasets with ground-truths verify both the effectiveness and efficiency of our algorithms. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.14778/3447689.3447694 | Hosted Content |
DocType | Volume | Issue |
Journal | 14 | 6 |
ISSN | Citations | PageRank |
2150-8097 | 1 | 0.35 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xuliang Zhu | 1 | 1 | 1.36 |
| Xin Huang | 2 | 379 | 29.42 |
| Byron Choi | 3 | 143 | 10.57 |
| Jiaxin Jiang | 4 | 26 | 4.07 |
| Zhaonian Zou | 5 | 331 | 15.78 |
| Jianliang Xu | 6 | 2743 | 168.17 |