Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering

Undirected graphs are widely used for network data analysis, where nodes can represent entities or data samples, and the existence and strength of edges can represent relations or affinity between nodes. For attributional data (e.g., multivariate data samples), such a graph can be constructed by calculating and thresholding the similarity measure between nodes. For relational data (e.g., friendships), the edges reveal the interactions between nodes. The goal of graph clustering is to group the nodes into clusters of high similarity. Applications of graph clustering, also known as community detection [1], [2], include but are not limited to graph signal processing [3]-[12], multivariate data clustering [13]-[15], image segmentation [16], [17], structural identifiability in physical systems [18], and network vulnerability assessment [19]. Spectral clustering [13]-[15] is a popular method for graph clustering, which we refer to as spectral graph clustering (SGC). It works by transforming the graph adjacency matrix into a graph Laplacian matrix [20], computing its eigendecomposition, and performing K-means clustering [21] on the eigenvectors to partition the nodes into clusters. Although heuristic methods have been proposed to automatically select the number of clusters [13], [14], [22], rigorous theoretical justifications on the selection of the number of eigenvectors for clustering are still lacking and little is known about the capabilities and limitations of spectral clustering on graphs.