Paper Info
Title
Subgraph Matching with Set Similarity in a Large Graph Database
Abstract
In real-world graphs such as social networks, Semantic Web and biological networks, each vertex usually contains rich information, which can be modeled by a set of tokens or elements. In this paper, we study a subgraph matching with set similarity (SMS2) query over a large graph database, which retrieves subgraphs that are structurally isomorphic to the query graph, and meanwhile satisfy the condition of vertex pair matching with the (dynamic) weighted set similarity. To efficiently process the SMS2 query, this paper designs a novel lattice-based index for data graph, and lightweight signatures for both query vertices and data vertices. Based on the index and signatures, we propose an efficient two-phase pruning strategy including set similarity pruning and structure-based pruning, which exploits the unique features of both (dynamic) weighted set similarity and graph topology. We also propose an efficient dominating-set-based subgraph matching algorithm guided by a dominating set selection algorithm to achieve better query performance. Extensive experiments on both real and synthetic datasets demonstrate that our method outperforms state-of-the-art methods by an order of magnitude.
Year
DOI
Venue
2015
10.1109/TKDE.2015.2391125
Knowledge and Data Engineering, IEEE Transactions  
Keywords
Field
DocType
graph database,graph matching,index,set similarity,lattices,indexes,upper bound,proteins,pattern matching
Data mining,Hypercube graph,Computer science,Vertex (graph theory),Theoretical computer science,Artificial intelligence,Subgraph isomorphism problem,Feedback vertex set,Dominating set,Pattern recognition,Graph factorization,Matching (graph theory),Factor-critical graph
Journal
Volume
Issue
ISSN
PP
99
1041-4347
Citations 
PageRank 
References 
5
0.40
37
Authors
4
Name
Order
Citations
PageRank
Liang Hong119333.79
Lei Zou2116168.43
Xiang Lian3933.86
Philip S. Yu4306703474.16