Parallel Graph Partitioning for Complex Networks
Henning Meyerhenke

Christian Schulz

Peter Sanders

Abstract—Processing large complex networks like social networks or web graphs has recently attracted considerable interest.
In order to do this in parallel, we need to partition them
into pieces of about equal size. Unfortunately, previous parallel
graph partitioners originally developed for more regular meshlike networks do not work well for these networks. This paper
addresses this problem by parallelizing and adapting the label
propagation technique originally developed for graph clustering.
By introducing size constraints, label propagation becomes applicable for both the coarsening and the refinement phase of
multilevel graph partitioning. We obtain very high quality by
applying a highly parallel evolutionary algorithm to the coarsened
graph. The resulting system is both more scalable and achieves
higher quality than state-of-the-art systems like ParMetis or PTScotch. For large complex networks the performance differences
are very big. For example, our algorithm can partition a web
graph with 3.3 billion edges in less than sixteen seconds using
512 cores of a high performance cluster while producing a high
quality partition – none of the competing systems can handle this
graph on our system.

I.

I NTRODUCTION

It is well-known that there are more realistic (and more
complicated) objective functions involving also the block that
is worst and the number of its neighboring nodes [2], but
minimizing the cut size has been adopted as a kind of standard
since it is usually highly correlated with the other formulations.
The graph partitioning problem is NP-complete [3], [4] and
there is no approximation algorithm with a constant ratio factor
for general graphs [5]. Hence, heuristic algorithms are used in
practice.
A successful heuristic for partitioning large graphs is the
multilevel graph partitioning (MGP) approach depicted in
Figure 1, where the graph is recursively contracted to achieve
smaller graphs which should reflect the same basic structure as
the input graph. After applying an initial partitioning algorithm

The main contributions of this paper are a scalable parallelization of the size-constrained label propagation algorithm
and an integration into a multilevel framework that enables
us to partition large complex networks. The parallel sizeconstrained label propagation algorithm is used to compute
a graph clustering which is contracted. This is repeated until
the graph is small enough. The coarsest graph is then partitioned by the coarse-grained distributed evolutionary algorithm
KaFFPaE [6]. During uncoarsening the size-constraint label
propagation algorithm is used as a simple, yet effective,
parallel local search algorithm.
The presented scheme speeds up computations and improves solution quality on graphs that have a very irregular
structure such as social networks or web graphs. For example,
a variant of our algorithm is able to compute a partition of a
web graph with billions of edges in only a few seconds while
producing high quality solutions.
We organize the paper as follows. We begin in Section II
by introducing basic concepts and outlining related work.
Section III reviews the recently proposed cluster contraction
algorithm [7] to partition complex networks, which is parallelized in this work. The main part of the paper is Section IV,
which covers the parallelization of the size-constrained label
propagation algorithm, the parallel contraction and uncontraction algorithm, as well as the overall parallel system. A
summary of extensive experiments to evaluate the algorithm’s
performance is presented in Section V. Finally, we conclude
in Section VI.
contraction phase

Graph partitioning (GP) is a key prerequisite for efficient
large-scale parallel graph algorithms. A prominent example is
the PageRank algorithm [1], which is used by search engines
such as Google to order web pages displayed to the user by
their importance. As huge networks become abundant, there
is a need for their parallel analysis. In many cases, a graph
needs to be partitioned or clustered such that there are few
edges between the blocks (pieces). In particular, when you
process a graph in parallel on k PEs (processing elements),
you often want to partition the graph into k blocks of about
equal size. In this paper we focus on a version of the problem
that constrains the maximum block size to (1 + ) times the
average block size and tries to minimize the total cut size, i.e.,
the number of edges that run between blocks.

to the smallest graph, the contraction is undone and, at each
level, a local search method is used to improve the partitioning
induced by the coarser level.

output
partition

input
graph
...

contract

local improvement

initial

...

uncontract

uncoarsening phase

arXiv:1404.4797v3 [cs.DC] 26 Jan 2015

Karlsruhe Institute of Technology (KIT) Karlsruhe Institute of Technology (KIT) Karlsruhe Institute of Technology (KIT)
Karlsruhe, Germany
Karlsruhe, Germany
Karlsruhe, Germany
christian.schulz@kit.edu
sanders@kit.edu
meyerhenke@kit.edu

partitioning
Fig. 1. Multilevel graph partitioning. The graph is recursively contracted to
achieve smaller graphs. After the coarsest graph is initially partitioned, a local
search method is used on each level to improve the partitioning induced by
the coarser level.

II.

P RELIMINARIES

Most probably the fastest available parallel code is the
parallel version of Metis, ParMetis [21]. The parallel version
of Jostle [13] applies local search to pairs of neighboring
partitions and is restricted to the case where the number of
blocks equals the number of processors. This parallelization
has problems maintaining the balance of the partitions since
at any particular time, it is difficult to say how many nodes
are assigned to a particular block. PT-Scotch [22], the parallel
version of Scotch, is based on recursive bipartitioning. This
is more difficult to parallelize than direct k-partitioning since
in the initial bipartition, there is less parallelism available.
The unused processor power is used by performing several
independent attempts in parallel. The involved communication
effort is reduced by considering only nodes close to the
boundary of the current partitioning (band-refinement). KaPPa
[23] is a parallel matching-based MGP algorithm which is
also restricted to the case where the number of blocks equals
the number of processors used. PDiBaP [24] is a multilevel
diffusion-based algorithm that is targeted at small to medium
scale parallelism with dozens of processors.

A. Basic concepts
Let G = (V = {0, . . . , n − 1}, E, c, ω) be an undirected
graph with edge weights ω : E → R>0 , node weights
c : V → R≥0 , n = |V
P|, and m = |E|. We extend
P c and ω
to sets, i.e., c(V 0 ) := v∈V 0 c(v) and ω(E 0 ) := e∈E 0 ω(e).
Γ(v) := {u : {v, u} ∈ E} denotes the neighbors of v. A node
v ∈ Vi that has a neighbor w ∈ Vj , i 6= j, is a boundary node.
We are looking for blocks of nodes V1 ,. . . ,Vk that partition
V , i.e., V1 ∪ · · · ∪ Vk = V and Vi ∩ Vj = ∅ for i 6= j.
The balancing constraint demands that ∀i ∈ {1..k} : c(Vi ) ≤
)
Lmax := (1 + )d c(V
k e for some imbalance
P parameter . The
objective is to minimize the total cut
i<j w(Eij ) where
Eij := {{u, v} ∈ E : u ∈ Vi , v ∈ Vj }. We say that a block Vi
is underloaded if |Vi | < Lmax and overloaded if |Vi | > Lmax .
A clustering is also a partition of the nodes, however, k
is usually not given in advance and the balance constraint is
removed. A size-constrained clustering constrains the size of
the blocks of a clustering by a given upper bound U such that
c(Vi ) ≤ U . Note that by adjusting the upper bound one can
somehow control the number of blocks of a feasible clustering.
For example, when using U = 1, the only feasible sizeconstrained clustering in an unweighted graph is the clustering
where each node forms a block on its own.

As reported by [25], most large-scale graph processing
toolkits based on cloud computing use ParMetis or rather
straightforward partitioning strategies such as hash-based partitioning. While hashing often leads to acceptable balance,
the edge cut obtained for complex networks is very high. To
address this problem, Tian et al. [25] have recently proposed
a partitioning algorithm for their toolkit Giraph++. The algorithm uses matching-based coarsening and ParMetis on the
coarsest graph. This strategy leads to better cut values than
hashing-based schemes. However, significant imbalance is introduced by their method, so that their results are incomparable
to ours.

An abstract view of the partitioned graph is the so-called
quotient graph, in which nodes represent blocks and edges are
induced by connectivity between blocks. The weighted version
of the quotient graph has node weights which are set to the
weight of the corresponding block and edge weights which are
equal to the weight of the edges that run between the respective
blocks.

The label propagation clustering algorithm was initially
proposed by Raghavan et al. [26]. Moreover, the label propagation algorithm has been used to partition networks by Uganer
and Backstrom [27]. The authors do not use a multilevel
scheme and rely on a given or random partition which are
improved by combining the unconstrained label propagation
approach with linear programming. Hence, the approach does
not yield high quality partitionings. Another distributed algorithm for balanced graph partitioning has been proposed by
Rahimian et al. [28]. The authors use random initializations as
starting point for local search which is basically node swapping. However, if the initialization is not balanced, the final
partition computed by the algorithm will also be imbalanced
and the largest graph under consideration has less than 70K
nodes.

By default, our initial inputs will have unit edge and node
weights. However, even those will be translated into weighted
problems in the course of the multilevel algorithm. In order
to avoid tedious notation, G will denote the current state of
the graph before and after a (un)contraction in the multilevel
scheme throughout this paper.
B. Related Work
There has been a huge amount of research on graph
partitioning so that we refer the reader to [8], [9], [10] for
most of the material. Here, we focus on issues closely related
to our main contributions. All general-purpose methods that
are able to obtain good partitions for large real-world graphs
are based on the multilevel principle. The basic idea can
be traced back to multigrid solvers for solving systems of
linear equations [11] but more recent practical methods are
based on mostly graph theoretic aspects, in particular edge
contraction and local search. There are many ways to create
graph hierarchies such as matching-based schemes [12], [13],
[14], [15], [16] or variations thereof [17] and techniques
similar to algebraic multigrid [18], [19], [20]. We refer the
interested reader to the respective papers for more details.
Well-known software packages based on this approach include
Chaco [12], Jostle [13], Metis [14], Party [15] and Scotch [16].
While Chaco and Party are no longer developed and have no
parallel version, the others have been parallelized, too.

Recent work by Kirmani and Raghavan [29] solves a
relaxed version of the graph partitioning problem where no
strict balance constraint is enforced. The blocks only have
to have approximately the same size. Thus the problem is
easier than the version of the problem where a strict balance
constraint has to be fullfilled. Their approach attempts to
obtain information on the graph structure by computing an
embedding into the coordinate space using a multilevel graph
drawing algorithm. Afterwards partitions are computed using
a geometric scheme.

2

targeted at complex network such as social networks and
web graphs. We start by explaining the size-constrained label
propagation algorithm, which is used to compute clusterings
of the graph. To compute a graph hierarchy, the clustering
is contracted by replacing each cluster by a single node, and
the process is repeated recursively until the graph is small.
Due to the way the contraction is defined, it is ensured that
a partition of a coarse graph corresponds to a partition of
the input network with the same objective and balance. Note
that cluster contraction is an aggressive coarsening strategy.
In contrast to most previous approaches, it can drastically
shrink the size of irregular networks. The intuition behind this
technique is that a clustering of the graph (one hopes) contains
many edges running inside the clusters and only a few edges
running between clusters, which is favorable for the edge cut
objective. Regarding complexity, experiments in [7] indicate
already one contraction step can shrink the graph size by orders
of magnitude and that the average degree of the contracted
graph is smaller than the average degree of the input network.
Moreover, the clustering algorithm is fast and essentially runs
in linear time. On the other hand, the clustering algorithm is
parallelizable and, by using a different size-constraint, the label
propagation algorithm can also be used as a simple strategy to
improve a solution on the current level.

C. KaHIP
Within this work, we use the open source multilevel
graph partitioning framework KaHIP [30], [31] (Karlsruhe
High Quality Partitioning). More precisely, we employ the
distributed evolutionary algorithm KaFFPaE contained therein
to create high quality partitions of complex networks at the
coarsest level of the hierarchy. Hence, we shortly outline the
main components of KaHIP.
KaHIP implements many different algorithms, for example
flow-based methods and more-localized local searches within
a multilevel framework called KaFFPa, as well as several
coarse-grained parallel and sequential meta-heuristics. The
algorithms in KaHIP have been able to improve the best known
partitioning results in the Walshaw Benchmark [32] for many
inputs using a short amount of time to create the partitions.
Recently, also specialized methods to partition social networks
and web graphs have been included into the framework [7]. In
this work, we parallelize the main techniques presented therein
which are reviewed in Section III.
KaFFPaE: We now outline details of the evolutionary
algorithm, KaFFPaE [6], since we use this algorithm to obtain
a partition of the coarsest graph of the hierarchy. KaFFPaE is
a coarse-grained evolutionary algorithm, i.e. each processing
element has its own population (set of partitions) and a copy
of the graph. After initially creating the local population, each
processor performs combine and mutation operations on the
local population/partitions. The algorithm contains a general
combine operator framework provided by modifications of
the multilevel framework KaFFPa. All combine operators can
assure that the offspring has a solution quality at least as good
as the better of both parents.

A. Label Propagation with Size Constraints
Originally, the label propagation clustering algorithm was
proposed by Raghavan et al. [26] for graph clustering. It is a
very fast, near linear-time algorithm that locally optimizes the
number of edges cut. We outline the algorithm briefly. Initially,
each node is in its own cluster/block, i.e. the initial block ID
of a node is set to its node ID. The algorithm then works in
rounds. In each round, the nodes of the graph are traversed in
a random order. When a node v is visited, it is moved to the
block that has the strongest connection to v, i.e. it is moved to
the cluster Vi that maximizes ω({(v, u) | u ∈ N (v)∩Vi }). Ties
are broken randomly. The process is repeated until the process
has converged. Here, at most ` iterations of the algorithm are
performed, where ` is a tuning parameter. One round of the
algorithm can be implemented to run in O(n + m) time.

The basic combine operation works as follows: Let P1 and
P2 be two partitions of the graph G. The partitions are both
used as input to the multilevel graph partitioner KaFFPa in
the following sense. First of all, all edges that are cut edges in
any of the two input partitions, i.e. edges that run between two
blocks, are not eligible for contraction during the coarsening
phase. This means that they are not contracted during the
coarsening phase.
As soon as the coarsening phase is stopped, the better
partition is applied to the coarsest graph and used as initial
partitioning. This is possible since we did not contract any
cut edge of P1 or P2 . Since local search algorithms guarantee
no worsening of the input partition and random tie breaking
is used, it is assured that partition quality is not decreased
during uncoarsening. Note that the local search algorithms can
effectively exchange good parts of the solution on the coarse
levels by moving only a few nodes.

The computed clustering is contracted to obtain a coarser
graph. Contracting a clustering works as follows: each block
of the clustering is contracted into a single node. The weight
of the node is set to the sum of the weight of all nodes in
the original block. There is an edge between two nodes u and

...

To exchange individuals between the processors over time,
the algorithm is equipped with a scalable communication
protocol similar to randomized rumor spreading. That means
that from time to time, the best local partition is sent to a
random selection of other processors. For more details, we
refer the reader to [6].
III.

000 111
111
000
111
111
000
000 000
111
000
111

00
11
11
00
00
11

11
00
00
11

...

Scan

111
000
000
111
000
111

11
00
00
11
00
11
00
11
111
000
000
111
000
111
000
111
000
111
11
00
00
11
00
11
00
11

C LUSTER C ONTRACTION

11
00
00
11
00
11

→

11
00
00
11
00
11

11
00
00
11
00
11
00
11
111
000
000
111
000
111
000
111

Fig. 2. An example round of the label propagation graph clustering algorithm.
Initially each node is in its own block. The algorithm scans all vertices in a
random order and moves a node to the block with the strongest connection in
its neighborhood.

We now review the basic idea [7] which we chose to
parallelize. The approach for creating graph hierarchies is
3

111 111
000
000
000 111
111
000
000 111
111
000
111
000
111
000
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
000111
111
000
111
000
000
111
000 111
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
000
111
000 111
111
000 111
111
000
000
111
000
111
000
111
000
111
000
000111
111
000
111
000
111
000
111
000
000111
111
000
111

v in the contracted graph if the two corresponding blocks in
the clustering are adjacent to each other in G, i.e. block u and
block v are connected by at least one edge. The weight of
an edge (A, B) is set to the sum of the weight of edges that
run between block A and block B of the clustering. Due to
the way contraction is defined, a partition of the coarse graph
corresponds to a partition of the finer graph with the same cut
and balance. An example contraction is shown in Figure 3.

11
00
00
11
00
11
00
11

00000
11111
11111
00000
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111
00000
11111

Fig. 3. Contraction of clusterings. Each cluster of the graph on the left hand
side corresponds to a node in the graph on the right hand side. Weights of
the nodes and the edges are choosen such that a partition of the coarse graph
induces a partition of the fine graph having the same cut and balance.

In contrast to the original label propagation algorithm [26],
Meyerhenke et al. [7] ensure that each block of the cluster
fulfills a size constraint. There are two reason for this. First,
consider a clustering of the graph in which the weight of
a block would exceed (1 + )d |Vk | e. After contracting this
clustering, it would be impossible to find a partition of the
contracted graph that fulfills the balance constraint. Secondly,
it has been shown that using more balanced graph hierarchies is
beneficial when computing high quality graph partitions [23].
To ensure that blocks of the clustering do not become too
large, an upper bound U := max(maxv c(v), W ) on the size
of the blocks is introduced, where W is a parameter that will
be chosen later. When the algorithm starts to compute a graph
clustering on the input graph, the constraint is fulfilled since
each of the blocks contains exactly one node. A neighboring
block V` of a node v is called eligible if V` will not be
overloaded once v is moved to V` . Now when a node v is
visited, it is moved to the eligible block that has the strongest
connection to v. Hence, after moving a node, the size of
each block is still smaller than or equal to U . Moreover, after
contracting the clustering, the weight of each node is smaller or
equal to U . One round of the modified version of the algorithm
can still run in linear time by using an array of size |V | to store
the block sizes. Note that when parallelizing the algorithm this
is something that needs to be adjusted since storing an array of
size |V | on a single processor would cost too much memory.
The parameter W is set to Lfmax , where f is a tuning parameter.
Note that the constraint is rather soft during coarsening, i.e.
in practice it does no harm if a cluster contains slightly more
nodes than the upper bound. We go into more detail in the
next section.

likely to compute better clusterings of the graph by using node
orderings based on node degree.
By using a different size-constraint – the constraint W :=
Lmax of the original partitioning problem – the label propagation is also used as a simple and fast local search algorithm
to improve a solution on the current level [7]. However, small
modifications to handle overloaded blocks have to be made.
The block selection rule is modified when the algorithm is
used as a local search algorithm in case that the current node
v under consideration is from an overloaded block V` . In this
case it is moved to the eligible block that has the strongest
connection to v without considering the block V` that it is
contained in. This way it is ensured that the move improves
the balance of the partition (at the cost of the number of edges
cut).
IV.

PARALLELIZATION

We now present the main contributions of the paper. We
begin with the distributed memory parallelization of the sizeconstrained label propagation algorithm and continue with the
parallel contraction and uncoarsening algorithm. At the end of
this section, we describe the overall parallel system.
A. Parallel Label Propagation
We shortly outline our parallel graph data structure and the
implementation of the methods that handle communication.
First of all, each processing element (PE) gets a subgraph,
i.e. a contiguous range of nodes a..b, of the whole graph as
its input, such that the subgraphs combined correspond to the
input graph. Each subgraph consists of the nodes with IDs
from the interval I := a..b and the edges incident to the
nodes of those blocks, as well as the end points of edges
which are not in the interval I (so-called ghost or halo nodes).
This implies that each PE may have edges that connect it to
another PE and the number of edges assigned to the PEs might
vary significantly. The subgraphs are stored using a standard
adjacency array representation, i.e. we have one array to store
edges and one array for nodes storing head pointers to the edge
array. However, the node array is divided into two parts. The
first part stores local nodes and the second part stores ghost
nodes. The method used to keep local node IDs and ghost node
IDs consistent is explained in the next paragraph. Additionally,
we store information about the nodes, i.e. its current block and
its weight.

The process of computing a size-constrained clustering and
contracting it is repeated recursively. As soon as the graph is
small enough, it is initially partitioned. That means each node
of the coarsest graph is assigned to a block. Afterwards, the
solution is transferred to the next finer level. To do this, a
node of the finer graph is assigned to the block of its coarse
representative. Local improvement methods of KaHIP then try
to improve the solution on the current level, i.e. reducing the
number of edges cut.
Recall that the label propagation algorithm traverses the
nodes in a random order and moves a node to a cluster
with the strongest connection in its neighborhood to compute
a clustering. Meyerhenke et al. [7] have shown that using
the ordering induced by the node degree (increasing order)
improves the overall solution quality and running time. Using
this node ordering means that in the first round of the label
propagation algorithm, nodes with small node degree can
change their cluster before nodes with a large node degree.
Intuitively, this ensures that there is already a meaningful
cluster structure when the label propagation algorithm chooses
the cluster of a high degree node. Hence, the algorithm is

Instead of using the node IDs provided by the input graph
(called global IDs), each PE maps those IDs to the range
4

0 .. np − 1, where np is the number of distinct nodes of the
subgraph. Note that this number includes the number of ghost
nodes the PE has. Each global ID i ∈ a .. b is mapped to a
local node ID i − a. The IDs of the ghost nodes are mapped
to the remaining np − (b − a) local IDs in the order in which
they appeared during the construction of the graph structure.
Transforming a local node ID to a global ID or vice versa,
can be done by adding or subtracting a. We store the global
ID of the ghost nodes in an extra array and use a hash table
to transform global IDs of ghost nodes to their corresponding
local IDs. Additionally, we store for each ghost node the ID
of the corresponding PE, using an array for O(1) lookups.

We maintain the balance of different blocks during coarsening as follows. Roughly speaking, a PE maintains and
updates only the local amount of node weight of the blocks of
its local and ghost nodes. Due to the way the label propagation
algorithm is initialized, each PE knows the exact weights of
the blocks of local nodes and ghost nodes in the beginning.
The label propagation then uses the local information to bound
the block weights. Once a node changes its block, the local
block weight is updated. Note that this does not involve
additional amounts of communication. We decided to use this
localized approach since the balance constraint is not tight
during coarsening. More precisely, the bound on the cluster
sizes during coarsening is a tuning parameter and the overall
performance of the system does not depend on the exact choice
of the parameter.

To parallelize the label propagation algorithm, each PE
performs the algorithm on its part of the graph. Recall, when
we visit a node v, it is moved to the block that has the
strongest connection. Note that the cluster IDs of a node can
be arbitrarily distributed in the range 0 .. n−1 so that we use a
hash map to identify the cluster with the strongest connection.
Since we know that the number of distinct neighboring cluster
IDs is bounded by the maximum degree in the graph, we use
hashing with linear probing. At this particular point of the
algorithm, it turns out that hashing with linear probing is much
faster than using the hash map of the STL.

During uncoarsening we use a different approach since
the number of blocks is much smaller and it is unlikely
that the previous approach yields a feasible partition in the
end. This approach is similar to the approach that is used
within ParMetis [21]. Initially, the exact block weights of
all k blocks are computed locally. The local block weights
are then aggregated and broadcast to all PEs. Both can be
done using one allreduce operation. Now each PE knows the
global block weights of all k blocks. The label propagation
algorithm then uses this information and locally updates the
weights. For each block, a PE maintains and updates the total
amount of node weight that local nodes contribute to the block
weights. Using this information, one can restore the exact
block weights with one allreduce operation which is done at the
end of each computation phase. Note that this approach would
not be feasible during coarsening since there are n blocks in
the beginning of the algorithm and each PE holds the block
weights of all blocks.

During the course of the algorithm, local nodes can change
their block and hence the blocks in which ghost nodes are contained can change as well. Since communication is expensive,
we do not want to perform communication each time a node
changes its block. We use the following scheme to overlap
communication and computation. The scheme is organized in
phases. We call a node interface node if it is adjacent to at
least one ghost node. The PE associated with the ghost node is
called adjacent PE. Each PE stores a separate send buffer for
all adjacent PEs. During each phase, we store the block ID of
interface nodes that have changed into the send buffer of each
adjacent PE of this node. Communication is then implemented
asynchronously. In phase κ, we send the current updates to our
adjacent PEs and receive the updates of the adjacent PEs from
round κ − 1, for κ > 1. Note that in case the label propagation
algorithm has converged, i.e. no node changes its block any
more, the communication volume is really small.

C. Parallel Contraction and Uncoarsening
The parallel contraction algorithm works as follows. After
the parallel size-constrained label propagation algorithm has
been performed, each node is assigned to a cluster. Recall
the definition of our general contraction scheme. Each of the
clusters of the graph corresponds to a coarse node in the coarse
graph and the weight of this node is set to the total weight of
the nodes that are in that cluster. Moreover, there is an edge
between two coarse nodes iff there is an edge between the
respective clusters and the weight of this edge is set to the
total weight of the edges that run between these clusters in the
original graph.

The degree-based node ordering approach of the label propagation algorithm that is used during coarsening is parallelized
by considering only the local nodes for this ordering. In other
words, the ordering in which the nodes are traversed on a PE
is determined by the node degrees of the local nodes of this
PE. During uncoarsening random node ordering is used.

In the parallel scheme, the IDs of the clusters on a PE
can be arbitrarily distributed in the interval 0 .. n − 1, where n
is the total number of nodes of the input graph of the current
level. Consequently, we start the parallel contraction algorithm
by finding the number of distinct cluster IDs which is also the
number of coarse nodes. To do so, a PE p is assigned to count
the number of distinct cluster IDs in the interval Ip := pd Pn e+
1 .. (p + 1)d Pn e, where P is the total number of PEs used.
That means each PE p iterates over its local nodes, collects
cluster IDs a that are not local, i.e. a 6∈ Ip , and then sends
the non-local cluster IDs to the responsible PEs. Afterwards, a
PE counts the number of distinct local cluster IDs so that the
number of global distinct cluster IDs can be derived easily by
using a reduce operation.

B. Balance/Size Constraint
Recall that we use the size-constrained label propagation
algorithm during coarsening using Lmax
as a size constraint
f
and during uncoarsening using Lmax as a size constraint.
Maintaining the balance of blocks is somewhat more difficult
in the parallel case than in the sequential case. We use two
different approaches to maintain balance, one of which is
used during coarsening and the other one is used during
uncoarsening. The reason for this is that during coarsening
there is a large number of blocks and the constraint is rather
soft, whereas during uncoarsening the number of blocks is
small and the constraint is tight.
5

Parallel
Coarsening

Parallel
Uncoarsening

Let n0 be the global number of distinct cluster IDs. Recall
that this is also the number of coarse nodes after the contraction
has been performed. The next step in the parallel contraction
algorithm is to compute a mapping q : 0 .. n − 1 → 0 .. n0 − 1
which maps the current cluster IDs to a contiguous interval
over all PEs. This mapping can be easily computed in parallel
by computing a prefix sum over the number of distinct local
cluster IDs a PE has. Once this is done, we compute the
mapping C : 0 .. n − 1 → 0 .. n0 − 1 which maps a node ID
of G to its coarse representative. Note that, if a node v is in
cluster V` after the label propagation algorithm has converged,
then C(v) = q(`). After computing this information locally,
we also propagate the necessary parts of the mapping to
neighboring PEs so that we also know the coarse representative of each ghost node. When the contraction algorithm is
fully0 completed, PE p0 will be responsible for the subgraph
pd nP e + 1 .. (p + 1)d nP e of the coarse graph. To construct the
final coarse graph, we first construct the weighted quotient
graph of the local subgraph of G using hashing. Afterwards,
each PE sends an edge (u, v) of the local quotient graph,
including its weight and the weight of its source node, to the
responsible PE. After all edges are received, a PE can construct
its coarse subgraph locally.

Distributed Evoluationary Partitioning
Graph not partitioned

Graph partitioned

Fig. 4. The overall parallel system. It uses the parallel cluster coarsening
algorithm, the coarse-grained distributed evolutionary algorithm KaFFPaE to
partition the coarsest graph and parallel uncoarsening/local search. After the
first iteration of the multilevel scheme the input partition is used as a partition
of the coarsest graph and used as a starting point by the evolutionary algorithm.

the input partition as the node itself. We do the same in our
parallel approach to realize V-cycles.
E. The Overall Parallel System
The overall parallel system works as follows. We use `
iterations of the parallel size-constrained label propagation
algorithm to compute graph clusterings and contract them in
parallel. We do this recursively until the remaining graph has
10 000 · k nodes left, where k is the number of blocks that
the input network should be partitioned in. The distributed
coarse graph is then collected on each PE, i.e. each PE has
a copy of the complete coarsest graph. We use this graph as
input to the coarse-grained distributed evolutionary algorithm
KaFFPaE, to obtain a high quality partition of it. KaFFPaE
uses modified combine operations that also use the clusteringbased coarsening scheme from above. The best solution of
the evolutionary algorithm is then broadcast to all PEs which
transfer the solution to their local part of the distributed coarse
graph. Afterwards, we use the parallel uncoarsening algorithm
to transfer the solution of the current level to the next finer
level and apply r iterations of the parallel label propagation
algorithm with the size constraints of the original partitioning
problem (setting W = (1 + )d |Vk | e) to improve the solution
on the current level. We do this recursively on each level and
obtain a k-partition of the input network in the end. If we use
iterated V-cycles, we use the given partition of the coarse graph
as input to the evolutionary algorithm. More precisely, one
individual of the population is the input partition on each PE.
This way it is ensured that the evolutionary algorithm computes
a partition that is at least as good as the given partition.

The implementation of the parallel uncoarsening algorithm
is simple. Each PE knows the coarse node for all its nodes in
its subgraph (through the mapping C). Hence, a PE requests
the block ID of a coarse representative of a fine node from the
PE that holds the respective coarse node.
D. Miscellanea
Iterated Multilevel Schemes: A common approach to obtain high quality partitions is to use a multilevel algorithm
multiple times using different random seeds and use the best
partition that has been found. However, one can do better by
transferring the solution of the previous multilevel iteration
down the hierarchy. In the graph partitioning context, the
notion of V-cycles was introduced by Walshaw [33]. More
recent work augmented them to more complex cycles [34].
These previous works use matching-based coarsening with
cut edges not being matched (and hence cut edges are not
contracted). Thus, a given partition on the finest level can be
used as initial partition of the coarsest graph (having the same
balance and cut as the partition of the finest graph).
Iterated V-cycles are also used within clustering-based
coarsening by Meyerhenke et al. [7]. To adopt the iterated
multilevel technique for this coarsening scheme, it has to
be ensured that cut edges are not contracted after the first
multilevel iteration. This is done by modifying the label
propagation algorithm such that each cluster of the computed
clustering is a subset of a block of the input partition. In other
words, each cluster only contains nodes of one unique block
of the input partition. Hence, when contracting the clustering,
every cut edge of the input partition will remain. Recall that the
label propagation algorithm initially puts each node in its own
block so that in the beginning of the algorithm each cluster is a
subset of one unique block of the input partition. This property
is kept during the course of the label propagation algorithm by
restricting the movements of the label propagation algorithm,
i.e. we move a node to an eligible cluster with the strongest
connection in its neighborhood that is in the same block of

V.

E XPERIMENTS

In this section we carefully evaluate the performance of the
proposed algorithm. We start by presenting our methodology,
the systems used for the evaluation and the benchmark set that
we used. We then look into solution quality as well as weak
and strong scalability comparing our algorithm to ParMetis,
which is probably the most widely used parallel partitioning
algorithm.
A. Methodology
We have implemented the algorithm described above using
C++ and MPI. Overall, our parallel program consists of about
6

TABLE I.
BASIC PROPERTIES OF THE BENCHMARK SET WITH A
ROUGH TYPE CLASSIFICATION . S STANDS FOR SOCIAL OR WEB GRAPHS ,
M IS USED FOR MESH TYPE NETWORKS .

7000 lines of code (not including the source of KaHIP 0.61).
We compiled it using g++ 4.8.2 and OpenMPI 1.6.5. For the
following comparisons we used ParMetis 4.0.3. All programs
have been compiled using 64 bit index data types. We also
ran PT-Scotch 6.0.0, but the results have been consistently
worse in terms of solution quality and running time compared
to the results computed by ParMetis, so that we do not
present detailed data for PT-Scotch. Our default value for
the allowed imbalance is 3% since this is one of the values
used in [35] and the default value in Metis. By default we
perform ten repetitions for each configuration of the algorithm
using different random seeds for initialization and report the
arithmetic average of computed cut size, running time and the
best cut found. When further averaging over multiple instances,
we use the geometric mean in order to give every instance
a comparable influence on the final score. Unless otherwise
stated, we use the following factor f of the size-constraint (see
Section IV-B for the definition): during the first V-cycle the
factor f is set to 14 on social networks as well as web graphs
and to 20 000 on mesh type networks. In later V-cycles we use
a random value f ∈rnd [10, 25] to increase the diversifaction
of the algorithms. Our experiments mainly focus on the case
k = 2 to save running time and to keep the experimental
evaluation simple. Moreover, we used k = 16 for the number
of blocks when performing the weak scalability experiments
in Section V-B.

graph
amazon
eu-2005
youtube
in-2004
packing
enwiki
channel
hugebubble-10
nlpkkt240
uk-2002
del26
rgg26
arabic-2005
sk-2005
uk-2007
delX
rggX

n

m

Large Graphs
≈407K
≈2.3M
≈862K
≈16.1M
≈1.1M
≈2.9M
≈1.3M
≈13.6M
≈2.1M
≈17.4M
≈4.2M
≈91.9M
≈4.8M
≈42.6M
≈18.3M
≈27.5M
≈27.9M
≈373M
≈18.5M
≈262M
≈67.1M
≈201M
≈67.1M
≈575M
Larger Web Graphs
≈22.7M
≈553M
≈50.6M
≈1.8G
≈105.8M
≈3.3G
Graph Families
[219 , . . . , 231 ]
≈1.5M–6.4G
[219 , . . . , 231 ]
≈3.3M–21.9G

Type

Ref.

S
S
S
S
M
S
M
M
M
S
M
M

[39]
[36]
[39]
[36]
[36]
[41]
[36]
[36]
[37]
[41]
[23]
[23]

S
S
S

[41]
[41]
[41]

M
M

[23]
[23]

8x256 KB L2-Cache. System B is a cluster where each node
is equipped with two Intel Xeon E5-2670 Octa-Core processors
(Sandy Bridge) which run at a clock speed of 2.6 GHz. Each
node has 64 GB local memory, 20 MB L3-Cache and 8x256
KB L2-Cache. All nodes have local disks and are connected
by an InfiniBand 4X QDR interconnect, which is characterized
by its very low latency of about 1 microsecond and a point
to point bandwidth between two nodes of more than 3700
MB/s. We use machine B for the scalability experiments in
Section V-B.

Algorithm Configurations: Any multilevel algorithm has a
considerable number of choices between algorithmic components and tuning parameters. We define two “good” choices:
the fast setting aims at a low execution time that still gives
good partitioning quality and the eco setting targets even better
partitioning quality without investing an outrageous amount
of time. When not otherwise mentioned, we use the fast
parameter setting.

Instances: We evaluate our algorithms on graphs collected
from [36], [37], [38], [39]. Table I summarizes the main
properties of the benchmark set. Our benchmark set includes a
number of graphs from numeric simulations as well as social
networks and web graphs. Moreover, we use the two graph
families rgg and del for comparisons. rggX is a random
geometric graph with 2X nodes where nodes represent random
points in the unit square and edges
connect nodes whose
p
Euclidean distance is below 0.55 ln n/n. This threshold was
chosen in order to ensure that the graph is almost certainly
connected. The largest graph of this class is rgg31, which has
about 21.9 billion edges. delX is a Delaunay triangulation of
2X random points in the unit square. The largest graph of
this class is del31, which has about 6.4 billion edges. Most of
these graphs are available at the 10th DIMACS Implementation
Challenge [40] website. The largest graphs (with 226 to 231
nodes) of these families have been generated using modified
code taken from [23]. We will make these graphs available on
request.

The fast configuration of our algorithm uses three label
propagation iterations during coarsening and six during refinement. We also tried larger amounts of label propagation
iterations during coarsening, but did not observe a significant
impact on solution quality. This configuration gives the evolutionary algorithm only enough time to compute the initial
population and performs two V-cycles. The eco configuration
of our algorithm uses three label propagation iterations during
coarsening and six label propagation iterations during refinement as well. Time spent during initial partitioning is dependent on the number of processors used. To be more precise,
when we use one PE, the evolutionary algorithm has t1 = 211 s
to compute a partition of the coarsest graph during the first
V-cycle. When we use p PEs, then it gets time tp = t1 /p to
compute a partition of an instance. This configuration performs
five V-cycles. There is also a minimal variant of the algorithm,
which is similar to the fast configuration but only performs
one V-cycle. We use this variant of the algorithm only once
– to create a partition of the largest web graph uk-2007 on
machine B (described below).

B. Main Results and Comparison to ParMetis
In this section we compare variants of our algorithm against
ParMetis in terms of solution quality, running time as well as
weak and strong scalability. We start with the comparison of
solution quality (average cut, best cut) and average running
time on most of the graphs from Table I when 32 PEs
of machine A are used. Table III gives detailed results per
instance.

Systems: We use two different systems for our experimental evaluation. System A is mainly used for the evaluation of
the solution quality of the different algorithms in Table III. It is
equipped with four Intel Xeon E5-4640 Octa-Core processors
(Sandy Bridge) running at a clock speed of 2.4 GHz. The
machine has 512 GB main memory, 20 MB L3-Cache and

First of all, ParMetis could not solve the largest instances
in our benchmark set, arabic, sk-2005 and uk-2007 when 32
7

TABLE II.
AVERAGE PERFORMANCE ( CUT AND RUNNING TIME ) AND BEST RESULT ACHIEVED BY DIFFERENT PARTITIONING ALGORITHMS . R ESULTS
ARE FOR THE BIPARTITIONING CASE k = 2. A LL TOOLS USED 32 PE S OF MACHINE A. R ESULTS INDICATED BY A * MEAN THAT THE AMOUNT OF MEMORY
NEEDED BY THE PARTITIONER EXCEEDED THE AMOUNT OF MEMORY AVAILABLE ON THAT MACHINE WHEN 32 PE S ARE USED (512GB RAM). T HE
PAR M ETIS RESULT ON ARABIC HAS BEEN OBTAINED USING 15 PE S ( THE LARGEST NUMBER OF PE S SO THAT PAR M ETIS COULD SOLVE THE INSTANCE ).

algorithm
graph
amazon
eu-2005
youtube
in-2004
packing
enwiki
channel
hugebubbles
nlpkkt240
uk-2002
del26
rgg26
arabic-2005
sk-2005
uk-2007

avg. cut
48 104
33 789
181 885
7 016
11 991
9 578 551
48 798
1 922
1 178 988
787 391
18 086
44 747
*1 078 415
*
*

ParMetis
best cut
47 010
24 336
171 857
5 276
11 476
9 553 051
47 776
1 854
1 152 935
697 767
17 609
42 739
*968 871
*
*

t[s]
0.49
30.60
6.10
3.43
0.24
326.92
0.55
4.66
15.97
128.71
23.74
8.37
*1 245.57
*
*

avg. cut
46 641
20 898
174 911
3 172
10 185
9 622 745
56 982
1 918
1 241 950
434 227
17 002
38 371
551 778
3 775 369
1 053 973

PEs of machine A are used. This is due to the fact that
ParMetis cannot coarsen the graphs effectively so that the
coarsening phase is stopped too early. Since the smallest graph
is replicated on each of the PEs, the amount of memory needed
by ParMetis is larger than the amount of memory provided by
the machine (512GB RAM). For example, when the coarsening
phase of ParMetis stops on the instance uk-2007, the coarsest
graph still has more than 60M vertices. This is less than a
factor of two reduction in graph size compared to the input
network (the same holds for the number of edges in the coarse
graph). The same behaviour is observed on machine B, where
even less memory per PE is available. Contrarily, our algorithm
is able to shrink the graph size significantly. For instance, after
the first contraction step, the graph is already two orders of
magnitude smaller and contains a factor of 300 less edges than
the input graph uk-2007. We also tried to use a smaller amount
of PEs for ParMetis. It turns out that ParMetis can partition
arabic when using 15 PEs cutting nearly twice as many edges
and consuming thirty-seven times more running time than our
fast variant. Moreover, ParMetis could not solve the instance
sk-2005 and uk-2007 for any number of PEs.

Fast
best cut
45 872
18 404
171 549
3 110
9 925
9 565 648
55 959
1 857
1 228 086
390 182
16 703
37 676
471 141
3 204 125
1 032 000

t[s]
1.85
1.63
8.74
1.38
1.84
157.32
2.71
38.00
35.06
19.62
165.02
55.91
33.45
471.16
169.96

avg. cut
44 703
18 565
167 874
3 027
9 634
9 559 782
52 101
1 678
1 193 016
415 120
15 826
34 530
511 316
3 265 412
1 010 908

Eco
best cut
44 279
18 347
164 095
2 968
9 351
9 536 520
50 210
1 620
1 181 214
381 464
15 690
34 022
475 140
2 904 521
981 654

t[s]
71.04
70.04
105.87
69.19
68.69
264.64
71.95
216.91
192.78
146.77
697.43
263.81
184.01
1 688.63
723.42

needing more than five times as much running time. This is due
to the fact that this type of network usually has no community
structure so that the graph sizes do not shrink as fast. Still the
eco configuration computes 11.8% smaller cuts than ParMetis.
To obtain a fair comparison on this type of networks, we also
compare the best cut found by ParMetis against the average
cuts found by our algorithms. While the best cuts on mesh type
networks of ParMetis are comparable to the average results
of our fast configuration, the eco configuration still yields
8.2% smaller cuts. When partitioning the instances into 32
blocks, improvements are distributed similarly, i.e. they are
much larger on social networks than on mesh type networks.
Overall, our fast and eco configuration compute 6.8% and
16.1% smaller cuts than ParMetis, respectively. Yet, in this
comparison ParMetis simplifies the problem by relaxing it:
On some instances it does not respect the balance constraint
and computes partitions with up to 6% imbalance. A table
10-4

DelX Fast
RggX Fast
DelX ParMetis
RggX ParMetis

time per edge [s]

10-5

When only considering the networks that ParMetis could
solve in Table III, our fast and eco configuration compute
cuts that are 19.2% and 27.4% smaller on average than the
cuts computed by ParMetis, respectively. On average, fast and
eco need more time to compute a partition. However, there is
a well defined gap between mesh type networks that usually
do not have a community structure to be found and contracted
by our algorithm, and social networks as well as web graphs,
which our algorithm targets. Considering only social networks
and web graphs, our fast algorithm is more than a factor
two faster on average and improves the cuts produced by
ParMetis by 38% (the eco configuration computes cuts that
are 45% smaller than the cuts computed by ParMetis). The
largest speedup over ParMetis in Table III was obtained on
eu-2005 where our algorithm is more than eighteen times as
fast as ParMetis and cuts 61.6% less edges on average. In
contrast, on mesh type networks our algorithm does not have
the same advantage as on social networks. For example, our
fast configuration improves on ParMetis only by 2.9% while

10-6
10-7
10-8
10-9

10-10

1

2

4

8 16 32 64
256
number of PEs p

1K 2K

Fig. 5. Weak scaling experiments for random geometric graph class rggX
and the Delaunay triangulation graph class delX. When using p PEs, the
instance with 219 p nodes from the corresponding graph class was used, i.e.
when using 2048 cores all algorithms partition the graphs del30 and rgg30.
The figure shows the time spend per edge. Sixteen blocks have been used for
the partitioning task.

8

reporting detailed results can be found in the Appendix.
We now turn to the evaluation of weak scalability. These
experiments have been performed on the high-performance
cluster (machine B). To evaluate weak scalability, we use the
two graph families rggX and delX, and use k = 16 for
the number of blocks for the partitioning task. Moreover, we
focus on the fast configuration of our algorithm and ParMetis
to save running time. We expect that the scalability of the
eco configuration of our algorithm is similar. When using
p PEs, the instance with 219 p nodes from the corresponding
graph class is used, i.e. when using 2048 cores, all algorithms
partition the graphs del30 and rgg30. Figure 5 reports the
running time per edge of the algorithms under consideration.
Our algorithm shows weak scalability all the way down to
the largest number of cores used while the running time per
edge has a somewhat stronger descent compared to ParMetis.
ParMetis has trouble partitioning the largest Delaunay graphs.
The largest Delaunay graph that ParMetis could partition was
del28 using 512 cores. Considering the instances that ParMetis
could solve, our fast configuration improves solution quality
by 19.5% on random geometric graphs and by 11.5% on
Delaunay triangulations on average. Since the running time
of the fast configuration is slower on both graph families,
we again compare the best cut results of ParMetis achieved
in ten repetitions against our average results to obtain a fair
comparison (in this case ParMetis has a slight advantage in
terms of running time). Doing so, our algorithm still yields
an improvement of 16.8% on the random geometric graphs
and an improvement of 9.5% on the Delaunay triangulations.
Eventually, ParMetis is slower than the fast version of our
partitioner. On the largest random geometric graph used during
this test, we are about a factor of two faster than ParMetis,
while improving the results of ParMetis by 9.5%. In this case
our partitioner needs roughly 65 seconds to compute a 16partition of the graph. In addition, our algorithm is a factor
five faster on the largest Delaunay graph that ParMetis could
solve and produces a cut that is 9.5% smaller than the cut
produced by ParMetis.

10000

Fast Del31
Fast Del29
Fast Del27

Fast Del25
ParMetis Del27
ParMetis Del25

total time [s]

1000
100
10
1
1

2

4

10000

Fast Rgg31
Fast Rgg29
Fast Rgg27
Fast Rgg25

1000
total time [s]

8 16 32 64
256
number of PEs p

1K 2K

ParMetis Rgg31
ParMetis Rgg29
ParMetis Rgg27
ParMetis Rgg25

100
10
1
0.1
1

2

4

1000

total time [s]

We now look at strong scalability. Here we use a subset
of the random geometric and Delaunay graphs as well as the
four large graphs arabic, uk-2002, sk-2007, and uk-2007. In
all cases we use up to 2048 cores of machine B (except for
del25 and rgg25, for which we only scaled up to 1024 cores).
Again, we focus on the fast configuration of our algorithm and
ParMetis to save running time. Figure 6 summarizes the results
of the experiments. First of all, we observe strong scalability
to thousands of processors if the graphs are large enough. On
del29 and rgg31, our algorithm scales all the way down to 2048
cores. Using all 2048 cores, we need roughly 6.5 minutes to
partition del31 and 73 seconds to partition rgg31. Note that
the rgg31 graph has three times more edges than del31 but
the running time needed to partition del31 is higher. This
is due to the fact that the Delaunay graphs have very bad
locality, i.e. when partitioning del31 more than 40% of the
edges are ghost edges, whereas we observe less than 0.5%
ghost edges when partitioning the largest random geometric
graph. Although the scaling behaviour of ParMetis is somewhat
better on the random geometric graphs rgg25-29, our algorithm
is eventually more than three times faster on the largest random
geometric graph under consideration when all 2048 cores are
used.

8 16 32 64
256
number of PEs p

Fast sk-2007
Fast arabic-2005
Fast uk-2002

1K 2K

Fast uk-2007
Minimal uk-2007

100

10
1

2

4

8 16 32 64
256
number of PEs p

1K 2K

Fig. 6. Top: Strong scaling experiments on Delaunay networks. The largest
graph that ParMetis could partition from this graph family was del27. Middle:
Strong scaling experiments on random geometric networks. Bottom: Strong
scaling experiments on the largest social networks from our benchmark set.
Due to ineffective coarsening, ParMetis was not able to partition any of these
graphs on machine B. On the largest graph, uk-2007, we also used the minimal
variant of our algorithm. Note, although our system is not built for mesh-type
networks such as Delaunay and random geometric graphs, we can partition
larger instances and compute better solutions than ParMetis.

9

Apache Giraph (https://giraph.apache.org/), Giraph++ [25],
and GraphLab [44]. In future work we want to develop a
very fast prepartitioner for such systems and we want to take
advantage of the already computed partition in later multilevel
iterations to further minimize the communication needed by
the label propagation algorithm. Our algorithm may also be
very helpful if a prepartition of the graph is already available,
e.g. from geographic initializations as in [27]. This prepartition
could be directly fed into the first V-cycle and consecutively
be improved. In practical applications it may be advantageous
to impart the information given by ground-truth communities
if such are available.

As on machine A, ParMetis could not partition the instances uk-2002, arabic, sk-2007 and uk-2007 – this is again
due to the amount of memory needed arising from ineffective
coarsening. On the smaller graphs, uk-2002 and arabic, our
algorithm scales up to 128 cores obtaining a 35-fold and 32fold speed-up compared to the case where our algorithm uses
only one PE. On the larger graphs sk-2007 and uk-2007 we
need more memory. The smallest number of PEs needed to
partition sk-2007 and uk-2007 on machine B has been 256
PEs and 512 PEs, respectively. We observe scalability up to 1K
cores on the graph sk-2007 (although, to be fair, the running
time does not decrease much in that area). On uk-2007 we do
not observe further scaling when switching from 512 - 2048
cores so that it is unclear where the sweet spot is for this graph.
We also applied the minimal configuration on machine B to the
largest web graph uk-2007 in our benchmark set. The minimal
configuration needs 15.2 seconds to partition the graph when
512 cores are used. The cut is 18.2% higher compared to the
cut of the fast configuration, which needs roughly 47 seconds
to perform the partitioning task and cuts approximately 1.03M
edges on average. This is fifty-seven times faster than the time
needed to partition this graph using one core of machine A
(which is faster).
VI.

It will be very interesting to generalize our algorithm for
graph clustering w.r.t. modularity. For example, it should be
straightforward to integrate the algorithm of Ovelgönne and
Geyer-Schulz [45] to compute a high quality modularity graph
clustering on the coarsest level of the hierarchy. This would
enable researchers to compute graph clusterings of huge unstructured graphs in a short amount of time. Another issue that
we want to look at are other objective functions. For example,
it might be interesting to integrate other objective functions
such as maximum/total communication volume or maximum
quotient graph degree into the evolutionary algorithm which
is called on the coarsest graph of the hierarchy as well as into
the label propagation algorithm.

C ONCLUSION AND F UTURE W ORK

Current state-of-the-art graph partitioners have difficulties
when partitioning massive complex networks, at least partially
due to ineffective coarsening. We have demonstrated that
high quality partitions of such networks can be obtained in
parallel in a scalable way. This was achieved by using a new
multilevel scheme based on the contraction of size-constrained
clusterings, which can reduce the size of the graph very fast.
The clusterings have been computed by a parallelization of the
size-constrained label propagation algorithm [7]. As soon as
the graph is small enough, we use a coarse-grained distributed
memory parallel evolutionary algorithm to compute a high
quality partitioning of the graph. By using the size-constraint
of the graph partitioning problem to solve, the parallel label
propagation algorithm is also used as a very simple, yet
effective, local search algorithm. Moreover, by integrating
techniques like V-cycles and the evolutionary algorithm on the
coarsest level, our system gives the user a gradual choice to
trade solution quality for running time.

ACKNOWLEDGEMENTS
We would like to thank the Steinbuch Centre of Computing
for giving us access to the Instituts Cluster II. Moreover,
we would like to thank Horst Gernert and his team for the
support that we received while we performed the scalability
experiments on the cluster.
R EFERENCES
[1]

[2]

[3]

The strengths of our new algorithm unfolds in particular
on social networks and web graphs, where average solution
quality and running time is much better than what is observed
by using ParMetis. Due to the ability to shrink highly complex
networks drastically, our algorithm is able to compute high
quality partitions of web scale networks in a matter of seconds,
whereas ParMetis fails to compute any partition. Moreover, our
algorithm scales well up to thousands of processors.

[4]

[5]
[6]

[7]

Considering the good results of our algorithm, we want
to further improve and release it. An important emerging
application scenario are large-scale graph processing toolkits
based on cloud computing. Significant savings for several
algorithmic kernels within the toolkit GPS have been reported
by using graph partitioning [42] – ParMetis in their case. Due
to the superiority of our new algorithm compared to ParMetis
on large complex networks, further running time savings can
be anticipated, also for related tools like Google’s Pregel [43],

[8]

[9]
[10]

10

S. Brin and L. Page, “The Anatomy of a Large-Scale Hypertextual Web
Search Engine,” Computer Networks, vol. 30, no. 1-7, pp. 107–117,
1998.
B. Hendrickson and T. G. Kolda, “Graph Partitioning Models for
Parallel Computing,” Parallel Computing, vol. 26, no. 12, pp. 1519–
1534, 2000.
L. Hyafil and R. Rivest, “Graph Partitioning and Constructing Optimal
Decision Trees are Polynomial Complete Problems,” IRIA – Laboratoire
de Recherche en Informatique et Automatique, Tech. Rep. 33, 1973.
M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some Simplified NPComplete Problems,” in Proceedings of the 6th ACM Symposium on
Theory of Computing, ser. STOC ’74. ACM, 1974, pp. 47–63.
T. N. Bui and C. Jones, “Finding Good Approximate Vertex and Edge
Partitions is NP-Hard,” IPL, vol. 42, no. 3, pp. 153–159, 1992.
P. Sanders and C. Schulz, “Distributed Evolutionary Graph Partitioning,” in Proc. of the 12th Workshop on Algorithm Engineering and
Experimentation (ALENEX’12), 2012, pp. 16–29.
H. Meyerhenke, P. Sanders, and C. Schulz, “Partitioning Complex
Networks via Size-constrained Clustering,” in Proc. of the 13th Int.
Symp. on Experimental Algorithms, ser. LNCS. Springer, 2014.
K. Schloegel, G. Karypis, and V. Kumar, “Graph Partitioning for High
Performance Scientific Simulations,” in The Sourcebook of Parallel
Computing, 2003, pp. 491–541.
C. Bichot and P. Siarry, Eds., Graph Partitioning. Wiley, 2011.
A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, “Recent
Advances in Graph Partitioning,” in Algorithm Engineering – Selected
Topics, to app., ArXiv:1311.3144, 2014.

[11]

[12]
[13]

[14]

[15]

[16]
[17]
[18]

[19]

[20]

[21]

[22]
[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]
[31]

[32]

[33]
[34]

R. V. Southwell, “Stress-Calculation in Frameworks by the Method of
“Systematic Relaxation of Constraints”,” Proc. of the Royal Society of
London, vol. 151, no. 872, pp. 56–95, 1935.
B. Hendrickson, “Chaco: Software for Partitioning Graphs,” http://www.
cs.sandia.gov/~bahendr/chaco.html.
C. Walshaw and M. Cross, “JOSTLE: Parallel Multilevel GraphPartitioning Software – An Overview,” in Mesh Partitioning Techniques
and Domain Decomposition Techniques, 2007, pp. 27–58.
G. Karypis and V. Kumar, “A Fast and High Quality Multilevel
Scheme for Partitioning Irregular Graphs,” SIAM Journal on Scientific
Computing, vol. 20, no. 1, pp. 359–392, 1998.
B. Monien, R. Preis, and R. Diekmann, “Quality Matching and Local
Improvement for Multilevel Graph-Partitioning,” Parallel Computing,
vol. 26, no. 12, pp. 1609–1634, 2000.
F. Pellegrini, “Scotch Home Page,” http://www.labri.fr/pelegrin/scotch.
A. Abou-Rjeili and G. Karypis, “Multilevel Algorithms for Partitioning
Power-Law Graphs,” in Proc. of 20th IPDPS, 2006.
H. Meyerhenke, B. Monien, and S. Schamberger, “Accelerating Shape
Optimizing Load Balancing for Parallel FEM Simulations by Algebraic
Multigrid,” in Proc. of 20th IPDPS, 2006.
C. Chevalier and I. Safro, “Comparison of Coarsening Schemes for
Multilevel Graph Partitioning,” in Proceedings of the 3rd International
Conference on Learning and Intelligent Optimization, ser. LNCS, vol.
5851, 2009, pp. 191–205.
I. Safro, P. Sanders, and C. Schulz, “Advanced Coarsening Schemes
for Graph Partitioning,” in Proceedings of the 11th International Symposium on Experimental Algorithms (SEA’12), ser. LNCS, vol. 7276.
Springer, 2012, pp. 369–380.
G. Karypis and V. Kumar, “Parallel Multilevel k-way Partitioning
Scheme for Irregular Graphs,” in Proceedings of the ACM/IEEE Conference on Supercomputing’96, 1996.
C. Chevalier and F. Pellegrini, “PT-Scotch,” Parallel Computing, vol. 34,
no. 6-8, pp. 318–331, 2008.
M. Holtgrewe, P. Sanders, and C. Schulz, “Engineering a Scalable
High Quality Graph Partitioner,” Proc. of the 24th Int. Parallal and
Distributed Processing Symposium, pp. 1–12, 2010.
H. Meyerhenke, “Shape optimizing load balancing for mpi-parallel
adaptive numerical simulations,” in Proc. of the 10th DIMACS Implementation Challenge – Graph Partitioning and Graph Clustering, ser.
Cont. Mathematics. AMS, 2013.
Y. Tian, A. Balmin, S. A. Corsten, S. Tatikonda, and J. McPherson,
“From" think like a vertex" to" think like a graph,” Proc. of the VLDB
Endowment, vol. 7, no. 3, 2013.
U. N. Raghavan, R. Albert, and S. Kumara, “Near Linear Time
Algorithm to Detect Community Structures in Large-Scale Networks,”
Physical Review E, vol. 76, no. 3, 2007.
J. Ugander and L. Backstrom, “Balanced Label Propagation for Partitioning Massive Graphs,” in 6’th Int. Conf. on Web Search and Data
Mining (WSDM’13). ACM, 2013, pp. 507–516.
F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and
S. Haridi, “JA-BE-JA: A Distributed Algorithm for Balanced Graph
Partitioning,” in 7th International Conference on Self-Adaptive and SelfOrganizing Systems. IEEE, 2013, pp. 51–60.
S. Kirmani and P. Raghavan, “Scalable Parallel Graph Partitioning,” in
International Conference for High Performance Computing, Networking, Storage and Analysis (SC’13). ACM, 2013, p. 51.
P. Sanders and C. Schulz, “KaHIP – Karlsruhe High Qualtity Partitioning Homepage,” http://algo2.iti.kit.edu/documents/kahip/index.html.
——, “Think Locally, Act Globally: Highly Balanced Graph Partitioning,” in Proc. of the 12th Int. Symp. on Experimental Algorithms
(SEA’13), ser. LNCS. Springer, 2013.
A. J. Soper, C. Walshaw, and M. Cross, “A Combined Evolutionary
Search and Multilevel Optimisation Approach to Graph-Partitioning,”
Journal of Global Optimization, vol. 29, no. 2, pp. 225–241, 2004.
C. Walshaw, “Multilevel Refinement for Combinatorial Optimisation
Problems,” Annals of OR, vol. 131, no. 1, pp. 325–372, 2004.
P. Sanders and C. Schulz, “Engineering Multilevel Graph Partitioning
Algorithms,” in Proc. of the 19th European Symp. on Algorithms, ser.
LNCS, vol. 6942. Springer, 2011, pp. 469–480.

[35]

[36]

[37]
[38]

[39]
[40]
[41]
[42]

[43]

[44]

[45]

C. Walshaw and M. Cross, “Mesh Partitioning: A Multilevel Balancing
and Refinement Algorithm,” SIAM Journal on Scientific Computing,
vol. 22, no. 1, pp. 63–80, 2000.
D. A. Bader, H. Meyerhenke, P. Sanders, C. Schulz, A. Kappes, and
D. Wagner, “Benchmarking for Graph Clustering and Partitioning,” in
Encyclopedia of Social Network Analysis and Mining, to appear.
T. Davis, “The University of Florida Sparse Matrix Collection.”
P. Boldi and S. Vigna, “The WebGraph framework I: Compression
techniques,” in Proc. of the 13th Int. World Wide Web Conference
(WWW 2004). Manhattan, USA: ACM Press, 2004, pp. 595–601.
J. Leskovec, “Stanford Network Analysis Package (SNAP).”
D. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Eds., Proc. of the
10th DIMACS Impl. Challenge, ser. Cont. Mathematics. AMS, 2012.
U. o. M. Laboratory of Web Algorithms, “Datasets.”
S. Salihoglu and J. Widom, “GPS: A Graph Processing System,” in
Proce. of the 25th Int. Conf. on Scientific and Statistical Database
Management, ser. SSDBM. ACM, 2013, pp. 22:1–22:12.
G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser,
and G. Czajkowski, “Pregel: a system for large-scale graph processing,”
in Proc. of Int. Conf. on Management of Data, ser. SIGMOD’10. ACM,
2010, pp. 135–146.
Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M.
Hellerstein, “Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud,” Proc. VLDB Endow., vol. 5, no. 8,
pp. 716–727, Apr. 2012.
M. Ovelgönne and A. Geyer-Schulz, “An Ensemble Learning Strategy
for Graph Clustering,” in Graph Partitioning and Graph Clustering 10th DIMACS Implementation Challenge Workshop, ser. Contemporary
Mathematics, vol. 588, 2013, pp. 187–206. [Online]. Available:
http://www.ams.org/books/conm/588/11701

A PPENDIX

11

TABLE III.

AVERAGE PERFORMANCE ( CUT AND RUNNING TIME ) AND BEST RESULT ACHIEVED BY DIFFERENT PARTITIONING ALGORITHMS . R ESULTS
ARE FOR THE CASE k = 32. A LL TOOLS USED 32 PE S OF MACHINE A. R ESULTS INDICATED BY A * MEAN THAT THE AMOUNT OF MEMORY NEEDED BY
THE PARTITIONER EXCEEDED THE AMOUNT OF MEMORY AVAILABLE ON THAT MACHINE WHEN 32 PE S ARE USED (512GB RAM). T HE PAR M ETIS RESULT
ON ARABIC HAS BEEN OBTAINED USING 15 PE S ( THE LARGEST NUMBER OF PE S SO THAT PAR M ETIS COULD SOLVE THE INSTANCE ).

algorithm
graph
amazon
eu-2005
youtube
in-2004
packing
enwiki
channel
hugebubbles
nlpkkt240
uk-2002
del26
rgg26
arabic-2005
sk-2005
uk-2007

avg. cut
253 568
974 279
918 520
34 445
349 000
32 539 098
934 264
28 844
7 296 962
2 636 838
167 208
423 643
*4 095 660
*
*

ParMetis
best cut
249 071
951 537
916 657
32 711
343 611
32 279 759
919 975
28 443
7 217 145
2 603 610
165 361
419 911
*3 993 166
*
*

t[s]
0.62
33.28
10.41
4.76
0.28
364.88
0.63
4.98
17.09
193.48
23.04
8.14
*1 414.83
*
*

avg. cut
235 614
1 218 484
951 591
26 618
338 458
33 464 700
989 570
27 832
8 048 555
1 710 106
153 835
356 589
3 309 602
58 107 145
5 682 545

12

Fast
best cut
231 169
1 154 916
936 333
25 819
335 732
33 256 794
983 211
27 607
7 987 330
1 677 872
152 889
352 749
2 648 126
46 972 182
5 114 349

t[s]
3.20
3.30
13.86
1.97
24.65
787.41
26.23
117.72
104.96
33.44
274.75
125.07
45.40
693.91
223.68

avg. cut
224 550
1 089 613
905 330
23 795
318 242
33 358 352
932 175
25 358
7 770 995
1 635 757
145 902
326 743
2 372 631
34 858 430
4 952 631

Eco
best cut
222 450
1 010 128
889 941
22 371
315 684
32 579 351
927 128
25 102
7 726 512
1 610 979
145 191
323 997
2 178 837
29 868 523
4 779 495

t[s]
81.83
79.87
137.61
73.22
92.55
989.20
100.86
342.75
274.67
218.27
859.33
376.27
251.38
2 183.10
794.87

