2011 DualActiveFeatureandSampleSelec

• (Kong et al., 2011) ⇒ Xiangnan Kong, Wei Fan, and Philip S. Yu. (2011). “Dual Active Feature and Sample Selection for Graph Classification.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020511

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Dual+Active+Feature+and+Sample+Selection+for+Graph+Classification
• http://dl.acm.org/citation.cfm?id=2020408.2020511&preflayout=flat#citedby

Quotes

Author Keywords

• Active learning; algorithms; data mining; data mining; experimentation; feature construction; feature selection; graph classification; performance; subgraph pattern

Abstract

Graph classification has become an important and active research topic in the last decade. Current research on graph classification focuses on mining discriminative subgraph features under supervised settings. The basic assumption is that a large number of labeled graphs are available. However, labeling graph data is quite expensive and time consuming for many real-world applications. In order to reduce the labeling cost for graph data, we address the problem of how to select the most important graph to query for the label. This problem is challenging and different from conventional active learning problems because there is no predefined feature vector. Moreover, the subgraph enumeration problem is NP-hard. The active sample selection problem and the feature selection problem are correlated for graph data. Before we can solve the active sample selection problem, we need to find a set of optimal subgraph features. To address this challenge, we demonstrate how one can simultaneously estimate the usefulness of a query graph and a set of subgraph features. The idea is to maximize the dependency between subgraph features and graph labels using an active learning framework. We propose a branch-and-bound algorithm to search for the optimal query graph and optimal features simultaneously. Empirical studies on nine real-world tasks demonstrate that the proposed method can obtain better accuracy on graph data than alternative approaches.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 DualActiveFeatureandSampleSelec	Wei Fan Philip S. Yu Xiangnan Kong			Dual Active Feature and Sample Selection for Graph Classification				10.1145/2020408.2020511		2011