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.

我们研究了多维平衡图分区问题，提出一种基于随机投影梯度下降的可扩展技术来解决该问题，并在实验中表明该方法在大规模图处理时具有卓越的性能表现。