Rethinking Progress in Attribute-Missing Graph Clustering: A Benchmark and a Simple Scalable Framework

Graph clustering aims to uncover latent communities by jointly exploiting graph structure and node attributes in an unsupervised manner. In real-world applications, however, some nodes may have completely missing attributes due to privacy constraints, data acquisition failures, and cold-start nodes. Missing semantic information makes learning discriminative representations for clustering more challenging. Despite substantial recent efforts on attribute-missing graph clustering, it remains unclear how much genuine progress has been made and how much model complexity is actually needed. Current evaluations are often too narrow to establish generality, while increasingly elaborate pipelines obscure which mechanisms are actually necessary for effective clustering. To systematically revisit these questions, we establish a comprehensive and reproducible benchmark covering 22 graph datasets and 32 baselines from four method families across diverse graph scales. The benchmark reveals that specialized attribute-missing methods can even underperform conventional graph clustering methods. Moreover, we propose VISTA, a lightweight and scalable framework. By performing bounded sparse topology propagation, VISTA recovers missing semantics from locally observed attributes without a learnable imputer. By adopting topology-conditioned cross-view prototype learning, it learns clustering-oriented representations without graph reconstruction or dense node-pair modeling. Extensive experiments demonstrate that VISTA achieves competitive clustering performance, remains robust under high attribute-missing rates, and scales efficiently to large graphs.