Beyond Implicit Constraint: Explicit Low-Rank Structured Subspace Learning for Fast Attributed Graph Clustering

Abstract

Attributed graph clustering has achieved remarkable success by synergistically integrating topological structures and node attributes. While subspace learning has emerged as a dominant paradigm for node partitioning, most existing methods rely on implicit low-rank constraints, which often fail to capture complex nonlinear manifolds and suffer from prohibitive computational overhead on large-scale graphs. In this paper, we propose ELSS (Explicit Low-rank Structured Subspace learning), a scalable and robust framework that transcends implicit formulations. Specifically, ELSS learns an explicit and nonlinear low-rank subspace within a graph-structured embedding space, effectively uncovering latent cluster structures. To effectively mitigate the pervasive oversmoothing issue, we introduce a homophily-aware adaptive graph filter, which dynamically calibrates smoothing intensity to preserve discriminative ego-information. Furthermore, to ensure linear scalability, we develop a PageRank-guided structural sampling strategy for anchor-based approximation, which identifies pivotal landmarks based on their global topological prestige. Theoretical analysis guarantees that ELSS effectively mitigates spectral collapse while maintaining a linear complexity. Extensive experiments on diverse benchmarks demonstrate that ELSS consistently delivers superior clustering accuracy over state-of-the-art methods.