Applying bootstrap AMG in spectral clustering

Computing eigenvectors of graph Laplacian is a main computational kernel in data clustering, i.e., in identifying different groups such that data in the same group are similar and points in different groups are dissimilar with respect to a given notion of similarity. Data clustering can be reformulated in terms of a graph partitioning problem when the given set of data is represented as a graph, also known as similarity graph. In this context, eigenvectors of the graph Laplacian are used to obtain a new geometric representation of the original data set which generally enhances cluster properties and improves cluster detection. In this work we apply a bootstrap Algebraic MultiGrid (AMG) method to compute an approximation of the eigenvectors corresponding to small eigenvalues of the graph Laplacian and analyse their ability to catch clusters both in synthetic and in realistic graphs.