Constraint-Aligned Subspace Transformation for Scalable Kernel Metric Learning in Clustering
TL;DR
Constraint-Aligned Subspace Transformation (CAST), a novel framework that restricts metric adaptation to a low dimensional subspace strictly induced by pairwise constraints, is proposed, and an implicit update formulation that enables distance evaluation in O (r) time, effectively reducing memory complexity to O (nr).
Abstract
Kernel Distance Metric Learning (KDML) is a powerful tool for enhancing clustering performance by adapting the data geometry to correct structural mismatches. However, traditional global KDML methods suffer from severe scalability issues, often incurring O (n3) computational costs and O (n2) memory usage, where n is the sample size. Furthermore, these holistic deformations can lead to overfitting when supervision is sparse. To address these limitations, we propose Constraint-Aligned Subspace Transformation (CAST), a novel framework that restricts metric adaptation to a low dimensional subspace strictly induced by pairwise constraints. By orthonormalizing constraint directions, we reduce the learning problem from estimating a full kernel matrix to a rank-efficient Linear Program (LP). We further derive an implicit update formulation that enables distance evaluation in O (r) time, effectively reducing memory complexity to O (nr). Extensive experiments on diverse datasets demonstrate that CAST matches or exceeds state-of-the-art KDML competitors in downstream clustering tasks while dramatically reducing optimization time, delivering 33×-259× speedups over the fastest baseline in the weak-supervision (1%) regime, while still achieving 3×–20× speedups at 20% supervision.