Karlsruhe Institute of Technology<EMAIL_ADDRESS>Karlsruhe Institute
of Technology<EMAIL_ADDRESS>The source code and data has
been made available at https://algo2.iti.kit.edu/seemaier/ddeep_mgp/.

###### Acknowledgements.

This work was performed on the HoreKa supercomputer funded by the Ministry of
Science, Research and the Arts Baden-Württemberg and by the Federal Ministry
of Education and Research. This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No. 882500).
. [100]Mathematics of computing Graph algorithms

# Distributed Deep Multilevel Graph Partitioning

Peter Sanders  Daniel Seemaier

###### Abstract

We describe the engineering of the distributed-memory multilevel graph
partitioner dKaMinPar. It scales to (at least) 8192 cores while achieving
partitioning quality comparable to widely used sequential and shared-memory
graph partitioners. In comparison, previous distributed graph partitioners
scale only in more restricted scenarios and often induce a considerable
quality penalty compared to non-distributed partitioners. When partitioning
into a large number of blocks, they even produce infeasible solution that
violate the balancing constraint. dKaMinPar achieves its robustness by a
scalable distributed implementation of the deep-multilevel scheme for graph
partitioning. Crucially, this includes new algorithms for balancing during
refinement _and_ coarsening.

###### keywords:

algorithms, distributed systems, graph partitioning, multilevel algorithm,
balancing

##  1 Introduction

Graphs are a central concept of computer science used whenever we need to
model relations between objects. Consequently, handling _large_ graphs is very
important for parallel processing. This often requires to _partition_ these
graphs into blocks of approximately equal weight with most edges inside the
blocks (balanced graph partitioning). Applications include scientific
computing, handling social networks, route planning, and graph databases [4].

In principle, _multilevel graph partitioners_ (MGP) achieve high quality
partitions for a wide range of input graphs $G$ with a good trade-off between
quality and partitioning cost. They are based on first iteratively
_coarsening_ $G$ by contracting edges or small clusters. The resulting small
graph $G^{\prime}$ is then still a good representation of the overall input
and an _initial partition_ of $G^{\prime}$ already induces a good partition of
$G$. This is further improved by _uncoarsening_ the graph and improving the
partition on each level through refinement algorithms.

However, parallelizing multi-level graph partitioning has proved challenging
over several decades. While shared-memory graph partitioners have recently
matured to achieve high quality and reasonable scalability [16, 2, 11, 12],
current distributed-memory partitioners [23, 15, 28] induce a severe quality
deterioration and often are not able to consistently achieve feasible (i.e.
balanced) partitions. In particular, high quality partitioners do not scale to
the number of processing elements (PEs) available in large supercomputers.
This situation is exacerbated by the fact that often the number of blocks $k$
should increase linearly in the number of PEs. Previous systems are not able
to directly handle large $k$ running into even larger problems with achieving
feasibility.

In this paper, we present dKaMinPar which addresses all these issues. Its
basis is a distributed-memory adaptation of the deep-multilevel graph
partitioning concept [11] that continues the multilevel approach deep into the
initial partitioning phase. This makes the large $k$ case much easier and
eliminates a parallelization bottleneck due to initial partitioning. Our
coarsening and refinement algorithms are based on the label propagation
approach previously used in several partitioners [23, 28, 15]. Label
propagation [24, 22] greedily moves vertices to other clusters/blocks when
this reduces cuts (and does not violate the balance constraint). This is
simple, fast, effective and robust even for complex networks. We develop a
distributed-memory version with improved scalability, e.g., by using improved
sparse-all-to-all primitives. Perhaps the main algorithmic innovation are new
scalable distributed techniques allowing to maintain the balance constraint.
During coarsening, a maximum cluster weight is approximated by unwinding
contractions that lead to overweight clusters. During uncoarsening, block
weight constraints are achieved by finding, selecting and applying globally
“best” block moves.

The experiments described in Section 6 indicate that our implementation has
achieved the main goals. It scales to at least 8 192 cores even for complex
networks that did not scale on previous distributed solvers. Feasibility is
guaranteed, even for large $k$ and quality is typically within a few percent
of the shared-memory systems. Section 7 summarizes the results and discusses
possible future improvements.

### Contributions

  * •

Scalable distributed implementation of deep multilevel graph partitioning.

  * •

Simplicity using label propagation for both contraction and refinement.

  * •

New scalable balanced coarsening and uncoarsening algorithm.

  * •

Extensive evaluation on both large real world networks and huge synthetic
networks from 3 input families.

  * •

Quality comparable to shared-memory systems.

  * •

Scalability up to (at least) $2^{13}$ cores and $2^{39}$ edges.

  * •

Works both for complex networks and large number of blocks where previous
systems often fail.

##  2 Preliminaries

#### Notation and Definitions.

Let $G=(V,E,c,\omega)$ be an undirected graph with vertex weights
$c:V\rightarrow\mathbb{N}_{>0}$, edge weights
$\omega:E\rightarrow\mathbb{N}_{>0}$, $n\coloneqq\lvert V\rvert$, and
$m\coloneqq\lvert E\rvert$. We extend $c$ and $\omega$ to sets, i.e.,
$c(V^{\prime})\coloneqq\sum_{v\in V^{\prime}}c(v)$ and
$\omega(E^{\prime})\coloneqq\sum_{e\in E^{\prime}}\omega(e)$.
$N(v)\coloneqq\\{u\mid\\{u,v\\}\in E\\}$ denotes the neighbors of $v$. For
some $V^{\prime}\subseteq V$, $G[V^{\prime}]$ denotes the subgraph of $G$
induced by $V^{\prime}$. We are looking for _blocks_ of nodes
$\Pi\coloneqq\\{V_{1},\dots,V_{k}\\}$ that partition $V$, i.e.,
$V_{1}\cup\dots\cup V_{k}=V$ and $V_{i}\cap V_{j}=\emptyset$ for $i\neq j$.
The _balance constraint_ demands that for all $i\in\\{1,\dots,k\\}$,
$c(V_{i})\leq
L_{\text{max}}\coloneqq\max\\{(1+\varepsilon)\frac{c(V)}{k},\frac{c(V)}{k}+\max_{v}c(v)\\}$
for some imbalance parameter $\varepsilon$111Traditionally,
$L_{k}\coloneqq(1+\varepsilon)\lceil\frac{c(V)}{k}\rceil$ is used as balance
constraint. We relax this constraint since it is otherwise NP-complete to find
a feasible partition.. The objective is to minimize
$\text{cut}(\Pi)\coloneqq\sum_{i<j}\omega(E_{ij})$ (weight of all cut edges),
where $E_{ij}\coloneqq\\{\\{u,v\\}\in E\mid u\in V_{i}\text{ and }v\in
V_{j}\\}$. We call a vertex $u\in V_{i}$ that has a neighbor in $V_{j}$,
$i\neq j$, a _boundary vertex_. A _clustering_
$\mathcal{C}\coloneqq\\{C_{1},\dots,C_{\ell}\\}$ is also a partition of $V$,
where the number of blocks $\ell$ is not given in advance (there is also no
balance constraint).

#### Machine Model and Input Format.

The distributed memory model used in this work considers $P$ processing
elements (PEs) numbered $1..P$, connected by a full-duplex, single ported
communication network. The input graph is given with a (usually balanced) 1D
vertex partition. Each PE is given a subgraph of the input graph (i.e., a
block of the 1D partition) with consecutive vertices. An undirected edge
$\\{u,v\\}$ is represented by two directed edges $(u,v)$, $(v,u)$, which are
stored on the PEs owning the respective tail vertices. Vertices adjacent to
vertices owned by other PEs are called _interface vertices_ and are replicated
as _ghost vertices_ (i.e., without outgoing edges) on those PEs.

##  3 Related Work

There has been a huge amount of research on graph partitioning so that we
refer the reader to overview papers [3, 27, 4, 5] for most of the general
material. Here, we focus on parallel algorithms for high-quality graph
partitioning.

#### Distributed Graph Partitioning.

Virtually all high-quality partitioners are based on the multilevel paradigm,
e.g., ParMETIS [15, 14], ParHIP [23, 26] and others [30, 6]. These algorithms
partition a graph in three phases. First, they build a hierarchy of
successively coarse approximations of the input graph, usually by contracting
matchings or clusters. Once the graph has only few vertices left (e.g., $n\leq
Ck$ for some _contraction limit_ $C$), the graph is partitioned into $k$
blocks. Finally, this partition is successively projected onto finer levels of
the hierarchy and refined using local search algorithms.

The performance of multilevel algorithms is defined by the algorithmic
components used for these phases. Partitioners designed for mesh-partitioning
usually contract matchings to coarsen the graph [15, 30, 6]. However, this
technique is not suitable for partitioning complex networks that only admit a
small maximum matching. Thus, other partitioners use two-hop matchings [17] or
size-constrained label propagation [11, 13, 23]. Due to its simple yet
effective nature, the latter is also commonly used as a local search algorithm
during refinement [23, 15, 11, 13, 2, 30, 8].

Label propagation has also been used by non-multilevel graph partitioning
algorithms such as XtraPuLP [28], which reports scalability up to $2^{17}$
cores, a level which has not been reached by multilevel algorithms. However,
using label propagation without the multilevel paradigm comes with a
pronounced decline in quality; Ref. [11] reports edge cuts for PuLP [29] (non-
multilevel) that are on average more than twice as large and those of KaMinPar
(multilevel). Across a large and diverse benchmark set, this is considered a
lot; most multilevel algorithms achieve average edge cuts within a few
percentage points of each other.

Another class of highly scalable graph partitioners include geometric
partitioners, which work on a geometric embedding of the graph. While these
algorithms are orders of magnitude faster than multilevel algorithms [19],
they generally compute larger edge cuts and only work on graphs with a
meaningful geometric embedding.

#### Deep Multilevel Graph Partitioning.

As plain MGP algorithms usually shrink the graph down to $Ck$ vertices, large
values for $k$ break the assumption that the coarsest graph is small. This
causes their performance to deteriorate [11]. Instead, recursive
bipartitioning can be used to compute partitions with large $k$, but this
induces an additional $\log k$ factor in running time and makes it more
difficult to compute balanced partitions due to the lack of global view. _Deep
multilevel graph partitioning_ (deep MGP) [11] circumvents these problems by
continuing coarsening deep into initial partitioning. More precisely, deep MGP
coarsens the graph until only $2C$ vertices are left, independent of $k$.
Hereby, parallelism is exploited by maintaining the invariant that each PE
processes at least $C$ vertices, which is ensured by replicating coarser
graphs and splitting the available PEs whenever the invariant would be
violated. After bipartitioning the coarsest graphs, it maintains the invariant
that a (coarse) graph with $n$ vertices is partitioned into $\min\\{k,n/C\\}$
blocks by using recursive bipartitioning on the current level. By using
additional balancing techniques, partitioners based on deep MGP can obtain
feasible high-quality partitions with a large number of blocks (e.g.,
$k\approx 1M$) while often being an order of magnitude faster than
partitioners based on plain MGP. Compared to recursive bipartitioning the
entire graph, it reduces the additional $\log k$ factor to $\log kC/n$.
KaMinPar [11] is a scalable shared-memory implementation of deep MGP which
uses size-constrained label propagation during coarsening and refinement.

##  4 Distributed Deep Multievel Graph Partitioning

We introduce dKaMinPar, a distributed graph partitioner based on deep MGP. We
first describe the distributed deep MGP scheme itself, simplified by assuming
that $k$ and $P$ are powers of two. Then, we outline the building blocks for
coarsening, initial partitioning, refinement and balancing implemented in
dKaMinPar.

#### Distributed Deep Multilevel Graph Partitioning.

Figure 1: Distributed deep multilevel graph partitioning on $P=4$ PEs.
Unpartitioned graphs are labeled with their number of vertices, partitioned
graphs are labeled with their number of blocks. Blocks are subdivided into
$K=2$ blocks, and the goal is to partition to graph into $k=4$ blocks.

Input: $G=(V,E)$, $k$, const. $C,K$

Output: $k$-way partition $\Pi$ of $G$

1 if  _$\lvert V(G)\rvert >C\cdot\min\\{k,K\\}$_ then // deep coarsening

2 if  _$\lvert V(G)\rvert <C\cdot P$_ then // duplicate graph if too small for
$P$ PEs

3 $c\coloneqq P/\mathrm{ceil}_{2}(\lvert V(G)\rvert/C)$ // number of copies

4 $G\coloneqq\textnormal{{Replicate}}(G,c)$ // replicate graph $c$ times and
group PEs

5 $P\coloneqq P/c$ // number of PEs per group

6

// standard multilevel graph partitioning:

7 $G_{c}\coloneqq\textnormal{{Coarsen}}(G)$

8 $\Pi_{c}\coloneqq\textnormal{{DeepMGP}}(G_{c},k,P)$

9 $\Pi\coloneqq\textnormal{{Project}}(G,\Pi_{c})$

10 $\Pi\coloneqq\textnormal{{BalanceAndRefine}}(G,\Pi)$

11

12else // base case

13 $\Pi\coloneqq\\{V\\}$ // trivial $1$-way partition

14

15$k^{\prime}\coloneqq\min\\{k,\textrm{ceil}_{2}(\lvert V\rvert/C)\\}$

16 while  _$\lvert\Pi\rvert <k^{\prime}$_ do // extend partition

17
$G^{\prime}_{1},\dots,G^{\prime}_{\lvert\Pi\rvert/P}\coloneqq\textnormal{{DistributeBlocks}}(G,\Pi)$
// $G^{\prime}_{i}$s are local graphs

// partition each local graph into $\min\\{k^{\prime}/\lvert\Pi\rvert,K\\}$
blocks:

18 for  _$i\coloneqq 1$ to $\lvert\Pi\rvert/P$_ do

19
$\Pi^{\prime}_{i}\coloneqq\textnormal{{LocalPartitioning}}(G^{\prime}_{i},\min\\{k^{\prime}/\lvert\Pi\rvert,K\\})$

20

// combine local partitions $\Pi^{\prime}_{i}$ of $G^{\prime}_{i}$ to global
partition $\Pi$ of $G$:

21
$\Pi\coloneqq\textnormal{{CollectPartitions}}(\Pi^{\prime}_{1},\dots,\Pi^{\prime}_{\lvert\Pi\rvert/P})$

22 $\Pi\coloneqq\textnormal{{BalanceAndRefine}}(G,\Pi)$

23

return _$\Pi$_

Algorithm 1 $\textnormal{{DeepMGP}}(G,k,P)$: Deep multilevel with $k$ blocks
on $P$ PEs.

We outline the partitioning scheme in Figure 1 and Algorithm 1. Distributed
deep MGP starts by coarsening the input graph down to $K\cdot C$ vertices,
building a hierarchy of successively coarse graphs $G_{1},\dots,G_{\ell}$
(Figure 1, left, and Algorithm 1, lines 1–1). Here, $C$ is the _contraction
limit_ and $K$ is a tuning parameter that generalizes the bipartitioning steps
from Ref. [11] to $K$-way partitioning. To improve scalability on coarse
levels, we follow Ref. [30] and maintain the invariant that $P$ PEs work on a
graph with at least $P\cdot C$ vertices by splitting the PEs into groups and
duplicating the current graph whenever this invariant would be violated
otherwise (lines 1–1). Once coarsening converged, we gather the coarsest graph
$G_{\ell}$ on all PEs and partition it into $\min\\{k,K\\}$ blocks using a
non-distributed graph partitioner (Figure 1, middle). The best partition
(within each group of PEs) is selected and projected onto $G_{\ell-1}$. From
here, we maintain two invariants: (1) the current partition is feasible, which
is ensured by using the distributed balancing algorithm described below, and
(2) a graph with $n_{\ell}$ vertices is partitioned into
$\min\\{k,\textrm{ceil}_{2}(n_{\ell}/C)\\}$ blocks. Here,
$\textrm{ceil}_{2}(x)$ denotes the smallest power of $2$ equal to or larger
than $x$. The second invariant is maintained using recursive $K$-way
partitioning. More precisely, whenever the invariant is violated, we extract
the block-induced subgraphs of the current partition and gather them on PEs
such that each PE receives $k/P$ complete subgraphs (note that $k\geq P$ due
to the duplication process described above). From there, we use a non-
distributed graph partitioner to recursively partition the subgraphs and
project the new partitions back onto the distributed graph. This process is
illustrated by Algorithm 1, lines 1–1. The resulting partition, satisfying
both invariants, is then improved using a distributed $k$-way refinement
algorithm. Note that if $k>\textrm{ceil}_{2}(\lvert V(G_{1})\rvert/C)$, the
partition computed on the finest graph has not enough blocks. In this case, we
distribute and partition the block-induced subgraphs once more to compute the
missing blocks (omitted from Algorithm 1).

#### Coarsening.

We use a similar parallelization of size-constrained label propagation as
ParHIP [23] and KaMinPar [11]. The algorithm works by first assigning each
vertex to its own cluster. In further iterations over the vertices (we use
$\\{3,5\\}$ iterations), they are then moved to adjacent clusters such that
the weight of intra-cluster edges is maximized without violating the maximum
cluster weight $W\coloneqq\varepsilon\frac{c(V)}{k^{\prime}}$ where
$k^{\prime}\coloneqq\min\\{k,\lvert V\rvert/C\\}$ [11].

As noted in Ref. [22, 2], the solution quality of label propagation is
improved when iterating over vertices in increased degree order. Since this is
not cache efficient and lacks diversification by randomization, we sort the
vertices into exponentially spaced degree buckets, i.e., bucket $i$ contains
all vertices with degree $2^{i}\leq d<2^{i+1}$, and rearrange the input graph
accordingly. This happens locally on each PE, i.e., we do not sort the
vertices globally. Then, during label propagation, we split buckets into small
chunks and randomize traversal on a inter-chunk and intra-chunk level. This is
analogous to the randomization of the matching algorithm used by Metis [14].

To communicate the current cluster assignment of interface vertices, we follow
ParHIP and split each iteration into $\max\\{\alpha,\beta/P\\}$ (we use
$\alpha=8$, $\beta=128$) batches. After each batch, we use a sparse all-to-all
operation to notify adjacent PEs of interface vertices that were moved to a
different cluster. Since clusters can span multiple PEs, enforcing the maximum
cluster weight becomes more challenging than in a shared-memory setting.
ParHIP relaxes the weight limit and only enforces it locally, i.e., allows
clusters with weight up to $P\cdot W$. This can lead to very heavy coarse
vertices, making it more difficult to compute balanced partitions. Instead, we
track the global cluster weights by sending the change in cluster weight after
each batch to the PE owning the initial vertex of the cluster, which
accumulates the changes and replies with the total weight of the cluster. If a
cluster becomes heavier than $W$, each PE reverts moves proportional to its
part of the total cluster weight. Those vertices can then be moved to other
clusters during the next iteration.

After clustering the graph, we contract all clusters to build the next graph
in the hierarchy. We give more details on this operation in Section 5.

#### Refinement.

We also use size-constrained label propagation to improve the current graph
partition. In contrast to label propagation for clustering as described above,
vertices are initially assigned to clusters representing the blocks of the
partition, and the maximum block weight is used as weight constraint. We use
the same iteration order and number of batches as during coarsening to move
vertices to adjacent blocks such that the weight of intra-block edges is
maximized without violating the balance constraint. Ties are broken in favor
of the lighter block, or by coin flip if both blocks have the same weight.

Since the number of blocks during refinement is usually much smaller than the
number of clusters during coarsening, we track the global block weights using
an allreduce operation after each vertex batch. Note that this does not
prevent violations of the balance constraint if multiple PEs move vertices to
the same block during the same vertex batch. In this case, we use our global
balancing algorithm described below afterwards to restore the balance
constraint. This is a downside compared to refinement via size-constrained
label propagation in shared-memory parallel graph partitioners, where the
balance constraint can be strictly enforced using atomic compare-and-swap
operations.

#### Balancing.

As noted in Ref. [11], balance constraint violations during deep MGP can occur
after initial partitioning or after projecting a coarse graph partition onto a
finer level of the graph hierarchy. Since these balance constraint violations
are bounded by the weight of the heaviest vertex, we design the following
balancing algorithm following the assumption that only few vertex moves are
necessary to restore balance and that thus, it is feasible to invest a
moderate amount of work per vertex movement. The greedy algorithm works as
follows.

For each overloaded block $B$, we maintain a priority queue $P_{B}$ of local
vertices of that block on each PE. The vertices in the priority queues are
ordered by their _relative gain_ , which we define as $g\cdot c(v)$ if $g\geq
0$ and $g/c(v)$ if $g<0$, where $g$ is the largest reduction in edge cut when
moving $v$ to a block that would not become overloaded. Note that this rating
function generally prefers to move few heavy vertices over moving many lighter
vertices, which follows our assumption that few vertex moves are sufficient to
balance the partition. To keep the priority queues small, we maintain the
invariant that a priority queue $P_{B}$ stores no more vertices than are
necessary to remove all excess weight $o(B)\coloneqq c(B)-L_{\text{max}}$ from
$B$. We initialize the priority queues by iterating over the vertices. If a
vertex is in an overloaded block $B$ and $c(P_{B})<o(B)$, we insert it.
Otherwise, we only insert the vertex if its relative gain is larger than the
lowest relative gain of any vertex in $P_{B}$ and remove its lowest vertex if
$c(P_{B})>o(B)+\max_{v}c(v)$ after insertion.

After initializing the priority queues, we use a binary tree reduction to
repeatedly identify the $\ell$ highest scored vertices per block globally, for
some constant input parameter $\ell$. For each overloaded block, each PE
contributes up to $\ell$ vertices from its local priority queue. At each level
of the reduction tree, the two lists of size $\leq\ell$ are then merged and
cut off after at most $\ell$ vertices, or sooner if a shorter prefix is
sufficient to remove all excess weight from the corresponding block. The root
PE then decides which moves to perform such that no block becomes overloaded
and broadcasts its decision to all PEs. Using this information, PEs remove
vertices that were moved from their priority queues and update the relative
gain of neighbors of moved vertices. We repeat this process until the
partition is balanced.

##  5 Implementation Details

#### Vertex and Edge IDs.

To reduce the communication overheads, we distinguish between local- and
global vertex- and edge identifiers. This allows us to use
$64\text{\,}\mathrm{b}\mathrm{i}\mathrm{t}$ data types for global and
$32\text{\,}\mathrm{b}\mathrm{i}\mathrm{t}$ data types for local IDs.

#### Graph Contraction.

Contracting a clustering consisting of $n_{C}$ clusters and constructing the
corresponding coarse graph works as follows. First, the clustering algorithm
described above assigns a cluster ID to each vertex, which corresponds to some
vertex ID in the distributed graph. We say that a cluster is _owned_ by the PE
owning the corresponding vertex. After contracting the local subgraphs (i.e.,
deduplicating edges between clusters and accumulating vertex- and edge
weights), we map clusters to PEs such that each PE gets roughly the same
number of coarse vertices while attempting to minimize the required
communication amount. We assign $\leq\delta\cdot n_{C}/P$ clusters owned by
each PE to the same PE (in our experiments, $\delta=1.1$). If a PE owns more
clusters, we redistribute the remaining clusters to PEs that have the smallest
number of clusters assigned to them. Afterwards, each PE sends outgoing edges
of coarse vertices to the respective PE using an all-to-all operation, then
builds the coarse graph by deduplicating edges and accumulating vertex- and
edge weights.

#### Low-latency Sparse All-to-All.

Many steps of dKaMinPar require communication along the cut edges of the
distributed graph, which translates to (often very) sparse and irregular all-
to-all communication. Since MPI_Alltoallv has relatively high latency, we
instead use a two-level approach that arranges PEs in a grid [25]. Then,
messages are first sent to the right row, then to the right column, reducing
the total number of messages send through the network from
$\mathcal{O}(P^{2})$ to $\mathcal{O}(P)$.

##  6 Experiments

We implemented the proposed algorithm dKaMinPar in C++ and compiled it using
g++-12.1 with flags -O3 -march=native. We use OpenMPI 4.0 as parallelization
library and growt [21] for hash tables. The raw data of all experiments is
available online222https://algo2.iti.kit.edu/seemaier/ddeep_mgp/.

#### Setup.

We evaluate the solution quality of our algorithm on a shared-memory machine
equipped with $1\text{\,}\mathrm{T}\mathrm{B}$ of main memory and one AMD EPYC
7702P processor with 64 cores (Machine A). Additionally, we perform
scalability experiments on a high-performance cluster where each compute node
is equipped with $256\text{\,}\mathrm{G}\mathrm{B}$ of main memory and two
Intel Xeon Platinum 8368 processors (Machine B). The compute nodes are
connected by an InfiniBand 4X HDR
$200\text{\,}\mathrm{G}\mathrm{B}\mathrm{i}\mathrm{t}\mathrm{/}\mathrm{s}$
network with approx. $1\text{\,}\mathrm{\SIUnitSymbolMicro}\mathrm{s}$
latency. We only use 64 out of the available 78 cores since some of the graph
generators require the number of cores to be a power of two. While our
partitioner can use multiple threads per MPI process, we only evaluate the
configuration with one thread per MPI process, since this usually gives the
best performance.

We compare dKaMinPar against the distributed versions of the algorithms
included in Ref. [11], i.e., ParHIP [23] (v3.14) and ParMETIS [15] (v4.0.3).
We do not include the distributed version PuLP [29] (XtraPuLP [28]) in our
main comparison, since its quality is not competitive with multilevel
partitioners. Instead, a comparison against XtraPuLP is available in Section
12. We evaluate two configurations of our algorithm: dKaMinPar-Fast uses
$C=2000$ as contraction limit (same as in Ref. [11]), KaMinPar [11] for
initial partitioning and performs 3 iterations of label propagation during
coarsening, whereas dKaMinPar-Strong uses $C=5000$ (same as in Ref. [23]), Mt-
KaHyPar [13] for initial partitioning and 5 iterations of label propagation
during coarsening.

#### Instances.

We evaluate our algorithm on the graphs from benchmark set B of Ref. [11] and
the graphs used in Ref. [23]. A list of all graphs is available in Table 1,
Section 8. Additionally, we use the graph generator KaGen [10] to evaluate the
scaling capabilities of our algorithm on huge randomly generated 2D and 3D
geometric and hyperbolic graphs denoted
$\textsf{rgg}_{\textrm{2D}}N\textrm{d}D$,
$\textsf{rgg}_{\textrm{3D}}N\textrm{d}D$ and $\textsf{rhg}_{3.0}N\textrm{d}D$.
These graphs have $2^{N}$ vertices per compute node (64 cores) and average
degree $D$. The random hyperbolic graphs have power-law exponent $3$. The
largest graphs of these families have $2^{33}$ vertices and $2^{39}$ edges.

#### Methodology.

We call a combination of a graph and the number of blocks an _instance_. For
each instance, we perform 5 repetitions with different seeds and aggregate the
edge cuts and running times using the arithmetic mean. To aggregate over
multiple instances, we use the geometric mean.

To compare the solution quality of different algorithms, we use _performance
profiles_ [9]. Let $\mathcal{A}$ be the set of algorithms we want to compare,
$\mathcal{I}$ the set of instances, and $q_{A}(I)$ the quality of algorithm
$A\in\mathcal{A}$ on instance $I\in\mathcal{I}$. For each algorithm $A$, we
plot the fraction of instances
$\frac{\lvert\mathcal{I}_{A}(\tau)\rvert}{\lvert\mathcal{I}\rvert}$ ($y$-axis)
where $\mathcal{I}_{A}(\tau)\coloneqq\\{I\in\mathcal{I}\mid
q_{A}(I)\leq\tau\cdot\min_{A^{\prime}\in\mathcal{A}}q_{A^{\prime}}(I)\\}$ and
$\tau$ is on the $x$-axis. Achieving higher fractions at lower $\tau$-values
is considered better. For $\tau=1$, the $y$-value indicates the percentage of
instances for which an algorithm performs best.

#### Solution Quality and Running Time.

Figure 2: Results for $k=\\{2,4,8,16,32,64,128\\}$ with $\varepsilon=3\%$ on
Machine A. From left to right: (a) edge cuts of dKaMinPar-Fast, ParHIP-Fast
and ParMETIS, (b) edge cuts of dKaMinPar-Fast, dKaMinPar-Strong and ParHIP-
Eco, (c) running times of all algorithms. The numbers above the x-axis are
geometric mean running times [s] over all instances for which all algorithms
produced a result. Timeouts are marked with 🕒, failed runs or infeasible
results are marked with $\times$.

We evaluate the quality and running time of dKaMinPar against competing
distributed MGP algorithms using all 64 cores of Machine A. Here, we partition
the graphs of our benchmark set into $k\in\\{2,4,8,16,32,64,128\\}$ blocks
with $\varepsilon=3\%$. To gain insights into the performance penalties of
dKaMinPar due to its distributed nature, we also include a comparison against
the shared-memory partitioner KaMinPar. Additionally, we report results for
$k\in\\{2^{11},2^{14},2^{17},2^{20}\\}$ (_large_ $k$) in Section 9. We set the
time limit for a single instance to one hour, which is approx. 10 times the
running time of dKaMinPar-Fast for small $k$ on most instances333Only
twitter-2010 takes $6\text{\,}\mathrm{min}$ resp. $7\text{\,}\mathrm{min}$ for
$k=64$ resp. $k=128$..

The results are summarized in Figure 2a–c. In Figure 2a, we can see that
dKaMinPar-Fast finds the lowest edge cuts on approx. 60% of all benchmark
instances, whereas ParMETIS and ParHIP-Fast only find better edge cuts on
approx. 30% resp. 10% of all instances. Moreover, both competing algorithms
frequently fail to compute feasible partitions — in particular, ParMETIS is
unable to partition most social networks, violating the balance constraint or
crashing on 34% of all instances. When looking at running times (Figure 2c),
we therefore only average over those instances for which all partitioners
computed a feasible partition or ran into the timeout (145 out of 224
instances). dKaMinPar-Fast ($4.93\text{\,}\mathrm{s}$ geometric mean running
time) is 1.4 and 3.4 times faster than ParMETIS ($6.98\text{\,}\mathrm{s}$)
and ParHIP-Fast ($16.77\text{\,}\mathrm{s}$), respectively. We attribute this
to several reasons. Compared to ParMETIS, the lower running time is due to
faster shrinkage of complex networks, while the advantage over ParHIP-Fast is
due to our more cache-efficient implementation of label propagation, more
efficient graph contraction and the low-latency sparse all-to-all
implementation described in Section 5.

ParHIP also offers a strong configuration ParHIP-Eco, which performs more
V-cycles and uses an evolutionary algorithm for initial partitioning to
produce significantly better edge cuts at the cost of a much higher running
time. In Figure 2b, we show that dKaMinPar can achieve the same solution
quality when using the dKaMinPar-Strong configuration described above, while
still being faster than ParHIP-Fast.

Figure 3: Results for $k=\\{2,4,8,16,32,64,128\\}$ with $\varepsilon=3\%$ on
Machine A. From left to right: (a) edge cuts of dKaMinPar-Fast and KaMinPar,
(b) corresponding running times. The numbers above the x-axis are geometric
mean running times [s].

Finally, we compare out distributed partitioner against KaMinPar, which is a
shared-memory implementation of deep multilevel graph partitioning with label
propagation for coarsening and refinement. The results are summarized in
Figure 3. The edge cut quality of both partitioners is almost the same, with a
difference in average edge cut computed of less than 0.5%. However, the
distributed partitioner is approx. 50% slower than the shared-memory
partitioner. This is expected, as communication through message passing is
generally less efficient than shared-memory communication.

#### Weak Scalability of dKaMinPar.

Figure 4: Throughput of $\textsf{rgg}_{\textrm{2D}}$,
$\textsf{rgg}_{\textrm{3D}}$ and rhg graphs with $2^{26}$ vertices per compute
node, average degree $\in\\{8,32\\}$, $k=16$ and $\varepsilon=3\%$ on 64–8 192
cores of Machine B.

We evaluate the weak scalability of dKaMinPar using 64–8 192 cores (i.e.,
1–128 compute nodes) of the high-performance cluster Machine B. For benchmark
instances, we use randomly generated geometric (2D and 3D) and hyperbolic
graphs with $2^{26}$ vertices per compute node and average degree
$\in\\{8,32\\}$.

In Figure 4, we partition these graphs into $k=16$ blocks and observe weak
scalability for dKaMinPar-Fast all the way to 8 192 cores on all three graph
families. On the geometric graphs, we achieve similar throughputs to ParMETIS,
while ParHIP-Fast shows a drop in scalability beyond 2 048 cores. This is most
likely due to the extensive and inefficient communication performed by ParHIP-
Fast during graph contraction. Moreover, we note that ParHIP-Fast was
originally designed to overlap local work and global communication during
label propagation through the use of nonblocking MPI operations. This
implementation relies on MPI progression threads, which seem to be unavailable
in modern OpenMPI versions. ParMETIS shows significantly worse throughputs on
random hyperbolic graphs and is unable to compute a partition on 8 192 cores.
As mentioned before, this is most likely due to its inefficient coarsening
strategy on graphs that follow a power-law degree distribution.

Looking at edge cuts (Table 3 in Section 10, upper half), ParMETIS finds lower
edge cuts than dKaMinPar-Fast on the dense
$\textsf{rgg}_{\textrm{2D}}26\textrm{d}32$ graph and both
$\textsf{rgg}_{\textrm{3D}}$ graphs by 5%–13%. However, on the sparser
$\textsf{rgg}_{\textrm{2D}}26\textrm{d}8$ graph, dKaMinPar-Fast has 19%
smaller cuts than ParMETIS which is already a considerable improvement. The
gap gets much larger for the hyperbolic graph where ParMETIS only finds
approx. 5.5–6.1 times larger cuts. Such solutions will be unsuitable for many
applications.

Figure 5: Throughput of rgg2D, rgg3D and rhg graphs with $2^{26}$ vertices per
compute node, average degree $8$, and $\varepsilon=3\%$ on 64–8 192 cores of
Machine B. The number of blocks are scaled with the size of the graph such
that each block contains $2^{12}$ or $2^{15}$ vertices.

We now evaluate weak scalability in terms of graph size _and_ number of blocks
by scaling $k$ with the number of compute nodes used. This implies that the
number of blocks is large when using a large number of cores. The throughput
of each algorithm in this setting is summarized in Figure 5. Note that we only
use the sparser graphs in this experiment, since ParMETIS and ParHIP are
unable to partition the dense versions of the graphs even on few compute
nodes.

ParHIP-Fast is unable to obtain a feasible partition on all but 6 instances,
none of which uses more than 1 024 cores, and only shows increasing
throughputs up to 256 cores. While ParMETIS achieves decent weak scalability
and computes feasible solutions on the mesh-type graphs, it is unable to
partition any graph on 8 192 cores and often crashes on fewer cores (e.g., it
only works on up to 1 024 cores on $\textsf{rgg}_{\textrm{2D}}$ with $2^{12}$
vertices per block). On the random hyperbolic graph, it only computes a
feasible solution on 64 cores. Meanwhile, dKaMinPar-Fast shows weak
scalability up to 8 192 cores _on every graph family_ , although it should be
noted that the throughput increase from 4 096 to 8 192 is rather small.

In terms of number of edges cut, we summarize that dKaMinPar finds on average
19.3% and 2.8% lower edge cuts than ParMETIS and ParHIP-Fast, respectively
(only averaging over instances for which the respective partitioner computed a
feasible partition), with improvements ranging from 0% on
$\textsf{rgg}_{\textrm{3D}}26\textrm{d}8$ to approx. 60% on
$\textsf{rhg}_{8}3.0\textrm{d}26$ ($2^{15}$ vertices per block). Detailed per-
instance edge cut results are available in Table 3 (Section 10).

#### Strong Scalability of dKaMinPar.

We now look at strong scalability of dKaMinPar. Here, we partition three of
the largest low- and high-degree graphs from our benchmark set into $k=16$
blocks using 64–8 192 cores of Machine B and a time limit of
$15\text{\,}\mathrm{min}$. The results are summarized in Figure 6, where we
can observe strong scalability for up to 1 024–2 048 cores on high-degree
graphs. ParMETIS is unable to partition these graphs regardless of the number
of cores used. While ParHIP-Fast scales up to 2 048 cores on uk-2007-05, it
should be noted that its running time is still higher than dKaMinPar on just
64 cores. The twitter graph is difficult to coarsen due to its highly skewed
degree distribution; here, we observe that only dKaMinPar can partition the
graph within the time limit.

Turning towards graphs with small maximum degree, we observe strong
scalability for up to 2 048, 2 048 and 1 024 cores on kmer_V1r, nlpkkt240 and
$\textsf{rgg}_{\textrm{2D}}27$, respectively. Other algorithms seem to be
unable to partition kmer_V1r, which ParMETIS is only able to partition on
512–4 096 cores, even though the graph is relatively small and fits into the
memory of a single compute node. ParHIP-Fast is not able to partition the
graph at all. Similar to our weak scaling experiments, ParMETIS shows better
scalability and throughput on the mesh-type graph $\textsf{rgg}_{\textrm{2D}}$
as well as on nlpkkt240.

The edge cuts obtained remain relatively constant (Table 4 in Section 11) when
scaling to large number of cores. Surprisingly, the geometric mean edge cut on
8 192 cores is slightly better than on 64 cores (by 2.0%).

Figure 6: Strong scaling running times for the largest low- and high-degree
graphs in our benchmark set, with $k=16$, $\varepsilon=3\%$ on 64–8 192 cores
of Machine B.

##  7 Conclusion and Future Work

Our distributed-memory graph partitioner dKaMinPar successfully partitions a
wide range of input graphs using many thousands of cores yielding high speed
and good quality. Further improvements of the implementation might be
possible, for example making better use of shared-memory on each compute node.
Beyond that, one can explore the quality versus time trade off. By distributed
implementations of more powerful local improvement algorithms like local
search or flow-based techniques one could achieve better quality at the price
of higher execution time. It then also makes sense to look at a portfolio of
different partitioners variants that can be run in parallel achieving good
quality for subsets of inputs. For example, matching based coarsening as in
ParMETIS might help for mesh-like networks. On the other hand, more aggressive
methods for handling high-degree nodes might help with some social networks.

## References

  * [1] Benchmarking for Graph Clustering and Partitioning. Encyclopedia of Social Network Analysis and Mining, Springer (2014)
  * [2] Akhremtsev, Y., Sanders, P., Schulz, C.: High-Quality Shared-Memory Graph Partitioning. IEEE Trans. Parallel Distributed Syst. 31(11), 2710–2722 (2020)
  * [3] Bichot, C., Siarry, P. (eds.): Graph Partitioning. Wiley (2011)
  * [4] Buluç, A., et al.: Recent Advances in Graph Partitioning. In: Algorithm Engineering — Selected Results and Surveys, LNCS, vol. 9220, pp. 117–158 (2016)
  * [5] Çatalyürek, U.V., et al.: More Recent Advances in (Hyper)Graph Partitioning. ACM Comput. Surv. (2022)
  * [6] Chevalier, C., Pellegrini, F.: PT-Scotch: A Tool for Efficient Parallel Graph Ordering. Parallel Comput. 34(6–8), 318–331 (2008)
  * [7] Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38(1), 1:1–1:25 (2011)
  * [8] Devine, K.D., et al.: Parallel Hypergraph Partitioning for Scientific Computing. In: 20th International Parallel and Distributed Processing Symposium (IPDPS 2006)
  * [9] Dolan, E.D., Moré, J.J.: Benchmarking Optimization Software with Performance Profiles. Math. Program. 91(2), 201–213 (2002)
  * [10] Funke, D., et al.: Communication-free Massively Distributed Graph Generation. J. Parallel Distributed Comput. 131, 200–217 (2019)
  * [11] Gottesbüren, L., et al.: Deep Multilevel Graph Partitioning. In: 29th European Symposium on Algorithms, (ESA) 2021. LIPIcs, vol. 204, pp. 48:1–48:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
  * [12] Gottesbüren, L., Heuer, T., Sanders, P.: Parallel Flow-Based Hypergraph Partitioning. In: 20th International Symposium on Experimental Algorithms (SEA 2022). vol. 233, pp. 5:1–5:21. LIPICS
  * [13] Gottesbüren, L., Heuer, T., Sanders, P., Schlag, S.: Scalable Shared-Memory Hypergraph Partitioning. In: 23rd Workshop on Algorithm Engineering and Experiments (ALENEX 2021). pp. 16–30. SIAM
  * [14] Karypis, G., Kumar, V.: A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Sci. Comput. 20(1), 359–392 (1998)
  * [15] Karypis, G., Kumar, V.: Multilevel $k$-way Partitioning Scheme for Irregular Graphs. J. Parallel Distributed Comput. 48(1), 96–129 (1998)
  * [16] LaSalle, D., Karypis, G.: Multi-threaded Graph Partitioning. In: 27th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS). pp. 225–236 (2013)
  * [17] LaSalle, D., et al.: Improving Graph Partitioning for Modern Graphs and Architectures. In: 5th Workshop on Irregular Applications - Architectures and Algorithms, (IA3) 2015. pp. 14:1–14:4. ACM
  * [18] Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data (2014)
  * [19] von Looz, M., Tzovas, C., Meyerhenke, H.: Balanced k-means for Parallel Geometric Partitioning. In: 47th International Conference on Parallel Processing, (ICPP) 2018. pp. 52:1–52:10. ACM
  * [20] o. M., U.: Laboratory of Web Algorithms. Datasets. http://law.di.unimi.it/datasets.php
  * [21] Maier, T., Sanders, P., Dementiev, R.: Concurrent Hash Tables: Fast and General(?)! ACM Trans. Parallel Comput. 5(4), 16:1–16:32 (2019)
  * [22] Meyerhenke, H., Sanders, P., Schulz, C.: Partitioning Complex Networks via Size-Constrained Clustering. In: Experimental Algorithms - 13th International Symposium, (SEA) 2014. LNCS, vol. 8504, pp. 351–363. Springer
  * [23] Meyerhenke, H., Sanders, P., Schulz, C.: Parallel Graph Partitioning for Complex Networks. IEEE Trans. Parallel Distrib. Syst. 28(9), 2625–2638 (2017)
  * [24] Raghavan, N., Albert, R., Kumara, S.: Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical review. E, Statistical, nonlinear, and soft matter physics 76, 36–106 (2007)
  * [25] Sanders, P., Schimek, M.: Engineering Massively Parallel MST Algorithms. In: 27th IEEE Int. Parallel and Distributed Processing Symposium (IPDPS) (2023)
  * [26] Sanders, P., Schulz, C.: Think Locally, Act Globally: Highly Balanced Graph Partitioning. In: 12th Symposium on Experimental Algorithms, (SEA) 2013
  * [27] Schulz, C., Strash, D.: Graph Partitioning: Formulations and Applications to Big Data. In: Encyclopedia of Big Data Technologies. Springer (2019)
  * [28] Slota, G.M., et al.: Scalable, Multi-Constraint, Complex-Objective Graph Partitioning. IEEE Trans. Parallel Distributed Syst. 31(12), 2789–2801 (2020)
  * [29] Slota, G.M., Madduri, K., Rajamanickam, S.: PuLP: Scalable Multi-Objective Multi-Constraint Partitioning for Small-World Networks. In: 2014 IEEE Int. Conference on Big Data (IEEE BigData 2014). pp. 481–490
  * [30] Walshaw, C., Cross, M.: JOSTLE: Parallel Multilevel Graph-Partitioning Software — An Overview. Mesh Partitioning Techniques and Domain Decomposition Techniques pp. 27–58 (2007)

##  8 Benchmark Instances

Table 1: Basic properties of the benchmark set. Graphs are roughly classified as _low degree_ and _high degree_ graphs based on their maximum degree $\Delta$. | Graph | $n$ | $m$ | $\Delta$ | Ref.
---|---|---|---|---|---
Low-degree graphs | packing | 2 145 839 | 34 976 486 | 18 | [1]
channel | 4 802 000 | 85 362 744 | 18 | [1]
hugebubbles | 19 458 087 | 58 359 528 | 3 | [1]
nlpkkt240 | 27 993 600 | 746 478 752 | 27 | [1]
europe.osm | 50 912 018 | 108 109 320 | 13 | [1]
kmerU1a | 64 678 340 | 132 787 258 | 35 | [7]
$\textsf{rgg}_{\textrm{3D}}26$ | 67 106 449 | 755 904 090 | 34 | [10]
$\textsf{rgg}_{\textrm{2D}}26$ | 67 108 858 | 1 149 107 290 | 45 | [10]
$\textsf{del}_{\textrm{3D}}26$ | 67 108 864 | 1 042 545 824 | 40 | [10]
$\textsf{del}_{\textrm{2D}}26$ | 67 108 864 | 402 653 086 | 26 | [10]
$\textsf{rgg}_{\textrm{3D}}27$ | 134 214 672 | 1 575 628 350 | 36 | [10]
$\textsf{rgg}_{\textrm{2D}}27$ | 134 217 728 | 2 386 714 970 | 46 | [10]
$\textsf{del}_{\textrm{2D}}27$ | 134 217 728 | 606 413 354 | 14 | [10]
$\textsf{del}_{\textrm{3D}}27$ | 134 217 728 | 2 085 147 648 | 40 | [10]
kmerP1a | 138 896 082 | 296 930 692 | 40 | [7]
kmerA2a | 170 372 459 | 359 883 478 | 40 | [7]
kmerV1r | 214 004 392 | 465 409 664 | 8 | [7]
High-degree graphs | amazon | 400 727 | 4 699 738 | 2 747 | [18]
eu-2005 | 862 664 | 32 276 936 | 68 963 | [1]
youtube | 1 134 890 | 5 975 246 | 28 754 | [18]
in-2004 | 1 382 867 | 27 182 946 | 21 869 | [1]
com-orkut | 3 072 441 | 234 370 166 | 33 313 | [18]
enwiki-2013 | 4 203 323 | 183 879 456 | 432 260 | [20]
enwiki-2018 | 5 608 705 | 234 488 590 | 248 444 | [20]
uk-2002 | 18 483 186 | 523 574 516 | 194 955 | [1]
arabic-2005 | 22 743 881 | 1 107 806 146 | 575 628 | [20]
uk-2005 | 39 454 463 | 1 566 054 250 | 1 776 858 | [20]
it-2004 | 41 290 648 | 2 054 949 894 | 1 326 744 | [20]
twitter-2010 | 41 652 230 | 2 405 026 092 | 2 997 487 | [20]
sk-2005 | 50 636 059 | 3 620 126 660 | 8 563 816 | [20]
uk-2007-05 | 105 153 952 | 6 603 753 128 | 975 419 | [1]
webbase-2001 | 115 554 441 | 1 709 619 522 | 816 127 | [20]

##  9 Detailed Results for Large $k$

Table 2: Edge cut and running time results for $k\in\\{2^{10},2^{14},2^{17},2^{20}\\}$ and $\varepsilon=3\%$ on Machine A. The gmean imbalance of infeasible solutions is shown next to the number of infeasible solutions. The last two columns _rel. time_ and _rel. cut_ show the gmean running times and edge cuts relative to dKaMinPar-Fast of all instances for which the respective algorithm does not crash (timeout instances are additionally excluded in edge cut comparisons). Algorithm | # timeout | # crash | # infeasible | # feasible | rel. time | rel. cut
---|---|---|---|---|---|---
dKaMinPar-Fast | 0 | 0 | 0 | 128 | 1.00 | 1.00
ParHIP-Fast | 6 | 48 |  57 (1.19) | 17 | 22.21 | 1.06
ParHIP-Eco | 39 | 40 |  37 (1.10) | 12 | 88.35 | 0.96
ParMETIS | 0 | 44 |  54 (1.18) | 30 | 2.38 | 1.01
KaMinPar | 0 | 0 | 0 | 128 | 0.46 | 0.98

As can be seen in Table 2, only partitioners based on (distributed) deep MGP
consistently compute feasible partitions with a large number of blocks.
ParHIP-Fast and ParMETIS only manage to do so on 17 and 30 out of 128
instances, respectively. We also note that ParHIP becomes quite slow, with
even its fast configuration being more than an order of magnitude slower than
dKaMinPar-Fast. This is because ParHIP keeps a relatively larger number of
vertices per block in the coarsest graph ($C=5000$), and is therefore unable
to shrink the graph sufficiently even for moderate values of $k$.

##  10 Edge Cut Results for Weak Scaling

Table 3: Edge cut results for weak scaling experiments on randomly generated graphs using 64–8 192 cores of Machine B and $\varepsilon=3\%$. Some columns are not shown due to size constraints. Edge cuts and gmeans are reported relative to dKaMinPar-Fast. Timeouts (15 minutes) and crashes are marked with 🕒 and $\times$, infeasible solutions are marked with $\triangle$.  |  |  |  Cut on number of PEs / 1 000 |
---|---|---|---|---
| Graph | Algorithm | 128 | 512 | 2 048 | 8 192 | gmean
$k=16$ | $\textsf{rgg}_{\textrm{2D}}26\textrm{d}8$ | dKaMinPar-Fast | 280 | 572 | 1 177 | 2 428 | 1.00
ParHIP-Fast | 1.10 | 1.13 | 1.14 | $\triangle$ | 1.11
ParMETIS | 1.22 | 1.19 | 1.18 | 1.17 | 1.19
XtraPuLP | 87.12 | 131.52 | 333.21 | 637.60 | 190.28
$\textsf{rgg}_{\textrm{2D}}26\textrm{d}32$ | dKaMinPar-Fast | 4 156 | 8 544 | 17 508 | 36 050 | 1.00
ParHIP-Fast | 1.12 | 1.14 | 1.16 | $\triangle$ | 1.15
ParMETIS | 0.95 | 0.94 | 0.94 | 0.94 | 0.94
XtraPuLP | 24.39 | 41.98 | 78.05 | 174.62 | 53.72
$\textsf{rgg}_{\textrm{3D}}26\textrm{d}8$ | dKaMinPar-Fast | 4 668 | 12 037 | 31 526 | 81 200 | 1.00
ParHIP-Fast | 1.01 | 1.01 | 1.00 | 🕒 | 1.01
ParMETIS | 0.95 | 0.96 | 0.92 | 0.92 | 0.94
XtraPuLP | 12.48 | 19.92 | 25.31 | 37.47 | 21.13
$\textsf{rgg}_{\textrm{3D}}26\textrm{d}32$ | dKaMinPar-Fast | 40 411 | 103 491 | 267 885 | 701 865 | 1.00
ParHIP-Fast | 1.02 | 1.02 | 1.01 | $\triangle$ | 1.02
ParMETIS | 0.88 | 0.87 | 0.86 | 0.84 | 0.87
XtraPuLP | 6.25 | 10.03 | 11.41 | 15.71 | 9.94
$\textsf{rhg}_{3.0}26\textrm{d}8$ | dKaMinPar-Fast | 3 | 11 | 6 | 3 | 1.00
ParHIP-Fast | 1.04 | 1.06 | 1.34 | $\triangle$ | 1.20
ParMETIS | 4.85 | $\times$ | $\times$ | $\times$ | 5.51
XtraPuLP | 9 830.42 | 12 480.89 | 77 483.14 | 608 259.52 | 48892.85
$\textsf{rhg}_{3.0}26\textrm{d}32$ | dKaMinPar-Fast | 76 | 66 | 70 | 90 | 1.00
ParHIP-Fast | 1.06 | 1.13 | 1.18 | 🕒 | 1.12
ParMETIS | 4.22 | 6.11 | 8.95 | $\times$ | 6.07
XtraPuLP | 1 074.49 | 4 613.94 | 17 322.39 | 59 519.97 | 6125.31
$2^{15}$ vertices per block | $\textsf{rgg}_{\textrm{2D}}26\textrm{d}8$ | dKaMinPar-Fast | 5 543 | 22 517 | 90 764 | 364 279 | 1.00
ParHIP-Fast | $\triangle$ | $\triangle$ | $\triangle$ | $\times$ | –
ParMETIS | 1.18 | 1.17 | 1.16 | $\times$ | 1.17
XtraPuLP | $\triangle$ | $\triangle$ | $\times$ | $\times$ | –
$\textsf{rgg}_{\textrm{3D}}26\textrm{d}8$ | dKaMinPar-Fast | 38 348 | 156 298 | 635 175 | 2 560 517 | 1.00
ParHIP-Fast | 1.03 | 1.03 | $\times$ | 🕒 | 1.03
ParMETIS | 0.99 | 1.00 | 0.99 | $\times$ | 1.00
XtraPuLP | $\triangle$ | $\triangle$ | $\times$ | $\times$ | –
$\textsf{rhg}_{3.0}26\textrm{d}8$ | dKaMinPar-Fast | 1 028 | 5 157 | 19 457 | 77 084 | 1.00
ParHIP-Fast | $\triangle$ | $\triangle$ | $\times$ | $\times$ | –
ParMETIS | 2.45 | $\times$ | $\times$ | $\times$ | 2.52
XtraPuLP | 117.45 | $\times$ | $\times$ | $\times$ | 115.92
$2^{12}$ vertices per block | $\textsf{rgg}_{\textrm{2D}}26\textrm{d}8$ | dKaMinPar-Fast | 16 751 | 68 202 | 277 126 | 1 109 307 | 1.00
ParHIP-Fast | $\triangle$ | $\times$ | $\times$ | $\times$ | –
ParMETIS | 1.09 | 1.07 | $\times$ | $\times$ | 1.08
XtraPuLP | $\times$ | $\times$ | $\times$ | $\times$ | –
$\textsf{rgg}_{\textrm{3D}}26\textrm{d}8$ | dKaMinPar-Fast | 74 560 | 300 409 | 1 213 176 | 4 876 567 | 1.00
ParHIP-Fast | $\triangle$ | $\times$ | $\times$ | $\times$ | 1.03
ParMETIS | 1.00 | $\times$ | $\times$ | $\times$ | 1.01
XtraPuLP | $\times$ | $\times$ | $\times$ | $\times$ | –
$\textsf{rhg}_{3.0}26\textrm{d}8$ | dKaMinPar-Fast | 7 255 | 30 901 | 123 132 | 495 273 | 1.00
ParHIP-Fast | $\triangle$ | $\times$ | $\times$ | $\times$ | –
ParMETIS | 1.67 | $\times$ | $\times$ | $\times$ | 1.67
XtraPuLP | $\times$ | $\times$ | $\times$ | $\times$ | –

##  11 Edge Cut Results for Strong Scaling

Table 4: Edge cut results for strong scaling experiments on 64–8 192 cores of Machine B, $k=16$, $\varepsilon=3\%$. Some columns are not shown due to size constraints. Edge cuts and gmeans are reported relative to dKaMinPar-Fast. Timeouts (15 minutes) and crashes are marked with 🕒 and $\times$, infeasible solutions are marked with $\triangle$. |  |  Cut on number of PEs / 1 000 |
---|---|---|---
Graph | Algorithm | 128 | 512 | 2 048 | 8 192 | gmean
High-degree graphs
webbase-2001 | dKaMinPar-Fast | 9 634 | 9 618 | 9 602 | 9 524 | 1.00
ParHIP-Fast | 1.09 | 1.10 | 1.14 | 1.12 | 1.11
ParMETIS | $\times$ | $\times$ | $\times$ | $\times$ | –
XtraPuLP | 2.62 | 3.30 | 6.13 | 13.79 | 5.20
uk-2007-05 | dKaMinPar-Fast | 4 093 | 4 138 | 4 176 | 4 064 | 1.00
ParHIP-Fast | 1.07 | 1.03 | 1.01 | 1.06 | 1.04
ParMETIS | $\times$ | $\times$ | $\times$ | $\times$ | –
XtraPuLP | 42.94 | 116.57 | 185.19 | 264.43 | 125.13
twitter-2010 | dKaMinPar-Fast | 616 530 | 601 073 | 604 954 | 588 380 | 1.00
ParHIP-Fast | 🕒 | 🕒 | 🕒 | 🕒 | –
ParMETIS | 🕒 | $\times$ | $\times$ | $\times$ | –
XtraPuLP | 1.36 | 1.48 | 1.51 | 1.58 | 1.48
Low-degree graphs
kmer_V1r | dKaMinPar-Fast | 10 936 | 10 897 | 10 880 | 10 836 | 1.00
ParHIP-Fast | $\times$ | $\times$ | $\times$ | $\times$ | –
ParMETIS | $\times$ | 0.84 | 0.84 | 🕒 | 0.84
XtraPuLP | 13.19 | 13.12 | 12.56 | 12.56 | 12.85
nlpkkt240 | dKaMinPar-Fast | 5 658 | 5 641 | 5 623 | 5 547 | 1.00
ParHIP-Fast | 0.99 | 1.00 | 1.00 | $\times$ | 1.00
ParMETIS | 0.93 | 0.94 | 0.95 | 0.97 | 0.95
XtraPuLP | 3.44 | 3.88 | 2.80 | 2.43 | 3.09
$\textsf{rgg}_{\textrm{2D}}27$ | dKaMinPar-Fast | 349 | 349 | 350 | 347 | 1.00
ParHIP-Fast | 1.14 | 1.15 | 1.13 | 1.15 | 1.14
ParMETIS | 1.19 | 1.18 | 1.17 | 1.15 | 1.17
XtraPuLP | 72.87 | 150.46 | 259.72 | 194.77 | 153.46

##  12 Comparison against XtraPuLP

We compare dKaMinPar against the single-level partitioner XtraPuLP [28]
(v0.3), which is a hybrid (OpenMPI+OpenMP) implementation of single-level
label propagation. To avoid excessive running time overheads due to graph
generation, we only execute XtraPuLP using a single thread per MPI process.

Strong scaling runnign times are shown in Figure 7, while weak scaling runing
times are shown in Figure 8 ($k=16$) and Figure 9 ($\\{2^{15},2^{18}\\}$
vertices per block). The corresponding edge cuts are included in Table 4
(Section 11) and Table 3 (Section 10). Surprisingly, dKaMinPar shows higher
throughputs on most tested real-world and artificial graphs, although it
should be noted that the performance of XtraPuLP could likely be improved by
running it with more threads per MPI process. Moreover, we note that the edge
cuts computed are often significantly worse (by up to 5 orders of magnitude on
$\textsf{rhg}_{8}3.0\textrm{d}26$ partitioned on 8 192 cores) than those of
the multilevel partitioners.

Figure 7: Strong scaling running times for the largest low- and high-degree
graphs in our benchmark set, with $k=16$, $\varepsilon=3\%$ on 64–8 192 cores
of Machine B.

Figure 8: Throughput of $\textsf{rgg}_{\textrm{2D}}$,
$\textsf{rgg}_{\textrm{3D}}$ and rhg graphs with $2^{26}$ vertices per compute
node, average degree $\in\\{8,32\\}$, $k=16$ and $\varepsilon=3\%$ on 64–8 192
cores of Machine B.

Figure 9: Throughput of rgg2D, rgg3D and rhg graphs with $2^{26}$ vertices per
compute node, average degree $8$, and $\varepsilon=3\%$ on 64–8 192 cores of
Machine B. The number of blocks are scaled with the size of the graph such
that each block contains $2^{12}$ or $2^{15}$ vertices.