Efficient Anchor Graph Clustering Through Enhanced Within-Cluster Homogeneity

Anchor-based clustering methods have gained attention for their efficiency in subspace, multi-view, and ensemble clustering tasks. Most existing methods focus on using anchors to reduce computational complexity in the original data space. However, clustering directly on anchors, followed by label propagation to the original data, can significantly improve computational efficiency. In this paper, we propose an Efficient Anchor Graph Clustering (EAGC) method that maximizes within-cluster homogeneity among anchors. Inspired by the relaxation and discretization model in spectral clustering, we propose two corresponding models, namely EAGC-R and EAGC-D. EAGC-R first obtains relaxed spectral embedding of anchors and then the embedding is discretized by K-Means. EAGC-D directly solves the discrete anchor membership matrix by coordinate descent method. Once anchor clustering results are obtained, original data labels can be obtained through anchor label transmission. Extensive experiments conducted on both synthetic and real datasets illustrate the effectiveness of proposed methods.