A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
This work addresses the challenge of efficient clustering queries for graph analysis, but it is incremental as it builds on prior oracles with relaxed assumptions.
The paper tackles the problem of designing a sublinear-time spectral clustering oracle for graphs with strong clusterability, achieving a solution that relaxes previous assumptions on conductance gaps and preprocessing time, albeit with a slightly higher misclassification ratio, and validates the approach with experiments on synthetic networks.
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 $\textrm{poly}(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.