В качестве примера взял 1.3 млн точек из множества Жюлиа (-0.123+0.745*j), каждую точку соединил с ближайшими 8 соседями - получился граф с симметричной матрицей смежности X, которую слева и справа умножил на случайную ортонормированную матрицу R размером 1.3M на 130 (R сначала заполняется гауссовским шумом, а затем пропускается через быструю QR декомпозицию для ортонормировки):

Y = (R^T)*X*R,

Так перешел от матрицы 1.3M х 1.3M к матрице 130 х 130. По теореме Пуанкаре собственные значения маленькой матрицы Y зажаты между собственными значениями большой X, примерно сохраняя их распределение. Значит можно взять несколько λ от Y (я взял первые 13 собственных значений) прогнать их итерациями через X и получить соответствующие им собственные вектора матрицы X, а дальше отправить в k-means или гауссовские смеси (выбрал этот вариант, потому-то k-means оказался более шумный). Получается такая кластеризация графа на случайных проекциях.