# Exact Partitioning of High-order Planted Models with a Tensor Nuclear Norm Constraint

arXiv: https://arxiv.org/abs/2006.11666 · HTML: https://mlsanity.com/paper/2006.11666/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2020.

## Built on by (most cited first, 1 of 1)

- [Information Theoretic Limits of Exact Recovery in Sub-hypergraph Models for Community Detection](https://mlsanity.com/paper/2101.12369/) (2021)

## Abstract (arXiv)

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.