论文标题
具有张量核标准约束的高级种植模型的精确分区
Exact Partitioning of High-order Planted Models with a Tensor Nuclear Norm Constraint
论文作者
论文摘要
我们研究了高级种植模型产生的超图的有效精确分配的问题。高阶种植模型假定一些基本的群集结构，并通过在节点之间放置超增强来模拟高阶相互作用。示例模型包括分离超截图，最密集的次毛图和HyperGraph随机块模型。我们表明，通过通过张量核定标准约束来解决计算有效的凸优化问题，可以通过解决计算有效的凸优化问题来实现高阶种植模型的精确分区（通常是NP硬化问题）。我们的分析为我们的方法提供了成功的条件，即以很高的可能性恢复了真正的基础群集结构。
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.
