Spectral clustering in birthday paradox time

Given a vertex in a (k, φ, ϵ)-clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of φ-expanders of size ≈ n/k with outer conductance bounded by ϵ, can one quickly tell which cluster it belongs to? This is a classical question going back to the expansion testing problem of Goldreich and Ron'11 (the case of k = 2) that has received a lot of attention in the literature. For k = 2 a sample of ≈ n 1/2+O(ϵ/φ 2 ) logarithmic length walks from a given vertex approximately determines its cluster membership by the birthday paradox: two vertices whose random walk samples are 'close' are likely in the same cluster, and otherwise in different clusters.

The study of the general case k > 2 was initiated by Czumaj, Peng and Sohler [STOC'15], and the works of Chiplunkar et al. [FOCS'18], Gluch et al. [SODA'21

random walk samples, and the same query time, suffices for general k. This matches the k = 2 result up to polynomial factors in k, but one notices a conceptual inconsistency: if the birthday paradox is indeed the phenomenon guiding the query complexity here, then the query complexity should decrease, as opposed to increase, with the number of clusters k! Since clusters have size ≈ n/k, we expect to need ≈ (n/k) 1/2+O(ϵ/φ 2 ) random walk samples, which gets smaller when k gets larger, and reduces to constant when k ≈ n. The currently best known query time (of Gluch et al. [SODA'21]), however, increases with k due to computationally heavy linear-algebraic post-processing of random walk samples.

In this paper we design a novel representation of vertices in a (k, φ, ϵ)-clusterable graph by a mixture of samples of logarithmic length walks. This representation not only uses the optimal ≈ (n/k) 1/2+O(ϵ/φ 2 ) number of walks per vertex, but also allows for fast nearest neighbor search: given a collection of ≈ k vertices representing the clusters, and a query vertex x, we can find the cluster of x, using nearly linear time in the representation size of x. This gives a spectral clustering oracle with query time ≈ (n/k) 1/2+O(ϵ/φ 2 ) and space complexity k • (n/k) 1/2+O(ϵ/φ 2 ) , matching the birthday paradox bound.