EXACT PARTITIONING OF HIGH-ORDER PLANTED MODELS WITH A TENSOR NUCLEAR NORM CONSTRAINT

We study the problem of exact partitioning of the hypergraphs generated by high-order planted models. A high-order planted model assumes some underlying cluster structures, and simulates high-order interactions by placing hyperedges among nodes. Example models include the disjoint hypercliques, the densest subhypergraphs, and the hypergraph stochastic block models. We show that exact partitioning of high-order planted models is achievable through solving a convex optimization problem with a tensor nuclear norm constraint. Our analysis provides the statistical upper bounds for our approach to succeed on recovering the true underlying cluster structures, with high probability.