曾立关于 GPU 加速超大规模子图同构算法的论文 (SGSI: A Scalable GPU-friendly Subgraph Isomorphism Algorithm) 被 TKDE 2022 录用。

子图同构常用于金融风控、商业推荐和电信网络运维等应用场景中。由于真实图的规模高达十亿级，子图同构的性能往往是系统瓶颈所在。通过基于 GPU 体系结构的建模和优化，我们将子图同构算法在超大规模图上的性能提升了3倍以上。

已有的 GPU 子图同构算法都是基于两阶段边拼接，并采用图划分的方式来处理超大图，GPU每次只处理一个分区。但对于跨分区的匹配，需要在各个分区间进行表拼接，因此极其耗时。此外，它们的 GPU显存占用极高，因此可扩展性有限。

在这篇论文中，我们提出了一种高可扩展的GPU子图同构算法 SGSI。SGSI使用基于点拼接的新策略，无须进行两次拼接过程，并提出PCSR结构以更好地在GPU上存储和访问带边标签的图。对于超大图，SGSI用细粒度的结构划分取代图划分，从而在CPU-GPU间更好地传输和计算。同时，通过对GPU各层级计算资源的建模，SGSI设计代价模型以选择最佳的负载均衡策略。在真实图和人工图上的一系列实验证明了 SGSI 算法的高性能和可扩展性，SGSI 不但比现有方法快3~15倍，而且可以有效处理包含数十亿条边的图。