Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringStochastic Block ModelSimilar Papers 제목 키워드 기반
Improved Moves for Truncated Convex Models
We consider the problem of obtaining the approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose an impro…
Convex Relaxations of Bregman Divergence Clustering
Although many convex relaxations of clustering have been proposed in the past decade, current formulations remain restricted to spherical Gaussian or discriminative models and are susceptible to imbalanced clusters. To a…
ClusteringA New Relaxation Approach to Normalized Hypergraph Cut
Normalized graph cut (NGC) has become a popular research topic due to its wide applications in a large variety of areas like machine learning and very large scale integration (VLSI) circuit design. Most of traditional NG…
ClusteringHow to tell when a clustering is (approximately) correct using convex relaxations
We introduce the Sublevel Set (SS) method, a generic method to obtain sufficient guarantees of near-optimality and uniqueness (up to small perturbations) for a clustering. This method can be instantiated for a variety of…
ClusteringConstrained fractional set programs and their application in local clustering and community detection
The (constrained) minimization of a ratio of set functions is a problem frequently occurring in clustering and community detection. As these optimization problems are typically NP-hard, one uses convex or spectral relaxa…
ClusteringCommunity Detection