Research Of Multiple Kernel Graph Clustering

Data is a new strategic resource in the digital era and an important factor driving innovation,which is changing human society.Therefore,how to exploit valuable information from massive complex data has became an important scientific problem in recent years.As we known,as an important branch of artificial intelligence,machine learning mainly focus on the theories and algorithms of intelligent data analysis,which can be used to achieve the above goal.In recent years,for clustering high-dimensional,nonlinear,and complex attribute data,multiple kernel graph clustering(MKGC)has received extensive attentions in both academia and industry communities.The main reasons are that(1)using multiple kernel functions to map the original data to different candidate kernel spaces,such that the data linearly separable in the kernel space.One one hand,this can avoid the challenge of kernel function and kernel parameter selection faced by traditional kernel methods.On the other hand,this can also resist curse of dimensionality caused by the original high-dimensional data;(2)multiple kernel data has the complementarity,consensus,compatibility,and completeness.These properties are conducive to make full use of all base kernels to improve the clustering performance;(3)graph learning has strong identification and modeling capabilities,and can effectively exploit the latent cluster structure information of complex data.Accordingly,based on kernel method and graph theory,combined with advanced academic ideas,such as multi-view learning,subspace learning,tensor learning,and structure preservation,this dissertation aims to study MKGC methods for clustering high-dimensional,non-linear,and complex attribute data.In summary,the main contributions of this dissertation are summarized as follows:1.The traditional linear kernel weighted multiple kernel graph clustering paradigm(LKW)faces the following problems:(1)From the perspective of multiple kernel learning(MKL),the existing MKGC methods follow LKW,and this paradigm assumes the optimal consensus kernel is a linear combination of the multiple base kernels,so it faces the problem of constrained solution set;(2)From the perspective of graph learning,in order to capture the low-rank structure of data in the kernel space,the existing methods often directly impose low-rank constraint on the kernel matrix,but it cannot achieve the desired goal.To address these problems,this dissertation proposes a new learning paradigm,i.e.,neighbor linear kernel weighted MKGC paradigm(or NLKW in short),and then proposes a novel method,namely Local Structural Graph and Low-Rank Consensus Multiple Kernel Learning(LLMKL).Experiments show that the LLMKL method can effectively preserve the low-rank property of the data in the kernel space,and the experimental results verify the effectiveness of LLMKL.2.The NLKW paradigm faces the following problems:(1)From the perspective of MKL,although NLKW paradigm can expand the solution set to a certain extent,the linear weighted kernel may deviate far from the true best consensus kernel,such that the extended solution set may not be effective.Moreover,the weighting updating scheme of the base kernels relies on quadratic programming(QP),which suffers high computational complexity;(2)From the perspective of graph learning,the structural information of the data in the kernel space is very important for clustering,and the existing methods do not fully exploit these information.To address these problems,this dissertation proposes a new learning paradigm,i.e.,neighbor self-weighted MKGC paradigm(or NSW in short),and then proposes two MKGC methods,namely,Joint Robust Multiple Kernel Subspace Clustering(JMKSC)and Structure Preserving Multiple Kernel Clustering(SPMKC).Experimental results on some widely used real-world benchmarks validate the effectiveness of the proposed NSW learning paradigm;meanwhile,the proposed methods have a significant improvement in terms of clustering performance and running time compared with the existing MKGC methods.3.The NSW paradigm faces the following problems:(1)From the perspective of MKC,NSW usually designs a fat model that poses challenges for computational cost and clustering performance,since it learns both an affinity graph and an extra consensus kernel cumbersomely.Obviously,NSW pays more attention to the consensus kernel rather than an affinity graph,and this violates the fact that the affinity graph is the key of the graph-based clustering task;(2)The learned consensus kernel often no longer satisfies the Mercer theorem and cannot speed up the optimization.To address these problems,this dissertation proposes a new learning paradigm,i.e.,pure graph MKGC paradigm(or PG in short),and then proposes a MKGC method,namely Consensus Affinity Graph Learning(CAGL).Experimental results on ten benchmark datasets and two synthetic datasets show that CAGL consistently and significantly outperforms the state-of-the-art MKGC methods;meanwhile,the effectiveness of the PG learning paradigm is also demonstrated.4.The PG paradigm faces the following problems and challenges:(1)This paradigm ignores the high-order structure information or deep structure information existing in all the candidate graphs,so it does not fully exploit the structural information.Usually,the high-order structural information is very effective for improving clustering performance;(2)From the perspective of graph learning,except for the common self-expressiveness and adaptive neighbor graph learning methods,there is an urgent need for new graph learning methods to enrich graph learning theory for handling non-linear data.To address these problems,this dissertation proposes a new learning paradigm,i.e.,high-order MKGC paradigm(or HO in short),and then proposes two novel methods,namely Non-negative Matrix Factorization Tailored Graph Tensor(NMFTGT)and Kernel k-Means Coupled Graph Tensor(KCGT).The experimental results verifies the effectiveness of high-order structural information for clustering tasks.Moreover,extensive experiments shows that the superiorities of NMFTGT and KCGT methods compared with the state-of-the-art MKGC methods.