S3FC

Scalable Sparse Spectral Fusion Clustering for Multi-Manifold Data

Abstract

Clustering data that lies on multiple manifolds with mixed linear and nonlinear geometry remains a challenging problem. Existing sparse subspace methods are limited to linear structures, while spectral methods rely on a single similarity measure that cannot separate intersecting manifolds. We present S3FC (Scalable Sparse Spectral Fusion Clustering), which fuses a sparse subspace affinity with a spectral affinity so that connections survive only where both views agree. We investigate three fusion operators (product, power diffusion, and Hadamard) and show that different operators suit different data geometries. Experiments on 9 datasets against 10 baselines show that S3FC achieves the highest Normalized Mutual Information (NMI) on 7 of 9 datasets and ties on 1, including perfect clustering on 4 datasets. On a mixed-dimension problem of lines through a sphere, S3FC achieves 0.966 NMI where the best competitor reaches 0.696, and on real-world drone GPS data S3FC achieves perfect clustering. Sparse storage and dictionary restriction enable scaling to N = 50,000 with 666× memory savings compared to dense N × N storage, where dense competitors crash with out-of-memory errors.