A Projective Theory of Local Stability for Generalized Spectral Clustering

Generalized Spectral Clustering (GSC) on directed graphs depends on a tunable vertex measure, but it is unclear when changing this measure can change the resulting partition. We show that a naïve perturbation analysis can be misleading: positive rescaling of the measure rescales the GSC Laplacian but leaves its eigenspaces (and, whenever the bottom-k target is well defined, the clustering) unchanged. We therefore study stability after quotienting out this irrelevant scale. Before measuring stability, we check whether the target bottom-k eigenspace is uniquely defined, and give a cheap, linear-time structural test that detects an important class of non-identifiable cases. When the target is identifiable, we derive a local anchored-rounding stability radius that factors into three interpretable terms: how strongly the measure moves the operator, how well the target eigenspace is spectrally isolated, and how robust the embedding is to rounding. Local certificates then compose through continuation. Experiments on directed graphs show that removing scale changes the inferred stability by an order of magnitude, that clustering quality and stability need not coincide, that the radius tracks directly verified finite perturbations, and that local certificates compose through continuation into reachable regions more than 58× larger.