关键词: 图半监督学习, 贪心最大割, 早期停止策略, 目标函数值

Abstract: Aiming at the problem of high computational complexity of Greed Max-Cut Graph semi-supervised learning algorithm（GGMC）, an improved Greed Max-Cut Graph semi-supervised learning algorithm based on Early stopping strategy, called GGMC-Estop, is proposed. According to the experimental analysis on that object function  value in optimization procedure of GGMC, the algorithm is improved in which two early stopping strategies are applied to stop GGMC training and prediction. Standard propagation is used to predict the label of data over the whole graph in one step. Experimental results on typical data sets show that the computational amount using the improved algorithm is far less than that of using GGMC algorithm, while the performance of classification for these two algorithms is almost approximate.

Key words: graph semi-supervised learning, greedy max-cut, early stopping strategy, object function value