GPU acceleration of subgraph isomorphism search in large scale graph

Abstract

A novel framework for parallel subgraph isomorphism on GPUs is proposed, named GPUSI, which consists of GPU region exploration and GPU subgraph matching. The GPUSI iteratively enumerates subgraph instances and solves the subgraph isomorphism in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, a task-queue based method and the virtual-CSR graph structure are used to balance the workload among warps, and warp-centric programming model is used to balance the workload among threads in a warp. The prototype of GPUSI is implemented, and comprehensive experiments of various graph isomorphism operations are carried on diverse large graphs. The experiments clearly demonstrate that GPUSI has good scalability and can achieve speed-up of 1.4–2.6 compared to the state-of-the-art solutions.

Keywords

parallel graph isomorphism / GPU / backtrack paradigm

References

[1] HEH-h, SINGHA KGraphs-at-a-time: Query language and access methods for graph databases [C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 2008USAACM405-418

[2] ZASLAVSKIYM, BACHF, VERTJ P. Global alignment of protein–protein interaction networks by graph matching methods [J]. Bioinformatics, 2009, 25(12): 1259-1267

[3] DESHPANDEM, KURAMOCHIM, WALEN, KARYPISG. Frequent substructure-based approaches for classifying chemical compounds [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(8): 1036-1050

[4] OHLRICHM, EBELINGC, GINTINGE, SATHERLSubGemini: Identifying subcircuits using a fast subgraph isomorphism algorithm [C]// Proceedings of the 30th international Design Automation Conference, 1993USAACM31-37

[5] YANX-f, YUP S, HANJ-weiGraph indexing: A frequent structure-based approach [C]// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004USAACM335-346

[6] SHANGH-c, ZHANGY, LINX-m, YUJ X. Taming verification hardness: An efficient algorithm for testing subgraph isomorphism [J]. Proceedings of the VLDB Endowment, 2008, 1(1): 364-375

[7] NVIDIAC. Compute unified device architecture programming guide [M]. Santa Clara, CA: NVIDIA Corporation, 20103-5

[8] CORDELLAL P, FOGGIAP, SANSONEC, VENTOM. A (sub) graph isomorphism algorithm for matching large graphs [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10): 1367-1372

[9] ZHAOP-x, HANJ-wei. On graph query optimization in large networks [J]. Proceedings of the VLDB Endowment, 2010, 3: 340-351

[10] ZHANGS-j, LIS-r, YANGJiongGADDI: Distance index based subgraph matching in biological networks [C]// Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, 2009USAACM192-203

[11] HANW S, LEEJ, LEEJ HTurbo iso: Towards ultrafast and robust subgraph isomorphism search in large graph databases [C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013USAACM337-348

[12] SHAOB, WANGH-x, LIY-taoTrinity: A distributed graph engine on a memory cloud [C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013USAACM505-516

[13] JENKINSJ, ARKATKARI, OWENSJ D A, SAMATOVAN FLessons learned from exploring the backtracking paradigm on the GPU [C]// Euro-Par 2011 Parallel Processing, 2011BerlinSpringer425-437

[14] HONGS, KIMS K, OGUNTEBIT, OLUKOTUNK. Accelerating CUDA graph algorithms at maximum warp [J]. ACM SIGPLAN Notices, 2011, 46(8): 267-276

[15] HWUWGPU Computing Gems Emerald Edition [M], 2011105-113

[16] SUNZ, WANGH-z, WANGH-x, SHAOB, LIJ-zhong. Efficient subgraph matching on billion node graphs [J]. Proceedings of the VLDB Endowment, 2012, 5(9): 788-799

[17] LINX-j, ZHANGR, WENZ-y, WANGH-z, QIJianzhongEfficient Subgraph Matching Using GPUs [M]// Databases Theory and Applications, 2014BerlinSpringer74-85

[18] LEEJ, HANW S, KASPEROVICSR, LEEJ H. An in-depth comparison of subgraph isomorphism algorithms in graph databases [J]. Proceedings of the VLDB Endowment, 2012, 6(2): 133-144