Efficient Structure-Aware Discrete Clustering via Multi-Order Anchor Graphs

Anchor graph-based clustering has demonstrated strong potential for uncovering complex latent structures in large-scale scenarios. Nevertheless, existing approaches face two critical limitations: first, most fail to fully exploit the deep structural relationships among samples, resulting in graphs that inadequately capture the intrinsic data topology; second, the conventional two-stage paradigm that separates spectral embedding from label assignment introduces relaxation errors and redundant computations, degrading clustering performance and increasing computational overhead. To address these challenges, we propose an Efficient Structure-Aware Discrete Clustering via Multi-Order Anchor Graphs (ESADC). ESADC adaptively fuses multi-order anchor graphs to model complementary approximations of the underlying continuous manifold, while employing a single-stage, structure-aware framework that jointly learns spectral embeddings and discrete cluster labels, thereby enhancing both clustering effectiveness and computational efficiency. Furthermore, a fast coordinate descent-based optimization algorithm is developed for the discrete ESADC model to accelerate convergence. Extensive experiments on both regular and large-scale real-world datasets demonstrate that ESADC consistently outperforms state-of-the-art methods, highlighting its efficiency and strong structure-aware capability.