Research map / Learning theory and algorithms / Clustering

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering

ICML 2025 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces the "core kernel", a small s×s set of base kernel matrices built via SVD of anchor-based kernel matrices, whose MKC kernel weights provably approximate those from full kernel matrices, enabling a theoretically guaranteed large-scale extension of MKC.

Problem

Multiple kernel clustering (MKC) algorithms have O(n^3) cost in computing kernel weights, which makes them infeasible on large-scale datasets.

Approach

Define a core kernel as a small set of base kernel matrices (size O~(1/ε²)) on which running an MKC algorithm yields kernel weights within (1+ε) of those from full kernels; construct it via SVD of the n×s anchor kernel matrix (SVD-CK) and combine with Nyström-style anchor SVD for scalable clustering.

Key results

• On large-scale datasets, SMKKM (CK) reaches 97.53% NMI on CIFAR10 and 97.00% on MNIST, versus 84.75% best baseline (LMVSC) on MNIST and 83.81% (OPMC) on CIFAR10.
• MKKM-MR (CK) achieves 59.24% NMI on Winnipeg versus 51.94% for the best baseline LMVSC, with about 259 s runtime.
• Kernel weight error from SVD-CK decreases rapidly with anchor number s and is consistently lower than uniform random sampling of the kernel matrix on Flower17 and DIGIT.

Measured effects reported in the paper

Surprising findings

• Uniform random sampling of kernel rows/columns is noticeably worse at approximating kernel weights than SVD-CK, and the authors note SVD-based approximation is much better at eigenvalues though costlier than the simpler W-based approach.

Limitations

• Theory requires assumptions such as eigenvalue gaps (Assumption 3.2), bounded kernels, and constant number of base kernels and clusters.
• Theoretical guarantee for MKKM-MR requires additional full-rank conditions on the Frobenius inner product matrices.
• Experiments are limited to a laptop CPU and the approximation study uses only six small-scale datasets.

Experimental setup

Datasets: Flower17 Digit CCV Flower102 4Area Cal102 CIFAR10 MNIST Winnipeg

Benchmarks: CIFAR10 MNIST Winnipeg Flower17 Digit CCV Flower102 4Area Cal102

Metrics: NMI execution time kernel weight approximation error (L-infinity)

Baselines: RMKMC LMVSC OPMC AWMVC uniform random sampling core kernel

Builds on: SMKKM MKKM MKKM-MR Nyström method coresets for clustering

Closest papers by meaning

• Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel (NeurIPS 2022 · similarity 0.92)
• Hierarchical Multiple Kernel Clustering (AAAI 2021 · similarity 0.92)
• Optimal Neighborhood Kernel Clustering with Multiple Kernels (AAAI 2017 · similarity 0.91)
• Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.90)
• Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.90)
• Dynamic Similarity Graph Construction with Kernel Density Estimation (ICML 2025 · similarity 0.86)