论文标题
通过凸出的MLE的凸松弛，可靠的超颗粒聚类
Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
论文作者
论文摘要
我们研究了加权$ D $均匀的超颗粒随机块模型（$ d $ \ textsf {-whsbm}）中的HyperGraph聚集，其中每个边缘由来自同一社区的$ D $节点组成的每个边缘的预期重量都高于不同社区的节点的边缘。我们提出了一种新的HyperGraph群集算法，称为\ Textsf {CrtMle}，并根据$ d $ \ textsf {-whsbm}提供了其性能保证，以进行常规参数制度。我们表明，所提出的方法可实现订单的最佳或最佳现有结果，以大约平衡的社区规模。此外，我们的结果解决了越来越多的不平衡大小群集的首次恢复保证。涉及理论分析和经验结果，我们证明了算法与社区规模不平衡或存在异常节点的不平衡性的鲁棒性。
We study hypergraph clustering in the weighted $d$-uniform hypergraph stochastic block model ($d$\textsf{-WHSBM}), where each edge consisting of $d$ nodes from the same community has higher expected weight than the edges consisting of nodes from different communities. We propose a new hypergraph clustering algorithm, called \textsf{CRTMLE}, and provide its performance guarantee under the $d$\textsf{-WHSBM} for general parameter regimes. We show that the proposed method achieves the order-wise optimal or the best existing results for approximately balanced community sizes. Moreover, our results settle the first recovery guarantees for growing number of clusters of unbalanced sizes. Involving theoretical analysis and empirical results, we demonstrate the robustness of our algorithm against the unbalancedness of community sizes or the presence of outlier nodes.
