A probabilistic model selection criterion for spectral clustering

Article type: Research Article

Authors: Bruneau, Pierrick^* | Otjacques, Benoît

Affiliations: Luxembourg Institute of Science and Technology 5, Avenue des Hauts-Fourneaux L-4362 Esch-sur-Alzette, Luxembourg

Correspondence: [*] Corresponding author: Pierrick Bruneau, Luxembourg Institute of Science and Technology 5, Avenue des Hauts-Fourneaux L-4362 Esch-sur-Alzette, Luxembourg. E-mail: pierrick.bruneau@list.lu.

Abstract: Model selection in spectral clustering consists in estimating the ground truth number of clusters K*. We propose a novel probabilistic framework to address this problem in a principled manner. The spectral clustering pipeline relies on a latent representation over which a mixture model with K components is eventually fitted. However the dimensionality of the latent representation varies alongside K: this setting is uncommon in the literature on mixture model selection. This raises issues regarding probabilistic modelling, and leads to the ineffectiveness of classical criteria such as the Bayesian Information Criterion (BIC). Alternatively, we propose an adapted Gaussian likelihood expression, and use it to derive a probabilistic model selection criterion for spectral clustering. We give theoretical arguments and empirical evidence suggesting the proposed criterion mitigates the peculiarities observed with classical criteria in an effective way. The performance of the method is evaluated on real and synthetic data sets, and compared to concurrent approaches from the literature.

Keywords: Spectral clustering, model selection

DOI: 10.3233/IDA-173607

Journal: Intelligent Data Analysis, vol. 22, no. 5, pp. 1059-1077, 2018