- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes randomized kernel compression as a preprocessing stage for SimpleMKKM. It constructs low-dimensional kernel projections using random matrices that are exploited either independently or through a shared spectral subspace. Then the existing SimpleMKKM optimization is applied to the reduced kernel matrices. The experiments indicate significant savings in computational time compared to SimpleMKKM along with some improvement in clustering quality.
Critical strengths
S1. The paper proposes a preprocessing approach to an important computational bottleneck in multiple-kernel clustering through a clear preprocessing framework that enables SimpleMKKM to operate on compact kernel matrices obtained through random projection and spectral analysis. The shared-subspace construction provides a principled way to combine spectral information across kernels, supported by reconstruction-error bounds and conditions for exact preservation of the leading clustering eigenspace.
S2. Experimental results indicate significant savings in computational time and improvement in clustering quality.
Critical weaknesses
W1. A clear intuitive explanation is needed why this method performs better than other kernel reduction approaches. The latter should be briefly explained in the paper in order to assess the novelty of the proposed methodology.
W2. The are some issues to be clarified and several concerns related to comparative experimental evaluation that are presented in the questions section below.
Questions for authors
Q1. The role of oversampling should be explained in Definition 1. What is the effect of s on the results? How the results are affected if s=0? Q2. Since the independent kernels method is inferior to shared kernels, I don’t see any reason to focus on independent kernels. The paper should propose only one approach. Q3. How does the randomness of projection matrix \Omega affect the results? Q4. It seems that the same \Omega is used for all kernels. What if separate random matrices are sampled for each kernel? Q5. I suppose that matrix Q used in eq. (13) – eq. (17) is Q* defined in proposition 1. Q6. The method is tailored to SimpleMKKM but since it constitutes an indepent preprocessing, it could followed by any other algorithm for multiple kernel clustering. This possibility could be investigated in the experiments. Q7. It would be interesting to see how different \gamma values are produced among the proposed method and standard SipleMKKM. Q8. There seems to be an analogous approach (COKE, ICML 2025) which is not included in the experimental comparison. Q9. A brief description of the compared approaches should be provided (e.g. is there a compared method that first applies Nystrom sampling and then clustering?). Q10. There are no details on the kernels considered for each dataset. For example two views are mentioned for Cora but the employed kernels are 16.
5 comments
Q6:Can the method be combined with other multiple kernel clustering algorithms?
A6:We thank the reviewer for the suggestion. Randomized kernel compression has the potential to be extended, as an independent module, to other multiple kernel clustering methods. We chose SimpleMKKM because its main computational cost comes from the repeated kernel fusion and eigendecomposition during kernel weight optimization, which directly demonstrates the computational benefit of the compact kernel representation. We conducted a simple transfer experiment on MKKM, and the results are as follows:
| Dataset | Method | ACC (%) | NMI (%) | Purity (%) | F-score (%) | Algorithm Time (s) |
|---|---|---|---|---|---|---|
| Reuters1200 | MKKM | 37.98 ± 3.94 | 21.01 ± 2.84 | 42.43 ± 3.24 | 29.70 ± 2.05 | 2.681 |
| Reuters1200 | MKKM-Sha | 38.04 ± 3.01 | 21.09 ± 3.27 | 41.20 ± 2.98 | 30.31 ± 1.21 | 0.943 |
| Reuters1200 | MKKM-Ind | 48.82 ± 0.21 | 32.41 ± 0.20 | 53.03 ± 0.30 | 37.73 ± 0.19 | 0.189 |
| 100Leaves | MKKM | 47.13 ± 2.64 | 72.45 ± 1.52 | 49.24 ± 2.64 | 35.89 ± 2.63 | 3.800 |
| 100Leaves | MKKM-Sha | 72.15 ± 2.91 | 88.70 ± 1.32 | 74.96 ± 2.93 | 66.30 ± 3.54 | 7.355 |
| 100Leaves | MKKM-Ind | 69.92 ± 1.40 | 85.47 ± 0.53 | 72.86 ± 1.12 | 62.28 ± 1.31 | 0.674 |
| HW-2Views | MKKM | 72.75 ± 6.56 | 71.38 ± 4.37 | 75.27 ± 5.88 | 65.70 ± 6.26 | 2.873 |
| HW-2Views | MKKM-Sha | 89.48 ± 6.32 | 85.16 ± 2.89 | 90.70 ± 4.63 | 84.94 ± 4.87 | 0.943 |
| HW-2Views | MKKM-Ind | 70.15 ± 0.30 | 63.78 ± 0.30 | 72.91 ± 0.38 | 60.24 ± 0.34 | 0.097 |
| Cora | MKKM | 20.13 ± 1.85 | 0.55 ± 0.15 | 30.28 ± 0.10 | 19.29 ± 1.87 | 6.936 |
| Cora | MKKM-Sha | 22.52 ± 2.70 | 3.38 ± 1.85 | 31.23 ± 1.51 | 20.77 ± 1.48 | 3.251 |
| Cora | MKKM-Ind | 21.21 ± 0.09 | 4.38 ± 0.07 | 34.27 ± 0.03 | 18.28 ± 0.03 | 0.328 |
| Scene15 | MKKM | 38.47 ± 1.26 | 39.02 ± 0.58 | 43.01 ± 0.83 | 28.19 ± 0.68 | 38.036 |
| Scene15 | MKKM-Sha | 42.37 ± 1.24 | 42.39 ± 0.51 | 47.05 ± 1.15 | 31.04 ± 1.05 | 6.027 |
| Scene15 | MKKM-Ind | 41.90 ± 0.65 | 37.44 ± 0.59 | 44.86 ± 0.66 | 29.30 ± 0.47 | 1.171 |
| CCV | MKKM | 15.63 ± 0.44 | 10.70 ± 0.25 | 19.57 ± 0.34 | 10.11 ± 0.19 | 22.575 |
| CCV | MKKM-Sha | 15.77 ± 0.33 | 12.95 ± 0.38 | 21.24 ± 0.39 | 10.41 ± 0.17 | 6.138 |
| CCV | MKKM-Ind | 19.31 ± 0.47 | 15.27 ± 0.41 | 23.48 ± 0.53 | 11.64 ± 0.22 | 0.447 |
| Hdigit | MKKM | 74.47 ± 7.33 | 72.45 ± 4.90 | 76.70 ± 5.84 | 67.22 ± 7.07 | 98.480 |
| Hdigit | MKKM-Sha | 89.98 ± 6.43 | 84.78 ± 3.03 | 91.22 ± 4.51 | 85.38 ± 5.14 | 5.393 |
| Hdigit | MKKM-Ind | 69.82 ± 0.07 | 62.40 ± 0.06 | 72.24 ± 0.05 | 59.31 ± 0.07 | 3.223 |
| ALOI100 | MKKM | 50.78 ± 2.95 | 71.51 ± 2.61 | 52.32 ± 3.14 | 43.25 ± 3.71 | 463.359 |
| ALOI100 | MKKM-Sha | 66.03 ± 2.37 | 82.81 ± 1.07 | 69.13 ± 2.48 | 60.49 ± 2.48 | 223.779 |
| ALOI100 | MKKM-Ind | 56.12 ± 1.57 | 73.64 ± 0.45 | 58.34 ± 1.24 | 46.43 ± 1.02 | 17.474 |
The results demonstrate that our method is effective and can be seamlessly integrated into other multiple kernel clustering algorithms in a plug-and-play manner.
A7:How do the learned weights γ differ from those of standard SimpleMKKM?
Q7:We additionally compared the kernel weights learned by the proposed method with those learned by standard SimpleMKKM, using the L1 distance, L2 distance, L$_\infty$ distance, and cosine similarity. The overall values are as follows:
| Dataset | Method | L1 | L2 | L∞ | Relative L2 | cos |
|---|---|---|---|---|---|---|
| 100Leaves | SMKKM-Sha | 0.024570 | 0.008330 | 0.005206 | 2.88% | 0.999586 |
| 100Leaves | SMKKM-Ind | 0.019812 | 0.006798 | 0.003451 | 2.35% | 0.999725 |
| ALOI-100 | SMKKM-Sha | 0.024223 | 0.007325 | 0.003188 | 2.92% | 0.999573 |
| ALOI-100 | SMKKM-Ind | 0.022579 | 0.006503 | 0.002835 | 2.59% | 0.999664 |
| CCV | SMKKM-Sha | 0.145568 | 0.050666 | 0.020911 | 17.46% | 0.985121 |
| CCV | SMKKM-Ind | 0.034299 | 0.012587 | 0.006763 | 4.34% | 0.999069 |
| Cora | SMKKM-Sha | 0.684331 | 0.261683 | 0.192866 | 68.97% | 0.724180 |
| Cora | SMKKM-Ind | 0.127951 | 0.047156 | 0.031289 | 12.43% | 0.993778 |
| HW_2Views | SMKKM-Sha | 0.028352 | 0.011853 | 0.008343 | 3.33% | 0.999451 |
| HW_2Views | SMKKM-Ind | 0.021498 | 0.008159 | 0.004458 | 2.29% | 0.999740 |
| Hdigit | SMKKM-Sha | 0.017356 | 0.007176 | 0.005055 | 2.01% | 0.999799 |
| Hdigit | SMKKM-Ind | 0.024435 | 0.009353 | 0.005000 | 2.62% | 0.999659 |
| Reuters-1200 | SMKKM-Sha | 0.203329 | 0.054385 | 0.020619 | 23.39% | 0.972317 |
| Reuters-1200 | SMKKM-Ind | 0.022058 | 0.005986 | 0.002265 | 2.57% | 0.999695 |
| Scene-15 | SMKKM-Sha | 0.145857 | 0.046726 | 0.021478 | 15.93% | 0.987948 |
| Scene-15 | SMKKM-Ind | 0.026427 | 0.009270 | 0.004483 | 3.16% | 0.999505 |
Q8:Why is COKE (ICML 2025) not compared?
A8:We thank the reviewer for pointing out this related work. The two methods differ in how the core representation is constructed. COKE first randomly selects anchor points, builds a sample-anchor kernel matrix, and uses its singular values and right singular vectors to form a core kernel. In contrast, our method obtains the spectral subspace of each kernel via Gaussian random sampling, and then explicitly aggregates cross-kernel spectral information to construct a unified shared basis Q. We have added the comparison experiments as follows. The performance results are shown below:
| Datasets | MKKM | RMKKM | LMKKM | LMTC | CMKC | SMKKM | COKE | SMKKM-Ind | SMKKM-Sha |
|---|---|---|---|---|---|---|---|---|---|
| Reuters | 37.98 ± 3.94 | 39.69 ± 3.06 | 50.27 ± 1.00 | 50.13 ± 0.06 | 48.17 ± 0.00 | 50.65 ± 0.95 | 43.76 ± 1.62 | 49.20 ± 1.60 | 49.40 ± 1.18 |
| 100Leaves | 47.13 ± 2.64 | 60.94 ± 2.28 | 82.69 ± 2.23 | 68.64 ± 1.54 | 82.30 ± 1.98 | 82.66 ± 1.56 | 81.99 ± 2.11 | 81.86 ± 1.39 | 84.50 ± 1.10 |
| HW-2view | 72.75 ± 6.56 | 81.01 ± 6.60 | 76.06 ± 0.56 | 89.92 ± 0.21 | 68.60 ± 0.42 | 73.47 ± 1.46 | 74.63 ± 0.58 | 69.99 ± 0.52 | 91.86 ± 0.07 |
| Cora | 20.13 ± 1.85 | 18.89 ± 0.66 | 24.37 ± 0.16 | 41.96 ± 1.22 | 32.77 ± 0.16 | 39.33 ± 0.41 | 35.98 ± 0.63 | 34.47 ± 0.83 | 49.21 ± 0.17 |
| Scene15 | 38.47 ± 1.26 | 39.88 ± 1.10 | 40.37 ± 1.31 | 39.50 ± 0.93 | 39.05 ± 0.76 | 40.07 ± 1.21 | 41.58 ± 1.22 | 39.59 ± 0.96 | 49.00 ± 0.66 |
| CCV | 15.63 ± 0.44 | 15.83 ± 0.57 | 19.90 ± 0.68 | 22.96 ± 0.61 | 21.44 ± 0.84 | 22.04 ± 0.74 | 21.40 ± 0.49 | 21.96 ± 0.54 | 27.38 ± 0.56 |
| Hdigit | 74.47 ± 7.33 | 78.48 ± 4.92 | 72.31 ± 1.15 | 78.55 ± 2.75 | 72.48 ± 1.23 | 71.34 ± 0.12 | 72.96 ± 0.09 | 69.54 ± 0.05 | 92.11 ± 0.01 |
| ALOI100 | 50.78 ± 2.95 | 64.75 ± 1.74 | 75.46 ± 1.26 | 67.32 ± 1.84 | 74.90 ± 1.99 | 73.67 ± 1.58 | 73.58 ± 1.66 | 74.56 ± 1.29 | 77.69 ± 1.42 |
The running time results are shown below.
| Datasets | MKKM | RMKKM | LMKKM | LMTC | CMKC | SMKKM | COKE | SMKKM-Ind | SMKKM-Sha |
|---|---|---|---|---|---|---|---|---|---|
| Reuters | 2.681 | 2.724 | 6.955 | 19.061 | 10.629 | 46.286 | 9.665 | 0.178 | 0.286 |
| 100Leaves | 3.800 | 10.061 | 8.322 | 18.598 | 6.148 | 31.184 | 4.371 | 0.751 | 0.894 |
| HW-2view | 2.873 | 6.723 | 8.558 | 1.379 | 2.417 | 22.353 | 1.916 | 0.193 | 0.252 |
| Cora | 6.936 | 13.735 | 31.140 | 25.753 | 27.011 | 273.499 | 12.922 | 0.584 | 0.891 |
| Scene15 | 38.036 | 44.002 | 72.689 | 4.644 | 8.897 | 212.908 | 5.178 | 1.247 | 1.749 |
| CCV | 22.575 | 88.545 | 142.709 | 8.329 | 2.148 | 115.494 | 1.879 | 1.244 | 0.943 |
| Hdigit | 98.480 | 147.822 | 430.698 | 8.936 | 12.462 | 611.855 | 9.392 | 4.301 | 5.156 |
| ALOI100 | 463.359 | 495.077 | 694.397 | 82.126 | 31.871 | 1581.531 | 21.127 | 13.699 | 16.557 |
Q9:Can you briefly describe the compared methods (e.g., Nyström sampling followed by clustering)?
A9:We thank the reviewer for the suggestion. We briefly describe the compared methods below.
MKKM: Fuses multiple base kernels through a weighted combination and alternately updates the kernel weights and the cluster assignment, so that the combined kernel adapts to the clustering task. It is the basic multiple kernel clustering method.
RMKKM: Uses an -norm loss to reduce the influence of noise and outliers, and learns the kernel weights and clustering result jointly, with an emphasis on robustness.
LMKKM: Learns a different kernel combination for each sample, so that kernel fusion adapts to local characteristics of the data rather than applying one global set of weights to all samples.
LMTC: Expresses pairwise sample similarities through implicit linear kernels and integrates multi-view information via tensor modeling. Its optimization algorithm has linear complexity, which improves scalability.
CMKC: Analyzes the consistency between kernel weights learned on a sampled subset and those learned on the full data. Its large-scale version first learns the weights on the subset and then applies a Nyström extension to obtain the clustering representation for all samples.
SMKKM: Adopts a min-max optimization framework over the kernel weights and the spectral representation, evaluating the objective through the leading eigen-subspace of the fused kernel and updating the weights accordingly.
Among the compared methods, CMKC is the large-scale multiple kernel clustering algorithm that incorporates the Nyström method.
Q10:Which kernels are used for each dataset?
A10:Except for CCV, which comes with precomputed kernel data, we generate the kernels for every other dataset by producing four kernels per view: one linear kernel and three RBF kernels with different bandwidths. The Cora entry in the paper was a typo. The original data has four views, so 16 kernels are actually used.
We sincerely thank the reviewer for the valuable comments. We will respond to each of the reviewer’s comments point by point.
A1:About the oversampling parameter s.
Q1:In Definition 1, r is the target compression dimension, and r+s sets the width of the initial sample. The oversampling parameter s lets the algorithm first search a subspace larger than the target and then pick out the r directions it needs. This captures the dominant spectral information more fully and makes the randomized approximation more reliable. For a fixed r, increasing s adds to the cost of sampling and orthogonalization but leaves the dimension of the final core matrix unchanged. When s=0, random sampling may miss important spectral directions.
Q2:Why keep the independent-kernel variant if it is inferior to the shared-kernel one?
A2 :We thank the reviewer for the suggestion. Shared-subspace compression is the main method of this paper. Independent compression is a baseline that compresses each kernel separately, which lets us measure what the shared representation gains. In our experiments, shared compression generally gives better clustering performance, while independent compression runs faster on seven of the eight datasets, which reflects a trade-off between clustering quality and computational efficiency. In the revised manuscript, we will organize the method description and experimental analysis around shared-subspace compression and reduce the main-text coverage of independent compression.
Q3:How does the randomness of Ω affect the results?
A3:The random matrix Ω determines the initial sampled subspace, so different random realizations may yield different compressed representations. However, when the sampling dimension is sufficient and the dominant spectral structure of the kernel matrix is well captured, the subspaces obtained from different random matrices generally preserve similar principal spectral information.
Q4: What if each kernel uses its own random matrix instead of a shared Ω?
A4:Using independently sampled Gaussian matrices Ωp is also feasible. Each kernel can first obtain its own sampled subspace, and these subspaces can then be aggregated to construct a common basis Q. Compared with a shared Ω, independent sampling introduces kernel-specific approximation errors, which may change the correlations between sampling errors across kernels and consequently affect the directions selected for the shared basis. In contrast, using a common Ω provides a consistent sampling scheme across kernels, facilitating cross-kernel spectral information aggregation. Therefore, we adopt a shared Ω to maintain consistency in constructing the common subspace.
Q5:Is Q in Eqs. (13)–(17) the same as Q* in Proposition 1?
A5:We thank the reviewer for pointing this out. Yes, the Q used in the subsequent shared-compression formulation is the consensus subspace solution Q⋆ given in Proposition 1. To simplify notation, we drop the superscript ⋆ in the derivations that follow, and we will add a note stating this in the main text.