Beyond Bottom-k: Structural Nullspaces in Spectral Clustering of Sparse Heterogeneous Graphs

Spectral clustering is often reported to underperform on sparse heterogeneous graphs, motivating increasingly sophisticated spectral operators. We show that on several standard benchmarks the classical Laplacian is not the main obstacle: literal bottom-k selects structural zero modes created by disconnected components before it reaches the nonzero low-frequency spectrum. We prove that when these zero modes fill the k-dimensional embedding and the evaluated vertices lie in one component, row normalization collapses the representation and removes all within-component geometry available to k-means. We also quantify the partial-distortion regime below capacity. This suggests a minimal correction: skip the structurally known zero modes and use the first k nonzero eigenvectors, leaving the graph, Laplacian, normalization, and clustering algorithm unchanged. Across the sparse benchmarks we study, this corrected classical baseline reaches the highest mean AMI (0.62) in a strictly protocol-matched comparison against the sophisticated operators proposed for this regime (regularized spectral clustering, Bethe–Hessian, and Di-SIM). Because the nullspace is known from connected components, the correction can also be implemented directly in a sparse eigensolver without computing the discarded modes. Our results suggest that spectral benchmarks should verify which part of the spectrum a baseline actually extracts before attributing performance gains to a better operator.