许子沧关于GPU上子图匹配算法的论文BUG: Balanced DFS-Based Subgraph Matching with a Reuse Strategy on GPUs 被GraphChallenge 2025录用。

 子图匹配是图分析领域中的一个基础问题，有着广泛的应用场景，如生物信息学、欺诈检测、社交网络和推荐系统等。在CPU上，尽管研究者探索了许多优化方案，在大规模数据集上进行子图匹配这一NP难的问题仍然难以有效实现。GPU以其大规模并行的计算能力和高速的内存带宽，为加速子图匹配计算提供了新的方向。然而，现存的GPU算法面临着诸多难题。以BFS为基础的算法虽然可以有效利用并行性能，却会产生大量中间结果超过GPU显存限制；而以DFS为基础的算法虽然只需有限的内存，却面临严重的负载不均和计算冗余。

本论文提出了两种方案来应对DFS为基础的子图匹配算法中的问题。一是引入任务卸载的机制来动态地平衡不同线程束之间工作负载。二是在该机制下实现symmetry-breaking和重用策略以减少冗余的集合求交操作。本论文用实验证明了这两种方案显著提高了算法的性能。