杨凌林关于 top-k 子图匹配的论文《Accelerating Top-k Subgraph Matching with Topology-Aware Pruning and Parallel Processing》被 TKDE 接收。

给定一个查询图，top-k 子图匹配旨在数据图中找到最多 k 个匹配结果，并根据用户定义的评分函数赋予最高分数。该问题在知识图谱、社交网络等多个领域具有广泛应用。由于搜索空间巨大，现有方法在大图上的效率仍不够理想。本文提出了一种高效的串行算法 PTAB，用于解决 top-k 子图匹配问题。该方法通过拓扑感知的子空间分数上界来探索经过高效剪枝的搜索空间，这些上界基于一种新的邻域索引计算得到，该索引存储了每个节点在一定跳数邻域内的属性取值范围。此外，PTAB 还集成了代价感知的根节点选择策略，优先选择能够使搜索过程最大程度利用邻域索引剪枝能力的查询节点。同时，我们采用一种新的边切分策略来处理带有环路的通用查询图。我们还将 PTAB 扩展为并行版本 PTABP，通过多线程技术和增强的剪枝技术进一步提升性能。在真实及合成数据集上的实验结果表明，我们的方法优于现有方法。