Graph Classification with Imbalanced Data Sets

Many graph classification methods have been proposed in recent years. These graph classification methods can perform well with balanced graph data sets, but perform poorly with imbalanced graph data sets. In this paper, we propose a new graph classification method based on cost sensitivity to deal with imbalance. First, we introduce a misclassification cost-matrix, and select the weighted subgraph based on the least misclassification cost as the attribute of graph. Then we build up a decision stump classifier and ensemble learning, finally obtain classify critical function to classify a new graph. Especially we prove that the supergraph of a weighted subgraph has an upper bound. And we can use the upper bound of supergraph to reduce the number of candidate subgraphs, so our method can be very efficient. Moreover we compare our method with other graph classification methods through experiment on imbalanced graph date sets.