Reproduce “Fast $k$-means Seeding Under The Manifold Hypothesis” on OpenResearch

About this paper

Poojan Shah, Shashwat Agrawal, Ragesh Jaiswal

Researchers at Indian Institute of Technology Delhi developed Qkmeans, a fast k-means++ seeding algorithm that leverages the manifold hypothesis to accelerate clustering on high-dimensional data. This method theoretically establishes and empirically validates scaling laws for intrinsic data properties, achieving speedups of 5-10x over AFKMC^2 and PRONECoreset, and up to two orders of magnitude over RejectionSampling, while preserving clustering quality.

Key insights

• Under the manifold hypothesis, intrinsic data properties like the ratio of optimal 1-mean to k-means cost (`β_k`) and the dataset aspect ratio (`η`) follow predictable polynomial scaling laws, governed by the data's intrinsic dimension through the quantization exponent `ε = 2/d`.
• A carefully designed perturbed rejection sampling mechanism, utilizing approximate distances from ANNS, can effectively simulate the D^2 sampling of k-means++ with quantifiable approximation guarantees and significant runtime improvements.
• Leveraging geometric regularities intrinsic to the input data distribution (like the manifold hypothesis) provides a robust and practical framework for designing efficient clustering algorithms, bridging the gap between theoretical worst-case analysis and empirical performance.

Summary by alphaXiv.