Spectral Clustering Oracles in Sublinear Time

Given a graph G that can be partitioned into k disjoint expanders with outer conductance upper bounded by ǫ ≪ 1, can we efficiently construct a small space data structure that allows quickly classifying vertices of G according to the expander (cluster) they belong to? Formally, we would like an efficient local computation algorithm that misclassifies at most an O(ǫ) fraction of vertices in every expander. We refer to such a data structure as a spectral clustering oracle.

Our main result is a spectral clustering oracle with query time O * (n 1/2+O(ǫ) ) and preprocessing time 2 ǫ) that provides misclassification error O(ǫ log k) per cluster for any ǫ ≪ 1/ log k. More generally, query time can be reduced at the expense of increasing the preprocessing time appropriately (as long as the product is about n 1+O(ǫ) ) -this in particular gives a nearly linear time spectral clustering primitive.

The main technical contribution is a sublinear time oracle that provides dot product access to the spectral embedding of G by estimating distributions of short random walks from vertices in G. The distributions themselves provide a poor approximation to the spectral embedding, but we show that an appropriate linear transformation can be used to achieve high precision dot product access. We give an estimator for this linear transformation and analyze it using spectral perturbation bounds and a novel upper bound on the leverage scores of the spectral embedding matrix of a k-clusterable graph. We then show that dot product access to the spectral embedding is sufficient to design a clustering oracle. At a high level our approach amounts to hyperplane partitioning in the spectral embedding of G, but crucially operates on a nested sequence of carefully defined subspaces in the spectral embedding to achieve per cluster recovery guarantees.