Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent
复制标题
DOI：
10.14778/3324301.3324307
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Dmitrii Avdiukhin;S. Pupyrev;G. Yaroslavtsev
中科院分区：
文献类型：
--
作者：
Dmitrii Avdiukhin;S. Pupyrev;G. Yaroslavtsev
受将图分布在多台机器上的大规模图处理系统性能优化的推动，我们考虑平衡图划分问题。与之前的大多数工作相比，我们研究了需要根据多个权重函数进行平衡的多维变体。正如我们通过实验评估证明的那样，这种多维平衡对于实现典型分布式图处理工作负载的性能改进至关重要。我们针对多维平衡图划分问题提出了一种新的可扩展技术。它基于将随机投影梯度下降应用于目标的非凸连续松弛。我们展示了如何利用各种投影步骤方法在理论和实践中有效地实现新算法。对包含多达数千亿条边的大规模图的实验表明，与现有技术相比，我们的算法具有卓越的性能。
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 most of the previous work, we study the multi-dimensional variant in which balance according to multiple weight functions is required. As we demonstrate by experimental evaluation, such multi-dimensional balance is essential for achieving performance improvements for typical distributed graph processing workloads. We propose a new scalable technique for the multidimensional balanced graph partitioning problem. It 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 the projection step. Experiments with large-scale graphs containing up to hundreds of billions of edges indicate that our algorithm has superior performance compared to the state of the art.