COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Authors: Weixuan Liang
Xinwang Liu
KE LIANG
Jiyuan Liu
En Zhu
Venue: ICML 2025 poster (2025)
Keywords: Multiple Kernel Clustering
Multi-View Clustering
Primary area: general_machine_learning->clustering

Abstract: Inspired by the well-known coreset in clustering algorithms, we introduce the definition of the core kernel for multiple kernel clustering (MKC) algorithms. The core kernel refers to running MKC algorithms on smaller-scale base kernel matrices to obtain kernel weights similar to those obtained from the original full-scale kernel matrices. Specifically, the core kernel refers to a set of kernel matrices of size $\widetilde{\mathcal{O}}(1/\varepsilon^2)$ that perform MKC algorithms on them can achieve a $(1+\varepsilon)$-approximation for the kernel weights. Subsequently, we can leverage approximated kernel weights to obtain a theoretically guaranteed large-scale extension of MKC algorithms. In this paper, we propose a core kernel construction method based on singular value decomposition and prove that it satisfies the definition of the core kernel for three mainstream MKC algorithms. Finally, we conduct experiments on several benchmark datasets to verify the correctness of theoretical results and the efficiency of the proposed method.

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Weixuan Liang' Xinwang Liu
Ke Liang' Jiyuan Liu? En Zhu'
Abstract
struggles to handle large-scale datasets, making it difficult to meet the demands of the big data era.
Inspired by the well-known coreset in cluster- ing algorithms, we introduce the definition of the core kernel for multiple kernel clustering (MKC) algorithms. The core kernel refers to running MKC algorithms on smaller-scale base kernel ma- trices to obtain kernel weights similar to those obtained from the original full-scale kernel ma- trices. Specifically, the core kernel refers to a set of kernel matrices of size (11/=?) that per- form MKC algorithms on them achieve a (1 approxxiitooinii for the kernel weights. Sub- sequently, we can leverage approximated kernel weights to obtain a theoretically guaranteed large- scale extension of MKC algorithms. In this paper, we propose a core kernel construction method based on singular value decomposition and prove that it satisfies the definition of the core kernel for three mainstream MKC algorithms. Finally, we conduct experiments on several benchmark datasets to verify the correctness of theoretical results and the efficiency of the proposed method.
To address the high complexity of MKC, this paper intro- duces the concept of core kernel, inspired by the idea of coreset (Har-Peled & Mazumdar, 2004; Chen, 2009). In the field of clustering, the coreset technique an essential method for reducing the complexity of algorithms on large- scale datasets. A coreset is a weighted subset of the training set, such that the algorithm obtains a solution similar to the one derived from the entire training set. The coreset method has been proven to be effectively applicable to k-median (Sohler Woodruff, 2018), CeeennsCoheen-aae 2022), and kernel k-means clustering (Jiang al., 2024).
et al.,
In MKC, a fundamental assumption is that the optimal ker- nel matrix is weighted combination of the base kemne matrices (Huang et al., 2012: Liu et al., 2016; Liu, 2022). Thus, kernel weights are a crucial parameter that can sig- nificamtly impact the final clustering performance. Multiple kernel k-means (MKKM) (Huang al., 2012) minimizes the objective with regard the kernel weights and clus- tering partition. After the optimization of kernel weights, MKKM can obtain better clustering performance compared to using fixed weights. Subsequently, (Liu et al., 2016) in- troduces a matrix-induced regularization term for the kernel weights to increase the diversity of the consensus kernel ma- trix. To avoid kernel weights falling into poor local optima, (Liu, 2022) proposes min-max optimization-base objec- tive function, which enables learning better kernel weights. Therefore, for good approximation method, it is neces- sary to better approximate the kernel weights of the original algorithm.
1. Introduction
Multiple kernel clustering (MKC) algorithms (Zhao et al., 2009; Liu, 2023; 2022; Ren Sun, 2020; Liu et al., 2017: 2016; Li et al., 2016; Feng et al., 2025), which have a strong capability to handle multi-source data, have been widely applied in various fields. MKC can be applied in various areas, including cancer biology (Gönen & Margolin, 2014), urban VANETs (Sellami & Alaya, 2021), healthcare (Che & Yang, 2024), network security (Hu et al., 2021). and others. However, due to the high computational complexity, MKC
To quantitatively analyze the approximation degree of the kernel weights, we attempt to adapt the concept of "coreset" to MKC algorithms. We define smaller-scale base kernel matrices that can well approximate the kernel weights of the original base kernel matrices as the core kernel. The formal definition of the core kernel can be found in Defi- nition 3.1. By using a core kernel of size ((1/e2)) as the input to MKC, we can obtain the (1 + -)aaproxximttion kernel weights. With the approximated kernel weights, we
'College of Computer Science and Technology, National Uni- versity of Defense Technology, Changsha, China. *College of Systems Engineering, National University of Defense Technology, Changsha. China. Correspondence to: Xinwang Liu <xinwan- gliu@ nudt.edu.cn.>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
*Ö(+) hides logarithmic terms.

---

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
design large-scale extension method for MKC algorithms with theoretical guarantee. Then, we propose effective method for constructing the core kernel. Our method is inspired by the observation that the singular values of the column sampling matrix can effectively approximate the full kernel matrix. Specifically, we first select s anchors, where 8 is much less than the sample number n. For each base kernel, we construct a kernel similarity matrix whose elements are computed based on the full training set and the anchor set through the kernel function. We then use the right singular vectors and the singular values to construct s x s core kernel, and this method is termed singular value decomposition -ased core kernel (SVD-CK). The detailed process of the SVD-CK method placed in Section
contexts of use. For any kernel function used in this paper, we assume that / I K(x, S with positive constants I, b. The number of base kernels yn and clusters & are both assumed to be constants.
2.1. Multiple Kernel Clustering
Multiple kemel clustering (MKC) (Huang et al., 2012) is an extension of kernel k-means (KKM) (Dhillon et al., 2004). Assume that the sample space is X,, the training set is S =
{1, )i=1 S Xx and the kernel function is K : X x X + R. The objective function of KKM is
(2K(II-HHH)) s.t. H 12
min ur H
In the existing literature on the large-scale extension of MKC, (Liang et al., 2023) achieves good approximation of kernel weights by using random sampling. However, the method in (Liang et al., 2023) requires sampling many data points to achieve a sufficiently ideal approximation, which increases the computational cost during the algorithm's 's it- erative process. As an improvement to the above method, (Liang et al., 2024) achieves better approximation results based on SVD, but its computational complexity is rela- tively high and related to The method proposed in this paper, SVD-CK, achieves an approximation performance comparable to that of (Liang et al., 2024). Moreover, during the algorithm's 's iterative process, it reduces the computa- tional complexity to be independent of n. Additionally, the methods of (Liang et al., 2023; 2024) are solely designed to accelerate the SMKKM (Liu, 2022). In contrast, the method proposed in this paper can accelerate more MKC algorithms based on kernel weight learning, offering a broader range of applications.
where H E Bank is termed clustering indicator matrix, and K E Rax" is the kernel matrix whose elements can be represented by Kú = K (xx,,,)) One can perform aggendecomppostiion on K and let H be the first & largest eigenvectors. Then, the clustering results can be obtained by performing standard h--maans on H.
In the actual execution of KKM, we do not know which kernel function performs better. Therefore, we can select m multiple kernel functions and compute base kernel ma- trices {k accordingly. A fundamental assumption of the MKC algorithm is that the optimal kernel matrix is weighted linear combination of the base kernel matrices. During the optimization process, the clustering indicator ma- trix and kernel weights are jointly optimized. In this section, we introduce two MKC algorithms. The first one is multiple kernel k-means (MKKM) (Huang et al., 2012). Denoting that A is the simplex constraint, the objective function of MKKM is
(1 K, -HH))
Finally, experiments are conducted on several benchmark datasets to evaluate the approximation performance of SVD- CK on three mainstream MKC algorithms. The experi- mental results demonstrate that the proposed method can effectively approximate the kernel weights learned from the whole kernel matrix. Furthermore, the experiments also verify that the scalable extension method can be effectively applied to multiple large-scale datasets, proving the effi- ciency of the proposed approach.
min tr 7.H
(I)
s.t. H H YEA,
where K,, = =1 P2 and 7 hn.... . 7ml are the kernel weights. Another highly influential MKC algorithm is SMKKM (Liu, 2022), and its objective function is
min f(7), s.t. 7 EEA,
(2)
where f(7) maxH H=I, tr (H,, Whether MKKM SMKKM, the computational complexity of ob- taining the optimized kernel weights reaches (n²), which limits its application to large-scale datasets. It is noticed that MKC algorithms can also handle multi-view datasets, if we construct a kernel matrix for each view.
2. Related Work
Before we introduce the related work, we briefly introduce basic assumptions and mathematical notations.
Basic mathematical notations and assumptions. We use ||- to present the spectral norm of a matrix or the 2-norm of vector. For some vector x, ||x||>o = max; |a=|- f(-) g(-) means ʃ(-) & cg(-) with some positive constant c. We provide definitions for all other symbols in their respective
2.2. Coresets of Approximation Clustering
(Har-Peled & Mazumdar, 2004) introduces the concept of coreset for approximation clustering. A general definition of clustering is as follows.
2

---

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Definition 2.1 (Clustering Loss, (Har-Peled & Mazumdar, 2004)). For a set of points S from sample space X, with weight function w 8 + IR and clustering centroids C, let (c(S)= = Eves w( (z))((x, C*) as the clustering loss of the k-median clustering caused by C, where d(x,, C) = minyec d(x, y) is the distance between I and C. Similarly, denote that (S) = Exes w(x)d((x, C)² is the clustering loss of k-means clustering of S caused by the clustering centroids C. Moreover, the clustering loss of the optimal k-median and k-means clustering for S are respectively denoted by
by performing some MKC algorithm on {K p=p== are x'. For some positive integer 8, K, {K, }رm C Ix* is another set of kernel matrices, and the corresponding kernel weights are â obtained from the same MKC algorithm. K2 is a (1 + approxxmmatio core kernel set of Kn, if 0 - a 2 E.
Remark. As seen, the core kernel is concept proposed for the approximation of kernel weights. If the time com- plexity of some MKC algorithm is O(n"), one can obtain the approximated kernel weights from the core kernel with time complexity Oss)). When s < n, the time cost of the MKC algorithm can be dramatically reduced. Moreover, by incorporating the Nyström method (Wang et al., 2019), the construction of the core kernel enables the MKC algorithm to handle large-scale datasets, which we will introduce in the next subsection.
(S, min (S(S) and O_X,[C]=k
(3)
(S,k)
oCx, (S).
min
The main idea of the coreset is to identify a small, weighted subset T of the large dataset S, ensuring that performing a clustering task on this subset can yield an approximately optimal solution for the original dataset. The specific defini- tion of coreset is as follows.
3.2. Large-scale Extension for MKC Algorithms
Now, we introduce how to use the core kernel set for the large-scale extension of MKC algorithms with Nytröm method (Wang et al., 2019). Suppose that there is an anchor set (randomly sampled from the training set S) (a1.-... .a,) and core kernel set K, = (K)) For some MKC algorithms, we can use the core kernel set to obtain group of the approximated kernel weights â. The complexity of MKC algorithms is usually Os*"). Then, we construct m kernel similarity matrices (P, }mm S IR*x where the element in the i-th row and j-th column of Pp is Kp ()()),))) Then, make a weighted combination of pp by Pa = -pm PPP. The summation of (P pp] costs (mms)) time. Then, we can perform SVD on Pa. and obtain its first k left singular vectors H. This step costs O(ns²) time. Finally, we can obtain the clus- tering results by performing the standard k-means H. Above all, the time cost is basically linear with the sample number n (if m, & n). and thus, it can be used to han- dle large-scale datasets. The above large-scale extension method is listed in Algorithm 1.
Definition 2.2 (Coreset, (Har-Peled & Mazumdar, 2004)). A weighted set T S X is (coreeet of S for the k- median clustering, if VC' C X of k points, the following equality holds,
(1- S (T) S (1 (1)))
Similarly. T is (ki c)-corettt of S for the k-means cluster- ing, if VC C X. we have
(1 (1-)) S Pc(T) S (11 + ())c))((S).
A coreset is general data compression tool that allows clus- tering algorithms to run on smaller-scale datasets, enabling the attainment of good approximate solution with reduced computational cost. In the MKC algorithm, the objective function typically lacks explicit clustering loss and cluster centroids, while the kernel weights play critical role in determining the clustering performance. Therefore, this pa- per proposes the concept of "core kernel," inspired by the idea of the coreset, to approximate the kernel weights in the MKC algorithm.
We will now conduct theoretical analysis of the above algorithm. Before that, we need to introduce a common assumption.
Assumption 3.2. For any vector y E RT", let the difference between the j-th and (j + 1)-th eigenvalues of the kernel matrix K,, be denoted as 6, (r)) For any j E [A]] and any 7 E A, there exists a constant e 2 0 such that 8,(7) 2 1/c.
3. Core Kernel and Its Application for Large-scale Extension
In this section, we introduce the core kernel definition and its application for the large-scale extension of MKC algorithms.
Remark.
The assumption regarding eigenvalue gaps is quite common in matrix perturbation theory (Stewart, 1990). Specifically, when studying the perturbation of cigenvectors or orthogonal projections, researchers often assume that the gaps between eigenvalues are greater than a certain constant. (Von Luxburg et al., 2008) assumes that all eigenvalues of
3.1. Definition of Core Kernel
< is a set of base kernel matrices, and the kernel weights obtained
Definition 3.1. Assume that K,, = K 1m
3

---

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Algorithm 1 Large-Scale Extensions of MKC by Core Ker-
4.1. Construction Idea
nel
Now, we present the construction idea of the core kernel. Our main objective is to approximate the spectrum of X kernel matrix by a X s one.
1:
Input: Training set m kernel functions {Kp('.) Ip= anchor sets A = { (sampling from S = { J
without replacement); core kernel set {K ) num- ber of clusters k.
Spectral approximation (Weinberger, 1974; Swartworth & Woodruff, 2023) of matrices is an essential field in linear algebra. It aims to approximate the eigenvalues or eigenvec- tors of large-seale matrices. Given n X n kernel matrix - K, computing the precise spectrum of _ K is massive problem when n is large. Alternatively, can random- ized methods to approximate the spectrum of J K. The most straightforward and often effective method is uniform sam- pling. Specifically, let E R be a random sampling ma- trix, and every column of T has only one non-zero element. Assume that we uniformly sample s indexes (i....., {.. from {1, .n] n3 without replacement. For the j-th column of T, its elements
2:
Output: clustering indicator matrix H: the clustering results.
3: Perform MKC algorithm core kernel set to obtain approximated kernel weights ã.
n
4: Compute m base kernel similarity matrices (p))
by P pi( = Kp(z,,a)) for any i E [m].] E [s].
5: Make the weighted combination of (Pp) 1m by Pa =
_p
a p.
6: Perform SVD on P& to obtain its first & left singular
vectors H E TR
7: Perform k-means on H for the final clustering results.
be represented as Ti 1, if = in and Tij O, otherwise. Assuming that W = --TKT KT, then we can use the eigenvalues of W to approximate the eigen- values of KK. Denoting that P = T K. another method is using the singular values of 1 P for the approximation of 1 K's eigenvalues.
T
the Laplacian matrix are distinct, which is analogous to the assumption of eigenvalue gaps. In other research of kernel clustering (Liang et al., 2024; Mitz& & Shkolnisky, 2022), the authors also make this assumption.
vns
Theorem 3.3. Under Assumption 3.2, denote that the ker- nel weights output by performing some MKC algorithm on the original base matrices p yn p=1 is a, and the corre- sponding clustering indicator matrix is H, i.e., the first k eigenvectors of K a- When the inputs of Algorithm I are (1 +++))-appp approximmaaonnn core kernel set, denote that the output kernel weights are â which satisfies l|ā ax Z where 3 denotes inequality up to constant factor. If the anchor number& & 2 clog(n/ / the clustering indicator matrix
Empirical observations. We conduct numerical experi- ments on two kernel datasets to verify the approximation effect of the above two methods. Flower17 and CCV are two commonly used multiple kernel datasets, and we aim to approximate the eigenvalues of their average kernel matri- ces. We then compute " K's largest & eigenvalues {Ag 1 (in a descending order). For two approximation methods, we construct T randomly, and compute !''s largest l eigenvalues along with - P's largest i singular values. vns
j=1
H output by Algorithm I can make
Fixed the anchor number s, we compute the difference be- tween the precise eigenvalue and the approximated one for every j E [k.] We let the maximal difference be the ap- proximation error. We let vary in (50- 50 1000} and record the variations of the approximation errors. To reduce the randomness, we repeat the above experiments 30 times and plot the mean values in Figure 1. As seen from Figure 1, the approximation effect of vns P is much better than W. However, the time consumed by SVD decomposition of Vns Ths is relatively high. Therefore, when constructing the core kernel, we aim to combine the strengths of two approximation methods, i.e., achieving an approximation of SVD decomposition using the matrix with size
HH
F
holds with probability at least - 6.
Remark. Theorem 3.3 gives an upper bound of the differ- ence between the subspace spanned by H and H. When is sufficiently small, the clustering performance by performing k-means on H and H will be similar. Theorem 3.3 gives a theoretical guarantee that we can use the core kernel set and Algorithm approximate the original MKC algorithms effectively. The proof can be found in Section C. of the appendix.
Theoretical observations. Next, we conduct a theoretical analysis of the approximation effect of A P's singular
4. Construction Method and Theoretical Analysis
values on the eigenvalues of LK. This is also crucial for our subsequent analysis of the properties of the core kernel. We have the following theorem.
In this section, we present a method for constructing the core kernel. We then provide a theoretical analysis and prove that our method can produce the core kernel set for several MKC algorithms.
Theorem 4.1. Let T E R be a random sampling matrix and for the j-th column (j E [s)), Túj = 1 with probability
4

---

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
7lower77
Flower17
CCV
CCV
0/12
0018
W
0.06
P) 1,1KK
0065
0.16
0/014
0.90
Aggosiiniie Ertor
0004
Argrntimiiion Error
0012
0005
0.003
0012
0.11
Time
0.01
0.055
0.000
0.000
0.02
0.0%
0.000
0.055
0.0%
00002
0.002
0.02
0.00
550 Ancbor Number
830
533
030
700
Anzbor Number
Anchor Number
Anchor Number
Figure 1. The comparison on the cigenvalue approximation errors of two methods, i.c., the eigenvalues of : W (red curves) and the singular values of Jms
P (blue curves).
1/n and Ti = 0 otherwise. Assume that P Then, if 2 clog(n/0)/e² for some positive constant, with probubility least 6, for all I. [n))
K.
Algorithm SVD-based Core Kernel Construction
I: Input: Training set S = {-;] anchor set A
{a:)i= base kernel functions (Kp(.-))m= ym
Output: Core kernel matrices {K
( 1 T18
1 -K
Ae
SS
for p 1: m do
((p,))=((ozi..0 4: Compute P by Pp(i..) = (p(zi,ag) az).
5: Perform eigen-decomposition on P, P,P, such that
where ()(.) the t-th singular value of some matrix, and Xx(.) is the 1-th eigenvalue.
P. p P, V,D.V.p.
6: Let the p-th core kernel matrix be K VyDi/VV.
Remark. Theorem 4.1 proves that using SVD) decompo- sition can effectively approximate the eigenvalues of the whole kernel matrix, providing a theoretical foundation for constructing the core kernel. The proof of Theorem 4.1 can be found in Section C.2 of the appendix.
p
end for
In this section, we first analyze the proposed Algorithm from a theoretical perspective. Then, we utilize the core kernel for the large-scale extension of MKC algorithms and give the corresponding theoretical analysis.
4.2. SVD-based Core Kernel
Based on the previous subsection, we begin constructing the core kernel and propose an algorithm based SVD. For better approximation,
4.3. Theoretical Analysis of SVD-based Core Kernel
use the singular values of 1. P to approximate the eigenvalues of K. Meanwhile, to reduce computational costs, use the right singular vectors of V Pa as the eigenvectors of the core kernel.
The most significant difficulty of the analysis is the different sizes of the original kernel and the core kernel. To address this issue, we need to introduce the following empirical integral operator Lx associated with K (Von Luxburg et al., 2008).
Vns
Specifically, first randomly select anchors A (a:)i= from 5 = {x:) For the p-th base kernel, de- noting that the corresponding kernel function is (,),,), we can compute P, whose element can be computed by ((. = K,(z,,a)) (i E [n].] J E [s)). Then, we per- form eigen-decompossition on P P, and denote p
Lx C(x)) + C(X),
(4)
LKf(x) = Σ K(x, (x)
P.P.P, V,D,V VJ where V, E R D,, E Rx Notice that the diagonal elements of 1 is the first s singular values of Pp and Vp is composed of the corresponding singular vec- tors. Then, we can construct the core kernel matrix of the p. The pseudo- code is provided in Algorithm 2. It can be seen that the algorithm we propose is very simple and easy to implement.
where C(x²) is the space of continuous functions defined on X. Then, I, and _ has the same non-zero eigenvalues and the eigenfunction of Lx
p-th kernel by 1 K, = 1 V, //2VT Vns
yns
1 a
he(x) = nde
Σ ((r,z;))(
5

---

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
where hy(2;)) Vhhgg by is the i-th component of h, and (Ae, h2) is the 1-th eigen-pair of K. A detailed introduc- tion of the empirical integral operator and its perturbation property can be found in Section B. 1 in the appendix.
Lemma 4.2. For any kernel weights Y, when the number of anchors clog(n/5)f with some constant c O,
(Tn ( TT, (13)) ke,
holds with probability at least 1 - 8.
We then rewrite the core kernel matrix into the form of a function, i.e., the kernel function associated with the core kernel K. For some kernel function K( ((.,)), assume that vns the corresponding feature map is Φ(-), i.e., o (zr)(()= K(x, y). Denote that D, n. ( ... ((2n)) and Φ, (6(a1). ... ((a))] ]. It can be checked that
By Lemma 4.2, we can derive the following Lemma 4.3 under Assumption 3.2.
Lemma 4.3. Under Assumption 3.2, for any kernel weights ar 3, when the number of anchors 8 2 clog(n/0)/e with some constant c. > 0,
1
[Tx } (T,p (Kp: (T
1==0 S 11a3311 +
D. 2 Ln
D n
Pn)
1 p..
n8
118
118
holds with probability at least 1 5.
+1/2 then the kernel function associated with K can be represented by ((r.y)- = (x)( ((V))
Denote II'
2. Φ pn)
Remark. Lemma 4.2 gives the differences between the alignment level of the base kernel and core kernel for the same kernel weights. Furthermore, Lemma 4.3 gives the alignment differences with different weights. The proofs of the above lemmas are in C.3. By combining Lemma 4.3, can utilize the recurrence relation to analyze the gradient differences of the base kernel and the core kernel during each step of the optimization process in the gradient descent- based MKC algorithms. Subsequently, we can prove that the SVD-based CK constructed by Algorithm 2 satisfies the definition of a core kernel as described in Definition 3.1 for SMKKM (Liu, 2022) and SMKKM-KK KWW (Li et al., 2023) (Theorem 4.4). Moreover, with some additional conditions, SVD-based CK is also the core kernel of MKKM-MR (Liu et al., 2016) (Theorem 4.5). The proofs of Theorem 4.4 and Theorem 4.5 are respectively placed in Section C.4 and Section C.5 of the appendix.
Assume that (Ne, he) is the t-th eigen-pat pair of 1 K. We let the first & eigenfunctions of L be (h,(-)} i.e.
vns
1 Σ K a(
hx(x)= SAt
where ha. = Shhj.. and haj is the 1-th component of he Based on the above definitions of empirical operators and eigenfunctions, we can define the alignment level between the p-th base kernel function (p(.,)) and eigenfunctions ( by
Theorem 4.4. Under Assumption 3.2, if 2 clog(n/8)/s², with probability at least - 5, Algorithm 2 produces (1 + --apprrxximation core kernel set for SMKKM and SMKKM-KWZ
(Kp. (he 1-1 n²
Similarly, the alignment level between the p-th core ker- nel function -p(s-) -) and eigenfunctions (h)(-)} can be given by
Theorem 4.5. Denote that the elements of M, M mR are respectively the Frobenius inner products of original and core base kernel matrices, i.e., Mpq = tr( 122 K K2 1 ns K,KK)). Under Assumption 3.2, if 2
and MM = tr( clog(n/5)) /)2 and M, M have fill ranks, with probability at least 1- Algorithm produces a (1+5) -aprrxxiiaato core kernel set for MKKM-MK.
T. T.(Kp, (h1)
(h1))
ka, at (d(
= 8²
j=1
For any kernel weights γ h...... 7ml T_ letting (x, Em= (x Suppose that the corre- sponding eigenfunctions of the empirical integral operator LK, are {h?) = Similarly, for the same kernel weights, suppose that the weighted combination of the core kernel matrices is (x. y) = p=1
5. Experiments
In this section, we conduct two kinds of experiments. The first one is verify that Algorithm 2 can produce the core kernel set for SMKKM, SMKKM-KWI KWRR and MKKM-MR. In the second kind of experiment, we then demonstrate that the core kernel set can also enable the above three MKC algorithms to handle large-scale datasets efficiently. All the above experiments are conducted on a computer with a configuration of Intel(R) Core(TM)-i7-108)) CPU.
2 (T, y). We assume that
the eigenfunctions of T.R,, are ( The following two lemmas give the upper bounds of the differences between the alignment level of the p-th base kernel and core base kernel with their corresponding eigenfunctions.
6

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
5.1. Information of the Kernel Datasets
5.3. Large-Scale Experiments
To verify the approximation effect of the core kernel on the kernel weights, selected six small-scale kernel datasets for experimentation, including Flower17, Digit, CCV, Flower102, 4Area, and Cal Their links and de- tailed information are reported in Section D.2 of the ap- pendix.
Table I. Large-scale datasets
Number of
Dataset
Samples
Views
Clusters
Features
CIFARIO
50000
3
10
512,2048, 1024
MNIST
60000
3
10
342, 1024, 64
Winnipeg
325834
2
7
49, 38
5.2. Approximation Effect of Core Kernel on Kernel Weights
Experimental setting. To validate the effectiveness of Algorithm 1, this section also conducts tests several commonly used large-scale datasets, including CIFARIO. MNIST and Winnipeg'. Their detailed information is re- ported in Table 1. The number of samples in the datasets used in the experiments exceeds 50, 000, with the largest be- ing 325, 834. For each view, base kernel similarity matrix is constructed using a Gaussian kernel function as follows:
Experimental setting. We conduct experiments on three MKC algorithms, i.e., SMKKM, SMKKM-KWR and MKKM-MR. For the methods with hyper-parameters we let all of the apper-parameters be equal to We first perform the MKC algorithms the original kernel datasets to obtain set of kernel weights, denoted as a. Then, we randomly selected s distinct numbers {i1, .. . from (1.....n1) where n is the number of samples in the training set. Then, we use the indices {i....., , to construct a core kernel set by Algorithm 2. We perform the MKC algorithm on the core kernel set and denote the corresponding kernel weights by ā. Let The value of vary within the range [50: : 50 1000], with the constraint that s is less than the number of samples but greater than the number of clusters. For each s, we record the value of || |=| To reduce randomness, we repeated the experiment 30 times and com- puted the average of | ael no. The experimental results are shown as the blue curve in Figure 2. Additionally, for comparison, construct
K (I,, 0z) exp (- [| - ag 12
(5)
20
where x, E S(i [n]) and a E A(t E [s]). In the proposed algorithm, is set 500. The parameter o² represents the average squared distance between the sample points in S and A, and is computed as:
1 T18
Σ
Σ
|| - aell
(6)
IIES a.EA
base kernel matrices via uniform sampling from the selected indices {ii,...,,, , selecting the corresponding rows and columns. We also recorded the difference between the kernel weights obtained from the original kernel matrices and the kernel matrices based on uniform sampling. After repeating the experiment 30 times, the average value is shown as the red curve in Figure 2.
Table 2, Results large-scale experiments
Datasets
CIFAR10
MNIST
Winnipeg
NMI (%)
RMKMC
82.07
81.05
49.43
LMVSC
45.04
84.75
51.94
OPMC
83.81
82.67
50.82
AWMVC
76.38
80.76
38.86
SMKKM (CK)
97.53
97.00
54.14
SMKKM-KWR (CK)
97.78
96.96
$4.12
MKKM-MR (CK)
98.07
97.33
59.24
Experimental results. Due to space limitations, only the ex- perimental results on two datasets, i.c., Flower17 and DIGIT, are presented in the main text, while the results on other datasets can be found in Section D.1 of the appendix. From the blue eurve, it can be observed that as increases, the kernel weights obtained by the algorithm on the proposed SVD-CK rapidly approach those obtained the original kernel matrices. This fully demonstrates the correctness of Theorem 4.4 and Theorem 4.5. The red curve represents the kernel weight error obtained by the algorithm on the kernel matrices based on uniform sampling. It can be seen that the proposed method significantly outperforms uniform sampling. In addition, a relatively small can achieve a low approximation error on kernel weights, which highlights the effectiveness of SVD-CK in enabling scalable extensions of MKC algorithms.
Time (s)
RMKMC
162.09
155.16
297.40
LMVSC
16.22
67.44
142.63
OPMC
27.56
49.94
20.29
AWMVC
203.01
64.78
59.77
SMKKM (CK)
47.84
65.18
288.06
SMKKM KWR (CK)
43.61
65.77
248.51
MKKM-MM (CK)
38.99
62.26
259.24
For comparison, experiments are also conducted on several state-of ffute-of-ther th-the- large-scale multi-view clustering algorithms,
Pttpp: http://www..oooottoee//////r/rre far. html
h http://iiiieeeeaeaa////aaaaaaaan
525 heep:c/enammpiiinssssrrrrreeaiar data+aet

---

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Flower17 (SMKKM)
Flowort7 (SMKKM KWR)
Flowor17 (MKKM MR)
011
5:54
SVD-based Core Kemel
SVD-baaed Core Kernel
SVD-based Care Keree
Rendomly Samplin
0.37
Randomly Sampling
Randomly Sampling
0.1
0.00
0.55
0.50
0.06
6:15
0.30
0.32
010
5:04
200
400
250
1000
100
300
-00
52C
620
1000
200
300
200
700
Anchorr Number
Anchor Number
Anchor Number
DIGIT (SMKKM)
DIGIT (SMK0G KWR)
DIGIT (ZK))--MR)
0.806
0.30
0.06
SVD- based Core Kamai
SVD-based Core Kernal
SVD -e---baddd Core Kemai
Randomly Sampling
0.00
Randomly Sampling
Randomly Sampling
2.000
0.325
0.004
0.012
0.00
0.315
0.21
0.000
0.02
0.000
0.35
0.04
0.52
103
202
300
400
530
500
700
300
900
1000
100
200
300
400
505
020
702
600
500
1000
120
200
330
500 Anchor Number
430
200
700
300
500
1300
Anchor Numbor
Anchar Number
Figure 2. The proposed SVD-CK is illustrated through diagram showing the kernel weight approximation performance. The blue curve represents the kernel weight approximation error constructed using SVD-CK. It can be observed that as increases, the approximation error decreases rapidly, enabling the weights obtained by the three MKC methods on SVD-CK to closely approximate those the original kemne matrices. For comparison, the red curve represents the kemel weight approximation error hased on random sampling of the kernel matrix. SVD-CK demonstrates a clear advantage in kernel weight approximation.
including: RMKMC (Cai et al., 2013), LMVSC (Kang et al., 2020), OPMC (Liu et al., 2021), and AWMVC (Wan et al., 2024). Detailed information on these comparison methods is reported in Section D.3 of the appendix. For the above comparison algorithms with hyper-parameters, the optimal are selected via grid search as described in the corresponding papers. Our experiments employ three widely used clustering metrics: accuracy (ACC), normal- ized mutual information (NMI), and purity. Additionally, we record the exccution time for all experiments. Due to limited space, we only show NMI and execution time in the main text. We use Algorithm 1 for the large-scale exten- sions of SMKKM, SMKKM-KWR, and MKKM-MR, and they are termed SMKKM (CK), SMKKM-KWR (CK), and MKKM-MR (CK), respectively. The experimental results are presented in Table 4, with the best outcomes highlighted in bold. For the whole experimental results, please refer to Section D.4 of the appendix.
the perspective of clustering efficiency, the proposed large- scale extension of the MKC algorithms can obtain clustering results quickly, indicating that the computational cost is rela- tively low. The above experimental results fully demonstrate the effectiveness and efficiency of Algorithm 1.
6. Conclusion
This paper introduces a new concept, the core kernel, to ad- dress kernel weight approximation in multiple kernel cluster- ing algorithms. We define the core kernel and, based this definition, propose a theoretically guaranteed large-scale ex- tension method for MKC. Subsequently, we introduce SVD- CK, a core kernel construction method based on singular value decomposition. We prove that SVD-CK satisfies the definition of the core kernel for the three MKC algorithms. Finally, we validate the approximation performance of SVD- CK for kernel weights on several commonly used kemel datasets. Additionally, on large-scale datasets, we verify the effectiveness and efficiency of the proposed large-scale extension method. Although this paper only explores the approximation of MKC, the proposed method demonstrates strong potential for broader applications. In particular, could be extended to analyze the approximation algorithms of multi-view clustering (Yu al., 2024; 2023), which is direction we intend to explore in future work.
As shown in Table 4, the proposed method enables the three MKC algorithms to operate on large-scale datasets. From the perspective of clustering performance, the three MKC methods demonstrate better clustering results compared to several large-scale multi-view clustering algorithms that directly process the original features of the data. This is because the kernel functions are effectively utilized, allow- ing better handling of non-linearly separable datasets. From
8

---

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Acknowledgments
Gönen, M. and Margolin, A. A. Localized data fusion for kernel k-means clustering with application to cancer biology. In Advances in Neural Information Processing Systems, pp. 1305-1313, 2014.
This work is supported by the National Science Fund for Distinguished Young Scholars of China (No. 62325604), the National Natural Science Foundation of China (No. 62306324, U24A20333, 62441618, and 62276271), and the Science and Technology Innovation Program of Hunan Province (No. 2024RC3128).
Har- Pele-Peled, S. and Mazumdar, S. On coresets for k-means and k-median clustering. In Proceedings of the thirty- sixth annual ACM symposium on Theory of compuling (STOC), pp. 291-300, 2004.
Impact Statement
Hu, N., Tian, Z., Lu, H., Du, X., and Guizani, M. A multiple- kernel clustering based intrusion detection scheme for 5g and iot networks. International Journal of Machine Learning and Cybernetics, pp. 1-16, 2021.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Huang, H.-C., Chuang, Y.-Y,, and Chen, C.-S. Multiple kemel fuzzy clustering. IEEE Transactions on Fuzzy Systems, 20(1):120-134 2012.
References
Bach, F. Sharp analysis of low-rank kernel matrix approxi- mations. In Conference on learning theory ( (COLT), pp. 185-209. PMLR, 2013.
Jiang, S. H.-C., Krauthgamer, R., Lou, J., and Zhang, Y.
Coresets for kernel clustering. Machine Learning, pp. 1-16, 2024.
Bakshi, A., Chepurko, N., and Jayaram, R. Testing positive semi-definiteness via random submatrices. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS). pp. 1191-1202. IEEE, 2020.
Kang, Z., Zhou, W., Zhao, Z., Shao, J., Han, M., and Xu, Z. Large-scale multi-view subspace clustering in linear time. In AAAI Conference on Artificial Intelligence (AAAI), pp. 441 4412-4419, 2020.
Cai, X., Nie, F., and Huang, H. Multi-view k-means clus- tering on big data. In Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), 2013.
Li M., Liu, X., Wang, L., Dou, Y., Yin, J., and Zhu, E. Multiple kernel clustering with local kernel alignment maximization. In Proceedings of the Twenty- In- ternational Joint Conference on Artificial Intelligence (IJCAI), pp. 1704-1710, 2016.
Che, H. and Yang. X. A multi-kernel-based multi-view deep non-negative matrix factorization for enhanced health- care data clustering. IEEE Transactions on Consumer Electronics, pp. 1-1, 2024.
Li, M., Zhang, Y., Liu, S., Liu, Z., and Zhu, X. Simple mul- tiple kernel k-means with kernel weight regularization. Information Fusion, 100:101902, 2023.
Chen, K. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing, 39(3):923-947) 2009.
Liang, W., Liu, X., Liu, Y., Ma, C.,, Zhao, Y., Liu, Z., and Zhu, E. Consistency of multiple kernel clustering. In International Conference on Machine Learning (ICML), pp.
Cohen-Addad, V., Larsen, K. G., Saulpic, D., and Schwiegelshohn, C. Towards optimal lower bounds for k- median and k-means coresets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Comput- ing. pp. 1038-1051, 2022.
PMLR, 2023.
Liang, W., Tang, C., Liu, X., Liu, Y., Liu, J., Zhu, E., and He, K. On the consistency and large-scale extension of multiple kemel clustering. IEEE Transactions on Patlern Analysis and Machine Intelligence (TPAMI), 2024.
Dhillon, I. S., Guan, Y., and Kulis, B. Kernel k-means: spec- tral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference Knowl- edge discovery and data mining. pp. 551-556, 2004.
Liu, J., Liu, X., Yang, Y., Liu, L., Wang, S., Liang, W., and Shi, J. One-pass multi-view clustering for large-scale data. In Proceedings of the IEEF/CVF international conference on computer vision (CVPR), pp. 12344-12353, 2021.
Feng, Y., Liang, W., Wan, X., Liu, J., Liu, S., Qu, Q. Guan, R., Xu, H., and Liu, X. Incremental nyström- multiple kernel clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 39, pp. 16613-16621, 2025.
Liu, X. Simplemkkm: Simple multiple kernel k-means. IEEE Transactions on Pattern Analysis and Machine In- telligence (TPAMI), 45(4):57-111 2022.

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Liu, X. Hyperpaarmmeter-free localized simple multiple ker- nel k-means with global optimum. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023.
Wan, X., Liu, X., Liu, J., Wang, S., Wen, Y., Liang, W., Zhu, E.,, Liu, Z., and Zhou, L. Auto-weighted multi- view clustering for large-scale data. In AAAI Conference on Artificial Intelligence (AAAI), number 8, pp. 10078- 10086, 2024.
Liu, X., Dou, Y., Yin, J., Wang, L., and Zhu, E. Multiple kernel k-means clustering with matrix-induced regular- ization. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 1894, 2016.
Wang. S., Gittens, A., and Mahoney, M. W. Scalable kernel k-means clustering with nyström approximation: relative- error bounds. The Journal of Machine Learning Research, 20( 20(1):31-449, 2019.
Liu, X., Zhou, S., Wang, Y., Li, M., Dou, Y., Zhu, E., and Yin, J. Optimal neighborhood kernel clustering with multiple kemels. In Proceedings of the Thirty-Firss First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pp. 2266-2272, 2017.
Wedin, P.-A. Perturbation theory for pseudo-inverses, BIT Numerical Mathematics, 13:217-232, 1973.
Weinberger, H. F. Variational methods for eigenvalue ap- proximation. SIAM, 1974.
Mitz, R. and Shkolnisky, Y. perturbation- based kernel ap- proximation framework. In Journal of Machine Learning Research, volume 23, pp. 1-26, 2022.
Yu, S., Liu, S., Wang, S., Tang. C., Luo, Z., Liu, X., and Zhu, E. Sparse low-rank multi-view subspace clustering with consensus anchors and unified bipartite graph. IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2023.
Perozzi, B., Akoglu, I.., Iglesias Sánchez, P., and Müller, E. Focused clustering and outlier detection in large attributed graphs. In Proceedings of the 20th ACM SIGKDD inter- national conference on Knowledge discovery and data mining (KDD), pp. 1346-1355, 2014.
Yu, S., Wang. S., Zhang, P., Wang, M., Wang, 7., Liu, Z.,, Fang, L., Zhu, E., and Liu, X. Dvsai: Diverse view-shared anchors based incomplete multi-viww clustering. In Pro- ceedings of the AAAI Conference on Artificial Intelligecce (AAAI), volume 38, pp. (6568-16577) 2024.
Ren, Z. and Sun, Q. Simultaneous global and local graph structure preserving for multiple kernel clustering. IEEE transactions neural networks and learning systems, 32 (1),1839-1851, 2020.
Yu, Y., Wang. T., and Samworth, R. A useful variant of the davis-kahan theorem for statisticians. Biometrika, pp. 315-323. 2014.
Sellami, L. and Alaya, B. Samnet: Self-adaptative multi- kernel clustering algorithm for urban vanets. Vehicular Communications, 29: 100332, 2021.
Zhao, B., Kwok, J. T., and Zhang, C. Multiple kernel clustering. Proceedings of the 2009 SIAM international conference on data mining, pp. 638 649. SIAM, 2009.
Smale, S. and Zhou, D.-X. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153-1) 2007.
Sohler, C. and Woodruff, D. P. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 802-813. IEEE, 2018.
Songgui, W., Mixia, W., Zhongzhen, J., et al. Matrix in- equality, 2006.
Stewart, G. W. Matrix perturbation theory. Citeseer, 1990.
Swartworth, W. and Woodruff, D. P. Optimal eigenvalue ap- proximation via sketching. In Proceedings of the 55th An- nual ACM Symposium on Theory of Computing (STOC), pp. 145-155, 2023.
Von Luxburg, U., Belkin, M., and Bousquet, O. Consistency of spectral clustering. In The Annals of Statistics, pp. 555-586, 2008.
10

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
A. Brief Introduction of SMKKM, SMKKM-KWR, and MKKM-MR
this section, we introduce SMKKM (Liu, 2022), SMKKM-KWR (Li et al., 2023), and MKKM-MR (Liu et al., 2016) and their optimization method.
1. SMKKM. (Liu, 2022) The objective function of SMKKM is
min f()), s.t. 7EA,
where [(7) maxH n- HHH The optimization of SMKKM is based reduced gradient descent method. Specifically, fixed some index [mi, the reduced gradient of fo is follows,
0f(r)
0f(7),
@f(7)
of(7))
[
Ap
[V
Σ
(8)
0%p
0%
0%pp
pzuu
where
0f(7) 87 (r, (HT) and H arg min H I tr (r(KK (I,
2T
To keep the positivity constraint of y, the descent direction d [di, dml T can be set as
0,
if 7/P = 0 and 0f(m) 8f(7)
> 0,
0%p
87u
af(7) 0f(7)
dp =
m-
8%p
if 7p > and # u
(9)
m E Eptur19200
05(7)
of(r)
for p
0ge
0hP
Compared with (Liu, 2022), in this paper, the reduced gradient is divided by for the normalization of the w-th component. Nevertheless, the reduced gradient of this paper still makes f(y) converge within several iterations. The updating scheme is 7 = + rjd, where v) is assumed to be less than some constant c 0.
SMKKM-KWR. (Li et al., 2023) SMKKM-KWR is an improvement of SMKKM, and its objective function
min f(r), s.t. Y A,
(10)
where f(y) maxp H-T, tr ( (H) + Ally - -ol12. where Yo denotes the average kernel weights. The p-th
component of the gradient is 0f(7) 27z tr (t, (I, H) + 2A(7p %0p), and H arg min H-I, tr(K, (I,
Oyr
HH )). Similar to SMKKM, SMKKM-KWR can be optimized using the reduced gradient descent algorithm.
3. MKKM-MM. (Liu et al., 2016) MKKM-MR is an enhanced version of MKKM, and the objective function is
(In HHT) + Ay MY, s.t. 7 E A H I
min ir
7.H
where À is hyper-parameter, M mm and its element can be represented by Mpy = tr (,, (for p, [m]). The optimization of MKKM-MR is based on coordinate descent method as follows.
1) Optimize H with fixed 7. Perform the eigen decomposition on K.y, and let H be its first eigenvectors.
2) Optimize y with fixed H. Let 8, = tr (I, HH and D |Rxx be a diagonal matrix with Dpp = 8p (for
p E [m]). Then, 7 = L (AM+D) 11,..
(AM+D) '1,
the optimal solution.

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
B. Preliminaries of Proofs
B.1. Empirical Integral Operator and Perturbation Theory
We first introduce the empirical integral operator (Von Luxburg et al., 2008) associated with some kernel matrix K E R"x" K E R can be regarded as an operator from R R R", i.e.,
1 Σ ==1
Kw
K 31),
Σ 1=1
K (rnn 2i Wi
for any w = =[1,," wn] T E R". Then, the empirical integral operator Lx associated with 1 K is
LK: C(X) + C(X), Lxf(x) 1 Σ ((z,x;)faa.)
where C(X) denotes the space of continuous functions defined on N. LK has the same non-zero eigenvalues with 1 K. Let {* A (in a descending order) be the non-zero eigenvalues of L and _K. Assume that the corresponding eigenvectors of _ K are ( ,h,. Then, the t-th (t E [4] eigenfunction he of LK n
ha(x)
((r,
nd i=1
where (x,) = Vnhaa, and ha the i-th component of hy. The following theorem gives a perturbation bound of the empirical integral operator.
Lemma B.1 (Theorem 7, (Von Luxburg et al., 2008)). Let (E, (1E) be Banach space, and let B denote the unit ball in this space. Let (Kn)nen+ and K be compact operators on E, with Kn converging to K. For a non-zero eigenvalue E (K), let Pr denote its corresponding spectral projection. Let M C C be an open neighborhood of such that ((K n = X. There exists an integer E N such that for Vn > N, (KK) n M = X is isolated in o (KK)). ). Let Pr denote the spectral projection corresponding to of (Kn) n M for Kn. Then there exists a constant C such that for every PrE, the following holds:
| - Pr.æle E & C(I(K,, -KCKN K) + ||]| Kn).
(1I)
B.2. Concentration Inequalities for Matrices and Vectors
In our proofs, we need the following three concentration inequalities: The first one gives matrix Chernoff bound for the eigenvalues of sums of finite random matrices. The second and third are two inequalities of subsampled covariance matrices and vectors, respectively.
Theorem B.2 (Chernoff bound of eigenvalues (Bakshi et al., 2020)). Assume that (Ajhi2 a finite sequence of independent, random, positive-semidefin matrices with size n X n. If || s L for some positive real number almost surely, then the following tail inequalities hold
12/L
Pr Ex A2) 2 (1 5)μu
S (n
+ 1)
6
for O,
(1+8)1-1
(12)
14/T.
Pr >e A,) < 8)pk < k.
c-
for 8 [0,
(1-8)1-8
where fa = E(A)), and k(S n) is some integer.
2b,,1 E R' and || S R. for each E [n]. Let be an Theorem B.3 (Lemma2, (Bach, 2013)). Let L [ (I,..., nn without replacement. Then, for all E >> 0, index set that consists of elements sampled from
-s22/2
Pr
D.
> S exp
I. V.
(R 1/3)
Theorem B.4 (Lemmal, (Smale & Zhou, 2007)). Let H be a Hilbert space and (wb Pi= be s i.i.d. random variables valued in H. Assume that || < with some constant 0. Denote that o²= 112). Then,
SE2
Pr Σ (ab. - E(bb.))
2 < 2exp
2.R + 20
12

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
C. Proofs of Theoretical Results
C.1. Proof of Theorem 3.3
To prove Theorem 3.3, we need the following lemma on the upper bound of matrix cigenvector perturbation.
Lemma C.I. (Yu et al., 2014) Let A, E TRuxx be Hermitian matrices with eigenvalues A 2 ... 2 Xn and X₃ ... An >s41) > 0, where Xo == co and An+1 == -c0 Let = s - + 1. Assume that H [hr hr+1, ... .hsl E Rnxd and H = [hr. hy41, ,h,] E Rn are column- orthogonal and satisfy, for any j E {r, 1. 88. Ab; = Azhا and Bh,- = A5h3, Then, there exists an orthogonal matrix O Raxxd such that
respectively. Fix 2 r S I n, and assume min (1 Ar. A
2 min /2 A BII ||A BlFF)
HÒ - H||
(13)
min (p--1 Xa, X Aat1)
Proof. Let H be the first & eigenvectors of Ka. For any orthogonal matrix Ô R have
HH
HH
HOO
H
HÓH
HÓH
HH
(14)
HÒJ
HÒ
[
HÒ
F
$2
HÒ
By setting r = 1,8 = k Lemma C.I, according to Assumption 3.2,
HH
HÒ
H
F
Ka
1 K
VA
5(a)
n
K2 (3 v2)
21
(ā
a2)²
n²
[=1
(15)
a az)²
max
K2 (2(2)x0))
(E(N),1(M))
a apl
Σ (āp + ap)
pE [[]m]
i appl
l| az x 3
pE [m]
Notice that H is the first eigenvectors of 1 LP.PT. ns
Then, by Lemma C.I,
HAA
HH
Vi
ns
PPPTT K2
n
3 Vk
1
P &
- K2 n
(16)
8(ā)
For any kernel matrix K E RRxn let E R be its s columns selected by uniform sampling. Let 1/2
(xx)) in $
vn
Theorem B.3. Then, in Theorem B.3, 1 M V = 1 2 and least 1 - 5,
1 L
us 1PP By Theorem B.3, with probability at
1
PP T
K2
Ne.
n n²
According to (q.(1 we have
HH HH
3 Vks.
13

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Combining Eq,(1 with probability at least 6,
HH
HH
HH
3 c.
C.2. Proof of Theorem 4.1
Proof. Denote that T = [t,,... .t.). Then, Aj 1 Kt K and Σド= A LKT K. is can be checked that t n K Thus, 2j-1 [[A,] = + K2. Moreover, ||A = d K have
By Theorem B.2, for any
A₂) 2 (1 +0p0 (n (c-1)))000)))))))((t1)) M/2
Pr
A Ag)
(n (n=-++1) 1)
(17)
(Because 8 - (1 + 8) log(1 -52/2.)
Let 8 = _
we have
vPa
Pr
Ae Σ Aj) 2 (1 81/4
I (n (n-t++ 1) -
Consequently, with probability at least
(n - 1-11+10 1+ -
de A( A2) S (1+ )m
Vhh
Thus, for any s 2
(6) 6²
E
A,)
<
/44 S (1
VPn
V44
By the definition of
and Ma, have
Vns
1
| K
P
X
(18)
Vns
n
Now, we proceed to prove the other half of Theorem 4.1. According to Theorem B.2, for any 8 [0. 1),
Pr
X Σ A2)
(1 5)14
St. 66- [6-6-(1-0) log(1)))))))))))
oue St.e 2
(19)
(Because 8 + (1-6)loghl - 8) 2 82)2.)
Let - we have
VPr
Pr
X E 51 5)m0 $1.e-
which is equivalent to
E 11 S dxl EAA A,)
vph
14

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
holds with probability at least - e 2 For any 2 2log(n/ ( due to
we have
VP I /a
(1
U S
Ael
Aj):
Vuu
VPL
holds with probability at least 6. By the definition of oz
(w and (izs we have Vns
K
-
E S 0z
P
(20)
Vns
Combining Eq.(18) and (q,,) by union bound, when
2 2log(2n/8)
with probability at least - 6,
(LP)
P
K
E.
T25
n
C.3. Proof of Lemma 4.2 and Lemma 4.3
Lemma C.2 (Theorem 7.3.2, (Songgui et al., 2006)). Assume that A, B are two PSD mutrices, and A x B Then, A & B.
Lemma C.3. sfs 2 clog(n/8)/s²,, with probability at least 5,
① d.
4 1 , 1/2
Se.
nss
+
Proof. Assume that sb: =
1 1 Φ3)
vs $ x ((z)))
Then, is easy to check that there exists a constant c >> 0 such
that || S e and
1
v
S c. By Theorem B.3, we have
1 -
- c. (c + t/3)
-s=
Pr
V v
>5 S nnxp
S exp
4c
It is equivalent to, for all 2 clog(n/0) // with probability at least
8,
(
((210)
+
( 1.
p.
T 4.
$
T
Se,
8
128
which implies
1
1
1 $ (
(1 e))
<
<
(1++).
ns
By Lemma C.2, we have
1
1
1/2
(L T
VI-E
Φ
$ VI+E.
ns5
For any E (0, 1), due to 1 5 VI- and VI+
+
we have
(1 6)-
6)
1 Φ
T
x
1
o5
1/2
& (1+e)
( ( To
15

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Then, obtain
1/2
4.
4
S
Ze
Proof of Lemma 4.2. For convenience of expression, we use {hz} to present (17)5-1 and {hy}i=1 present
{K]} ) Then, by triangle inequality, have
[T (K (h115=1) (K (h1))=1)
11
Ky(a, a (h
71
82
==
Σ
(,, 21),
Kyla,, ae (a)))a)))
82
j=
(21)
K Kplos, (1)
22
1=1
Ka (()()))))()))
Kylas, (a)
1=1
For any X, assume that (b()) h (z)) (r). For all i E [n]. it is easy to check that |/*b(x;)] S and B[[lvb<>:))1 S with some constant e >> 0. By Theorem B.4, with probability at least -- 6,
(aa)) 1 Σ (x;)
SE.
For Item A in Eq. (21), with probability at least
8,
1 n
n
(a.))
(a.))
46
(xx)
Σ ((a))
n Σ
(x,) + Σ (aa)
3e. (22)
n2
For Item 13 in Eq. (21), according to Lemma C.3, with probability least 1 - 5,
B x
1 - K,
1 K, p
1
(b dh Tb 1b )/22 S..
1/2
(23)
V ns
For Item C in Eq. (21), we have
c
Kyla, az)l - -
I sup (1))((a) (3h((1) (x))) 2.9
+ - (a - sup (1)h,(1)) (a,h, h((7))
(24)
s sup
sup 7l(xo)
#.y
3 Ilayh; - h
16

---

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
For any v; y E X, denote that
K(x,y)= 1
a(z,zz)K(z LRf(x)
K (1),
n
n²
and
K(x,y) v)
E K (() [g](2)
K K(x, x.) xx) (x,, ())())))
118
==1
By the definitions of cigenfunctions, it can be checked that { and { are {hy و the eigenfunctions of L and Lg, respectively. According to Proposition 18 of (Von Luxburg et al., 2008) and Lemma B.I, we have
|layh; h2lloo 3 ||(LRR L + 11(LR
L 3 IL L
(25)
Then, we process to magnify | - Lxll-
|| k
LK
sup
((x,))))
x
ns
I1f =1
sup x
((1
K K x K az)
12
1=1 t=1
n Σ
Σ K ((n, - 1 Σ
sup x o0
[K(,,,;)|
K(z,, a))
i=1
(26)
1 Σ
(((z))
1 n
Σ (()))(()))
- Σ H(a)d(a)))
sup
||1 71
"
sup
1
|[((z))l
Σ f(1))((1))
1 Σ f(a))o(a))
|1
n2
|o(x;)]
e 3 (By Lemma B.4.)
Combining (24,) (25) and (26)),) we know that C 3 e. According the derived bounds for A and B, if 2 clog(n/0)/E², with probability at least 1 8.
(Kp, (h1)) - ToKK,, (h,))1 ke.
Proof of Lemma 4.3. For any a. 3 E A, denote that Ha, H. are composed of the first & eigenvectors of K. and Kgg
respectively. Then, for any orthogonal matrix Ó bx we have
Ta (h }== - (K ( 1==1)
1 tr(K K, H H ) tr (K (gHH)HH)
n
K,
<
H.H HgH I
n
(27)
H.
H.
H H. OH
H. OH HaH
< H Ó
Ha ó Hg
+ Hg
H. Ó Hg
<2
H. Ó H
17

---

COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
For any vector a I let 8(): denote the gap between the k-th and (k: + 1)-th eigenvalues of the matrix 1 a By
Assumption 3.2, there exists constant 2 0 such that for any a A, 8( 1/c. Using Lemma C.I, let = 1 and = k, then we have:
K k 8(a)
|Ha -Hg) FF
3 || 31 oc.
(28)
Combining (27) and (28),
(Tp p. ( - Tm (n p. 1 1==1 2 l|a -B1
Thus, according to Lemma 4.2, with probability at least 1 - 6,
(Kp, ( (Rp ( )==1 I (Kps ( Tm (Kpz (119 ) ) + 1T (Kp: (()))-1)
-To(p: 1hg 1--1)
(29)
< $1 x B11 x + ke.
C.4. Proof of Theorem 4.4
Proof. 1) Proof for SMKKM. When the input is original base kernel matrices, in the updating process, we assume that the kernel weights are ( (t))) ... (T() in which ( denotes the kernel weights after the t-th updating. Correspondingly, when the input is core kernel matrices, assume that the kemel weights are 3(0) - .,()),,,..... ... . in the
optimization process. By the assumption of the same initialization of kemne weights, we have (0) = 3(0)
With some fixed index u E [ra]. for the t-th step, according to Lemma 4.3, we have
la((t1) - 3((+1)] - la - -1
<la(t+1) - aa -(8(++) - )(
Σ
c Tn (1gg()) )ラ=1) - TT (1g/00)
1 }3=1))
S m prtue
Σ
(TK)TT(Kpp (1(g(0))511 )1=1)) - - (1 }3=11)
4 (t) (Kg. (hg (1g(1)) }5=1) - To (Kgy (1 |3=1)
max
<E(m) [m)]
09 (1) Kg (igg9) (t) }/=1) - 3341) Tn Kg (hg
ik }
+ T (Kg (hg }1=1) - To0 (7g }
max
V mm)
(a() - |00) Tv (
2k + ((()
TT
- TK(KK (hg }|=n
max
4 mm]]
max (a() 4 + ||a(t) /3(t) + ks
B(0|
/E|m]
~31a0 (1) - 3(0 1100 + ke.
(30)
Similarly, for p E [m], p # u. we have
laf+1)
g((++)] - -1a - 1
- 0p
(1+1)
(((t)= (8(44)) -3
1
0 (((() (K,,, ) - -a on Tn ( 1/-1)]
(31)
1
(3(t)T.(K (
)/21)) - 26. T,(KKr (12100)
+ m 1
L/ (t) - -3(())
11,0 + ke.
18

---

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
Combining Eq.(30) and Eq)(31), with probability at least 6,
||a((+11 - 3((t1)) 2 (|aa -31 + ke.
-
Based on the above recurrence relation, it can be concluded that if & 2 (log(n///)//= =0(1/e2) with probability at least
1-6, 8,
- - 3 (|aTT-)) - -3((T1) + ke 3 ... || - 310 + KE,
which satisfies the condition of Definition 3.1.
2) Proof for SMKKM-KWR. The proof for SMKKM-KWR is similar to SMKKM. We use the same notation to represent the kernel weight changes at each iteration step.
With some fixed index u E [m]. for the t-th step, according Lemma 4.3, we have
la,(+11)
(1(+1) - 3((+1)| - |a!! |/611
< 10 (1++1 (1) ( )(
1
Σ
(T (Kpr 1hg (0) }/=1) (/11))==))000/
- - (To (1g )3=1) + 21)
a
m
pfuu
Σ PyN
(880) (T.( )/1)) +)= - (T (ii } + 2))
(32)
(t) (Tn( (hg 11 15 (hg(0))=1)++ -)
3//0 (T, (Kg: 1
) ) + 2)
max
q
g6 m
(t) TT(K (1g })=1) T. (KKr (hg"" الدرور + 2lao - 0
max
@Emm]
(t) -3() 100 + Ke.
Similar, for forp* u.pE [m].
l0 (1+1) - - 1aall-aapp- - -8/8 3 \1 -
-1100))3(1)11 1/00 + ke.
Combining all, with prohability at least - 5,
- ((+++)))ll 1o0 2 (1)ae(1)= -3((t) 1l,c + ks.
Based on the above recurrence relation, with probability at least - 5,
||a (T) - 100 I - - -p + ke .... x ll A.A
- (000 + ks = AT
which satisfies the condition of Definition 3.1.
C.5. Proof of Theorem 4.5
Lemma C.4. Assume that M e m is computed by core kernel, i.e., Mpg tr (2 probability at least - 8,
ns K.KKKK))) Ifs 2 clog(n/6)/E2, with
-mmIm & M M $ mmm..
Proof. For any two indexed p. E [m]. let K, = $ Fn and K, = V Un, where $ = =00((2)) (x((x))) and V = (1)())) (xn)) Let &. = (0)(a)), ... (p())) and V. = (0,(a1), (g,))) Consequently,
19

---

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
K ($, 4 1 a)) 12/2 and K2
(VV V,
11/2 v
Then, have
1
Mpg tr
cp
T 4 1 xx))
V
L
V
V
2//2/3
128
(33)
(V1ss
1
1/2
1/2
1/2
1/2
tr
T
$
V
T
V
T
V
ns
ns
Vns
vns
Thus, we can obtain
2 (v
1 125
1/2
1
1/2
Mpg
D.
11
n1
Let the SVD of - L. T be A, VI. where U1 RRxx V1 Rexe and A RR in which the diagonal elements /ns
in the first x block are j Ms. i.e., the singular values of be U2A2 VJ. and A2 contains the corresponding singular values A,, As Because the Frohenius norm unitarily invariant, we have
vns & Ds. Similarly, let the SVD of TTS
V
Mp Ú,A V
A U2A
V
1/2 1/22 U2A
A
1/2 1/2 A2
A
Σ m.
Denote that the eigenvalues of 1 1 Pn, and 1 1 n u are P1 and -., An. respectively. With similar derivation, we have
Mpg
i=1
Letting (ūs) and (2:)120t1 be O, by Theorem 4.1, we have
1
MMp Mpgl S (mnr made) S Σ
Ao) +
Σ
(i4 (
mild
S
Σ
+
A
ZE.
1=1
1=1
2=1
Thus, for unit vector u E R.m.
m
m
m
M M| sup 1 T (M M)ul
<
up - Mpg)1 SE
2
[ppl
S Em.
p=1
9=1
The desirable result follows.
Lemma C.5 (Theorem 4.1, (Wedin, 1973)). For any two m m real matrices A, B. if rank(A) = rank(B) = m, then
B A+I
B
A+
B
All -
Proof of Theorem 4.5. For any unit vector E m we have
))² m.
u Mu
Up nz k, = tr "
Kp
5 tr
1 Σ Up p=1
3
m.
(34)
p=1
Similarly, we also have u Mu 2 m.
We use the same notation to represent the kernel weight changes at each iteration step. Then, by the optimization of MKKM-MR, we have
20

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
(AM + D 11 'mm
(AM + D ((+)) 1
(a -3(41)
m (AM D(O) 1 1m
1 (AM + D(t)) 11
[I + + ( 1mm (AM -
(35)
min (M + D(0))-1mm M + D(1))-111) 11m
1(M + +D(1)) 1m (AM D 1m
min Vm
1T (AM+ D(0))
1 Imm, vm 1. (AM D -1 1
m
vm
v
Because |D( - 1, we have vm 1T (AM + D 1m 2 (Am + +1- x (Am)-1. Moreover, Vm
L17 (AM +
1 ( 1m x (Am)- Combining (35,, we have
||a - -B
<AI D(1)) (AM + D(0)) (09))111 mm 00
<X][ +
(AM + D(t))=11m 1m
I AA + +(()) -AM + 1(1))-111
SAm + (()) - D(0)) D (AM + B
(By Lemma C.5.)
(>/M M|| + [D(0) 1)
(By the assumption that M, M have full ranks.)
Aam max qE(m)
tr - K,))
1
tr(
1
K.))
+ max qE(m)
TT thg }5=1) To(Roi (hg }
Vns
3 (Aem + + ||ae") 1010-3p00 100)
311a
( 10 te.
(36)
We can obtain the desirable result based on the above recurrence relation. The proof complete.
21

---

COКE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
D. More Experimental Results
D.I. Approximation Effect of Core Kernel on Kernel Weights
Flowar102 (SMKKK
Flowert 3MMKKM-WFF
Flowor102 (MKKM
0.11
4
0.44
SVD based Cora Kamal
SVD based Core Kernel
SVD based Care Kamee
Randomly Samping
Randomly Sampling
0.025
Randomly Sampling
0.1
0.00
0.002
0.200
0.05
0.00
0.015
0.304
0.300
0.22
250
00.5
553
158
353
450
5.0
Anchor Number
Anchor Number
Anchor Number
CCV (BMKKM)
CCV (SMK034-KWF))
CCV (MKIOX-MF)
0.52
0.14
SVD-based Core Kemei
SVD DDD-based Core Kernel
SVD based Care Kemel
0.500
Randomly Samplin
0.00
Randomly Sampling
Randomiy Sampling
0.00
3.00
0.1
0.325
0.012
0.0
0.51
0.00
0.310
8:008
0.01
0.00
8:00
0.02
100
200
203
481
6.30
600
730
800
900
1000
100
200
300
100
600
608
705
600
803
1000
120
200
330
430
500
700
800
1000
Anchhrr Number
Anchor Number
Anchor Number
4Area (SMKKM)
4Aren KWF)
4Area (MKKM-MF)
SVD-based Core Kemee
SVD-based Core Kernel
SVD-based Core Kereel
Raidomll Samping
Randomly Sampling
0.3
Randomly Sampling
0:21
0.06
0.2
0.04
0.00
8:005
0.00
0.0
22
-20
300
322
1000
022
220
753
053
600
100
200
302
100
GEC
660
702
600
603
1063
54
100
300
360
455
563
653
750
600
550
Anchor Number
Anchor Number
Anchor Number
Call:02 (MKKM MR)
Cal 102 (SMKKM KWR)
Cal102 (MKKM MR)
SVD 200-based Core Kamei
SVD-based Core Kernel
SVD V/D-based Core Kemea
Randomly Samping
0.54
Randomly Sampling
Randomll Sampling
0.04
0.23
0.00
0.2
0.22
0.21
0.1
0.00
150
250
250
020
602
503
153
352
450
5.0
750
850
100
252
302
682
750
550
Anchor Number
Anchor Number
Anchor Number
Figure 3. The proposed SVD-CK is illustrated through diagram showing the kernel weight approximation performance. The blue curve represents the kernel weight approximation error constructed using SVD-CK. It can be observed that as increases, the approximation error decreases rapidly, enabling the weights obtained by the three MKC methods SVD-CK to closely approximate those the original kernel matrices. For comparison, the red curve represents the kemel weight approximation error based on random sampling of the kernel matrix. SVD-CK demonstrates clear advantage in kernel weight approximation.
22

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
D.2. Information of Kernel Datasets
The detailed information of six large-scale datasets is listed in Table 3, and their URL links
ottp:
Digit: http:://s...yaLL.ecd.ccc//.
httt:://www.robots.t
4Area: (Perozzi et al., 2014)
Cal102: http::htp///. http://wwww...iiio/./////. wew.hchhhcccccc.cccc.... htt.ccccce///maagaaaaaaaaaaaaaaa
Table 3. Six small-scale kernel datasets.
Number of
Dataset
Samples
Kernels
Clusters
Flower17
1360
7
17
DIGIT
2000
3
10
CCV
6773
3
20
Flower102
8189
4
102
4Area
4236
2
4
Cal102
1530
25
102
D.3. Information of Comparison Methods
Detailed information of comparison methods is as follows.
1) Robust Multi-View k-MMans Clustering (RMKMC)(Cai et al., 2013): RMKMC robust large-scale scale multi-view k-means clustering algorithm.
2) Large-Scale Multi View Subspace Clustering (LMVSC)(Kang et al., 2020): LMVSC constructs a similarity matrix using selected anchor points to reduce redundant computations in subspace clustering.
3) One-Pass Multi-View Clustering (OPMC)(Liu et al., 2021): OPMC eliminates the non-negative constraints in non-negative matrix factorization and integrates all views to achieve a unified partition.
4) Auto- Auto-Weigge Weighted Multi- Clustering AWWMCC)(War al., 2024): AWMVC derives coefficient matrices from the base matrices of different dimensions and fuses them to obtain the optimal consensus matrix.
23

---

COКЕ: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering
D.4. Whole Experimental Results Large-Scale Datasets
Table 4. Results of large-scale experiments
Datasets
CIFARIO
MNIST
Winnipeg
ACC (%)
RMKMC
82.95
85.60
62.25
LMVSC
49.50
86.14
60.25
OPMC
69.59
84.92
53.53
AWMYC
80.90
83.23
53.66
SMKKM (CK)
97.46
99.02
62.09
SMKKM-KWR (CK)
98.15
99.01
62.10
MKKM-MR (CK)
99.28
99.15
59.24
NMI (%)
RMKMC
82.07
81.05
49.43
LMVSC
45.04
84.75
51.94
OPMC
83.81
82.67
50,82
AWMVC
76.38
80.76
38,86
SMKKM (CK)
97.53
97.00
54.14
SMKKM-KWR (CK)
97.78
96.96
54.12
MKKM-MR (CK)
98.07
97.33
59.24
Purity (%)
RMKMC
86.78
86.74
65.98
LMVSC
58.96
89.14
70.31
OPMC
87.82
85.45
64.72
AWMVC
84.00
87.41
67.74
SMKKM (CK)
97.96
99.02
79.24
SMKKM-KWR (CK)
98.43
99.01
79.71
MKKM-MR (CK)
99.28
99.15
69.25
Time (s)
RMKMC
162.09
155.16
297.40
LMVSC
16.22
67.44
142.63
OPMC
27.56
49.94
20.29
AWMVC
203.01
64.78
59.77
SMKKM (CK)
47.84
65.18
288.06
SMKKM-KWR (CK)
43.61
65.77
248.51
MKKM-MR (CK)
38.99
62.26
259.24
24


Reviews:
[{"review_id": "tJ89VCAEkb", "reviewer": "Reviewer_qRUV", "summary": "This paper first proposes the concept of core kernel, and proposes a core kernel construction method based on singular value decomposition, and proves that it meets the core kernel definition of three mainstream MKC algorithms. The correctness of the theoretical results and the effectiveness of the proposed method are verified on multiple benchmark datasets.\n\n## update after rebuttal\n\nI keep my positive score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the feedback of Reviewer qRUV and have addressed each comment point by point, as detailed below.\n\n\n### Q1: The relationship between Algorithm 1 and spectral clustering.\n\nA1: Assume that the consensus kernel matrix obtained by the original multiple kernel clustering (MKC) is $\\mathbf{K}_ {\\boldsymbol{\\alpha}}$. The proposed Algorithm 1 is used to approximate kernel $k$-means on $\\mathbf{K}_ {\\boldsymbol{\\alpha}}$. Specifically, we utilize the first $k$ singular vectors of matrix $\\mathbf{P}_ {\\tilde{\\boldsymbol{\\alpha}}}$ instead of the first $k$ eigenvectors of matrix $\\mathbf{K}_ {\\boldsymbol{\\alpha}}$ to obtain clustering results similar to those of the original MKC algorithm. Our proposed algorithm is different from spectral clustering. However, our algorithm is similar to spectral clustering in the final step, where, after obtaining the clustering indicator matrix, $k$-means clustering is used to get the final clustering results.\n\n###  Q2: The relationship between Algorithm 2 and Nyström approximation?\n\nA2: Algorithm 2 and the Nyström method are both methods used to approximate the spectrum of kernel matrices, but they focus on different aspects as follows.\n\nDifferent usage: The Nyström algorithm mainly approximates the kernel $k$-means clustering results on a single kernel through the approximated eigen-decomposition of the kernel matrix. In contrast, our method is mainly used to approximate the kernel weights in MKC. \n\nDifferent output: The Nyström method outputs an $n\\times n$ kernel matrix with low rank. However, the size of the kernel matrices outputted by our algorithm is $s\\times s$. Therefore, the kernel matrix output by our algorithm is more suitable for approximating the kernel weights in the MKC algorithm. \n\n### Q3: What is the intuition of Algorithm 2?\n\nA3: Our intuition is that it is possible to approximate the weights of MKC on the original base kernel matrix using several base kernel matrices whose sizes are independent of the number of samples $n$. The kernel matrix $\\widetilde{\\mathbf{K}}_p$ output by Algorithm 2 can precisely approximate the spectrum of the original kernel matrix, and its size is $s\\times s$, which meets our conception.\n\n### Q4: Are the eigenvalues of Assumption 3.2 sorted?\n\nA4: Yes, the eigenvalues described in Assumption 3.2 are sorted in descending order, which is a common assumption in kernel learning theory. To avoid unnecessary confusion, we will clarify this point in the revised version.\n\n### Q5: Theorem 3.3 and Theorem 4.1 require a large $s$, but Flower17 in Figure 1 only has 1000 points.\n\nA5: The error bound derived theoretically may, for various reasons, be worse than the results observed empirically. However, empirical observations are always consistent with the theoretical results. The main reason for this phenomenon is that, under the necessary assumptions, the theoretically derived results hold universally under any conditions. In contrast, empirical observations fix certain conditions (such as the data distribution and the kernel function, etc.), which may lead the experiments to exhibit smaller errors. In the future, we also hope to obtain tighter error bounds under some reasonable assumptions, making them closer to the results of empirical observations.\n\n### Q6: Why is the approximation effect of $\\frac{1}{\\sqrt{ns}} \\mathbf{P}$ is much better than $\\frac{1}{s} \\mathbf{W}$?\n\nA6: The theoretical proof of why the approximation effect is better is also an issue we are currently researching. At present, we provide the following explanation for this phenomenon: $\\frac{1}{\\sqrt{ns}} \\mathbf{P}$ is constructed from the entire training set and the sampled anchor set, whereas $\\frac{1}{s} \\mathbf{W}$ is constructed solely from the anchor set. It can be seen that compared to $\\frac{1}{s} \\mathbf{W}$, $\\frac{1}{\\sqrt{ns}} \\mathbf{P}$ contains more information about the training set, which is why the approximation effect is better.\n\n### Q7: Draw the graph of the relative eigenvalue approximation errors $\\frac{|a-b|}{\\lambda_j(\\mathbf{K}/n)}$.\n\nA7: We have already plotted the graph of the relative eigenvalue approximation errors of the two methods. Please refer to the anonymous link https://anonymous.4open.science/r/ICML2025-8D7F/eigen_appro.svg. It can be seen that the relative approximation error of eigenvalues caused by SVD is much smaller than that of uniform sampling.\n\n### Q8: What kernels were used? Are they all Gaussian kernels? How are their parameters set?\n\nA8: For small-scale datasets, we used publicly available multiple kernel datasets. Relevant researchers carefully construct these datasets and make them available for public download. As for large-scale datasets, as described in Section 5.3, we employed the Gaussian kernel function and provided the corresponding parameters based on previous research experience.", "claims_and_evidence": "yes.", "methods_and_evaluation_criteria": "yes.", "theoretical_claims": "no.", "experimental_designs_or_analyses": "no.", "relation_to_broader_scientific_literature": "Inspired by the well-known core set in clustering algorithms, a definition of the core kernel is introduced to obtain kernel weights similar to those obtained using the standard basis kernel matrix.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The definition of the core kernel is interesting.\n\nThe paper provides solid theoretical guarantees.", "other_comments_or_suggestions": "please see questions.", "questions_for_authors": "1. What is the relationship between Algorithm 1($k$-means after using SVD) and spectral clustering? \n\n2. How is the proposed method  (algorithm 2) related to Neystrom?\n\n3. What is the intuition of Algorithm 2 (such as what is the meaning of Kp~)?\n\n4. Are the eigenvalues ​​of Assumption 3.2 sorted?\n\n5. Theorem 3.3 and 4.1 require a large $s$. (Flower17 in Figure 1 only has 1000 points?)\n\n6. the approximation effect of $\\frac{1}{\\sqrt(ns)}P$ is much better than $\\frac{1}{s}W$. Why is this? W is the eigenvalue calculated directly, while $\\frac{1}{\\sqrt(ns)}P$ is estimated using singular. Why is it better?\n\n7. Figure 1 only shows the difference $| a-b|$, but how big is $\\lambda_j(\\frac{1}{n}K)$? Can you show $\\frac{| a-b|}{\\lambda_j(\\frac{1}{n}K)}$ in a new figure?\n\n8. What kernels were used? Are they all Gaussian kernels? How are their parameters set?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F9wKaewfow", "reviewer": "Reviewer_hzsf", "summary": "This paper introduces a novel concept called the \"core kernel,\" which aims to approximate kernel weights in multiple kernel clustering (MKC) algorithms by running them on smaller-scale base kernel matrices. The core kernel, with a size of $\\widetilde{\\mathcal{O}}(1/\\varepsilon)$, achieves a $1+\\varepsilon$-approximation. The authors propose a core kernel construction method based on singular value decomposition (SVD-CK) and prove its applicability to three mainstream MKC algorithms (SMKKM, SMKKM-KWR, and MKKM-MR). Theoretical analysis shows that using the core kernel reduces the time complexity of MKC algorithms from $\\mathcal{O}(n^3)$ to $\\mathcal{O}(s^3)$. Experiments on benchmark datasets validate the approximation performance of SVD-CK on kernel weights, while tests on large-scale datasets demonstrate the efficiency of the scalable extension. The core contribution lies in providing a theoretically guaranteed framework for efficient large-scale extensions of MKC algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the work of Reviewer hzsf and respond to the review comments as follows.\n\n### Q1: Assumption 3.2 assumes eigenvalue gaps, but real-world data may violate this. If eigenvalue gaps approach zero, does Theorem 3.3 still hold? Please discuss this scenario.\n\nA1: The reason for making this assumption is that, in the perturbation analysis of matrix eigenvectors, the eigenvalues of a matrix are often considered to be isolated, and thus the eigenvalue gap is always greater than 0. Since the proof of Theorem 3.3 involves the results from matrix perturbation theory (Lemma C.1), we have to make this assumption in this paper.\n\nIn practical situations, even if there exist cases where the eigenvalue gap is 0, we conjecture that the above conclusions from matrix perturbation theory still hold. However, this would require more powerful mathematical tools. Currently, it is necessary to strengthen the conclusions regarding eigenvector perturbations in matrix perturbation theory to avoid this assumption.\n\n\n### Q2: Is the construction time of SVD-CK significantly higher than random uniform sampling? Please include runtime comparisons.\n\nA2: The method of constructing the base kernel matrix using random uniform sampling requires a time complexity of $\\mathcal{O}(s^2)$ since it only needs to sample the indices of anchor points. In contrast, the construction method of SVD-CK provided by Algorithm 2 requires a time complexity of $\\mathcal{O}(ns^2)$. However, this process only needs to be executed once, so it does not significantly increase the overall time of the algorithm. We compared the time taken to obtain the final kernel weights using random sampling and SVD-CK, as shown in the figure (https://anonymous.4open.science/r/ICML2025-8D7F/time_cost.svg). It can be seen that the total time for obtaining kernel weights using the two construction methods is roughly the same. This fully demonstrates that the proposed SVD-CK in this paper is not significantly less efficient than random uniform sampling.", "claims_and_evidence": "Key claims are supported by experiments and theory:\nClaim 1: SVD-CK can effectively approximate kernel weights.\nEvidence: Theorems 4.4 and 4.5 demonstrate that the SVD-CK method can produce a $1+\\varepsilon$-approximation core kernel set for SMKKM, SMKKM-KWR, and MKKM-MK. Figures 2 show that the kernel weight error of SVD-CK decreases rapidly as the anchor number $s$ increases, significantly outperforming random sampling (blue vs. red curves).\n\nClaim 2: The core kernel enables large-scale extensions for MKC.\nEvidence: Algorithm 1 first obtains approximate weights through the SVD-CK method, then combines the base similarity matrices using these weights, and finally derives the cluster indicator matrix via SVD on the combined matrix. Theorem 3.3 proves that if the algorithm inputs are identical, the cluster indicator matrix obtained through Algorithm 1 can arbitrarily approximate the cluster indicator matrices obtained by other MKC algorithms. Table 2 shows that core kernel-based MKC algorithms (e.g., SMKKM) achieve high clustering performance (NMI >97%) on datasets with 50k samples, with reasonable time costs.", "methods_and_evaluation_criteria": "Method Rationality: SVD-CK compresses kernel matrices via anchor sampling and SVD, aligning with coreset principles.\nEvaluation Criteria: Experiments cover benchmark datasets (e.g., Flower17, CCV) and large-scale datasets (e.g., Winnipeg), with metrics including NMI, ACC, and runtime.", "theoretical_claims": "Theorem 3.3\nStatement: Under Assumption 3.2 (eigenvalue gap), the subspace difference between the clustering indicator matrix $\\widetilde{\\mathbf{H}}$ from the core kernel (via Algorithm 1) and the original $\\mathbf{H}$ satisfies.\nPotential Issues: Validity of Assumption 3.2: Eigenvalue gaps may not hold for high-dimensional/noisy data where eigenvalues are densely distributed.\n\nTheorem 4.1\nStatement: The singular values of the uniformly sampled matrix approximate the eigenvalues of the original kernel matrix with $\\varepsilon$-error, high probability.\nPotential Issues: Uniform Sampling Assumption: May fail for non-uniform data distributions.", "experimental_designs_or_analyses": "Reproducibility: Hyperparameter settings (e.g., $\\sigma^2$ for Gaussian kernels) are clear, but code or implementation details for anchor sampling are missing.\nStatistical Analysis: Experiments are repeated 30 times for averaging, reducing randomness, but variance or significance tests are not reported.", "relation_to_broader_scientific_literature": "The paper connects to:\n1. Coresets in clustering (Har-Peled & Mazumdar, 2004).\n2.MKC algorithms (Huang et al., 2012; Liu, 2022).\n3.Large-scale kernel methods (Wang et al., 2019).", "essential_references_not_discussed": "The paper essentially covers the important relevant literature.", "other_strengths_and_weaknesses": "Strengths:\n1. Novelty: Extends coreset ideas to kernel weight approximation with solid theoretical analysis.\n2. Practicality: The method is simple and scales to datasets with over 300k samples.\nWeaknesses:\n1. Experiments only use the Gaussian kernel function, lacking validation on other kernel functions.\n2. Time costs for core kernel construction (e.g., SVD complexity) are not discussed.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Q1: Assumption 3.2 assumes eigenvalue gaps, but real-world data may violate this. If eigenvalue gaps approach zero, does Theorem 3.3 still hold? Please discuss this scenario.\n\nQ2: Is the construction time of SVD-CK significantly higher than random sampling? Please include runtime comparisons.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y9USHlSyoh", "reviewer": "Reviewer_s6E6", "summary": "The paper introduces a novel approach to multiple kernel clustering by proposing the concept of core kernel. This method aims to reduce the computational complexity of clustering large datasets while preserving performance.\n\n**Main Contributions:**\n\n1.\tCore Kernel Definition: The core kernel is defined as a set of smaller-sized kernel matrices that can approximate the original kernel weights with a (1+$\\varepsilon$)-approximation guarantee.\n\n2.\tAlgorithmic Contribution: The paper propose an algorithm based on SVD to construct core kernel efficiently. This algorithm significantly reduces the size of the kernel matrices while preserving essential information for clustering.\n\n3.\tTheoretical Guarantees: The paper provides theoretical proofs (Theorem 4.4 and Theorem 4.5) that establish the effectiveness of the core kernels in approximating the original kernel weights under certain assumptions, such as the existence of a spectral gap.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the comments of Reviewer s6E6 and have responded to them individually.\n\n### Q1: Why are kernel weights crucial?\n\nA2: In many previous studies, it can be observed that the kernel weights of multiple kernel clustering (MKC) algorithms have a significant impact on the learning performance of the algorithms. For example, in a classical reference [1] (https://ojs.aaai.org/index.php/AAAI/article/download/10249/10108), the authors compare various clustering metrics of the optimal single kernel, average kernel, and various MKC algorithms, showing that their clustering performances differ greatly. Different optimization principles for kernel weights, tailored to different datasets and learning scenarios, result in significant differences in clustering performance. According to the no free lunch theorem, for a specific problem, we need to adjust the algorithm correspondingly. The same applies to MKC algorithms, where it is essential to develop targeted kernel weight design schemes. The above empirical evidence fully demonstrates that the kernel weights of base kernels have a crucial impact on improving the performance of MKC algorithms.\n\n### Q2:  Discuss the relationship between the clustering subspace and the weights in the remark of Theorem 3.3.\n\nA2: For the original MKC algorithm, $\\mathbf{H}$ is the sample embedding used to obtain the final clustering results, while the approximate embedding proposed in this paper is $\\widetilde{\\mathbf{H}}$. We aim to demonstrate through Theorem 3.3 that the proposed method and the original algorithm can achieve similar clustering performance. To measure the difference between $\\mathbf{H}$ and $\\widetilde{\\mathbf{H}}$, the best way is to compare the distance between their projections. We will include a more detailed description in the revised version.\n\n### Q3: Why does the chosen value of the number of anchor points $s$ not correspond to the conclusion obtained in the theorem?\n\nA3: The main reasons are as follows: Firstly, the theoretical derivation is based on some general assumptions, and the conclusions obtained are valid under all conditions. However, in empirical observations, factors such as the distribution of the dataset, the kernel function, and other elements affecting the approximation effect may result in a smaller required value of $s$ in practice. Secondly, the boundary of the theoretical derivation is constrained by the matrix concentration inequality shown in Theorem B.3 of the appendix. In real situations, the concentration of the dataset used in experiments may be smaller than the upper bound presented in Theorem B.3.\n\n### Q4: Compare the clustering performance between the proposed method and the original algorithm.\n\nA4: We compared the NMI of the proposed algorithm and the original algorithm on SMKKM and MKKM-MR using two datasets, Flower17 and DIGIT. The number of anchors ranged from 100 to 1000, with a step size of 100. The final experimental results are shown in the figure (https://anonymous.4open.science/r/ICML2025-8D7F/NMI_RES.svg). It can be observed that when the number of anchors is around 500, the proposed algorithm achieves similar clustering performance to the original.\n\n### Q5: Elaborate on the differences between the proposed method and the algorithm in [2].\n\nA5: The method presented in this paper has the following advantages: 1. Wider Applicability: This paper proves that the proposed method can be widely applied to the kernel weight approximation of three types of MKC algorithms, whereas the method in [2] can only approximate one type of MKC algorithm. 2. Better Approximation Effect: As shown in Figures 2 and 3, the approximation effect of the proposed method is better than that of the method in [2].\n\n[2] Consistency of Multiple Kernel Clustering. ICML 2023.\n\n### Q6: Approximate different kernels with different anchor points.\n\nA6: We have attempted to use different anchor points for different base kernels to perform approximation. However, due to the inconsistency of the anchor sets, the approximation effect turned out to be rather poor. In multi-view clustering, some studies have employed different anchor points for different views and achieved promising clustering results. However, these works lack theoretical guarantees for approximation, and they do not provide theoretical insights that are applicable to our results. The reviewer’s suggestion is highly insightful for us, and we will attempt to address this issue in our future work.\n\n### Q7: Evaluate the quality of anchor points theoretically.\n\nA7: Compared with uniform sampling, importance sampling methods (such as leverage scores) can select more representative anchor points, allowing good approximation results with fewer anchors. However, this leads to inconsistency in the anchor points of different base kernels, which affects the final kernel weight approximation. This situation is similar to that described in Question 6, and we will investigate this issue in future work.", "claims_and_evidence": "The overall logic of the paper is quite clear. \n\n**Introduction**\n\nIt is important to emphasize the differences between this paper and the related work, highlighting the innovative aspects of the proposed method.\n\n**Motivation Needs More Detailed Elaboration**\n\nThe motivation of the paper requires more detailed elaboration to clearly illustrate the significance of kernel weights. Specifically, it should provide a more thorough explanation of why kernel weights are crucial and how they impact the final clustering results.", "methods_and_evaluation_criteria": "The methods section is well-organized, and the explanation regarding the core kernel is very clear. However, concerning matrix T, the paper mentions using uniform sampling, and it may be worth considering leverage score sampling as well.", "theoretical_claims": "The theoretical theorems and proofs presented in the paper are clear and rigorous. It is recommended to discuss the relationship between the clustering subspace and the weights in the remark section of Theorem 3.3, emphasizing the motivation behind it.", "experimental_designs_or_analyses": "The experimental design is relatively reasonable; however, there are several issues: \n\n1. Why does the chosen value of the number of anchor points s not correspond to the conclusion of the number s obtained in the theorem?\n \n2. It is recommended to include a comparison of clustering performance between the kernel weights \\alpha obtained from SMKKM and MKKM, as well as the kernel weights \\tilde{ \\alpha } proposed in the paper.", "relation_to_broader_scientific_literature": "The key contributions of this paper build upon prior research in clustering and kernel methods, particularly enhancing the understanding of anchor point selection and its impact on clustering performance.", "essential_references_not_discussed": "As far as I know, this paper has basically discussed all the essential related work.", "other_strengths_and_weaknesses": "Strength: the paper provides rigorous mathematical proofs to support their claims, ensuring that the proposed SVD-CK method has a strong theoretical basis.\n\nWeakness : the paper lacks performance experiments for the proposed method on small datasets.", "other_comments_or_suggestions": "It is recommended that the differences and advantages of the proposed method be elaborated in detail compared to the methods in “Consistency of Multiple Kernel Clustering”.", "questions_for_authors": "The paper uses the same anchor point set for all kernel approximations. Has there been any consideration of approximating different kernels with different anchor points?\n\nIn this paper, the number and quality of anchor points are relatively important. The theorems presented only provide conclusions regarding the number of anchor points. Has there been any consideration of whether the quality of anchor points can be theoretically evaluated?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All Reviewers agree on the novelty and theoretical contribution of this paper. Therefore, I recommend for Accept.
Decision: Accept (poster)