acceptodds
Desk rejected at ICLR 2027

Learning to Construct the Learning Space for Scalable Multiple Kernel Clustering

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Standard complete multiple kernel clustering (MKC) is infeasible for large-scale data, requiring \(O(n^2)\) storage and \(O(n^3)\) decomposition of \(V\) \(n \times n\) kernel matrices. Scalable MKC methods approximate kernel as (, ), reducing storage to and decomposition to . However, existing methods freeze , so as view weights update, the combined kernel diverges from the frozen approximation, degrading clustering performance. To address this limitation, we propose a Learning to Construct the Learning Space for Scalable Multiple Kernel Clustering (LCLS-SMKC) method, which is a space-plasticity method that jointly optimizes the space-shaping parameters and the consensus embedding. Specifically, multi-scale leverage scores select diverse landmarks to cover the kernel space, yielding a more accurate per-view approximation . Subsequently, A self-learning dual-mode switch modulates the kernel space to be adaptive to view disparity rather than frozen. For small disparity, an enlarged-disparity space is selected to retain cross-view diversity. For large disparity, a purified space suppresses noise via adaptive joint feature denoising, embedding alignment, and view consistency mining. Furthermore, the dimensionality variation coefficient is embedded into kernel-space parameters, and an error-driven feedback loop updates these space parameters to minimize approximation error to enable adaptive learning. Finally, theoretical analysis establishes guarantees on approximation error, Lyapunov stability, linear convergence, and generalization, while experiments on six diverse datasets confirm consistent superiority over state-of-the-art scalable MKC methods in performance.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
scalable clustering, Nystr\"om approximation, kernel space learning, space plasticity, adaptive landmark selection, graph diffusion, error-driven feedback, large-scale learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ZqQfOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes LCLS-SMKC for scalable multiple kernel clustering. It combines multi-scale landmark sampling, a dimensionality-dependent choice of kernel construction, feature diffusion and reweighting, and feedback-controlled consensus learning. The authors claim improved approximation, stability, convergence, and generalization guarantees. Experiments cover six datasets, comparisons with kernel and multi-view clustering methods, component ablations, and robustness to noise and outliers.

Critical strengths

(1) Improving the compatibility between low-rank kernel representations and consensus learning is a meaningful problem for scalable clustering.

(2) The method integrates several concrete, testable design choices, including sampling across kernel scales and feedback-controlled regularization.

(3) The evaluation covers six datasets, including 70,000 samples in MNIST, and includes component ablations, runtime comparisons, and noise/outlier experiments.

Critical weaknesses

(1) Theorem 1 is false under its stated assumptions. For K = I_n and s < n landmarks, every size-s subset gives the same squared Frobenius Nystrom error n-s. Thus, multi-scale sampling cannot strictly improve on uniform sampling by a positive amount. This directly contradicts the claimed universal improvement and undermines a central theoretical justification.

(2) The optimization does not clearly implement the claimed adaptation. Algorithm 1 constructs KH_v before the loop without subsequently updating it, and Eq. (20) measures embedding disagreement rather than kernel-approximation error. Moreover, the S_v update in Eq. (24) omits the diversity term in Eq. (23). The claimed kernel-space updates and convergence guarantees therefore need a consistent derivation.

(3) Some reported metrics contradict their definitions in Appendix A.3. Under these definitions, PUR cannot be lower than ACC when both metrics are computed from the same clustering assignments and averaged over the same runs. However, Table 7 reports ACC = 63.42 and PUR = 63.05 for LCLS-SMKC on MSRC-v6. This basic inconsistency raises serious concerns about the reliability of the reported experimental results.

Questions for authors

(1) How should Theorem 1 be revised to accommodate kernels such as K = I_n, where all landmark subsets of the same size have identical approximation error?

(2) Can Eqs. (24) and (27) be derived from Eq. (23), including its diversity and graph terms? Which kernel-space quantities actually change inside the optimization loop?

(3) Were ACC and PUR computed from identical cluster assignments and averaged over the same runs? How should the conflicting values in Table 7 be reconciled?

Reviewer_WpM6OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes LCLS-SMKC, a scalable multiple kernel clustering method that adaptively constructs the kernel learning space. The framework combines multi-scale leverage score sampling, a dual-mode modulation strategy, and error-driven feedback to update kernel-space parameters during optimization. The authors provide theoretical analyses and evaluate the method on six benchmark datasets.

Critical strengths
  1. The paper addresses a relevant problem in scalable multiple kernel clustering by considering how kernel approximations should adapt during optimization.
  2. The proposed framework incorporates several mechanisms for improving kernel approximation and consensus learning, supported by theoretical analysis.
  3. The experimental results show competitive clustering performance across the evaluated datasets.
Critical weaknesses
  1. The central motivation is not fully convincing. Although the paper shows increasing kernel approximation error during optimization, it remains unclear whether this error is the main cause of degraded clustering performance in existing methods.
  2. The framework involves several components, including multi-scale sampling, dual-mode switching, and feedback optimization. The necessity of these mechanisms and their individual contributions need stronger justification.
  3. The theoretical analysis is extensive, but its connection to the practical behavior of the complete framework is not sufficiently clear. In particular, the conditions under which the theoretical guarantees hold deserve further discussion.
Questions for authors
  1. Is there direct evidence that reducing kernel approximation error consistently leads to better clustering results?
  2. How sensitive is the dual-mode strategy to the dimensionality threshold, especially when views have similar dimensions but different distributions?
  3. What is the main technical distinction between the proposed space adaptation and existing adaptive kernel approximation methods?
1 comment

Thanks for the rebuttal. After reading the authors' reply, my concerns have been solved and I raise my score.

Reviewer_2LmBOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work presents LCLS-SMKC that adaptively builds a multi-kernel clustering space using multi-scale sampling, dual-mode kernel switching with a feedback mechanism. This work ran experiments on six datasets and also give theoretical guarantees on approximation error, convergence, and generalization.

Critical strengths
  1. Trying to get past the limits of fixed-kernel approximation is a worthwhile problem to tackle.
  2. The experiments cover a range of baselines and ablations, and the clustering gains are clear.
Critical weaknesses

The core novelty isn't clearly separated out. A fixed single-view Nyström factor doesn't mean the fused kernel is frozen. From my point of view, it's still unclear whether the method actually learns a new kernel space. The theory has real problems too. Eq. (31) in Appendix Theorem 1 doesn't hold in general, and the strict error-improvement guarantee isn't well supported.

Questions for authors
  1. If each view's kernel approximation is fixed, why does that mean the fused kernel can't change with the weights?
  2. I've question for the description of 'learning a kernel space', which kernel construction parameters actually get updated? And how is that really different from just fixing the Nyström factors and optimizing weights?
  3. How does Eq. (31) on page 14 of the appendix actually hold up? The Nyström approximation isn't an orthogonal projection, does that mess with Theorem 1?
  4. Why flip between Gaussian and linear kernels just based on view dimensionality? Is that really better than simply picking whichever kernel fits best?
  5. Does the complexity analysis count the kernel matrix inversion and building the full similarity graph? And how do you actually make it scale to large data? I'd be happy to improve my rating if the authors adequately address the concerns raised above.

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

Related papers

Discussion (0)

Sign in to comment.