Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE
arXiv:2003.10038 · doi:10.1109/JSAIT.2020.3037170
Abstract
We study hypergraph clustering in the weighted -uniform hypergraph stochastic block model (\textsf{-WHSBM}), where each edge consisting of 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 \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.
arXiv comment20 pages, 4 figure
References in corpus (13)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- User-friendly tail bounds for sums of random matrices
- Consistency of spectral clustering in stochastic block models
- Random hypergraphs and their applications
- Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
- Guaranteed clustering and biclustering via semidefinite programming
- Improved Graph Clustering
- Size biased couplings and the spectral gap for random regular graphs
- Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
- Evolution of high-order connected components in random hypergraphs