Detailansicht
Engineering NOI-based coarsening algorithms for multilevel graph partitioning
Jakob Niedermüller
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Physik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Computational Science
Betreuer*in
Monika Henzinger
Mitbetreuer*in
Christian Schulz
DOI
10.25365/thesis.70108
URN
urn:nbn:at:at-ubw:1-11164.25078.656873-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Graphpartitionierungsproblem besteht darin einen Graphen in k Blöcke zu
teilen, wobei die Größe des Kantenschnitts minimal sein soll und eine Gleichgewichts-
bedingung in Bezug auf die Blockgröße eingehalten werden muss. Graphpartition-
ierung ist darüber hinaus für viele reale Anwendungen relevant. Beispielsweise
um die Komplexität von Verkehrsnetzen[4, 16] zu reduzieren oder um das parallele
Prozessieren eines bestimmten Graphen zu ermöglichen.
Graphen aus realen Anwendungen, wie sozialen Netzwerke, bestehen oftmals aus
Millionen Knoten und Kanten und sind somit zu groß um eine direkte Lösung zu
berechnen. Darüber hinaus ist das Graphpartitionierungsproblem NP-vollständig
und es existiert dafür kein Näherungsalgorithmus mit konstantem Faktor. Folglich
müssen Heuristiken wie Multilevel-Graphpartitionierung[11] verwendet werden. Ein
solches Multilevel-Graphpartitionierungs-Framework nach modernstem Stand wird
etwa im Karlsruhe High Quality Partitionin (KaHIP) Softwarepaket[11, 27] verwen-
det. Dieses Multilevel-Schema besteht aus drei Hauptphasen. In der Coarsening-
Phase wird der Graph durch das iterative Kontrahieren von Kanten geschrumpft,
während die grobe Struktur des Graphen beibehalten werden soll und ohne dabei
die Größe des Kantenschnitts der letztendlichen Partitionierung zu stark zu beein-
flussen. In der sogenannten Initial Partitioning-Phase ist der Graph bereits klein
genug um direkt partitioniert zu werden. In der Uncoarsening-Phase werden die
zuvor kontrahierten Kanten wieder dekontrahiert.
Wir entwickeln neue Coarsening-Algorithmen, wobei wir KaHIP als Partitionier-
ungs-Framework verwenden. Unsere Coarsening-Methoden bauen auf CAPFOREST
(CF) [21, 22] auf - einem Algorithmus von Nagamochi-Ono-Ibaraki (NOI). CF berech-
net eine Kantenbewertung, die als Heuristik dient um zu entscheiden ob eine Kante
kontrahiert werden kann ohne dabei den minimalen Kantenschnitts zu vergrößern.
Wir beziehen diese Kantenbewertung in ein Coarsening-Schema ein, das wir daher
als NOI-Coarsening bezeichnen. Insgesamt entwickeln wir vier Varianten von NOI-
Coarsening, drei davon kontrahieren direkt basierend auf der Kantenbewertung. Die
vierte Variante basiert auf dem Size-Constraint Label Propagation (SCLaP) Algo-
rithmus[19], inkludiert jedoch die CF-Kantenbewertung.
Wir evaluieren unsere Coarsening-Algorithmen, indem wir die Parameter opti-
mieren und die Algorithmen mit KaHIPs State-of-the-art-Partitionierungsprogramm
vergleichen. Als Benchmark partitionieren wir einen Satz an Sozialen Netzwerk-
und Webgraphen, sowie einen Satz an traditionelleren mehr gitterartigen Graphen
aus technischen und physikalischen Anwendungsbereichen. Wir evaluieren sowohl
Qualität als auch Ausführungszeit. Im Allgemeinen kommen die NOI-Methoden bei
den sozialen Netzwerk- und Webgraphen nicht über die State-of-the-art-Performance
hinaus, sondern fallen eher etwas zurück. Bei Partitionierung mit hohem k-Wert
(k = 64) kommt unsere beste Methode im Median bis auf 8 Prozent Unterschied
heran, was die Schnittqualität betrifft. Auf dem Satz an gitterartigen Graphen
erreichen wir bei der Bipartitionierung State-of-the-art-Performance in Bezug auf
Qualität bei nur halber Ausführungszeit.
Abstract
(Englisch)
The graph partitioning problem asks for dividing a graph into k blocks of vertices
while minimizing the size of the edge cut and while maintaining a balance constraint
on the block size. Graph partitioning is relevant for many real world applications
such as reducing complexity of a traffic network[4, 16] or enabling parallel processing
of a certain graph.
Real world graphs, such as social networks, often count millions of vertices and
edges and are, thus, too large to compute a direct solution. Moreover, the problem
of partitioning a graph exactly is NP complete and no constant factor approximation
algorithms exist. Consequently, heuristics like multilevel graph partitioning[11] are
used. A state-of-the-art multilevel partitioning framework is provided by Karlsruhe
High Quality Partitioning (KaHIP)[11, 27]. This multilevel scheme consists of three
main phases. In the coarsening phase the graph is reduced by iteratively contracting
edges while maintaining the overall structure of the graph and without effecting the
size of the cut of the final partitioning too much. In the initial partitioning phase
the graph is small enough to be directly partitioned. In the uncoarsening phase the
previously contracted edges are uncontracted.
We engineer new coarsening algorithms using KaHIP as a partitioning framework.
Our coarsening methods build on the CAPFOREST (CF)[21, 22] algorithm devel-
oped by Nagamochi-Ono-Ibaraki (NOI). CF calculates an edge rating that acts as a
heuristic to determine whether the eligible edge can be contracted without effecting
the minimum cut size. We incorporate this edge rating into a coarsening procedure,
which we, thus, refer to as NOI-Coarsening. We develop four variants of NOI-
Coarsening. Three of them directly contract edges based on the calculated CF edge
rating. The fourth variant incorporates the CF edge rating into the Size-Constraint
Label Propagation (SCLaP) algorithm[19].
We evaluate our coarsening algorithms by performing parameter tuning and com-
paring them with KaHIP’s state-of-the-art partitioner. For benchmarking we parti-
tion a set containing social network and web graphs as well as a set of more tradi-
tional meshlike graphs from technical and physics applications. We evaluate both,
quality and running time. In general, NOI-Coarsening methods do not improve over
state-of-the-art performance on social networks and web graphs but fall behind to
some degree. On high k partitionings (k = 64) our best method comes as close as a
median 8 percent difference in terms of quality. On the set of rather meshlike graphs
we achieve state-of-the-art bipartitioning at only half the running time.
Schlagwörter
Schlagwörter
(Englisch)
graph partitioning coarsening multilevel graphpartitioning
Schlagwörter
(Deutsch)
Graphpartitionierung Coarsening Multi-Level Graphpartitionierung
Autor*innen
Jakob Niedermüller
Haupttitel (Englisch)
Engineering NOI-based coarsening algorithms for multilevel graph partitioning
Paralleltitel (Deutsch)
Entwicklung von NOI-basierten Algorithmen für Multi-Level Graphpartitionierung
Publikationsjahr
2021
Umfangsangabe
x, 66 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Monika Henzinger
Klassifikation
54 Informatik > 54.80 Angewandte Informatik
AC Nummer
AC16460884
Utheses ID
59942
Studienkennzahl
UA | 066 | 910 | |