HYPE: Massive Hypergraph Partitioning with Neighborhood Expansion

Many important real-world applications - such as social networks or distributed data bases - can be modeled as hypergraphs. In such a model, vertices represent entities - such as users or data records - whereas hyperedges model a group membership of the vertices - such as the authorship in a specific topic or the membership of a data record in a specific replicated shard. To optimize such applications, we need an efficient and effective solution to the NP-hard balanced k-way hypergraph partitioning problem. However, existing hypergraph partitioners that scale to very large graphs do not effectively exploit the hy-pergraph structure when performing the partitioning decisions. We propose HYPE, a hypergraph partitionier that exploits the neighborhood relations between vertices in the hypergraph using an efficient implementation of neighborhood expansion. HYPE improves partitioning quality by up to 95% and reduces runtime by up to 39% compared to streaming partitioning.