A Mixed-State Streaming Edge Partitioning based on Combinatorial Design

Graph partitioning is crucial in distributed graph computing systems, while impacting load balancing and communication between machines. To cope with the soaring scale of graphs, the streaming model has shown promising performance in graph partitioning. Although streaming model can deal with the bottleneck of memory usage for large-scale graphs, existing streaming partitioning algorithms not only lack sufficient quality but also cannot provide theoretical boundaries for graph partitioning. In addition, most streaming partitioning algorithms are sensitive to the order of edge streaming. In this paper, we model the edge partitioning problem as a combinatorial design problem, and provide a tight theoretical boundary. Based on the balanced edge partitioning design, we proposed a mixed-state streaming edge partitioning algorithm, which can generate high-quality graph partitions by mapping matrix and use the historical partition information to further optimize the partition quality and load balance. The experiments show that our proposed algorithm reduces partitioning time by more than half compared to the mainstream HDRF algorithm while maintaining load balance, and improves partitioning quality by about three times.