Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective

Wenlong Lyu, Yuheng Jia, Hui Liu, Junhui HouarXiv 2025 · DOI · arXiv

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:

  1. Spectral Clustering (SC): Relaxes non-negativity, requiring a secondary $k$-means step on eigenvectors.
  2. SymNMF: Relaxes the doubly stochastic constraint, losing probabilistic interpretability.
  3. 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.

Relationships between kernel k-means and various relaxations, including the proposed LoRD and B-LoRD models.

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.

Geometric representation of the constraint space reduction using the class probability parameter $\mu$.

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

Abstract

The well-known graph-based clustering methods, including spectral clustering, symmetric non-negative matrix factorization, and doubly stochastic normalization, can be viewed as relaxations of the kernel $k$-means approach. However, we posit that these methods excessively relax their inherent low-rank, nonnegative, doubly stochastic, and orthonormal constraints to ensure numerical feasibility, potentially limiting their clustering efficacy. In this paper, guided by our theoretical analyses, we propose \textbf{Lo}w-\textbf{R}ank \textbf{D}oubly stochastic clustering (\textbf{LoRD}), a model that only relaxes the orthonormal constraint to derive a probabilistic clustering results. Furthermore, we theoretically establish the equivalence between orthogonality and block diagonality under the doubly stochastic constraint. By integrating \textbf{B}lock diagonal regularization into LoRD, expressed as the maximization of the Frobenius norm, we propose \textbf{B-LoRD}, which further enhances the clustering performance. To ensure numerical solvability, we transform the non-convex doubly stochastic constraint into a linear convex constraint through the introduction of a class probability parameter. We further theoretically demonstrate the gradient Lipschitz continuity of our LoRD and B-LoRD enables the proposal of a globally convergent projected gradient descent algorithm for their optimization. Extensive experiments validate the effectiveness of our approaches. The code is publicly available at https://github.com/lwl-learning/LoRD.
BibTeX
@misc{lyu2025graph,
  author = {Wenlong Lyu and Yuheng Jia and Hui Liu and Junhui Hou},
  title = {{Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective}},
  year = {2025},
  eprint = {2509.18826},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.18826},
}
Figure