Refer to documentation section 2.3.5:
https://scikit-learn.org/stable/modules/clustering.html#spectral-clustering
The documentation says that spectral clustering is especially efficient if the affinity matrix is sparse (and the pyamg module is installed). My understanding of a sparse matrix is that there are more zeros than nonzeros within the matrix.
When an affinity matrix is 'sparse', does this mean there are overall less calculations to find the affinity matrix and that makes it more efficient? My reasoning is that these 'sparse zero values' will have a distance of 0 and have high similarity.
If this is true, to prepare your data it would be better to preprocessing.normalize rather than preprocessing.scale before doing spectral cluster analysis...?