Research On Robust Semi-Supervised Graph Clustering Method

Clustering analysis,as an important learning task in machine learning,is a process of exploring the cluster or class structure of sample data in unsupervised mode,thereby revealing the inherent laws of the data.Among them,the graph clustering method based on graph theory is a novel and widely applicable clustering method,and the Semi-Supervised Graph Clustering(SSGC)that combines semi-supervised learning to add auxiliary information(such as paired constraints)to guide graph clustering has also been widely studied and applied.In practical applications,the collected sample data usually contains noise or errors,which will seriously affect the performance of the algorithm.For this reason,this paper proposes two corresponding robust semi-supervised graph clustering methods based on the semi-supervised graph clustering method combined with some robust metrics:l1-based Semi-Supervised Graph Clustering(SSGC_L1):Aiming at the problem that the pair-constrained loss function in the original SSGC model is based on l2 and thus lacks robustness,we replace it with a robust metric l1,thus proposing a robust semi-supervised graph clustering model.Furthermore,for the problem that the resulted non-smooth objective function is not easy to optimize in the SSGC_L1 model,we proposed a new algorithm based on the Majorization-Minimization framework and proved its convergence.Experimental results on multiple data sets show that SSGC_L1 can improve the robustness and effectiveness of semi-supervised clustering when there is noise or error in labels of auxiliary information.lp-based Semi-supervised Graph Clustering(SSGC_LP):Since the lp(0<p<1)pseudo-metric is more insensitive to larger deviation values,we further propose a robust semi-supervised graph clustering model based on this pseudo-metric.Correspondingly,for the problem that the resulted non-convex and non-smooth objective function is not easy to optimize in this model,by constructing a series of smooth functions,we propose a new algorithm and prove its convergence.Through experimental comparison,the robustness and effectiveness of SSGC_Lp are verified.