Hypergraph Label Propagation Network

Many problems in computer science can be represented by a graph and reduced to a graph clustering or k-way partitioning problem. In the classical definition, a graph consists of nodes and edges which usually connect exactly two nodes. Hypergraphs are a generalization of graphs, where every edge can connect an arbitrary number of nodes. Recent results suggest that some problems in computer science are better and more intuitively modeled with hypergraphs instead of graphs. This thesis investigates the adaptation of label propagation, a graph clustering algorithm, to hypergraph partitioning. We propose three adaptations of label propagation which are motivated by graph-based hypergraph modeling and evaluate them as coarsening strategies in a direct k-way multilevel hypergraph partitioning framework. Furthermore, we propose a greedy local search algorithm inspired by label propagation for the uncoarsening and refinement phase of the multilevel partitioning heuristic. We compare our algorithms to the state-of-the-art hypergraph partitioners hMetis and PaToH. Our results imply that the utilization of label propagation in the multilevel hypergraph partitioning scheme is promising, as we outperform both hMetis and PaToH on VLSI instances for larger values of k: for k = 128 our proposed algorithms produce 2% better cuts than hMetis and 4% better cuts than PaToH. Definitions and Terminology , e 4 = v 4 , v 5 , v 6 , v 7 , e 5 = v 5 , v 6 , v 7 c ≡ 1 ω ≡ 1 v 6 v 5 v 7 v 4 v 2 v 1 v 3 e 2 e 1 e 3 e 4 e 5