首页|期刊导航|桂林电子科技大学学报|一种新的多子图匹配符号算法

一种新的多子图匹配符号算法OA

A new symbolic algorithm for multiple subgraph matching

中文摘要英文摘要

针对多子图匹配查询中两两相似性检测的时间复杂度高以及存储查询中间结果的空间复杂度高的问题,提出了一种新的多子图匹配符号算法.通过引入图神经网络技术对查询图集合进行预分组,降低图相似性检测复杂度;利用代数决策图对查询图和数据图进行存储表示降低存储空间复杂度.为进一步提高有效共享子图检测以及查询顺序的生成的效率,提出了一种新型最大公共连通子图算法.最后,利用改进的子图匹配符号算法求解多子图匹配问题.实验结果表明,与多子图同构查询优化算法相比,所提的多子图匹配符号算法有效提高了多子图匹配的求解效率.

To address the high computational cost of pairwise graph similarity computation and the large memory overhead caused by storing intermediate query results in multi-subgraph matching,an efficient symbolic algorithm is proposed.Graph neural net-work(GNN)techniques are employed to pre-cluster query graphs and data graphs,thereby reducing the computational complexity of pairwise graph similarity computation.Furthermore,algebraic decision diagrams(ADDs)are adopted to compactly represent query graph sets and data graphs,thereby reducing memory consumption.To further improve shared subgraph detection efficiency and op-timize query ordering,a novel maximum common connected subgraph(MCCSG)algorithm is developed.Finally,an improved sub-graph matching algorithm,termed SSMGNN-MQO,is designed to solve the multi-subgraph matching problem.Experimental re-sults demonstrate that the proposed method achieves significantly higher matching efficiency than the existing MQO-based sub-graph isomorphism search method.

龙广兴;徐周波;王嘉鑫

桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004

信息技术与安全科学

多查询优化子图同构代数决策图图神经网络图匹配

multi-query optimizationsubgraph isomorphismalgebraic decision diagramgraph neural networkgraph matching

《桂林电子科技大学学报》 2026 (3)

295-302,8

国家自然科学基金(61762027)

10.16725/j.1673-808X.202349

评论