Graph ensemble boosting for imbalanced noisy graph stream classification

Shirui Pan, Jia Wu, Xingquan Zhu, Chengqi Zhang

Research output: Contribution to journalArticlepeer-review

59 Citations (Scopus)


Many applications involve stream data with structural dependency, graph representations, and continuously increasing volumes. For these applications, it is very common that their class distributions are imbalanced with minority (or positive) samples being only a small portion of the population, which imposes significant challenges for learning models to accurately identify minority samples. This problem is further complicated with the presence of noise, because they are similar to minority samples and any treatment for the class imbalance may falsely focus on the noise and result in deterioration of accuracy. In this paper, we propose a classification model to tackle imbalanced graph streams with noise. Our method, graph ensemble boosting, employs an ensemble-based framework to partition graph stream into chunks each containing a number of noisy graphs with imbalanced class distributions. For each individual chunk, we propose a boosting algorithm to combine discriminative subgraph pattern selection and model learning as a unified framework for graph classification. To tackle concept drifting in graph streams, an instance level weighting mechanism is used to dynamically adjust the instance weight, through which the boosting framework can emphasize on difficult graph samples. The classifiers built from different graph chunks form an ensemble for graph stream classification. Experiments on real-life imbalanced graph streams demonstrate clear benefits of our boosting design for handling imbalanced noisy graph stream.

Original languageEnglish
Article number6884853
Pages (from-to)940-954
Number of pages15
JournalIEEE Transactions on Cybernetics
Issue number5
Publication statusPublished - 1 May 2015
Externally publishedYes


  • Data streams
  • graph ensemble boosting (gEBoost)
  • graphs
  • imbalanced class distributions
  • noise


Dive into the research topics of 'Graph ensemble boosting for imbalanced noisy graph stream classification'. Together they form a unique fingerprint.

Cite this