Engineering a direct k-way Hypergraph Partitioning Algorithm
We develop a fast and high quality multilevel algorithm that directly partitions hypergraphs into k balanced blocks – without the detour over recursive bipartitioning. In particular, our algorithm efficiently implements the powerful FM local search heuristics for the complicated k-way case. This is important for objective functions which depend on the number of blocks connected by a hyperedge. We also remove several further bottlenecks in processing large hyperedges, develop a faster contraction algorithm, and a new adaptive stopping rule for local search. To further reduce the size of hyperedges, we develop a pin-sparsifier based on the min-hashing technique that clusters vertices with similar neighborhood. Extensive experiments indicate that our KaHyPar-partitioner compares favorably with the best previous systems. KaHyPar is faster than hMetis and computes better solutions. KaHyPar's results are considerably better than the (faster) PaToH partitioner.
Code (0)
등록된 구현이 없습니다.
Tasks
graph partitioninghypergraph partitioningSimilar Papers 제목 키워드 기반
Multilevel Acyclic Hypergraph Partitioning
A directed acyclic hypergraph is a generalized concept of a directed acyclic graph, where each hyperedge can contain an arbitrary number of tails and heads. Directed hypergraphs can be used to model data flow and executi…
hypergraph partitioningSchedulingConsistency of Spectral Hypergraph Partitioning under Planted Partition Model
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 partiti…
graph partitioninghypergraph partitioningStochastic Block ModelHypergraph Partitioning using Tensor Eigenvalue Decomposition
Hypergraphs have gained increasing attention in the machine learning community lately due to their superiority over graphs in capturing super-dyadic interactions among entities. In this work, we propose a novel approach …
graph partitioninghypergraph partitioningBalanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy
We propose a balanced coarsening scheme for multilevel hypergraph partitioning. In addition, an initial partitioning algorithm is designed to improve the quality of k-way hypergraph partitioning. By assigning vertex weig…
hypergraph partitioningUniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
In a series of recent works, we have generalised the consistency results in the stochastic block model literature to the case of uniform and non-uniform hypergraphs. The present paper continues the same line of study, wh…
Clusteringhypergraph partitioningStochastic Block Model