Granular-Ball-Induced Multiple Kernel K-Means

1 Introduction

Clustering, a fundamental task in machine learning, groups data based on inherent similarities [Aggarwal, 2018; Duran and Odell, 2013]. Classic methods include K-means [MacQueen and others, 1967], spectral clustering [Ng et al., 2001], and density-based clustering [Ester et al., 1996]. K-means, widely used for its simplicity, minimizes squared distances to cluster centroids but struggles with nonlinear and arbitraryshaped data distributions.

∗Corresponding Author

To overcome this limitation, various K-means variants have been developed. K-means++ [Arthur and Vassilvitskii, 2006] improves the convergence speed and clustering accuracy by optimizing the selection of initial cluster centers. [Mussabayev et al., 2023] proposed an adaptive clustering algorithm that does not require initialization or parameter selection. Although this algorithm somewhat improves robustness to initial values, its performance remains limited when dealing with high-dimensional and non-separable datasets.

Kernel trick is a powerful technique widely used to handle non-linearly separable data. For example, kernel K-means (KKM) [Sinaga and Yang, 2020] algorithm was proposed by mapping original data to a high-dimensional kernel space, where data can easily be separated linearly, and K-means clustering is subsequently performed. In practice, a kernel matrix is required to construct using the inner products of data points in the high-dimensional space, thereby capturing the nonlinear features of the data [Abin and Beigy, 2015; Yan et al., 2023; Yu et al., 2011; Girolami, 2002]. However, KKM's performance is highly dependent on the choice of the kernel function, which is often challenging to determine across different datasets.

To alleviate the limitation of selecting a single kernel function, the multiple kernel clustering (MKC) concept was introduced [Chao et al., 2021; Zhao et al., 2009; Zhang et al., 2020]. The core idea of MKC is to leverage multiple kernel functions to extract complementary information from different feature spaces and optimally fuse these kernel matrices to improve clustering performance. Among MKC algorithms, one of the most popular approaches is the multiple kernel K-means (MKKM) [Huang et al., 2011]. MKKM learns a weighted combination of multiple kernel functions, and its core optimization objective can be defined as:

where H and Kγ represent the clustering partition matrix and the γ-th kernel matrix, respectively. ∆ = {σ ∈ Rω | ∑ωk=1 σk = 1, σk ≥ 0, ∀k}, where ω represents the number of kernel functions and σk is the kernel function's weight. MKKM adopts an alternating optimization strategy to update the kernel weights and the clustering partition matrix iteratively. However, this alternating approach easily suffers from the local optima, leading to a degraded overall clustering performance [Yao et al., 2020; Liu et al., 2016]. To further improve the MKKM, [Liu, 2022] proposed SimpleMKKM, which reformulates the min-max formula into a parameterfree minimization problem and designs a streamlined gradient descent algorithm to solve for the optimal solution. Although this method alleviates the local optimum problem, it is still limited as it requires joint optimization over all samples to compute kernel matrices, significantly increasing time and space complexity.

In this paper, we propose an adaptive and robust granularball-induced multiple-kernel K-means clustering framework. It presents the advantages of scalability and clustering performance compared to recent multi-kernel clustering methods. Intuitively, granular-ball computing is a data representation technique that can capture complex data structures with a set of balls. Using a density-based central consistency measurement [Xia et al., 2019], granular balls can be adaptively generated from coarse to acceptable fine granularities. The use of granular balls reduces the amount of data while effectively capturing the distribution information of the data. Based on granular-ball computing, we introduce the granular-ballinduced kernel (GBK) into a multi-kernel K-means clustering framework. Note that the proposed GBK can be play-andplugged into existing MKKMmethods for clustering, significantly improving the efficiency and clustering performance.

In summary, our main contributions are listed as follows:

• We are the first to introduce a granular-ball-induced kernel (GBK) into multi-kernel K-means clustering that can be easily extended to existing multiple-kernel methods.
• The proposed GBK effectively reduces storage requirements and computational costs while ensuring superior clustering performance because it allows for reducing the kernel matrix size from "the number of samples n" to "the number of granular-balls m" (m ≪ n).
• Experimental results verify its effectiveness across various commonly used multi-kernel clustering datasets.

2 RelatedWork

2.1 Multiple Kernel Clustering

To address the issue of single kernel insufficiency, multiple kernel K-means (MKKM), as an algorithm combining multiple kernel learning and K-means clustering, improves clustering performance by integrating multiple kernel functions. Based on classical MKKM, recent studies have made improvements from different perspectives, including selecting kernels based on kernel correlation [G¨onen and Margolin, 2014], introducing local adaptive kernel fusion [Liu et al., 2016], optimizing kernel alignment criteria [Cortes et al., 2012], enhancing robustness [Tao et al., 2018], simplifying the optimization process [Zhang et al., 2021], and removing noisy kernels [Li et al., 2023], etc. For instance, LMKKM [G¨onen and Margolin, 2014] was proposed better to capture sample-specific features through local adaptive kernel fusion. RMKKM [Du et al., 2015] adopted the l2-norm to improve resistance to outliers, achieving joint optimization of clustering labels, multi-kernel combinations, and memberships through alternating optimization. Besides, ONKC [Liu et al., 2017] was introduced to enhance the representation capability of the optimal kernel. A multi-view clustering method, LFMVC [Li et al., 2024], based on SimpleMKKM was further studied, which optimized a new objective function using an efficient two-step optimization strategy. Moreover, a multiple kernel clustering method with multi-scale partition selection [Wang et al., 2024] was developed that dynamically removes noisy kernels, and significantly improves performance.

One of the main limitations of the above MKKM methods is that they require constructing kernel matrices for all samples and performing optimization, which results in high time and space costs. In this work, we use the distribution information of samples in multiple kernel spaces to enhance efficiency and clustering accuracy.

2.2 Granular-ball Computing

Granular-ball computing (GBC) [Xia et al., 2019] is a helpful tool for improving efficiency by covering data at multiple granularities. This aligns with the strategy of "human cognition prioritizing global features before processing details" proposed in [Chen, 1982] and the concept of multigranularity cognitive computing [Wang, 2017].

Figure 1 shows how granular balls cover and represent data sets, which provides an intuitive macroscopic perspective for understanding granular computing. Granular-ball computing has been studied in various applications, including accelerating unsupervised K-means [Xia et al., 2020], enhancing density-based clustering like DPC and DBSCAN [Cheng et al., 2023], [Cheng et al., 2024], and addressing high-dimensional challenges through granular-ball-weighted K-means and manifold learning [Xie et al., 2024b; Liu et al., 2024]. In spectral clustering, granular-ball methods exploit data structure for efficiency [Xie et al., 2023]. Recent advancements include the granular-ball clustering algorithm [Xia et al., 2024], introducing center consistency for complex data, and fuzzy theory integration to resolve overlapping boundaries from concept drift [Xie et al., 2024a]. Moreover, Granular-ball computing has recently been applied to point cloud registration [Hu et al., 2025] and multi-view contrastive learning [Su et al., 2025]. These successes demonstrate granular balls' powerful representation and generalization capabilities, confirming their potential for multi-view learning.

3 Methodology

This section formally elaborates on the proposed granularball-induced multiple kernel clustering framework. It mainly includes four steps: i) the granular-ball generation step, ii) the granular-ball-induced kernel construction, iii) the multiple kernel fusion step, and iv) the optimization of multikernel clustering. The granular-ball-induced multiple kernel construction procedure (the first three steps) is shown in Figure 2. Through the above steps, the proposed method significantly improves the multi-kernel optimization efficiency (smaller number of granular balls) and achieves better clustering performance (granular balls fit the data distribution well and exclude potential noises).

3.1 Granular-ball Generation

Let D = {xu ∈ Rd , u = 1, 2, . . . , n} be a dataset where n and d denote the number of samples and the dimensionality of the data, respectively. The subscript u indicates the sample index. The granular-ball set is defined as GB = {GB1,GB2, . . . ,GBm}, where m granular balls cover and describe the dataset D. We use i to denote the i-th ball where i ∈ {1, 2, . . . ,m}. The ball GBi's size is Si.

Definition 1. Granular-ball Representation: For the i-th GBi, its center ci is given by ci = 1 Si ∑Si u=1 xu. Its radii (maximum radius rmax and average radius rave) are

Definition 2. Center-Consistency Measure: For the i-th granular-ball GBi, its center-consistency measure [Xia et al., 2024] is

where χi = {xu | ∥xu - ci∥ ≤ rave}. Equation (3) means the density ratio between the average radius and the maximum radius within a granular ball. Intuitively, a smaller ratio means a lower sparsity level of sample distribution within a granular ball. The criterion for splitting a granular ball is determined by comparing its CCM value with the median CCM of all balls. Specifically, if CCMGBi < λ · CCMmedian (λ is two empirically), the granular ball will be split; otherwise, the splitting process stops. The algorithm of granular ball generation is provided in Section 1 of the Appendix.

3.2 Calculation of Granular-ball Kernel

Kernel methods embed the data into a new feature space via projections to uncover the nonlinear relationships among the data. For the dataset D, we consider a set of ω projection functions Φ = {ϕ1, ϕ2, . . . , ϕω}. Each projection ϕk (k = 1, 2, . . . , w) encodes the data into the feature space as a new vector ϕk(x). Let {K1, K2, . . . , Kω} denote the Mercer kernel matrices corresponding to these implicit projections:

We embed granular balls into the kernel space and derive the Granular-ball Kernel (GBK), defined as follows:

where i, j ∈ {1, 2, ...,m}. Kernel mappings of samples within the same granular ball are approximately equal due to their proximity in the input space. This aligns with the local smoothness assumption in kernel methods, where nearby points have similar kernel mappings. Thus, in (5), the mean of the mappings of the samples {xu} within the same ball can estimate the granular-ball center ci's kernel mapping:

Intuitively, each granular ball can be seen as a small local distribution or cluster, and the kernel mappings of its internal points are expected to concentrate around a common region in the kernel-induced feature space. Let granular balls GBi and GBj be regarded as distributions P and Q respectively, then the granular-ball kernel reflects the expected kernel:

Thus, in practice, we have:

Theorem 1. The granular-ball kernel KGB k (ci, cj) satisfies the Mercer condition. 1. KGB k (ci, cj) is symmetric. 2. For any p, we have pT KGB k p ≥ 0.

Proof. Symmetry: Since Kk(xu, xv) = Kk(xv, xu) satisfies symmetry, it follows that:

Positive Semi-Definiteness: Let p = [p1, p2, . . . , pm] and pi = p′i /Si. Since Kk is a kernel and it is positive semidefinite, we have p′T Kkp′ ≥ 0. Then,

Thus, KGB k satisfies the Mercer condition.

3.3 Multiple Kernel Fusion

Based on the granular-ball kernel KGB k (ci, cj) in Equation (5), we construct a granular-ball multi-kernel, defined as:

where σ2 k is the kernel weight and σ ∈ ∆. ∆ represents the constraints for kernel weights and ∆ = {σ ∈ Rω | ∑ωk=1 σk = 1, σk ≥ 0, ∀k}. Here, KGB σ will be used in the subsequent establishment of the granular-ball-induced multikernel clustering model.

3.4 GB-inducedMultiple Kernel K-means

In multiple kernel clustering, the kernel matrices and the clustering partition matrix are the keys to clustering optimization. The granular-ball clustering partition matrix Hgb ∈ Rm×J is a binary matrix recording the assignment information of granular balls to clusters, defined as:

Algorithm 1 GB-SMKKM Algorithm

Input: Granular-ball kernel matrix { ¯KGB k }ωk=1, initial t = 1. Output: Optimized σ.

• 1: Initialize σ(1) = 1ω and flag = 1.
• 2: while flag holds do
• 3: Compute KGB σ(t) = ∑ωk=1 (σ(t) k )2 ¯KGB k and obtain H(t) gb .
• 4: Compute ∂Kσ ∂σk and obtain descent direction d(t) via gradient descent in Equation (14).
• 5: Update σ(t+1) ← σ(t) +αd(t) .
• 6: if max |σ(t+1) - σ(t) | ≤ e-4 then
• 7: Set flag = 0.
• 8: end if
• 9: t ← t + 1.
• 10: end while
• 11: return σ.

To balance the influence of different kernels and ensure the rationality of sample assignments, we optimize the model by minimizing the following objective for the kernel coefficient σk (k = 1, 2, ..., w):

where Rk,i,s = KGB k (ci, ci)-2KGB k (ci, zs)+KGB k (zs, zs). Here, J clusters are considered. The center of the s-th cluster is denoted as zs. In the objective, the first term is the self-similarity of the granular-ball GBi in the kernel space. The second term measures the similarity between GBi and the cluster center zs, while the third term denotes the cluster center's self-similarity kernel.

To simplify the objective function, we omit explicit cluster centers in Equation (12) and reformulate the objective into a matrix form. Thereby, we can construct a granular-ball-based multi-kernel clustering model (GB-SMKKM):

where Ω = {Hgb ∈ Rm×J |HTgbHgb = IJ}. Further, we havemin

Algorithm 1 presents the GB-SMKKM optimization procedure. Section 2 of the Appendix provides proof to show that the above objective is differentiable and convex.

3.5 Computational Complexity

In this work, n represents the number of samples, m denotes the number of granular balls, ω denotes the number of kernel functions, and k represents the number of clusters. The main computational cost of the proposed method involves the construction of the (m×m) kernel matrix KGB σ and the optimization of the assignment matrix Hgb. Specifically, for ω kernel matrices, traversing them for calculation incurs a O(ωm2 ) complexity. Then, for the maximum optimization step and clustering assignment matrix computation, each update of Hgb ∈ Ω requires solving a positive semi-definite optimization problem, where the largest eigenvalue is calculated once using K-means clustering. Hence, this step incurs a complexity of O(m3 + m2kt), where t is the number of optimization iterations. The computational bottleneck lies in the matrix decomposition step, which incurs a O(m3 ) complexity. In contrast, MKKM operates on the complete n × n kernel matrix, where the matrix decomposition has a O(n3 ) complexity. This highlights the advantage of the granularball kernel approach, as it reduces the O(n3 ) term to O(m3 ), where m ≪ n. Finally, when the optimization process for the GB-SMKKM objective function requires T iterations, the total time complexity is: O(T [ωm2 +m3 +m2kt]).

4 Experiments

In this section, we conduct the following experiments, including evaluating the clustering performance of the proposed granular-ball-induced multiple kernel clustering against recent strong multiple kernel baselines on nine single-view datasets and three multiple-view datasets; comparing different anchor-sampling methods in multi-kernel clustering frameworks to verify the effectiveness of using granularball computing; and analyzing optimization convergence and computational cost. The experiments are conducted using MATLAB R2022a 1 .

4.1 Setup

Datasets. We evaluated the proposed algorithm on 12 datasets. The detailed information of datasets is summarized in Table 1. As can be seen, these datasets differ significantly in terms of sample size, multi-view attributes, dimensionality, and the number of categories, making them highly representative and capable of comprehensively verifying the applicability and robustness of the algorithm.

Metrics. We adopt three widely-used external evaluation metrics [Rand, 1971] to measure clustering performance: i) Adjusted Rand Index (ARI), which evaluates the similarity between the predicted and true cluster assignments while adjusting for chance; ii) Normalized Mutual Information (NMI), which quantifies the amount of information shared between the predicted clusters and the ground truth; and iii) Clustering Accuracy (ACC) directly measures the proportion of correctly classified samples. To ensure the reliability of the results and reduce the impact of randomness, each method is repeated 20 times, and the average results are reported.

1 Source code and supplementary materials are available at: https: //github.com/WangYifan4211115/GB-MKKM.

Baselines. In the experiments, the following recent strong baselines are included for comparison.

• Approximate kernel K-means (RKKM-a) approximates kernel K-means using a low-rank matrix decomposition, significantly reducing the computational cost.([Chitta et al., 2011], SIGKDD)
• Affinity aggregation for spectral clustering (AASC) aggregates affinity matrices to enhance spectral clustering. ([Huang et al., 2012], CVPR)
• Multiple kernel K-means (MKKM) combines multiple kernels into a consensus kernel to enhance alignment and performance. ([Huang et al., 2011], IEEE TFS)
• Robust multiple kernel K-means (RMKKM) leverages the L2,1-norm to handle noise and outliers. ([Du et al., 2015], IJCAI)
• Simple multiple kernel K-means (Simple-MKKM) simplifies optimization by introducing a streamlined min-max formulation with fewer parameters. ([Liu, 2022], IEEE TPAMI)
• Multiple kernel K-means clustering with simultaneous spectral rotation (MKKM-SR) integrates spectral rotation with multiple kernel K-means to align the clustering structure across kernels. ([Lu et al., 2022], ICASSP)
• Scalable multiple kernel clustering (SMKC) scales multiple kernel clustering by learning consensus clustering structures from expectation kernels. ([Liang et al., ][2024], ICML)

Furthermore, we introduce the proposed granular-ballinduced kernel into the baselines (MKKM, MKKM-SR, and SMKKM). For a fair comparison, we uniformly employ three types of kernels (with various parameters): Linear, Polynomial, and Gaussian, resulting in 6 kernel functions. It is noteworthy that for the comparison with RMKKM, we adopt the optimal parameters and 12 kernel functions as used in their original paper [Du et al., 2015].

4.2 Results on Single-viewClustering

Table 2 reports comparison results averaged on nine singleview clustering tasks regarding ACC, NMI, and ARI metrics. As can be seen, the proposed GB-SMKKM consistently achieves the best results in the three metrics.

Specifically, compared to SMKKM, the ACC, NMI, and ARI improvements by the proposed method are 6.83%, 13.93%, and 5.93% respectively. These improvements are statistically significant as the paired T-test yields P-values of 0.038, 0.014, and 0.022 for ACC, NMI, and ARI, respectively. Moreover, the improvements are still significant when the proposed granular-ball-induced kernel is introduced into other baselines, such as MKKM and MKKM-SR. For example, the average improvements of ACC, NMI, and ARI of GBMKKM-SR are 5.59%, 11.79%, and 5.84% higher than those of MKKM-SR, respectively, and the upgrades of ACC, NMI, and ARI of GB-MKKM are 1.05%, 3.47%, and 1.33%, respectively. These indicate that using granular balls is beneficial in improving the optimization in the multi-kernel spaces.

This might be explained by the fact that granular balls can capture the data distribution from multiple granularities and exclude potential noisy data by estimated ball boundaries.

We also conducted a statistical analysis regarding ACC using the Friedman Test. Friedman test results are reported in Figure 4. Section 3 of the Appendix, the detailed calculation process of the Friedman Test, is added.

4.3 Results onMulti-viewClustering

Here, three multi-view clustering tasks are conducted by comparing a recent strong multi-view baseline SMKC ([Liang et al., ][2024], ICML) for comparison. Note that SMKC is also built upon the SMKKM, which shares a foundation similar to our model. Results are summarized in Table 3. In the experiments using granular-ball kernels in SMKC, we introduce our variant GB-SMKC. This is achieved by using granular-ball computing to replace their anchor-selection method. Also, the number of anchors in SMKC is kept close to the number of granular balls to ensure fairness.

Table 3: Comparison of GB-SMKC and SMKC.

As seen in Table 3, GB-SMKKM still outperforms SMKC in terms of all ACC, NMI, and ARI metrics. Specifically, the ACC of GB-SMKC is higher by 0.56%, 5.4%, and 4.14% on the Handwritten, Mfeat, and Caltech101-7 tasks, respectively. This validates the effectiveness and applicability of the GBinduced framework on these multi-view clustering tasks.

4.4 Effects of Anchor Selection Strategies

Granular-ball computing reduces the computational cost by transforming the calculation of point-point relationships into that of ball-ball relationships. As it adaptively determines subsets, Granular-ball computing can be regarded as an anchor selection method. Compared to other anchor-sampling methods (e.g., Balanced K-means based Hierarchical Kmeans(BKHK) [Zhu et al., 2017], K-means [Cai and Chen, 2014], and random anchor selection [Nie et al., 2023]), granular-ball computing can be better at describing data distribution with complex shapes. This is because the generated granular balls adaptively determine multi-granularity subsets based on data distribution characteristics and metric criteria. The ball boundaries can exclude unknown noise points, further improving robustness. In this experiment, we compare the above anchor-sampling methods to provide empirical evidence to verify the effectiveness.

Figure 3 summarizes the comparison results. As can be seen, granular-ball computing is a better choice than all other sampling methods for multi-kernel clustering optimization. This is because the procedure of granular-ball generation is based on data distribution. The generated balls better fit the original data distribution through the density-based consistency metric. Moreover, the ball boundaries can exclude unknown noise points, improving robustness. Hence, the above results further verify the effectiveness of the proposed granular-ball kernels.

4.5 Runtime Analysis

Table 4 presents the runtime comparison between the GBinduced framework and six baselines. The results on five representative datasets show that the average speed of GB-MKKM is 0.170 seconds higher than that of MKKM, and the average speed of GB-MKKM-SR is 0.201 seconds higher. Similarly, GB-SMKKM is 1.491 seconds faster than SMKKM respectively. Note that granular-ball construction can be done in advance independently of the optimization of different models. Thus, we do not include the construction time here. In section 4 of the Appendix, we report both ball generation and model optimization time. The results show that the speed increases as the dataset scale increases. Therefore, granular-ball-induced kernel matrix construction scales the MKKM algorithms. Meanwhile, in the section 5 of the appendix, convergence graphs of the monotonically decreasing target values of multiple datasets during the iterative process are presented.

4.6 Analysis of Granular-ball Numbers

Computing a full n × n kernel matrix in traditional MKKM methods is computationally expensive. The GB-MKKM framework uses granular balls to characterize data distribution. By reducing the size of the kernel matrix, GB-MKKM minimizes the complexity of subsequent optimization, avoiding modeling the point-to-point dependency inherent in traditional methods. In Figure 5, we report the number of granular balls adaptively optimized by the granular-ball computing process.

As can be seen, the granular-ball number is significantly smaller than the original number of sample points on the same datasets. The results indicate that the GB-MKKM framework not only achieves promising high clustering performance, but also effectively reduces the number of sample points. This demonstrates its remarkable flexibility and applicability to various MKKM algorithms, fully proving the ability of granular balls to characterize data in kernel space effectively. Other experimental results about the single kernel method and other methods are supplemented in Section 6 of the Appendix.

5 Conclusion

This paper introduces the GB-induced clustering framework, which enhances multi-kernel k-means (MKKM) by incorporating granular-ball computing. Traditional MKKM suffers from high computational costs due to full kernel matrix construction and point-to-point dependencies. To address this, we propose a novel granular-ball representation that models relationships between local data regions (granular balls) instead of individual points. This ball-to-ball approach significantly reduces complexity, improves robustness to noise, and achieves higher clustering accuracy. Extensive experiments show that GB-induced and its variants consistently outperform traditional MKKM methods across diverse datasets, demonstrating strong generalization, robustness, and scalability. The framework is broadly applicable to existing MKKM algorithms and can be extended to deep architectures for enhanced multi-kernel clustering in neural networks.

Acknowledgments

This research was supported by the Chongqing Graduate Research Innovation Program CYB25259 and the National Natural Science Foundation of China under Grant Nos. 62221005, 62450043, 62222601, and 62176033.