Fuzzy Clustering via Orthogonal Tensor Decomposition on High-Order Anchor Graphs

Clusteringis an important unsupervised learning technique widely applied in data analysis and pattern recognition. Graph-based clustering methods have gained attention for their ability to effectively model complex data structures. However, traditional methods mainly rely on first-order proximity information, which struggles to capture high-order structural relationships between data points. Such limitation can significantly degrade clustering performance. To address this issue, we propose a novel fuzzy clustering approach leveraging orthogonal tensor decomposition on high-order anchor graphs (OTDHAG). Unlike conventional high-order graph-based methods that rely on self-multiplication of proximity matrices, which are computationally expensive, our method introduces the high-order anchor graph with low computational complexity, and exploits high-order proximity information via orthogonal tensor factorization on high-order anchor graphs. Meanwhile, tensor nuclear norm regularization is adopted to enhance clustering consistency, thereby improving clustering quality. Experiments on 10 benchmark datasets (e.g., MNIST, Wine, PIE) demonstrate that OTDHAG outperforms 14 state-of-the-art methods, achieving 92.3% accuracy on Wine (vs. 86.5% for DenoHOG) and 88.7% NMI on MNIST (vs. 82.1% for AOPL-Root). In conclusion, OTDHAG not only significantly improves clustering accuracy and computational efficiency but also provides a scalable solution for clustering tasks. Code available: <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://anonymous.4open.science/r/HOAGTD-CED0</uri>.