SQBC:Anefficientsubgraphmatchingmethodoverlargeanddensegraphs资源-CSDN文库

80 浏览量 2021-02-21 07:46:32 上传评论收藏 481KB PDF 举报

在现代生物学和计算机科学的研究中，许多复杂的网络可以被视为大型且密集的图结构。这些图结构需要有效的子图匹配方法来应对日益增长的计算需求。本文提出的SQBC（Subgraph Query Based on Clique Feature）技术，是一种新的子图查询方法，它通过精心设计的团特征编码与已有的顶点编码相结合，作为基本的索引单元来减少搜索空间。此外，SQBC基于团特征优化了子图同构性测试。通过在生物网络、RDF数据集和合成图上的广泛实验表明，SQBC在大型且密集的数据图上尤其具有显著的优势，其效果和效率均优于其他流行的竞争方法。关键词中提到了算法、大型网络、数据库、图论、子图同构以及索引策略。这些是研究大型且密集图结构的子图匹配问题所涉及的关键知识点。具体到知识点的详解，我们可以将相关知识点归纳如下： 1. 子图匹配问题（Subgraph Matching Problem）：子图匹配是图数据库和图挖掘中的一个核心问题，它涉及到在大型图中寻找与某个特定查询图相匹配的图结构。该问题在生物学、社交网络、网络安全性等多个领域都有广泛的应用。 2. 团特征（Clique Feature）：团是图论中的一个概念，指的是在一个图中一个完全连通的子图，即图中任意两个不同的顶点都相连。利用团特征进行子图匹配可以显著减少匹配过程中需要考虑的候选子图数量。 3. 索引策略（Index Strategy）：在图的查询和处理中，索引策略是提高效率的关键技术之一。SQBC采用的索引单元结合了团特征和顶点编码，目的是通过减少搜索空间来提高子图匹配的效率。 4. 子图同构测试（Subgraph Isomorphism Testing）：确定一个图是否能够与另一个图的结构相匹配的过程称为子图同构测试。这是一个NP完全问题，在SQBC方法中进行了优化处理。 5. 大型且密集图（Large and Dense Graphs）：随着生物学和计算机科学的发展，产生了许多复杂网络的表示，它们通常可以看作是大型且密集的图。在这些图上进行有效的子图匹配是非常必要的，但也是具有挑战性的。 6. 大型网络（Large Networks）：在图论和数据库理论中，大型网络的研究受到广泛关注，因为它们需要处理大规模的图数据，并需要高效的算法和数据结构来支持查询、分析等操作。 7. 数据库（Database）：在数据库领域，特别是图数据库领域，如何存储和查询大规模图结构数据是一个重要问题。SQBC方法在数据库环境下对于图数据的查询和匹配提供了解决方案。 8. 图论（Graph Theory）：图论是数学的一个分支，它研究由边连接的顶点组成的图的性质。SQBC方法正是建立在图论的基础上，对图的结构特性进行分析和匹配。 9. 算法（Algorithms）：算法是解决问题的一系列步骤。SQBC方法提出了一种新的算法来优化子图匹配过程，提高效率。通过对这些关键词的深入理解和挖掘，我们可以更清晰地认识到SQBC方法的研究背景、目的、方法论和技术路径。SQBC方法针对的是大规模和复杂网络中的子图匹配问题，这在当前信息技术的背景下具有重要的理论和实践意义。通过精心设计的团特征编码与顶点编码结合的索引单元，结合对子图同构测试的优化，SQBC不仅提高了子图匹配的有效性，也提升了处理的效率，尤其是在大型且密集的图数据处理中。

资源推荐

资源详情

资源评论

SQBC: An efﬁcient subgraph matching method over

large and dense graphs

Weiguo Zheng

†

, Lei Zou

†

, Xiang Lian

⊥

, Huaming Zhang

∗

, Wei Wang

Dongyan Zhao

†

Peking University, No.5 Yiheyuan Road Haidian District, Beijing, P.R.China

⊥

Department of Computer Science, University of Texas - Pan American, 1201 West University Drive Edinburg, TX

78539, USA

∗

Computer Science Department, University of Alabama in Huntsville, Huntsville, AL 35899, USA

Department of Electronic Technology, Engineering University of CAPF, Xi’an, P.R.China

Abstract

Recent progress in biology and computer science have generated many compli-

cated networks, most of which can be modeled as large and dense graphs. Devel-

oping effective and efﬁcient subgraph match methods over these graphs is urgent,

meaningful and necessary. Although some excellent exploratory approaches have

been proposed these years, they show poor performances when the graphs are

large and dense. This paper presents a novel Subgraph Query technique Based

on Clique feature, called SQBC, which integrates the carefully designed clique

encoding with the existing vertex encoding [40] as the basic index unit to reduce

the search space. Furthermore, SQBC optimizes the subgraph isomorphism test

based on clique features. Extensive experiments over biological networks, RDF

dataset and synthetic graphs have shown that SQBC outperforms the most popular

competitors both in effectiveness and efﬁciency especially when the data graphs

are large and dense.

Keywords:

Algorithms, Large networks, Database, Graph theory, Subgraph isomorphism,

Index strategy

Corresponding author: Dr. Lei Zou, Institute of Computer Science and Technology, Peking

University, No.5 Yiheyuan Road Haidian District, Beijing, P.R.China, 100871.

Email: zoulei@pku.edu.cn

Preprint submitted to Information Sciences July 4, 2013

1. Introduction

Graph is fascinating and superior to other data structures to model complex

relationships among objects. For example, a chemical compound can be repre-

sented as a graph, where each vertex is an atom and each edge is a chemical

bond. The complex interactions among components in cells (e.g. proteins, genes,

metabolites) can also be modeled as graphs, such as pathways and protein-protein

interaction networks.

Recently, the growing popularity of biological networks has generated many

interesting graph data management problems, such as motif detection, pathway

ﬁnding and network alignment, among which, a basic operation is to search a

query graph over a large graph database, called subgraph search, which can as-

sist biologists to ﬁnd some interesting complexes and motifs in biological net-

works. However, the key challenge of subgraph search lies in its inherent hard-

ness (subgraph isomorphism is a NP-complete problem [32]) and large graph

sizes. PathGuide (http://www.pathguide.org/) contains 325 biological pathway

databases, most of which are large and growing rapidly.

There are two scenarios of subgraph queries. One is searching a query graph

over a large number of small graphs, and the other is searching a query graph over

a single large graph. For example, searching for chemical compounds contain-

ing a speciﬁc substructure associated with biological activity from a compound

database belongs to the former one, where each compound corresponds to a small

data graph. Given a structural motif, locating its occurrences over a large biologi-

cal network belongs to the latter scenario, which is the focus of this work.

Since the volume (amount of data), velocity (speed of data in and out) and

variety (range of data types and sources) of scientiﬁc and Web data are increasing

sharply [14], studying subgraph queries over large and dense graphs is meaningful

and has attracted extensive attention. For example, the RDF (Resource Descrip-

tion Framework) data model is a W3C standard to describe resources on the Web

and enables data exchange and richer integration [13]. In RDF, data items are rep-

resented in the form of triples, (subject, predicate, object). As a standard language

for querying RDF data, SPARQL is considered as one of the key technologies of

the semantic web. Figure 1(a) gives a query example, which retrieves the given

name and family name of a scientist, who was born in Germany, and whose spouse

was born in Hungary. In this SPARQL query, the “where” clause consists of triple

patterns that contain either variables or literals. Actually, each SPARQL query

can be represented by a graph [16]. The graph corresponding to this SPARQL

query is presented in Figure 1(b). As a result, any SPARQL query can be equiv-

select ?gn ?fn

where{?gn <givenNameOf> ?p.

?fn <familyNameOf> ?p.

?p <type> “scientist”.

?p <bornInLocation> ?city.

?city <locatedIn> “Germany”.

?p <marriedTo> ?s.

?s <bornInLocation> ?city2.

?city2 <locatedIn> “Hungary”. }

(a) A SPARQL query

?gn

?fn

hasFamilyName

hasGivenName

“scientist”

type

?city

isMarriedTo

?city2 “Hungray”

“Germany”

bornIn

locatedIn

(b) The graph corresponding to the SPARQL query

Figure 1: A SPARQL query and its corresponding graph.

alently transformed a subgraph query problem, which locates the subgraphs in

RDF data graph matching with the query graph. Besides the application in Se-

mantic Web mentioned above, studying the problem of subgraph query over large

graphs is useful and promising in social networks [33], bioinformatics [20], and

road networks [2] as well.

Subgraph isomorphism has been well studied for almost forty years, and many

classical algorithms have been proposed to solve this problem, such as ULMMAN

[32] and VF2 [4]. However, these methods do not work well in subgraph search

problem since they need to compute everything on the ﬂy. Therefore, the sub-

graph search problem has attracted tremendous interests in database community.

In order to speed up query processing, existing approaches adopt ﬁltering-and-

reﬁnement paradigm and the whole framework has two steps: ofﬂine and online.

Given a graph database, we ﬁrst build structural indexes in ofﬂine processing.

When a query graph is issued, structural indexes are utilized to prune false posi-

tives in graph databases. Speciﬁcally, in the ﬁrst scenario, data graphs that cannot

contain the query graph are eliminated. In the second scenario, some subgraphs

of the target large graph that cannot contain query graph are ﬁltered out to reduce

the search space for subgraph isomorphism.

In this paper, we propose a novel Subgraph Query technique Based on Clique

(see Deﬁnition 3) features (denoted as SQBC), which also follows the ﬁltering-

and-reﬁnement paradigm. It employs a hybrid index by considering both neigh-

borhood information and structural features. To summary, we make the following

contributions in this paper:

• We propose a new subgraph query algorithm over large and dense graphs.

• We exploit a hybrid index by considering both the neighborhood informa-

tion and structural features, and carefully design the vertex code and clique

code to strengthen the pruning power.

• We optimize the subgraph isomorphism test based on clique features.

• Extensive experiments over synthetic and real datasets have shown the ef-

fectiveness and efﬁciency of the proposed algorithm.

The remaining of this paper is organized as follows: Section 2 reviews the

related work on subgraph search. The preliminaries and problem deﬁnition are

introduced in Section 3. Section 4 presents the hybrid index, based on which an

effective and efﬁcient subgraph search algorithm is described in Section 5. In

Section 6, the experimental results are reported over synthetic and real datasets in

terms of efﬁciency. The analyses of the proposed method are discussed in Section

7, and Section 8 concludes this paper.

2. Related work

So far, many subgraph search algorithms have been proposed and their dif-

ferences lie in pruning strategies [5, 9, 7, 6, 17, 23, 24, 27, 35, 36, 37, 39, 34,

28, 20, 3, 43, 38, 42, 40]. A popular way to perform ﬁltering is to select struc-

tural features (e.g., paths, subtrees, subgraphs) as features, and occurrences of

these features in graph databases are recorded, like an inverted index. When a

query graph Q is given, all features in Q are enumerated and their occurrences

in G are utilized to ﬁnd matches of Q. In GraphGrep [7], all paths up to maxL

are enumerated as features. SING [20] follows the same method, but proposes

a compression technique to reduce the index size. gIndex [35] and FG-index [3]

propose to use frequent subgraphs as features instead of paths, since subgraphs

can provide larger pruning power. In order to reduce the search space, QuickSI

[23] uses the frequencies of tree features that appear in the graph database, and

determines an effective search order. However, these feature-based solutions do

not work well in a single large graph G, i.e., the speciﬁc problem addressed by

this paper. For example, it is costly to enumerate all paths in a large dense graph.

Mining frequent subgraphs from a large single graph is still an open problem in

data mining community [10, 41]. Therefore, existing features are not suitable for

large dense biological networks. Furthermore, most features are only designed

for pruning. They do not consider how to utilize features to speed up subgraph

isomorphism test except for GraphGrep.

Another index strategy is based on neighborhood structure around each ver-

tex. The rationale of these methods is as follows: According to the subgraph

isomorphism deﬁnition, each vertex u in query graph Q must have a mapping ver-

tex v in data graph G if G contains Q. Furthermore, the neighborhood structure

around u should also be preserved around v. Based on the intuition, some ver-

tices in G can be eliminated to reduce the search space for subgraph isomorphism

algorithms. For example, GCoding [43] computes spectral code for each vertex

by considering two-hop subgraph around the vertex. SPath [38] utilizes n-step

shortest paths around vertices as basic index units. NOVA [42] proposes a novel

vector index (nIndex) based on the the neighborhood label distribution of vertices.

However, these methods do not show satisfactory performance in large and dense

networks, because the n-step local structures around some high-degree vertices

are very large, which will lead to large ofﬂine computing overhead. SMS [40]

designs a vertex code for each vertex according to their neighborhoods, which is

lightweight. However, its pruning ability is limited due to the little local informa-

tion it captures.

In this paper, we propose to employ a hybrid index by considering both the

neighborhood information and structural features. First, we propose a simple yet

effective strategy to encode neighborhood structure around each vertex, which is

similar to that in SMS. Speciﬁcally, given a vertex v, we only consider its neighbor

labels and the degrees of the neighbors. Different from that in SMS, we incorpo-

rate the clique (see Deﬁnition 3) information into the signature to improve its

pruning ability. The lightweight encoding strategy facilitates both ofﬂine index

building and online pruning process in dense graphs. Compared with existing

approaches, experimental study shows that the pruning power of the lightweight

encoding strategy does not degrade signiﬁcantly.

Furthermore, we ﬁnd all maximal cliques (a subgraph where each pair of ver-

tices has an edge, formally deﬁned in Deﬁnition 3) in data graph G as features.

Obviously, if a query graph Q contains a clique, its matches also contain cliques.

Therefore, we only need to probe cliques and their neighborhood structures in

data graph G. Cliques in biological networks are of interest to biologists because

many different problems from bioinformatics have been modeled using cliques

[25, 22, 18]. For example, Samudrala and Moult [22] model protein structure

prediction as a problem of ﬁnding cliques in a graph whose vertices represent

positions of subunits of the protein. Moreover, “clique” features can be used to

optimize subgraph isomorphism check. It is easy to check if a query graph Q (or a

subgraph of Q) is subgraph isomorphic to a clique by a cheap set operation, based

on which, we optimize veriﬁcation process, i.e, subgraph isomorphism test.

剩余31页未读，继续阅读

评论收藏

内容反馈

weixin_38694343

粉丝: 3
资源: 915

SQBC: An efficient subgraph matching method over large and dense...

最新资源

SQBC: An efficient subgraph matching method over large and dense...

subgraph-matching

A survey of algorithms for dense subgraph discovery

一种改进的基于SURF特征匹配的图像拼接算法

基于优化采样的高分辨率非刚性密集匹配

KPTD-3216QBC-D(Ver.21B).pdf

起重机程序文件.pdf

基于CORDIC的反正弦和反余弦计算的FPGA实现

使用3DCNN和卷积LSTM进行手势识别学习时空特征

BA无标度网络中的SIR模型

基于三次贝塞尔曲线的类汽车曲率连续路径平滑

基于机器学习的设备剩余寿命预测方法综述

基于维纳过程的退化模型，具有递归过滤算法，可用于估计剩余使用寿命

基于FPGA的奇异值和特征值分解的快速实现。

磁悬浮系统自适应模糊PID控制器的设计

基于BP神经网络的人口预测

两轮平衡车的建模与控制研究

无人机协同目标的多无人机协同搜索方法

基于改进遗传算法的六自由度机器人时间最优轨迹规划

一种基于深度学习的机械臂抓取方法

基于深度神经网络的交通流量预测

一种去除ECG中基线漂移和工频干扰的高效滤波方法

适用于1-8GHz宽带应用的原始Vivaldi天线

基于稀疏贝叶斯学习的高效DOA估计方法

亮度保持和细节增强的红外图像增强方法

近场中的磁偶极子模型

最新资源