Source-linked AI summary
Human-Assisted Graph Search: It's Okay to Ask Questions
Aditya Parameswaran, Anish Das Sarma, Hector Garcia-Molina, Neoklis Polyzotis, Jennifer Widom
TL;DR
HumanGS studies how to identify unknown target nodes in a directed acyclic graph by selecting reachability questions for humans. It formalizes dimensions of the problem, develops algorithms and complexity results, and evaluates question-selection methods for practical crowdsourcing use. The framework produces optimal question sets that can be issued in parallel, while general optimization remains computationally hard and future work includes uncertainty and erroneous answers.
Problem
HumanGS asks how to minimize human questions while identifying unknown target nodes in graph-search applications such as categorization, curation, debugging, and interactive search.
Method
The paper formalizes HumanGS through target sets, reachability questions, candidate sets, and three dimensions, then develops algorithms and complexity analyses across graph structures.
Results
The paper develops optimal question sets for all combinations of its three dimensions, with questions independent of prior answers and issuable in parallel.
Takeaways & Limitations
HumanGS provides a framework for optimizing human computation in crowdsourcing systems such as Mechanical Turk.
Takeaways & Limitations
The paper identifies future work on target-node probability distributions, error-resilient HumanGS, and other human-computation optimization problems.
Abstract
from arXiv · showhide
We consider the problem of human-assisted graph search: given a directed acyclic graph with some (unknown) target node(s), we consider the problem of finding the target node(s) by asking an omniscient human questions of the form "Is there a target node that is reachable from the current node?". This general problem has applications in many domains that can utilize human intelligence, including curation of hierarchies, debugging workflows, image segmentation and categorization, interactive search and filter synthesis. To our knowledge, this work provides the first formal algorithmic study of the optimization of human computation for this problem. We study various dimensions of the problem space, providing algorithms and complexity results. Our framework and algorithms can be used in the design of an optimizer for crowd-sourcing platforms such as Mechanical Turk.
1. INTRODUCTION
HumanGS formulates human-assisted search over a directed acyclic graph as the problem of selecting reachability questions that identify unknown target nodes while controlling question cost. The paper develops algorithms and complexity results for multiple variants motivated by crowdsourcing applications.
- HumanGS asks whether a target node is reachable from a queried graph node, with the goal of discovering the unknown target set.
- Applications include image categorization, hierarchy curation, workflow debugging, interactive search, and filter synthesis.
- Correlated answers and node location make question selection nontrivial: ancestor answers follow from descendant answers, while middle nodes may provide more information.
- Crowdsourcing latency discourages sequential questioning, motivating question sets that can be selected and issued efficiently.
- The paper identifies three orthogonal dimensions, formally defines HumanGS, develops algorithms and complexity results, and evaluates algorithms on real-world data.
2. APPLICATIONS AND DIMENSIONS
The paper organizes HumanGS instances along three dimensions—target-set size, question budget, and graph structure—and formalizes how reachability answers constrain possible targets. Candidate sets capture the remaining target possibilities after selected questions.
- The three dimensions are Single/Multi, Bounded/Unlimited, and DAG/Downward-Forest/Upward-Forest.
- Single/Multi: Single has one target node, whereas Multi does not constrain target-set size; these variants correspond to different applications.
- Bounded/Unlimited: Bounded search limits the question set to k and minimizes remaining candidates, while Unlimited seeks the smallest set that precisely identifies the target set.
- The formal procedure selects questions, obtains human answers, and computes candidate target nodes that may be the target set or a superset.
- A question at u returns YES exactly when a target lies in u’s reachable set, and DAG monotonicity propagates YES to predecessors and NO to descendants.
- The candidate set is the maximal set of nodes indistinguishable from the target set under answers to questions at N; with no questions, it is V.
4. SINGLE TARGET NODE
For a single target node, the paper defines bounded search by minimizing worst-case candidate-set size under a question budget and analyzes algorithms across DAGs and forest structures. General DAG search is hard, while restricted forests admit efficient solutions in several cases.
- Single-Bounded: Single-Bounded chooses k queried nodes to minimize the largest candidate set over all possible target nodes.
- Single-Bounded: DAG: For any DAG, worst-case candidate size is computable in O(n^2 · k), while brute-force optimization takes O(n^k·n^2 · k).
- Single-Bounded: DAG: Single-Bounded cannot be solved in polynomial time unless P = NP, although constant k permits a polynomial-time solution.
- Single-Bounded: Downward-Forest: On downward-forests, the problem is equivalent to partitioning the tree and has an O(n log n) algorithm.
- Single-Bounded: Upward-Forest: On upward-forests, an algorithm solves Single-Bounded in O(m · k^2 · n^5), while the questions needed for worst-case candidate size one can range from O(log n) to O(n).
- Single-Unlimited: For Single-Unlimited on downward-forests, almost all nodes must be queried, whereas upward-forests require all but at most one leaf and all internal nodes with indegree 1.
5. MULTIPLE TARGET NODES
The Multi-Bounded problem seeks a fixed-size set of questions that minimizes the worst-case candidate set for multiple independent target nodes. It is NP-hard on arbitrary DAGs, while forest-structured instances admit a polynomial-time dynamic-programming algorithm.
- Multi-Bounded asks for k nodes whose questions minimize the worst-case candidate set for an unknown independent target set.
- Arbitrary DAGs: The general Multi-Bounded problem is NP-hard in n and k.
- Arbitrary DAGs: The decision version of Multi-Bounded lies in ΣP2, leaving a gap between the established lower and upper bounds.
- Downward/Upward-Forests: Multi-Bounded on downward-trees is equivalent to Multi-Bounded on upward-trees.
- Downward/Upward-Forests: A dynamic-programming algorithm solves Multi-Bounded on forests in O(k2 · n6).
6. EXPERIMENTAL STUDY
The experiments evaluate HumanGS question-selection algorithms on webpage categorization using the DMOZ hierarchy. Across question counts, tree sizes, and phases, humanGS reduces candidate sets faster than the baselines, with more phases often preferable to more questions per phase.
- Methodology: The study evaluates HumanGS on webpage categorization using the 11,600-plus-node science subtree of the DMOZ hierarchy.
- Methodology: The humanGS algorithm is compared with random node selection and breadth-first general-first selection.
- Methodology: The experiments measure average candidate-set size over 100 randomly sampled tasks, with additional averaging over 10 runs for random.
- Results: With 10 questions, humanGS reduces the candidate set to around 1000 nodes, a 10-fold decrease, while both baselines remain above 1000 even after 100 questions.
- Results: HumanGS outperforms the baselines as tree depth increases, with an increasing margin near the actual tree size.
- Results: After five phases, humanGS identifies the target on average, compared with eight phases for general-first, while random stays above 10,000 candidates.
- Results: Using 50 questions per phase requires six phases and 300 total questions, versus five phases and 500 questions for 100 per phase; extra phases increase latency and reduce parallelism.
7. RELATED WORK
Related work addresses crowdsourcing, active learning, data integration, and decision trees, but does not study the same general problem of optimizing reachability questions for human-assisted graph search.
- Crowdsourcing research has studied social aspects, games, and task-specific annotation or search-relevance applications, but not minimizing the set of questions in this problem.
- Active learning also requests human input for information content, but typically generates machine-learning training data and does not ask questions in parallel.
- Data-integration and exploration work also minimizes questions, but studies different, less generally applicable models in which humans assist computer programs.
- HumanGS resembles decision-tree classification, but lacks training statistics and restricts questions to reachability queries on the DAG.
8. CONCLUSIONS AND FUTURE WORK
The paper presents HumanGS across three orthogonal axes and develops algorithms for all combinations, including question sets that can be issued in parallel. It identifies probabilistic targets, answer errors, and broader human-computation optimization as future directions.
- HumanGS is studied along Single / Multi, Bounded / Unlimited, and DAG / Downward-Forest / Upward-Forest axes.
- The algorithms generate optimal question sets without depending on answers to earlier questions, enabling parallel issuance in crowdsourcing systems.
- Future HumanGS work could use target-node probability distributions to minimize the expected candidate-set size.
- The paper proposes studying error-resilient HumanGS because human answers may be incorrect.
- The authors also identify optimization of other human-computation problems through selecting questions as an open direction.
A.3 Proof of Theorem 4.4
The proof establishes NP-completeness for Single-Bounded-DECISION on DAGs by reducing max-cover to question selection and showing that candidate-set verification is polynomial-time.
- Single-Bounded-DECISION asks whether a budget-k node set yields a worst-case candidate set of size at most m.
- The reduction represents max-cover sets and items as two DAG layers, adding singleton nodes to complete the construction.
- With budget k, YES answers at set nodes produce candidate sets of at most m, while YES answers at item or singleton nodes produce size 1.
- The worst case corresponds to all selected questions receiving NO answers, leaving at least m+n candidate nodes.
- Because wcase(N) is computable in polynomial time, a proposed solution is verifiable in polynomial time, placing the decision problem in NP.
- The proof transfers an optimal forest solution to an augmented tree with an additive worst-case candidate-set increase of at most one node.
A.5 Proof of Lemma 4.8
The lemma characterizes the candidate set produced by questions in a directed tree as the partition containing the target, whether or not the partition-root question is asked.
- If the target lies in x's partition and x is queried, the YES answer restricts candidates to x's subtree while other queried nodes eliminate incompatible regions.
- If x is the tree root and is not queried, NO answers from descendant queries remove their subtrees, leaving the same partition containing the target.
A.6 Proof of Theorem 4.9
The proof reduces Single-Bounded on a downward-tree to an equivalent partition problem and solves it by minimizing the largest partition under a question budget. For balanced downward m-ary trees, Algorithm 1 is optimal in constant time when k < m^d/2.
- The candidate set for any question selection corresponds to an induced partition, so minimizing the worst-case candidate set is equivalent to minimizing the largest partition.
- The algorithm augments a downward-forest with a root, then binary-searches partition sizes while using dynamic programming to find the required number of edge cuts.
- Algorithm 1 initially asks all nodes at depth l = floor(log_m k), then distributes remaining questions across their subtrees.
- For a balanced downward m-ary tree of depth d, Single-Bounded is solved optimally in O(1) when k < m^d/2.
A.9 Proof of Theorem 4.11
The section develops bottom-up dynamic programming for Single-Bounded search on upward-trees, representing question allocations by worst-case candidate-set contributions. For balanced upward-trees, an optimal constant-time strategy selects well-spread leaf questions.
- Dynamic programming: For each node, child-subtree tuples are combined over all budget splits to generate candidate allocations for the parent.The recurrence considers all k1 and k2 satisfying the parent budget and combines the corresponding child options.
- Dynamic programming: The algorithm processes each tree bottom-up and stores, for every question budget, nondominated tuples describing subtree allocations and worst-case contributions.Each tuple records question counts across child subtrees together with candidate-set contributions for different target locations.
- Balanced upward-trees: In balanced upward-trees of large depth, Algorithm 3 finds the optimal Single-Bounded solution in O(1).The strategy selects leaf nodes that are as spread out as possible and share as little ancestry as possible.
- Dynamic programming: Dominated tuples can be discarded because an allocation no worse in every tracked contribution is always preferable.This pruning rule bounds the retained options while preserving the best allocation represented by the dynamic program.
- Balanced upward-trees: Leaf questions are especially informative because a leaf answer can eliminate the entire path to the root from the worst-case candidate set.The balanced-tree strategy therefore prioritizes leaves while distributing them across the tree.
B.1 Proof of Theorem 4.14
The proof establishes that Single-Unlimited search on an upward-forest requires questions at nearly all structurally necessary nodes. It propagates indistinguishability arguments upward from leaves to internal nodes and roots.
- Necessity of questions: Every leaf must be queried, because an unqueried leaf cannot be distinguished from its parent when the parent answers YES and its other children answer NO.The same ambiguity argument is then applied recursively to internal nodes after lower-level questions return NO.
- Necessity of questions: After leaves are handled, the proof repeats the argument for each parent and continues upward through the forest.This establishes the need to query internal nodes with indegree 1 under the theorem’s upward-forest structure.
- Root exception: At the forest roots, at most one root can remain unqueried because querying all other roots and relevant children can identify it from their NO responses.Leaving two roots unqueried would make them indistinguishable.
C.1 Proof of Theorem 5.2
The section proves hardness for Multi-Bounded through a max-cover reduction, then gives specialized algorithms for balanced trees and forests. It concludes that Multi-Unlimited is trivialized: every node must be queried.
- Hardness: The Multi-Bounded reduction maps max-cover sets and items to separate DAG layers, with edges representing set membership.Additional singleton nodes complete the constructed instance used to preserve the optimization correspondence.
- Hardness: Selecting set nodes in the Multi-Bounded instance corresponds precisely to selecting sets in max-cover because set questions eliminate the most item nodes in the worst case.Thus the constructed search problem inherits the max-cover optimization structure.
- Balanced trees: For balanced m-ary trees, Multi-Bounded is solvable in O(1) when k ≤ m.The strategy chooses nodes at a depth balancing the root path and the subtree size, making either answer eliminate roughly comparable numbers of candidates.
- Balanced forests: For a balanced forest, Multi-Bounded is solvable in O(k^2r), where r is the number of trees.Dynamic programming allocates questions across trees and combines their independent worst-case candidate sets.
- Multi-Unlimited: The optimal Multi-Unlimited solution is N = V, so a question must be asked at every graph node.If a node is unqueried, identical ancestor-YES and descendant-NO answers leave its membership in the target set ambiguous.