Spectral clustering in birthday paradox time

Given a vertex in a \((k,\varphi,\epsilon)\)-clusterable graph, i.e. a graph whose vertex set can be partitioned into a disjoint union of \(\varphi\)-expanders of size \(\approx n/k\) with outer conductance bounded by \(\epsilon\), 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 \(\approx n^{1/2+O(\epsilon/\varphi^{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.