# A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 27 Oct 2023.

## Builds on (most cited first, 16 of 16)

- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Flow-Based Algorithms for Local Graph Clustering](https://mlsanity.com/paper/1307.2855/) (2013)
- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Learning Communities in the Presence of Errors](https://mlsanity.com/paper/1511.03229/) (2015)
- [Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs](https://mlsanity.com/paper/1904.09710/) (2019)
- [Average Sensitivity of Spectral Clustering](https://mlsanity.com/paper/2006.04094/) (2020)
- [Spectral Clustering Oracles in Sublinear Time](https://mlsanity.com/paper/2101.05549/) (2021)
- [Spectral concentration and greedy k-clustering](https://mlsanity.com/paper/1404.1008/) (2014)
- [Constant Factor Approximation for Balanced Cut in the PIE model](https://mlsanity.com/paper/1406.5665/) (2014)
- [Tight Error Bounds for Structured Prediction](https://mlsanity.com/paper/1409.5834/) (2014)
- [Sublinear-Time Clustering Oracle for Signed Graphs](https://mlsanity.com/paper/2206.13813/) (2022)
- [Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds](https://mlsanity.com/paper/2207.02581/) (2022)

## Abstract (arXiv)

We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain k latent clusters, each characterized by a large inner conductance (at least varphi) and a small outer conductance (at most varepsilon). Our aim is to preprocess the graph to enable clustering membership queries, with the key requirement that both preprocessing and query answering should be performed in sublinear time, and the resulting partition should be consistent with a k-partition that is close to the ground-truth clustering. Previous oracles have relied on either a textrmpoly(k)log n gap between inner and outer conductances or exponential (in k/varepsilon) preprocessing time. Our algorithm relaxes these assumptions, albeit at the cost of a slightly higher misclassification ratio. We also show that our clustering oracle is robust against a few random edge deletions. To validate our theoretical bounds, we conducted experiments on synthetic networks.