{"ID":2867052,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.18826","arxiv_id":"2509.18826","title":"Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective","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.","short_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, doub...","url_abs":"https://arxiv.org/abs/2509.18826","url_pdf":"https://arxiv.org/pdf/2509.18826v1","authors":"[\"Wenlong Lyu\",\"Yuheng Jia\",\"Hui Liu\",\"Junhui Hou\"]","published":"2025-09-23T09:14:39Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false,"code_links":[{"ID":609433,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2867052,"paper_url":"https://arxiv.org/abs/2509.18826","paper_title":"Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective","repo_url":"https://github.com/lwl-learning/LoRD","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}