Sublinear Spectral Clustering Oracle with Little Memory

Ranran Shen, Xiaoyi Zhu, Pan Peng +1

We study the problem of designing \emph{sublinear spectral clustering oracles} for well-clusterable graphs. Such an oracle is an algorithm that, given query access to the adjacency…