The current landscape of balanced graph partitioning is divided into
high-quality but expensive multilevel algorithms and cheaper approaches with
linear running time, such as single-level algorithms and streaming algorithms.
We demonstrate how to achieve the best of both worlds with a \emph{linear time
multilevel algorithm}. Multilevel algorithms construct a hierarchy of
increasingly smaller graphs by repeatedly contracting clusters of nodes. Our
approach preserves their distinct advantage, allowing refinement of the
partition over multiple levels with increasing detail. At the same time, we use
\emph{edge sparsification} to guarantee geometric size reduction between the
levels and thus linear running time.
We provide a proof of the linear running time as well as additional insights
into the behavior of multilevel algorithms, showing that graphs with low
modularity are most likely to trigger worst-case running time. We evaluate
multiple approaches for edge sparsification and integrate our algorithm into
the state-of-the-art multilevel partitioner KaMinPar, maintaining its excellent
parallel scalability. As demonstrated in detailed experiments, this results in
a $1.49\times$ average speedup (up to $4\times$ for some instances) with only
1\% loss in solution quality. Moreover, our algorithm clearly outperforms
state-of-the-art single-level and streaming approaches.

Questo articolo esplora i giri e le loro implicazioni.

Scarica PDF: