Online Partitioning of Multi-Labeled Graphs∗

Graph partitioning is an old problem that is finding renewed in-terest in the era of big, complex datasets and parallel computing frameworks that can benefit from a proper partitiong of big graph data across multiple nodes in a cluster. In this paper we look into a specific instance of the problem termed online graph partitioning that addresses the need to partition large graphs that do not fit in main memory. A neglected aspect of modern graph datasets is that real graphs have labels! Node labels may, for instance, correspond to categorical attributes (such as country, profession, participating groups, etc.) of the entities depicted by the vertices of the graph. Edge labels may represent different relationship types (e.g. “friend-of”, “likes”, etc.). In this work we first revisit the formulation of the graph partitioning problem for graphs with labels on both nodes and edges. We introduce “relation-cut”, as a new metric that ex-tends the traditional “edge-cut ” metric used in graph partitioning in order to take into account the existence of different edge-types. Then, we combine this metric with a novel “label-cut ” metric that takes into consideration the displacement of related nodes with sim-ilar labels across partitions. In our experiments we adapt two recent online partitioning algorithms for the new proposed metric and pro-vide a thorough evaluation on a variety of real and synthetic graphs. Our experiments demonstrate that the proposed technique balances the generated cuts on both relations and labels on the resulting par-titions. 1