Graph Classification with Imbalanced Class Distributions and Noise

Publication Type:
Conference Proceeding
International Joint Conference on Artificial Intelligence, 2013, pp. 1586 - 1592
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002988OK.pdf771.63 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: