Premium
Discriminative frequent subgraph mining with optimality guarantees
Author(s) -
Thoma Marisa,
Cheng Hong,
Gretton Arthur,
Han Jiawei,
Kriegel HansPeter,
Smola Alex,
Song Le,
Yu Philip S.,
Yan Xifeng,
Borgwardt Karsten M.
Publication year - 2010
Publication title -
statistical analysis and data mining: the asa data science journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.381
H-Index - 33
eISSN - 1932-1872
pISSN - 1932-1864
DOI - 10.1002/sam.10084
Subject(s) - discriminative model , submodular set function , computer science , feature selection , graph , data mining , greedy algorithm , pattern recognition (psychology) , artificial intelligence , mathematics , combinatorics , theoretical computer science , algorithm
The goal of frequent subgraph mining is to detect subgraphs that frequently occur in a dataset of graphs. In classification settings, one is often interested in discovering discriminative frequent subgraphs, whose presence or absence is indicative of the class membership of a graph. 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. Copyright © 2010 Wiley Periodicals, Inc. Statistical Analysis and Data Mining 3: 302‐318, 2010