Parallel-S \(^2\) CAG: Efficient Multi-core Spectral Subspace Clustering for Large-Scale Attributed Graphs
摘要
Spectral subspace clustering uses both graph structure and node attributes, but the \(O(V^3)\) cost makes it impractical for large networks. We built a parallel version of S \(^2\) CAG (Spectral Subspace Clustering for Attributed Graphs) and ran it on graphs ranging from 169K to 2M nodes. A key finding emerged: graph scale matters more than density for parallel speedup. Graphs in the medium-sparse range (0.0001 to 0.001% density) gave the best results. Testing on 5 large datasets with 1 to 32 cores, we achieved up to 8.51 times speedup over sequential S \(^2\) CAG. Efficiency remains high: 61 to 99% at 4 cores, 35 to 88% at 8 cores, with no loss in clustering quality. The sparse Arxiv_2M (2M nodes) reached 8.51 times while denser Corafull_250k (250K nodes) achieved 4.36 times. Eight cores appears to be the practical optimal point, and increasing graph size by 11.8 times yields approximately 1.32 times better speedup.