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

We appreciate the comments of Reviewer s6E6 and have responded to them individually.

Q1: Why are kernel weights crucial?

A2: 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.

Q2: Discuss the relationship between the clustering subspace and the weights in the remark of Theorem 3.3.

A2: 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.

Q3: Why does the chosen value of the number of anchor points $s$ not correspond to the conclusion obtained in the theorem?

A3: 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.

Q4: Compare the clustering performance between the proposed method and the original algorithm.

A4: 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.

Q5: Elaborate on the differences between the proposed method and the algorithm in [2].

A5: 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].

[2] Consistency of Multiple Kernel Clustering. ICML 2023.

Q6: Approximate different kernels with different anchor points.

A6: 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.

Q7: Evaluate the quality of anchor points theoretically.

A7: 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.

We greatly appreciate the feedback of Reviewer qRUV and have addressed each comment point by point, as detailed below.

Q1: The relationship between Algorithm 1 and spectral clustering.

A1: 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.

Q2: The relationship between Algorithm 2 and Nyström approximation?

A2: 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.

Different 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.

Different 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.

Q3: What is the intuition of Algorithm 2?

A3: 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.

Q4: Are the eigenvalues of Assumption 3.2 sorted?

A4: 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.

Q5: Theorem 3.3 and Theorem 4.1 require a large $s$, but Flower17 in Figure 1 only has 1000 points.

A5: 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.

Q6: Why is the approximation effect of $\frac{1}{\sqrt{ns}} \mathbf{P}$ is much better than $\frac{1}{s} \mathbf{W}$?

A6: 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.

Q7: Draw the graph of the relative eigenvalue approximation errors $\frac{|a-b|}{\lambda_j(\mathbf{K}/n)}$.

A7: 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.

Q8: What kernels were used? Are they all Gaussian kernels? How are their parameters set?

A8: 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.

We sincerely appreciate the work of Reviewer hzsf and respond to the review comments as follows.

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.

A1: 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.

In 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.

Q2: Is the construction time of SVD-CK significantly higher than random uniform sampling? Please include runtime comparisons.

A2: 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.