Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Combining near-optimal feature selection with gSpan


Gretton,  A
Max Planck Institute for Biological Cybernetics, Max Planck Society;
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 119KB

Supplementary Material (public)
There is no public supplementary material available

Borgwardt, K., Yan, X., Thoma, M., Cheng, H., Gretton, A., Song, L., et al. (2008). Combining near-optimal feature selection with gSpan. In 6th International Workshop on Mining and Learning with Graphs (MLG 2008) (pp. 1-3).

Cite as: https://hdl.handle.net/21.11116/0000-0003-3D79-2
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 optimises a submodular quality criterion, which means that we can yield a near-optimal solution using greedy feature
selection. Second, our submodular qual-
ity 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.