Low-Rank Recovery of High-Order Neighbor Structure for Scalable Multi-View Clustering

Anchor-based multi-view clustering has attracted considerable attention for its scalability. However, existing methods face three limitations: (1) direct sample–anchor graphs insufficiently capture high-order neighbor connectivity; (2) conventional tensor nuclear norm regularization may over-shrink dominant singular values; (3) heterogeneous relationships among view pairs are often not explicitly modeled. To address these limitations, we propose High-Order Neighbor Recovery (HONR), a scalable framework for recovering high-order neighbor structure through low-rank tensor learning. Specifically, HONR uses multi-step random walks to capture indirect sample–anchor connections and aggregates transitions across orders and views into a compact tensor. For a more accurate approximation of tensor rank, we introduce an arctangent-based nonconvex approximation that alleviates the excessive shrinkage of dominant singular values. Furthermore, a view-relation regularizer based on order-wise transition similarities explicitly models pairwise view relationships and promotes consistency between structurally similar views. An alternating optimization algorithm is developed, with computational complexity linear in the number of samples when the numbers of anchors and views are fixed. Experiments against eight baselines on seven benchmark datasets demonstrate the effectiveness of the proposed HONR.