多编码树GPU并行轴心子图匹配  

Parallel pivoted subgraph matching with multiple coding trees on GPU

作　　者：汪洋 江世杰 曹宇聪 李传文 WANG Yang;JIANG Shijie;CAO Yucong;LI Chuanwen(School of Computer Science and Engineering,Northeastern University,Shenyang Liaoning 110169,China)

机构地区：[1]东北大学计算机科学与工程学院,沈阳110169

出　　处：《计算机应用》2022年第1期132-139,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61872071)。

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

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

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]