  Graph partitioning is an important preprocessing step to distributed graph
processing. In edge partitioning, the edge set of a given graph is split into
$k$ equally-sized partitions, such that the replication of vertices across
partitions is minimized. Streaming is a viable approach to partition graphs
that exceed the memory capacities of a single server. The graph is ingested as
a stream of edges, and one edge at a time is immediately and irrevocably
assigned to a partition based on a scoring function. However, streaming
partitioning suffers from the uninformed assignment problem: At the time of
partitioning early edges in the stream, there is no information available about
the rest of the edges. As a consequence, edge assignments are often driven by
balancing considerations, and the achieved replication factor is comparably
high. In this paper, we propose 2PS, a novel two-phase streaming algorithm for
high-quality edge partitioning. In the first phase, vertices are separated into
clusters by a lightweight streaming clustering algorithm. In the second phase,
the graph is re-streamed and edge partitioning is performed while taking into
account the clustering of the vertices from the first phase. Our evaluations
show that 2PS can achieve a replication factor that is comparable to
heavy-weight random access partitioners while inducing orders of magnitude
lower memory overhead.
