  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 characterized by a large inner conductance (at least
$\varphi$) and a small outer conductance (at most $\varepsilon$). Our aim is to
preprocess the graph to enable clustering membership queries, with the key
requirement that both preprocessing and query answering should be performed in
sublinear time, and the resulting partition should be consistent with a
$k$-partition that is close to the ground-truth clustering. Previous oracles
have relied on either a $\textrm{poly}(k)\log n$ gap between inner and outer
conductances or exponential (in $k/\varepsilon$) preprocessing time. Our
algorithm relaxes these assumptions, albeit at the cost of a slightly higher
misclassification ratio. We also show that our clustering oracle is robust
against a few random edge deletions. To validate our theoretical bounds, we
conducted experiments on synthetic networks.
