Is a Small Matrix Eigendecomposition Sufficient for Spectral Clustering?

Spectral clustering is effective but expensive at large scales because its standard formulation constructs an $n\times n$ affinity matrix and solves a large spectral problem. A central challenge is to retain informative cluster representations while reducing the matrix size to depend only on the number of clusters $k$. We address this challenge from a distributional perspective: each representative summarizes a distribution rather than an individual point. D-SPEC constructs an $n\times k$ point–distribution bipartite graph and reduces its spectral problem to a $k\times k$ matrix. We establish exact partition recovery under explicit affinity-profile conditions, perturbation-to-clustering error guarantees, and finite-partition bounds valid for adaptively selected representatives. Extensive experiments on synthetic and real-world datasets demonstrate the effectiveness and scalability of this distributional construction.