# Spectral Clustering Oracles in Sublinear Time

arXiv: https://arxiv.org/abs/2101.05549 · HTML: https://mlsanity.com/paper/2101.05549/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2021.

## Built on by (most cited first, 6 of 6)

- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)

## Abstract (arXiv)

Given a graph G that can be partitioned into k disjoint expanders with outer conductance upper bounded by εll 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 textitspectral clustering oracle. Our main result is a spectral clustering oracle with query time O^*(n1/2+O(ε)) and preprocessing time 2^O(frac1ε k4 log2(k)) n1/2+O(ε) that provides misclassification error O(ε log k) per cluster for any ε ll 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 n1+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 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.