Graph Classification: A Diversified Discriminative Feature Selection Approach

Publisher:
ACM
Publication Type:
Conference Proceeding
Citation:
Proceedings of 2012 ACM International Conference on Information and Knowledge Management, 2012, pp. 205 - 214
Issue Date:
2012-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002432OK.pdf754.95 kB
Adobe PDF
A graph models complex structural relationships among objects, and has been prevalently used in a wide range of applications. Building an automated graph classification model becomes very important for predicting unknown graphs or understanding complex structures between different classes. The graph classification framework being widely used consists of two steps, namely, feature selection and classification. The key issue is how to select important subgraph features from a graph database with a large number of graphs including positive graphs and negative graphs. Given the features selected, a generic classification approach can be used to build a classification model. In this paper, we focus on feature selection. We identify two main issues with the most widely used feature selection approach which is based on a discriminative score to select frequent subgraph features, and introduce a new diversified discriminative score to select features that have a higher diversity. We analyze the properties of the newly proposed diversified discriminative score, and conducted extensive performance studies to demonstrate that such a diversified discriminative score makes positive/negative graphs separable and leads to a higher classification accuracy.
Please use this identifier to cite or link to this item: