  We consider the problem of testing graph cluster structure: given access to a
graph $G=(V, E)$, can we quickly determine whether the graph can be partitioned
into a few clusters with good inner conductance, or is far from any such graph?
This is a generalization of the well-studied problem of testing graph
expansion, where one wants to distinguish between the graph having good
expansion (i.e.\ being a good single cluster) and the graph having a sparse cut
(i.e.\ being a union of at least two clusters). A recent work of Czumaj, Peng,
and Sohler (STOC'15) gave an ingenious sublinear time algorithm for testing
$k$-clusterability in time $\tilde{O}(n^{1/2} \text{poly}(k))$: their algorithm
implicitly embeds a random sample of vertices of the graph into Euclidean
space, and then clusters the samples based on estimates of Euclidean distances
between the points. This yields a very efficient testing algorithm, but only
works if the cluster structure is very strong: it is necessary to assume that
the gap between conductances of accepted and rejected graphs is at least
logarithmic in the size of the graph $G$. In this paper we show how one can
leverage more refined geometric information, namely angles as opposed to
distances, to obtain a sublinear time tester that works even when the gap is a
sufficiently large constant. Our tester is based on the singular value
decomposition of a natural matrix derived from random walk transition
probabilities from a small sample of seed nodes.
  We complement our algorithm with a matching lower bound on the query
complexity of testing clusterability. Our lower bound is based on a novel
property testing problem, which we analyze using Fourier analytic tools. As a
byproduct of our techniques, we also achieve new lower bounds for the problem
of approximating MAX-CUT value in sublinear time.
