Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 14, No. 2, 2025 20 Application of Sparse Kernel Graph‐regularized Discriminant Non‐negative Matrix Factorization in Image Clustering Ran Zhou, Jianlei Li * Electronic Information Major, School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou, Henan Province, 450046, China * Corresponding author: Jianlei Li (Email: lijianlei@ncwu.edu.cn) Abstract: Non-negative Matrix Factorization (NMF) is widely used in image clustering; however, it has inherent limitations, including its unsupervised nature, lack of sparsity constraints, inability to leverage label information, and difficulty in capturing the geometric structure and nonlinear characteristics of data. To address these limitations, this paper proposes a Sparse Kernel Graph-regularized Discriminant Non-negative Matrix Factorization (SKGDNMF) algorithm. The algorithm innovatively adopts a dual normalization strategy, which involves column normalization for the basis matrix and row normalization for the coefficient matrix, and integrates spectral clustering to construct an end-to-end deep clustering framework. By applying sparse regularization to the coefficient matrix, the model’s robustness is significantly improved; this regularization forms complementary optimization with graph regularization, thereby effectively alleviating overfitting. A three-dimensional golden-section parameter optimization method is employed to determine key parameters, which enhances the algorithm’s practicality. Comparative experiments conducted on multiple datasets show that SKGDNMF significantly outperforms mainstream algorithms in terms of sparsity, robustness, and clustering performance, indicating its superior effectiveness for image clustering tasks. Keywords: Graph Regularization; Image Clustering; Non-negative Matrix Factorization; Sparsity; Spectral Clustering. 1. Introduction In image clustering algorithms, data dimensionality reduction is a key focus of researchers. Data usually changes before and after dimensionality reduction, and based on these changes, dimensionality reduction methods are categorized into nonlinear dimensionality reduction and linear dimensionality reduction. In the real world, however, there exists a large amount of data, and such data is often non- negative; otherwise, it would be meaningless. Therefore, the Non-negative Matrix Factorization (NMF) algorithm is widely applied in data feature extraction and has also been proven equivalent to many clustering methods. Inspired by the Non-negative Matrix Factorization algorithm, this paper proposes a Kernel-based Sparse Discriminative Graph-regularized Non-negative Matrix Factorization (SKGDNMF) algorithm. This algorithm is a semi-supervised method that mainly uses label information to construct a label matrix. Meanwhile, it incorporates a graph regularization term to capture the geometric structure of data, adopts a kernel method to handle the nonlinear nature of data, and adds an 1L regularization term to reduce the impact of noise on clustering results and enhance the discriminative power of clustering. 2. Sparse Kernel Graph Discriminative Non-negative Matrix Factorization Algorithm 2.1. SKGDNMF Algorithm This paper combines three algorithms, namely GNMF [1], DNMF [2], and KNMF [3], and incorporates a sparsity regularization term into the model to propose a new algorithm. Since the NMF algorithm is solved through an iterative update approach, and the matrix for initial iteration is randomly generated, this paper, inspired by Reference [4], adopts a "warm-start" strategy [4] at the initial stage of the algorithm. The warm-start strategy first performs K-means clustering on the data, and uses the obtained cluster centers as the initial basis matrix of the model. Based on the above, Sparse Kernel Graph Discriminative Non-negative Matrix Factorization (SKGDNMF) is proposed. The model of the algorithm is presented as follows: 2 2 l 0, 0 2 0 1 min ( ) ( ) Tr( ) T T F FU V T F X U V Q AV V LV U U V                (1) Similar to the standard NMF model, the optimization problem of solving U and V simultaneously is non-convex. Therefore, this paper still adopts the alternating iterative update approach to solve the iterative formulas. The objective formula can be simplified to: T T T T T T 0 0 0 =Tr(K )-2Tr(K V )+Tr(VK V ) αTr(QQ ) 2αTr(QV ) αTr( V V )+βTr(V LV) γTr(U ) 2γTr(U ) γTr( ) XX XU UU T l l l T T T A A A U U U U        (2) By constructing the Lagrangian function, we can obtain: T T T T T T 0 0 0 =Tr(K )-2Tr(K V )+Tr(VK V ) αTr(QQ ) 2αTr(QV ) αTr( V V ) +βTr(V LV) γTr(U ) 2γTr(U ) γTr( ) Tr( U )+Tr( V ) XX XU UU T l l l T T T T T A A A U U U U          L (3) 21 Herein, ik and ik are the Lagrange multipliers corresponding to constraints 0iku  and 0ikv  . Therefore, by differentiating the Lagrangian function and based on the KKT conditions (Karush-Kuhn-Tucker conditions): 0ik iku  , 0ik ikv  , U   =0 L , 0 V    L , and 0 A    L , the update rules can be derived as follows: ' 0 ' ( ) ( ) XU ik ik ik UU ik K V U u u UBK U      (4) ( ( ) ( ) ) ( ( ) ( ) ) T T XU l ik ik ik T T UU l ik K Q A V A A WV v v VK Q A V A A DV                    (5) 1( )T l l lA QV V V regAI   (6) Here, a regularization parameter regA is incorporated into the iterative formula of A to avoid matrix singularity. Regarding the update rules, Theorem 1 holds as follows: The optimization problem (1) is non-increasing under the update rules (4), (5), and (6). The value of the objective function remains unchanged if and only if the matrices U , V , and A reach a stable point. 2.2. Convergence Analysis The following proof refers to Reference [8].Let Model (1.1) be defined as the following objective function: 2 2 l 2 0 1 ( ) ( ) Tr( ) T T F F T F M X U V Q AV V LV U U V               (7) Definition 1: Function ( , )tG h h , which is the auxiliary function of Function ( )M h , satisfies the following two conditions: ( , ) ( ), ( , ) ( )tG h h M h G h h M h  (8) Lemma 1: If function ( , )tG h h is the auxiliary function of function ( )M h , then ( )M h is non-increasing under the iterative rule: 1 arg min ( , )t t h m G h h  (9) It can be proven as follows: 1 1( ) ( , ) ( , ) ( )t t t t t tM h G h h G h h M h    (10) Moreover, 1( ) ( )t tM h M h  holds if and only if tm is a local minimum point of ( , )tG h h . If the derivative of M exists and is continuous within a small neighborhood of 'm , then the differential '( ) 0M h  exists. Through Equation (9), a series of sequences that converge to the local minimum point min arg min ( ) h m M h can be obtained: 1 min 2 1 0 ( ) ( ) ( ) ( ) ( ) ( ) t tM h M h M h M h M h M h          (11) For an element ijv in matrix V (from the objective function), the formulas for the first-order partial derivative ' ijv M and the second-order partial derivative '' ijv M of the objective function with respect to ijv can be obtained as follows: ' ( 2 2 2 2 2 ) ij T v XU UU T l ij M K VK Q A V A A LV            (12) '' 2( ) 2 ( ) 2 , 2( ) 2 ,ij T UU jj jj ii i v UU j j ii K A A L if x M has labels otheL rK s           (13) Lemma 2: Function ' 2 ( , ) ( ) ( )( ) ( ( ) ( ) ) ( ) ij ij t t t t ij v ij v ij ij T T UU l ij t ijt ij G v v M v M v v v VK Q A V A A DV v v v               (14) is the auxiliary function of ijv M . Proof: As can be seen from Definition 1, to prove a function is the auxiliary function (of another function), it must satisfy both ( , ) ( )t ij ijG v v M v and ( , ) ( )ijG v v M v simultaneously. Obviously, ( , ) ( )ijG v v M v can be obtained directly. Next, we conduct a detailed proof for ( , ) ( )t ij ijG v v M v . First, perform a Taylor expansion on ( )ijM v ; by comparing it with Equation (14), to prove ( , ) ( )t ij ijG v v M v , it is equivalent to proving that: ''( ( ) ( ) ) 1 ( ) 2 ij T T UU l ij t v ijt ij VK Q A V A A DV M v v          (15) Substitute Equation (13) into Equation (15): ( ( ) ( ) ) [( ) ( ) ] ( ) [( ) ] T T UU l ij t T ij UU jj jj ii i t UU ij ij UU jj ii has labels others VK Q A V A A DV v K A A L if x VK DV v K L                         (16) Given ( ) ( )t UU ij ik UU kj k VK v K  , thus it is obvious that: ( ) ( ) ( )t t UU ij ik UU kj ij UU jj k VK v K v K  (17) Similarly, it can be obtained that: ( ) ( ) t t ij ik kj ii ij k t t ii ii ij ii ij DV D v D v D W v L v            (18) Moreover, if ax has labels, then both ( )l ab abV V and ( ) 0TQ A   hold; thus it follows that: [ ( ) ( ) ] [ ( ) ] [ ( )] ( ) ( ) T T T l ab l ab T t T t T l ab ik kj ij jj k Q A V A A V A A V A A V A A V A A              (19) From Equations (17), (18), and (19), it can be proven that Equation (17) holds. Thus, Equation (14) is the auxiliary function of ijv M , and Theorem 2 is proven. The above is the convergence proof for the update rule of Matrix V , and the update rule of Matrix U can be proven similarly. Since objective function A (with respect to the matrix) in Algorithm Model (1) is a convex function, the update rule can be obtained directly by setting 0 A    L and solving it; thus, the update formula of Matrix A is also convergent. In conclusion, Theorem 1 is proven. 3. Experiments and Results Analysis This paper tests the clustering performance of the 22 SKGDNMF algorithm on the face dataset PIE, the object dataset COIL20, and the handwritten digit dataset MNIST, and compares it with other algorithms including K-means [5], KPCA [6], NMF [7], GNMF, GDNMF [8], and KGDNMF [9] in terms of clustering performance. 3.1. Experimental Datasets In the COIL20 dataset, all images are uniformly resized to a size of 32×32 pixels. In the PIE dataset, 68 subjects are randomly selected, and 42 facial images of each subject under different lighting conditions are used; these images are uniformly cropped to 32×32 grayscale images. For the MNIST dataset, 200 images are randomly selected for each digit (0-9) from the training set, resulting in a total of 2000 images. 3.2. Experimental Process At the start of the experiment, we first load and standardize the three datasets, then divide them into a preset number of categories. For semi-supervised clustering algorithms, we randomly select k categories of data subsets each time, randomly extract 20% of the samples from each category to construct labeled data, and then run the algorithm model for semi-supervised decomposition. For the other algorithms, we set the dimensionality reduction dimension to the corresponding number of clusters k. In the algorithm post- processing stage, clustering labels are obtained through Spectral Clustering [10]. We calculate the Accuracy and Mutual Information (MI) metrics, repeat the experiment 10 times for each k to obtain the mean and standard deviation, and finally output the result table. The algorithm proposed in this paper has a total of four parameters, and different parameters exert different impacts on the experimental results. Therefore, this paper adopts the control variable method to investigate the selection of experimental parameters on the three datasets. With the number of neighbors fixed, we conduct parameter sensitivity analysis for  ,  , and  respectively, repeat the experiment ten times to calculate the classification accuracy, and take the average value. The relevant results are shown in the figure below: Figure 1. Parameter Sensitivity Analysis From the three groups of experiments, it can be observed that the proposed algorithm exhibits extremely high robustness to the label constraint weight  and the warm- start weight  ; parameter variations hardly affect the clustering performance. The graph regularization weight  only has slight optimization potential for specific datasets, such as the COIL20 dataset with high graph structure dependence. This characteristic also indicates that most parameters of the SKGDNMF algorithm do not require strict tuning to ensure model stability, further enhancing the algorithm's practicality. 3.3. Analysis of Experimental Results Table 1. Three Scheme comparing COL20 PIE MINST AC MIH AC MIH AC MIH K-means 0.6920 0.7455 0.3140 0.3765 0.6400 0.5449 KPCA 0.6979 0.7506 0.3162 0.3801 0.6461 0.5548 NMF 0.6840 0.7129 0.4904 0.5712 0.5992 0.4698 GNMF 0.8356 0.8910 0.8332 0.8840 0.6830 0.6588 GDNMF 0.8813 0.9267 0.9389 0.9498 0.9527 0.8736 KGDNMF 0.8756 0.9250 0.9344 0.9470 0.8914 0.8133 SKGDNMF 0.9584 0.9534 0.9833 0.9724 0.9543 0.8769 Table 1 presents the experimental results of the six algorithms on the three datasets. Among them, the results for the COIL20 and PIE datasets are the average values when the number of clusters ranges from 2 to 20 (with a step size of 2); the results for the MNIST dataset are the average values when the number of clusters ranges from 2 to 10. It can be seen that 23 the proposed algorithm exhibits significant performance advantages in the clustering tasks of the three datasets, achieving higher Accuracy and Mutual Information (MI). This indicates that the algorithm can stabilize the discriminative structure of manifold data across different image datasets, proving its effectiveness in aspects such as preserving manifold structures and suppressing noise interference. In conclusion, the proposed algorithm provides a new solution for semi-supervised clustering tasks, is more suitable for feature learning and structure mining of high- dimensional nonlinear data, and has important theoretical reference value and practical application prospects. 4. Conclusion This paper proposes the Sparse Kernel Graph Discriminative Non-negative Matrix Factorization (SKGDNMF) algorithm, which integrates semi-supervised learning, sparse constraints, label information, capture of the inherent geometric structure of data, and nonlinear data processing capabilities into a comprehensive model. Experimental results show that compared with existing algorithms, the proposed algorithm exhibits significant comprehensive advantages in image clustering tasks, with improvements in clustering accuracy, robustness, and sparsity. Through its innovative design, the algorithm effectively overcomes the limitations of traditional methods, provides a more effective solution for the clustering analysis of complex image data, and holds important theoretical significance and promising application prospects. References [1] Cai D, He X, Wu X, et al. Non-negative matrix factorization on manifold[C]//2008 Eighth IEEE International Conference on Data Mining. IEEE, 2008: 63-72. [2] Babaee M, Tsoukalas S, Babaee M, et al. Discriminative nonnegative matrix factorization for dimensionality reduction [J]. Neurocomputing, 2016, 173: 212-223. [3] Zhang D, Zhou Z H, Chen S. Non-negative matrix factorization on kernels[C]//PRICAI 2006: Trends in Artificial Intelligence: 9th Pacific Rim International Conference on Artificial Intelligence Guilin, China, August 7-11, 2006 Proceedings 9. Springer Berlin Heidelberg, 2006: 404-412. [4] Sun L, Zhao K, Han C Y, et al. Enhancing hyperspectral unmi- xing with two-stage multiplicative update nonnegative matrix factorization[J]. IEEE Access, 2019,7:171023-171031. [5] Ashabi A, Sahibuddin S B, Salkhordeh Haghighi M. The systematic review of K-means clustering algorithm[C]// Proceedings of the 2020 9th International Conference on Networks, Communication and Computing. 2020: 13-18. [6] Schölkopf B, Smola A ,Müller, K.Nonlinear Component Analysis as a Kernel Eigenvalue Problem[J].Neural Computation, 1998, 10(5):1299-1319. [7] Lee D D , Seung H S. Learning the parts of objects by non- negative matrix factorization[J]. Nature, 1999, 401(6755):788- 791. [8] Li H, Zhang J, Shi G, et al. Graph-based discriminative nonnegative matrix factorization with label information[J]. Neurocomputing, 2017, 266: 91-100. [9] Li X L, Zhang Y. Kernel-based discriminative graph regularized non-negative matrix factorization [in Chinese][J]. Journal of Computer Science and Exploration, 2020,14 (11): 1899-1907. [10] Ng A Y, Jordan M I , Weiss Y .On Spectral Clustering: Analysis and an algorithm[J].proc nips, 2002.