acceptodds
Under review as a conference paper at ICLR 2027

Efficient and Effective Multiple Kernel Clustering via Randomized Kernel Compression

Abstract

Multiple kernel clustering (MKC) has attracted widespread attention in recent years. Its core advantage lies in its ability to effectively capture the complex nonlinear and complementary structures of data by adaptively combining multiple kernel functions. Although various MKC methods have achieved significant success, they generally rely on the storage and spectral decomposition of multiple kernel matrices. This computational bottleneck limits the practical applicability of these methods when handling large-scale datasets. To address this, we propose a scalable multiple-kernel clustering framework based on symmetric randomized compression. Specifically, by compressing each base kernel into a low-dimensional core space, we retain its dominant spectral information while substantially reducing the cost of subsequent kernel fusion and spectral optimization. Furthermore, we construct a shared subspace to capture spectral structures consistently supported across multiple kernels, enabling kernel fusion and weight learning in a common representation space. Theoretically, we establish a reconstruction-error bound for each compressed base kernel and analyze how the shared subspace captures cross-kernel consensus structures. Experimental results on eight multi-view benchmark datasets show that the proposed method achieves significant improvements in clustering performance and computational efficiency, and exhibits notable scalability advantages in large-scale data scenarios.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Multi-view clustering, Multiple kernel clustering, Clustering

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_H8CzOpenReview ↗
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

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, rr is the target compression dimension, and r+sr+s sets the width of the initial sample. The oversampling parameter ss lets the algorithm first search a subspace larger than the target and then pick out the rr directions it needs. This captures the dominant spectral information more fully and makes the randomized approximation more reliable. For a fixed rr, increasing ss adds to the cost of sampling and orthogonalization but leaves the dimension of the final core matrix unchanged. When s=0s=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\Omega_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 Ω\Omega, 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 Ω\Omega provides a consistent sampling scheme across kernels, facilitating cross-kernel spectral information aggregation. Therefore, we adopt a shared Ω\Omega 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 QQ used in the subsequent shared-compression formulation is the consensus subspace solution Q⋆Q^\star given in Proposition 1. To simplify notation, we drop the superscript ⋆\star in the derivations that follow, and we will add a note stating this in the main text.

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:

DatasetMethodACC (%)NMI (%)Purity (%)F-score (%)Algorithm Time (s)
Reuters1200MKKM37.98 ± 3.9421.01 ± 2.8442.43 ± 3.2429.70 ± 2.052.681
Reuters1200MKKM-Sha38.04 ± 3.0121.09 ± 3.2741.20 ± 2.9830.31 ± 1.210.943
Reuters1200MKKM-Ind48.82 ± 0.2132.41 ± 0.2053.03 ± 0.3037.73 ± 0.190.189
100LeavesMKKM47.13 ± 2.6472.45 ± 1.5249.24 ± 2.6435.89 ± 2.633.800
100LeavesMKKM-Sha72.15 ± 2.9188.70 ± 1.3274.96 ± 2.9366.30 ± 3.547.355
100LeavesMKKM-Ind69.92 ± 1.4085.47 ± 0.5372.86 ± 1.1262.28 ± 1.310.674
HW-2ViewsMKKM72.75 ± 6.5671.38 ± 4.3775.27 ± 5.8865.70 ± 6.262.873
HW-2ViewsMKKM-Sha89.48 ± 6.3285.16 ± 2.8990.70 ± 4.6384.94 ± 4.870.943
HW-2ViewsMKKM-Ind70.15 ± 0.3063.78 ± 0.3072.91 ± 0.3860.24 ± 0.340.097
CoraMKKM20.13 ± 1.850.55 ± 0.1530.28 ± 0.1019.29 ± 1.876.936
CoraMKKM-Sha22.52 ± 2.703.38 ± 1.8531.23 ± 1.5120.77 ± 1.483.251
CoraMKKM-Ind21.21 ± 0.094.38 ± 0.0734.27 ± 0.0318.28 ± 0.030.328
Scene15MKKM38.47 ± 1.2639.02 ± 0.5843.01 ± 0.8328.19 ± 0.6838.036
Scene15MKKM-Sha42.37 ± 1.2442.39 ± 0.5147.05 ± 1.1531.04 ± 1.056.027
Scene15MKKM-Ind41.90 ± 0.6537.44 ± 0.5944.86 ± 0.6629.30 ± 0.471.171
CCVMKKM15.63 ± 0.4410.70 ± 0.2519.57 ± 0.3410.11 ± 0.1922.575
CCVMKKM-Sha15.77 ± 0.3312.95 ± 0.3821.24 ± 0.3910.41 ± 0.176.138
CCVMKKM-Ind19.31 ± 0.4715.27 ± 0.4123.48 ± 0.5311.64 ± 0.220.447
HdigitMKKM74.47 ± 7.3372.45 ± 4.9076.70 ± 5.8467.22 ± 7.0798.480
HdigitMKKM-Sha89.98 ± 6.4384.78 ± 3.0391.22 ± 4.5185.38 ± 5.145.393
HdigitMKKM-Ind69.82 ± 0.0762.40 ± 0.0672.24 ± 0.0559.31 ± 0.073.223
ALOI100MKKM50.78 ± 2.9571.51 ± 2.6152.32 ± 3.1443.25 ± 3.71463.359
ALOI100MKKM-Sha66.03 ± 2.3782.81 ± 1.0769.13 ± 2.4860.49 ± 2.48223.779
ALOI100MKKM-Ind56.12 ± 1.5773.64 ± 0.4558.34 ± 1.2446.43 ± 1.0217.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 γ\boldsymbol{\gamma} 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:

DatasetMethodL1L2L∞Relative L2cos
100LeavesSMKKM-Sha0.0245700.0083300.0052062.88%0.999586
100LeavesSMKKM-Ind0.0198120.0067980.0034512.35%0.999725
ALOI-100SMKKM-Sha0.0242230.0073250.0031882.92%0.999573
ALOI-100SMKKM-Ind0.0225790.0065030.0028352.59%0.999664
CCVSMKKM-Sha0.1455680.0506660.02091117.46%0.985121
CCVSMKKM-Ind0.0342990.0125870.0067634.34%0.999069
CoraSMKKM-Sha0.6843310.2616830.19286668.97%0.724180
CoraSMKKM-Ind0.1279510.0471560.03128912.43%0.993778
HW_2ViewsSMKKM-Sha0.0283520.0118530.0083433.33%0.999451
HW_2ViewsSMKKM-Ind0.0214980.0081590.0044582.29%0.999740
HdigitSMKKM-Sha0.0173560.0071760.0050552.01%0.999799
HdigitSMKKM-Ind0.0244350.0093530.0050002.62%0.999659
Reuters-1200SMKKM-Sha0.2033290.0543850.02061923.39%0.972317
Reuters-1200SMKKM-Ind0.0220580.0059860.0022652.57%0.999695
Scene-15SMKKM-Sha0.1458570.0467260.02147815.93%0.987948
Scene-15SMKKM-Ind0.0264270.0092700.0044833.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:

DatasetsMKKMRMKKMLMKKMLMTCCMKCSMKKMCOKESMKKM-IndSMKKM-Sha
Reuters37.98 ± 3.9439.69 ± 3.0650.27 ± 1.0050.13 ± 0.0648.17 ± 0.0050.65 ± 0.9543.76 ± 1.6249.20 ± 1.6049.40 ± 1.18
100Leaves47.13 ± 2.6460.94 ± 2.2882.69 ± 2.2368.64 ± 1.5482.30 ± 1.9882.66 ± 1.5681.99 ± 2.1181.86 ± 1.3984.50 ± 1.10
HW-2view72.75 ± 6.5681.01 ± 6.6076.06 ± 0.5689.92 ± 0.2168.60 ± 0.4273.47 ± 1.4674.63 ± 0.5869.99 ± 0.5291.86 ± 0.07
Cora20.13 ± 1.8518.89 ± 0.6624.37 ± 0.1641.96 ± 1.2232.77 ± 0.1639.33 ± 0.4135.98 ± 0.6334.47 ± 0.8349.21 ± 0.17
Scene1538.47 ± 1.2639.88 ± 1.1040.37 ± 1.3139.50 ± 0.9339.05 ± 0.7640.07 ± 1.2141.58 ± 1.2239.59 ± 0.9649.00 ± 0.66
CCV15.63 ± 0.4415.83 ± 0.5719.90 ± 0.6822.96 ± 0.6121.44 ± 0.8422.04 ± 0.7421.40 ± 0.4921.96 ± 0.5427.38 ± 0.56
Hdigit74.47 ± 7.3378.48 ± 4.9272.31 ± 1.1578.55 ± 2.7572.48 ± 1.2371.34 ± 0.1272.96 ± 0.0969.54 ± 0.0592.11 ± 0.01
ALOI10050.78 ± 2.9564.75 ± 1.7475.46 ± 1.2667.32 ± 1.8474.90 ± 1.9973.67 ± 1.5873.58 ± 1.6674.56 ± 1.2977.69 ± 1.42

The running time results are shown below.

DatasetsMKKMRMKKMLMKKMLMTCCMKCSMKKMCOKESMKKM-IndSMKKM-Sha
Reuters2.6812.7246.95519.06110.62946.2869.6650.1780.286
100Leaves3.80010.0618.32218.5986.14831.1844.3710.7510.894
HW-2view2.8736.7238.5581.3792.41722.3531.9160.1930.252
Cora6.93613.73531.14025.75327.011273.49912.9220.5840.891
Scene1538.03644.00272.6894.6448.897212.9085.1781.2471.749
CCV22.57588.545142.7098.3292.148115.4941.8791.2440.943
Hdigit98.480147.822430.6988.93612.462611.8559.3924.3015.156
ALOI100463.359495.077694.39782.12631.8711581.53121.12713.69916.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 ℓ2,1\ell_{2,1}-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.

Reviewer_vwHYOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes an efficient multiple kernel clustering framework based on randomized kernel compression to address the high computational cost of existing multiple kernel k-means methods. Building upon SimpleMKKM, the authors introduce two compression strategies: an independent compression scheme that constructs a separate low-dimensional basis for each kernel matrix, and a shared compression scheme that learns a common basis to represent multiple kernels in a unified low-dimensional space. By performing kernel fusion and optimization on the compressed representations, the proposed methods aim to substantially reduce computational complexity while preserving clustering performance. Experiments on eight benchmark datasets demonstrate considerable speedups over SimpleMKKM, with the shared compression scheme generally achieving competitive or superior clustering accuracy compared with the evaluated baselines.

Critical strengths
  1. Substantial computational efficiency improvements. The paper addresses an important computational bottleneck in multiple kernel clustering by transferring kernel fusion and spectral optimization into a compact low-dimensional space. The reported geometric-mean speedups of 140.52× and 112.68× over SimpleMKKM for the independent and shared compression schemes, respectively, are impressive. These results demonstrate the potential practical value of randomized kernel compression for accelerating multiple kernel clustering.

  2. Effective shared-subspace representation with strong empirical performance. The shared compression strategy provides a unified representation space for multiple kernels, allowing their spectral information to be integrated consistently. The experimental results are encouraging: SMKKM-Sha achieves the highest clustering accuracy on seven of the eight evaluated datasets, with particularly notable improvements on several benchmarks. The paper also provides theoretical analysis of kernel approximation errors and the shared subspace construction, offering additional support for the proposed framework.

Critical weaknesses

Although the paper investigates the sensitivity to compression rank, a more comprehensive evaluation of the trade-off between clustering accuracy, computational cost, and compression rank is needed. In particular, comparing the two proposed compression schemes across different ranks in terms of ACC, runtime, and peak memory usage would help determine whether the substantial acceleration can be consistently achieved without sacrificing clustering quality, and clarify the practical advantages of the shared-subspace design.

Questions for authors

End-to-end scalability. Although the reported computational speedups are impressive, the proposed methods still involve operations on the original kernel matrices. Could the authors provide a more comprehensive evaluation of end-to-end scalability, including kernel construction time, total runtime, and peak memory consumption as the dataset size increases? In particular, comparisons with existing scalable kernel clustering methods on larger datasets would help clarify the practical scalability advantages of the proposed framework.

1 comment

We sincerely thank the reviewer for the valuable comments. We will respond to each of the reviewer’s comments point by point.

W1: Please evaluate the trade-off among accuracy, runtime, and peak memory across different compression ranks for both schemes.

QW1: We thank the reviewer for the suggestion. The paper currently analyzes how the compression rank affects ACC in Figure 2 and in Figure 5 of the appendix. We will also report the corresponding running time and memory cost. In response to this question, we will add comparison experiments across different compression ranks in the revised manuscript, recording ACC, running time, and peak memory usage for both SMKKM-Ind and SMKKM-Sha. We will also discuss how the compression rank affects computational cost, so as to make clear the trade-offs between clustering performance, computational efficiency, and memory use for the two compression strategies, and to give guidance on choosing the rank in practice. e conducted experiments on the ALOI-100 dataset at six different compression ranks:

RankMethodACC (%)Algorithm Time (s)Peak Memory (GB)Additional Memory (GB)
105SMKKM-Sha77.69 ± 1.4215.4316.781.92
105SMKKM-Ind74.56 ± 1.299.5916.821.88
200SMKKM-Sha77.45 ± 1.4422.4017.062.21
200SMKKM-Ind74.18 ± 1.0615.2216.911.97
300SMKKM-Sha76.98 ± 1.3534.9518.213.35
300SMKKM-Ind74.96 ± 1.4721.8717.072.13
400SMKKM-Sha75.66 ± 1.2252.5219.574.71
400SMKKM-Ind75.19 ± 1.7831.9317.332.39
500SMKKM-Sha74.99 ± 1.2875.0421.186.32
500SMKKM-Ind75.19 ± 1.5041.1117.432.49
600SMKKM-Sha75.52 ± 1.61104.0923.078.21
600SMKKM-Ind74.86 ± 1.5548.4817.732.79

Peak Working Set: The maximum memory reached by the MATLAB process while running the method.

Additional Memory: The peak increase in memory usage relative to the initial state before the method is run.

A1: Please provide an end-to-end scalability evaluation (kernel construction, total runtime, peak memory) on larger datasets, with comparisons to existing scalable kernel clustering methods.

Q1: We thank the reviewer for the suggestion. In the paper, Figure 4 already examines how the running time of the proposed method changes as the number of samples is gradually increased. In all our experiments, timing starts after the kernel matrices have been precomputed, so the construction time of the original kernel matrices is not included. We have further added a comparison with COKE (ICML 2025), a recent scalable multiple kernel clustering method; please refer to our response to Q8 of Reviewer H8Cz. Our method still achieves competitive or better clustering performance with higher efficiency.

Reviewer_6PJtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents an efficient way of performing multiple kernel clustering. Specifically, it modifies the SimpleMKKM framework to achieve speed-ups of over x100 times via the compression of each base kernel into a lower dimensional space. By doing this while preserving the dominant spectral information they succeed in achieving a great speed-up and competitive performance across 8 datasets. The authors also provide theoretical reconstruction-error bounds for the compressed kernels and two different variants of their method, with a shared-subspace compression variant that ends up with the greatest accuracy.

Critical strengths
  • The paper is successful in its objective of improving the efficiency of the base method while preserving clustering performance.

  • The paper looks mathematically sound. Implementation details, algorithms, time complexity analysis are provided and clarify both the implementation, and the possible efficiency gains.

Critical weaknesses
  • The related work is weak. SimpleMKKM is a relevant work in the field and it must have inspired relevant works to the one presented in the paper. In this same line, competitors are not explained in detail in the appendix, and we get no explanation on how this method is superior over them.
Questions for authors
  • Under my understanding of the paper, the presented methods should achieve the speedup we observe, but at an ACC cost (a speed vs performance trade-off). Why is that not the case, since SMKKM-Sha is the best performing one by much?

  • Do the authors have any table/results on the tradeoff with r between speed and performance?

  • I would appreciate a deeper explanation of why the shared method performs so well. Could the authors also provide some intuition, showing in which settings the independent variant would be preferable?

  • I would ask the authors to release code with the paper.

3 comments

We sincerely thank the reviewer for the valuable comments. We will respond to each of the reviewer’s comments point by point.

W1: Related work is weak: SimpleMKKM-inspired works and the competitors are not explained in detail, and it is unclear why the proposed method is superior.

AW1: We thank the reviewer for pointing out that the related work is insufficiently discussed. In the revised version, we will expand the Related Work section to further introduce scalable multiple kernel clustering methods based on approximation strategies such as Nyström sampling, and to supplement the development of research related to SimpleMKKM.

The comparison methods are briefly described 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 ℓ2,1\ell_{2,1}-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.

We will further explain the advantages of our method over existing approaches and the reasons behind them. Rather than approximating the entire kernel matrix by selecting a small number of representative samples, our method extracts the dominant spectral information of multiple kernels to construct a shared subspace, thereby moving the subsequent kernel fusion and weight optimization into a low-dimensional space. The shared subspace not only preserves the principal spectral information of each kernel, but also integrates the common structure and complementary information across different kernels. As a result, our method substantially improves efficiency while achieving high clustering performance.

Q1. The method should give a speedup at some accuracy cost. Why is that not the case, given that SMKKM-Sha performs best by a large margin?

A1: We thank the reviewer for raising this question. Low-rank compression does discard part of the information, but this does not necessarily lead to a drop in clustering accuracy. For spectral clustering, what matters is preserving the dominant eigen-subspace of the fused kernel matrix, rather than fully recovering all the information in the matrix. In this paper, we extract the dominant spectral information of each base kernel through random projection and power iteration. What is discarded is mainly the spectral components with small energy, so the compressed low-dimensional representation still retains the information closely related to the clustering structure. The performance gain of SMKKM-Sha mainly comes from the integration of multi-kernel consensus information. The ablation study in the appendix shows that clustering performance keeps improving as the number of kernels participating in the construction of the shared subspace increases, which indicates that integrating consensus information plays an important role in the improvement.

Q2. Are there tables/results on the speed-performance trade-off with respect to r?

A2: We thank the reviewer for the suggestion. Figure 2 currently shows how the compression rank rr affects clustering accuracy. To give a fuller picture of how the rank affects both efficiency and clustering performance, we add running-time results for different values of rr in the revised manuscript and compare them with the corresponding ACC results.

Experimental Results on ALOI-100

RankMethodACC (%)Algorithm Time (s)
105SMKKM-Sha77.69 ± 1.4215.43
105SMKKM-Ind74.56 ± 1.299.59
200SMKKM-Sha77.45 ± 1.4422.40
200SMKKM-Ind74.18 ± 1.0615.22
300SMKKM-Sha76.98 ± 1.3534.95
300SMKKM-Ind74.96 ± 1.4721.87
400SMKKM-Sha75.66 ± 1.2252.52
400SMKKM-Ind75.19 ± 1.7831.93
500SMKKM-Sha74.99 ± 1.2875.04
500SMKKM-Ind75.19 ± 1.5041.11
600SMKKM-Sha75.52 ± 1.61104.09
600SMKKM-Ind74.86 ± 1.5548.48

The results show that ACC remains relatively stable across compression ranks, with a small rr achieving high clustering accuracy at a lower computational cost.

Q3. Why does the shared method perform so well, and in which settings would the independent variant be preferable?

A3: We thank the reviewer for the suggestion. We believe SMKKM-Sha performs better mainly because it makes fuller use of the shared structure and complementary information across base kernels. Different kernels describe different characteristics of the data, but they usually carry some common clustering information. By combining the sampled subspaces of multiple kernels into a shared subspace, this step distills the main structure of the kernels and, at the same time, greatly reduces their dimension. This speeds up the algorithm while giving better clustering performance.

For SMKKM-Ind, independent compression may be the better choice when the base kernels differ strongly in spectral structure and the spectral information unique to each kernel is valuable. It preserves the dominant spectral structure of each kernel separately and is not limited by the dimension of a shared subspace.

Q4. Will the code be released with the paper?

A4: We will release the code upon acceptance of the paper.

The authors have properly addressed my questions. I think the proposed additions will make for a solid paper. I will keep my score.

Reviewer_RnjoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper speeds up weight optimization in multi-kernel clustering using random low-rank compression and a shared spectral subspace. They run experiments on 8 datasets and report solid clustering results with clear speedups.

Critical strengths
  1. Moving the spectral optimization into a low-dimensional space clearly cuts down the repeated computation cost.
  2. The experiments cover 8 datasets and show clear gains in both performance and efficiency.
Critical weaknesses

Different kernels' compressed matrices sit in different coordinate systems, so just adding them together could shift the original objective and the optimal weights. The method mostly leans on existing randomized SVD and spectral projection, and the theory doesn't really back up guarantees on clustering results or kernel weights.

Questions for authors
  1. Each kernel uses its own basis, so why can the compressed matrices just be added together? How do you know the resulting weights still match the original problem?
  2. The shared subspace basically comes from SVD of a concatenated matrix. Compared with existing randomized SVD and consensus-subspace methods, what's actually new theoretically?
  3. The paper only gives a single-kernel reconstruction bound—so how do you guarantee the compressed clustering results and kernel weights match the original SimpleMKKM?
  4. Independent compression doesn't help on most datasets. Is the gain from shared compression a real new mechanism, or just from putting everything in one coordinate system?
  5. Why not compare efficiency and accuracy with more modern low-rank MKC methods, like CoKE or Nyström-based ones?
  6. The method still needs the full kernel matrix and is quadratic. Do the reported speedups include the cost of building the original kernel matrices?
2 comments

We sincerely thank the reviewer for the valuable comments. We will respond to each of the reviewer’s comments point by point.

Q1. Why can the compressed matrices, each in its own basis, be added together, and how do you know the resulting weights still match the original problem?

A1: We thank the reviewer for raising this question. SMKKM-Ind is a low-dimensional surrogate problem, not an equivalent form of the original one. As we note in the manuscript, compressing each kernel separately leads to inconsistent coordinates across kernels. Its purpose is to trade a small approximation cost for a speedup, and this limitation is what motivated us to propose shared compression (SMKKM-Sha), which resolves the issue.

In SMKKM-Sha, all kernels are projected onto the same orthonormal basis QQ, so kernel fusion and projection commute. Learning the weights in this space amounts to solving the original SimpleMKKM problem with the spectral embedding restricted to the column space of QQ. The only difference from the original problem is how well QQ covers the dominant spectral information of the kernels: the better the coverage, the closer the two problems are. When the eigen-subspace of the original optimal solution lies within the column space of QQ, the two solutions are close. Otherwise, the result is an approximate solution of the original problem.

Q2. The shared subspace essentially comes from the SVD of a concatenated matrix; what is theoretically new compared with randomized SVD and consensus-subspace methods?

A2: We thank the reviewer for the attention. The main contribution of this paper is combining randomized spectral compression with multiple kernel clustering, and using a shared subspace to balance computational efficiency and clustering performance. Specifically, we first sample each kernel randomly, then combine the sampled subspaces of all kernels into a shared subspace that captures their common and complementary information. Kernel fusion and weight optimization are then done on the small projected core matrix, which avoids repeated large-scale spectral decompositions. When a small compression rank rr is enough to keep the main spectral information, our method maintains clustering performance while greatly reducing computational cost. In addition, we analyze the reconstruction error of randomized kernel compression and give an error bound for compressing the base kernel matrices.

Q3. Only a single-kernel reconstruction bound is given; how do you guarantee that the compressed clustering results and kernel weights match the original SimpleMKKM?

A3: Our aim is not to guarantee that the optimization results before and after compression are identical in every case. Instead, we aim to cut the cost of repeated spectral optimization while keeping as much of the main spectral information as possible. We use the reconstruction error bound for the base kernels to describe the information lost in compression, and Proposition 3 gives the conditions under which the shared subspace recovers the dominant clustering subspace without loss. We therefore focus on how well the compressed method preserves the main clustering structure. In our experiments, the kernel weights learned by our method are close to those of standard SimpleMKKM under the L1, L2, and L$_\infty$ distances and cosine similarity, while its clustering performance is comparable to or better than the standard method and its running time is much lower.

Q4. Independent compression does not help on most datasets; is the gain from shared compression a genuinely new mechanism, or just from putting everything in one coordinate system?

A4: To further examine the role of the shared subspace, we ran an ablation study in the appendix. We vary the number of kernels used to build the shared subspace QQ, and compare a single-kernel subspace, a two-kernel consensus subspace, and an all-kernel consensus subspace. In all settings, the same shared representation space is used, and the kernel preprocessing, random compression, weight optimization, and clustering evaluation stay unchanged. The results show that as more kernels are used to build the shared subspace, the average ACC rises from 38.91% to 52.15%, and then to 65.14%. This indicates that the gain from shared compression does not come merely from using a unified coordinate system. More importantly, by combining the spectral information of multiple kernels, the consensus subspace brings together the complementary structural information carried by different kernels.

Q5. Why not compare efficiency and accuracy with more modern low-rank MKC methods, such as COKE or Nyström-based ones?

A5: We thank the reviewer for this suggestion. In fact, our paper already includes CMKC (Liang et al., ICML 2023) in the experimental comparison, a method that uses Nyström approximation for large-scale multiple kernel clustering. We have also added the results of COKE (ICML 2025). Please refer to our response to Reviewer H8Cz for the experimental results.

Q6. The method still needs the full kernel matrices and is quadratic; do the reported speedups include the cost of building the original kernel matrices?

A6: The reported running times are measured starting from the precomputed kernel matrices and therefore do not include the kernel construction time. All compared methods follow the same timing protocol to ensure a fair comparison. Our method does require access to the full kernel matrices, but it involves only one-time operation that is quadratic in the number of samples N (the randomized projection of each kernel). The subsequent kernel fusion and weight optimization are carried out in the low-dimensional subspace. Therefore, despite this one-time O(N²) preprocessing step, the overall running time remains substantially lower than that of the compared methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.