On Parameter Tuning for Spectral Clustering: Two Simple, Fast, and Effective Criteria
Guangliang Chen, Valen Feldmann, Irene Seo · IEEE Access · 2025
Spectral clustering is a modern clustering approach with many successful applications such as image segmentation and document grouping. However, it has faced two major challenges – high computational complexity and sensitivity of a scale parameter associated to the similarity function used. Since its introduction, much effort has been devoted to improving the scalability of spectral clustering, while little research has been conducted on parameter tuning. In this paper, we address the parameter tuning challenge of spectral clustering in a general context. We first recognize that the task of parameter tuning is equivalent to identifying a proper scale of the data set that corresponds to the natural clusters in it. We then propose two new criteria –relative k-means and relative NCut– for tuning the scale parameter used in similarity functions such as Gaussian and cosine. Therelative k-meanscriterion examines the tightness of the clusters in the embedding space, whereas therelative NCutcriterion is directly based on a spectral clustering objective. Experiments were conducted on a combination of synthetic and real data sets, which demonstrate the effectiveness of the proposed tuning techniques.