Coreset Spectral Clustering without Kernel Intermediary

Existing coreset methods for spectral clustering commonly proceed through the equivalence between normalized cut and weighted kernel $k$-means. We study whether the compressed graph can instead be constructed and solved directly in the graph domain. GCSC combines degree-stratified vertex sampling, retention of high-weight input edges, spectral clustering on the endpoints of those edges, and average-affinity lifting. Every retained edge keeps its original weight, and no off-support edge is introduced. For a fixed sample and edge count, we establish edge-tail optimality. We also derive an explicit stratified-sampling bound for endpoint coverage. Under stated perturbation/gap, tolerance-separation, balance, and margin conditions, same-vertex spectral stability and robust lifting yield two-sided full-graph NCut fidelity to a fixed reference partition, such as standard spectral clustering. On six benchmark datasets, GCSC attains the highest mean ARI among the compared coreset methods on five datasets at the largest shared coreset size. Mechanism studies further characterize sampling fidelity, edge-budget sensitivity, and affinity lifting.