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

arXiv: https://arxiv.org/abs/2509.18826 · HTML: https://mlsanity.com/paper/2509.18826/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 58 references that are in the map.
- First posted on arXiv 23 Sep 2025.

## Builds on (most cited first, 14 of 14)

- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Subspace Clustering by Block Diagonal Representation](https://mlsanity.com/paper/1805.09243/) (2018)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [EAGLE: Eigen Aggregation Learning for Object-Centric Unsupervised Semantic Segmentation](https://mlsanity.com/paper/2403.01482/) (2024)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [Structured Graph Learning for Clustering and Semi-supervised Classification](https://mlsanity.com/paper/2008.13429/) (2020)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [A Comprehensive Survey on Spectral Clustering with Graph Structure Learning](https://mlsanity.com/paper/2501.13597/) (2025)
- [SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)](https://mlsanity.com/paper/1710.10604/) (2017)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Self-supervised Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/2103.01689/) (2021)

## Built on by (most cited first, 1 of 1)

- [Exact Rank-Space KL Projection for Shared-Marginal Low-Rank Factors: Application to Doubly Stochastic Clustering](https://mlsanity.com/paper/2608.08642/) (2026)

## Abstract (arXiv)

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 Low-Rank Doubly stochastic clustering (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 Block diagonal regularization into LoRD, expressed as the maximization of the Frobenius norm, we propose 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.