Despite its effectiveness, spectral clustering is often impractical for large-scale data due to its high computational complexity$(O(n^{2}))$and limited clustering quality arising from three fundamental limitations: (1) reliance on a fixed similarity graph that cannot adapt to complex local structures, (2) inability to capture higher-order relationships, and (3) a decoupled two-step pipeline that separates embedding and clustering. To address these issues, we propose OA2H-SP, a novel framework that achieves linear-time spectral clustering$(O(nm)$with$m\ll n)$while enhancing clustering accuracy and scalability. Our method constructs an anchor-adaptive hypergraph to model both adaptive and higher-order affinities efficiently. It further unifies representation learning and discrete clustering in a one-step optimization scheme, avoiding the need for k-means post-processing. Extensive experiments on benchmark datasets demonstrate that$\text{OA}^{2}\mathrm{H}$. SP delivers superior performance in terms of accuracy, robustness, and runtime compared to existing hypergraph-based and anchor-driven spectral clustering methods.

Attributed graph clustering is a fundamental task in network mining, essential for uncovering valuable insights in various applications. However, the heterogeneity of information from structural and attribute spaces poses significant challenges in achieving consistent and meaningful clustering. To address this, we propose Relative Entropy-based Regularized Non-negative Matrix Factorization (RENMF), a novel approach that integrates structural and attribute information through advanced matrix factorization techniques. RENMF employs Symmetric NMF and Projective NMF to extract community membership distributions from the structural and attribute spaces, respectively. By treating these distributions as homogeneous, RENMF preserves distinct, denoised information from both spaces while considering their heterogeneous complementary information. We introduce Relative Entropy (RE) as a novel regularization term to facilitate interaction between these spaces, aiming to maximize consistency between the discovered latent distributions. In this interaction, we leverage the asymmetric property of RE to emphasize attributes as essential complementary information for structural clustering. The RENMF model is solved using a new iterative multiplicative update rule, with convergence theoretically proven. We evaluate RENMF’s effectiveness through extensive experiments on 10 real-world networks, comparing it to 11 state-of-the-art clustering methods. The results demonstrate RENMF’s superiority in ground truth matching and key quality metrics, outperforming existing methods.