Massive hypergraph partitioning

Abstract

The hypergraph model is a more generic version of the graph model. Instead of edges connecting only two vertices, hyperedges can connect an arbitrary number of vertices. This way, the hypergraph model has a higher expressiveness than the original graph model. It can model group memberships in social media or group chats in messengers easily. In the past years both, social media and instant messengers, gained much more popularity. The increased number of users and the thus increasing traffic result in larger hypergraph data sets, which can not be processed by a single machine. Hence, the hypergraphs need to be partitioned, thereby maintaining a low communication overhead in the later processing and having balanced partition sizes to ensure efficient parallelization. There are already many hypergraph partitioning algorithms so far, yet they are often limited in their parallelization, which is needed to process massive hypergraphs. A known paradigm which can be parallelized easily is label propagation. We created three approaches called Credit Label Propagation (CLP), Split Credit Label Propagation (SCLP) and Split Credit Label Propagation -- Credit Value Compensation (SCLP-cc) based on label propagation introducing new balancing punishments to improve the partitions balance leading to a better scalability. Thereby we introduced a credit value to regulate the growth of the label clusters. In the later algorithms we modified the credit value handling to prevent clusters from becoming to large, by regulating the amount of credit value available in the system. Further, we created a novel hypergraph partitioning algorithm called Gravity Expansion based on graph visualization algorithms. The hypergraphs vertices are placed in the center of a two-dimensional space. Next they are expanded into the space while keeping connected vertices close due to vertex movements via barrier jumps. After the expansion two gravity holes are placed which absorb and therefore partition the vertices. During the absorbing the vertices are further expanded to react to previous assignments. The SCLP-cc algorithm outperformed the Label Propagation Partitioning algorithm from the hyperX framework in terms of balance and cut size. Our Gravity Expansion algorithm outperformed hMetis when creating many subgraphs. In addition, it outperformed the publicly available version of Hype in terms of the cut size on some input graphs. Summarized, we provide new approaches for label propagation partitioning algorithms to increase the balancing. Further, we created a novel scalable partitioning algorithm which introduces the field of visualization algorithms to the partitioning problem.

Das Hypergraph-Modell ist eine Verallgemeinerung des Graph-Modells. Hyperkanten verbinden eine beliebige Anzahl an Knoten, anstatt nur zwei wie es beim Graph-Modell der Fall ist. Somit kann das Hypergraph-Modell mehr Datenstrukturen darstellen. Gruppenmitgliedschaften in sozialen Netzwerken oder Gruppenkommunikationen in Sofortnachrichtendiensten können einfach modelliert werden. In den letzten Jahren gewannen sowohl Soziale Netzwerke als auch Sofortnachrichtendienste sehr viel Beliebtheit. Steigende Nutzerzahlen und der somit steigende Datenverkehr führten zu größeren Hypergraphen, die nicht mehr von einer einzelnen Maschine verarbeitet werden können. Daher müssen die Hypergraphen partitioniert werden, wobei ein geringer Kommunikationsoverhead bei der späteren Verarbeitung und gleichmäßige Partitionsgrößen, um effiziente Parallelisierbarkeit zu ermöglichen, benötigt werden. Es gibt bereits viele Partitionsalgorithmen für Hypergraphen, aber diese sind meist in ihrer Parallelisierbarkeit limitiert, die wiederum notwendig ist um riesige Hypergraphen effizient zu verarbeiten. Ein bekanntes parallelisierbares Paradigma ist Label Propagation. Wir entwickelten drei Ansätze basierend auf Label Propagation, die neue Möglichkeiten vorstellen, die Balance der Partitionen zu verbessern und somit die Parallelisierbarkeit verbessern. Namentlich sind dies Credit Label Propagation (CLP), Split Credit Label Propagation (SCLP) und Split Credit Label Propagation-Credit Value Compensation (SCLP-cc). Wir nutzten einen Kreditwert, um das Wachstum der Label-Cluster zu regulieren. Bei einigen Ansätzen modifizierten wir den Umgang mit dem Kreditwert, um zu verhindern, dass einzelne Cluster zu groß werden, indem wir die global verfügbare Menge an Kreditwert regulierten. Zudem entwickelten wir einen neuen Partitionierungsalgorithmus basierend auf Graphvisualisierungsalgorithmen für Hypergraphen namens Gravity Expansion. Dabei werden die Knoten des Hypergraphen zunächst in der Mitte eines zweidimensionalen Raums platziert. Von dort aus expandieren diese in den Raum, wobei verbundene Knoten mittels Barrier Jumps nahe beieinanderbleiben. Nach dem Expandieren werden zwei Gravitationspunkte erstellt, die Knoten in ihrer Nähe absorbieren und den Hypergraphen somit partitionieren. Während der Absorbierungsphase expandieren die Knoten weiter, um auf die bisherige Partitionierung zu reagieren. Der SCLP-cc Algorithmus übertraf den Label Propagation Partitioning Algorithmus aus dem hyperX Framework bezüglich der geschnittenen Hyperkanten und der Balance der Partitionsgrößen. Unser Gravity Expansion Algorithmus übertraf hMEtis wenn besonders viele Partitionen angelegt wurden. Zudem übertraf er bezüglich der geschnittenen Hyperkanten bei einigen Eingabedaten die öffentlich verfügbare Version von HYPE. Zusammengefasst präsentieren wir neue Ansätze im Bereich der Label Propagation Algorithmen, die die Balance der Partitionsgrößen verbessern. Außerdem stellen wir einen neuen skalierbaren Partitionierungsalgorithmus vor, der Visualisierungsalgorithmen auf das Partitionierungsproblem anwendet.