VLDB2012_Answering pattern match queries in large graph databases via graph embedding_Lei Zou · Lei Chen · M. Tamer Özsu · Dongyan Zhao.pdf

樱木花道

146

25页

0次

2022-09-21

免费下载

Noname manuscript No.

(will be inserted by the editor)

Answering Pattern Match Queries in Large Graph

Databases Via Graph Embedding

∗

Lei Zou · Lei Chen · M. Tamer

Ozsu · Dongyan Zhao

the date of receipt and acceptance should be inserted later

Abstract The growing popularity of graph databases

has generated interesting data management problems,

such as subgraph search, shortest path query, reacha-

bility veriﬁcation, and pattern matching. Among these,

a pattern match query is more ﬂexible compared to

a subgraph search and more informative compared to

a shortest path or a reachability query. In this paper,

we address di stance-based pattern match queries over a

large data graph G. Due to the huge search space, we

adopt a ﬁlter-and-reﬁne framework to answer a pattern

match query over a large graph. We ﬁrst ﬁnd a set of

candidate matches by a graph embedding technique and

then evaluate these to ﬁnd the exact matches. Extensive

experiments conﬁrm the superiority of our m ethod.

1 Introduction

As one of the most popular and powerful representa-

tions, graphs have been used to model many appli-

cation data, such as social networks, biological net-

works, and World Wide Web. In order to conduct eﬀec-

tive analysis over graphs, various types of queries have

Extended version of paper “Distance-Join: Pattern Match Query

In a Large Graph Database” that was presented in the Proceed-

ing of 35th International Conference on Very Large Databases

(VLDB), pages 886-897, 2009.

Lei Zou , Dongyan Zhao

Peking University, Beijing, China

E-mail: {zoulei,zdy}@icst.pku.edu.cn

Lei Chen

Hong Kong University of Science and Technology, Hong Kong

E-mail: leichen@cse.ust.hk

M. Tamer

Ozsu

University of Waterloo, Waterloo, C anada

E-mail: Tamer.Ozsu@uwaterloo.ca

been investigated, such as shortest path query [9,18,

7], reachability query [9,29,27,5], and subgraph query

[24,34,6,17,31,36,15,25]. These are all interesting, but

in this paper, we focus on pattern match queries, since

they are more ﬂexible than subgraph queries and more

informative than simple shortest path or reachability

queries. Speciﬁcally, a pattern match query searches

over a large lab eled graph to look for the existence

of a pattern graph in a large data graph. A pattern

match query is diﬀerent from subgraph search in that

it only speciﬁes the vertex lab els and connection con-

straints between vertices. In other words, a pattern

match query emphasizes the connectivity between la-

beled vertices rather than checking subgraph isomor-

phism as subgraph search does.

In this paper, we propose a distance-based pattern

match query, which is deﬁned as follows: given a large

graph G, a query graph Q with n vertices and a param-

eter δ, n vertices in G match Q iﬀ: (1) these n vertices

in G have the same labels as the corresponding vertices

in Q, and (2) for any two adjacent vertices v

and v

in Q (i.e., there is an edge between v

and v

in Q and

1 ≤ i, j ≤ n), the distance between two corresponding

vertices in G is no larger than δ. We need to ﬁnd all

matches of Q in G. In this work, we use the shortest

path to measure the distance between two vertices, but

our approach is not restricted to this distance function,

and can be applied to other metric distance functions

as well. Note that, for ease of presentation, we use the

term “pattern match” instead of “distance-based pat-

tern match” in the rest of this paper, when the context

is clear.

A key problem of pattern match queries is huge

search space. Given a query Q with n vertices, for each

vertex v

in Q, we ﬁrst ﬁnd a list of vertices in data

graph G that have the same labels as that of v

. Then,

for each pair of adjacent vertices v

and v

in Q, we

need to ﬁnd all matching pairs in G whose distances

are less than δ. This is called an edge query. To an-

swer an edge query, we need to conduct a distance-

based join operation between two lists of matching ver-

tices correspondin g to v

and v

in G. Therefore, ﬁnding

pattern Q in G requires a sequence of di stance-based

join operations, which is very costly for large graphs.

In order to answer patte rn match queries eﬃciently, we

adopt the ﬁlter-and-reﬁne framework. Speciﬁcally, we

need eﬃcient pruning strategies to reduce the search

space. Although many eﬀective pruning techniques have

been proposed for subgraph search (e.g., [24,34,6,17,

31,36,15,25]), they can not be applied to pattern match

queries since these pruning rules are based on the nec-

essary condition of subgraph isomorphism. We propose

a novel and eﬀective method to reduce the search space

signiﬁcantly. Speciﬁcally, we transform vertices into points

in a vector space via graph embedding methods, con-

verting a pattern match query into a distance-based

multi-way join problem over the vector space to ﬁnd

candidate matches. In order to reduce the join cost, we

propose several pruning rules to reduce the search space

further, and propose a cost model to guide the selection

of the join order to process multi-way join eﬃciently.

During the reﬁnement process, we adopt 2-hop dis-

tance label [9] to compute the shortest path distance

for each candidate match. Unfortunately, ﬁnding the

optimal 2-hop distance-aware labeling (i.e., one where

the size of 2-hop distance-aware labels is minimized) is

a NP-hard problem [9]. Although a heuristic method to

compute 2-hop distance-aware labels in a large directed

graph has been proposed [7], this method cannot work

well in a large undirected graph. We will d iscuss this

method in detail in Section 2. In this paper, we propose

a betweenness (Deﬁnition 3) estimation-based method

to guide 2-hop distance-aware center selection. Exten-

sive experiments on both real and synthetic datasets

conﬁrm the eﬃciency of our method.

To summarize, in this work, we make the following

contributions:

1) We propose a general framework for handling

pattern match queries over a large graph. Speciﬁcally,

we adopt a ﬁlter-and-reﬁne framework to answer pat-

tern match queries. During ﬁltering, we map vertices

into vectors via an embedding method and conduct

distance-based multi-way join over the vector space.

2) We design an eﬃcient distance-based join algo-

rithm (D-join for short) for an edge query in the con-

verted vector space, which well utilizes the block nes ted

loop join and hash join techniques to handle the high

dimensional vector space. We also develop an eﬀective

cost model to estimate the cost of each join operation,

based on which we can select the most eﬃcient join

order to reduce the cost of multi-way join.

3) In order to address the high complexity of of-

ﬂine processing, we propose a graph partitioning-based

method and bi-level version of D-join algorithm, called

bD-join.

4) In order to enable shortest path distance compu-

tation eﬃciently, we propose betweenness estimation-

based method to compute 2-hop distance labels in a

large graph.

5) In order to answer an approximate subgraph query

(Deﬁnition 9), we ﬁrst transform it into a distance-

based pattern match query. Then, we ﬁnd candidates by

D-join algorithm. Finally, for each candidate, we verify

whether it is an approximate subgraph match (Deﬁni-

tion 8).

6) Finally, we conduct extensive experiments with

real and synthetic data to evaluate the proposed ap-

proaches.

The rest of this paper is organized as follows. We

discuss the related work in Section 2. Our framework

is presented in Section 3. We propose betweenness esti-

mation-based method to compute 2-hop distance labels

in Section 4. The oﬄine process is discussed in Section

5. We discuss the neighbor area pruning technique in

Section 6, and a distance-based join algorithm for an

edge query and its cost model in Section 7. Section

7 also presents a distance-based multi-way join algo-

rithm for a pattern match query and join order selection

method. In Section 8, we propose a graph partition-

based method to reduce the cost of oﬄine processing

and the bD-join algorithm. In Section 9, we propose

a distance-join based solution to answer approximate

subgraph queries. We study our methods by experi-

ments in Section 10. Section 11 concludes this paper.

2 Background and Related Work

Let G = hV, Ei be a graph where V is the set of vertices

and E is the set of edges. Given two vertices u

and u

in G, a reachability query veriﬁes if there exists a path

from u

to u

, and a distance query returns the shortest

path distance between u

and u

[9]. These are well-

studied problems, with a numb er of vertex labeling-

based solutions [9]. A family of labeling techniques have

been prop osed to answer both reachability and distance

queries. A 2-hop labeling method over a large graph

G assigns to each vertex u ∈ V (G) a label L(u) =

(u), L

out

(u)), where L

(u), L

out

(u) ⊆ V (G). Ver-

tices in L

(u) and L

out

(u) are called centers. There are

two kinds of 2-hop lab eling: 2-hop reachability label-

ing (reachability labeling for short) and 2-hop distance

of 25

免费下载

关注

评论