Среди обилия методов кластеризации, существует метод спектрального кластеринга (spectral clustering). Исходя из того что мы знаем сейчас спектральный кластеринг (и/или его вариации, к примеру c non-bactracking operator) — это один из наиболее адекватных способов кластеризации (см. к примеру сравнение тут, как это в общих чертах работает можно почерпнуть отсюда). В этом суждении естественно есть personal bias, который возник у меня из-за того, что в моем кругу общения люди спектральный кластеринг сильно любят. Эта любовь обоснована некоторым набором теорем, которые делают спектральный кластеринг наиболее оправданным, так сказать. В целом написано довольно много обзоров, туториалов и т.д.

Не смотря на это обилие туториалов и статей, имеется проблема следующего рода. Первым шагом в спектральном кластеринге является нахождение спектра (собственных значений+векторов) матрицы Кирхгофа. Эта простая задача: миллиард методов реализовано, с ними все хорошо. Спектральный кластеринг основан на идее, что информация о кластерах в сети/графе сидит в изолированных собственных значениях. Под этим понимается следующее: спектр матрицы содержит "колбаску" непрерывных собственных значений и некоторое конечное число изолированных (дискретных) собственных значений.

Насколько нам известно, отделение дискретной части спектра от непрерывной — это некоторое "рукомахание". По всей видимости, не придумано ничего лучше чем "отсечение" дискретной части путем анализа квантилей набора расстояний между собственными значениями (в непрерывной части спектра расстояния между собственными значениями очень малы в сравнении с изолированным куском).

Вопрос: существует ли более строгий способ отделения изолированных собственных значений в спектре от непрерывной его части, чем "рукомахание", основанное на квантилях? Если его не существует, то можно ли его сформулировать? По всей видимости, в качестве отправной точки можно стартовать со stochastic block model.

В истории со spectral clustering есть еще один вопрос (кажется, что это мини-вопрос). Он состоит в следующем. Обычно с наличием кластеров связаны изолированные "низкоэнергетические" собственные значения (с.з.), т.е. те, которые лежат в начале спектра. Однако мы наблюдаем (глаза вроде все еще видят) что имеются изолированные с.з. в конце спектра, т.е. "высокоэнергетические". Насколько нам известно, такие с.з. указывают на наличие симметрий в кластерах, к примеру некоторой "дольности". Хочется убедиться в верности этого суждения и установить все-таки природу таких с.з.