Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
This work addresses a theoretical gap in hypergraph partitioning for researchers in machine learning and network sciences, though it is incremental as it extends known graph results to hypergraphs.
The paper tackles the lack of theoretical guarantees for hypergraph partitioning algorithms by presenting a planted partition model for sparse random non-uniform hypergraphs and deriving an error bound for a spectral partitioning algorithm under this model, achieving the first consistency result for non-uniform hypergraphs.
Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received attention in the literature as compared to the extensive studies on the guarantees of graph partitioning. For instance, consistency results of spectral graph partitioning under the stochastic block model are well known. In this paper, we present a planted partition model for sparse random non-uniform hypergraphs that generalizes the stochastic block model. We derive an error bound for a spectral hypergraph partitioning algorithm under this model using matrix concentration inequalities. To the best of our knowledge, this is the first consistency result related to partitioning non-uniform hypergraphs.