计算机研究与发展

作者：薛欣,朱天晨,孙庆赟,周号益,李建欣,

关键词：子图匹配, 图神经网络, 回溯式算法, 组合优化, 注意力机制,

子图匹配是在大型目标图中找出给定查询子图的全部匹配位置，在社交网络、生物化学和认知科学等多个领域都具有关键意义.基于回溯搜索的子图匹配算法时间复杂度高，需要有效的剪枝策略减少运行时间.然而，现有启发式剪枝算法只能依据当前状态的粗略邻域信息做出结构冲突判断，使得大量无效状态难以被筛出，导致子图匹配的性能不佳.提出了一种高效、准确、自适应的融合图神经网络的子图匹配算法，通过图神经网络捕获细粒度邻域结构信息，生成全局结构关联，利用模型推理代替传统剪枝策略，估算剪枝概率.该算法能够在单次查询中有效利用全局信息，显著提升对无效状态的筛选效率.此外，还设计了一种数据采样机制，以缓解样本分布不均衡导致的网络训练崩溃问题.实验证明，以基于图神经网络的算法替代回溯式算法的剪枝策略，能够显著提高其搜索效率.

来源：2025年第3期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2025年第3期