Abstract
Clustering is a cornerstone of machine learning, with Kernel $k$-means serving as a theoretical gold standard. However, its NP-hard nature necessitates relaxations such as Spectral Clustering and Symmetric Non-negative Matrix Factorization (SymNMF). These traditional relaxations often sacrifice essential constraints, resulting in a "relaxation gap" that impacts interpretability and performance. This paper introduces LoRD (Low-Rank Doubly stochastic clustering) and B-LoRD (Block-diagonality regularized LoRD), which bridge this gap by maintaining low-rank and doubly stochastic constraints while relaxing only strict orthonormality. We demonstrate that these models achieve state-of-the-art accuracy across diverse datasets through a globally convergent algorithm.
Introduction: The Relaxation Gap
The fundamental challenge in graph-based clustering is solving the kernel $k$-means problem efficiently. To circumvent its NP-hardness, researchers typically employ one of three relaxations:
- Spectral Clustering (SC): Relaxes non-negativity, requiring a secondary $k$-means step on eigenvectors.
- SymNMF: Relaxes the doubly stochastic constraint, losing probabilistic interpretability.
- Doubly Stochastic Normalization (DSN): Relaxes the low-rank structure, leading to high computational costs ($O(n^3)$).
These methods are often "overly relaxed," discarding constraints that are vital for clear cluster assignments. The proposed work seeks a middle ground: a model that preserves non-negativity, low-rank structure, and double stochasticity while remaining computationally feasible.
Theoretical Framework
The authors map the landscape of these relaxations to situate their proposed models, LoRD and B-LoRD, within the existing literature.
LoRD: Low-Rank Doubly Stochastic Clustering
LoRD relaxes only the orthonormal constraint of kernel $k$-means. The core innovation is Theorem 1, which proves that the non-convex quadratic doubly stochastic constraint can be reduced to a linear convex constraint by introducing a class probability parameter, $\mu$. This reduction significantly simplifies the optimization landscape.
The Role of the $\mu$ Parameter
The vector $\mu$ represents the prior probability of each class, serving as a bridge between optimization and statistical prior knowledge.
B-LoRD: Block-Diagonality Regularization
B-LoRD extends LoRD by incorporating a regularization term that maximizes the Frobenius norm $\|V\|_F^2$. The authors theoretically establish that under doubly stochastic constraints, the orthogonality of the assignment matrix is equivalent to the block diagonality of the resulting similarity matrix. This allows B-LoRD to promote an ideal cluster structure where points relate primarily to others within the same cluster.
Optimization and Scalability
To solve these models, a Projected Gradient Descent algorithm was developed. By proving that the objective functions are gradient Lipschitz continuous, the authors ensure global convergence with an automatically determined step size. Furthermore, by exploiting the low-rank structure of the assignment matrix $V$, the per-iteration complexity is reduced from $O(n^3)$ to $O(n^2k)$, or $O(n \log(n)k)$ for sparse graphs, enabling scalability to large datasets.
Experimental Results
The models were rigorously tested on 12 datasets, including balanced sets (e.g., YaleB, COIL100) and imbalanced sets (e.g., MNIST, Yeast).
Key Findings
- State-of-the-Art Performance: B-LoRD achieved the highest accuracy in 11 out of 12 datasets, outperforming the next best method by an average of 0.053 in ACC.
- Robustness: The model demonstrated stability even when class priors were unknown, showing robustness to the choice of $\mu$.
- Objective-Accuracy Correlation: A high correlation ($R^2 > 0.9$) was observed between the objective function value and clustering accuracy, indicating that the mathematical optimization directly translates to better clustering.
Conclusion and Future Directions
While LoRD and B-LoRD significantly narrow the relaxation gap, they remain somewhat dependent on the class prior parameter $\mu$. Future research will focus on automated methods for estimating the optimal $\mu^*$ during the clustering process. Additionally, the authors plan to extend this framework to multi-view clustering and integrate it with deep learning architectures to further enhance its applicability to complex, high-dimensional data.
Summary updated