English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Combining near-optimal feature selection with gSpan

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).

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0003-3D79-2 Version Permalink: http://hdl.handle.net/21.11116/0000-0003-3D7A-1
Genre: Conference Paper

Files

show Files
hide Files
:
MLG-2008-Borgwardt.pdf (Any fulltext), 119KB
Name:
MLG-2008-Borgwardt.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show
hide
Description:
-

Creators

show
hide
 Creators:
Borgwardt, KM, Author              
Yan, X, Author
Thoma, M, Author
Cheng, H, Author
Gretton, A1, 2, Author              
Song, L, Author
Smola, A, Author              
Han, J, Author
Hu, P, Author
Kriegel, H-P, Author
Affiliations:
1Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497794              
2Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s):
 Dates: 2008-07
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: -
 Degree: -

Event

show
hide
Title: 6th International Workshop on Mining and Learning with Graphs (MLG 2008)
Place of Event: Helsinki, Finland
Start-/End Date: 2008-07-04 - 2008-07-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: 6th International Workshop on Mining and Learning with Graphs (MLG 2008)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1 - 3 Identifier: -