Skip to Main content Skip to Navigation
New interface
Conference papers

Balanced graph edge partition

Abstract : Balanced edge partition has emerged as a new approach to partition an input graph data for the purpose of scaling out parallel computations, which is of interest for several modern data analytics computation platforms, including platforms for iterative computations, machine learning problems, and graph databases. This new approach stands in a stark contrast to the traditional approach of balanced vertex partition, where for given number of partitions, the problem is to minimize the number of edges cut subject to balancing the vertex cardinality of partitions. In this paper, we first characterize the expected costs of vertex and edge partitions with and without aggregation of messages, for the commonly deployed policy of placing a vertex or an edge uniformly at random to one of the partitions. We then obtain the first approximation algorithms for the balanced edge-partition problem which for the case of no aggregation matches the best known approximation ratio for the balanced vertex-partition problem, and show that this remains to hold for the case with aggregation up to factor that is equal to the maximum in-degree of a vertex. We report results of an extensive empirical evaluation on a set of real-world graphs, which quantifies the benefits of edge- vs. vertex-partition, and demonstrates efficiency of natural greedy online assignments for the balanced edge-partition problem with and with no aggregation.
Document type :
Conference papers
Complete list of metadata
Contributor : Marc Lelarge Connect in order to contact the contributor
Submitted on : Wednesday, December 3, 2014 - 5:48:19 PM
Last modification on : Friday, November 18, 2022 - 9:25:46 AM



Florian Bourse, Lelarge Marc, Milan Vojnovic. Balanced graph edge partition. KDD '14 - 20th ACM SIGKDD international conference on Knowledge discovery and data mining, Aug 2014, New York, United States. pp.1456-1465, ⟨10.1145/2623330.2623660⟩. ⟨hal-01090593⟩



Record views