Simulated Annealing for Edge Partitioning

Description

In distributed graph computation, graph partitioning is an important preliminarystep, because the computation time can significantly depend on how the graph has been split amongthe different executors. In this paper, we propose a framework for distributed edge partitioningbased on simulated annealing. The framework can be used to optimize a large family of partitioningmetrics. We provide sufficient conditions for convergence to the optimum as well as discuss whichmetrics can be efficiently optimized in a distributed way. We implemented our partitioners inApache GraphX and performed a preliminary comparison with JA-BE-JA-VC , a state-of-the-artpartitioner that inspired our approach. We show that our approach can provide improvements,but further research is required to identify suitable metrics to optimize as well as to design a moreefficient exploration phase for our algorithm without sacrificing convergence properties.

Additional details