Effective feature construction by maximum common subgraph sampling |
| |
Authors: | Leander Schietgat Fabrizio Costa Jan Ramon Luc De Raedt |
| |
Affiliation: | 1.Department of Computer Science,Katholieke Universiteit Leuven,Leuven,Belgium |
| |
Abstract: | The standard approach to feature construction and predictive learning in molecular datasets is to employ computationally expensive
graph mining techniques and to bias the feature search exploration using frequency or correlation measures. These features
are then typically employed in predictive models that can be constructed using, for example, SVMs or decision trees. We take
a different approach: rather than mining for all optimal local patterns, we extract features from the set of pairwise maximum
common subgraphs. The maximum common subgraphs are computed under the block-and-bridge-preserving subgraph isomorphism from
the outerplanar examples in polynomial time. We empirically observe a significant increase in predictive performance when
using maximum common subgraph features instead of correlated local patterns on 60 benchmark datasets from NCI. Moreover, we
show that when we randomly sample the pairs of graphs from which to extract the maximum common subgraphs, we obtain a smaller
set of features that still allows the same predictive performance as methods that exhaustively enumerate all possible patterns.
The sampling strategy turns out to be a very good compromise between a slight decrease in predictive performance (although
still remaining comparable with state-of-the-art methods) and a significant runtime reduction (two orders of magnitude on
a popular medium size chemoinformatics dataset). This suggests that maximum common subgraphs are interesting and meaningful
features. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|