Network Performance Aware Graph Partitioning for Large Graph Processing Systems in the Cloud - Large Scale and Big Data: Processing and Management - page 246

Hierarchical combination

Data transfer to the target
vertex

0 1 2 3 4 5 6 7

FIGURE 7.5 Hierarchical combination according to the partition sketch of the machine
graph of eight machines.

the partition sketch of the machine graph. With the hierarchical combination optimi-
zation, the data transfer on the low-bandwidth connection is reduced.

Example

Figure 7.5 illustrates one example of performing hierarchical combination on
eight machines. Suppose each machine holds one graph partition and machine
0 needs to read data from other machines. Note that the partition sketch of
the machine graph has captured the network bandwidth unevenness. After
local combination on each machine, the first-level combination between two
machines (for example, between machines 6 and 7) are performed, and the
result is stored on a representative machine. Let us assume machines 2, 4, and 6
are the representative machines at the first-level combination. Further combina-
tion is performed on the representative machines. Finally, all the partial results
are sent to machine 0. On the low-bandwidth connections between machine 0
and machine i (4 ≤ i ≤ 7), hierarchical combination has only one data transfer
for the partial results, compared with four in the baseline implementation with
local combination.

7.7 RELATED WORK ON GRAPH PARTITIONING
In addition to the recent work on network performance aware partitioning, a large
number of graph partitioning techniques have been proposed. In this section, we
provide a review of general graph partitioning algorithms and then highlight some
existing distributed graph partitioning algorithms.
Graph partitioning is important not only in emerging applications like Web and
social graphs, as discussed in previous sections, but also traditional applications such
as circuit placement and matrix factorization. The problem is NP-hard for general
graphs [15,29]. There have been many studies on graph partitioning problems, which
we can divide into five major categories: geometric methods [11,26,60], spectral
methods [25,71], multilevel methods [44,46], metaheuristic-based approaches [51],
and streaming graph partitioning [3,72,74]. We also refer the readers to two compre-
hensive surveys [28,51] for more related work on graph partitioning.