TKDE 2021_Graph Algorithms with Partition Transparency_深算院.pdf

tinge

12页

3次

2023-09-13

免费下载

Graph Algorithms with Partition Transparency

Wenfei Fan Muyang Liu Ping Lu Qiang Yin

Abstract—Graph computations often have to be conducted in parallel on partitioned graphs. The choice of graph partitioning

strategies, however, has strong impact on the design of graph computation algorithms. A graph algorithm developed under edge-cut

partitions may not work correctly under vertex-cut, and vice versa. We often have to rewrite our algorithms when we switch from, e.g.,

edge-cut to vertex-cut. To cope with this, we propose a notion of partition transparency, such that graph algorithms are able to work

correctly under different partitions without changes and moreover, beneﬁt from recent hybrid partitions to speed up computations.

Furthermore, we identify conditions under which graph algorithms are guaranteed to be partition-transparent, in graph-centric and

vertex-centric models. We show that a variety of graph algorithms can be made partition-transparent. Using real-life and synthetic

graphs, we experimentally verify that partition-transparent algorithms compute correct answers under different partitions; better still,

under hybrid partitions these algorithms perform better than algorithms tailored for edge-cut and vertex-cut partitions in efﬁciency.

Index Terms—graph partition, partition transparency, graph-centric algorithms, vertex-centric algorithms

1 INTRODUCTION

To handle large-scale real-life graphs, it is often necessary to

conduct parallel computations on partitioned graphs. The

idea is to cut a large graph G into smaller fragments and

distribute the fragments to a cluster of processors (a.k.a.

workers), such that computations on G can be conducted in

parallel by the processors on their local fragments, subject

to message passing among different processors.

A variety of graph partitioning algorithms (a.k.a. parti-

tioners) have been developed. These partitioners are often

either edge-cut [8], [30], which evenly partitions vertices

and cuts edges, or vertex-cut [11], [25], [31], which evenly

partitions edges by replicating vertices. There have also been

recent work on hybrid partitioners, which cut both edges and

vertices [20], [14], [17], [52], [33], [9], [50], [43], to overcome

the limitations of edge-cut and vertex-cut partitions. It has

been shown that the hybrid partitioners often make graph

computations faster than edge-cut and vertex-cut.

The choice of a partitioning strategy has strong impact

on the performance of graph algorithms. Neither vertex-cut

nor edge-cut consistently outperforms the other for different

algorithms. Worse still, an algorithm developed under edge-

cut may not work correctly under vertex-cut, and vice versa.

Hence, when developing a parallel algorithm for a graph

computation problem, one has to decide in advance which

partitioning strategy to use. If the strategy picked does not

work well, we may want to switch to the other method,

but then we may have to rewrite our algorithms. Moreover,

algorithms developed for edge-cut and vertex-cut often

do not work correctly under hybrid partitions, and hence

cannot beneﬁt from the state-of-the-art hybrid partitioners.

• Wenfei Fan is with Shenzhen Institute of Computing Sciences, University

of Edinburgh, and BDBC, Beihang University

Email: wenfei@inf.ed.ac.uk.

• Muyang Liu is with University of Edinburgh

Email: muyang.liu@ed.ac.uk.

• Ping Lu (corresponding author) is with SKLSDE, Beihang University

Email: luping@buaa.edu.cn

• Qiang Yin is with Shanghai Jiao Tong University and Alibaba Group

Email: q.yin@sjtu.edu.cn

(a) Graph G

(b) Edge-cut

(d) Hybrid partition

Fig. 1: Graph partitions

Example 1: Consider the common neighbor problem (CN),

which computes the number of common neighbors for each

pair of vertices in a graph. It is widely used in link pre-

diction, product recommendation and fraud detection [35],

[16]. For a directed graph G = (V, E), where V is the

set of vertices and E is the set of edges, denote by Γ

(v)

(resp. Γ

−

(v)) the set of outgoing (resp. incoming) neighbors

of vertex v in V . To simplify the discussion, here we consider

common outgoing neighbors, i.e., given G, CN is to compute

CN(u, v) = |Γ

(u) ∩ Γ

(v)| for all pairs (u, v) ∈ V × V .

Consider graph G shown in Figure 1 and its partitions

, F

) and (F

, F

) under edge-cut (Figure 1(a)) and

vertex-cut (Figure 1(b)), respectively. Observe the follow-

ing. (1) Edge-cut partitioning cuts edges to generate vertex

disjoint fragments, e.g., {v

, v

} and {v

, v

}. A vertex

is assigned to only one fragment [8], [30] (colored in gray

in Figure 1), referred to as a master vertex; the others are

mirrors, e.g., v

in F

is a master vertex and v

in F

is a

mirror. Each master and all of its incident edges reside in the

same fragment. (2) In contrast, vertex-cut partitioning cuts

vertices to produce edge disjoint partitions. Thus all edges

incident to a master vertex may not be necessarily assigned

to the same fragment, e.g., v

is a master vertex in F

and

its edge set at F

does not include the edge (v

, v

), which

resides in fragment F

(see Figure 1(b)).

Algorithms developed for edge-cut partitions may not

work under vertex-cut partitions, and vice versa. To see

these, let us consider the following algorithms.

(1) Edge-cut. Under edge-cut, an algorithm A

for CN works

as follows. (a) For each master vertex v in a fragment F

it increases the local count CN

, v

) for each incoming

neighbor pair (v

, v

) of v. (b) After this, A

collects the

local CN counts from all fragments, and computes their sum

for all vertex pairs (v

, v

). It returns the aggregate values

as the ﬁnal result. One can verify that A

correctly returns

count CN(v

, v

) = 2 in the partition of Figure 1(a). Indeed,

CN(v

, v

) is set to be 1 after step (a) in each fragment, and

is then increased to 2 after the aggregation in step (b).

However, A

erroneously returns CN(v

, v

)=1 when it

runs on the vertex-cut partition of Figure 1(b). That is the

count in fragment F

due to the common neighbor v

. It

misses the common neighbor v

for v

and v

since the edge

, v

) is missing for master vertex v

in fragment F

(2) Vertex-cut. Under vertex-cut, an algorithm A

works in

three steps. (a) It ﬁrst computes the local count CN for each

master vertex v. (b) It then collects all incoming edges of

v from other fragments, and increases the CN counts using

these received edges. Denote by Γ

−

∆

(v) the set of incoming

neighbors of v adjacent to received edges. Then A

increases

CN(v

, v

) for each v

∈ Γ

−

(v) and v

∈ Γ

−

∆

(v), where

is a vertex on a received edge. Note that A

has all

incoming edges Γ

−

(v) of v after collecting edges from other

fragments. (c) Finally, it collects and aggregates local CN

counts from all fragments. One can verify that A

correctly

computes CN given the vertex-cut partition in Figure 1(b).

For instance, A

ﬁrst increases the CN(v

, v

) in fragment

to 1, and then increases it to 2 after receiving (v

, v

In contrast, algorithm A

does not work correctly when

given the edge-cut partition of Figure 1(a). To see this,

observe that A

would return CN(v

, v

) = 4, which is

wrong. This is because there exist duplicated edges in the

edge-cut partition (e.g., (v

, v

) and (v

, v

) are in both F

and F

); after collecting such edges from other fragments,

counts CN(v

, v

) twice for each duplicated edge.

The problem with algorithm A

is that it assumes a

master vertex to have all its edges in its local fragment,

which is not true under vertex-cut. Algorithm A

gets

wrong answers on edge-cut partitions due to the duplicated

edges, which do not exist under vertex-cut partitions.

(3) Hybrid partition. For the same reason, neither algorithm

nor A

works under the hybrid partition (F

, F

) of

Figure 1(c). More speciﬁcally, master vertex v

in fragment

does not have all of its incident edges in F

, and edge

, v

) replicates in F

and F

. As a result, A

ﬁnds

CN(v

, v

)=1, and A

gets CN(v

, v

)=3. None is correct. 2

This example gives rise to several questions. Is it possible

to make an algorithm A transparent to different partitions

of a graph G, i.e., it works correctly no matter how G is

partitioned? If so, we do not have to rewrite our algorithms

when, e.g., switching from edge-cut partitions to vertex-

cut; and better still, we can capitalize on the state-of-the-art

hybrid partitions to speed up graph computations. Another

question concerns under what conditions algorithms are

transparent to different partitions? Moreover, is it within the

reach in practice to develop transparent algorithms?

Contributions & organization. This paper aims to answer

the questions above, all in the afﬁrmative. We consider

parallel graph-centric [23], [7] and vertex-centric [25], [36]

algorithms, which will be reviewed in Section 2.

(1) Partition transparency (Section 3). We introduce a notion

of partition transparency for parallel graph algorithms. A

partition-transparent algorithm A works correctly under both

edge-cut and vertex-cut without requiring any change to A.

Better yet, they work correctly under hybrid partitions, and

hence are able to reduce the cost of graph computations by

leveraging, e.g., application-driven partitions [20].

(2) Transparency conditions (Section 4). We identify conditions

for algorithm A to be guaranteed partition-transparent, i.e., A

works correctly under edge-cut, vertex-cut and hybrid par-

titions without requiring any change to A. We provide such

conditions for both graph-centric programs of GRAPE [23]

and vertex-centric GAS programs of PowerGraph [25].

(3) Transparent algorithms (Section 5). We show that partition-

transparent algorithms are within the reach of a variety of

problems, including common neighbor (CN), single source

shortest path (SSSP), weakly connected component (WCC),

PageRank (PR), strongly connected components (SCC), and

maximum cliques (MaxClique). We show that these algo-

rithms work correctly no matter what partitions are given.

(4) Experimental study (Section 6). Using real-life and syn-

thetic graphs, we verify the effectiveness and efﬁciency of

partition-transparent algorithms. We ﬁnd the following. (a)

Transparent algorithms work correctly regardless of what

partitions are adopted, without changes, in both graph-

centric PIE mode and vertex-centric GAS model. (b) Trans-

parent algorithms A under hybrid partitions of [20] are

on average 2.3 times faster than non-transparent B under

vertex-cut or edge-cut, while B may not work correctly

under hybrid partitions. (c) Even when all algorithms run

under vertex-cut and edge-cut, transparent A performs

comparably to B developed for vertex-cut and edge-cut.

The performance gap is less than 5.8%. (d) Under hybrid

partitions, transparent algorithms scale well with both the

size of graphs and the number of processors used, e.g.,

transparent WCC and PR take on average 66.5s on graphs

of 500 million nodes and 6 billion edges with 90 processors.

Related work. This paper extends its conference version [20]

as follows. (1) While [20] targets hybrid partitioners, this

paper focuses on partition-transparent algorithms. We have

substantially reorganized and rewritten a large part of the

paper, from motivation and examples to technical discus-

sions (Sections 1–7). (2) We have provided a detailed anal-

ysis of partition transparency conditions for graph-centric

algorithms, from examples to proofs; we have also devel-

oped new transparency conditions for vertex-centric GAS

programs (Section 4). (3) We have developed new partition-

transparent algorithms as proof of concept (Section 5: SSSP,

WCC, SCC and MaxClique). (4) The experimental study

is almost entirely new, and evaluates partition-transparent

algorithms with more cases and datasets (Section 6).

We discuss the other related work as follows.

A host of graph partitioners have been developed for

edge-cut and vertex-cut (see [13], [10] for surveys). Edge-cut

(resp. vertex-cut) aims to (a) partition vertices (resp. edges)

into disjoint subsets of even sizes for load balancing, and

(b) reduce replicated edges (resp. vertices). Popular edge-

cut partitioners include exact algorithms [8], [32] such as

METIS [28], [29] and its parallel version ParMETIS [27], as

of 12

免费下载

yashandb paper 崖山深算院 tkde

关注

评论