Graph classification with imbalanced class distributions and noise

Shirui Pan, Xingquan Zhu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

32 Citations (Scopus)


Recent years have witnessed an increasing number of applications involving data with structural dependency and graph representations. For these applications, it is very common that their class distribution is imbalanced with minority samples being only a small portion of the population. Such imbalanced class distributions impose significant challenges to the learning algorithms. This problem is further complicated with the presence of noise or outliers in the graph data. In this paper, we propose an imbalanced graph boosting algorithm, igBoost, that progressively selects informative subgraph patterns from imbalanced graph data for learning. To handle class imbalance, we take class distributions into consideration to assign different weight values to graphs. The distance of each graph to its class center is also considered to adjust the weight to reduce the impact of noisy graph data. The weight values are integrated into the iterative subgraph feature selection and margin learning process to achieve maximum benefits. Experiments on realworld graph data with different degrees of class imbalance and noise demonstrate the algorithm performance.

Original languageEnglish
Title of host publicationIJCAI 2013 - Proceedings of the 23rd International Joint Conference on Artificial Intelligence
Number of pages7
Publication statusPublished - 1 Dec 2013
Externally publishedYes
EventInternational Joint Conference on Artificial Intelligence 2013 - Beijing, China
Duration: 3 Aug 20139 Aug 2013
Conference number: 23rd (conference proceedings)


ConferenceInternational Joint Conference on Artificial Intelligence 2013
Abbreviated titleIJCAI 2013
Internet address

Cite this