Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
复制标题
谱图聚类的同时维数和复杂性模型选择
DOI：
--
复制
发表时间：
2019
影响因子：
2.4
通讯作者：
D. Marchette
中科院分区：
文献类型：
--
作者：
Congyuan Yang;C. Priebe;Youngser Park;D. Marchette
摘要我们感兴趣的问题是通过识别潜在的社区结构来聚类图的顶点。在各种顶点聚类方法中，谱聚类是最流行的方法之一，因为它易于实现，同时往往优于传统的聚类算法。然而，在谱聚类中有两个固有的模型选择问题，即估计嵌入维数和聚类数。本文试图解决这个问题，建立一个新的模型选择框架，专门为图上的顶点聚类下的随机块模型。第一个贡献是一个概率模型，它近似的分布图的扩展谱嵌入。该模型是基于嵌入的信息部分的渐近正态性的理论结果构建的，并且基于模拟结果提供了嵌入的冗余部分的限制行为的猜想。第二个贡献是一个同步模型选择框架。与传统的方法相比，我们的模型选择过程估计嵌入维数和集群的数量同时。基于我们的约束分布模型，给出了模型参数估计的相合性定理，为我们的方法的实用性提供了支持。我们的同时模型选择（SMS）的顶点聚类算法提出，在模拟实验中表现出上级性能。我们说明了我们的方法通过应用程序的脑图的集合。
Abstract Our problem of interest is to cluster vertices of a graph by identifying underlying community structure. Among various vertex clustering approaches, spectral clustering is one of the most popular methods because it is easy to implement while often outperforming more traditional clustering algorithms. However, there are two inherent model selection problems in spectral clustering, namely estimating both the embedding dimension and number of clusters. This article attempts to address the issue by establishing a novel model selection framework specifically for vertex clustering on graphs under a stochastic block model. The first contribution is a probabilistic model which approximates the distribution of the extended spectral embedding of a graph. The model is constructed based on a theoretical result of asymptotic normality for the informative part of the embedding, and on simulation results providing a conjecture for the limiting behavior of the redundant part of the embedding. The second contribution is a simultaneous model selection framework. In contrast with traditional approaches, our model selection procedure estimates embedding dimension and number of clusters simultaneously. Based on our conjectured distributional model, a theorem on the consistency of the estimates of model parameters is presented, providing support for the utility of our method. Algorithms for our simultaneous model selection (SMS) for vertex clustering are proposed, demonstrating superior performance in simulation experiments. We illustrate our method via application to a collection of brain graphs.