acceptodds
Under review as a conference paper at ICLR 2027

Bilevel Certified Multiple Kernel Clustering

Abstract

Multiple kernel clustering (MKC) integrates heterogeneous data views through dynamic kernel weighting, yet its robustness is typically evaluated only against empirical attacks. Crucially, existing studies overlook weight re-optimization, discrete assignment stability, and numerical approximation errors. To address this, we propose Bilevel Certified MKC (BC-MKC). During training, BC-MKC employs a bilevel optimization framework: the lower level computes a self-consistent spectral response via a strongly convex fixed-subspace weight formulation, while the upper level optimizes a smooth proxy—targeting alignment, clustering margin, and eigengap—using guarded implicit differentiation. A trace-normalized Nyström bank is incorporated to stabilize the approximation geometry. For post-training evaluation, we introduce a fixed-core verifier that propagates admissible base-kernel perturbations through weight re-optimization, kernel fusion, and spectral projection. This verifier either rigorously certifies the full partition and selected co-assignments up to label permutation, or safely abstains. Theoretically, we formally bound fixed-point and eigensolver residuals against the certification margin, seamlessly accommodating uniform full-kernel approximation bounds when available. We prove that under established regularity, eigengap, and margin conditions, our reported certificate provides a sufficient guarantee for clustering invariance within specified kernel-perturbation sets.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Adversarial Certification, Partition Invariance, Weight Re-optimization, Implicit Differentiation

Reviews

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

This paper proposes BC-MKC, which combines a trace-normalized Nyström kernel library, projection sub-aggregation, self-consistent kernel weight optimization and post-training fixed-core authentication, trying to give assignment invariance in approximate multi-kernel clustering. Methods include bilevel implicit updates, guarded outer updates, and a verification process that propagates kernel perturbations and solver residuals to the sample-to-core distance margin. The experiment reports ACC/NMI/F1/ARI on 10 benchmarks and 22 MKC baselines, and provides ablation, parameter sensitivity, and certification coverage.

Critical strengths
  1. Propagating kernel perturbations, weight re-optimization, eigensolver residuals, and row-normalized decoding through to the assignment margin offers greater methodological value than merely reporting empirical clustering metrics.

  2. The combination of Nyström kernels, projector aggregation, self-consistent lower responses, and a post-training verifier forms an end-to-end pipeline that yields significant improvements in accuracy (ACC) across multiple datasets.

  3. Analyses of lower responses, upper objectives, consensus kernels, landmark/rank budgets, and parameter grids provide insight into the contributions of individual components.

Critical weaknesses
  1. The scope of certification is overly narrow, with a very low actual coverage rate. It is limited to "frozen approximate kernels" and "fixed decoding," while excluding considerations such as semantic correctness, parameter re-selection, feature variation, and new discretization schemes. As shown in Figure 6, the coverage is 0% when ε=10⁻³, and only approximately 20.4%/17.4% when ε=10⁻⁴. This means the core selling point—"certified"—applies to only a small fraction of samples. Furthermore, the paper relies on a "nominal partition," rendering the claims in the title and the stated contributions overly ambitious.

  2. The font size in the table appears to have been changed.

Questions for authors
  1. Clarify the definition of Δ(%) in Table 2 and explain why these values ​​differ from the improvement figures mentioned in the main text (e.g., 5.1% for P-Fold, 30.2% for CUB, 19.0% for Reuters, 17.8% for Scene15, and 26.5% for YTF10).

  2. Report the values ​​for χ\chi, γr\gamma_r, RPR_P, and the proportions of certified/partial/abstain samples for each dataset, as well as the ACC/NMI/ARI scores calculated exclusively on the certified subset. Furthermore, how do the results support the core claim of "certified clustering" when ε=10⁻³ and coverage=0%?

  3. Is the "certified" approach extensible to scenarios involving re-discretization, landmark re-selection, or perturbations of the original features? If not, why is "certified" highlighted as a primary contribution in the title and abstract?

  4. Do the baselines utilize the same landmark budget, retained rank, hyperparameter tuning budget, and computational environment as BC-MKC? Additionally, do the runtime figures in Figure 8 account for the certification phase and all preprocessing steps?

  5. How were the numerous hyperparameters and thresholds (e.g., QQ, ρ\rho, τ\tau, τa\tau_a, wa,…,whw_a,\ldots,w_h, μ\mu, α\alpha, σ\sigma, ϵj\epsilon_j, etc.) determined? Was ground truth information or a validation set used for hyperparameter tuning? Were the certification thresholds validated on independent data?

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

This paper proposes Bilevel Certified Multiple Kernel Clustering. The method constructs a trace-normalized Nyström kernel bank with a reliability-weighted subspace consensus kernel. Kernel weights are obtained through a self-consistent spectral response, while an outer objective learns a weight prior using alignment, assignment margins, eigengap, and additional regularization terms. After training, a separate verifier freezes the kernel construction, learned prior, and core-selection coefficients. It propagates kernel perturbations through weight re-optimization, spectral projection, row normalization, and nearest-core decoding to obtain sufficient conditions for assignment invariance. The theoretical analysis includes conditional uniqueness and differentiability of the lower response and a residual-aware assignment certificate.

Critical strengths

The paper goes beyond bounding a fixed kernel’s eigenspace perturbation: it incorporates weight re-optimization and carries the resulting projector error through row normalization and moving core representatives to assignment margins. This connects continuous spectral stability with the discrete clustering output. The explicit distinction between the training proxy and the certificate, together with the stated frozen-computation scope, makes the guarantee easier to interpret.

Critical weaknesses
  1. The limitations of existing research and the motivation are insufficiently analyzed. Although the paper identifies several challenges in multiple kernel clustering, its discussion of the closest existing methods remains too general. It does not sufficiently explain which specific limitations remain unresolved, why they are consequential, and how they motivate the proposed bilevel formulation and certification framework.

  2. The connection between the conditional theorem and an operationally valid numerical certificate is not fully established. The theoretical guarantees rely on regularity, spectral separation, and valid residual bounds. However, the paper does not sufficiently explain how the implemented verifier checks these conditions and converts numerically estimated quantities into bounds that justify the reported certificates.

Questions for authors
  1. What specific limitations of the closest existing MKC and spectral-stability methods motivate this work? Could you distinguish limitations in their guarantees from limitations in their optimization procedures or empirical performance?

  2. Why is the proposed bilevel formulation necessary to address these limitations? What does it provide beyond regularized kernel-weight optimization followed by post-training spectral perturbation analysis?

  3. How does the implemented verifier establish the regularity and spectral-separation conditions required by Assumptions 1–2 throughout the admissible perturbation region? Please distinguish conditions that are computationally verified from those that remain assumptions.

  4. How are the computed eigengap and solver residuals converted into valid bounds for Theorem 2? In particular, how is eigensolver error incorporated into the fixed-point residual, and how is the safety factor justified?

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

This work proposes a bilayer multi-kernel clustering method, which combines adaptive kernel weight optimization, Nyström approximation and clustering stability certification. In the experiment part, it was compared against 22 baseline methods on 10 datasets and reported competitive clustering performance with certification results.

Critical strengths

Combining kernel weight re-optimization with clustering stability certification is worth looking into. The experiments cover 10 datasets and 22 baselines, and the performance gains are clear.

Critical weaknesses

Strong regularization could make the lower-level re-optimization barely matter in practice, and the ablations don't really separate the effects of bilevel optimization, prior learning, and kernel construction. The theory also leans on strong spectral gap and contraction assumptions, and only guarantees assignments under a frozen setup. With bigger perturbations, certification coverage drops noticeably—so it's still unclear whether the robustness guarantees are meaningful in practice.

Questions for authors
  1. With μ=5×10⁵ and normalized kernel trace, lower-level weights barely move. So how much does bilevel re-optimization actually contribute?
  2. Compared with Davis–Kahan plus clustering margin certification, what does this paper add that's truly irreplaceable?
  3. How do you guarantee the spectral gap, contraction, and residual bounds hold across the whole perturbation range, not just at the nominal solution?
  4. Input data changes can shift the Nyström kernel, consensus kernel, and cluster centers. Why does freezing them still reflect the real algorithm's robustness?
  5. The upper-level objective targets margin and spectral gap, but does it actually improve certification radius or coverage? Any direct ablation on certification metrics?
  6. At a 10⁻³ perturbation budget, coverage hits zero. What real data change does the current radius correspond to, and where's the advantage over a simple certification baseline? I'm willing to raise my score if the authors can address the concerns above.
Reviewer_aS6VOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The manuscript addresses the issue of unstable clustering results in multi-core clustering due to core approximation errors, changes in core weights, and perturbations in spectral structure. Consequently, it proposes a framework that combines stable core construction, dual-layer weight optimization, and clustering result verification. Preliminary validations were conducted on multiple datasets.

Critical strengths

(1) The experiments are sufficient and the results are competitive. The author has conducted sufficient experiments to verify their ideas, and there are many comparison methods. (2) The theoretical analysis covers multiple error propagation links.

Critical weaknesses

(1) The practical value of clustering authentication has not been fully verified. Although the paper proposed a theoretical certification for the invariance of clustering allocation, the experiments did not fully illustrate the significance of the certification results in real scenarios. (2) The ablation experiments were not conducted on all datasets.

Questions for authors

(1) Is there a clear connection between the improvement of clustering performance and the authentication capability? (2) Why is a two-layer optimization necessary to achieve clustering authentication?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.