  We study the problem of efficient 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 (a NP-hard problem in
general) is achievable through solving a computationally efficient convex
optimization problem with a tensor nuclear norm constraint. Our analysis
provides the conditions for our approach to succeed on recovering the true
underlying cluster structures, with high probability.
