INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

gMLC: a multi-label feature selection framework for graph classification

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF gMLC.pdf (547KB) (no description provided) PDF
Title: gMLC: a multi-label feature selection framework for graph classification
Author(s): Kong, Xiangnan; Yu, Philip S.
Subject(s): Feature selection Graph classification Multi-label learning Subgraph Pattern Label correlation
Abstract: Graph classification has been showing critical importance in a wide variety of applications, e.g. drug activity predictions and toxicology analysis. Current research on graph classification focuses on single-label settings. However, in many applications, each graph data can be assigned with a set of multiple labels simultaneously. Extract- ing good features using multiple labels of the graphs becomes an important step before graph classification. In this paper, we study the problem of multi-label feature selec- tion for graph classification and propose a novel solution, called gMLC, to efficiently search for optimal subgraph features for graph objects with multiple labels. Different from existing feature selection methods in vector spaces which assume the feature set is given, we perform multi-label feature selection for graph data in a progressive way together with the subgraph feature mining process. We derive an evaluation criterion to estimate the dependence between subgraph features and multiple labels of graphs. Then a branch-and-bound algorithm is proposed to efficiently search for optimal sub- graph features by judiciously pruning the subgraph search space using multiple labels. Empirical studies demonstrate that our feature selection approach can effectively boost multi-label graph classification performances and is more efficient by pruning the sub- graph search space using multiple labels.
Issue Date: 2012-05
Publisher: Springer Verlag
Citation Info: Kong, X. N. and P. S. Yu (2012). "gMLC: a multi-label feature selection framework for graph classification." Knowledge and Information Systems. 31(2): 281-305. DOI: 10.1007/s10115-011-0407-3
Type: Article
Description: Post print version of article may differ from published version. The original publication is available at; DOI:10.1007/s10115-011-0407-3
ISSN: 0219-1377
Sponsor: This work is supported in part by NSF through grants IIS 0905215, DBI-0960443, OISE-0968341 and OIA-0963278.
Date Available in INDIGO: 2012-10-02

This item appears in the following Collection(s)

Show full item record


Country Code Views
United States of America 101
China 24
United Kingdom 11
Germany 5
Netherlands 2


My Account


Access Key