High-Order Anchor Graph-Based Clustering for Efficient Structured Proximity Matrix Learning

Structured proximity matrix learning, a central topic in clustering research, aims to construct a proximity matrix with explicit clustering structures from an initial first-order proximity matrix. Due to the complexity of data structures, the original first-order proximity matrix often lacks essential must-links compared to the ground-truth proximity matrix. Moreover, traditional structured proximity matrix learning methods typically suffer from high computational complexity. To address these issues, we propose High-Order Anchor Graph-based Clustering (HAGC). The introduced high-order anchor graph effectively compensates for missing must-links while significantly reducing the computational burden. Furthermore, we exploit the consistency of high-order proximity information by fusing multiple high-order anchor graphs into a unified structured joint anchor graph. Specifically, we develop an efficient fusion framework that adaptively assigns weights to different orders of high-order anchor graph matrices. Finally, we obtain a consensus structured anchor proximity matrix under a Laplacian rank constraint. Extensive experiments validate the superiority and effectiveness of the proposed method. Code available: https://anonymous.4open.science/r/HAGC/.