CogBoost: boosting for fast cost-sensitive graph classification

Shirui Pan, Jia Wu, Xingquan Zhu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

46 Citations (Scopus)


Graph classification has drawn great interests in recent years due to the increasing number of applications involving objects with complex structure relationships. To date, all existing graph classification algorithms assume, explicitly or implicitly, that misclassifying instances in different classes incurs an equal amount of cost (or risk), which is often not the case in real-life applications (where misclassifying a certain class of samples, such as diseased patients, is subject to more expensive costs than others). Although cost-sensitive learning has been extensively studied, all methods are based on data with instance-feature representation. Graphs, however, do not have features available for learning and the feature space of graph data is likely infinite and needs to be carefully explored in order to favor classes with a higher cost. In this paper, we propose, CogBoost, a fast cost-sensitive graph classification algorithm, which aims to minimize the misclassification costs (instead of the errors) and achieve fast learning speed for large scale graph data sets. To minimize the misclassification costs, CogBoost iteratively selects the most discriminative subgraph by considering costs of different classes, and then solves a linear programming problem in each iteration by using Bayes decision rule based optimal loss function. In addition, a cutting plane algorithm is derived to speed up the solving of linear programs for fast learning on large scale data sets. Experiments and comparisons on real-world large graph data sets demonstrate the effectiveness and the efficiency of our algorithm.

Original languageEnglish
Article number7006795
Pages (from-to)2933-2946
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number11
Publication statusPublished - 1 Nov 2015
Externally publishedYes


  • boosting
  • cost-sensitive learning
  • cutting plane algorithm
  • Graph classification
  • large scale graphs
  • subgraphs


Dive into the research topics of 'CogBoost: boosting for fast cost-sensitive graph classification'. Together they form a unique fingerprint.

Cite this