2013 ActiveSearchonGraphs

• (Wang et al., 2013) ⇒ Xuezhi Wang, Roman Garnett, and Jeff Schneider. (2013). “Active Search on Graphs.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487605

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Active+Search+on+Graphs
• http://dl.acm.org/citation.cfm?id=2487575.2487605&preflayout=flat#citedby

Quotes

Author Keywords

• Active learning; graph search; information search and retrieval

Abstract

Active search is an increasingly important learning problem in which we use a limited budget of label queries to discover as many members of a certain class as possible. Numerous real-world applications may be approached in this manner, including fraud detection, product recommendation, and drug discovery. Active search has model learning and exploration / exploitation features similar to those encountered in active learning and bandit problems, but algorithms for those problems do not fit active search.

Previous work on the active search problem [5] showed that the optimal algorithm requires a lookahead evaluation of expected utility that is exponential in the number of selections to be made and proposed a truncated lookahead heuristic. Inspired by the success of myopic methods for active learning and bandit problems, we propose a myopic method for active search on graphs. We suggest selecting points by maximizing a score considering the potential impact of selecting a node, meant to emulate lookahead while avoiding exponential search. We test the proposed algorithm empirically on real-world graphs and show that it outperforms popular approaches for active learning and bandit problems as well as truncated lookahead of a few steps.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 ActiveSearchonGraphs	Jeff Schneider Xuezhi Wang Roman Garnett			Active Search on Graphs				10.1145/2487575.2487605		2013