Top-k subgraph matching query in a large graph

ABSTRACT

Recently, due to its wide applications, subgraph search has attracted a lot of attention from database and data mining community. Sub-graph search is defined as follows: given a query graph Q, we report all data graphs containing Q in the database. However, there is little work about sub-graph search in a single large graph, which has been used in many applications, such as biological network and social network.

In this paper, we address top-k sub-graph matching query problem, which is defined as follows: given a query graph Q, we locate top-k matchings of Q in a large data graph G according to a score function. The score function is defined as the sum of the pairwise similarity between a vertex in Q and its matching vertex in G. Specifically, we first design a balanced tree (that is G-Tree) to index the large data graph. Then, based on G-Tree, we propose an efficient query algorithm (that is Ranked Matching algorithm). Our extensive experiment results show that, due to efficiency of pruning strategy, given a query with up to 20 vertices, we can locate the top-100 matchings in less than 10 seconds in a large data graph with 100K vertices. Furthermore, our approach outperforms the alternative method by orders of magnitude.

REFERENCES

• 1: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 2: D. Cai, Z. Shao, X. He, X. Yan, and J. Han. Community mining from multi-relational networks. In PKDD, 2005.
• 3: James Cheng , Yiping Ke , Wilfred Ng , An Lu, Fg-index: towards verification-free query processing on graph databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247574]
• 4: D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. IJPRAI, 18(3), 2004.
• 5: Luigi P. Cordella , Pasquale Foggia , Carlo Sansone , Mario Vento, A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.10, p.1367-1372, October 2004 [doi>10.1109/TPAMI.2004.75]
• 6: J. H. D. W. Williams and W. Wang. Graph database indexing using structured graph decomposition. In ICDE, 2007.
• 7: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 8: S. Fortin. The graph isomorphism problem. Department of Computing Science, University of Alberta, 1996.
• 9: P. Y. H. Jiang, H. Wang and S. Zhou. Gstring: A novel approach for efficient search in graph databases. In ICDE, 2007.
• 10: T. R. Hagadone. Molecular substructure similarity searching: Efficient retrieval in two-dimensional structure databases. J.Chem. Inf. Comput. Sci, 32, 1992.
• 11: Huahai He , Ambuj K. Singh, Closure-Tree: An Index Structure for Graph Queries, Proceedings of the 22nd International Conference on Data Engineering, p.38, April 03-07, 2006 [doi>10.1109/ICDE.2006.37]
• 12: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 13: Michihiro Kuramochi , George Karypis, Finding Frequent Patterns in a Large Sparse Graph*, Data Mining and Knowledge Discovery, v.11 n.3, p.243-271, November 2005 [doi>10.1007/s10618-005-0003-9]
• 14: Vincent Lacroix , Cristina G. Fernandes , Marie-France Sagot, Motif Search in Graphs: Application to Metabolic Networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.4, p.360-368, October 2006 [doi>10.1109/TCBB.2006.55]
• 15: A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, 2001.
• 16: E. Ravasz and A.-L. Barabasi. Hierarchical organization in complex networks. Physical Review E, 67, 2003.
• 17: A. SF, G. W, M. W, M. EW, and L. DJ. Basic local alignment search tool. J Mol Biol., 215(3), 1990.
• 18: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 19: Silke Trißl , Ulf Leser, Fast and practical indexing and querying of very large graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247573]
• 20: D. J. Watts. Six Degrees:The Science of a Connected Age. W. W. Norton & Company, 2004.
• 21: P. Willett. Chemical similarity searching. J. Chem. Inf. Comput. Sci, 38(6), 1998.
• 22: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]
• 23: Q. Yang and S. hoi Sze. Path matching and graph matching in biological networks. J Comput Biol., 14(1), 2007.
• 24: S. Zhang, M. Hu, and J. Yang. Treepi: A novel graph indexing method. In ICDE, 2007.
• 25: Peixiang Zhao , Jeffrey Xu Yu , Philip S. Yu, Graph indexing: tree + delta <= graph, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Experimentation, Performance

Keywords:
graph database, index, top-k matching