Parallel pivoted subgraph matching with multiple coding trees on GPU

doi:10.11772/j.issn.1001-9081.2021071219

Abstract

Abstract:

The subgraph isomorphism problem is a Non-deterministic Polynomial （NP）-complete problem， and the pivoted subgraph isomorphism is a special subgraph isomorphism problem. There are many existing efficient subgraph isomorphism algorithms， but there is no GPU-based search algorithm for the pivoted subgraph isomorphism problem at present， and a large number of unnecessary intermediate results will be generated when the pivoted subgraph matching problem is solved by the existing subgraph isomorphism algorithms. Therefore， a GPU-based pivoted subgraph isomorphism algorithm was proposed. Firstly， through a novel coding tree method， nodes were encoded by the combination of node labels， degrees and the structural features of node neighbors. And the query graph nodes were pruned on GPU in parallel， so that the size of search space tree generated by the data graph candidate nodes was significantly reduced. Then， the candidate nodes of the query graph node were visited level by level， and the unsatisfied nodes were filtered out. Finally， the obtained subgraph was verified whether it was an isomorphic subgraph of the query graph， and the search of pivoted subgraph isomorphism was realized efficiently. Experimental results show that compared with GPU-friendly Subgraph Matching （GpSM） algorithm， the proposed algorithm has the execution time reduced by one-half， and the proposed algorithm can efficiently perform the pivoted subgraph isomorphism search with scalability. The proposed pivoted subgraph isomorphism algorithm can reduce the time required to solve the pivoted subgraph isomorphism problem， while reducing GPU memory consumption and improving the performance of algorithm.

Key words: GPU, coding tree, pivoted subgraph isomorphism, subgraph isomorphism, parallel acceleration

摘要：

子图同构问题是非确定多项式（NP）完全问题，而轴心子图同构是一种特殊的子图同构问题。针对现在已经有许多高效的子图同构算法，然而对于轴心子图同构问题目前并没有基于GPU的搜索算法，且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题，提出了一种基于GPU的轴心子图同构算法。首先，通过一种新颖的多编码树方式，利用节点的标签、度以及节点邻居的结构特征的组合对节点进行编码，并在GPU上对查询图节点并行地进行剪枝，从而明显地减小数据图候选节点所生成的搜索空间树的尺寸；然后，逐层访问查询图节点的候选节点，过滤掉不满足的节点；最后，验证得到的子图是否是查询图的同构子图，从而高效地完成轴心子图同构搜索。实验结果表明，与GPU友好子图匹配（GpSM）算法相比，所提算法的执行时间降低了二分之一，且该算法能够高效地执行轴心子图同构搜索并且具有可扩展性。所提轴心子图同构算法可以减少解决轴心子图同构问题所需的时间，同时降低了GPU内存消耗，提升了算法的性能。

关键词: GPU, 编码树, 轴心子图同构, 子图同构, 并行加速

CLC Number:

TP391.3

Yang WANG, Shijie JIANG, Yucong CAO, Chuanwen LI. Parallel pivoted subgraph matching with multiple coding trees on GPU[J]. Journal of Computer Applications, 2022, 42(1): 132-139.

汪洋, 江世杰, 曹宇聪, 李传文. 多编码树GPU并行轴心子图匹配[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 132-139.

Figures/Tables 10

Fig.1 Query graph and data graph

Fig.2 Two-level tree structures generated by query node u1 and data nodes v1,v5

Tab.1 Thirty labels hashing into label buckets to generate 2 trees

标签范围	桶ID	二进制数
1~10	1	01
11~20	2	10
21~30	3	11

Fig.3 Label trees generated by query node u1 and data nodes v1,v5

Fig.4 Node coding of query graph Q and data graph G

Fig.5 Validation process of one pivoted candidate node

Fig.6 Filtering ability to candidate nodes with different tree numbers on Human dataset

Fig. 7 Filtered candidate nodes on Human dataset

Fig. 8 Filtering time of algorithms on different datasets

Fig. 9 Total execution time of algorithms on different datasets

References 21

1	ZHANG S J， HU M， YANG J. TreePi： a novel graph indexing method［C］// Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering. Piscataway： IEEE， 2007： 966-975. 10.1109/icde.2007.368955
2	YAN X F， YU P S， HAN J W. Graph indexing： a frequent structure-based approach［C］// Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2004： 335-346. 10.1145/1007568.1007607
3	JIANG H L， WANG H X， PHILIP S Y， et al. GString： a novel approach for efficient search in graph databases［C］// Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering. Piscataway： IEEE， 2007： 566-575. 10.1109/icde.2007.367902
4	CHO Y R， ZHANG A D. Predicting protein function by frequent functional association pattern mining in protein interaction networks［J］. IEEE Transactions on Information Technology in Biomedicine， 2010， 14（1）： 30-36. 10.1109/titb.2009.2028234
5	ELSEIDY M， ABDELHAMID E， SKIADOPOULOS S， et al. GraMi： frequent subgraph and pattern mining in a single large graph［J］. Proceedings of the VLDB Endowment， 2014， 7（7）： 517-528. 10.14778/2732286.2732289
6	HAN J L， WEN J R. Mining frequent neighborhood patterns in a large labeled graph［C］// Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York： ACM， 2013： 259-268. 10.1145/2505515.2505530
7	ABDELHAMID E， ABDELAZIZ I， KHAYYAT Z， et al. Pivoted subgraph isomorphism： the optimist， the pessimist and the realist［C］// Proceedings of the 22nd International Conference on Extending Database Technology. ［S.l.］： OpenProceedings.org， 2019： 361-372.
8	SHANG H C， ZHANG Y， LIN X M， et al. Taming verification hardness： an efficient algorithm for testing subgraph isomorphism［J］. Proceedings of the VLDB Endowment， 2008， 1（1）： 364-375. 10.14778/1453856.1453899
9	HAN W S， LEE J， LEE J H. Turbo_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. New York： ACM， 2013： 337-348. 10.1145/2463676.2465300
10	ZHANG S J， LI S R， YANG J. GADDI： distance index based subgraph matching in biological networks［C］// Proceedings of the 12th International Conference on Extending Database Technology： Advances in Database Technology. New York： ACM， 2009： 192-203. 10.1145/1516360.1516384
11	LEE J， HAN W S， KASPEROVICS R， et al. An in-depth comparison of subgraph isomorphism algorithms in graph databases［J］. Proceedings of the VLDB Endowment， 2012， 6（2）： 133-144. 10.14778/2535568.2448946
12	徐周波，李珍，刘华东，等. 基于邻居信息聚合的子图同构匹配算法［J］. 计算机应用， 2021， 41（1）：43-47. 10.11772/j.issn.1001-9081.2020060935
	XU Z B， LI Z， LIU H D， et al. Subgraph isomorphism matching algorithm based on neighbor information aggregation［J］. Journal of Computer Applications， 2021， 41（1）：43-47. 10.11772/j.issn.1001-9081.2020060935
13	MOORMAN J D， CHEN Q Y， TU T K， et al. Filtering methods for subgraph matching on multiplex networks［C］// Proceedings of the 2018 IEEE International Conference on Big Data. Piscataway： IEEE， 2018： 3980-3985. 10.1109/bigdata.2018.8622566
14	LIN X J， ZHANG R， WEN Z Y， et al. Efficient subgraph matching using GPUs［C］// Proceedings of the 2014 Australasian Database Conference， LNCS8506. Cham： Springer， 2014： 74-85.
15	SUN Z， WANG H Z， WANG H X， et al. Efficient subgraph matching on billion node graphs［J］. Proceedings of the VLDB Endowment， 2012， 5（9）： 788-799. 10.14778/2311906.2311907
16	BONNICI V， GIUGNO R， BOMBIERI N. An efficient implementation of a subgraph isomorphism algorithm for GPUs［C］// Proceedings of the 2018 IEEE International Conference on Bioinformatics and Biomedicine. Piscataway： IEEE， 2018： 2674-2681. 10.1109/bibm.2018.8621444
17	TRAN H N， KIM J J， HE B S. Fast subgraph matching on large graphs using graphics processors［C］// Proceedings of the 2015 International Conference on Database Systems for Advanced Applications， LNCS9049. Cham： Springer， 2015： 299-315.
18	ZENG L， ZOU L， ÖZSU M T， et al. GSI： GPU-friendly subgraph isomorphism［C］// Proceedings of the 2020 IEEE 36th International Conference on Data Engineering. Piscataway： IEEE， 2020： 1249-1260. 10.1109/icde48307.2020.00112
19	ZOU L， CHEN L， YU J X， et al. A novel spectral coding in a large graph database［C］// Proceedings of the 11th International Conference on Extending Database Technology： Advances in Database Technology. New York： ACM， 2008： 181-192. 10.1145/1353343.1353369
20	ZHENG W G， ZOU L， ZHAO D Y. Answering subgraph queries over large graphs［C］// Proceedings of the 2011 International Conference on Web-Age Information Management， LNCS6897. Berlin： Springer， 2011： 390-402.
21	SUN S X， LUO Q. In-memory subgraph matching： an in-depth study［C］// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2020： 1083-1098. 10.1145/3318464.3380581

[1]	Rui ZHANG, Pengyun ZHANG, Meirong GAO. Self-optimized dual-modal multi-channel non-deep vestibular schwannoma recognition model [J]. Journal of Computer Applications, 2024, 44(9): 2975-2982.
[2]	Runlian ZHANG, Mi ZHANG, Xiaonian WU, Rui SHU. Differential property evaluation method based on GPU for large-state cryptographic S-boxes [J]. Journal of Computer Applications, 2024, 44(9): 2785-2790.
[3]	Tao JIANG, Zhenyu LIANG, Ran CHENG, Yaochu JIN. GPU-accelerated evolutionary optimization of multi-objective flow shop scheduling problems [J]. Journal of Computer Applications, 2024, 44(5): 1364-1371.
[4]	Xiang LIU, Bei HUA, Fei LIN, Hongyuan WEI. Design and implementation of component-based development framework for deep learning applications [J]. Journal of Computer Applications, 2024, 44(2): 526-535.
[5]	Jinxing TU, Zhixiong LI, Jianqiang HUANG. Dynamic partition algorithm for diagonal sparse matrix vector multiplication based on GPU [J]. Journal of Computer Applications, 2024, 44(11): 3521-3529.
[6]	Li LIU, Changbo CHEN. Band sparse matrix multiplication and efficient GPU implementation [J]. Journal of Computer Applications, 2023, 43(12): 3856-3867.
[7]	Jingwen CAI, Yongzhuang WEI, Zhenghong LIU. GPU-based method for evaluating algebraic properties of cryptographic S-boxes [J]. Journal of Computer Applications, 2022, 42(9): 2750-2756.
[8]	Qidi XU, Zhenghong LIU, Lin ZHENG. Low density parity check code decoding acceleration technology based on GPU [J]. Journal of Computer Applications, 2022, 42(12): 3841-3846.
[9]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[10]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[11]	Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster [J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.
[12]	XU Zhoubo, LI Zhen, LIU Huadong, LI Ping. Subgraph isomorphism matching algorithm based on neighbor information aggregation [J]. Journal of Computer Applications, 2021, 41(1): 43-47.
[13]	FANG Guokang, LI Jun, WANG Yaoru. Real-time face recognition on ARM platform based on deep learning [J]. Journal of Computer Applications, 2019, 39(8): 2217-2222.
[14]	HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system [J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.
[15]	WU Xuchen, PIAO Chunhui, JIANG Xuehong. Siting model of electric taxi charging station based on GPU parallel computing [J]. Journal of Computer Applications, 2019, 39(10): 3071-3078.