Interactive Graph Search: Efficient Strategies for Navigating Decision Graphs
Interactive Graph Search
Ahmet Deniz
Introduction
We study Interactive Graph Search (IGS), with the conceptual objective of departing from the conventional “top-down” strategy in searching a poly-hierarchy, also known as a decision graph. In IGS, a machine assists a human in looking for a target node z in an acyclic directed graph G, by repetitively asking questions. In each question, the machine picks a node u in G, asks a human “is there a path from u to z?”, and takes a boolean answer from the human. The efficiency goal is to locate z with as few questions as possible.
It is concerned with the scenario where a human needs to explore a potentially massive poly-hierarchy— an acyclic directed graph (DAG) where each edge represents specialization — in order to locate the deepest node that best describes a certain concept.
Contribution
- The DAG (acyclic directed graph), typically, is stored at a remote server, and must be communicated to the human, with a unit cost charged on every node communicated. The algorithmic challenge is to devise a strategy to minimize the amount of interaction.
- The efficiency goal in the above scenario is to minimize the number of questions asked. More formally, one can think of the problem as a game between two players, Alice and Bob. Initially, Bob secretly chooses a target node z in the hierarchy. Alice’s job is to figure out which node is z. There is an oracle that Alice can inquire repeatedly.
- Manual Curation: Many hierarchies (better known as taxonomies or categories) require this kind of periodic extension; some examples are Wikipedia, the web of concepts, the ACM computing classification system, and so on.
- A Commercial Site: To provide, for example, technical support, an organization would rely on the decision tree/graph to interact with a customer, in order to diagnose the problem encountered by the customer and to suggest the corresponding remedy.
Methodology
- Heavy-Path Decomposition:
Let T be a tree of n nodes which may not be balanced. The goal of heavy-path decomposition is to produce a balanced representation of T. - DFS and White-Path Theorem (Depth-First Search):
The vertices on this path have not been discovered yet. It is guaranteed that the algorithm must be able to discover v while u is still in the stack.
Conclusions
Conventionally, people are used to searching a decision tree/graph in the straightforward top-down fashion. This paper aims to show that there can be alternative strategies achieving better efficiency than that traditional wisdom. To allow for a rigorous algorithmic study, we introduced the interactive graph search problem. Here, the input is a directed acyclic graph G. Given an initially unknown vertex z in G, the objective is to eventually locate z by asking reachability questions: each question specifies a query node q and obtains a boolean answer as to whether z is reachable from q. We have described algorithms which solve variants of the problem using a provably small number of questions, and established a nearly matching lower bound. We have also presented an experimental evaluation to demonstrate the efficiency and usefulness of the proposed solutions in real-world scenarios.