  Motivated by performance optimization of large-scale graph processing systems
that distribute the graph across multiple machines, we consider the balanced
graph partitioning problem. Compared to the previous work, we study the
multi-dimensional variant when balance according to multiple weight functions
is required. As we demonstrate by experimental evaluation, such
multi-dimensional balance is important for achieving performance improvements
for typical distributed graph processing workloads. We propose a new scalable
technique for the multidimensional balanced graph partitioning problem. The
method is based on applying randomized projected gradient descent to a
non-convex continuous relaxation of the objective. We show how to implement the
new algorithm efficiently in both theory and practice utilizing various
approaches for projection. Experiments with large-scale social networks
containing up to hundreds of billions of edges indicate that our algorithm has
superior performance compared with the state-of-the-art approaches.
