A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time

Ranran Shen, Pan Peng

We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain $k$ latent clusters, each charact…