Granular-Ball-Induced Multiple Kernel K-Means

Shuyin Xia, Yifan Wang, Lifeng Shen, Guo-Yin WangIJCAI 2025 · DOI

Introduction

Multiple Kernel K-Means (MKKM) is a powerful tool for clustering non-linearly separable data by combining information from various feature spaces (kernels). However, it faces two major hurdles: high computational complexity and sensitivity to noise. Standard MKKM requires calculating and decomposing $n \times n$ kernel matrices, leading to an $O(n^3)$ complexity that becomes a massive bottleneck for large datasets. Furthermore, because MKKM relies on point-to-point relationships, outliers can easily distort learned cluster boundaries.

This paper introduces GB-MKKM, a novel clustering framework that shifts the optimization from $n$ individual samples to $m$ "granular balls" (where $m \ll n$). By prioritizing global distribution features over individual data points, the authors achieve significant speedups and improved robustness against noise while outperforming state-of-the-art methods.

Methodology

The core innovation is the Granular-Ball-Induced Kernel (GBK). The framework follows a structured pipeline to reduce complexity while maintaining representational power.

The GB-MKKM framework: from granular-ball generation to multiple kernel fusion.
  1. Granular-Ball Generation: The algorithm adaptively covers the dataset with balls. It starts with a coarse ball and splits it into smaller ones if the "Center-Consistency Measure" (CCM)—a ratio of average radius to maximum radius—falls below a threshold. This ensures balls accurately fit local data density.
  2. Kernel Construction (GBK): Instead of computing a kernel between two points, the authors define the kernel between two balls. This is mathematically represented as the expected kernel value between all points within those balls.
  3. Multiple Kernel Fusion: The framework fuses multiple GBKs using a weighted combination. Because the number of balls $m$ is much smaller than the number of points $n$, the resulting kernel matrix is only $m \times m$.
  4. Optimization (GB-SMKKM): The authors adapt the "SimpleMKKM" approach into a granular version, using a parameter-free minimization objective solved via gradient descent to find optimal kernel weights and cluster assignments.

Experimental Setup

The researchers evaluated their method on 12 diverse datasets ranging from gene expression and images to text and noisy synthetic data. These included single-view datasets like GLIOMA and JAFFE, and multi-view datasets like Caltech101-7 and Handwritten. The datasets varied in sample size (50 to 10,000) and dimensionality (9 to 7,454), providing a rigorous test for scalability and robustness.

Key Insights

  • From Points to Distributions: By treating a granular ball as a "small local distribution," the model captures essential data structures while naturally smoothing over individual outliers.
  • Complexity Reduction: The computational bottleneck drops from $O(n^3)$ to $O(m^3)$. For the Handwritten dataset ($n=10,000$), the number of balls $m$ was approximately 500, an order of magnitude reduction.
  • Noise Filtering: Granular balls effectively exclude noise because outliers either fail to form consistent balls or are relegated to very small, low-weight granules that do not dominate the optimization.

Key Results

The proposed GB-SMKKM consistently outperformed several strong baselines across almost all metrics. On average, it improved Clustering Accuracy (ACC) by 6.83% and Normalized Mutual Information (NMI) by 13.93% compared to standard SMKKM.

Critical Difference (CD) diagram showing the statistical superiority and ranking of GB-SMKKM against baselines.

Efficiency gains were equally striking. On the Ds8 dataset, GB-MKKM was roughly 4x faster than standard MKKM. Paired T-tests confirmed that the improvements in ACC, NMI, and ARI were statistically significant ($P < 0.05$), as visualized in the ranking diagrams.

Limitations and Future Work

While the paper demonstrates clear advantages, performance relies on the initial granular-ball generation threshold ($\lambda$), which is currently determined empirically. Future work may involve integrating this framework into deep architectures for multi-kernel clustering in neural networks and investigating the impact of the "curse of dimensionality" on initial ball splitting in extremely high-dimensional spaces.

Summary updated

BibTeX
@inproceedings{xia2025granular,
  author = {Shuyin Xia and Yifan Wang and Lifeng Shen and Guo-Yin Wang},
  title = {{Granular-Ball-Induced Multiple Kernel K-Means}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/738},
}
Figure