Empirical Inference

Near-optimal supervised feature selection among frequent subgraphs

2009

Conference Paper

ei


Graph classification is an increasingly important step in numerous application domains, such as function prediction of molecules and proteins, computerised scene analysis, and anomaly detection in program flows. Among the various approaches proposed in the literature, graph classification based on frequent subgraphs is a popular branch: Graphs are represented as (usually binary) vectors, with components indicating whether a graph contains a particular subgraph that is frequent across the dataset. On large graphs, however, one faces the enormous problem that the number of these frequent subgraphs may grow exponentially with the size of the graphs, but only few of them possess enough discriminative power to make them useful for graph classification. Efficient and discriminative feature selection among frequent subgraphs is hence a key challenge for graph mining. In this article, we propose an approach to feature selection on frequent subgraphs, called CORK, that combines two central advantages. First, it optimizes a submodular quality criterion, which means that we can yield a near-optimal solution using greedy feature selection. Second, our submodular quality function criterion can be integrated into gSpan, the state-of-the-art tool for frequent subgraph mining, and help to prune the search space for discriminative frequent subgraphs even during frequent subgraph mining.

Author(s): Thoma, M. and Cheng, H. and Gretton, A. and Han, J. and Kriegel, H-P. and Smola, AJ. and Song, L. and Yu, PS. and Yan, X. and Borgwardt, KM.
Journal: Proccedings of the 2009 SIAM Conference on Data Mining (SDM 2009)
Pages: 1076-1087
Year: 2009
Month: May
Day: 0
Editors: Park, H. , S. Parthasarathy, H. Liu
Publisher: Philadelphia, PA, USA

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: 9th SIAM Conference on Data Mining (SDM 2009)
Event Place: Sparks, NV, USA

Address: Society for Industrial and Applied Mathematics
Institution: Society for Industrial and Applied Mathematics
ISBN: 978-1-615-67109-0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
PDF

BibTex

@inproceedings{5666,
  title = {Near-optimal supervised feature selection among frequent subgraphs},
  author = {Thoma, M. and Cheng, H. and Gretton, A. and Han, J. and Kriegel, H-P. and Smola, AJ. and Song, L. and Yu, PS. and Yan, X. and Borgwardt, KM.},
  journal = {Proccedings of the 2009 SIAM Conference on Data Mining (SDM 2009)},
  pages = {1076-1087},
  editors = {Park, H. , S. Parthasarathy, H. Liu},
  publisher = {Philadelphia, PA, USA},
  organization = {Max-Planck-Gesellschaft},
  institution = {Society for Industrial and Applied Mathematics},
  school = {Biologische Kybernetik},
  address = {Society for Industrial and Applied Mathematics},
  month = may,
  year = {2009},
  doi = {},
  month_numeric = {5}
}