Bilevel Certified Multiple Kernel Clustering

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.