融合图神经网络的高效子图匹配算法  

Efficient Subgraph Matching Algorithm with Graph Neural Network

作　　者：薛欣 朱天晨 孙庆赟 周号益 李建欣[1,3] Xue Xin;Zhu Tianchen;Sun Qingyun;Zhou Haoyi;Li Jianxin(School of Computer Science and Engineering,Beihang University,Beijing 100191;School of Software,Beihang University,Beijing 100191;Beijing Advanced Innovation Center for Big Data and Brain Computing,Beijing 100191)

机构地区：[1]北京航空航天大学计算机学院,北京100191 [2]北京航空航天大学软件学院,北京100191 [3]北京市大数据与脑机智能高精尖创新中心,北京100191

出　　处：《计算机研究与发展》2025年第3期694-708,共15页Journal of Computer Research and Development

基　　金：国家杰出青年科学基金项目(62225202);国家自然科学基金青年科学基金项目(62202029);中国科协青年人才托举工程项目(2023QNRC001);中国人工智能学会-华为MindSpore学术奖励基金。

摘　　要：子图匹配是在大型目标图中找出给定查询子图的全部匹配位置,在社交网络、生物化学和认知科学等多个领域都具有关键意义.基于回溯搜索的子图匹配算法时间复杂度高,需要有效的剪枝策略减少运行时间.然而,现有启发式剪枝算法只能依据当前状态的粗略邻域信息做出结构冲突判断,使得大量无效状态难以被筛出,导致子图匹配的性能不佳.提出了一种高效、准确、自适应的融合图神经网络的子图匹配算法,通过图神经网络捕获细粒度邻域结构信息,生成全局结构关联,利用模型推理代替传统剪枝策略,估算剪枝概率.该算法能够在单次查询中有效利用全局信息,显著提升对无效状态的筛选效率.此外,还设计了一种数据采样机制,以缓解样本分布不均衡导致的网络训练崩溃问题.实验证明,以基于图神经网络的算法替代回溯式算法的剪枝策略,能够显著提高其搜索效率.Subgraph matching is an optimization problem in graph,which is to find all matching subgraphs of the query graph in a large target graph.Although subgraph matching is an NP-Hard problem,the problem is common in many fields such as social networks,biochemistry,and cognitive science.Backtracking searching algorithms for subgraph matching have high time complexity,and the pruning strategy is essential to reduce the operating time.However,complex expanding in the existing pruning strategy leads to high complexity of time and space.To balance the efficiency and the effectiveness,only limited neighborhood structure information can be used in conflicting judging,which lets lots of useless states pass the pruning judging and wastes time.An efficient,accurate,and adaptive subgraph matching algorithm is proposed.The algorithm captures the detail structure of the whole graph by graph neural network,builds structure connections,and generates pruning possibilities for all candidate searching states.It replaces complex expanding pruning method with inferring by the neural network model to rapidly estimate the probability of pruning during searching.A data sampling mechanism is designed to alleviate the problem of network training collapse.Experiments show that using our pruning method in traditional backtracking search can improve search efficiency.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]