Abstract: The subgraph isomorphism problem is Non-deterministic Polynomial(NP) complete problem and the pivoted subgraph isomorphism is a special subgraph isomorphism problem. There are already many efficient subgraph isomorphism algorithms, but there is currently no GPU-based search algorithm for the pivoted subgraph isomorphism problem, and a large number of pivoted subgraph matching problems are solved by transforming the subgraph isomorphism algorithm. For the problem of unnecessary intermediate results, a GPU-based pivoted subgraph isomorphism algorithm was proposed. First, through a novel coding tree method, nodes were encoded by the combination of node label, degree and structural features of node neighbors. Query graph nodes in parallel on GPU were pruned, the size of search space tree generated by the data graph candidate node was significantly reduced; then, the candidate nodes of the query graph node were visited level by level, the unsatisfied nodes were filtered out; finally, the obtained subgraph was verified whether it is an isomorphic subgraph of the query graph, and the search of pivoted subgraph isomorphism can be accomplished efficiently. Experimental results show that compared with the GPU-friendly subgraph matching(GpSM) algorithm, the execution time of the algorithm is reduced by one-half, and it can efficiently perform the pivoted subgraph isomorphism search and has 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 the algorithm.

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

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

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