Higher-Order Spectral Clustering for Geometric Graphs

Graph clustering--the task of identifying groups of tightly connected nodes in a graph--is a widely studied unsupervised learning problem, with applications in computer science, statistics, biology, economy or social sciences [7]. In particular, spectral clustering is one of the key graph clustering methods [15]. In its most basic form, this algorithm consists in partitioning a graph into two communities using the eigenvector associated with the second smallest eigenvalue of the graph's Laplacian matrix (the socalled Fiedler vector [6]). Spectral clustering is popular, as it is an efficient relaxation of the NPhard problem of cutting the graph into two balanced clusters so that the weight between the two clusters is minimal [15]. In particular, spectral clustering is consistent in the Stochastic Block Model (SBM) for a large set of parameters [1], [11]. The SBM is a natural basic model with community structure.