  Balanced partitioning is often a crucial first step in solving large-scale
graph optimization problems, e.g., in some cases, a big graph can be chopped
into pieces that fit on one machine to be processed independently before
stitching the results together. In other cases, links between different parts
may show up in the running time and/or network communications cost. We study a
distributed balanced partitioning problem where the goal is to partition the
vertices of a given graph into k pieces so as to minimize the total cut size.
Our algorithm is composed of a few steps that are easily implementable in
distributed computation frameworks. The algorithm first embeds nodes of the
graph onto a line, and then processes nodes in a distributed manner guided by
the linear embedding order. We examine various ways to find the first
embedding, e.g., via a hierarchical clustering or Hilbert curves. Then we apply
four different techniques including local swaps, minimum cuts on the boundaries
of partitions, as well as contraction and dynamic programming. As our empirical
study, we compare the above techniques with each other, and also to previous
work in distributed graph algorithms, e.g., a label propagation method, FENNEL
and Spinner. We report our results both on a private map graph and several
public social networks, and show that our results beat previous distributed
algorithms: e.g., compared to the label propagation algorithm, we report an
improvement of 15-25% in the cut value. We also observe that our algorithms
allow for scalable distributed implementation for any number of partitions.
Finally, we apply our techniques for the Google Maps Driving Directions to
minimize the number of multi-shard queries with the goal of saving in CPU
usage. During live experiments, we observe an ~40% drop in the number of
multi-shard queries when comparing our method with a standard geography-based
method.
