Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel
Authors: Weixuan Liang
Xinwang Liu
Yong Liu
sihang zhou
Jun-Jie Huang
Siwei Wang
Jiyuan Liu
Yi Zhang
En Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Kernel method
Clustering
Algorithmic stability

Abstract: Multiple kernel clustering (MKC) is an important research topic that has been widely studied for decades. However, current methods still face two problems: inefficient when handling out-of-sample data points and lack of theoretical study of the stability and generalization of clustering. In this paper, we propose a novel method that can efficiently compute the embedding of out-of-sample data with a solid generalization guarantee. Specifically, we approximate the eigen functions of the integral operator associated with the linear combination of base kernel functions to construct low-dimensional embeddings of out-of-sample points for efficient multiple kernel clustering. In addition, we, for the first time, theoretically study the stability of clustering algorithms and prove that the single-view version of the proposed method has uniform stability as $\mathcal{O}\left(Kn^{-3/2}\right)$ and establish an upper bound of excess risk as $\widetilde{\mathcal{O}}\left(Kn^{-3/2}+n^{-1/2}\right)$, where $K$ is the cluster number and $n$ is the number of samples. We then extend the theoretical results to multiple kernel scenarios and find that the stability of MKC depends on kernel weights. As an example, we apply our method to a novel MKC algorithm termed SimpleMKKM and derive the upper bound of its excess clustering risk, which is tighter than the current results. Extensive experimental results validate the effectiveness and efficiency of the proposed method.

Stability and Generalization of Kernel Clustering: From Single Kernel to Multiple Kernel
Weixuan Liang'
Xinwang Liu Yong 2.
Sihang Zhou
Jun-Jie Huang'
Siwei Wang*
Jiyuan Liu'
Yi Zhang
En Zhu
School of Computer, National University of Defense Technology (NUDT), Changsha, China
Gaollng School of Artificial Intelligence, Renmin University of China, Beijing, China Beijjng Key Laboratory of Big Data Management and Analysis Methods, Beijing, China *College of Intelligence Science and Technology. NUDT, Changsha, China
Abstract
Multiple kernel clustering (MKC) is an important research topic that has been widely studied for decades. However, current methods still face problems: inefficient when handling out-of-sample data points and lack of theoretical study of the stability and generalization of clustering. this paper. we propose novel method that can efficiently compute the embedding of out-of-sample data with a solid generalization guarantee. Specifically, we approximate the eigen functions of the integral operator associated with the linear combination of base kernel functions construet diw-dimnniional embeddings of out-of-sample points for efficient multiple kernel clustering. In addition, we, for the first time, theoretically study the stability clustering algorithms and prove that the single-view version of the proposed method has uniform stability as O (Kn -3/2) and establish an upper bound of excess risk as Ô (Kn 3/22 + inn 1//)), where K is the cluster number and n the number of samples. We then extend the theoretical results to multiple kernel scenarios and find that the stability of MKC depends on kernel weights. As an example, we apply our method to novel MKC algorithm termed SimpleMKKM and derive the upper bound of its excess clustering risk, which is tighter than the current results. Extensive experimental results validate the effectiveness and efficiency of the proposed method.
Introduction
Multiple kernel clustering (MKC) 33 aims to learn optimal kernel from a set of pre-specified kernel matrices for high-quality partition. These methods usually assume that the optimal kemnel matrix is a linear combination of the pre-specified base kernels. By jointly optimizing kernel weights and a clustering indicator matrix, MKC improves the clustering performance of single-view kernel k-means (K))). In recent years, MKC algorithms have been extensively studied. Among these works, Lu et al. [23] propose to change the MKC framework into the form kernel alignment. Gönen et al. [9] propose employ localized method obtain more sample-specific information from the data. Recently, Liu et al. (20) propose a parameter-free MKC algorithm that adopts a novel min-max optimization framework and achieves state-of-ther art performance wide range of applications. Although impressive improvements have been made by the existing methods, there
"Corresponding author: sinwangliu@munn edu.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

still lacks an effective and computationally efficient mechanism to handle out-of problems. This makes them inefficient in both space and computational consumption for large-scale unseen samples. More specifically, since all existing methods need to conduct digen-decomposition over the matrix consisting of all visible samples as an intermediate operation, the pre-extracted information is blocked for the new coming samples. This makes the algorithms computationally expensive to handle large-scale datasets.
To improve kernel clustering scalability, methods such as Nyström 30 approximation and random Fourier feature (RFF) 3 are proposed. These two methods acquire the non-linear feature of samples in real space by approximating the kernel matrix. However, the Nyström method can't 't be implemented directly on out-of- sample points of MKC directly. The shortcoming of RFF is also obvious, i.e., the dimension of the learned embedding is comparably large such that the subsequent clustering process time-cossuming More seriously, because it's difficult to bound the difference of the kernel weights before and after the approximation, these two methods are rarely implemented on MKC algorithms. In this paper, we propose a general method with solid generalization guarantee. More precisely, we find that the main complexity is caused by recomputing eigenvectors for the embedding of new coming samples. To this end, through the study of the integral operator associated with the kernel functions, we propose to perform an eigen-decompositionn approximation [27] for MKC. Specifically, we learn eigen functions from the empirical optimal kernel generated from base kernels and then use these eigen functions to calculate the approximation embedding for the saat--ll-mppee data points. Then, a standard k-means algorithm can be performed on the learned embedding for clustering.
To theoretically analyze our algorithm, we propose novel stability evaluation criterion for multiple kernel clustering and establish the generalization bound accordingly. Algorithmic stability 2 is a key property to estimate the generalization bound of learning algorithms. The stability- stability-based technique 66 [4] is widely used in analyzing the generalization ability of learning algorithms. However, existing literature lacks research on the stability of clustering algorithms. Unlike supervised learning, which possesses labels as a deterministic standard, the risk function of clustering tasks is highly correlated with uncertain clustering centroids. Therefore, it is hard to analyze the algorithm stability for clustering. To address the issue, we start from single-view kernel k-means with a pairwise learning framework. We show that the proposed method has uniform stability as O (Kn 3/3). where K is the number of clusters and n. is the number of samples. Consequently, the excess KK/23/22 risk can be upper bounded by Ô (Kn 3/2 + n { We then extend the generalization bound
analysis from single kernel clustering to multiple kernel clustering and prove that the stability of MKC is related to the learned kernel weights. As instantiation,
use the above results to analyze the simple multiple kernel k-means (SimpleMKKM) 20) and derive a generalization bound as Ô ((m + 1) -3/2 + ninn--n- -122,, where m is the number of kernels. As far as we know, this is the tightest bound for MKC algorithms. Finally, we conduct numerical experiments verify the effectiveness and efficiency of the proposed method.
Our contributions are three-fold and can be summarized follows:
1) We propose an efficient method enable MKC algorithms to handle out-of-sample problems.
2) We successfully apply algorithmic stability to derive the generalization bound of the clustering algorithm for the first time. We study the stability of SimpleMKKM with our method and derive its excess risk bound.
3) By comprehensive numerical experiments, the experimental results show that the proposed algorithm is effective and efficient.
The rest of the paper is organized as follows. Section 2 introduces the notations used in this paper. Section discusse the related work. Section@descrrbee the proposed method. Section [ analyzes the stability and generalization of KKM the single kernel and then extends the proposed method to multiple kernel clustering. The experimental results are reported in Section Finally, the paper is concluded in Section 7 All proofs are placed in the appendix due to the limited space.
26 hides logarithmic terms.

---

2 Notations
To avoid confusion with mathematical notations, the uppercase and lowercase letters in bold denote matrices and vectors, respectively. For example, is a matrix, and a is a vector. The component of them is denoted by A. a;. Let us denote with X' the sample space and with P the corresponding data distribution. The training dataset S = {x;
C X is drawn i.i.d. from P. The empirical distribution P., is defined as (x) 1 if x S, otherwise O. We assume that kernel function k(:,)): X x X' + R is positive-defintt and conjugate symmetric function. From M. know that there exist a Hilbert space H and a feature mapping o(.) X - H such that Vx, x' E X. k(x, = (o(x), 6(x)) H.. The kernel function k(.,.) used in this paper satisfies that Vx, E X, k(x, x) k(x','' x'). We assume that for any x E X, |(xx)]| Σ 1. Let us denote with I, the 8 x identity matrix, and with llo the infinity norm. For the convenience, the probability measure p after differential d is omitted, ie., dx is short for dp(xx).
Related Work
In this section, we give a brief introduction to pairwise learning and algorithmic stability which are two main contents related our proofs.
Pairwise Learning. Pairwise learning defines loss function with respect to sample pairs. It has been successfully applied to metric learning311 bipartite ranking 22)]. AUC maximization [25] and etc. Assume that (X1. ... X,,) } are n samples drawn independently from some probability measure. Suppose that the learning model is parameterized by The empirical behavior of the learning model can then be evaluated by the empirical risk as:
R(w
l(x,, Xy; xy:
22 +,==1
where denotes the loss function. Accordingly, the expected risk can be defined as:
R(w)= /] (:
Among the rescarches of learning theory, Lei et al. [[5] establish a sharper generalization bound of pairwise learning, Li et al. [17] utilize pairwise learning framework to verify the generalization ability of clustering algorithms. In [16), Lei et al. study the generalization
stochastic gradient descent for pairwise learning. In [4] 17.. the authors learn the excess risk bound of clustering in the form of pairwise learning. As mentioned above, in the centroid-ban based clustering algorithms, is generally hard to investigate the stability of the samples at the boundary of two centroids. To tackle this problem, we adopt pairwise learning framework in our analysis.
Algorithmic Stability. The analysis of algorithmic stability is powerful technique for deriving the generalization bound of stable learning algorithms. In the existing literature, uniform stability [2] is the most widely used one but needs the strongest assumptions. A variety of stability notions have been proposed for different algorithms to widen the application range of stability. Kutin et al. [14] define strong and weak stability for the algorithms which are not uniformly stable. Locally elastic stability is proposed in (6 to capture the sensitivity of the loss function in the population sense but not in the worst sense. Lei et al. [15] provide notation of uniform stability for pairwise learning. Despite the fact that algorithmic stability has been successfully used in analyzing numerous learning algorithms, no work applies it to clustering algorithms. In this paper, show that the clustering algorithm we studied is uniformly stable.
Framework
In this section, we first give brief introduction to kernel k-means and multiple kernel clustering, then introduce the proposed approximation method.
4.1 Kernel m-mmaas and Multiple Kernel Clustering
Given a training set [x:}__ and feature map o(-), kernel clustering algorithm aims to minimize the following objective w.t. clustering centroids:
3

---

Σ n
W(C, P.)
min (x)((,) cx11 kE[K]
(I)
where C = {c* [ denotes the centroids of K clusters.
A clustering indicator matrix H E RRaX is defined as follows: if x; E CE. his = 1/11/////// Cc.. otherwise his = 0, where [Cx| denotes the number of samples belong to the k-th cluster.
Kernel k-means. If <--) is defined by some single kernel function k(.)), then Eq. can be rewritten as:
min Tr(K,) - Tr(K, HH
(2)
where K,, is the empirical kernel matrix computed by the kernel function & and dataset S, i.e., Ki = x,),
The discrete constraint of H in Eq. ( can be relaxed as: 1) has can take any real number; 2) the orthogonal constraint still holds, ie., H IK- Consequently, the solution (2. are the K eigenvectors corresponding to the K largest eigenvalues of kernel matrix K,, Therefore, H can be regarded as a new embedding for the training dataset, and standard k-means can then be performed on H for the final clustering. To avoid confusion, in this paper, kernel k-means refers to the relaxed version as mentioned above.
Multiple Kernel Clustering. In the multiple kernel setting, sample has m(m 2 2) feature mappings (x) p=1 associated with m base kernel functions { As the setting multiple multiple kernel clustering (MKC) usually lets each kernel multiply by weight Opp (p (ml)) These weights satisfy Σp=1 Op and Opp [0, 1]. Thus, the feature mapping of MKC can be represented as:
kernel learning [
[a di (x), am (m))))))) (x)]
Similar to Eq. 2. Eq. in multiple kernel setting can be reformed as:
min 1 Tr(Ka)
Tr (r.KHHH")
(3)
H 71
where Ka = Ep=1 K,P,p MKC aims to learn a set of optimal combination weights. Then, the relaxed kernel k k-means is performed on Ka for unified embedding H. Notice that K is the kernel matrix of the training dataset. To obtain the embedding of an out-of-sample point, we have to perform -igo-deccomoosition the kernel matrix constructed by the training dataset and the new coming data point. Obviously, this process is inefficient.
4.2 The Proposed Approximation Method
In our approach, we do not approximate the kernel matrix but the eigen functions of the integral operator associated with the kernel function. First, we give brief analysis of the spectrum of the integral operator. We start from the risk function of sample and the expected risk, which are respectively defined as:
1(x, C) = min [1x(x) call",
E [[x(,, C)]
min [|x(x) Cx ddx
(4)
kE[K]
kE(K)
Similar to Eq.
2) we reform the risk function of MKC for any two samples y E X' as follows:
K
1(x, y, H) = kixx x)
hi (x. (xxx))xxxxx))
(5)
where k.(-.)) Ep= (..)) denotes the linear combination of base kernel functions, and H {xx(x)) denotes the clustering indicator functions which are defined as:
h4 (x) = { 1/ 1/v V/VSech SxEc, dx, x E Ck.
(6)
x $ Ck.

---

Algorithm 1 MKC-AE
Require: Out-of-sample example x; kernel weights p=1 clustering indicator matrix Ha and 1K the largest K cigenvalues {k= learned by some MKC on some training set; m kernel functions {kp p= cluster number K.
1: for = 1: do
2: For sample compute the k-th element of the embedding vector by Eq.
3: end for
Ensure: A K-dimension approximation embedding for x.
The expected clustering risk is then defined as:
R(H,P)= = /f 1(x,y, H Hdxxdy.
The following proposition shows that the expected risk of the proposed pairwise learning framework equals that of the original kernel clustering algorithm with the same cluster centroids. Thus, we can learn the excess risk bound with the proposed framework defined by Eq.(5) instead of the original one defined by (.. Proposition 4.1.
The expected clustering risk defined by Eq. 7 can reformed as:
R(H,P)= - / min [lx(x) - -cal/dxx = xxxxx))xx - Σ E/flaaa)kaa KE[R]
Obviously, (hx(x) are all unit functions and orthogonal to each other in the squared integrable space (X, p). Similar Eq. 2). the discrete constraint of these functions can also be relaxed, and the relaxed version is investigated in this paper. Denote that H = [x)) are the K eigen functions corresponding to the K largest eigenvalues of the integral operator T (2 L² (2(
(Lxf)x)= - ( k)
Obviously, H* is the minimizer of the expected clustering risk defined by Eq. However, H* cannot be obtained because the data distribution is unknown. Rosasco et al. (7 analyze the spectral properties of the integral operator defined by kernel function and its empirical version, i.e., kernel matrix. Inspired by their method, aim to construct clustering indicator functions from the empirical kernel matrix that can approximate H Suppose that the combination weights learned by some MKC algorithms on S are ppp11111 the embedding of Ka is H and the largest K eigenvalues (A kK We construct K functions follows:
Tx
Σ hikka
Σ (x)kp(x,x.))
where is ranges in [K] and hik,or the ik-th element of H Then, the approximation embedding for an out-of-sample point x can be constructed by a K-dimmnssional vector [7,,, (x)..... hx (x)]. The listed in Algorithm T1 and we term this algorithm multiple kernel clustering with approximation embedding (MKC-AE). This method has two noticeable ad advantages: 1) It can be applied to all MKC algorithmss based on embedding learning. 2) has theoretical generalization guarantee which will be studied in the following section.
above procedures
The application large-scale datasets. The proposed MKC-AE method can be adapted to perform MKC on large-scale datasets. Let us denote with Sy a large-scale dataset consisting of N samples. We first select samples landmarks and perform some MKC algorithm these landmarks. The remaining N - n samples can be regarded as "out-of-sample" examples, and the approximation embedding of these samples kernel matrix of some MKC algorithm on n landmarks is _K,,a- The matrix constructed by the K largest eigenvectors of 1 K,.a is denoted as H, RT*' and the corresponding eigenvalues matrix is D, k Assume that the partial kernel similarity constructed by N samples and
be obtained by the following process. Assume that the optimal
5

---

landmarks are (Pihe C RR i.e,, [Pilay = (x,, 1A E [m]. E [N], E [n]. According to (8) the approximation embedding of SN can be computed as:
m Σ
HN N
P
H.D
Notice that the main complexity of computing the approximation embedding is O (nmN + n nKN), which is caused by the summation of (Pr )r je and subsequent matrix multiplication. We then give an example to show how the proposed MKC-AE method can accelerate MKC. The time complexity of the MKC algorithm termed SimpleMKKM proposed in [20] is basically cubic with the number samples will cost O (N²) time, while the proposed MKC-AE method reduces the complexity to O (n² + nmN + =KKN), When n & N, the complexity is linear with the number of samples N. Thus, the proposed algorithm can enable MKC algorithms to be performed on large-scale datasets.
of training samples. Performing SimpleMKKM on
5 Theoretical Analysis
As the foundation for the theoretical analysis of multiple kernel clustering, we first analyze the stability of kernel k-mmaas (KKM) with our approximation method and then establish the generalization bound.
5.1 Stability and Generalization of Clustering on Single Kernel
Notice that there two intractable problems in the analysis for the stability of kernel clustering: 1) The clustering risk is concerned with centroids. However, the random initialization of clustering centroids makes the stability of kernel clustering hard to be analyzed: 2) To compute the clustering risk of a sample, it needs to find the nearest centroid. As a result, it is difficult to estimate the stability of the samples located at the boundary of two centroids. In this paper, since the proposed method adopts a pairwise risk function, the above two issues can be avoided. The detailed deduce process is follows.
In the single kernel setting, us denote with K,, the (normalized) empirical kernel matrix con- structed by the training set, and suppose that the K largest eigenvalues and the corresponding respectively. According to Eq. (8), the approxi- are given by:
cigenvectors of K,, are {A and mated clustering indicator functions H = {
hx(x)) 1 nd
Σ (iac((xxxx))
(9)
where his is the i-th component of hg. We aim bound the excess clustering risk as:
Es - R(H,,))
= -EsR(H,P) - EsR(H, (A.R(H,,)))BBAA P.) R(H" .P.
(10)
By the following proposition, we know the second item C < 0 in Eq. Proposition 5.1. In Eq. (TO) EgR(H,,P.) R(H*,P).
To give the upper bound of B, we first prove that the approximation method given by Eq. has uniform stability O K with respect to the risk function defined by Eq.
n
Theorem 5.2. Denote that two training datasets St have samples and differ by only one sample Suppose that the empirical kernel matrix has properties as: 1) there exist two constant c, C1 such that the K th eigenvalue is larger than 1/c; and 2) the gaps of first K eigenvalues larger than cy The approximation clustering indicator functions of S, S'
iee. wk E [K], d A Z ci 2. v
In fact, St is derived replacing the i-th sample of S.

---

obtained by Eq. ② are denoted as H and H', respectively. Then, for any x.y E R. there exists
constant Co 0 such that
CoK
[xx, H - [x, y, H - nVn
(11)
Remark 1. Suppose that the K-th eigenvalue of the integral operator associated with kernel function k(;-) is Xx- Then, by Proposition 10 in [27]. the K'thh eigenvalue of the corresponding empirical kernel matrix Ax converges to Ax when approaches infinity. When the kernel function is fixed, Xx can be considered as constant. Consider that a sequence of the K-th eigenvalue X with different sample number n. Let Σy then there exists positive integer N such that Vn 2 N,
A Ax }. then the assumption that λσ 1/c holds. Similarly, the assumption about eigen gap of the kernel matrix related to the eigen gap of make
IA -xxl < λς We let 1/c m
the integral operator corresponding the kernel function, thus appropriate kernel function the assumption hold. We conduct experiments to verify that the kernel functions we adopted satisfy The detailed experimental results are reported in Section B.4
the assumptions in Theorem 5.2
The following theorem 15 is about the generalization risk bound of the stable pairwise learning algorithm.
Theorem 5.3. [15] Assume that algorithm A has y-stability. If there exists a constant M > such that [[x y, A(S))] <, M holds for all x, y E X. Then for all 10e),e), the following inequality holds with probability 1 - 5:
(((AS))P.)) - R(A(S), P)I 4ry +e 12/2M
log (e/0)
+ 48 48 n. log
e.) 8
It is easy to check that the proposed risk function defined by Eq. can be upper bounded by some constant M. Then, combining Theorem 5.2 and Theorem 5.3 the proposed method has generalization risk bound B Ö
K
Vn As seen, the item Ö VT masters the whole
DVn
bound. Notice that this is the first bound for clustering deduced by algorithmic stability, and we can use learn the stability and generalization of multiple kernel clustering algorithms. In the future, we will improve this bound by further investigating the generalization theorem about the proposed pairwise learning framework.
5.2 Stability and Generalization of Clustering Multiple Kernel
To study the generalization ability of the proposed MKC-AE method on multiple kernel, we first reveal the relation between the stability of MKC-AE and the learned kernel weights.
Theorem 5.4. Denote that two training datasets S, S have n samples and differ by only one sample. Assume that for any kernel weights a, the empirical kernel matrix 1 Ka satisfies the same properties in Theorem 5.2 Iflla a011,0 17, there exists constant co such that
ComK n
(xx,y, Ha) y, Ha.)l
1
nyn
holds.
Remark 2. Theorem 5.4 shows that if the kernel weights of an MKC algorithm are stable, then its approximation method proposed in Algorithm I has uniform stability. Specifically, if r) Theorem 5.4 can be bounded by O (1/ it can be checked that the risk function has the stability in order of
(1z2-+11) (1-++))K In this regard, for a tighter risk bound, the kernel weights of MKC algorithms should n//n
be more stable. This can be design principle for MKC algorithms.
As an instantiation, we use the above theoretical results to analyze simple multiple kernel k-means (SimpleMKKM)) (20), which is oftte-of-theaar art MKC algorithm without any Syyeer-prramteet We first give brief introduction and then derive the generalization bound of SimpleMKKM with the proposed approximation method.
In the task of unsupervised learning, finding the optimal hyper-parameter an open question. Sim- plcMKKM is proposed hypee-parameteer-fee MKC algorithm and achieves desirable clustering
7

---

performance. The variants of SimpleMKKM 19 22 further boost the clustering performance and widen its upplication. Specifically, SimpleMKKM aims solve the following kemee alignment- based optimization problem:
min F(a); aEA
(12)
where F(a) = maxH Tr (K HHH S.L. = IK. and = fa E R R
- Op
1, Op 2 0, Vp E [ml). F(ax) in Eq. (2) is proven differentiable, and can be optimized by a reduced gradient algorithm [26]. One can refer Section in the appendix for a detailed optimization procedure.
The following theorem indicates that the learned kernel weights of SimpleMKKM are stable with the input samples.
Theorem 5.5. Assume that for any kernel weights a, the empirical kernel matrix K satisfies the same properties in Theorem Denote that the kernel weights obtained by performing SimpleMKKM on S, are respectively o. B. and the number of iterations is T. If in each iteration, the index of the largest element of is the same as B, then there exists constant co 2 1 such that
Tod
|| -llo S
Vn"
holds.
By Theorem 5.4 and Theorem 5.5 have the following corollary. We know that SimpleMKKM with the proposed method has uniform stability, thus the generalization bound can be established.
Corollary 5.6. Assume that for any kernel weights a,, and the empirical kernel matrix 1 K satisfies the same properties in Theorem 5.2 Then, there exists constant co such that
co(m + 1)K
[xx,y, Ho) -(x,,, Ha 5
n/n
holds.
the appendix, SimpleMKKM always converges within several iterations, and thus 7' can be regarded as a constant. Above all, according to Theorem 5.3 we know that the excess risk of SimpleMKKM with the approximation method can be
Remark 3. From the empirical results of Section B.3
bounded by O [m+1)K
Our bound is tighter than the existing results O ((/)) proposed in 20 As far as we know, this is the first time to study the generalization ability of MKC with stability,
nyn vn
and the provided bound is the tightest among existing results of MKC algorithms.
6 Experiments
Besides the theoretical analysis, we further validate the effectiveness of the proposed method ex- perimentally. To illustrate that the proposed method can handle out-of-sample problems properly. we first apply the proposed method to SimpleMKKM [20 and compare the clustering accuracy and efficiency of the proposed method and the original SimpleMKKM 20 To evaluate the scalability of our method, we again apply it to SimpleMKKM and compare it against several state-of saate-of-the-art efficient MKC algorithms on four large-scale datasets. The analysis of convergence is reported in Section B.3 of the appendix.
6.1 The Comparison with SimpleMKKM
We follow the settings in SimpleMKKM 20 and conduct experiments on 5 benchmark datasets, including Flo17, Flo102, DIGIT, Cal102 and Reuters to evaluate the effectiveness of the proposed algorithm over the -f--plee problem. The details of the above datasets are listed in Section B.J of the appendix. We first uniformly select samples at random from the original dataset, and the remaining - samples are regarded as out-of-sample points. We perform SimpleMKKM on the n samples for the related parameters and compute the approximated embedding by (8. We record the clustering performance the approximated embedding. For comparison, the results of SimpleMKKM on all N samples are also recorded. In our experiments, is ranged in [K, 200, 300, ... ,1000],
8

---

where K is the cluster number. To avoid the influence of randomness, we run the experiments 20 times with the same setting. All experiments are performed on a desktop with Intel(R) Core(TM)-i7-7820X CPU and 64G RAM.
We record the clustering performance of the proposed method (denoted proposed) and Sim- PlcMKKM (denoted as original) in terms of accuracy (ACC), normalized mutual information (NMI) purity, and execution time Table I The best performance of the proposed method and the corre- sponding running time are reported among different landmarks. As observed in Table the proposed method is comparable with SimpleMKKM in terms of the clustering performance evaluation indexes. This verifies that the approximated embedding obtained by our method is as effective as the exact embedding. On the other hand, the processing time of the proposed method is much less than that of SimpleMKKM. We can also see that the proposed method achieves more evident acceleration effect with an increasing number of samples. For example, in Flo17, the proposed method works 2.35 times faster than SimpleMKKM, while in Reuters, the proposed method is around 238.5 times faster than SiMPleMKKM.
Table Experimental results of the proposed method in comparison with the original SimpleMKKM.
Flol7
Digit
CCV
Flo102
Reuters
Original
Proposed
Original
Proposed
Original
Proposed
Orginal
Proposed
Original
Proposed
ACC
59.60
60.26
90.50
91,40
22.04
21.26
42.07
41.92
45.82
45.09
NMI
57.55
58.77
83.62
84.38
18.21
17.95
58.46
58.39
27.76
26.
Purity
91.40
25.21
53.28
$2.67
Time
41.14
17,51
35.9
2,57
370.3
43.42
2026.
140.6
3713.1
15.58
We also stndy the clustering performance of the proposed method with different numbers of landmarks. Due to limited space, please refer to Section B.2 for details.
6.2 Experiments on Large-scale Datasets
As mentioned in Section the proposed method can enable MKC to applied to large-scale datasets. To verify the efficiency, we evaluate the performance of the proposed algorithm on 4 large-scale datasets, including NUSWIDE, AwA and MNIST and ViVideo. The sample numbers of these datasets are all larger than 30,000, and the maximal one is 101,499. The detailed information of these datasets reported in Section B.T of the appendix.
For comparison, we conduct experiments on several SOTA large-scale multi-view clustering algo- rithms, including (I) scalable and parameter-free multi-view graph clustering (SFMC) [T8] which is graph-based multi-view clustering algorithm with adaptively selected anchors; (2) binary multi-view clustering (BMVC) which encodes each graphical view into binary form for lower computational complexity; (3) large-scale multi-vies subspace clustering (LMVSC) [[3] which constructs matrix with selected anchors reduce the redundant computation of subspace clustering. For the comparison algorithms, we select the hest prreee-prrmeters by grid searching suggested in the comparison methods. For sufficient landmarks, we set the number of landmarks of the proposed method as 1000.
Table 2: Experimental results of different clustering methods large-scale scale datasets. N/A means the corresponding method is out of memory. (The best result in each row is in bold.)
Proposed+ SimpleMKKMM
Metric
ACC
14.02
15.24
NMI
3.97
12.84
11.84
14.02
NUSWIDE
Purity
15.87
24.43
15.52
26.33
Time
268.64
28.28
73.68
20.46
ACC
3,26
8.06
8.68
9.65
11.92
AwA
Purity
5.34
10.73
10.02
11.81
Time
ACC
N/A
45.99
98.97
99.09
NML
N/A
39.86
96.86 86.86
97.17
MNIST
Purity
99.09
Time
N/A
26.08
46.74
6.34
ACC
N/A
19.41
17.25
17.35
YtVidoo
NMI
NIA
15.80
14.08
15.24
Purity
NA
30.78
32.25
29.58
53.88

---

We can see from Table 2 that the proposed method outperforms all comparison algorithms in NUSWIDE, AwA and MNIST. For YrVideo data, it vast dataset, but our algorithm still works and achieves comparable performance. Moreover, the proposed method achieves the fastest processing speed among all comparison methods. Above all, can be verified that the proposed algorithm efficient and effective on large-scale datasets.
7 Conclusions and Future Work
In this paper. we propose simple yet effecttve approximation embedding method for multiple kernel clustering. It can be applied to accelerate the existing MKC algorithms to efficiently obtain the embedding of out-of-sample points, therefore is suitable for clustering large-scale datasets. We, for the first time, thcoretically study the stability of clustering algorithms and establish the generalization bound of the proposed method. We first give the learning bound of relaxed KKM with algorithmic stability which is then extended for the analysis of MKC. Finally, the experimental results verify the effectiveness and efficiency of the proposed method.
Although we give some theoretical results about the generalization of clustering algorithms by stability, some assumptions still limit the application range of theorems, 6-g., the assumptions about eigenvalues. In the future, we aim to 1) establish the stability and generalization bounds for a wider range of MKC algorithms based on milder assumptions; determine the optimal number of landmarks through theoretical analysis.
Acknowledgments and Disclosure of Funding
This work supported by the National Key R&D Program of China 2020AAA0107100 and the National Natural Science Foundation of China (project no. 61773392, 61872377, 61922088, 61976196, and 62006237).
References
[1] N. Aronszajn. Theory of reproducing kernels. In Transactions of the American Mathematical Society, page 337-404, 1950.
[2] Olivier Bousquet and André Elisseeff. Stability and generalization. In The Journal of Machine Learning Research (JMLR), pages 499-526, 2002.
[3] Radha Chitta, Rong Jin, and Anil K Jain. Efficient kernel clustering using random fourier features. In International Conference on Data Mining (ICDM), pages 161-170, 2012.
[4] Stéphan Clémeneccon. On u-processes and clustering performance. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
[5] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE conference computer vision and 2009.
pattern recognition (CVPR), pages
[6] Zhun Deng, Hangfeng He, and Weijie Su. Toward better generalization bounds with locally elastic stability. In International Conference on Machine Leurning (ICML), pages 2590-2600, 2021.
[7] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[8] Mehmet Gönen and Ethem Alpaydmn. Multiple kernel learning algorithms. In The Journal of Machine Learning Research (JMLR), pages 2211-2268, 2011.
[9] Mehmet Gönen and Adam A Margolin. Localized data fusion for kernel k-means clustering with application to cancer biology. In Advances in Neural Information Processing Systems (NeurIPS), pages 1305-1313, 2014.
[10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pages 770-778, 2016.
10

---

[11] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pages 4700-4708, 2017.
[12] Hsin-Chien Huang, Yung-Yu Yu Chuang, and Chu-Song Chen. Multiple kernel fuzzy clustering. In IEEE Transactions on Fuzzy Systems (TFS), pages 120-134, 2011.
[13] Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, and Zenglin Xu. Large- scale multi-view subspace clustering in linear time. In AAAI Conference on Artificial Intelligence (AAAI), pages 4412-44199 2020.
[14] Samuel Kutin and Partha Niyogi. weeoweeeeerywhere algorithmic stability and generalization error. In arXiv preprint arXiv:1301.0579 2012.
[15] Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[16] Yunwen Lei, Mingrui Liu, and Yiming Ying. Generalization guarantee of sgd for pairwise learning. In Advances in Neural Information Processing Systems (NeurIPS), page Preprint, 2021.
[17] Shaojie Li and Yong Liu. Sharper generalization bounds for clustering. In International Conference on Machine Learning (ICML), pages 6392-6402, 2021.
[18] Xuelong Li, Han Zhang, Rong Wang, and Feiping Nie. Multi-view clustering: A scalable and parameter-free free bipartite graph fusion method. In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), pages 1-1, 2020.
[19] Xinwang Liu. Incomplete multiple kernel alignment maximization for clustering. In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), pages 1-1, 2021.
[20] Xinwang Liu. Simplemkkm: Simple multiple kemel k-means. In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), pages 1-1, 2022.
[21] Xinwang Liu, Yong Dou, Jianping Yin, Lei Wang, and En Zhu. Multiple kernel k-means clustering with matrix-induced regularization. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 1888-1894, 2016.
[22] Xinwang Liu, Sihang Zhou, Li Liu, Chang Tang, Siwei Wang, Jiyuan Liu, and Yi Zhang. Localized simple multiple kernel k-means. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 9293-9301, 2021.
[23] Yanting Lu, Liantao Wang, Jianfeng Lu, Jingyu Yang, and Chunhua Shen. Multiple kernel clustering based on centered kernel aligmment. In Pattern Recognition, pages 3656-3664 2014.
[24] Boaz Nadler. Finite sample approximation results for principal component analysis: A matrix perturbation approach. In The Annals of Statistics, pages 2791-2817, 2008.
[25] Michael Natole, Yiming Ying, and Siwei Lyu. Stochastic proximal algorithms for auc maxi- mization. In International Conference on Machine Learning (ICML), pages 3710-3719, 2018. 88
[26] A. Rakotomamonjy, F. Bach, Canu, Grandvalet, al. Simplemkl. In Journal of Machine Learning Research (JMLR), pages 2491-2521, 2008.
[27] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. In Journal of Machine Learning Research (JMLR), page 905-934, 2010.
[28] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations (ICLR), 2015.
[29] Jiaxi Tang and Ke Wang. Ranking distillation: Learning compact ranking models with high performance for recommender system. In International Conference on Knowledge Discovery Data Mining (KDD), pages 2289-2298 2018

---

[30] Shusen Wang, Alex Gittens, and Michael W Mahoney. Scalable kernel k-means clustering with nyström approximation: relative-error bounds. In The Journal of Machine Learning Research (JMLR), pages 431-479, 2019.
[31] Din Yeung and Hong Chang. A kernel approach for semisupervised metric learning. In IEEE Transactions on Neural Networks (TNNLS), pages 141-149, 2007.
[32] Zheng Zhang. Li Liu, Fumin Shen, Heng Tao Shen, and Ling Shao. Binary multi-view clustering. In IEEE transactions patter analysis and machine intelligence (TPAMI), pages 1774-1782, 2018.
[33] Bin Zhao, James T Kwok, and Changshui Zhang. Multiple kernel clustering. In International Conference on Data Mining (ICDM), pages 638-649, 2009.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section for general technical conditions not given in statements of results.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are given in the supplementary material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "qpXTN14FIYe", "reviewer": "Reviewer_LK5c", "summary": "The paper studies the problem of clustering out-of-sample data over multiple kernel clustering dataset. The authors of the paper seek to solve the problem by learning the embedding functions with a novel approximation strategy by take advantage of the relation between empirical kernel matrix and integral operator of the kernel function. Then, the generalization ability of the method is studied with valuable depth from single kernel setting to multiple kernel setting. Finally, numerical experiments are conducted to verify the superiority of the proposed algorithm.", "questions": "In experiments, the clustering performance of SimpleMKKM with the proposed method on some datasets is superior to the original one. I think that the authors should give more discussions about this phenomenon.", "limitations": "None.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed method can greatly accelerate MKC on handling out-of-sample problem. Though the method is simple, it can reduce the time complexity from $\\mathcal{O}(N^3)$ to $\\mathcal{O}(N)$. Consequently, the method can enable MKC to be performed on large-scale dataset.\n2. The authors offer theoretical analysis about the proposed method. It is the first time the stability of clustering algorithm is analyzed. The paper is technically sound, and the proofs are strict.\n3. The paper establishes a connection between the stability of MKC algorithm and the output kernel weights, which enlightens a design principle for this type of algorithms.\nWeakness:\n1. Some other methods for large-scale implementation of kernel clustering algorithms should be referred, e.g., Nystr\\\"om [1] and random Fourier feature [2].\n\n2. The proposed clustering risk bound should be compared with other relevant works.\n\n[1] Cameron Musco and Christopher Musco. Recursive sampling for the Nystr\\\"om method. In NeurIPS 2017.\n\n[2] Radha Chitta, Rong Jin, and Anil K. Jain. Efficient Kernel Clustering Using Random Fourier Features. In ICDM 2012.\n\n3. Experiments are not sufficient. In Section 5.1, the authors provide theoretical analysis of clustering on single kernel. However, the paper lacks corresponding experiments.\n\n4. The codes of experiments are not available.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ViyP9R4pdxl", "reviewer": "Reviewer_YqyK", "summary": "The paper proposes a new method for efficient multiple kernel clustering (MKC) over out-of-sample data. This method has the potential to scale the existing MKC algorithms to handle large-scale datasets. Then, the generalization ability of the method is studied from the single kernel setting to the multiple kernel setting, which provides valuable insight of the algorithm. Finally, numerical experiments are conducted to verify the superiority of the proposed algorithm.", "questions": "Please check the Weakness box.", "limitations": "None.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Some strengths:\n1. This work studies the generalization ability of the clustering algorithm based on algorithmic stability, which is a significant and interesting research topic.  By selecting $n$ samples as landmarks, the approximation embedding of the remaining samples can be computed with $O(N)$ time complexity, where $N$ is the sample number. Thus, the method can make existing MKC scalable to large-scale datasets.\n2. The theoretical analysis of the paper is novel and sound. Theoretical analysis has proved that the proposed method has desirable generalization ability ($\\mathcal{O}((m+1)Kn^{-3/2}+n^{-1/2})$), which provides a tighter bound than the one ($\\mathcal{O}(mKn^{-1/2})$) provided in [1]. It guarantees the effectiveness of the proposed method. Moreover, the analysis can be scalable to multiple kernel clustering and the proofs are correct.\n3. The paper is easy to follow and well-written.\n\nSome weaknesses:\n1. The paper only discusses uniform sampling as the selected method of landmarks. Other sampling strategies (e.g., leverage score [2]) could be tried to further improve the performance of the algorithm.\n2. The authors haven’t analyzed the optimal number of landmarks. In the experiments, the number of landmarks is regarded as a hyper-parameter, which seems to require more effort to select the best one.\n3. The authors only provide the theoretical and empirical results about SimpleMKKM. Some classic MKC algorithms are not discussed.\n\n[1] Xinwang Liu, En Zhu, Jiyuan Liu, Timothy Hospedales, Yang Wang, and Meng Wang. Simplemkkm: Simple multiple kernel k-means. In arXiv preprint arXiv:2005.04975, 2020.\n\n[2] Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13:3441–3472, 2012.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0dlkQasAO3r", "reviewer": "Reviewer_Ymww", "summary": "The paper provides a general method that enables multiple kernel clustering algorithms to compute the embedding of out-of-sample points efficiently. Instead of re-computing the sample embedding of the unseen samples with the support of the whole data matrix, the authors directly obtain the embedding by constructing the embedding functions through approximating the eigen function of the integral operator defined by the optimal kernel function. With these functions, the embedding of the out-of-sample data can be easily and accurately calculated. Moreover, the upper bound of excess clustering risk is established based on the studying of stability of the proposed method. Experimental results demonstrate the effectiveness and efficiency of the proposed method.", "questions": "1. Why do the authors select SimpleMKKM as a baseline for the implementation of the proposed method? \n\n2. The proposed method for construction of the approximated indicator functions is inspired by [3]. However, the contribution over the mentioned method is not clearly described in the manuscript. More information should be given.\n\n[3] Rosasco L, Belkin M, De Vito E., On learning with integral operators. In JMLR, page 905–934, 2010.", "limitations": "The limitation of the proposed method is considered in the conclusions. The societal impact is not discussed, and this will not cause any potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The out-of-sample problem of MKC studied by this paper is important and challenging. The idea of enabling kernel clustering algorithms to obtain the embedding of out-of-sample data is novel and interesting. \n\n2. The conducted generalization study of clustering algorithms is an important theoretical contribution. \n(1) The paper for the first time establishes the excess risk bound of kernel k-means by the analysis of its algorithmic stability. \n(2)  The analysis is extended to multiple kernel setting. The proposed theoretical results enlighten a new way to study the generalization ability of multiple kernel clustering algorithms. \n\n3. The paper is well written with clear and rational motivation. It presents a novel way of scaling the method to large scale multiple kernel clustering scenario and a new perspective of generalization analysis of MKC. These are valuable for AI researchers in this field. \n\n\nWeakness\n\n1. In the paper, only SimpleMKKM is used as an example to verify the effectiveness of the out-of-sample method. As a consequence, the experimental support of the paper is relatively weak. It will be better if more state-of-the-art multiple kernel clustering algorithms, such as [1][2], can be analyzed.\n\n[1] Liu, X.; Dou, Y.; Yin, J.; Wang, L.; and Zhu, E. 2016. Multiple kernel k-means clustering with matrix-induced regularization. In AAAI, 1888–1894.\n\n[2] Gonen, M., and Margolin, A. A. 2014. Localized data fusion for kernel k-means clustering with application to cancer biology. In NIPS, 1305–1313.\n\n2. Some minor issues are as follows.\n\nI. In the proof of Proposition 4.1, $R(H)$ should be written as $R(H,P)$ as its definition in the main text.\n\nII. “Denote the k-th eigenvalue/vector pairs” in Line 483.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept