Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
复制标题
DOI：
10.1109/jstsp.2018.2837638
复制
发表时间：
2018-10-01
影响因子：
7.5
通讯作者：
Suh, Changho
中科院分区：
文献类型：
--
作者：
Ahn, Kwangjun;Lee, Kangwook;Suh, Changho
光谱聚类是一种著名的基于成对相似度信息对对象进行划分的算法。虽然这种方法已经成功地应用于各种领域，但它也有局限性。原因是有许多其他应用程序中只有多路相似性度量可用。这促使我们探索多路测量设置。在本文中，我们开发了两种用于这种设置的算法：超图光谱聚类（HSC）和超图光谱聚类与局部细化（HSCLR）。我们的主要贡献在于随机超图模型下的多时算法的性能分析，我们将其命名为加权随机块模型，其中对象和多路度量分别被建模为超边的节点和权重。用n表示节点数，我们的分析揭示了以下内容：1)如果边权之和（稍后解释）为Omega (n)，则HSC输出的分区优于随机猜测；2)当边权和为(n)时，HSC输出一个除节点消失部分外与隐藏分区重合的分区；3)如果边权之和为n log n阶，HSCLR精确恢复隐藏分区。我们的结果改进了最近在模型下建立的技术状态，并且他们首先解决了二元边权情况下的有序最优结果。此外，我们证明了我们的结果导致子空间聚类的高效草图算法，这是一种计算机视觉应用。最后，我们表明HSCLR达到了一个特殊但实际相关的模型的信息理论极限，从而对这种情况没有计算障碍。
Spectral clustering is a celebrated algorithm that partitions the objects based on pairwise similarity information. While this approach has been successfully applied to a variety of domains, it comes with limitations. The reason is that there are many other applications in which only multiway similarity measures are available. This motivates us to explore the multiway measurement setting. In this paper, we develop two algorithms intended for such setting: hypergraph spectral clustering (HSC) and hypergraph spectral clustering with local refinement (HSCLR). Our main contribution lies in performance analysis of the polytime algorithms under a random hypergraph model, which we name the weighted stochastic block model, in which objects and multiway measures are modeled as nodes and weights of hyperedges, respectively. Denoting by n the number of nodes, our analysis reveals the following: 1) HSC outputs a partition which is better than a random guess if the sum of edge weights (to be explained later) is Omega (n); 2) HSC out puts a partition which coincides with the hidden partition except for a vanishing fraction of nodes if the sum of edge weights is.(n); and 3) HSCLR exactly recovers the hidden partition if the sum of edge weights is on the order of n log n. Our results improve upon the state of the arts recently established under the model and they first settle the orderwise optimal results for the binary edge weight case. Moreover, we show that our results lead to efficient sketching algorithms for subspace clustering, a computer vision application. Finally, we show that HSCLR achieves the information-theoretic limits for a special yet practically relevant model, thereby showing no computational barrier for the case.