Graph Classification with Imbalanced Class Distributions and Noise

Abstract

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 real-world graph data with different degrees of class imbalance and noise demonstrate the algorithm performance.