Revolver: Vertex-Centric Graph Partitioning Using Reinforcement Learning

Big graph analytics is gaining a widespread momentum across different fields, including biology, computer vision, social networks, recommendation systems and transportation logistics, to mention just a few. Distributed systems for graph analytics are utilized as a mean to process big graphs. To distribute and balance computation and communication loads within a distributed graph analytics system, graph partitioning algorithms can be leveraged. In this paper, we propose Revolver, a machine learning-based graph partitioning algorithm. In particular, Revolver uses reinforcement learning and label propagation to efficiently and effectively carry out the task of graph partitioning. It employs a vertex-centric approach where each vertex in a graph is associated with an autonomous agent responsible for assigning a suitable partition to the vertex. In addition, it uses label propagation to evaluate the decency of partitioning. Evaluation results show that Revolver can produce highly balanced and localized partitions compared to three popular and state-of-the-art graph partitioning algorithms.