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.　©　2011　IEEE.