AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering

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-11], multivariate data clustering [12-14], image segmentation [15, 16], and network vulnerability assessment [17]. Spectral clustering [12-14] 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 [18], computing its eigendecomposition, and performing K-means clustering [19] on the eigenvectors to partition the nodes into clusters. Although heuristic methods have been proposed to automatically select the number of clusters [12,13,20], 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. Based on a recent development of clustering reliability analysis for SGC under the random interconnection model (RIM) [21], we propose a novel automated model order selection (AMOS) algorithm for SGC. AMOS works by incrementally increasing the number of clusters, estimating the quality of identified clusters, and providing a series of clustering reliability tests.