Consistency of spectral hypergraph partitioning under planted partition model
Debarghya Ghoshdastidar, Ambedkar Dukkipati
The Annals of Statistics · 2017 · Volume 45 · Issue 1
Abstract
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 nonuniform 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 nonuniform hypergraphs.
Keywords
05C65, 05C80, 62F12, 62H30, Hypergraph, spectral algorithm, Stochastic block model
Enable JavaScript for citation tools and additional paper interactions.