Frequent Sub-Structure-Based Approaches for Classifying Chemical Compounds∗

In this paper we study the problem of classifying chemical com-pound datasets. We present a sub-structure-based classifica-tion algorithm that decouples the sub-structure discovery pro-cess from the classification model construction and uses frequent subgraph discovery algorithms to find all topological and geo-metric sub-structures present in the dataset. The advantage of our approach is that during classification model construction, all relevant sub-structures are available allowing the classifier to intelligently select the most discriminating ones. The computa-tional scalability is ensured by the use of highly efficient frequent subgraph discovery algorithms coupled with aggressive feature selection. Our experimental evaluation on eight different clas-sification problems shows that our approach is computationally scalable and on the average, outperforms existing schemes by 10 % to 35%.