Bootstrap AMG for Spectral Clustering

Graph Laplacian is a popular tool for analyzing graphs, in particular in graph partitioning and clustering. Given a notion of similarity (via an adjacency matrix), graph clustering refers to identifying different groups such that vertices in the same group are more similar compared to vertices across different groups. Data clustering can be reformulated in terms of a graph clustering 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 often 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 which constructs a set of vectors associated with the graph Laplacian. These vectors, referred to as algebraically smooth ones, span a low-dimensional euclidean space, which we use to represent the data, enabling cluster detection both in synthetic and in realistic well-clustered graphs. We show that in the case of a good quality bootstrap AMG, the computed smooth vectors employed in the construction of the final AMG operator, which by construction is spectrally equivalent to the originally given graph Laplacian, accurately approximate the space in the lower portion of the spectrum of the preconditioned operator. Thus, our approach can be viewed as a spectral clustering technique associated with the generalized spectral problem (Laplace operator versus the final AMG operator), and hence it can be seen as an extension of the classical spectral clustering which employs a standard eigenvalue problem.