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

2025-12-31 · Source: JMLR · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics, Mathematics & Computational Sciences · Depth: Expert, quick

Summary

Wenlong Lyu, Yuheng Jia, Hui Liu, and Junhui Hou introduce Low-Rank Doubly stochastic clustering (LoRD) and its enhanced variant, B-LoRD, as novel graph-based clustering methods. Published in 2026, these models address limitations in existing graph-based techniques, such as spectral clustering, which excessively relax constraints derived from kernel k-means. LoRD specifically relaxes only the orthonormal constraint to achieve probabilistic clustering results. B-LoRD further integrates block diagonal regularization, expressed as maximizing the Frobenius norm, to improve clustering performance, leveraging a theoretical equivalence between orthogonality and block diagonality under the doubly stochastic constraint. The authors ensure numerical solvability by transforming the non-convex doubly stochastic constraint into a linear convex one using a class probability parameter. A projected gradient algorithm, proven to have gradient Lipschitz continuity and a sublinear convergence-rate bound, ensures first-order stationarity. Extensive experiments confirm the effectiveness of LoRD and B-LoRD, with code available on GitHub.

Key takeaway

For Machine Learning Engineers developing graph-based clustering solutions, you should consider evaluating LoRD and B-LoRD. These models offer a theoretically grounded approach to enhance clustering efficacy by selectively relaxing kernel k-means constraints and integrating block diagonal regularization. Implementing these methods, particularly B-LoRD, could yield more robust and accurate probabilistic clustering results than traditional spectral clustering, especially if your current techniques suffer from over-relaxed constraints. You can explore the publicly available code to integrate these advancements into your projects.

Key insights

LoRD and B-LoRD improve graph-based clustering by selectively relaxing kernel k-means constraints and using block diagonal regularization.

Principles

• Excessive constraint relaxation limits clustering efficacy.
• Orthogonality is equivalent to block diagonality under doubly stochastic constraint.
• Block diagonal regularization enhances clustering performance.

Method

LoRD relaxes only the orthonormal constraint for probabilistic clustering. B-LoRD integrates block diagonal regularization by maximizing the Frobenius norm, solved via a projected gradient algorithm.

In practice

• Implement LoRD for probabilistic graph clustering.
• Apply B-LoRD for enhanced performance via regularization.
• Utilize the provided GitHub code for implementation.

Topics

• Graph Clustering
• Kernel k-Means
• LoRD Algorithm
• Block Diagonal Regularization
• Projected Gradient Algorithm
• Machine Learning Algorithms

Code references

• lwl-learning/LoRD

Best for: Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Unsupervised Feature Selection via Nonnegative Orthogonal Constrained Regularized Minimization — NOCRM offers a theoretically sound unsupervised feature selection method with convergence guarantees.
• Heat and Matérn Kernels on Matchings — A framework extends heat and Matérn kernels to matchings, using zonal polynomials for efficient evaluation.
• Spectral Clustering - Explained — Spectral clustering effectively separates non-linearly separable data by leveraging graph connectivity and Laplacian eigenvectors.
• Scalable Model-Based Clustering with Sequential Monte Carlo — A novel SMC algorithm improves scalability for online clustering by decomposing problems into independent subproblems.
• Smart Data Grouping: Organizing Networks Without Guesswork — A new differentiable structural information formulation enhances deep graph clustering via LSEnet.
• Structural interpretability in SVMs with truncated orthogonal polynomial kernels — ORCA provides exact, post-training interpretability for SVMs using truncated orthogonal polynomial kernels by decomposing their RKHS norm.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by JMLR.