2013 SelectiveSamplingonGraphsforCla

• (Gu et al., 2013) ⇒ Quanquan Gu, Charu Aggarwal, Jialu Liu, and Jiawei Han. (2013). “Selective Sampling on Graphs for Classification.” 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.2487641

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Selective+Sampling+on+Graphs+for+Classification
• http://dl.acm.org/citation.cfm?id=2487575.2487641&preflayout=flat#citedby

Quotes

Author Keywords

• Label complexity; learning; mistake bound; models; online learning; regret bound; selective sampling on graphs

Abstract

Selective sampling is an active variant of online learning in which the learner is allowed to adaptively query the label of an observed example. The goal of selective sampling is to achieve a good trade-off between prediction performance and the number of queried labels. Existing selective sampling algorithms are designed for vector-based data. In this paper, motivated by the ubiquity of graph representations in real-world applications, we propose to study selective sampling on graphs. We first present an online version of the well-known Learning with Local and Global Consistency method (OLLGC). It is essentially a second-order online learning algorithm, and can be seen as an online ridge regression in the Hilbert space of functions defined on graphs. We prove its regret bound in terms of the structural property (cut size) of a graph. Based on OLLGC, we present a selective sampling algorithm, namely Selective Sampling with Local and Global Consistency (SSLGC), which queries the label of each node based on the confidence of the linear function on graphs. Its bound on the label complexity is also derived. We analyze the low-rank approximation of graph kernels, which enables the online algorithms scale to large graphs. Experiments on benchmark graph datasets show that OLLGC outperforms the state-of-the-art first-order algorithm significantly, and SSLGC achieves comparable or even better results than OLLGC while querying substantially fewer nodes. Moreover, SSLGC is overwhelmingly better than random sampling.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 SelectiveSamplingonGraphsforCla	Charu C. Aggarwal Quanquan Gu Jialu Liu Jiawei Han			Selective Sampling on Graphs for Classification				10.1145/2487575.2487641		2013